Optimization and Evaluation of Disjunctive Queries

Authors:

Jens Claußen

Alfons Kemper

Guido Moerkotte

Klaus Peithner

Michael Steinbrunn

Abstract:

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.