New join processing using a multidimensional dynamic file organization

This paper proposes a new algorithm for processing joins (called the MLGF-J oin) for the relations indexed by the multilevel grid file(MLGF), a multidi mensional dynamic file organization. The MLGF-Join uses the domain space pa rtition maintained in the directory of the MLGF. The MLGF-Join can process a join with one scan of the relations to be joined, assuming a main memory buffer is available that is sufficiently large for a range-oriented subjoin . Besides, the MLGF-Join does not require the costly preprocessing such as sorting in the sort-merge join algorithm and domain partitioning in the has h join algorithm. We also discuss the advantages of the MLGF-Join over othe rs based on multidimensional dynamic file organizations such as the grid fi le, K-D tree, and multikey hashing.