Access path optimization in relational joins

Access path optimization in relational joins

0.00 Avg rating0 Votes
Article ID: iaor199917
Country: United States
Volume: 7
Issue: 3
Start Page Number: 257
End Page Number: 268
Publication Date: Jun 1995
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: graphs
Abstract:

The objective of access path optimization in relational joins is to minimize the number of pages accessed in performing a join, since the cost of data retrieval from disk accounts for most of the join processing costs. We develop an efficient approach to access path optimization by modeling an access path as a tree traversal process. Two join algorithms are developed using this model. The access path is stored as a compact index relation, which requires absolutely minimal storage. The join is easily materialized by reading the index relation sequentially, and performing the operations coded in its tuples in their serial order. The proposed approach is shown to result in globally minimal page accesses in certain classes of joins. Using a detailed probabilistic analysis and computational study, the proposed approach is shown to be much superior to the state-of-the-art join optimization methods for a general class of joins.

Reviews

Required fields are marked *. Your email address will not be published.