In this paper we develop a novel optimization strategy for disjunctive queries involving join predicates. This work is an extension of our previously published approach [KMPS94] for optimizing disjunctive selection predicates by generating two output streams from selection operators: a "true"-stream for objects (tuples) satisfying the selection predicate and a "false"-stream for those objects not satisfying the predicate. Then, each stream undergoes an individual, "customized" optimization. Here, we extend the basic idea of [KMPS94] to disjunctive queries with join operators. Analogously to selections, we propose to generate two output streams from a joint operator: one "true"-stream for pairs of objects (of the two input streams) that satisfy the join predicate and one "false"-stream for those pairs not satisfying it. In combination with the extended selection predicate processing, the provides a large potential for efficiently evaluating disjunctive queries because it allows to "bypass" expensive or non-selective joins as well as selections whenever the outcome of the query can be determined otherwise. In the paper, we develop techniques for effectively generating optimal and near-optimal "bypass" evaluation plans and quantitatively assess their quality in comparison to traditional plans for a range of benchmark queries.
Ulrike Peiker, Martin Griebl