  Despite decades of research into query optimization, optimizing queries with
disjunctive predicate expressions remains a challenge. Solutions employed by
existing systems (if any) are often simplistic and lead to much redundant work
being performed by the execution engine. To address these problems, we propose
a novel form of query execution called tagged execution. Tagged execution
groups tuples into subrelations based on which predicates in the query they
satisfy (or don't satisfy) and tags them with that information. These tags then
provide additional context for query operators to take advantage of during
runtime, allowing them to eliminate much of the redundant work performed by
traditional engines and realize predicate pushdown optimizations for
disjunctive predicates. However, tagged execution brings its own challenges,
and the question of what tags to create is a nontrivial one. Careless creation
of tags can lead to an exponential blowup in the tag space, with the overhead
outweighing the benefits. To address this issue, we present a technique called
tag generalization to minimize the space of tags. We implemented the tagged
execution model with tag generalization in our system Basilisk, and our
evaluation shows an average 2.7x speedup in runtime over the traditional
execution model with up to a 19x speedup in certain situations.
