Bypassing Joins in Disjunctive Queries

The bypass technique, which was formerly restricted to selections only [KMPS94], is extended to join operations. Analogous to the selection case, the join operator may generate two output streams---the join result and its complement---whose subsequent operator sequence is optimized individually. By extending the bypass technique to joins, several problems have to be solved. (1) An algorithm for exhaustive generation of the search space for bypass plans has to be developed. (2) The search space for bypass plans is quite large. Hence, partial exploration strategies still resulting in sufficiently efficient plans have to be developed. (3) Since the complement of a join can be very large, those cases where the complement can be restricted to the complement of the semijoin have to be detected. We attack all three problems. Especially, we present an algorithm generating the optimal bypass plan and one algorithm producing near optimal plans exploring the search space only partially. As soon a..