PlugJoin: An Easy-to-Use Generic Algorithm for Efficiently Processing Equi and Non-equi Joins

摘要

This paper present Plug&Join, a new generic algorithm for efficiently processing a broad class of differnet join types in extensible database systems. Depending on the join predicate Plug&Join is called with a suitable type of index structure as a parameter. If the inner relation fits in memory, the algorithm builds a memory resident index of the desired type on the inner relation and prbes all tuples all tuples of the outer relation against the index. Otherwise, a memory resident index is created by sampling the inner relation. The index is then used as a partitioning function for both relations.