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 , and our evaluation showed an average 2.7$\times$ speedup in runtime over the traditional execution model with up to a 19$\times$ speedup in certain situations.

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 , and our evaluation showed an average 2.7$\times$ speedup in runtime over the traditional execution model with up to a 19$\times$ speedup in certain situations.

October 2023
[revised]January 2024
[accepted]February 2024

§ INTRODUCTION

Despite decades of research in query optimization, optimizing queries with disjunctive predicates remains a relatively understudied problem.
Many systems and optimizers ignore disjunctions outright, and solutions (if any) employed by existing systems often fallback to simple and inefficient heuristics for evaluating disjunctive queries.
However, disjunctions continue to commonly appear in real workloads and pose issues for query optimization [Fontoura et al., 2010] [Henneberg et al., 2022] [Albe, 2018].

To illustrate the challenges, suppose we want to compile a list of potential movies to watch this weekend.
We are a fan of more recent movies because they have better special effects, so we are willing to watch them as long they have a score above 7.0.
However, we are also willing to tolerate the effects of older movies if they are “masterpieces” and have a score greater than 8.0.
<ref>=  (next page) expresses these constraints.
Note the schema for this query comes from the IMDB dataset provided by the Join Order Benchmark [Leis et al., 2015], and the query is a simplification of one of the queries in the benchmark[We take a few liberties with the attribute names and predicate expressions in this example to improve brevity and clarity.].

SELECT * FROM t̄itle AS t JOIN movie_info_idx AS mi_idx

ON t.id = mi_idx.movie_id

WHERE(́t.year > 2000 AND mi_idx.score > '7.0')

OR(́t.year > 1980 AND mi_idx.score > '8.0')

Due to the disjunction in <ref>'s predicate expression, performing pushdown optimizations is not straightforward.
In this case, existing systems typically do one of two things:

* Perform the join first, then evaluate the predicate expression on the resulting joined output.

* Treat each part of the disjunction as a separate query, applying pushdown optimizations separately, and combine the results with a union operator.
Note this is equivalent to internally transforming <ref> into:

SELECT * FROM t̄itle AS t JOIN movie_info_idx AS mi_idx

ON t.id = mi_idx.movie_id

WHEREt́.year > 2000 AND mi_idx.score > '7.0'

SELECT * FROM title AS t JOIN movie_info_idx AS mi_idx

ON t.id = mi_idx.movie_id

WHEREt́.year > 1980 AND mi_idx.score > '8.0'

Both solutions are unsatisfactory.
The first option is equivalent to performing no optimizations whatsoever.
<ref> only features a single join, but without a way to prune the relations before the join, as the number of joins grows, the size of the joined output will grow exponentially and the total runtime alongside with it.
The second option allows for pushdown optimizations, but does redundant work because movies that scored above 8.0 and were made after 2000 satisfy both parts of the disjunction.
The tuples representing these movies need to be constructed multiple times.
An additional, potentially expensive union operator is also required to filter out duplicate tuples.
It is also worth noting that the second option is only even available because <ref>'s predicate expression is a disjunct of conjuncts (DNF).
If it were a conjunct of disjuncts (CNF), the second option would not be available.

To address these problems, we propose a novel form of query execution called tagged execution.
In traditional query execution, operators such as filters and joins operate on and result in sets of tuples called relations.
In tagged execution, tags loaded with semantic information are attached to subsets of relations, and operators use that extra information to avoid performing any redundant work during query execution, thereby significantly improving runtime performance.
The tagged execution model allows the query optimizer to push down disjunctive predicates regardless of whatever form the predicate expression might have.
In addition, it ensures that each tuple is only ever materialized once and that each predicate subexpression is only evaluated once, even if it appears multiple times in the overall predicate expression.

Optimally executing <ref> under tagged execution would:

* Apply predicates  and  to the  table and attach the tags t.year > 2000 = T and t.year > 2000 = F, t.year > 1980 = T to the relevant tuples.

* Apply predicates  and  to the  table and attach the tags mi_idx.score > '8.0' = T and mi_idx.score > '8.0' = F, mi_idx.score > '7.0' = T to the relevant tuples.

* Do the following joins between the sets of tuples with tags:

* t.year > 2000 = T $\times$ mi_idx.score > '8.0' = T

* =
t.year > 2000 = T $\times$
mi_idx.score > '8.0' = F, mi_idx.score > '7.0' = T

t.year > 2000 = T $\times$ mi_idx.score > '8.0' = F, mi_idx.score > '7.0' = T

* =
t.year > 2000 = F, t.year > 1980 = T $\times$
mi_idx.score > '8.0' = T

t.year > 2000 = F, t.year > 1980 = T $\times$ mi_idx.score > '8.0' = T

Note the predicates are pushed down, and the join only ever processes each tuple once.

Although tagged execution is a powerful new paradigm for query execution, it introduces new technical challenges:

* Tag Management.
How should tags be generated, which should be preserved, and how should they be combined?
A naive implementation storing all true/false assignment values of predicates can lead to an exponential number of tags, so we must manage tags carefully to ensure overheads do not outweigh the benefits.

* Planning.
A new execution model requires a new query planner.
We must explore into how much of conventional planning wisdom we can bring into tagged execution and devise new planners which take advantage of the unique benefits offered by tagged execution.

In short our contributions are:

* The tagged execution model, with its ability to optimize and push down disjunctive predicates.

* Our solution for the tag management problem and several new planners to use with tagged execution.

* The evaluation of tagged execution in our system [The common basilisk can run across water by “pushing down” with its feet rapidly enough to create air pockets to push off of [Hsieh and Lauder, 2004]!], in which tagged execution achieved an average 2.7$\times$ speedup in runtime over traditional query execution with up to a 19$\times$ speedup in certain situations.

The rest of this paper is structured as follows.
<ref> provides a detailed explanation of the tagged execution model.

<ref> introduces a technique called tag generalization to solve the tag management problem and discusses how to handle NULL values.
<ref> provides an overview into planning for tagged execution.
<ref> presents our evaluation, <ref> discusses related work, and <ref> concludes the paper.

remove balance warning filter

§ TAGGED EXECUTION

In this section, we describe the tagged execution model.
We introduce the concept of tags and describe how operators in tagged execution use these tags to avoid redundant work.
It should be noted that the actual creation of tags and the decision of which tags to create are all done and made by the planner during plan time, which we describe in <ref>.
This section only focuses on how the execution engine performs tagged execution during runtime, given a query plan and some set of tags.

Example tagged execution query plan of <ref>. Here, P1 = , P2 = , P3 = , and P4 = .

As an overarching example for this section, consider <ref>=  (next page), which shows a sample query plan for the tagged execution of <ref>.
The base table nodes  and  feed into the four base predicates from <ref> before coming together for a final join.  As we describe next, this plan successfully achieves disjunctive predicate pushdown.
The orange numbers in parentheses refer to <ref> = (ex:title1)(next page), which list example tuples for each of these stages.
Focusing on the left side, the tuples from  are originally assigned the empty tag (i.e., ).
After applying the predicate , the tuples which evaluate to true are assigned the tag t.year > 2000 = T, and the tuples which evaluate to false are assigned the tag t.year > 2000 = F.
The second filter can then avoid redundant work by applying the predicate  on only the tuples with the tag t.year > 2000 = F; the tuples with the tag t.year > 2000 = T can pass through the filter untouched.
Note the second filter does not output the tuples which would be assigned the tag t.year > 2000 = F, t.year > 1980 = F.
These tuples do not satisfy the overall predicate expression, so they can be dropped here and do not need to be fed into the join.
After performing similar actions on the right side, the join operator then uses the tags to selectively join only the tuples which satisfy the overall predicate expression.
In particular, the tuples which would be associated with the tag t.year > 2000 = F, t.year > 1980 = T, mi_idx.score > '8.0' = F, mi_idx.score > '7.0' = T are never joined.
Thus, by relying on tags to keep track of predicate results, tagged execution is able to avoid much of the redundant work that would be performed by the traditional execution model.

In the remainder of this section, we first define the concept of relations with tags in <ref> and then describe how operators uses these tags in tagged execution in <ref>.
We wrap up with some important implementation details regarding tagged execution in <ref>.

§.§ Setup

In traditional query execution, operators process and produce sets of tuples, or relations.
In tagged execution, this basic unit of operation becomes tagged relations.
Tagged relations are similar to regular relations in that they comprise of sets of tuples, but subsets of tuples in tagged relations (called [s]) are annotated with tags containing semantic information, providing additional context for operators to take advantage of during query execution.

A tagged relation may have any number of [s].
However, the [s] must be mutually exclusive, and every [] must be associated with exactly one tag.
Although the model allows for [s] with zero tuples, in practice, these [s] are removed from tagged relations for performance reasons.

The tags themselves are sets of true/false assignments to arbitrarily complex predicate expressions from the query, and an assignment has the form:

\[
\langle expr \rangle = T/F
\]

In which $\langle expr \rangle$ is an arbitrarily complex Boolean SQL expression, and an assignment to $T$ represents $\langle expr \rangle$ is true, and an assignment to $F$ represents $\langle expr \rangle$ is false.
Each tag may have any number of assignments, and each tuple in the corresponding  [] must satisfy every assignment present in the associated tag.
For example, every tuple in the [] associated with the tag t.year > 2000 = F, t.year > 1980 = T must be a title produced between 1981 and 2000.

<ref> are all examples of tagged relations associated with <ref>.
The schema for the tuples are shown in the captions.
Tags are in bold, and corresponding [s] are given in the following non-bold lines.

Looking at <ref>, we see that the tagged relation is made up of 7 tuples split into 2 [s]; the two [s] divide the tuples based on whether they were produced after 2000 or not.

<ref> features an example of an assignment to a complex predicate expression, which we define as a predicate expression containing either an AND or an OR.
Note that in all examples, no tuple satisfies more than a single set of assignments present in a tagged relation, satisfying mutual exclusivity.

t.year > 2000 = T:

{('The Dark Knight', 2008, 1), ('Evolution', 2001, 2),

('Avatar', 2009, 7)}

t.year > 2000 = F:

{('The Shawshank Redemption', 1994, 3),

('Pulp Fiction', 1994, 4), ('The Godfather', 1972, 5)

('Beetlejuice', 1988, 6)}

t.year > 2000 = T:

{('The Dark Knight', 2008, 1), ('Evolution', 2001, 2),

('Avatar', 2009, 7)}

t.year > 2000 = F, t.year > 1980 = T:

{('The Shawshank Redemption', 1994, 3),

('Pulp Fiction', 1994, 4), ('Beetlejuice', 1988, 6)}

mi_idx.score > '8.0' = T

{('9.0', 1),  ('9.3', 3), ('8.9', 4), ('9.2', 5)}

mi_idx.score > '8.0' = F, mi_idx.score > '7.0' = T

{('7.5', 6),  ('7.9', 7)}

t.year > 2000 AND mi_idx.score > '7.0' = T:

{('The Dark Knight', 2008, '9.0', 1),

('Avatar', 2009, '7.9', 7)}

t.year > 2000 AND mi_idx.score > '7.0' = F,
t.year > 1980 AND mi_idx.score > '8.0' = T:

{('The Shawshank Redemption', 1994, '9.3', 3),

('Pulp Fiction', 1994, '8.9', 4)}

t.year > 2000 = T:

{('The Dark Knight', 2008, 1), ('Evolution', 2001, 2), ('Avatar', 2009, 7)}

t.year > 2000 = F:

{('The Shawshank Redemption', 1994, 3), ('Pulp Fiction', 1994, 4),

('The Godfather', 1972, 5), ('Beetlejuice', 1988, 6)}

t.year > 2000 = T:

{('The Dark Knight', 2008, 1), ('Evolution', 2001, 2), ('Avatar', 2009, 7)}

t.year > 2000 = F, t.year > 1980 = T:

{('The Shawshank Redemption', 1994, 3), ('Pulp Fiction', 1994, 4),

('Beetlejuice', 1988, 6)}

mi_idx.score > '8.0' = T

{('9.0', 1),  ('9.3', 3), ('8.9', 4), ('9.2', 5)}

mi_idx.score > '8.0' = F, mi_idx.score > '7.0' = T

{('7.5', 6),  ('7.9', 7)}

t.year > 2000 AND mi_idx.score > '7.0' = T:

{('The Dark Knight', 2008, '9.0', 1), ('Avatar', 2009, '7.9', 7)}

t.year > 2000 AND mi_idx.score > '7.0' = F, t.year > 1980 AND mi_idx.score > '8.0' = T:

{('The Shawshank Redemption', 1994, '9.3', 3), ('Pulp Fiction', 1994, '8.9', 4)}

t.year > 2000 = T:

{('The Dark Knight', 2008, 1), ('Evolution', 2001, 2), ('Avatar', 2009, 7)}

t.year > 2000 = F:

{('The Shawshank Redemption', 1994, 3), ('Pulp Fiction', 1994, 4),

('The Godfather', 1972, 5), ('Beetlejuice', 1988, 6)}

t.year > 2000 = T:

{('The Dark Knight', 2008, 1), ('Evolution', 2001, 2), ('Avatar', 2009, 7)}

t.year > 2000 = F, t.year > 1980 = T:

{('The Shawshank Redemption', 1994, 3), ('Pulp Fiction', 1994, 4),

('Beetlejuice', 1988, 6)}

mi_idx.score > '8.0' = T

{('9.0', 1),  ('9.3', 3), ('8.9', 4), ('9.2', 5)}

mi_idx.score > '8.0' = F, mi_idx.score > '7.0' = T

{('7.5', 6),  ('7.9', 7)}

t.year > 2000 AND mi_idx.score > '7.0' = T:

{('The Dark Knight', 2008, '9.0', 1), ('Avatar', 2009, '7.9', 7)}

t.year > 2000 AND mi_idx.score > '7.0' = F, t.year > 1980 AND mi_idx.score > '8.0' = T:

{('The Shawshank Redemption', 1994, '9.3', 3), ('Pulp Fiction', 1994, '8.9', 4)}

§.§ Filter

Given the previous setup, we can now describe how filter operators function in tagged execution.
In traditional query execution, a filter operator applies a predicate expression to an input relation and outputs the subset of tuples which evaluate to true for that predicate expression.
In tagged execution, each filter operator is given a tag map specifying  which [s] of the input tagged relation it should evaluate the predicate expression on and what to do with the results.
An entry in the tag map has the following signature:

\[
\inputtag \rightarrow \{T: Optional \postag,\; F: Optional \negtag\}
\]

The predicate expression is applied to all [s] which have a tag that matches .
If the optional  is specified, then the tuples which evaluate to true are stored as a [] in the output tagged relation with the tag .
Similarly, if  is specified, the tuples which evaluate to false form a [] with the tag .
Both  and  may be specified in a single entry.
All [s] which do not have any matching entries in the tag map are passed untouched to the output tagged relation.
Note that same tag may appear as an output in multiple entries.
In this case, [s] which share the same output tag are merged together in the output tagged relation.

As an example, consider the filter operator with the predicate expression  being given a tag map with one entry:
t.year > 2000 = F

$\rightarrow \{T:$ t.year > 2000 = F, t.year > 1980 = T }

t.year > 2000 = F $\rightarrow \{T:$ t.year > 2000 = F, t.year > 1980 = T }

When the tagged relation from <ref> is passed in as input, only the second [] has a matching entry.
Thus, the predicate expression is only evaluated on the tuples from that [].

The tuples which evaluate to true come together to form a new [] with the tag t.year > 2000 = F, t.year > 1980 = T.

Meanwhile, the  is missing from the tag entry, so tuples which evaluate to false are removed and not included in the output tagged relation.
The first [] does not match any entries in the tag map and is passed untouched to the output tagged relation.
The resulting tagged relation is shown in <ref>.

The planner determines the tag map for each filter operator.
During runtime, the execution engine simply follows the instructions encoded in the tag map.
As such, the degree of sophistication of the planner can have a large impact on performance, and a naive planner, such as one that produces a tag map entry for every [] in the input tagged relation and outputs all resulting true/false [s], can lead to  poor runtimes.
Thus, we show in <ref> how our planners build effective tag maps for efficient execution.
In the case of this example, the planner was intelligent enough to realize that titles produced after 2000 are also produced after 1980 and reduces the filter operator's work by omitting the tag map entry for t.year > 2000 = T.

§.§ Join

Similar to filter operators, join operators in tagged execution are given tag maps which determine how to combine their inputs during runtime.
Assuming a join operator has an input “left” tagged relation and an input “right” tagged relation, an entry in the tag map has the following signature:

\[
(\lefttag, \righttag) \rightarrow \outtag
\]

For every pairing between a left [] and a right [], if it has a matching $(\lefttag,\allowbreak \righttag)$ entry, the tuples in those [s] are joined to create an output [] with the tag .
Similar to filters, output [s] which share the same tag are merged together in the output tagged relation.
However, unlike filter operators, [s] without a matching tag map entry are discarded and not included in the output tagged relation.
Note the same join constraint is used for every pairing of [s].

As an example, consider the join between the tagged relations in <ref> (left) and <ref> (right) using the join constraint  given a tag map with the following entries:
(t.year > 2000 = T, mi_idx.score > '8.0' = T)

$\rightarrow$ t.year > 2000 AND mi_idx.score > '7.0' = T

(t.year > 2000 = T,

mi_idx.score > '8.0' = F, mi_idx.score > '7.0' = T)

$\rightarrow$ t.year > 2000 AND mi_idx.score > '7.0' = T

(t.year > 2000 = F, t.year > 1980 = T,

mi_idx.score > '8.0' = T)

$\rightarrow$ t.year > 2000 AND mi_idx.score > '7.0' = F,
$\rightarrow$ t.year > 1980 AND mi_idx.score > '8.0' = T

(t.year > 2000 = T, mi_idx.score > '8.0' = T)

$\rightarrow$ t.year > 2000 AND mi_idx.score > '7.0' = T

(t.year > 2000 = T,  mi_idx.score > '8.0' = F, mi_idx.score > '7.0' = T)

$\rightarrow$ t.year > 2000 AND mi_idx.score > '7.0' = T

(t.year > 2000 = F, t.year > 1980 = T,  mi_idx.score > '8.0' = T)

$\rightarrow$ t.year > 2000 AND mi_idx.score > '7.0' = F,
$\rightarrow$ t.year > 1980 AND mi_idx.score > '8.0' = T

The first and second entries join the first [] from <ref> with the first and second [s] respectively from <ref> to generate the [] with tag t.year > 2000 AND mi_idx.score > '7.0' = T.
The third entry joins the second [] from <ref> with the first [] from <ref> to produce the [] with movies produced after 1980 with a score above 8.0 not included in the first output [].
Just as with filter operators, the planner determines the tag map, and intelligent planners can choose to selectively join only the tuples that satisfy the overall predicate expression and avoid performing costly joins between [s] whose results would be thrown away later in the pipeline.
In this example, the entry (t.year > 2000 = F, t.year > 1980 = T, mi_idx.score > '8.0' = F, mi_idx.score > '7.0' = T) is omitted from the tag map because the planner recognizes that movies produced between 1981 and 2000 with a score between 7.1 and 8.0 do not satisfy the overall predicate expression.

§.§ Projection

A projection operator in tagged execution offers one final chance to filter based on tags before actual projection.
The operator is given a set of tags by the planner, and only the tuples in [s] which have a matching tag are projected.
In the case of <ref>, all [s] are required as results to <ref>, so the planner would include both tags for the projection operator.

§.§ Implementation

The exact implementation of tagged relations and the previously discussed operators can have a large impact on the overall runtime performance.
Here, we discuss the details of how tagged execution is implemented in our system .

§.§.§ Tagged Relation

is a column-oriented system, so intermediate representations of relations contain tuples of indices rather than tuples of actual values.
Each $n$-tuple is the result of joining $n$ tuples and contains indices into the $n$ tables.
The actual tuple of values can be reconstructed by doing an index-based lookup into each table when needed.

Given a relation of such tuples, tagged relations are constructed by creating an accompanying hash table of bitmaps.
Tags serve as keys to the hash table, and each bitmap specifies which tuples belong to which [].
Although an alternative implementation of separating out each [] into its own relation was considered, we found this version to be less performant because it required moving around tuples as opposed to manipulating bits in a bitmap.

§.§.§ Filter

There are two important implementation details for filter operators.
First, when evaluating the predicate expression,  takes the union across all bitmaps which have matching tags, and the predicate expression is evaluated once on the tuples specified by the combined bitmap.
This results in fewer I/O calls to read the underlying data values than evaluating the predicate expression separately for each [].
Second, filter operators do not actually modify the underlying, non-tagged relation.
Instead, only the hash table of bitmaps is updated to mirror the output tags and corresponding [s].
Even tuples which no longer belong to any [] remain in the relation because removing a tuple from the middle of a relation would require expensive modifications to every single bitmap.

§.§.§ Join

uses a hash join for all its joins.
However, rather than building a separate hash table for each [],  builds one giant hash table for all the [s].
The values of the hash table contain enough supplementary details to determine which [s] the key belongs to.
This significantly improves runtime performance because [s] can share join key values and only one hash table needs to be allocated.

§ TAG MANAGEMENT

The previous section described the mechanism by which tagged execution query operators can use tags during runtime to process only a subset of the input tagged relations.
We now turn our attention to the problem of tag management; for each query, how should the planner decide which tags to use, and how should it build each tag map.
This is important, since the tag maps ultimately dictate how much work is done for each query, and a naive strategy to tag management can lead to an exponential number of tags, causing the overhead of tagged execution to outweigh the benefits.
To demonstrate, we first describe this naive strategy in <ref>, and we show that while it is capable of accomplishing disjunctive predicate pushdown, its weaknesses make it inferior to traditional execution strategies.
We then introduce the concept of generalizing tags in <ref> and show that by using these generalized tags instead of the tags in the naive strategy, we can reduce the total number of tags in the system and avoid the exponential blowup in many cases.
In <ref>, we detail how to build efficient tag maps using the generalized tags to reduce the amount of unnecessary work done by the system.
Finally, we discuss how to extend our work to accommodate NULLs and three-valued logic in <ref>.

§.§ Naive Strategy

In the most naive strategy to tag management, each tag contains true/false assignments to only base [s] (as opposed to the arbitrarily complex predicate expressions described in <ref>).
Tags like t.year > 2000 = T, mi_idx.score > '7.0' = F are valid, while t.year > 2000 AND mi_idx.score > '7.0' = F are not because it contains an AND.
The tag map for each operator is built as follows.
First, base tagged relations, created directly from the base tables, contain only one [] with the “empty” tag which contains no assignments (i.e, ).
For filter operators, create a tag map entry for each input tag and output both the “true” and “false” results.
More formally, if the filter operator's associated predicate is $P$, for each input tag $I$, create the tag map entry:

\[
I \rightarrow \{T: I \cup \{P = T\},\; F: I \cup \{P = F\}\}
\]

For join operators, take the full Cartesian product of the input left and right tags.
In other words, for each pairing of left and right input tags $(L, R)$, generate the following tag map entry:

\[
(L, R) \rightarrow L \cup R
\]

Finally, the projection operator's set of allowed tags is the set of tags whose assignments satisfy the overall predicate expression.

This naive strategy is capable of performing disjunctive predicate pushdown.
Since the predicate evaluation results are stored in tags, filter operators can be pushed down to the base table, and the projection operator simply selects all tags which satisfy the query's overall predicate expression.
However, the naive strategy suffers from two large weaknesses.

(1) Filter operators output both “true” and “false ” each time, so they do not actually filter any tuples.
Since the join operators' tag maps contain the full Cartesian product of input tags, this results in joins being performed on the full base tables.
(2) In addition, each filter operator outputs two new tags for each input tag, multiplying the number of tags by two.
Thus, after $n$ filter operators, there will be $2^n$ output tags, and this exponential blowup can potentially cause the overhead to outweigh the benefits.

§.§ Tag Generalization

Propagation with predicate tree from <ref>.

To address the weaknesses of the naive strategy, we introduce the idea of generalizing tags.
Tag generalization is a technique which generalizes the assignments in a tag based on the structure present in the query's predicate expression and Boolean implication.
A generalized tag can be used in place of an ungeneralized tag, and multiple ungeneralized tags may generalize to the same generalized tag.
Thus, replacing all the tags in the naive strategy with generalized tags reduces the total number of tags in the system and avoids the exponential blowup in many cases.

An additional benefit of tag generalization is that it clearly exposes (as early as possible) which tags will not be part of the final output.
The planner can then use this information to build efficient tag maps which discard tuples that do not satisfy the overall predicate expression as early as possible (<ref>).

In tag generalization, the query's predicate expression is represented as a predicate tree, in which each node represents a subexpression.
Leaf nodes represent the base predicates, and intermediate AND/OR/NOT nodes apply their operations to their children to form their subexpressions[The predicate tree is also normalized such that an intermediate node cannot be of the same type as their parent (i.e., an AND node's parent cannot also be an AND node)].

The root node refers to the entire predicate expression.

<ref> shows the predicate tree for <ref>.

Tag generalization works by propagating a tag's assignments upwards in the predicate tree.
As an assignment travels upwards, it becomes more general and encompasses more possible tags.

For example, the assignment  can be generalized into the assignment  because the former implies the latter according to <ref>'s predicate tree.
The generalized tag (t.year > 2000 AND mi_idx.score > '7.0') = F can then be used in place of not only t.year > 2000 = F, but also tags such as mi_idx.score > '7.0' = F and t.year > 2000 = T, mi_idx.score > '7.0' = F because these tags also imply the generalized tag.

[1]
Tag “tag”

fringe $\gets$ keys(tag)
pred $\gets$ fringe.pop()
parent $\in$ parents(pred)

(pred, parent, tag)

(pred, parent, tag)

(root, tag)
pred, parent, tag
isNot(parent) or

(isOr(parent) and tag[pred] = ) or

(isAnd(parent) and tag[pred] = ) or

(isOr(parent) and $\forall c \in$ children(parent), tag[$c$] = ) or

(isAnd(parent) and $\forall c \in$ children(parent), tag[$c$] = )
pred, parent, tag
tag[parent] $\gets$ $\neg$tag[pred]
tag[parent] $\gets$ tag[pred]
node, tag
tag = $\{\}$
node $\in$ keys(tag)
$\{\text{node}: \text{tag[node]}\}$
$\bigcup_{c \in \text{children(node)}}$ ($c$, tag)

from <ref>=  (next page) outlines the general algorithm for generalizing tags.
The input to  is a tag which maps predicate expressions to true/false values; each key-value pair constitutes an assignment.
At its core,  is a fringe-based algorithm which propagates a predicate expression's assignment to its parent if the parent's assignment can be implied by its children.
The fringe is initialized with the set of all predicate expressions with an assignment in the input tag (i.e., “keys(tag)”).
The function  checks for the condition of Boolean implication and returns true if one of five conditions is satisfied:

* If the parent is a NOT node.

* If the predicate expression's assignment value is true and the parent is an OR node.

* If the predicate expression's assignment value is false and the parent is an AND node.

* If the parent is an OR node and all its children have false assignments.

* If the parent is AND node and all its children have true assignments.

The actual propagation is done with , and unless the parent is a NOT node, the predicate expression's assignment value is assigned directly to the parent.
If the propagation is successful, the parent is added to the fringe, and the loop continues.
Note that the same predicate expression may appear multiple times in the predicate tree, so the “parents” function returns the parent for each instance.
Once all assignments have been propagated as much as possible,  is called on the resulting tag to collect only the topmost assignments.
Assignments to predicate expressions, which are descendants of other predicate expressions with assignments, are all are discarded.
Note that  runs in $O(n)$ time, in which $n$ is the number of [s].

<ref> shows the predicate tree for <ref> undergoing this process for the tag t.year > 2000 = F, t.year > 1980 = T, mi_idx.score > '8.0' = T.
The red-colored leaf nodes mark the nodes with the initial assignments, the orange arrows show the propagation, and the blue-colored intermediate nodes mark the nodes which get assignments due to propagation.
After  is called, only the assignment at the root node remains, and the output of  is (t.year > 2000 AND mi_idx.score > '7.0') OR (t.year > 1980 = T AND mi_idx.score > '8.0') = T.

Using the predicate tree to generalize assignments also has the benefit of making it clear which predicate expressions still need to be applied to which tags.
In the previous example, the tag after propagation (t.year > 2000 AND mi_idx.score > '7.0') OR (t.year > 1980 = T AND mi_idx.score > '8.0') = T has a true assignment to the overall expression, signifying that every tuple with this tag should be part of the final output.
Thus, no additional filters need to be run on this tag.
Similarly, if the overall predicate expression has a false assignment, it signifies that every tuple with the tag does not match the criteria for the query, and these tuples can safely be removed from the pipeline.

As mentioned, the same predicate expression may appear multiple times in the overall predicate expression.
In fact,  conversations with real users of disjunctive workloads have led us to believe that this is actually a common occurrence for disjunctive queries.
Thus, careful consideration has gone into the development of  and  to handle this case.
Specifically,  allows different levels of propagation for different instances of the same predicate expression, and  only removes a predicate expression's assignment if every instance has an ancestor with an assignment.
It is this treatment of predicate expressions which allows tagged execution to evaluate each [] exactly once.

Although generalizing tags reduces the tag space in most cases, the number of tags produced can still be exponential in the worst case.
Consider the predicate expression with the form $(X_1 \lor Y_1) \land (X_2 \lor Y_2) \land ... \land (X_n \lor Y_n)$, in which all $X_i$ and $Y_i$ are [s].
If the filter operators are ordered and applied in $X_1, X_2, ..., X_n,Y_1,Y_2,...,Y_n$  order, then $2^{n}$ tags are still required to keep track of the unique [s].
However, such degenerate predicate expressions are not so common in practice, and the planner can interleave the $Y_i$ [s] (i.e., use a different plan) to reduce the number of tags.

§.§ Building Tag Maps

We now describe how the planner should build the tag maps for each operator in a given query plan.

Tag maps should minimize the amount of work performed by operators during runtime while still ensuring correctness of the query plan.
To accomplish this, our planners follow two main precepts when building tag maps:

* Avoid generating tags which do not get used by the rest of the pipeline.

* Do not apply filters on tags if it does not help refine the selection process.

Fortunately, tag generalization make it easy to recognize both cases.

For (1), we can identify such tags if they include a false assignment to the root node of the predicate tree.
Tuples with this tag are guaranteed to not satisfy the overall predicate expression and can be discarded without further consideration.
On the other hand, if an assignment to the root node does not emerge after generalizing a tag, it signifies that a portion of the tuples associated with that tag may still satisfy the overall predicate expression, and more filter operators must be applied to refine the associated [].
For example, in <ref>, the filter operator with the predicate expression  is applied before the filter operator with the predicate expression .
The first filter operator results in the tags t.year > 2000 = T and t.year > 2000 = F, and after tag generalization, t.year > 2000 = F becomes t.year > 2000 AND mi_idx.score > '7.0' = F.
However, the [] with the false tag may still contain tuples that satisfy the overall predicate expression, namely the movies produced after 1980 with a score greater than 8.0.
Thus, the [] must be kept.
However, after applying the second filter operator to this [], movies produced before 1980 will generate the tag t.year > 2000 AND mi_idx.score > '7.0' = F, t.year > 1980 = F, and this generalizes to (t.year > 2000 AND mi_idx.score > '7.0') OR (t.year > 1980 AND mi_idx.score > '8.0') = F.
At this point, we can be sure the [] with this tag does not contain any tuples which satisfy the overall predicate expression, since movies produced before 1980 do not satisfy the overall criteria.
Thus, for the second filter operator, the planner should omit the negative output tag () from the tag map entry.

For (2), let us assume we apply the filter operators with  and  in that order after joining the tables.
In this case, applying the predicate expression  to the [] with the tag t.year > 2000 = F is pointless.
The tuples with this tag are already guaranteed to not satisfy the first disjunctive clause in <ref>, so dividing this set of tuples into those that satisfy/do not satisfy  does nothing to help the tuple selection process.

Precept (2) states that such cases should be avoided, and generalized assignments make it trivial to identify such cases.
The tag t.year > 2000 = F after generalization becomes t.year > 2000 AND mi_idx.score > '7.0' = F, and this predicate expression is an ancestor (in the predicate tree) of the predicate expression we were trying to apply ().
Thus, both positive and negative outcomes of  (i.e., t.year > 2000 AND mi_idx.score > '7.0' = F, mi_idx.score > '7.0' = T and t.year > 2000 AND mi_idx.score > '7.0' = F, mi_idx.score > '7.0' = F) reduce to the same tag t.year > 2000 AND mi_idx.score > '7.0' = F after generalization, signifying that the application of  to this tag was not very helpful in refining the tuples according to overall predicate expression.

With these precepts in mind, we now describe the exact process our planners follow for building tag maps.
The overall construction is similar to the naive strategy, except it includes tag generalization and the two precepts.
First, base tagged relations, created directly from the base tables, contain only one [] with the “empty” tag which contains no assignments (i.e, ).

For filter operators, if the associated predicate expression is $P$, for each input tag $I$:

* If each instance of $P$ in the predicate tree has an ancestor with an assignment in $I$, do nothing (Precept (2)).

Otherwise, run  on both positive and negative output tags:

\begin{align*}
P & \gets \propup(I \cup \{P = T\}) \\
N & \gets \propup(I \cup \{P = F\})
\end{align*}

And create a tag map entry for $I$:

\[
I \rightarrow \{T: P,\; F: N\}
\]

If either $P$ or $N$ include a false assignment to the root node, remove it as an output tag from the entry (Precept (1)).

For join operators, take the full Cartesian product of the input left and right tags.
For each pairing of left and right input tags $(L, R)$, generate the output tag by generalizing the union:

\[
O \gets \propup(L \cup R)
%\outtag \gets \propup(\lefttag{} \cup \righttag)
\]

If $O$ does not have a false assignment to the root node (Precept (1)), create an entry in the tag map:

\[
(L, R) \rightarrow O
\]

For projections operators, restrict the set of allowed tags to only the tag with a true assignment to the root node.

§.§ Extension to Three-Valued Logic

Standard SQL allows for NULL values, and evaluating a [] on a NULL value often results in a non-true/false, ternary value called “unknown”.
Fortunately, our framework extends very naturally to this three-valued logic, and only four changes need to be made:

* Instead of restricting a tag's assignments to either be true/false, a tag's assignments may now be one of true/false/unknown.

* For filter operator tag map entries, include an optional output  for unknown results.

* The functions  and  in <ref> must be updated to handle unknown values.

For , the only difference is for conditions <ref> and <ref>, which must now be changed to:
<ref> If the parent is an OR node and all its children have false or unknown assignments.
<ref> If the parent is AND node and all its children have true or unknown assignments.

On the other hand,  must now update the parent's assignment value based on the three-valued logic from the SQL standard [Melton and Simon, 1993] (e.g., false OR unknown $\rightarrow$ unknown).

* Finally, applications of Precept (1) must be changed so that tag map entries do not contain output tags with either a false or unknown assignment to the root node.

§ PLANNING

Now that we understand how to execute queries under tagged execution, and how to build efficient tag maps which effectively prune tuples from disjunctive queries early, we describe how we can generate plans that take advantage of these early filtering capabilities.

We begin by presenting cost models for tagged execution (<ref>) and then give the details for several planners (<ref>).
Note that it is not the goal of this work to produce the most advanced, optimal planner for tagged execution.
Rather, we  present a few simple planners which highlight the advantages of tagged execution and demonstrate that even these simple planners can obtain substantial performance compared to existing methods.

§.§ Cost Models

Although tagged execution introduces a new model for query execution, internally, tagged operators employ the same relational operators from traditional query execution.
The only difference is that the input changes from whole relation(s) to individual [](s).
As such, our suggested cost models mirror existing models quite closely, differing mainly in that our cost models are summations of the costs of individual  [s].

For filter operators, the cost model is:

\[
C_{filter} = \alpha \sum_{I \in M} F_P \left|R[ I ]  \right|
\]

Here, $C_{filter}$ measures the cost of applying the filter operator with predicate expression $P$ on input tagged relation $R$.
The expression $I \in M$ iterates over each input tag in the given tag map, and $F_P$ is a certain constant cost factor specific to $P$.
The expression $R[I]$ selects the [] associated with tag $I$ in $R$, and $|R[I]|$ measures the cardinality of the selected [].
Finally, $\alpha$ is a constant cost factor used to calibrate filter costs with respect to join costs.
In short, the total cost is the summation of the costs from applying predicate expression $P$ to every [] whose tag appears as an input in the given tag map.

For join operators, the cost model is:

\begin{align*}
C_{join} &= C_{hash\_build} + C_{hash\_lookup} + C_{index\_build} \\[1em]
C_{hash\_build} &= F_{hash\_lookup} \left| R_{left}' \right| + F_{hash\_build} \cdot \text{unique}(R_{left}') \\
C_{hash\_lookup} &= F_{hash\_lookup} \left| R_{right}' \right| \\
C_{index\_build} &= F_{index\_build} \left| R_{left}' \Join R_{right}' \right|
%\left( | \text{tables}(R_{left})| + |\text{tables}(R_{right}) | \right)
\end{align*}

As mentioned, all join operators in our system are implemented as hash joins, so the cost of a join can be split into three components:

* $C_{hash\_build}$ – the cost of building a hash map from the left input tagged relation[Although this cost estimate assumes the hash map will be built from the left side, our system actually makes an estimate from both sides and chooses the cheaper side.],

* $C_{hash\_lookup}$ – the cost of performing the hash lookups from the right input tagged relation, and

* $C_{index\_build}$ – the cost of building the index for the output joined tagged relation.

Building the hash map requires performing a hash lookup for each element and creating entries for each unique element.
Accordingly, $F_{hash\_lookup}$ is some cost factor associated with hash lookups, $|R_{left}'|$ measures the cardinality of $R_{left}'$, $F_{hash\_build}$ is some cost factor associated with creating hash map entries, and $\text{unique}(R_{left}')$ counts the number of unique elements in $R_{left}'$.

Note that $R_{left}'$ is not the left input tagged relation; rather, $R_{left}'$ is the union of [s] in the left input tagged relation whose tags have at least one matching entry in the given tag map; $R_{right}'$ from $C_{hash\_lookup}$ is defined similarly.

Finally, the cost of building the index for the output joined tagged relation is the product of some cost factor $F_{index\_build}$ and its cardinality.

Note that the cost models for both filter and join operators require cardinality estimates for tagged relations/[s].
In general, the cardinality estimate for a tagged relation is given as the sum of its [s]'s cardinality estimates.
For filters, we measure and use the selectivities of [s] along with the independence assumption.
For joins, we use PostgreSQL's cardinality estimations of joins [Leis et al., 2015].

§.§ Planners

Here, we present several planners for tagged execution.
Each planner optimizes for a different situation, and in our system, we use the  planner, which estimates the cost of the plan produced by each of the following planners and selects the cheapest one.

This planner creates a filter operator for each [] in the predicate expression and pushes all filter operators down to the base table level.
All joins are performed after the filter operators and are ordered greedily; whichever join would produce the smallest cardinality tagged relation is performed next (this is actually the join ordering used for all our planners).
After pushdown, if there are multiple filter operators for a single table, they are sorted in benefiting order.

The benefit score of a filter operator is calculated with respect to a set of filter operators, and it  estimates the benefit of applying that filter operator first before the set of filter operators.
The score is used here and in other planners to avoid materializing every alternative plan and serves as an effective proxy for plan cost.
The exact method to calculate the benefit score can be found in = <ref>.our technical = report <cit.>.report <cit.>.
is the “naive” planner which simply pushes down all all filter operators down to the base table level.
It serves as a good baseline planner, since for many queries, the joined relation is much larger than the base table relations, and pushing filter operators down to the base table level prunes as many tuples as early as possible.
<ref> serves as an example query plan that  might produce.

[1]
(best_plan, best_cost) $\gets$ ()
filter $\in$ filters(plan)

new_plan $\gets$ best_plan
can_pullup(new_plan, filter)
(new_plan, new_cost) $\gets$ pullup_node(new_plan, filter)
new_cost < best_cost
(best_plan, best_cost) $\gets$ (new_plan, new_cost)

The pseudocode for this planner is presented in <ref>.
This planner uses the plan produced by , in which all filter operators are pushed down, as the base plan.
Then, for each filter operator (in reverse benefiting order), the planner considers pulling up [Hellerstein and Stonebraker, 1993] the operator by one node in the query plan, and if the resulting plan is cheaper, that plan is used as the base plan from then on.
In the end, the planner returns the cheapest plan it finds.
builds on  for situations in which certain predicate subexpressions are very selective and can cause the joined result to be much smaller than the base tables.
In these cases, it may be cheaper to delay the application of other more expensive subexpressions, so  pulls up each filter node to check.
For example, consider the predicate expression: .
There are only two movies in the IMDB dataset with a score above 9.0, so applying the score predicates to the  table and joining it with the  table will lead to a joined relation of two tuples.
As such applying the expensive regex pattern matching predicate on this joined result may result in a cheaper plan than applying it directly to the entire  table.
can check for situations such as this and output the following plan:

.1 Filter(t.title ILIKE '%godfather%').
.2 Join(t.id = mi_idx.movie_id).
.3 Table(title as t).
.3 Filter(mi_idx.score = '9.2').
.4 Filter(mi_idx.score = '9.3').
.5 Table(movie_info_idx as mi_idx).

.1 Filter(t.title ILIKE '%godfather%').
.2 Join(t.id = mi_idx.movie_id).
.3 Table(title as t).
.3 Filter(mi_idx.score = '9.2').
.4 Filter(mi_idx.score = '9.3').
.5 Table(movie_info_idx as mi_idx).

This planner operates in the “opposite” direction of .
The base plan performs all joins first, then all filters are applied in benefiting order.
For each filter operator (in benefiting order), the planner considers pushing down the operator to the base table level.
If the resulting plan is cheaper, that plan is used as the base plan from then on.
In the end, the planner returns the cheapest plan it finds.
One weakness of  is that it only considers moving one filter operator at a time.
Sometimes, there is no benefit to moving a single operator; only when multiple filter operators are moved can a change in the plan cost be observed.
Thus,  does not always find the optimal plan, and  serves as the opposite extreme, in which the default for all filter operators is to be performed after all the joins, and filter operators are only pushed down if it leads to a cheaper plan.
To take an example, let us consider the predicate expression: .
Once again, we would like to perform the expensive regex pattern matching predicates on the joined result, since  is so selective.
Consider the plan in which only  is pulled up:

.1 Filter(t.title ILIKE '%godfather%').
.2 Join(t.id = mi_idx.movie_id).
.3 Filter(t.title ILIKE '%lord%')  $\gets$ (1).
.4 Table(title as t).
.3 Filter(mi_idx.score > '9.0').
.4 Table(movie_info_idx as mi_idx).

.1 Filter(t.title ILIKE '%godfather%').
.2 Join(t.id = mi_idx.movie_id).
.3 Filter(t.title ILIKE '%lord%')  $\gets$ (1).
.4 Table(title as t).
.3 Filter(mi_idx.score > '9.0').
.4 Table(movie_info_idx as mi_idx).

This plan is not any cheaper compared to the plan in which all filters are pushed down.
This is because the tagged relation at (1) after the filter must include both t.title ILIKE '%lord%' = T and t.title ILIKE '%lord%' = F, so the join operator ends up joining to the entire  table.
In comparison, the base plan applies both parts of the disjunct to , and only the tuples with the tag t.title ILIKE '%godfather%' OR t.title ILIKE '%lord%' = T are joined.
is incapable of recognizing that pulling up both regex predicates would lead to a more optimal plan.
Thus to provide another perspective for these situations,  starts with all filters pulled up, and in this case pushes down only the  predicate to arrive at the following plan:

.1 Filter(t.title ILIKE '%godfather%').
.2 Filter(t.title ILIKE '%lord%').
.3 Join(t.id = mi_idx.movie_id).
.4 Table(title as t).
.4 Filter(mi_idx.score > '9.0').
.5 Table(movie_info_idx as mi_idx).

.1 Filter(t.title ILIKE '%godfather%').
.2 Filter(t.title ILIKE '%lord%').
.3 Join(t.id = mi_idx.movie_id).
.4 Table(title as t).
.4 Filter(mi_idx.score > '9.0').
.5 Table(movie_info_idx as mi_idx).

This planner mimics what existing planners might do for disjunctive predicates if the root node of the predicate tree is an AND node.
Children of the root node which are individual [s] or predicate expressions whose descendent [s] all apply to the same table are pushed down.
The remaining children are performed in increasing order of selectivity after all the joins.
In short, the planner pushes down the conjunctive filter operators it can, and resolves the remaining after the joins.
This planner mostly serves as a comparison point to traditional query execution.
Although it would arrive at the same plan as  for the previous example (in ), it would not be able to perform any pushdown optimizations for simple CNFs of the form $(P_1 \lor P_2) \land (P_3 \lor P_4)$, if $P_1$ and $P_2$ refer to different tables and $P_3$ and $P_4$ refer to different tables.

Note that in all these planners, we could reorder and push down/pull up [s] however we wanted, without having to worry about how it affects the evaluation of the query's predicate expression.
This is one of the highlights of the tagged execution abstraction model.
By encapsulating all the state required to evaluate the predicate expression into tags, tagged execution is able to disentangle the complexities of evaluating a disjunctive predicate expression from the query plan.
As a result, planners for tagged execution can rearrange [s] freely, almost as if they are planning for a predicate expression with only conjunctions.
Not only does this provide a cleaner interface, it also reduces the query plan space, allowing our planners to complete faster.

§ EVALUATION

For our evaluation, we wish to compare the runtime performance of the tagged execution model using our planners against the traditional execution model using existing planners.
In addition, we wish to measure the “overhead” of executing queries under the tagged execution model and explore how different query parameters can affect the level of benefit that the tagged execution model has to offer.
To this end, we executed queries from the Join Order Benchmark (JOB) [Leis et al., 2015] (<ref>) and a set of synthetic experiments varying different query parameters (<ref>) under both tagged and traditional execution models and measured their total runtimes.

To represent traditional execution, we implemented the following two planners:

*  is for predicate expressions with OR root nodes in the corresponding predicate trees (e.g., DNFs).
The planner treats each [] (i.e., child of the root node) as a separate query; each [] is executed independently of the others, applying pushdown optimizations wherever possible, and a final union operator to combine all the results.
This (or a variation) is the approach taken by many academic papers [Straube and Özsu, 1990] [JarkeMatthias and KochJurgen, 1984] [Muralikrishna, 1988] [Chang and Lee, 1997], and experts recommend rewriting SQL queries to achieve this manually for systems which do not support this internally [Albe, 2018].

*  is for predicate expressions with AND root nodes (e.g., CNFs) and is the counterpart to  for traditional execution.
Every [] whose [] descendants all refers to the same table are pushed down to that table, and the remaining [s] are performed after all the joins.
This (or a variation) is the approach taken by most real-world systems, such as PostgreSQL [Stonebraker and Rowe, 1986], Hyrise [Grund et al., 2010], and Vertica [Lamb et al., 2012].

Note that similar to the tagged execution planners from <ref>, both  and  order joins greedily.
We compared these traditional execution planners against our combined tagged execution planner  with its subplanners , , , and .

All experiments were conducted on our system [<https://github.com/alkim0/tagexec>], a column-oriented database system capable of performing both traditional and tagged query execution.
is coded in $\sim$12.6k lines of Rust, and data is stored on disk.
When the data for a [] is needed,  consults the corresponding bitmap, and reads are done using direct I/O calls with a LFU page cache sitting in the middle.
For bitmaps with low selectivity (i.e., only a few values need to be read), only the relevant pages are read from disk.
However, doing the same for bitmaps with high selectivity (i.e., many values need to be read) can lead to substantial penalties from the random I/O, so for all bitmaps with a selectivity above a certain threshold,  instead reads the entire column sequentially, and values are selected in memory.
For the experiments, we ran  on a server running Arch Linux with 40 Intel(R) Xeon(R) Gold 6230 CPU @ 2.10GHz processors, 128GB of memory, and a SSD with 6Gbps of I/O throughput.

§.§ Join Order Benchmark

/ ($>1$ = tagged execution is better)

/ ($>1$ = tagged execution is better)

/ ($>1$ = tagged execution is better)

/  ($>1$ = tagged execution is better)

Speedups in total runtime from using tagged execution for JOB queries.

Speedups in total runtime from using tagged execution for JOB queries ($> 1$ means tagged execution is better).

It should be noted that there is a distinct lack of publicly available disjunctive query workloads.
Although real workloads containing disjunctions have been reported [Fontoura et al., 2010] [Ji and Jacobsen, 2021], their proprietary nature prevents us from accessing them.

Luckily, JOB provides an avenue to concoct some realistic disjunctive queries.
Vanilla JOB does include a few queries with disjunctions, but these disjunctions never span more than a single table and are not fit for our workload by themselves.
JOB sorts its queries into 33 distinct query groups.
Each query group follows some sort of theme, and more importantly, all queries within a group operate on the same set of tables and use the same join conditions, differing only in the filtering predicate expressions.
Thus, the queries in each query group can be combined together by taking the disjunction of their predicate expressions.

For example, query group 20 is about superheroes; query 20a searches for superhero movies produced after 1950 with a character named "Iron Man", and query 20c searches for superhero movies produced after 2000 with just any character with the word "Man" in their name[The actual queries are more complex, but this serves as a summary.].
Combining queries 20a and 20c would give us one query which searches for superhero movies either produced after 1950 with a character named "Iron Man" or produced after 2000 with any character with the word "Man" in their name.
Doing this for every query group provides us with 33 complex and realistic disjunctive queries to use for evaluation.

<ref>=  (next page) presents the results of our evaluation for JOB.
We ran each query 5 times for each planner, and the figures use the average of those 5 times.
We present only the total runtimes and do not present planning and executions times separately because in every case, planning time accounted for less than 0.1% of the total runtime.

Key Takeaways.
We observed that tagged execution greatly outperformed traditional execution in many cases for JOB.
Specifically,  had an average 2.7$\times$ speedup over , and while the results varied more against , there were still queries in which  achieved a 19$\times$ speedup over .
At the same time, we observed that the tagged execution model incurred an average overhead of only 10% compared to traditional execution.

Speedups in total runtime from using tagged execution for JOB queries ($> 1$ means tagged execution is better).

<ref> presents the speedups in total runtime achieved by  over  for each query.
As shown clearly,  achieved at least a 2$\times$ speedup for most queries and for queries 27 and 21, achieved speedups of 9$\times$ and 8$\times$ respectively.
Deeper analysis revealed a multitude of reasons for these results.
First, the individual queries in each query group of JOB all shared common predicate subexpressions.
However, since  treats [s] as completely independent of one another, the system ended up performing redundant work in evaluating the same predicate subexpression multiple times.
In a similar vein, different [s] often operated on the same set of tuples.
Although  only materializes the indices for each tuple until projection (see <ref>), this still meant that the same tuple's indices needed be materialized multiple times in intermediate relations across different [] executions.
The final union operator that  appends to remove duplicate tuples also incurred significant runtime for queries whose final output relation size was large.
In contrast,  only ever evaluated each predicate subexpression once, and each tuple is only ever materialized once as well.
also does not require an additional union operator; the tag system is sufficient to track whether a tuple belongs to the final output or not.
Finally, joins in  often completed much quicker than the joins in , even for input (tagged) relations of similar sizes, displaying the importance of selective tag maps.

Since [s] often shared common predicate subexpressions, we wondered what would happen if a traditional execution planner was smart enough to take advantage of that information.
Thus, we searched for common predicate subexpressions that were children to every [] in a query and pulled out those predicate subexpressions to create an equivalent predicate expression with an AND root node (e.g., a predicate expressions $(A \land B \land C) \lor (A \land B \land D)$ would be transformed into $A \land B \land (C \lor D)$).
We ran  and  on the resulting queries, and <ref> shows the speedups achieved by  over .
Note that  always ran out of memory before completing query 18, so the figure does not include a speedup for that query.
For several queries,  still achieved significant speedups.
Specifically, for queries 6 and 20,  achieved speedups of 19$\times$ and 13$\times$ respectively (greater than any speedup achieved over ).
For these queries,  was able to push down all [s], while  was only able to push down the [s] belonging to the common predicate subexpressions.
This made a large difference because the unpushed [s] included several expensive predicates, such as regular expression matching, and the sizes of the relations after the joins were much larger than the sizes of the base tables.
In addition, the tagged join operator continued to exhibit superior runtimes compared to the regular join operator even for similar sized input (tagged) relations.
On the other hand, for many of the queries, the speedups ranged from 0.9 - 1.1, indicating similar performance between  and .
The primary reason for this was due to the highly selective nature of the common predicate subexpressions.
As mentioned, each query group in JOB follows some sort of theme, and the common predicate subexpressions often included highly selective [s] defining that theme.
These highly selective [s] would filter most of the tuples early in the pipeline, preventing  from really showcasing the benefits of tagged execution.
Even worse, for cases such as query 9, the speedup dipped as low as 0.6$\times$.
However, this was mostly due to inaccurate cost models.
Sometimes,  would select the “cheapest” plan, only for a different tagged execution planner to outperform it.
To account for this, we also measured speedup of the minimum runtime achieved by any tagged execution planner over .
<ref> shows the results.
As can be seen, the minimum speedup becomes 0.8$\times$, and the speedups of several queries jump even higher.
This indicates that with a more realistic cost model, tagged execution could potentially achieve even greater speedups over traditional execution.

Finally, we wanted to measure the “overhead” of tagged execution with respect to traditional execution.
That is, given a plan that can be run under both tagged and traditional execution models, how much slower is the tagged execution engine compared to the traditional execution engine in completing that plan.
We accomplished this by looking at the speedups of  over .
The plan generated by these planners forces tagged execution to behave exactly like traditional execution.
Filter operators for all pushed [s] do not include the  in their tag maps, and join operators take the full Cartesian product between their input left and right [s].
<ref> shows the results.
As can be seen, the average speedup is around 0.9$\times$, suggesting a 10% overhead in using tagged execution over traditional execution.

§.§ Synthetic Experiments

Selectivity (DNF)

Table Size (CNF)

Number of [Cs] (DNF)

Outer Conjunctive Factor (CNF)

Synthetic experiments varying a number of variety of different parameters.

Selectivity (DNF)

Table Size (CNF)

Number of [Cs] (DNF)

Outer Conjunctive Factor (CNF)

Synthetic experiments varying a number of variety of different parameters.

We also evaluated the tagged execution model on a set of synthetic experiments varying different parameters.
These experiments had two base queries; one in CNF and one in DNF.
The DNF version of the query was:

SELECT * FROM T̄0 J̄OIN T1 ON T0.id = T1.fid

JOIN T2 ON T0.id = T2.fid

WHERE(́T1.A1 < 0.2 AND T2.A1 < 0.2)

OR(́T1.A2 < 0.2 AND T2.A2 < 0.2)

The CNF version of the query was the same, except the ANDs and ORs were swapped in the predicate expressions (i.e., ).
These are relatively simple queries, but because each [] contains [s] referencing different tables, existing systems cannot optimize them very well.
In fact, there is no way to optimize the CNF version using a traditional execution model.
As for the underlying dataset, the tables , , and  each had 10k records.
Table 's  attribute was the primary key and had unique values ranging from 1 to 10,000.
and 's  attributes were the foreign keys, and their values were randomly generated using a Zipf distribution with a shape parameter value of 1.5.
The attributes that appeared as part of [s] (e.g.,  and ) had values ranging from 0 to 1, generated uniformly at random.

From these base queries and dataset, we varied a number of various parameters.
For DNF queries, we ran  and , while for CNF queries, we ran  and .
<ref> shows some of the results.
In every experimental configuration, each query was run 5 times for each planner, and the figures report the average of those 5 times.
With the exception of the experiment varying the number of [s], planning time once again accounted for less than 0.1% of the total runtime, so only <ref> plots the total runtime and the execution runtime separately.

Key Takeaways.

We observed that as the number of tuples handled by a query increased, tagged execution increasingly outperformed traditional execution.
Specifically,  = hadachieved speedups of up to 12$\times$ over  for DNF queries and speedups of up to 10$\times$ over  for CNF queries.

The first parameter we varied was the selectivity of the [s], which we varied from 0.1 to 0.9.
<ref> presents the results for DNF queries.
As shown, the runtimes diverged drastically as the selectivity value grew, with  achieving a speedup of 5$\times$ over  when selectivity is 0.9.
When selectivity was small, most tuples were filtered out early, so the difference between  and  was not as drastic.
However, as the selectivity grew, the sizes of the intermediate and resulting relations also grew, and this had a greater impact on  than  for three reasons.

First, even though the joins had similar size inputs for both tagged and traditional execution, the selective tag maps in tagged execution reduced the amount of work performed by each join operator.
Second, as selectivity grew, more duplicate tuples were materialized in intermediate relations across different [s] for , while  only materialized each tuple once.
Third, the union operator for  handled more tuples with increasing selectivity, resulting in more overhead.
The plot for the CNF version of the query had a slightly different shape.

Instead of the runtimes differing as a function of selectivity, there was instead a constant (large) difference between the runtimes for  and  ( was faster).
Due to each [] of the CNF referring to multiple tables,  could not push down any [s], so all filter operations were performed after all the joins.
Thus, the time taken to perform the join operations (the largest factor) remained constant even as selectivity varied.

Table Size.
Next, we varied the table sizes of , , and  from 1k records up to 50k records.
<ref> presents the results for CNF queries.
The plot displays the same trends as <ref>, with  achieving a speedup of 12$\times$ when the table size is 50k records.
The reasons were similar as well.
With larger table sizes, the sizes of intermediate and resulting relations also grew, and this affected  more than .
Because  could not push any [s] down, it suffered directly from the quadratic growth in the join result.
On the other hand,  could execute all its filter operators on the base tables, which grew linearly, and the join operators in tagged execution benefited significantly from the use of tag maps.
The plot for the DNF version of the query had the same shape, and the reasons were the same as those mentioned for the DNF version of the selectivity experiment.

Number of [Cs].
We also varied the number of [s] from 2 to 7.
Each additional [] referred to new attributes in  and  (e.g.,  and  ).
<ref> presents the results for DNF queries.
Note that this was the only experiment in which the planning time for  started to have a noticeable impact on the overall runtime.
As such, <ref> plots  (total) for the total runtime and  (exec) for only the execution runtime (without planning).
First, note that the difference in runtime between  and  (exec) increases with more [s]; at 7 [s],  achieved a 5$\times$ speedup over .
Since  executes each [] independently of others, additional [s] meant more tuples materialized multiple times across different [s] and additional join operators, each with their own overhead.
In comparison,  (exec) only experienced modest increases in runtime from executing the additional [s].
The figure also depicts a significant increase in planning time for  for more [s].
This increase was due to the unoptimized nature of ; recall that  attempts to pull up every filter node one node at a time and see if that results in a plan.
As the number of [s] increased, so did the number of filter nodes, and the number of plan comparisons increased exponentially.

A more optimized version of the planner which pulls filter nodes up to the next join juncture could substantially decrease planning time.
The plot for the CNF version of the query also showed an increasing difference in the runtime between the  and  (exec) ( was faster), though not as severe as <ref>.
Since  performs all joins before performing any filter operations, even with the base 2 [s], there was a large difference in runtime between  and , and increasing the number of [s] only had a secondary effect.

Outer Conjunctive Factor.
Throughout our experiments, we observed that if there were selective predicate subexpressions which filtered out most of the tuples early in the pipeline, tagged execution would not have a chance to exhibit its benefits.
In an attempt to isolate and measure this factor, we conducted an experiment in which we varied the selectivity of an additional conjunctive predicate expression, henceforth termed the outer conjunctive factor.
For CNF queries, the predicate expression with an outer conjunctive factor of 0.1 had the form: .
For DNF queries, the same  was included in each [].
<ref> shows the results for CNF queries.
As we can see, the runtimes for  and  remain mostly similar until a sharp increase when the outer conjunctive factor is 0.6.
At this point, the tagged execution model finally had a chance to display its benefits, and the difference in runtime peaked when the outer conjunctive factor was 1.0, with  achieving a 10$\times$ speedup over .
The reason for the sharp increase at 0.6 was because the first record in  (i.e., ) had a  value between 0.5 and 0.6.
As mentioned, we used a Zipf distribution to generate foreign keys randomly, and the most common value that appears in a Zipf distribution is 1.
Thus, the inclusion of the first record when the outer conjunctive factor rose to 0.6 meant a substantial increase in the resulting output and a substantial increase in the runtime for .
Although the same was true for , this inclusion had a much smaller impact on tagged execution due to its efficient join operators with selective tag maps.
The plot for DNF queries had the same shape, for the same reasons.

We might need a graph/table that measures number of predicates vs number of tags for various queries

We probably need some form of memory measurement for the overhead of tagged execution, but we can probably wait for the revision to do that

§ RELATED WORK

The set of related work can largely be divided into two parts:

* works related to tagging

* works related to disjunctions

Though not explicit, the idea of tagging is present in past works.
Most works in shared work optimization [Chen et al., 2000] [Giannikis et al., 2012] [Giannikis et al., 2014] [Candea et al., 2009] [Krishnamurthy et al., 2004] [Hong et al., 2009] use some form of tags to keep track of which tuples belong to which queries, and works built on the eddy processor [Avnur and Hellerstein, 2000] [Madden et al., 2002] [Hellerstein et al., 2000] typically use a tag to keep track of which operators have been evaluated for each tuple.
However, the context in which tags are used for these works is clearly very different compared to our work.
In addition, another critical difference between these works and tagged execution is the semantic information present in the tags for tagged execution.
The tags used in these works all represent some sort of simple membership into a query/operator set, and it is difficult to see that as semantic information compared to the predicate results present in the tags for tagged execution.

Disjunctions (Bypass).
The most relevant related work is the line of work regarding the bypass technique [Kemper et al., 1994] [Steinbrunn et al., 1995] [Claussen et al., 2000].
As originally introduced by Kemper et al. [Kemper et al., 1994], the bypass technique augments filter operators in traditional execution with an optional “false” output stream.
Input tuples which evaluate to true are output to the regular “true” output stream, and those that evaluate to false are sent to the “false” output stream.
The desire is that the tuples in the “true” output stream bypass the more expensive filter operators that appear later in the pipeline.
Steinbrunn et al. [Steinbrunn et al., 1995] extend this idea to join conditions, and Claussen et al. [Claussen et al., 2000] expand the technique to include NULL values.
While similar, tagged execution different from bypass in two main ways:
(1) First is the reuse of query operators and shared work.
By using tags to encode predicate expression results, tagged execution can reuse the same query operators for different [s] with different predicate expression results.

However, bypass depends on traditional relational query operators, and this results in using different query operators for relations with different predicate expression results.
Thus, even for a query as simple as <ref>, bypass requires multiple scans of the input tables and multiple join operators to execute.
(2) Second is the separation of tag space and query plan space.
Tagged execution encapsulates the evaluation of the predicate predicate in tags and separates this tag space from the query plan.

As a result, tagged execution planners can make planning decisions independently of the predicate expression evaluation.
On the other hand, bypass embeds the predicate expression evaluation directly into the query plan and only produces plans in which predicates are all pushed down.
However, as discussed in <ref>, this is not always desirable.

Disjunctions (CNF/DNF).
Aside from the bypass technique, most works involving disjunctive predicate expressions typically focus on converting the predicate expression into either CNF or DNF and optimizing the execution from these forms [Selinger et al., 1979] [Straube and Özsu, 1990] [JarkeMatthias and KochJurgen, 1984] [Muralikrishna and DeWitt, 1988] [Chang and Lee, 1997].
and  in our evaluation serve as representatives for these works.
However, in addition to the inefficiencies of CNF/DNF-based methods highlighted in the introduction, it is well-known that conversion into CNF/DNF can result in an exponential number of terms [Russell and Norvig, 2016], so just transforming the input into the correct form can be quite expensive.
In comparison, tagged execution has no such requirements on the form of the input predicate expression and optimizes all predicate expression forms equally well.

Disjunctions (Factorization).
Chaudhuri et al. [Chaudhuri et al., 2003] introduce techniques to factorize a disjunctive predicate expression to maximize usage of existing indexes.
In a sense, factorization works in the “opposite” direction of tag generalization, and we could have used factorization-like techniques to reduce the tag space in our work.
However, the techniques presented by Chaudhuri et al. involve searching over an exponential space, as opposed to 's linear runtime, and tag generalization has the highly convenient benefit of exposing which tags can be discarded early.

Disjunctions (Ordering).
The final group of works on disjunctions all have to do with ordering [s] [Hanani, 1977] [Kastrati and Moerkotte, 2017] [Kastrati and Moerkotte, 2018] [Kim et al., 2022].
Given a query with a disjunctive predicate expression, these works attempt to find the best order to evaluate the [s] of that predicate expression.
However, these works all assume a single-table query with no joins, so their relevance to our work is limited.

§ CONCLUSION

In this paper, we presented the tagged execution model, a powerful new way to execute queries, and demonstrated how it can be used to optimize disjunctive queries.
We showed how we could reduce the tag space using tag generalization and introduced several new planners which can take advantage of the benefits offered by tagged execution.
Finally, in our evaluation, we showed that our tagged execution planners outperform traditional execution planners with an average speedup of 2.7$\times$ and a maximum speedup of 19$\times$ in certain situations, while only incurring an average overhead of 10%, highlighting the prowess of the tagged execution model.

§ BENEFIT SCORE

The benefit score estimates the value of applying a certain filter operator before others.
It differs from other estimates of filter operator importance, such as simple selectivity and Boolean Difference Calculus [Kemper et al., 1992], in that it is calculated with respect to a set of unapplied filter operators.

This is important for cases in which we want an ordering for a subset of all filter operators.
In such cases, we only care about the impact each filter operator has on other filter operators in the subset and not on all other filter operators.
By specifying a reference unapplied filter set, the benefit score gives more accurate estimates of the value of each filter operator in such situations.

The algorithm to calculate the score is given by <ref>[The exact algorithm additionally allows specifying the number of input tuples for each filter operator in the unapplied reference filter operator set. This effectively weights each filter operator with a different level of importance. However, we omit such details here.].

[1]
Filter operator to score “to_score”, Unapplied filter operator set “unapplied_set”
benefit $\gets$ 0
unapplied $\in$ unapplied_set
is_and_descendant $\gets$ true
is_or_descendant $\gets$ true
ancestor_path $\in$ ancestor_paths(unapplied)
$\forall \text{parent} \in \text{parents(to\_score)}, \text{parent} \not\in \text{ancestor\_path} \lor \text{isOr(parent)}$
is_and_descendant $\gets$ false
$\forall \text{parent} \in \text{parents(to\_score)}, \text{parent} \not\in \text{ancestor\_path} \lor \text{isAnd(parent)}$
is_or_descendant $\gets$ false
benefit $\gets$ benefit + (1 - selectivity(to_score))
benefit $\gets$ benefit + selectivity(to_score)

For each filter operator in the unapplied set, the algorithm searches to see if that filter operator exists as a descendant of to_score's parent in the predicate tree.
If so, then the benefit score is updated with (1 - selectivity(to_score)) if to_score's parent is an AND node or just selectivity(to_score) if to_score's parent is an OR node.
This is because if to_score's parent is an AND node and we apply to_score first, then we only need to consider the tuples which evaluated to true for to_score as as the input to unapplied[This assumes that the predicates $P$ and $\neg P$ are treated as different predicate subexpressions in the predicate tree.].
Thus, we can remove (1 - selectivity(to_score)) of the tuples from consideration by applying to_score first, and that is the “AND benefit” of to_score with respect to this unapplied filter operator.
Similarly if to_score's parent is an OR node and we apply to_score first,  then we only need to consider the tuples which evaluated to false for to_score as as the input to unapplied.
Thus, we can remove selectivity(to_score) of the tuples from consideration by applying to_score first, and that is the “OR benefit” of to_score with respect to this unapplied filter operator.

However, due to the fact that a predicate subexpression may appear multiple times in the predicate tree, <ref> appears much more complex.
Here, to_score may have multiple parents (one for each instance in the predicate tree), and one instance of unapplied may be a descendant while another is not.
Thus, <ref> shows the modifications necessary to handle these cases.
The function ancestor_paths(unapplied) retrieves the path to the root node for each instance of unapplied in the predicate tree, and parents(to_score) returns the parent of each instance of to_score in the predicate tree.
If one of to_score's parents appears in every ancestor path of unapplied, then it is possible that to_score has some effect on unapplied.
Specifically, if an AND parent of to_score appears in every ancestor path of unapplied, then unapplied receives the “AND benefit” of applying to_score first.
Similarly, if an OR parent of to_score appears in every ancestor path of unapplied, then unapplied receives the “OR benefit” of applying to_score first.
Note that it is possible to receive both the “AND benefit” and “OR benefit” of applying to_score first; in this case, unapplied does not have to be applied at all.
The algorithm calculates this benefit value for each filter operator in the unapplied set and returns the sum.

Sorting a set of filter operators according to “benefiting order” calculates the benefit score of each filter operator with respect to the remaining filter operators and sorts those filter operators in decreasing $\left< benefit \right> / \left< cost\mhyphen factor \right>$ order.

[Albe, 2018]
Laurenz Albe.
Avoid OR for better PostgreSQL query performance, May 2018.
URL <https://www.cybertec-postgresql.com/en/avoid-or-for-better-performance/>.

[Avnur and Hellerstein, 2000]
Ron Avnur and Joseph M. Hellerstein.
Eddies: Continuously adaptive query processing.
In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, pages 261–272, Dallas Texas USA, May 2000. ACM.
ISBN 978-1-58113-217-5.
URL <https://dl.acm.org/doi/10.1145/342009.335420>.

[Candea et al., 2009]
George Candea, Neoklis Polyzotis, and Radek Vingralek.
A scalable, predictable join operator for highly concurrent data warehouses.
In Proceedings of the 35th International Conference on Very Large Data Bases (VLDB), number CONF, 2009.
URL <https://infoscience.epfl.ch/record/139392>.

[Chang and Lee, 1997]
Jae-young Chang and Sang-goo Lee.
An optimization of disjunctive queries: Union-pushdown.
In COMPSAC, pages 356–361. IEEE Computer Society, 1997.

[Chaudhuri et al., 2003]
Surajit Chaudhuri, Prasanna Ganesan, and Sunita Sarawagi.
Factorizing complex predicates in queries to exploit indexes.
In SIGMOD 2003, 2003.

[Chen et al., 2000]
Jianjun Chen, David J. DeWitt, Feng Tian, and Yuan Wang.
NiagaraCQ: A scalable continuous query system for Internet databases.
In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, pages 379–390, Dallas Texas USA, May 2000. ACM.
ISBN 978-1-58113-217-5.
URL <https://dl.acm.org/doi/10.1145/342009.335432>.

[Claussen et al., 2000]
Jens Claussen, Alfons Kemper, Guido Moerkotte, Klaus Peithner, and Michael Steinbrunn.
Optimization and evaluation of disjunctive queries.
IEEE Transactions on Knowledge and Data Engineering, 120 (2):0 238–260, 2000.
URL <https://ieeexplore.ieee.org/abstract/document/842265/>.

[Fontoura et al., 2010]
Marcus Fontoura, Suhas Sadanandan, Jayavel Shanmugasundaram, Sergei Vassilvitski, Erik Vee, Srihari Venkatesan, and Jason Zien.
Efficiently evaluating complex boolean expressions.
In Proceedings of the 2010 International Conference on Management of Data - SIGMOD '10, page 3, Indianapolis, Indiana, USA, 2010. ACM Press.
ISBN 978-1-4503-0032-2.
URL <http://portal.acm.org/citation.cfm?doid=1807167.1807171>.

[Giannikis et al., 2012]
Georgios Giannikis, Gustavo Alonso, and Donald Kossmann.
SharedDB: Killing One Thousand Queries With One Stone.
Proceedings of the VLDB Endowment, 50 (6), 2012.
URL <http://www.vldb.org/pvldb/vol5/p526_georgiosgiannikis_vldb2012.pdf>.

[Giannikis et al., 2014]
Georgios Giannikis, Darko Makreshanski, Gustavo Alonso, and Donald Kossmann.
Shared workload optimization.
Proceedings of the VLDB Endowment, 70 (6):0 429–440, February 2014.
ISSN 2150-8097.
URL <https://dl.acm.org/doi/10.14778/2732279.2732280>.

[Grund et al., 2010]
Martin Grund, Jens Krüger, Hasso Plattner, Alexander Zeier, Philippe Cudre-Mauroux, and Samuel Madden.
HYRISE: A main memory hybrid storage engine.
Proceedings of the VLDB Endowment, 40 (2):0 105–116, 2010.

[Hanani, 1977]
Michael Z. Hanani.
An Optimal Evaluation of Boolean Expressions in an Online Query System.
Commun. ACM, 200 (5):0 344–347, May 1977.
ISSN 0001-0782.
URL <http://doi.acm.org/10.1145/359581.359600>.

[Hellerstein and Stonebraker, 1993]
Joseph M. Hellerstein and Michael Stonebraker.
Predicate migration: Optimizing queries with expensive predicates.
In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, pages 267–276, 1993.

[Hellerstein et al., 2000]
Joseph M. Hellerstein, Michael J. Franklin, Sirish Chandrasekaran, Amol Deshpande, Kris Hildrum, Samuel Madden, Vijayshankar Raman, and Mehul A. Shah.
Adaptive query processing: Technology in evolution.
IEEE Data Eng. Bull., 230 (2):0 7–18, 2000.
URL <http://www.cs.cmu.edu/ natassa/courses/15-721/papers/hellerstein.pdf>.

[Henneberg et al., 2022]
Justus Henneberg, Felix Schuhknecht, Philipp Reutter, Nils Brast, and Peter Spichtinger.
Northlight: Declarative and Optimized Analysis of Atmospheric Datasets in SparkSQL.
In Proceedings of the 34th International Conference on Scientific and Statistical Database Management, pages 1–12, 2022.

[Hong et al., 2009]
Mingsheng Hong, Mirek Riedewald, Christoph Koch, Johannes Gehrke, and Alan Demers.
Rule-based multi-query optimization.
In Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, pages 120–131, 2009.

[Hsieh and Lauder, 2004]
S. Tonia Hsieh and George V. Lauder.
Running on water: Three-dimensional force generation by basilisk lizards.
Proceedings of the National Academy of Sciences, 1010 (48):0 16784–16788, 2004.

[JarkeMatthias and KochJurgen, 1984]
JarkeMatthias and KochJurgen.
Query Optimization in Database Systems.
ACM Computing Surveys (CSUR), June 1984.
URL <https://dl.acm.org/doi/abs/10.1145/356924.356928>.

[Ji and Jacobsen, 2021]
Shuping Ji and Hans-Arno Jacobsen.
A-tree: A dynamic data structure for efficiently indexing arbitrary boolean expressions.
In Proceedings of the 2021 International Conference on Management of Data, pages 817–829, 2021.

[Kastrati and Moerkotte, 2017]
Fisnik Kastrati and Guido Moerkotte.
Optimization of Disjunctive Predicates for Main Memory Column Stores.
In Semih Salihoglu, Wenchao Zhou, Rada Chirkova, Jun Yang, and Dan Suciu, editors, Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD Conference 2017, Chicago, IL, USA, May 14-19, 2017, pages 731–744. ACM, 2017.

[Kastrati and Moerkotte, 2018]
Fisnik Kastrati and Guido Moerkotte.
Generating Optimal Plans for Boolean Expressions.
In 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France, April 16-19, 2018, pages 1013–1024. IEEE Computer Society, 2018.

[Kemper et al., 1992]
Alfons Kemper, Guido Moerkotte, and Michael Steinbrunn.
Optimizing Boolean Expressions in Object-Bases.
In Li-Yan Yuan, editor, 18th International Conference on Very Large Data Bases, August 23-27, 1992, Vancouver, Canada, Proceedings, pages 79–90. Morgan Kaufmann, 1992.
URL <http://www.vldb.org/conf/1992/P079.PDF>.

[Kemper et al., 1994]
Alfons Kemper, Guido Moerkotte, Klaus Peithner, and Michael Steinbrunn.
Optimizing disjunctive queries with expensive predicates.
In ACM SIGMOD Record, volume 23, pages 336–347. ACM, 1994.

[Kim et al., 2022]
Albert Kim, Atalay Mert Ileri, and Sam Madden.
Optimizing Query Predicates with Disjunctions for Column Stores, October 2022.
URL <http://arxiv.org/abs/2002.00540>.

[Krishnamurthy et al., 2004]
Sailesh Krishnamurthy, Michael J. Franklin, Joseph M. Hellerstein, and Garrett Jacobson.
The case for precision sharing.
In Proceedings of the Thirtieth International Conference on Very Large Data Bases-Volume 30, pages 972–984, 2004.

[Lamb et al., 2012]
Andrew Lamb, Matt Fuller, Ramakrishna Varadarajan, Nga Tran, Ben Vandiver, Lyric Doshi, and Chuck Bear.
The vertica analytic database: C-store 7 years later.
Proceedings of the VLDB Endowment, 50 (12):0 1790–1801, 2012.

[Leis et al., 2015]
Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann.
How good are query optimizers, really?
Proceedings of the VLDB Endowment, 90 (3):0 204–215, 2015.

[Madden et al., 2002]
Samuel Madden, Mehul Shah, Joseph M. Hellerstein, and Vijayshankar Raman.
Continuously adaptive continuous queries over streams.
In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pages 49–60, 2002.

[Melton and Simon, 1993]
Jim Melton and Alan R. Simon.
Understanding the New SQL: A Complete Guide.
Morgan Kaufmann, 1993.
URL <https://books.google.com/books?hl=en   lr=   id=ZOOMSTZ4T_QC   oi=fnd   pg=PA1   dq=Understanding+the+New+SQL:+A+Complete+Guide   ots=e3HaeNQ5hu   sig=7hniGDnnji36apNp8_6hvtt5VtY>.

[Muralikrishna and DeWitt, 1988]
M. Muralikrishna and David J. DeWitt.
Optimization of multiple-relation multiple-disjunct queries.
In Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems - PODS '88, pages 263–275, Austin, Texas, United States, 1988. ACM Press.
ISBN 978-0-89791-263-1.
URL <http://portal.acm.org/citation.cfm?doid=308386.308452>.

[Muralikrishna, 1988]
Murali Muralikrishna.
Optimization of multiple-disjunct queries in a relational database system.
Technical report, University of Wisconsin-Madison Department of Computer Sciences, 1988.

[Russell and Norvig, 2016]
Stuart J. Russell and Peter Norvig.
Artificial Intelligence: A Modern Approach.
Malaysia; Pearson Education Limited,, 2016.

[Selinger et al., 1979]
P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price.
Access path selection in a relational database management system.
In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data - SIGMOD '79, page 23, Boston, Massachusetts, 1979. ACM Press.
ISBN 978-0-89791-001-9.
URL <http://portal.acm.org/citation.cfm?doid=582095.582099>.

[Steinbrunn et al., 1995]
Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, and Alfons Kemper.
Bypassing joins in disjunctive queries.
In VLDB, volume 95, pages 11–15, 1995.

[Stonebraker and Rowe, 1986]
Michael Stonebraker and Lawrence A. Rowe.
The Design of Postgres, volume 15.
ACM, 1986.

[Straube and Özsu, 1990]
David D. Straube and M. Tamer Özsu.
Queries and query processing in object-oriented database systems.
ACM Transactions on Information Systems (TOIS), 80 (4):0 387–430, 1990.