Optimizing the cost of relational join queries
Farshad A. Fotouhi · Michigan State University Libraries · 1988
The join operation is one of the most time consuming operations in a relational database system because it requires a large amount of cross referencing between tuples of different relations. Therefore, the efficiency of the join operation has a deterministic effect on the system performance. The best method for performing join depends, in general, on the access methods available, the parameters of the relations involved, and the context in which the query is presented. The objective of this thesis is to determine optimal strategies for performing join for a given set of constraints and assumptions. Here, the theoretical lower bound on the number of disk I/Os is achieved. Both join-only queries and queries involving restrictions, projections and join are considered. Here, the existing join algorithms are classified into Relation-Scan, Index-Scan, and Hybrid classes. This classification is based on the availability and use of indices on the join attribute values. This research will show that each class of algorithms performs best for a range of parameter values. It is shown that the relation-scan class of algorithms performs best when all or most of the tuples of the joining relations participate in the join. For the index-scan class of algorithms, several graph models are proposed in order to show that the optimization problem for these algorithms is NP-hard. Therefore, a heuristic algorithm with linear time complexity is given. For the hybrid class, several algorithms which are based on preprocessing a new auxiliary data structure, called the Partial-Relations, are proposed. It is shown that for a wide range of parameter values the proposed algorithms perform better than the best available algorithms of the other two classes.