  Database research has always given limited attention to optimizing predicates
with disjunctions. What little past work there is, has mostly focused on
optimizations for traditional row-oriented databases. However, a key difference
between how row-oriented and column-oriented engines evaluate predicates is
that while row-oriented engines apply predicates to a single tuple at a time,
column-oriented engines apply predicates to sets of tuples, adding another
dimension to the problem. As such, row-oriented engines focus only on the best
order to apply predicates in to "short-circuit" the overall predicate
expression, but column-oriented engines must additionally decide on the input
sets of tuples for each predicate application. This is important, since smaller
inputs lead to faster runtimes, and nontrivial, since the results of earlier
predicates can be used to reduce the inputs to later predicates and predicates
may be combined via disjunctions in the predicate expression. In this work, we
formally analyze the predicate evaluation problem for column-oriented engines
and present BestD/Update, the first ever polynomial-time, provably optimal
algorithms to deduce the minimum input sets for each predicate application.
BestD/Update's optimality is guaranteed under a wide range of cost models,
representing different real-world scenarios. Furthermore, when combined with
the predicate ordering algorithm Hanani, BestD/Update reduce into EvalPred, a
simple O(n log^2 n) algorithm, which we recommend for practical use and optimal
for all predicate expressions of nested depth 2 or less. Our evaluation shows,
thanks to its optimality and polynomial planning time, EvalPred outperforms not
implementing any disjunction optimizations and exiting optimal algorithms by up
to 2.6x and 28x respectively for synthetic workloads and by up to 1.3x and 100x
respectively for queries from TPC-H and the CH-benchmark.
