Improving temporal joins using histograms

Inga Sitzmann, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

8 Citations (Scopus)


Histograms are used in most commercial database systems to estimate query result sizes and evaluation plan costs. They can also be used to optimize join algorithms. In this paper, we consider how to use histograms to improve the join processing in temporal databases. We define histograms for temporal data and a temporal join algorithm that makes use of this histogram information. The join algorithm is a temporal partition-join with dynamic buffer allocation. Histogram information is used to determine partition boundaries that maximize overall buffer usage. We compare the performance of this join algorithm to temporal join evaluation strategies that do not use histograms, such as a partition-based algorithm based on sampling and a partition-join using the Time Index, an index structure for temporal data. The results demonstrate that the temporal partition-join is substantially improved through the incorporation of histogram information, showing significantly better performance than the sampling-based algorithm and achieving equivalent performance to the Time Index join without requiring an index.

Original languageEnglish
Title of host publicationDatabase and Expert Systems Applications - 11th International Conference, DEXA 2000, Proceedings
EditorsNorman Revell, Mohamed Ibrahim, Josef Kung
Number of pages11
ISBN (Print)9783540679783
Publication statusPublished - 1 Jan 2000
Externally publishedYes
EventInternational Conference on Database and Expert Systems Applications 2000 - London, United Kingdom
Duration: 4 Sep 20008 Sep 2000
Conference number: 11th (Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Database and Expert Systems Applications 2000
Abbreviated titleDEXA 2000
CountryUnited Kingdom
Internet address

Cite this