Heuristics for Join Processing Indexes
R Edward · 1989
Finding efficient procedures for implementing relational database operations, such as the join, is an important database prob- lem. In this paper, we examine join processing when the access paths available are nonclustered indexes on the joining attribute(s) for both relations involved in the join. We use a bipartite graph model to rep- resent the pages from the two relations which contain tuples that are to be joined. We are interested in minimizing the number of page ac- cesses needed to compute a join in our database environment. We ex- plore this problem from two perspectives. The first is to reduce the maximum buffer size so that no page is accessed more than once and the second is to reduce the number of page accesses for a fixed buffer size. We have developed heuristics for these problems and include per- formance comparisons of these heuristics and another method which recently appeared in the literature. The results show that one partic- ular heuristic performs very well for addressing the problem from either perspective.