Digital Symposium Collection 2000

The Bulk Index Join: A Generic Approach to Processing Non-Equijoins J. van den Bercken, B. Seeger,, and P. Widmayer   View Paper (PDF)   Return to Poster Session 2: Interoperable Databases Abstract Efficient join algorithms have been developed for processing different types of non-equijoins like spatial join, band join, temporal join or similarity join. Each of these algorithms is tailor-cut for a specific type of join, and a generalization of these algorithms to other join types is not obvious. We present an efficient algorithm called bulk index join that can be easily applied to a broad class of non-equijoins. Similar to the well-known index nested-loops join algorithm, the bulk index join probes the records of the outer relation against the inner relation by using a preexisting tree-based index structure. In order to support the index lookups efficiently, the nodes of the tree are visited in a top-down fashion. For each node, all of its assigned queries are distributed among its qualifying child nodes in bulk. The implementation of our algorithm only requires a small set of routines generally available in tree-based index structures. In our experiments, the so-called band join serves as an example. It is shown that probing in bulk reduces the I/O cost of the index nested-loops join up to two orders of magnitude. Copyright(C) 2000 ACM