Optimization and Evaluation of Disjunctive Queries

download complete text (postscript, 153k)

Jens Claußen
Alfons Kemper
Guido Moerkotte
Klaus Peithner
Michael Steinbrunn
Technical Report MIP-9615, Universität Passau, August 1996
It is striking that the optimization of disjunctive queries---i.e., those which contain at least one or-connective in the query predicate---has been vastly neglected in the literature as well as in commercial systems. In this paper we propose a novel technique, called bypass processing, for evaluating such disjunctive queries. The bypass processing technique is based on new selection and join operators that produce two output streams: the true-stream with tuples satisfying the selection (join) predicate and the false-stream with tuples not satisfying the corresponding predicate. Splitting the tuple streams in this way enables us to ``bypass'' costly predicates whenever the ``fate'' of the corresponding tuple (stream) can be determined without evaluating this predicate. In the paper we show how to systematically generate bypass evaluation plans utilizing a bottom-up building block approach. We show that our evaluation technique allows to incorporate the standard SQL semantics of null-values. For this we devise two different approaches: one is based on explicitly incorporating three-valued logic into the evaluation plans; the other one relies on two-valued logic by ``moving'' all negations to atomic conditions of the selection predicate. We describe how to extend an iterator-based query engine to support bypass evaluation with little extra overhead. This query engine was used to quantitatively evaluate the bypass evaluation plans against the traditional evaluation techniques utilizing a CNF- or DNF-based query predicate.

Last modified: Wed Nov 10 12:02:12 MET 1999