Abstract
A join-index is a data structure used for processing join queries in databases. Join-indices use precomputation techniques to speed up online query processing and are useful for data sets which are updated infrequently. The I/O cost of join computation using a join-index with limited buffer space depends primarily on the page-access sequence used to fetch the pages of the base relations. Given a join-index, we introduce a suite of methods based on clustering to compute the joins. We derive upper bounds on the length of the page-access sequences. Experimental results with Sequoia 2000 data sets show that the clustering method outperforms existing methods based on sorting and online-clustering heuristics.
Original language | English |
---|---|
Pages (from-to) | 1400-1421 |
Number of pages | 22 |
Journal | IEEE Transactions on Knowledge and Data Engineering |
Volume | 14 |
Issue number | 6 |
DOIs | |
State | Published - Nov 2002 |
Externally published | Yes |
Keywords
- Join index
- Join processing
- Optimal page access sequence
- Spatial join