Optimization and Evaluation of
Jens Christian Claussen, Alfons Kemper, Guido Moerkotte, Klaus Peithner, Michael Steinbrunn · 2000
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 processing, for evaluating such disjunctive queries. The 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 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 evaluation with little extra overhead. This query engine was used to quantitatively evaluate the evaluation plans against the traditional evaluation techniques utilizing a CNF- or DNF-based query predicate.