{'fraction_non_alphanumeric': 0.04930046173685159, 'fraction_numerical': 0.009317932860965904, 'mean_word_length': 4.122669318464325, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimizing Query Predicates with Disjunctions for Column Stores

Since its inception, database research has given limited attention to optimizing predicates with disjunctions. For conjunctions, there there exists a"rule-of-thumb"of evaluating predicates in increasing selectivity to minimize unnecessary predicate evaluations. However, for disjunctions, no such rule-of-thumb exists. Furthermore, what little past work there is, has mostly focused on optimizations for traditional row-oriented databases. A key difference in predicate evaluation for row stores and column stores is that while row stores apply predicates to a single record at a time, column stores apply predicates to sets of records. Not only must the execution engine decide the order in which to apply the predicates, but it must also decide how to combine these sets to minimize the total number of records these predicates are applied to. Our goal for this work is to provide a good"rule-of-thumb"algorithm for queries with both conjunctions and disjunctions in a column store setting. We present EvalPred, the first polynomial-time (i.e., O(n log n)) predicate evaluation algorithm with provably optimal guarantees for all predicate expressions of nested depth 2 or less. EvalPred's optimality is guaranteed under a wide range of cost models, representing different real-world scenarios, as long as the cost model follows a"triangle-inequality"-like property. Yet, despite its powerful guarantees, EvalPred is almost trivially simple and should be easy to implement, even in existing systems. Even for predicate expressions of depth 3 or greater, we show via experimentation that EvalPred comes quite close to optimal with 92% of queries within 5% of optimal. Furthermore, compared to other algorithms, EvalPred achieves average speedups of 2.6x over no disjunction optimization, 1.4x over a greedy algorithm, and 28x over the state-of-the-art for the top 10% of queries.


Introduction
Query optimization has been a core topic of database research for decades. However, despite all the work done in the field, optimizing queries with disjunctive predicates is an area that has been largely neglected. In fact, many works in the field simply say that they assume predicates will be conjunction-only and ignore disjunctions outright! The dearth of work focusing on optimizing disjunctions has even impacted real-world systems, with well-known databases such as PostgreSQL [26], MonetDB [12], Spark SQL [3], and Vertica [19] using only simple heuristics (if any) to optimize disjunctions. Rather, a common consensus is to actually avoid ORs wherever you can and replace them with other operators [1]. However, many real-world queries do contain disjunctions, and we cannot simply ignore these queries.
For queries with only conjunctions, a well-known "rule-of-thumb" is to evaluate predicates in increasing selectivity. Evaluating highly selective predicates first ensures that any records which do not satisfy the overall expression are rejected as soon as possible, thereby reducing the number of unnecessary predicate evaluations. However, no such rule-of-thumb exists once disjunctions are added to the mix. In the past, some have proposed ordering conjunctions in increasing selectivity and disjunctions in decreasing selectivity [11]. Others have proposed converting the predicate expression into conjunctive normal form (CNF) or disjunctive normal form (DNF) and evaluating the resulting expression [13] [28]. Others still have proposed using Boolean Difference Calculus to measure the "importance" of predicates and ordering their evaluation based on their importance [18]. The lack of a systemic approach to the problem has led to these diverse approaches and the absence of a good "default" algorithm for disjunctions.
The problem is further compounded for column-oriented databases. Whereas row-oriented databases operate on the basis of a single record, column-oriented databases operate on sets of records, adding another dimension to the problem. As an example, let us assume a query has the form: Query 1. Query with both conjunction and disjunction.
SELECT * FROM T WHERE (P 1 AND P 2 ) OR P 3 in which P 1 , P 2 , and P 3 are predicate atoms (indivisble predicate subexpressions with no ANDs or ORs). A row-oriented database would, for each record in T , evaluate P 1 , P 2 , and P 3 in some order until the overall value of the predicate expression can be determined for the record. The ordering is important, since if P 3 evaluates to true, P 1 and P 2 do not need to be evaluated for that same record. However, regardless of the ordering, a row-oriented database must read in the entire record to begin with, meaning any benefits from ordering come purely from the processing time of predicate evaluation. In contrast, a column-oriented databases applies predicate atoms to a column at a time, so with the correct ordering, significant I/O could additionally be saved. In the case of Query 1, after evaluating P 3 , a column-oriented database can skip all the blocks which contain records that evaluated to true for P 3 while evaluating P 1 and P 2 . Specifically, an efficient column-oriented execution engine would: (1) Evaluate P 3 on all records. (2) Remember the set of records which satisfy P 3 . (3) Evaluate P 1 and P 2 on the subset of records which do not satisfy P 3 . (4) Combine the result with the previously remembered set to present as the final answer. By doing so, the system can minimize the number of records each predicate atom is evaluated on, saving both I/O from skipping data blocks and processing time from expensive predicates. Thus, column-oriented databases must additionally perform the set management tasks of deciding when to remember a set of records, determining which sets of records to evaluate each predicate atom on, and choosing how to combine resultant sets of records.

Our Work
Our goal for this work is to provide an efficient algorithm for evaluating complex predicates with both conjunctions and disjunctions in a column-oriented database setting. To this end, we present EvalPred, which we believe satisfies the criteria of a good "rule-of-thumb" algorithm because: 1. EvalPred is provably optimal for all predicate expressions of nested depth 2 or less (e.g., ANDs of ORs).

2.
EvalPred is fast, with a runtime complexity of O(n log n), in which n is the number of predicate atoms. 3. EvalPred is exceedingly simple, and existing systems can implement it with little trouble. 4. EvalPred's optimality is guaranteed under a wide range of cost models, representing different realworld scenarios. 5. Our evaluation shows EvalPred achieves good performance even for predicate expressions of nested depth 3 or greater, with 92% of queries within 5% of optimal. Furthermore, compared to other algorithms, EvalPred achieved average speedups of 2.6× over no disjunction optimization, 1.4× over a greedy algorithm, and 28× over the state-of-the-art for the top 10% of queries.
While many previous works have had exponential runtimes due to searching over the exponential space of query plans [16] [15] [17], EvalPred's strong theoretical backing allows it achieve optimality while remaining almost trivially simple.
In proving EvalPred's optimality, we model the predicate evaluation process for column-oriented databases as a series of steps. Each step can either be an evaluation of a predicate atom on a set of records or a set operation manipulating the results of said evaluations. By leveraging a "triangle inequality"-like property of our cost models, we show that the series of steps performed by EvalPred has a lower cost than any other series of steps, thus achieving optimality.
Unfortunately, our proofs do not extend to predicate expressions of nested depth 3 or greater (e.g., ANDs of ORs of ANDs). EvalPred expects to traverse the predicate expression in a depth-first search (DFS) manner (e.g., in Query 1, if P 1 is evaluated, P 2 must be evaluated before P 3 ). While DFS orderings are guaranteed to be optimal for predicate expressions of depth 2 or less, that is no longer the case for depth-3+ predicate expressions. As such, EvalPred is no longer guaranteed to be optimal. To address this issue, we offer a set of supplemental algorithms (which are also optimal given an ordering of predicate atoms) for this situation, and our supplemental algorithms reduce down to EvalPred if the predicate expression is traversed in a DFS manner. Contributions. In short, our main contributions are: • EvalPred, the first polynomial-time (i.e., O(n log n)), provably optimal algorithm algorithm for evaluating predicates with disjunctions in a column-oriented database. • Our various theoretical results, including a formal analysis of the predicate evaluation problem for columnoriented databases and the proof of optimality for EvalPred. • Evaluation of our algorithms, in which we outperform the current state-of-the-art by orders of magnitude.
The remainder of this paper is structured as follows. First, we present related work in Section 2. We specify the exact problem we wish to solve in Section 3 and present EvalPred, which solves this problem, in Section 4. We present a proof of correctness in Section 5 and a proof for optimality in Section 6. Finally, we discuss evaluation in Section 7 and conclude with Section 8.

Related Work
As mentioned previously, predicate evaluation for column-oriented databases can be split into two components: (1) Predicate atom ordering (2) Set management. Although past works tackling disjunctions do exist, the majority of these works were done with row-oriented databases in mind and only tackle the predicate atom ordering component. The aforementioned split allows us to reuse previous works for the ordering component and focus on set management. Note, however, that these previous works do not provide the same formal rigor that we do in our work.
Tdacb/Byp. As far as the authors are aware, there is only one line of work which has focused on optimizing query predicates with disjunctions for column-oriented databases: Kastrati and Moerkotte's work on Tdacb [16] and Byp [15]. Aside from being the only works focusing on column-oriented databases, Tdacb and Byp stand unique from other related works in that the plans generated by these algorithms are optimal. However, a critical drawback of these algorithms is that they must search over the exponential space of all query plans. Despite several clever optimizations to prune the search space, such as branch-and-bound and memoization, Tdacb still incurs a runtime complexity of O(n3 n ), where n is the number of predicate atoms. Given that Fontoura et al. report a real workload (from Yahoo Inc.) of up to 150k predicate atoms with hundreds of unique attributes [9], clearly this solution is not scalable. In fact, we show in Section 7 that the planning time for Tdacb can be quite expensive for even as few as 16 predicate atoms. In comparison, EvalPred is able to produce the optimal predicate evaluation plan in O(n log n) time and has practical runtimes that are orders of magnitude faster than Tdacb. Furthermore, Tdacb is a fairly complex algorithm, and the implementation details have a large impact on the runtime. EvalPred, in comparison, is a simple algorithm that existing systems can implement and can perform well even with minimal optimization. Byp is Kastrati and Moerkotte's previous work which they improved upon with Tdacb. Byp requires its input to be in DNF and is only locally optimal while still searching the entire search space of predicate evaluation plans. Thus, Byp is strictly worse than Tdacb. Finally, both Byp and Tdacb are meant for in-memory systems, and they assume little to no overhead in fetching the actual data. Thus, their guarantees of optimality do not extend to situations in which data is not stored in memory. In contrast, EvalPred makes no such assumption. stream. In essence, if given an expression such as P 1 ∨ P 2 , the bypass technique ensures that P 2 is only evaluated on records for which ¬P 1 is true to minimize the number of predicate evaluations. Unfortunately, the bypass technique introduced by Kemper et al. requires an exponential amount of time to generate plans, similar to Tdacb and Byp, and therefore, are not suitable for some real-world use cases. Still, minimizing predicate evaluation via negation is an important idea for column-oriented databases and is used extensively in our work. Dewey Evaluation. Fontoura et al. [9] present a predicate evaluation algorithm similar to Hanani. However, their main contribution comes in the form of efficiently encoding predicate expressions with tens of thousands of predicate atoms into simple labels. This encoding scheme could be used with EvalPred to reduce memory footprint. Boolean Difference Calculus. Kemper et al. [18] propose a nice heuristic to ordering predicate atoms based on Boolean Difference Calculus (BDC). In BDC, each predicate atom's "importance" is measured based on their likelihood of affecting the overall result. We could potentially use BDC instead of Hanani as our predicate atom ordering algorithm. However, since DFS traversal is not guaranteed, this ordering algorithm has to be used in conjunction with our supplemental algorithms instead of EvalPred. Common Subexpression Elimination. Chaudhuri et al. [6] present a work on factorizing predicate expressions to take advantage of existing indexes. This work is related since it combines indexes for ANDs and ORs minimize query execution time. However, the work is also largely orthogonal because its emphasis is on reducing the number of reappearing subexpressions. For EvalPred to be optimal, there is a key assumption on the uniqueness of predicate atoms. As such, their algorithm to reduce commonly reappearing predicate atoms may be applied before the execution of our algorithm for optimal execution. Other key differences are that Chaudhuri et al. do not consider set minus as a possible index operation, and they restrict the forms of the possible output expressions (e.g., DNF) to shrink their search space. CNF/DNF. The remaining works on disjunction optimization all focus on first trying to convert the predicate expression into CNF/DNF and optimizing the execution from those forms [13] [27] [5] [7] [21]. Unfortunately, it is well-known that the conversion process into CNF/DNF can result in an exponential number of terms [23]. Thus, just transforming the input into the correct form could be quite expensive. In addition, Kastrati and Moerkotte report that CNF/DNF-based evaluations generally tend to produce very poor plans and should be avoided [15]. Algorithms based on CNF/DNF also tend to be quite complex and existing systems may avoid implementing them due to their complexity. In Practice. Other than common subexpression elimination and reduction via Boolean implication, existing, well-used database systems implement few, if any, optimizations for disjunctions. PostgreSQL [26], for example, does partial transformations to CNF if separate clauses contain accesses to the same table to minimize the number of records for joins. MonetDB [12] and Spark SQL [3] do not seem to implement any additional optimizations, and based on conversations with developers from Vertica [19], Vertica "doesn't do anything special for ORs". The lack of exploration into this area has affected these systems, and we hope EvalPred will serve as a good "rule-of-thumb" for systems to follow. Number of Predicate Atoms. Some readers may doubt whether queries have enough predicate atoms to warrant such optimizing efforts. However, as Fontoura et al. [9] report, advertising exchanges and automatic query builders can result in queries with tens of thousands of predicate atoms. In addition, Chaudhuri et al. [6] discuss a workload that ranges up to over a hundred predicate atoms. Johnson et al. [14] also evaluate their work on up to 40 predicate atoms and report that for in-memory systems, the cost of evaluating predicates outweighs the cost of performing joins. All of this suggests that further research into this area can be highly beneficial.

.1 Setup
We first discuss the setting in which this work is applicable. We assume that our data is stored in a columnar fashion rather than in rows (i.e., each attribute (column) is stored separately either in memory or externally on disk). When executing a query, we assume only the attributes referenced in the query need to be read, and lightweight data structures (e.g., bitmap indexes, record id lists) are used to manage the indices of records which need to be filtered and combined from the applicable columns. Although no strong assumptions are made about the backend storage, we assume that the time to fetch and process the data is significantly greater than the time to manipulate the lightweight indices of records in memory. Note that backend storage such as hard disk drives (HDDs), flash drives, and network-attached storage all fit within this criteria. The primary resource we are concerned with is time. We assume we either have enough memory to hold the data needed to process the query or that the query can be executed off disk using a conventional buffer pool design. Either way, our algorithms do not require any additional data structures; we only use the data structures that would be constructed by a column store anyway to evaluate the query. If indexing structures to accelerate query execution are available, our algorithms can take advantage of them, but the absence of them does not affect the correctness of our algorithm.

Query Properties
We assume that the queries given to us are selection queries with complex predicate expressions. Predicate expressions may be composed of any number and depth of conjunctions and disjunctions of Boolean-result predicate atoms. Predicate atoms may be expensive (perhaps user-defined), and different predicate atoms may have different costs. In our proofs, we assume a query's predicate atoms are unique and that each appears only once in the predicate expression. We believe this to be a reasonable assumption due to the large amount of effort in common subexpression elimination made by both research [6] and real systems [26] [10]. Without uniqueness, EvalPred is no longer guaranteed to be optimal, but it will still return correct results. For clarity's sake, this paper assumes that we are working with single-table queries, but this is not a strict requirement. As long as each record in the source (single or joined) table has a global id (real or virtual), our algorithms are applicable. Even with pushdown-type optimizations, our algorithms still apply to pusheddown predicate atoms at the individual table level.

Predicate Evaluation System
Like many other column-oriented databases, our predicate evaluation system uses Boolean arrays to represents sets of records. If the ith value of the Boolean array is true, it signifies that the ith record of the relation is included in the set. The goal of the predicate evaluation system is to return the Boolean array which represents the set of all records that satisfy the given predicate expression. To accomplish this goal, the predicate evaluation system can perform the following two types of actions: 1. A predicate atom may be applied to a set of records to return the subset which satisfies the predicate atom (both input and output sets of records are represented using Boolean arrays).
2. Boolean arrays may be combined via some bitwise operation. We allow all basic bitwise operations: bitwise OR, bitwise AND, bitwise XOR, and bitwise complement. The resulting value is another Boolean array.

Cost Model
As mentioned, EvalPred can operate under a wide range of cost models. In this section, we give examples of various cost models which reflect different real-world situations before presenting Cost Model 1, which we use for our evaluation. Since the primary cost we are concerned with is time, a basic cost model may be: in which A specifies the action to be taken, whether it be a predicate atom application or a bitwise operation, and D is the operand(s) the action is performed upon. In the case of a predicate atom application, D represents the set of records A is applied to, and κ is some constant overhead cost; it should make sense that the cost of a predicate atom application is proportional to the number of records it is applied to. In the case that A is a bitwise operation, |R| refers to the number of records in the relation, and κ is some other constant overhead cost; the cost of bitmap operations is more variable depending on the underlying implementation, but is at most, proportional to the overall size of the underlying relation R. More importantly, represents the ratio of costs between bitwise operation on record indices versus a predicate atom application on actual data. Depending on the environment, a predicate atom application could easily cost 30× ∼ 100000× more than a bitwise operation. This could be because of the difference in cost between a memory access and a disk seek or the fact that a single record id can be represented with a single bit in a bitmap whereas a single int type element in a column takes up at least 4 bytes. To take a concrete example, in our experiment environment, simply reading 10M 4-byte int values from a RAID5 [22] setup of HDDs took 274ms, while ANDing together two bitmaps of 10M elements in memory to produce another bitmap only took 8ms. Even for data stored in memory, predicates may contain expensive machine learning operations, JSON parsing, or unoptimized user-defined functions (UDFs), each of which is significantly more expensive than a simple bitwise operation. Thus for our purposes, we set ≈ 0 and arrive at the following cost model instead: We could also change our cost model to more closely reflect a spinning HDD. Due to the differences in sequential access and random access, the access cost for HDDs generally goes up linearly for random access until a certain threshold, when it becomes cheaper to scan the entire column instead: in which ϑ is the aforementioned threshold and γ is the fraction of total records represented by D (i.e., |D|/|R|).
A generic, block-based storage system (perhaps using flash storage) may have the following cost model: in which B(D) counts the number of unique blocks the records represented by D resides in.
If we want to take into account the different costs incurred by different predicate atoms based on their complexity: in which F A is a constant cost factor specific to each predicate atom. This is the cost model used in our experiments. All of the above cost models are compatible with EvalPred. In fact, EvalPred can be used with any other cost model (they do not have to be linear), provided that they follow the property that bitwise operations are much cheaper than predicate atom applications and satisfy a "triangle inequality"-like property for predicate atoms: in which D and E are sets of records. Estimation. EvalPred estimates the above costs with selectivities. For multiple predicate atoms, Eval-Pred uses the independence assumption: (1) For ANDs: These estimations based on selectivity are not a hard requirement for our supplemental algorithms; thus, they do not rely on the independence assumption.

Details
EvalPred takes as input the predicate expression P * and the relation which we are operating on, R. The predicate expression is expected to be in negation normal form (NOT operators are pushed inwards until they appear only in front of literals); if not, this conversion can be done in linear time. Furthermore, all negative predicate atoms are replaced with positive predicate atoms: P = ¬P . The returned value of the algorithm is a Boolean array, for which the ith value represents whether the ith record in R satisfies P * . The symbols "&", "|", and "∼" are bitwise operations which stand for bitwise AND, bitwise OR, and bitwise complement respectively. The expression node.applyPred(check, R) in Line 7 refers to applying node's predicate atom to the set of records in R specified by Boolean array check.
EvalPred starts by ordering the predicate atoms of the given predicate expression according to our desired ordering algorithm, OrderP. For our implementation, we set OrderP = Hanani, which orders subexpressions of ANDs in increasing selectivity and subexpressions of ORs in decreasing selectivity, using the independence assumption. For the reader's convenience, we provide a modern, updated version of Hanani compatible with EvalPred in Appendix B. However, as mentioned before, a number of ordering algorithms with differing priorities and assumptions have been developed from past research on row-oriented databases. Any of those ordering algorithms which would result in a DFS traversal of the predicate expression can be used with EvalPred. For algorithms which do not follow a DFS traversal, please see Algorithm 4 in Section 6.
Next, the "makeTree" function builds a predicate tree from the given predicate expression. The tree is analogous to the abstract syntax tree of the expression, and nodes are arranged according to the ordering passed in as an argument. Each node in the predicate tree is either an AND node, an OR node, or a predicate atom leaf node. The tree is normalized such that the parent of each AND node must be an OR node and vice versa, resulting in an interleaving of ANDs and ORs across different levels of the predicate tree.
The rest of the algorithm works by taking the Boolean array named check and refining it with the predicate tree. As an argument of EvalNode, check's Boolean array represents the set of records which we still have to apply predicate atoms to determine whether they satisfy the predicate expression. Initially, check is initialized to a |R|-length Boolean array of true's, since every record must be checked. If node is a predicate atom node, the predicate atom is directly applied to the records specified by check. If node is an AND node, it should take the bitwise AND of its children's EvalNode values, but we take advantage of the fact that B & P (B, R) = P (B, R) for any Boolean array B, predicate atom P , and relation R to update check directly. If node is an OR node, the done variable keeps track of which records evaluated to true in one of node's children. Then, todo is derived by taking the bitwise subtraction of done from check. Thus, node's children make sure to run EvalNode only on records which we are not sure evaluate to true yet. Both AND and OR cases feature early returns if there are no more records left to evaluate, as can be seen from Lines 10-11 and 18-19.
The runtime complexity of EvalNode is actually just O(n), in which n is the number of predicate atoms, since it just traverses the predicate tree once. However, OrderP involves sorting the predicate atoms, causing the runtime complexity of EvalPred to be bounded by OrderP. In our case, OrderP = Hanani, and Hanani has a runtime complexity of O(n log n), Thus, EvalPred has an overall runtime complexity of O(n log n).
As an example, consider the predicate expression P * = (P 1 ∧ P 2 ) ∨ P 3 from Query 1. Let T R and F R refer to |R|-length arrays of true and false values respectively. If the ordering given to us by OrderP is [P 1 , P 2 , P 3 ], EvalPred would perform the following steps: 1. Apply P 1 to the true array T R : B 1 = P 1 (T R , R).

2.
Apply P 2 to the result of previous step: B 2 = P 2 (B 1 , R).

3.
Since the records specified by B 2 already satisfy the overall predicate expression, bitwise subtract it from T R and apply P 3 to the results: B 3 = P 3 (T R & ∼B 2 , R). 4. Return the union of the previous two results: Implementation. The Boolean arrays check, done, and todo may be implemented as bitmaps or record id lists depending on selectivity. The relation R's actual data is only read during the node.applyPred call in Line 7. Note that most column-oriented systems would already have Lines 1-14 implemented and would only need to add Lines 15-21.

Correctness
The correctness of EvalPred can be shown with the following. We first introduce Theorem 1, shown below. Theorem  As the inductive hypothesis, we assume Theorem 1 applies to all predicate trees with height k or less. If node has a height of k + 1, node must be either an AND or an OR node. Let us first ignore the early returns featured in Lines 10-11 and Lines 18-19. We examine the AND and OR cases separately.
If node is an AND node, the inductive hypothesis must hold for each child of node since they must all be trees of height k or less. Let check i be the updated value of check in Line 12 after the EvalNode call to the ith child of node. Assuming child i refers to the ith child of node, we can express check i as a recurrence relationship: If we assume check 0 is the original value of check passed in as the argument to EvalNode and node has t children, the return value of Line 13 will be: The set of records which satisfy an AND node is the intersection of its children's satisfying sets, thus the above can be written as: If node is an OR node, the inductive hypothesis must again hold for each child of node. Let done i be the updated value of done in Line 20 after the EvalNode call to the ith child of node. Assuming child i refers to the ith child of node, we can express done i as a recurrence relationship: For any sets A, B, and C: A ∪ (B ∩ (C \ A)) = A ∪ (B ∩ C) (Appendix C). Since ref childi and check are Boolean arrays referring to sets, the same reasoning applies (set subtraction can be represented as the bitwise expression A & ∼B). Thus, the recurrence relationship can be rewritten as: Assuming once again node has t children, Line 21's return value is: Using the distributive property, we can clean this up as: The set of records which satisfy an OR node is the union of its children's satisfying sets, thus the above can be simplified to: Finally, the early returns in Lines 10-11 and 18-19 can be removed from consideration due to Property 1 (shown below). The property simply states that if F R is passed in as the check argument of EvalNode, F R is returned as the result regardless of the value of node. For an AND node, even without the early return lines, Line 12 will continue to update check as F R until finally returning F R in Line 13. For an OR node, even without the early return lines, Line 20 will continue to take the bitwise OR of done and F R , and the final returned value of done in Line 21 will remain unchanged from before the early return. Thus, in both cases, returning early leads to the same results as not returning early and has no bearing on the overall correctness of the algorithm. Property 1. For any predicate tree node node and relation R, This property is easy to verify for each of the different types of nodes. A predicate atom applied to F R will obviously return F R . An AND node with check as F R will return directly from Lines 10-11. An OR node with check as F R will lead to todo being set to F R and return done, which is initially set to F R , in Lines 18-19.

Optimality
We hope Algorithm 1 appears simple and maybe even somewhat obvious to the reader. While the simplicity is certainly a boon for users of the algorithm, actually proving that the algorithm is optimal is a bit more challenging. To accomplish this, we define the bounds of what a predicate evaluation system can do and show that our algorithm takes the lowest cost actions possible within these bounds.
The rest of this section is structured as follows. We first formalize the problem and show that a predicate evaluation system can be modeled as a sequence of operator/operand steps in Section 6.1. In Section 6.2, we constrain the solution space and show that the only operators we need to worry about are predicate atom applications. Recall the problem can be split into: (1) Set management: Finding the optimal sequence of operands, given any sequence of operators, and (2) Predicate atom ordering: Finding the optimal sequence of operators. We present BestD/Update as solutions to the first component and prove their optimality in Section 6. 3. In Section 6.4, we present OrderP for the second component, discuss its optimality, the conditions to reduce BestD/Update into EvalPred, and issues with depth-3+ predicate expressions. This section contains only the main theorems and their proofs. The proofs for lemmas can be found in Appendix A.

Valuations
For our proofs, rather than reasoning directly about Boolean arrays or the sets of records they represent, it is easier for us to instead borrow from propositional logic [4] and reason about valuations instead. Valuations are assignments of true/false values. Since each predicate atom results in a true/false value when applied to a database record, this is a perfect fit. Let the input predicate expression P * be a Boolean formula composed of n predicate atoms (P 1 , P 2 , ..., P n ). With n true/false values, there are a total of 2 n possible valuations, and each valuation is an n-length tuple that may look like (T, F, T, ..., F ) or (F, F, F, ..., F ). Given that every record in the relation may be turned into such valuation, a logical mapping from valuations to sets of records can be constructed (e.g., the set of all 2 n valuations would represent the entire relation). Valuations serve as an effective proxy for sets of records, and reasoning about valuations is sufficient to prove the optimality of EvalPred. Thus, the goal of the predicate evaluation can be stated as finding the set of all valuations (or the valuation set) which satisfy the given predicate expression.
To take a concrete example, consider predicate expression P * = (P 1 ∧ P 2 ) ∨ P 3 from Query 1 again. A sample record might have the valuation (P 1 , P 2 , P 3 ) = (T, F, T ). Such a valuation would satisfy the overall predicate expression, and the record which produced this valuation would be included in the result set for the query. The set of all valuations which satisfy the predicate expression P * would be {(T, T, T ), (T, F, T ), (F, T, T ), (F, F, T ), (T, T, F )}.

Predicate Evaluation System
We model a predicate evaluation system as follows. Starting initially with only the set of all possible valuations (representing the entire relation), each step can be one of two operations: 1. Predicate atom application. Take an existing set of valuations and split the set into two smaller, mutually exclusive sets of valuations; those that satisfy the predicate atom and those that do not. 1 . Perform a set operation on existing set(s) of valuations to generate a new set of valuations.

Set operation
To formally reason about "existing set(s)", we define a growing universe of valuation sets to keep track of the sets of valuations we have generated thus far. Definition 1. We define universe U i as the set of all valuation sets which have been constructed by the first i steps of a predicate evaluation system.
Initially, this universe contains only the set of all possible valuations in it, since the entire relation must be considered in the beginning. Then, after performing each step, the result of the step is incorporated into the universe. Future steps may choose any set in the universe as operands. The predicate evaluation system stops once the set of all valuations which satisfy the predicate expression exists in the universe.
More formally, let U i be the state of the universe after the ith step; initially, and would result in the intersection between two sets. After performing the operator on the operand(s), the result is added to the universe: Each operand D i in the operand array D i must come from the universe of valuations sets before the ith step: D i ∈ U i−1 . Assuming D * is the set of all valuations which satisfy the given predicate expression, the predicate evaluation system is said to have finished after the ith step if D * ∈ U i .
We can now formally state our problem: Problem 1. Given a predicate expression, find the sequence of steps [S 1 , S 2 , ..., S m ] which minimizes the total cost of the steps: m i=1 C(S i ). Assuming universe U i represents the state of the valuation set universe after step i, the set of all valuations which satisfy the predicate expression must appear in the final universe U m . Furthermore, given that each step S i is a (O i , D i ) pair representing the operator and operand, the operator O i may be either a predicate atom application or a set operation (∩, ∪, \) over the operand(s) D i , and each operand D i in D i must be an element of the universe U i−1 .

Problem Reduction
Although Problem 1's large solution space can seem daunting, we can leverage certain properties of our cost model to constrain it to a more tractable size.

Predicate Atom-only Sequences
According to Cost Model 1, set operations are free. Thus, any number of set operation steps may be added at any point in the sequence of steps while preserving the same overall cost. The addition of a set operation could potentially help derive a set of valuations to remove or reduce a costly predicate atom application later in the sequence. Rather than worrying about which set operations can be added at which points to create a more optimal solution, let us instead consider that after each predicate atom application step, every possible combination of set operations between the already derived valuation sets (i.e., sets of valuations in the universe) is performed and available to us for the next step. This way, we only need to consider the order of predicate atom application steps in finding our optimal solution, simplifying the problem. Once an optimal sequence of predicate atom application steps has been found, we can reconstruct the intermediate set operation steps with bookkeeping. To formally state this, we provide the definitions: Definition 2. A set formula is any expression consisting of operators and sets as operands. The result of a set formula is its value after evaluation.
Note that the although an infinite number of set formulas may be constructed from a set of operators and operands, the number of unique results, and thus the set formula space itself, must be finite (specifically, since there are 2 n possible valuations, there can be at most 2 2 n unique results). In the previous example, D 1 ∩ D 1 is also a valid set formula which uses only ∩ and D 1 . However, its result is the same as D 1 , and there is no need to include it separately. If our sequence consists solely of predicate atom application steps, we can let S i = (P i , D i ), in which P i is a predicate atom and D i is a set of valuations from the universe U i−1 . Originally, we would just update the universe with just the result of the action: However, we now instead define: Definition 5. The extended universe U i is the set of all valuation sets that can be constructed with the first i predicate atom application steps and any number of set operations (∩, ∪, \). The extended universe can be characterized with the recurrence relation: is the normal universe and not the extended universe), then we can define the recurrence relation: The (j + 1)th value of the recurrence relation is generated by performing all possible set combinations (X ∩ Y, X ∪Y, X \Y, Y \X) between every pair of sets (X, Y ) from the jth value U (j) i . This is performed repeatedly until no new valuation set appears, and that becomes our ith extended universe: Steps in a predicate atom-only sequence may use any operand from this extended universe instead of the original universe. Note that this extended universe is merely logical and not actually be realized in memory by the algorithm. In fact, as Algorithm 1 shows, EvalPred requires few set operations between predicate atom application steps.
For each solution in Problem 1, there must exist a corresponding solution in this modified setup, so we can rewrite Problem 1 as: Problem 2. Given a predicate expression, find the sequence of steps [S 1 , S 2 , ..., S m ] which minimizes the total cost of the steps: m i=1 C(S i ). Assuming that extended universe U i represents the state of the valuation set extended universe after step i, the set of all valuations which satisfy the predicate expression must appear in the final extended universe U m . Furthermore, given that each step S i is a (P i , D i ) pair representing the predicate atom and operand, each operand D i must be an element of the extended universe U i−1 .

Necessity of Predicate Atoms
It makes intuitive sense that to derive the final set of all valuations which satisfy the given predicate expression, every predicate atom of that predicate expression must be applied at least once. Thus, the optimal sequence must contain each predicate atom as a step at least once. While this may seem obvious, it helps us to constrain the solution space down to only sequences of length n or greater. Theorem 2. Each predicate atom of the given predicate expression must appear at least once as a step in the solution sequence to ensure the set of all valuations which satisfy the predicate expression appears in the extended universe at the end of the sequence. Proof. We first introduce some notation. For any valuation v, let v i refer to the ith value of v (i.e., the result of predicate atom of P i ). In addition, given valuation v, let the valuation v| i=T be the same valuation as v except the ith value is true. Similarly, v| i=F is the same valuation as v except that the ith value is false. Note that one of v| i=T and v| i=F must be equivalent to v. Multiple values may be assigned as well; the valuation v| i=T,j=F is the same as v except the ith value is true and the jth value is false.
Next, we introduce Lemmas 1 and 2. Lemma 1 states that for each predicate atom P i , there must exist some valuation for which only the result of P i (i.e., the ith element of the valuation) can determine whether the valuation satisfies the overall given predicate expression. At a high level, Lemma 2 states that before applying predicate atom P i , there is no way to split a set of valuations based on the ith value of a valuation. Lemma 1. Let P i refer to the ith predicate atom of the given predicate expression. There exists a valuation v such that v| i=T satisfies the overall predicate expression, but v| i=F does not.
Lemma 2. Given a predicate expression's predicate atoms {P 1 , ..., P n } and some valuation v ∈ {T, F } n , let D be some set of valuation sets. If every valuation set D ∈ D contains either both or neither of v| i=T and v| i=F , then every valuation set which can be derived from D without P i as an operator must also contain either both or neither of v| i=T and v| i=F . In other words: Now, assume to the contrary, sequence [S 1 , ..., S m ] does not contain any step with P i . Based on Lemma 1, let v be the valuation such that v| i=T satisfies the overall predicate expression and v| i=F does not. For [S 1 , ..., S m ] to be a valid sequence, there must exist a valuation set in the final extended universe U m which contains v| i=T but does not contain v| i=F . However, based on our definition of the extended universe, Since the origin set only contains the set of all valuations, and this obviously contains both v| i=T and v| i=F , the preconditions of Lemma 2 are met. Thus, every valuation set in the extended universe U m must contain either both v| i=T and v| i=F or neither v| i=T nor v| i=F . This is a contradiction, so the sequence [S 1 , ..., S n ] must contain predicate atom P i as an operator.

Minimizing Predicate Atom Usage
Next we show a slightly more surprising result. In the optimal sequence, each predicate atom application must appear exactly once. This is due to the triangle inequality-like property that we mentioned for our cost models. Theorem 3. Given a predicate expression with n unique predicate atoms, the optimal sequence of steps will be of length n and have exactly one predicate atom application step for each predicate atom.
Proof. Assume to the contrary that the optimal sequence is n + k steps long, for some k ≥ 1. By the pigeonhole principle, at least one predicate atom must appear at least twice in the sequence. Let P be the first predicate atom to do so, and let indices i and j, for some i < j, be the first two steps that P appears in: S i = (P, D i ) and S j = (P, D j ). We show that we can always construct a new, less costly sequence which does not include both S i and S j as steps, leading to a contradiction. There are two major cases: D i ∩ D j = ∅ : We can replace step S j with S j = (P, D j \ D i ) and still construct every set of valuations derived from U j−1 ∪ P (D j ), since we can directly calculate P (D j ) = P (D j \ D i ) ∪ (D j ∩ P (D i )). Therefore, replacing S j with S j gives us a less costly sequence while maintaining equivalence, leading to a contradiction. D i ∩ D j = ∅ : In this case, instead of applying P separately, we can combine steps S i and S j and replace them with a single step S = (P, D i ∪ D j ). With step S , we can directly calculate both P (D i ) = P (D i ∪ D j ) ∩ D i and P (D j ) = P (D i ∪ D j ) ∩ D j . It is clear that C(S ) < C(S i ) + C(S j ) due to the extra κ overhead. Thus, by replacing S i with S and removing S j , we have found a less costly sequence while maintaining equivalence, leading to a contradiction. There is a caveat when Calculating D i ∪ D j requires D j , which in turn requires P (D i ) which is not available before the ith step. However, Lemma 3 explicitly states that either this situation cannot arise or D j does not require P (D i ) in being derived. Thus, the contradiction is maintained. .., (P m , D m )] be the steps of a predicate evaluation system such that the set of all valuations which satisfy the given predicate expression is present in the final extended universe U m . Let steps i and j be the first two times that predicate atom P appears in such a sequence: P i = P j = P . If D i ∩ D j = ∅, then either D j can be derived directly from U i−1 without using P as an operator, or D j cannot be derived at all from U i−1 ∪ {P (D i )} without P as an operator.

Problem Restatement
With Theorems 2 and 3, we can restate the problem again: Problem 3. Given a predicate expression, find the sequence of steps [S 1 , S 2 , ..., S n ] which minimizes the total cost of the steps: n i=1 C(S i ). Assuming that extended universe U i represents the state of the valuation set extended universe after step i, the set of all valuations which satisfy the predicate expression must appear in the final extended universe U n . Furthermore, given that each step S i is a (P i , D i ) pair representing the predicate atom and operand, each operand D i must be an element of the extended universe U i−1 .

Setup
Problem 3 states that we are looking for a sequence of steps [S 1 , ..., S n ], in which each step S i is a predicate atom and operand pair (P i , D i ). Thus, the problem can be split into two components: (1) Finding the optimal sequence of predicate atoms [P 1 , ..., P n ].
We focus on the second component first. Our algorithms BestD and Update generate the optimal sequence of operands which minimize the total cost of applying all the predicate atoms, while ensuring that the set of all valuations which satisfy the predicate expression is present in the final extended universe. The critical distinction between the already presented EvalPred and BestD/Update is that BestD/Update are guaranteed to generate the optimal sequence of operands for any sequence of predicate atoms, while EvalPred expects OrderP to be a DFS traversal of the predicate expression.
To understand BestD and Update, we first provide some definitions. In all of the following definitions, the "associated predicate tree" refers to the tree created by "makeTree" from Algorithm 1, and the expression n.P is used to refer to the predicate atom that leaf node n points to. Definition 6. Given an ordering of a predicate expression's predicate atoms [P 1 , ..., P n ], node n of the associated predicate tree is complete on step i if: Given an ordering of a predicate expression's predicate atoms [P 1 , ..., P n ], node n of the associated predicate tree is positively determinable on step i if: Algorithm 2 BestD Input: Predicate tree node node, algorithm state state, predicate atom P i , step index i Output: Optimal operand D i to apply P i to 1: if node = Nil then 2: for child ∈ children(node) do 6: if complete(child, i) then 7: else if determ − (child, i) and isNotAncestor(child, P i ) then 9: for child ∈ children(node) do 15: if complete(child, i) then 16: Given an ordering of a predicate expression's predicate atoms [P 1 , ..., P n ], node n of the associated predicate tree is negatively determinable on step i if: The completeness of a node n on step i indicates whether the predicate atom of every leaf node descendant of n has already been applied by step i. If node n is complete, the exact set of all valuations which satisfy the predicate subexpression represented by n can be derived from the current extended universe; thus, these sets no longer need to be evaluated by future predicate atoms and can be removed from future operands. Positively (negatively) determinable nodes, on the other hand, can determine a subset of valuations which satisfy (do not satisfy) the predicate expression represented by the node. While not the full set, these subsets can still help to reduce the size of the operands for any unapplied predicate atoms of descendent leaf nodes.

BestD and Update
We now present BestD and Update in Algorithms 2 and 3 respectively. We also provide pseudocode of how one might use these algorithms in conjunction with OrderP in Algorithm 4. As can be seen from Algorithm 4, BestD determines the optimal operands [D 1 , ..., D n ], while Update applies predicate atoms to these operands and uses the state variable to keep track of valuation sets for complete and positively/negatively determinable nodes. The valuation sets in state are used by BestD to reduce the size of generated operands as much as possible.
Starting from Algorithm 4, leafNodes is a mapping from predicate atom P i to the predicate tree leaf node which contains that predicate atom. Variable state is an object which has three attributes: cmp, det + , and det -. Each of these attributes is a mapping from a predicate tree node to the valuation sets that can be determined by completion, positive determinability, and negative determinability respectively. Specifically, cmp contains the mappings to the set of valuations which satisfy the predicate subexpression represented by the node, while det + (det -) contains mappings to a subset of the valuations which satisfy (do not satisfy) the Algorithm 3 Update Input: Predicate tree node node, algorithm state state, predicate atom P i , set of valuations D i , step index i 1: if node = Nil then 2: if complete(node, i + 1) then 10: predicate subexpression represented by the node. The "initState" function creates a mapping to an empty set for every predicate tree node in the predicate tree for each of these attributes. The "parent" function of a node node returns the parent of node in the predicate tree; Nil is returned if node is the root node. The expression isNotAncestor(node, P i ) returns true if P is not a descendant of node. The root node is complete at the end of the n steps, since all n predicate atoms have been applied, and the set of valuations which satisfy the predicate expression for the complete root node is the final return value.
BestD determines the optimal operand for a predicate atom P i by traversing the predicate tree in a bottom-up manner. In the beginning, no nodes are complete nor determinable, so BestD has no choice but to return the set of all possible valuations for the first predicate atom; the algorithm traverses all the way to the parent of the root node, sees that it is Nil, and returns the set of all possible valuations {T, F } n . As state gets updated, the operand is trimmed according to the completeness and determinability of sibling nodes. As Lines 7 and 16 show, the intersection is taken for complete AND children, and additional sets are added to the set subtraction for complete OR children. Additionally, for AND children which are negatively determinable, the detmapping holds a subset of the valuations which do not satisfy those children's predicate subexpressions. Any valuation which does not satisfy the child of an AND node cannot satisfy the AND node itself, so the valuation no longer needs to be considered and is removed from the returned operand. Similarly, for OR children which are positively determinable, the det + mapping holds the subset of valuations which satisfy those children's predicate subexpression. Since these valuations already satisfy one child of an OR node, they do not need to be considered again for the remaining children of the OR node.
Update also traverses the predicate in a bottom-up fashion. It takes as input the current step's predicate atom P i and the optimal operand D i generated by BestD. The leaf node actually applies the predicate atom with P i (D i ) and updates state with both the set of valuations which satisfy and do not satisfy P i . After applying the predicate atom, Update is called on the ancestors of the leaf node. If an ancestor AND/OR node would be considered complete or positively/negatively determinable on step i + 1 now that P i has been applied, its cmp and det + /detvalues are updated correspondingly. Note that the expression child in these lines are used as a shorthand for child∈children(node) . For completed nodes, the cmp value of the AND (OR) node is the intersection (union) of its children. For an AND node, a valuation can only be considered a candidate to satisfy the node, and therefore an element of det + , if that valuation is a candidate for each of the AND node's positively determinable children; thus, the intersection in Line 12. On the other hand, a valuation is guaranteed to not satisfy an AND node, and be a part of det -, if it does not satisfy any of the AND node's children, inducing the union in Line 14. Similarly, a valuation is guaranteed to satisfy an OR node, and be part of det + , if the valuation satisfies any one of the OR node's children, inducing the union in Line 20. On the other hand, a valuation is only guaranteed to not satisfy an OR node, and be a part of det -, if the valuation does not satisfy every one of the OR node's children, inducing the intersection in Line 22.

Notation
The remainder of this section includes proofs of correctness and optimality for BestD and Update. We first provide some additional definitions, notation, and basic properties that will be used throughout these proofs. Definition 9. Given an ordering of predicate atoms [P 1 , ..., P n ] for a predicate expression, let index i be the position at which predicate atom P i appears in the ordering. If node is a node in the associated predicate tree, we define the rank of node on step i, denoted r(node, i), to be the largest index among node's predicate atom descendants that is smaller than i. If no such predicate atom exists, r(node, i) = 0. The final rank of node is the largest index among node's predicate atom descendants without any constraint and is be denoted as r * (node).
Put another way, the rank of node on step i is the latest step index on which a predicate atom descendant of node is applied. More explicitly, if node has predicate atom P j as a descendant and j < i, and node has no other predicate atom descendants P k such that j < k < i, then r(node, i) = j. If node is a leaf node, it considers itself as a descendant, so if node refers to predicate atom P j , r(node, i) = j if j < i and r(node, i) = 0 otherwise. The final rank of node is the largest index among its predicate atom descendants and can be seen as the last step before node becomes complete. Note that r * (node) = r(node, n + 1), since all predicate atoms must be complete after n steps.
To reason about the state variable whose value continuously changes throughout multiple steps in BestD/Update, we denote state i to be the value of state at the beginning of the ith step (before any updates). We also need a way to refer to node's complete, positively determinable, and negatively determinable children on step i. For this, we introduce the functions: children • (node, i), children + (node, i), and children − (node, i) which return node's complete, (incomplete) positively determinable, and (incomplete) negatively determinable children on step i respectively. We also use the convention of c • , c + , and c − to refer to a complete, positively determinable, and negatively determinable child respectively. Throughout the section we may refer to leaf nodes which contains predicate atoms as the predicate atoms themselves. For example, if node is a leaf node which contains predicate atom P i , the expression "P i 's parent" may be used to refer to node's parent. As another example, if we talk about all predicate atom descendants of a node, we are referring to the predicate atoms of the leaf node descendants of that node. Finally, in calls to BestD, we omit the state argument since it refers to the same object every time.
Next, we present some properties which we use throughout the proofs. Property 2. For any predicate atom P and valuation sets D and E: If we imagine that each predicate atom P has a corresponding set ref P which contains all possible valuations that satisfy P , then applying P (D) is akin to taking the intersection of ref P and D: P (D) = ref P ∩ D. Thus, any properties which pertain to normal intersection of sets also pertain to applied predicate atoms. Property 3. If node is not complete on step i but complete on step i + 1, then for all j > i: This property simply states that state[node].cmp does not change once node is complete. This is easy to see since the cmp attribute of state[node] is only ever updated once: right after node becomes complete. Once a node is complete, all its predicate atom descendants have already been applied, and it can never again become an ancestor of an incomplete predicate atom node. Thus, it will never be updated again as an ancestor in Update. Property 4. For any node and step indices i and j: This should make intuitive sense since the cmp/det + attributes for node holds valuations which satisfy the subexpression represented by node, while dethold valuations which do not satisfy the subexpression represented by node. Property 5. If node is complete on step i: This is easy to verify with induction. For leaf nodes, the cmp and det + attributes are set to the same value, and the lines in Update updating cmp and det + for non-leaf nodes become equivalent once they are complete.

Proof of Correctness
We prove the correctness of BestD/Update and GeneralEvalPred with Theorem 4. Theorem 4 states that if node is complete on step i, then state i [node].cmp must be the set of valuations in BestD(parent(node), state r * (node) , r * (node)) which satisfy the predicate subexpression represented by node. rootNode has n predicate atom descendants, so it must be complete after n steps. Given that parent(rootNode) is Nil, according to Algorithm 2, BestD(parent(rootNode), , ) returns {T, F } n . Since rootNode represents the entire predicate expression, state n+1 [rootNode].cmp must return the subset of {T, F } n which satisfies the predicate expression. Theorem 4. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a node in the associated predicate tree. Furthermore, let ref node be the set of all valuations which satisfy the predicate subexpression represented by node. On step i, if node is complete: Proof. Our proof for Theorem 4 is by strong induction on the height of the tree referred to by node. As the base case, let node be a leaf node which refers to predicate atom P j . Since node is complete on step i, that must mean that j < i, and node has been complete since step j + 1. Thus: Step (i) is a direct application of Property 3.
Step (ii) comes directly from Algorithm 3.
Step (iii) is simply the definition of r * (node). Finally, since node is a leaf node pointing to predicate atom P j , ref node = P j ({T, F } n ), and by applying Property 2, we get the last step, thereby proving the base case.
As the inductive hypothesis, assume that the theorem applies for all nodes in the predicate tree with height k or less. If node has a height of k + 1, node must either be an AND or OR node.
If node is an AND node, and node is complete on step i, Property 3 tells us that state i [node].cmp = state r * (node)+1 [node].cmp. Furthermore, Line 10 of Algorithm 3 states: Since all children of node must have height k or less and must be complete by the time node is complete, they must follow the inductive hypothesis. For any child c of node: Based on Lines 7 and 9 of Algorithm 2: Thus, Equation 2 expands to: Since node is only complete once all its children are complete, we can apply Lemma 4 (stated below) and assert BestD(parent(node), r * (node)) ⊆ BestD(parent(node), r * (c)). Then, we substitute Equation 3 back into Equation 1 to derive: We observe that the state r * (c) [c • ].cmp component in the second line of Equation 4 can be expanded using Equation 3. By repeatedly plugging Equation 3 into Equation 4, using Lemma 4, applying the identities for any sets A, B, C, and D (Appendix C), and removing duplicates, we get: .detmust be mutually exclusive for any step index i, so this simplifies to: .., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-leaf node in the associated predicate tree. For all pairs of node's predicate atom descendants P i and P j for which i < j: If node is an OR node, and node is complete on step i, Property 3 tells us again that state i [node].cmp = state r * (node)+1 [node].cmp. Line 18 of Algorithm 3 states: Since all children of node must have height k or less and must be complete by the time node is complete, they must follow the inductive hypothesis. For any child c of node: Based on Algorithm 2, this expands to: .det + , so this reduces to: We can once again apply Lemma 4 (BestD(parent(node), r * (node)) ⊆ BestD(parent(node), r * (c))) and substitute back into Equation 5 to get: We can apply the distributive property to pull the BestD outwards: Next, we introduce Lemma 5. Lemma 5. For any sets A, B, C, D, E, and F , if F ⊆ B and F ∩ C = ∅, then: In our case, for two different children c * and c : If we apply this trick to every child c of node, this simplifies to: .., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a node in the associated predicate tree. For any step index i: .., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-leaf node in the associated predicate tree. Furthermore, Let c and c be two different children of node. If node is an OR node, for all steps i and j: If node is an AND node, then for all steps i and j: 3.5 Proof of Optimality Theorem 5. For a given predicate expression and some ordering of its predicate atoms [P 1 , ..., P n ], the sequence of operands [D 1 , ..., D n ] generated by BestD and Update lead to the lowest cost (i.e., n i=1 C((P i , D i ))) possible, while still ensuring the set of all valuations which satisfy the predicate expression is in the extended universe after the nth step.
Proof. Assume to the contrary that there exists a better sequence of operands [D 1 , ..., D n ]. This must mean that there is at least one step i for which C(P i , D i ) < C(P i , D i ). Let i be the index of the first such step. Since D i and D i are different, to incur a cheaper cost, D i must be missing at least one valuation v that is present in D i . However, we show that if we apply P i to the operand D i that is missing v, we are not able to generate the set of all valuations which satisfy the given predicate expression, leading to a contradiction.
Let us consider a set of valuations D i from the extended universe In this case, the set of all possible valuations {T, F } n obviously contains all valuations (satisfying the precondition), thus the derived valuation set D i ∈ U i−1 must also contain either both or neither of v| i=T and v| i=F for any valuation v according to Lemma 2. If valuation v ∈ D i , then both v| i=T and v| i=F must be in D i . Furthermore, since P i+1 is also not included as an operator in the construction of U i−1 and v| i=T ∈ D i , both v| i=T,(i+1)=T and v| i=T,(i+1)=F must also be in D i by Lemma 2. Similarly, v| i=F,(i+1)=T and v| i=F,(i+1)=F must also be in D i . This logic can be applied recursively for all indices in i, ..., n, and the same logic can be applied in converse for when v ∈ D i . We define: Note that the 0th valuation group of any valuation is the set of all possible valuations {T, F } n .
Then, as a direct corollary of Lemma 2: Corollary 1. Given a predicate expression's ordering of predicate atoms [P 1 , ..., P n ] and any valuation v ∈ {T, F } n . Any set derived from {{T, F } n } without using {P i , . .., P n } as operators must either include the entirety of or not have any elements in common with the ith valuation group of v. In other words: In a similar vein, we present the following lemma which remarks that since each predicate atom is necessary for the final result, there exists at least one pair of valuations which must be distinguished by the ith value of valuation v using the ith predicate atom P i : Lemma 8. Given a predicate expression's ordering of predicate atoms [P 1 , ..., P n ], let valuation set D i be the ith operand generated by BestD and Update. For all valuations v ∈ D i , there exists a valuation u ∈ Γ(v, i) such that only one of u| i=T and u| i=F satisfies the given predicate expression.

Algorithm 5 BestD
Input: Predicate tree node node, algorithm state state, predicate atom P i , step index i Output: Optimal operand D i to apply P i to 1: if node = Nil then 2: return {T, F } n 3: else if isLeafNode(node) then 4: return BestD(parent(node), state, P i , i) 5: else if isAndNode(node) then 6: X ← BestD (parent(node), state, i) 7: for child ∈ children(node) do 8: if complete(child, i) then 9: for child ∈ children(node) do 15: if complete(child, i) then 16: As we initially stated, if the operand D i is cheaper than operand D i , then D i must contain some valuation v that is not in D i . Since D i and D i must both come from the extended universe U i−1 , Corollary 1 applies.
Valuation v's ith valuation group must be a subset of D i , and at the same time, cannot have any elements in common with . By Lemma 8, there must exist at least one valuation u ∈ Γ(v, i) such that only one of u| i=T and u| i=F satisfies the predicate expression. However, since Γ(v, i) is mutually exclusive with D i , any derived valuation set from U i−1 ∪ {P i (D i )} without P i as an operator must contain either both or neither of u| i=T and u| i=F according to Lemma 2. Since each predicate atom can be applied once at most, we have no more opportunities to apply P i , and every valuation set in the final extended universe will contain either both or neither of u| i=T and u| i=F . However, this is a contradiction since the set of all valuations which satisfy the given predicate expression must come from the final extended universe and contains only one of u| i=T and u| i=F . Thus, thus the sequence [D 1 , ..., D n ] generated by BestD and Update must be optimal.

Predicate Atom Ordering
We now turn our attention to the ordering of predicate atoms: OrderP. As mentioned previously, thanks to existing work on disjunctions for row-oriented databases, there are actually a few contenders for OrderP. In our implementation, we use Hanani as our OrderP. Not only is Hanani simple to implement and have a low runtime cost of O(n log n), the ordering returned by Hanani is guaranteed to traverse the predicate tree in a DFS manner. It is exactly this DFS traversal that allows us to reduce BestD and Update into EvalPred.
Lemma 9. Given a DFS ordering of predicate atoms for a predicate expression, if node node of the associated predicate tree is the child of an AND node and negatively determinable on step i, node must be complete on step i. Similarly, if node is the child of an OR node and positively determinable on step i, node must be complete on step i.

Reduction to EvalPred
Lemma 9 allows us to effectively ignore determinability in BestD, since all determinable nodes are also complete. Since determinability is never checked, both det + and detmappings are unused, and we can ignore the lines updating them in Update. Algorithm 5 and 6 (BestD and Update respectively) show if complete(node, i + 1) then 10: return X 3: else if isAndNode(node) then 4: for child ∈ children(node) do 5: if complete(child, i) then 6: return BestDFlipped(child, X, state, P i , i) 9: else 10: Y ← {} 11: for child ∈ children(node) do 12: if complete(child, i) then 13: what BestD and Update would look like after removing these lines.
Algorithm 5 works by traversing the predicate tree in a bottom-up fashion. Each node calls BestD on its parent, takes the returned value, modify it based on completed children, and return the filtered value to the child which called it. We can instead imagine constructing a dual algorithm which traverses the predicate top-down for any specific predicate atom; this is presented in Algorithm 7. For any predicate atom P i : Note that the expression chlidOfAndAncestorOf(node, P i ) returns the child of node which is the ancestor of the node referring to P i .
We can also combine BestDFlipped and Update . This will traverse top-down from the root node to P i for the BestD value and then traversing back up to the root node, updating state for complete nodes. Algorithm  together into one algorithm. We assume that the nodes of the predicate tree already sorted in the ordering given by [P 1 , ..., P n ]. Also, since everything is done in one pass, instead of a separate state variable, we simply use the returned values of each child.
As we can see, there is a 1-to-1 correspondence between Algorithm 9 and EvalPred. The only differences are: 1. check is named X in Algorithm 9.
2. Algorithm 9 does not feature early returns. 3. EvalPred operates on Boolean arrays representing sets of records, while Algorithm 9 operates on sets of valuations. 4. EvalPred uses bit operations, whereas Algorithm uses 9 uses set operations.
However, as mentioned before, sets of valuations are completely capable of representing sets of records. Thus, these differences are not significant, and the reduction is complete.

Depth-3+ Predicate Expressions
Hanani always returns a DFS ordering. For predicate expressions of depth 2 or less, this is not a problem since the optimal ordering is guaranteed to be DFS as well due to the following lemma: Lemma 10. Given any ordering of predicate atoms for a predicate expression of depth 2 or less, if node node of the associated predicate tree is the child of an AND node and negatively determinable, then node must be complete. Similarly, if node is the child of an OR node and positively determinable, then node must be complete.
As can be seen from Algorithm 2, only determinable nodes can affect the output operands for BestD. Thus, similar to Lemma 9, all relevant determinable nodes which affect the output operands in BestD must also be complete, and a DFS traversal is optimal. However, for predicate expressions of depth 3 or greater, the optimal sequence of predicate atoms may not follow a DFS pattern. Here is an example:

Algorithm 9 CombinedAll
Input: Predicate tree node node, filtered valuation set X 1: if isLeafNode(node) then 2: return P i (X) 3: else if isAndNode(node) then 4: for child ∈ children(node) do 5: for child ∈ children(node) do 10: return Y Example 1. Let the given predicate expression be P A ∧ (P B ∨ (P C ∧ P D )) in which P A , P B , P C , and P D are predicate atoms with selectivities γ A = 0.820, γ B = 0.313, γ C = 0.469, γ D = 0.984 and constant cost factors To calculate the cost of Hanani's ordering [P C , P D , P B , P A ]: 1. P C is applied to all records, leading to a cost of 1. 2. P D is then applied to all records for which P C is true, for a cost of γ C = 0.469. 3. P B is then applied to all records for which either P C or P D is not satisfied. Using the independence assumption, γ C∧D = γ C γ D = 0.461. Thus, the cost is 1 − 0.461 = 0.539. 4. Finally, P A is applied to all records for which P B ∨ (P C ∧ P D ) is satisfied. Using the independence assumption: γ B∨(C∧D) = γ B + γ C∧D − γ B γ C∧D = 0.630.
Let us now consider the ordering [P B , P C , P A , P D ]. Note this is not a DFS traversal, since the node containing P A is visited before its sibling is complete. To calculate the cost: 1. P B is applied to all records, leading to a cost of 1.
2. P C is then applied to all records for which P B is false, for a cost of 1 − γ B = 0.687. 3. P A is then applied to all records for which either P B or P C is true: γ B∨C = γ B + γ C − γ B γ C = 0.635. 4. Finally, P D is applied to all records for which P A ∧¬P B ∧P C is true: This leads to a total cost of 2.586, confirming the suboptimality of Hanani for depth-3 predicate expressions.
Determinability prevents us from dividing the problem into well-contained subproblems, and at each level, we must consider all possible determinable subsequences, of which there are exponentially many. Unfortunately, despite the authors' best efforts, we were unable to come up with a reduction from an NPcomplete problem.
However, even for these orderings which do not follow a DFS traversal, BestD and Update are still guaranteed to produce the lowest cost operands possible while making sure the final set of valuations which satisfy the predicate expression is derivable. Thus, if a polynomial-time algorithm to optimally order the predicate atoms of a depth-3+ predicate expression appears, it could be combined with BestD/Update to birth an end-to-end, polynomial-time, optimal algorithm for depth-3+ predicate expressions.

Evaluation
Since the primary cost we are concerned with is time, we evaluated our experiments with respect to two metrics: (1) Runtime: The time it takes to generate and execute a predicate evaluation plan 3 (until a bitmap of indices which satisfies the predicate expression is returned).
(2) Number of Evaluations: The sum total number of times a query's predicate atoms are evaluated (each evaluation of a predicate atom on a record counts as 1). This provides an implementation-agnostic measure of our algorithms.
NoOrOpt. Our straw man algorithm which does not have any optimizations for disjunctions. It evaluates conjunctions in increasing order of selectivity, but treats disjunctions as completely separate predicate expressions to be evaluated independently from one another. Although this may seem simplistic, this is the actual strategy employed by many real-world systems for disjunctions. GreedyD3. The combination of BestD/Update and OneLookaheadP, a greedy OrderP algorithm for depth-3+ predicate expressions. OneLookaheadP orders predicate atoms by performing the following procedure at each step: (1) For each remaining predicate atom, calculate the cost of applying the predicate atom and estimate the cost of the remaining steps using EvalPred.
(2) Return the predicate atom for which the sum of these two values is smallest. Though GreedyD3 is not guaranteed to be optimal, it is capable of generating non-DFS orderings and serves as a point of comparison for deeply-nested predicate expressions.
BDC. The combination of BestD/Update and BDC as the OrderP algorithm. Similar to GreedyD3, this algorithm is not guaranteed to be optimal, but serves as a good comparison point for predicate expressions of depth 3 or greater.
Tdacb. The current state-of-the-art algorithm, capable of generating optimal predicate evaluation plans for general Boolean expressions. Although the optimality of the plans ensures that the minimum number of evaluations is incurred, it comes at the cost of real runtime due to planning overhead.
Key Takeaways: EvalPred outperformed all other algorithms in runtime, with average speedups of up to 2.6× over NoOrOpt, 1.4× over GreedyD3, and 1.8× over BDC for the top 10% of queries. While Tdacb produced comparable runtimes for simpler predicate expressions, it resulted in runtimes orders of magnitude greater than even NoOrOpt for more complex expressions. For depth-2 predicate expressions, EvalPred had the same number of evaluations as Tdacb, verifying that it is optimal for the depth-2 case. For depth-3 predicate expressions, EvalPred still came quite close to the optimal number of evaluations, with 92% of queries within 5% of optimal.

Experimental Setup
Dataset. We used the Forest dataset [2] that was used in the majority of the experiments evaluating Tdacb [16]. The dataset has 10 quantitative attributes and 2 qualitative attributes of interest. Because we wanted to evaluate our algorithms on more than just 12 predicate atoms, we duplicated the original dataset 40 times, shuffled the records of each duplicate dataset, and added the attributes of the shuffled datasets as additional attributes of the original dataset, giving us a total of 480 attributes. Furthermore, the original dataset only contained 581K records, so we repeated the records 100 times for a total of 58M records. Altogether, the size of the generated dataset was 208GB. Queries. To mirror the evaluation of Tdacb [16], we used selection queries with randomly generated predicate expressions ranging up to 16 predicate atoms. However, Kastrati and Moerkotte's evaluation of Tdacb included logically related predicate atoms, and Tdacb leveraged Boolean implication (e.g., P 1 implies ¬P 2 ) to significantly increase its runtime performance. Since we wanted to directly measure the impact of the number of predicate atoms on our algorithms, we chose to make every predicate atom independent of each other. Furthermore, Tdacb was only evaluated on CNF and DNF queries, meaning their predicate expressions had a maximum depth of 2. In contrast, our predicate expressions were generated according to the following criteria. The root of the predicate tree was randomly chosen to either be an AND or an OR. Each predicate expression had a predetermined max depth of 2, 3, or 4. Each non-leaf node had a randomly chosen number of children between 2 and 5, and each child had some chance to be a leaf node, ensuring that we did not only test on balanced trees. For each of the quantitative attributes, we generated a simple x < c comparison predicate atom where c could one of 9 different constants, resulting in selectivities of [0.1, 0.2, ..., 0.9]. For the two qualitative attributes, we had equality predicate atoms of the form x = c where c is one of the possible values of that attribute (one had 4 possible values and the other had 7). For experiments with variable-cost predicate atoms, sleep times of 1-10ns were added per evaluation of a record to emulate variable cost. System. To evaluate our algorithms, we built a column-oriented database system capable of parsing and executing SQL selection queries with predicates, joins, and group-bys. In addition to simple inequality comparisons, our system is capable of handling predicates with regular expressions and commonly used functions, such as avg or substr. Generated plans are evaluated in single-threaded environment. Data is stored in columns on disk and intermediate filter results are stored as bitmaps. Our system is coded in Rust and contains around 6500 lines of code in total. All four algorithms were implemented in this system, and all of our experiments were conducted on a server with 64 Intel(R) Xeon(R) CPU E7-4830 @ 2.13GHz processors, 256GB of memory, and a RAID5 configuration of 7200rpm HDDs. Note that using a different storage backend may change absolute runtimes, but not the number of evaluations. Experiments. We conducted a total of 6 sets of experiments. Each set of experiments had either a uniform or varying-cost for all its predicate atoms and a fixed depth for its predicate expressions. 500 queries with randomly generated predicate expressions were used for each experiment. Figure 1 shows the results of our experiments with depth-2 predicate expressions and uniform predicate atom cost. We plot the average runtimes of EvalPred, NoOrOpt, and Tdacb when grouped by the number of predicate atoms in Figure 1(a). The same data is shown zoomed-in in Figure 1(b). Finally, we plot the average total number of evaluations incurred by each algorithm when grouped by the number of predicate atoms in Figure 1(c). As can be seen, Tdacb quickly becomes unviable for higher numbers of predicate atoms due to its exponential nature, incurring runtimes orders of magnitude greater than even NoOrOpt. However, even for smaller numbers of predicate atoms, EvalPred outperformed Tdacb with average speedups of 1.12× and 1.28× for 8 and 10 predicate atoms respectively. Since Figure 1(c) shows that number of evaluations performed by EvalPred and Tdacb are the same, this disparity must come from the difference in planning time. With respect to NoOrOpt, EvalPred enjoyed a consistent 1.41× average speedup in runtime and a total average of 1.88× speedup in number of evaluations. For the top 10% of queries, EvalPred had an average speedup of 2.12× in runtime and 4.04× in number of evaluations over NoOrOpt.

Depth-2 Predicate Expressions
We saw the same patterns for depth-2 predicate expressions with varying-cost predicate atoms. Tdacb continued to exhibit the same exponential behavior, but EvalPred outperformed Tdacb for even smaller numbers of predicate atoms with the same average speedups of 1.12× and 1.28× for 8 and 10 predicate atoms respectively. EvalPred also consistently outperformed NoOrOpt with a total average speedup of 1.43× in runtime and a total average speedup of 1.86× in number of evaluations. Figure 2 shows the results of our experiments for depth-3 predicate expressions with varying-cost predicate atoms. We plot the average runtimes of EvalPred, NoOrOpt, GreedyD3, BDC, and Tdacb when grouped by the number of predicate atoms in Figure 2(a). As Figure 2(a) shows, despite not being optimal, EvalPred still achieved the best runtime performance out of any algorithm, with total average speedups of 1.43× over NoOrOpt, 1.13× over GreedyD3, and 1.29× over BDC. For the top 10% of queries, EvalPred had average speedups of 2.60× over NoOrOpt, 1.36× over GreedyD3, and 1.84× over BDC. Tdacb exhibited the same exponential behavior as before and had runtimes orders of magnitude greater than NoOrOpt for 14-16 predicate atoms. Even for 8 and 10 predicate atoms, EvalPred outperformed Tdacb with average speedups of 1.10× and 1.21× respectively.

Depth-3+ Predicate Expressions
Though Tdacb's runtimes may be high, the plans that it generates are still optimal. As such, the number of evaluations incurred by Tdacb can be seen as the minimum possible for any given query and serve as a good reference for how close EvalPred comes to optimal for depth-3+ predicate expressions. Figure 2(b) shows the CDF of speedups in number of evaluations of various algorithms over Tdacb. It is apparent that EvalPred comes quite close to achieving optimal performance even for depth-3 predicate expressions, with 92% of queries within 5% of optimal. In comparison, GreedyD3 does not reach 15% of optimal for even 60% of queries, and others fare much worse. To serve as another comparison point, Figure 2(c) shows the CDF of speedups in runtime of EvalPred over GreedyD3. As mentioned before, GreedyD3 is able to generate orderings which are not DFS traversals, and this makes a difference for 6% of queries, in which GreedyD3 achieved better runtime performance than EvalPred. However, for the vast majority of queries, EvalPred still performed at least as well as, if not better than, GreedyD3. BDC also had similar results with only 4% of queries performing better than EvalPred.
Depth-3, uniform-cost predicate expressions and depth-4 predicate expressions exhibited very similar patterns to the depth-3, varying-cost case. With less than a 2% difference in total average speedups, the plotted figures were almost identical, so we do not show them separately here.

Conclusion
Predicate evaluation for disjunctions in column-oriented databases is in need of optimization. To address this issue, we present EvalPred. Our analysis and evaluation shows that EvalPred is optimal for all predicate expressions of depth 2 or less and still quite close to optimal for depth-3+ predicate expressions.
We hope that many systems can take advantage of our work and implement these optimizations to improve the performance of predicate evaluation.

A.1 Additional Definitions
We first provide some additional definitions that we will use throughout this section. Definition 11. For any predicate tree node node, we define the lineage of node as the sequence of ancestor nodes [A 1 , . .., A m ] in which A 1 is the parent of node, and A i+1 is the parent of A i for all i ∈ {1, ..., m − 1}, and A m is the root node.
Simply put, the lineage of node is the sequence of its ancestors starting with the parent up to the root. For example, if node a leaf node referring to the predicate atom P i , node[v] = T if and only if v i = T . In the following text, we may say that v is "evaluated against the subexpression represented by node" or "evaluated against node" to refer to the same thing.

A.2 Reference
For the reader's convenience, before diving into the proofs, we first list both BestD and Update algorithms and all definitions, properties, and lemmas used in this paper. The reader may refer to this section when reading through the proofs. In addition, Table 1 provides a table of some notation that we think would be helpful for the reader to remember when reading this section. Good luck.

Symbol
Meaning The value of the ith element of valuation v v| i=T Refers to the valuation that is the same as All valuations for which the first i − 1 elements are the same as v ref node The set of all valuations which satisfy node's predicate subexpression node [v] Evaluating valuation v against the subexpression represented by node r(node, i) The step index of node's last predicate atom descendant before i r * (node) The step index of node's final predicate atom descendant (i.e., r(node, n + 1)) children • (node, i) The set of complete children of node on step i children + (node, i) The set of positively determinable (but not complete) children of node on step i children − (node, i) The set of negatively determinable (but not complete) children of node on step i c X ← BestD(parent(node), state, i) 5: for child ∈ children(node) do 6: if complete(child, i) then 7: X ← X ∩ state[child].cmp 8: else if determ − (child, i) and isNotAncestor(child, P i ) then 9:

A.2.2 Definitions
Definition 1. We define universe U i as the set of all valuation sets which have been constructed by the first i steps of a predicate evaluation system. Definition 2. A set formula is any expression consisting of operators and sets as operands. The result of a set formula is its value after evaluation. Definition 5. The extended universe U i is the set of all valuation sets that can be constructed with the first i predicate atom application steps and any number of set operations (∩, ∪, \). The extended universe can be characterized with the recurrence relation: Given an ordering of predicate atoms [P 1 , ..., P n ] for a predicate expression, let index i be the position at which predicate atom P i appears in the ordering. If node is a node in the associated predicate tree, we define the rank of node on step i, denoted r(node, i), to be the largest index among node's predicate atom descendants that is smaller than i. If no such predicate atom exists, r(node, i) = 0. The final rank of node is the largest index among node's predicate atom descendants without any constraint and is be denoted as r * (node). Definition 13. Let node be a node in the predicate tree. We say that node is statically true with respect to a valuation set D if D ⊆ ref node and statically false with respect to D if D ∩ ref node = ∅. If node is either statically true or statically false with respect to a valuation set, it is said to be static with respect to that valuation set. Otherwise, node is dynamic with respect to that valuation set.

A.2.3 Properties
Property 1. For any predicate tree node node and relation R, EvalNode(node, F R , R) = F R .
Property 2. For any predicate atom P and valuation sets D and E: If node is not complete on step i but complete on step i + 1, then for all j > i: Each predicate atom of the given predicate expression must appear at least once as a step in the solution sequence to ensure the set of all valuations which satisfy the predicate expression appears in the extended universe at the end of the sequence. Theorem 3. Given a predicate expression with n unique predicate atoms, the optimal sequence of steps will be of length n and have exactly one predicate atom application step for each predicate atom. Theorem 4. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a node in the associated predicate tree. Furthermore, let ref node be the set of all valuations which satisfy the predicate subexpression represented by node. On step i, if node is complete: .cmp = ref node ∩ BestD(parent(node), r * (node)) Theorem 5. For a given predicate expression and some ordering of its predicate atoms [P 1 , ..., P n ], the sequence of operands [D 1 , ..., D n ] generated by BestD and Update lead to the lowest cost (i.e., n i=1 C((P i , D i ))) possible, while still ensuring the set of all valuations which satisfy the predicate expression is in the extended universe after the nth step.

A.2.5 Lemmas
Lemma 1. Let P i refer to the ith predicate atom of the given predicate expression. There exists a valuation v such that v| i=T satisfies the overall predicate expression, but v| i=F does not. Lemma 2. Given a predicate expression's predicate atoms {P 1 , ..., P n } and some valuation v ∈ {T, F } n , let D be some set of valuation sets. If every valuation set D ∈ D contains either both or neither of v| i=T and v| i=F , then every valuation set which can be derived from D without P i as an operator must also contain either both or neither of v| i=T and v| i=F . In other words: .., (P m , D m )] be the steps of a predicate evaluation system such that the set of all valuations which satisfy the given predicate expression is present in the final extended universe U m . Let steps i and j be the first two times that predicate atom P appears in such a sequence: P i = P j = P . If D i ∩ D j = ∅, then either D j can be derived directly from U i−1 without using P as an operator, or D j cannot be derived at all from U i−1 ∪ {P (D i )} without P as an operator. Lemma 4. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-leaf node in the associated predicate tree. For all pairs of node's predicate atom descendants P i and P j for which i < j: BestD(parent(node), j) ⊆ BestD(parent(node), i) Lemma 5. For any sets A, B, C, D, E, and F , if F ⊆ B and F ∩ C = ∅, then: Lemma 6. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a node in the associated predicate tree. For any step index i: .., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-leaf node in the associated predicate tree. Furthermore, Let c and c be two different children of node. If node is an OR node, for all steps i and j: If node is an AND node, then for all steps i and j: Given a predicate expression's ordering of predicate atoms [P 1 , ..., P n ], let valuation set D i be the ith operand generated by BestD and Update. For all valuations v ∈ D i , there exists a valuation u ∈ Γ(v, i) such that only one of u| i=T and u| i=F satisfies the given predicate expression. Lemma 9. Given a DFS ordering of predicate atoms for a predicate expression, if node node of the associated predicate tree is the child of an AND node and negatively determinable on step i, node must be complete on step i. Similarly, if node is the child of an OR node and positively determinable on step i, node must be complete on step i.

Lemma 10.
Given any ordering of predicate atoms for a predicate expression of depth 2 or less, if node node of the associated predicate tree is the child of an AND node and negatively determinable, then node must be complete. Similarly, if node is the child of an OR node and positively determinable, then node must be complete.
Lemma 11. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-root node in the associated predicate tree. If node's parent is an OR node, node is positively determinable on step i + 1, and Lemma 4 holds true up to step i, then for all j ≤ i: .det + ∩ BestD(parent(parent(node)), r(node, i + 1)) If node's parent is an AND node, node is negatively determinable on step i + 1, and Lemma 4 holds true up to step i, then for all j ≤ i: .det -∩ BestD(parent(parent(node)), r(node, i + 1)) Lemma 12. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-root node in the associated predicate tree. If node's parent is an OR node, node is positively determinable on step i + 1, and Lemma 4 holds true up to step i, then: If node's parent is an AND node, node is negatively determinable on step i + 1, and Lemma 4 holds true up to step i, then: .det -∩ BestD(parent(parent(node)), r(node, i + 1)) Lemma 13. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a node in the associated predicate tree. If node is positively determinable on step i + 1, and Lemma 4 holds true up to step i, then for all j ≤ i: If node is negatively determinable on step i + 1, and Lemma 4 holds true up to step i, then for all j ≤ i: .det -∩ BestD(parent(node), r(node, i + 1)) Lemma 14. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a node in the associated predicate tree. If node is positively determinable on step i + 1, and Lemma 4 holds true up to step i, then: If node is negatively determinable on step i + 1, and Lemma 4 holds true up to step i, then: .det -∩ BestD(parent(node), r(node, i + 1)) Lemma 15. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-leaf node in the associated predicate tree. Furthermore, Let c and c be two different children of node. If node is an OR node, Lemma 4 holds true up to step j max , and Lemma 14 holds true up to node's children, then for all steps i and j such that max(i, j) ≤ j max : If node is an AND node, Lemma 4 holds true up to step j max , and Lemma 14 holds true up to node's children, then for all steps i and j such that max(i, j) ≤ j max : 16. For any set of valuation sets D, predicate atom P , and any D ∈ D, let E be some valuation set derived from D ∪ {P (D)} without using P as an operator. There exists a valuation set E derived from D without using P as an operator, such that: Given a predicate expression's ordering of predicate atoms [P 1 , ..., P n ], let valuation set D i be the ith operand generated by BestD and Update. In addition, let A be an ancestor in P i 's lineage. For all v ∈ D i , there exists a u ∈ Γ(v, i) such that all incomplete children of A that are not ancestors of P i are statically true/false with respect to {u| i=T , u| i=F } if A is an AND/OR node respectively.
Lemma 18. Given a predicate expression's ordering of predicate atoms [P 1 , ..., P n ], let valuation set D i be the ith operand generated by BestD and Update. In addition, let A be an ancestor in P i 's lineage. For all v ∈ D i , an incomplete child of A which is not an ancestor of P i cannot be statically false/true with respect to Γ(v, i) if A is an AND/OR node respectively.
Lemma 19. Given a predicate expression's ordering of predicate atoms [P 1 , ..., P n ], let valuation set D i be the ith operand generated by BestD and Update. In addition, let node be a node in the associated predicate tree. For all v ∈ D i , if node is not positively determinable on step i, then node cannot be statically true with respect to Γ(v, i). Similarly, for all v ∈ D i , if node is not negatively determinable on step i, then node cannot be statically false with respect to Γ(v, i).
Lemma 20. Given a predicate expression's ordering of predicate atoms [P 1 , ..., P n ], let node be a node in the associated predicate tree. If node is positively determinable on step i, then state i [node].det + is the set of valuations v ∈ BestD(node, r(node, i)) such that every u ∈ Γ(v, i) evaluated against node is true: Similarly, if node is negatively determinable on step i, then state i [node].detis the set of valuations v ∈ BestD(node, r(node, i)) such that every u ∈ Γ(v, i) evaluated against node is false:

A.3 Proofs
Before we begin, a special note on Lemmas 4, 14, and 15. The co-dependent nature of BestD and Update require that these lemmas use each other in their proofs. However, both Lemmas 4 and 14 are inductive proofs, and by depending on the inductive hypotheses, we can avoid a cyclical dependency. To take an example, in the proof for Lemma 4, it is assumed the lemma holds up to step k. Then, for the (k + 1)th step, Lemma 14 is used 4 but the conditions to use Lemma 14 only requires that Lemma 4 hold up to step k. Thus, a cyclical dependency is avoided. A similar situation occurs with Lemma 15.
A. 3.1 Proof of Lemma 1 Lemma 1. Let P i refer to the ith predicate atom of the given predicate expression. There exists a valuation v such that v| i=T satisfies the overall predicate expression, but v| i=F does not. Proof. We prove the lemma by construction with the following algorithm: 1. Start with an empty n-length valuation v = ( , , ..., ).

Starting from P i 's direct parent, for each ancestor A in P i's lineage:
• For each predicate atom descendant P j of A that is not P i :

Return the pair of valuations (v| i=T , v| i=F ).
To see why v| i=T satisfies the overall predicate expression but v| i=F does not, let A refer to an ancestor node in P i 's lineage, and let A be A's child which is either also in P i 's lineage or is P i itself. Furthermore, let all predicate atoms that are descendants of A but not A be called "other" predicate atoms. If A is an AND node, setting the elements of v corresponding to "other" predicate atom descendants to true ensures that every child other than A will evaluate to true. As a result, A's overall evaluation on v is wholly dependent on whether A evaluates to true or false. In the case that A is an OR node, setting the elements of v corresponding to the "other" predicate atoms to false also ensures that every child other A will evaluate to false. As a result, A's overall evaluation on v once again is wholly dependent on whether A evaluates to true or false. The above algorithm applies this logic recursively to construct v| i=T and v| i=F , so the sole outcome of P i determines the outcome of the entire predicate expression.

A.3.2 Proof of Lemma 2
Lemma 2. Given a predicate expression's predicate atoms {P 1 , ..., P n } and some valuation v ∈ {T, F } n , let D be some set of valuation sets. If every valuation set D ∈ D contains either both or neither of v| i=T and v| i=F , then every valuation set which can be derived from D without P i as an operator must also contain either both or neither of v| i=T and v| i=F . In other words: Proof. We give a proof by case analysis. Let X be a valuation set which has either both v| i=T and v| i=F or neither v| i=T nor v| i=F . If we apply a predicate atom P j which is not P i to X, the result P j (X) will have both (v| i=T , v| i=F ) if v j = T and neither valuations if v j = F . Let Y be another valuation set which also has either both or neither of v| i=T and v| i=F . We show for every set operation between the two valuation sets, the result will also have either have both or neither valuations. Table 2 shows the results. The table elements reflect whether both or neither valuations are present in the results of set operations between X and Y . Thus, if every valuation set in D contains either both or neither of v| i=T and v| i=F , then all derived sets which do not use P i as an operator must also contain either both or neither of v| i=T and v| i=F .

Set Op
Both in X

A.3.3 Proof of Lemma 3
Lemma 3. Let [(P 1 , D 1 ), . .., (P m , D m )] be the steps of a predicate evaluation system such that the set of all valuations which satisfy the given predicate expression is present in the final extended universe U m . Let steps i and j be the first two times that predicate atom P appears in such a sequence: P i = P j = P . If D i ∩ D j = ∅, then either D j can be derived directly from U i−1 without using P as an operator, or D j cannot be derived at all from U i−1 ∪ {P (D i )} without P as an operator.
Proof. We prove Lemma 3 by showing that if D j ∩ D i = ∅, all valuation sets D j which can be derived from U i−1 ∪ {P (D i )} without using P as an operator can also be constructed from U i−1 without using P as an operator. We do this by applying the identity A = (A \ B) ∪ (A ∩ B) for any sets A and B (Appendix C): The second step comes from the precondition. Lemma 16 (shown below) states that there must exist some D j derived from U i−1 without using P as an operator such that can also be derived from U i−1 without using P as an operator.
Lemma 16. For any set of valuation sets D, predicate atom P , and any D ∈ D, let E be some valuation set derived from D ∪ {P (D)} without using P as an operator. There exists a valuation set E derived from D without using P as an operator, such that: 3.4 Proof of Lemma 4 Lemma 4. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-leaf node in the associated predicate tree. For all pairs of node's predicate atom descendants P i and P j for which i < j: BestD(parent(node), j) ⊆ BestD(parent(node), i) Proof. We prove this by performing induction over the maximum value that j can be (i.e., j max ≥ j).
The base case occurs when j max = 2. Since both P i an P j are descendants of node, there can be no positively or negatively determinable children along node's ancestors. Thus, BestD(parent(node), 1) = BestD(parent(node), 2) = {T, F } n , and the lemma is satisfied.
As the inductive hypothesis, assume the lemma holds for j max = k. For the inductive step, j max = k + 1. Let us assume that P j = P k+1 is a descendant of node. Otherwise, the lemma is trivially true based on the inductive hypothesis. Furthermore, assume that i = r(node, j). Due to the monotonicity of ⊆, if the lemma holds for i = r(node, j), then the lemma holds for all i < j.
We prove the case for j max = k + 1 by induction over the distance of node from the root node (henceforth referred to as the "inner" induction). For the base case of the inner induction, node is the root node. In this case, BestD(parent(node), i) = BestD(parent(node), j) = {T, F } n for all i and j, so the lemma is satisfied. Next, we assume as the inner inductive hypothesis that the lemma holds for when node is k distance away from the root node. For the inner inductive step, we assume node is k + 1 distance away from the root node.
If node's parent is an AND node, based on Algorithm 2, we can expand BestD(parent(node), j) as: BestD(parent(node), j) = BestD(parent(parent(node)), j) For any sets A, B, and C it is trivially true that A ⊇ A ∩ (B \ C). Thus: We show that the right-hand side of this equation is a superset of BestD(parent(node), j), completing the proof for the AND case. We start by expanding BestD(parent(node), i) according to Algorithm 2: BestD(parent(node), i) ⊇ BestD(parent(parent(node)), i) for all sets A, B, C, and D (Appendix C) to rearrange: Since j > i, the set of complete children at step j must be a superset of the complete children at step i (children • (parent(node), j) ⊇ children • (parent(node), i)). Furthermore, based on the Property 3, the cmp values of these complete children do not change, so the second line can be simplified: Next, the set of negatively determinable children at step j must be also superset of the negatively determinable children at step i. Some of these children may have graduated to also becoming complete, but the union in the third line is also over complete children. For each of these negatively determinable children, we apply Lemma 11 5 (shown below): By the inner inductive hypothesis, BestD(parent(parent(node)), i) ⊆ BestD(parent(parent(node)), r(c − , j)). BestD(parent(node), i) ⊇ BestD(parent(parent(node)), i)

Using the identity that
At this point, we can take the intersection of BestD(parent(parent(node)), j) to both sides and apply the inner inductive hypothesis which states that: BestD(parent(parent(node)), j) ⊆ BestD(parent(parent(node)), i) We end up with: BestD(parent(node), i) ∩ BestD(parent(parent(node)), j) ⊇ BestD(parent(parent(node)), j) Note that the right-hand side of this equation is equivalent to Equation 7. Thus: BestD(parent(node), i) ⊇ BestD(parent(node), j) Lemma 11. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-root node in the associated predicate tree. If node's parent is an OR node, node is positively determinable on step i + 1, and Lemma 4 holds true up to step i, then for all j ≤ i: .det + ∩ BestD(parent(parent(node)), r(node, i + 1)) If node's parent is an AND node, node is negatively determinable on step i + 1, and Lemma 4 holds true up to step i, then for all j ≤ i: .det -∩ BestD(parent(parent(node)), r(node, i + 1)) If node's parent is an OR node, based on Algorithm 2, we can expand BestD(parent(node), j) as: BestD(parent(node), j) = BestD(parent(parent(node)), j) For any sets A and B it is trivially true that A ⊇ A \ B. Thus: We once again show that the right-hand side of this equation is a superset of BestD(parent(node), j), completing the proof for the OR case. We start by expanding BestD(parent(node), i) according to Algorithm 2: BestD(parent(node), i) ⊇ BestD(parent(parent(node)), i) Since j > i, the set of complete and positively determinable children at step j must be a superset of the complete and positively determinable children at step i. Furthermore, Lemma 11 states if c is a positively determinable child of an OR node: .det + ∩ BestD(parent(parent(node)), r(c, j)) Using the inner inductive hypothesis once again, Equation 11 simplifies to: At this point, we can take the intersection of BestD(parent(parent(node)), j) to both sides and apply the inner inductive hypothesis which states that: BestD(parent(parent(node)), j) ⊆ BestD(parent(parent(node)), i) We end up with: BestD(parent(node), i) ∩ BestD(parent(parent(node)), j) ⊇ BestD(parent(parent(node)), j) Here, A is a common term on the outside, so it is sufficient to prove The first, second, and third steps use the following identities respectively (Appendix C). For any sets A, B, and C: The fourth step uses the assumptions B ⊇ F and F ∩ C = ∅. The last step uses the same identity as the first step in reverse.
A. 3.6 Proof of Lemma 6 Lemma 6. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a node in the associated predicate tree. For any step index i: Proof. We prove this by strong induction on the height of the tree referred to by node. As the base case, let node be a leaf node which refers to predicate atom P i . The variable state[node].det + is initially set to the empty set, and until P i is positively determinable, the lemma is trivially true. Once node is positively determinable, state[node].det + is updated with P i (D i ). By definition ref node = P i ({T, F } n ), and the largest D i can be is {T, F } n . As a result, the lemma holds even when node is positively determinable.
As the inductive hypothesis, assume that the lemma holds for all predicate tree nodes of height k or less. If node has a height of k + 1, node must either be an AND or OR node. Once again if node is not positively determinable, then the lemma holds trivially. Thus, we assume node is positively determinable on step i. Recall that r(node, i) is the largest index among node's predicate atom descendants that is smaller than i; in other words, r(node, i) is the last time node was updated before step i. By definition if node is an AND node and positively determinable, all of it children must also be positively determinable. A. 3.7 Proof of Lemma 7 Lemma 7. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-leaf node in the associated predicate tree. Furthermore, Let c and c be two different children of node. If node is an OR node, for all steps i and j: If node is an AND node, then for all steps i and j: Proof. This is just the non-conditional form of Lemma 15. The proof for Lemma 15 depends on Lemma 4 and Lemma 14. Since we have already shown Lemma 4 to be true for any node in the predicate tree, Lemma 14 must apply to predicate tree nodes of all height, and Lemma 15 must apply to all step indices as well, giving us this non-conditional form. Proof. We first introduce the concept of static and dynamic nodes. Definition 13. Let node be a node in the predicate tree. We say that node is statically true with respect to a valuation set D if D ⊆ ref node and statically false with respect to D if D ∩ ref node = ∅. If node is either statically true or statically false with respect to a valuation set, it is said to be static with respect to that valuation set. Otherwise, node is dynamic with respect to that valuation set.
More intuitively, if every valuation within a valuation set would evaluate to true when evaluated against node, then node is considered statically true with respect to that valuation set. Similarly, if every valuation within a valuation set would evaluate to false, then node is considered statically false with respect to that valuation set. If different valuations in a valuation set would result in different values when evaluated against node, then node is considered dynamic with respect to that valuation set.
Based on this definition, we present the following lemma about incomplete nodes. Lemma 17. Given a predicate expression's ordering of predicate atoms [P 1 , ..., P n ], let valuation set D i be the ith operand generated by BestD and Update. In addition, let A be an ancestor in P i 's lineage. For all v ∈ D i , there exists a u ∈ Γ(v, i) such that all incomplete children of A that are not ancestors of P i are statically true/false with respect to {u| i=T , u| i=F } if A is an AND/OR node respectively.
We are now ready to prove Lemma 8. Assume to the contrary that there exists a valuation v ∈ D i such that for all u ∈ Γ(v, i), the root node is static with respect to {u| i=T , u| i=F }. By definition, P i must be dynamic with respect to {u| i=T , u| i=F }. Therefore, somewhere along P i 's lineage, the nodes change from being dynamic to static with respect to {u| i=T , u| i=F }. Let A be the ancestor in P i 's lineage closest to the root such that A is dynamic with respect to {u| i=T , u| i=F } while A 's parent A is static with respect to {u| i=T , u| i=F }. We show that A cannot be static, leading to a contradiction.
If A is an AND node, based on Algorithm 2, we see that BestD(A, i) returns only valuations which satisfy every one of A's complete children on step i. Based on Property 6 (shown below), D i must be a subset of BestD(A, i), so all complete children of A must be statically true with respect to D i . Corollary 1 states that Γ(v, i) ⊆ D i and {u| i=T , u| i=F } ⊆ Γ(v, i), so all of A's complete children must also be statically true with respect to {u| i=T , u| i=F } as well. Based on Lemma 17, for all v ∈ D i , there must exist a u ∈ Γ(v, i) such that all incomplete children of A except A are statically true with respect to {u| i=T , u| i=F }. In other words, for this u, all children except A are statically true with respect to {u| i=T , u| i=F }. Since we only have positive predicate atom expressions, u| i=T must evaluate to true against A and therefore evaluates to true against A itself as well. On the other hand, u| i=F must evaluate to false against A and evaluates to false against A as well. Therefore, A is dynamic with respect to {u| i=T , u| i=F }, and a contradiction is reached.
The reasoning is basically the same if A is an OR node. Based on Algorithm 2, we see that BestD(A, i) returns only valuations which do not satisfy any one of A's complete children on step i, meaning all of A's complete children are statically false with respect to BestD(A, i). Based on Property 6, D i must be a subset of BestD(A, i), and Corollary 1 states that Γ(v, i) ⊆ D i . Since, {u| i=T , u| i=F } ⊆ Γ(v, i), all of A's complete children must also be statically false with respect to {u| i=T , u| i=F }. Based on Lemma 17, for all v ∈ D i , there must exist a u ∈ Γ(v, i) such that all incomplete children of A except A are statically false with respect to {u| i=T , u| i=F }. In other words, for this u, all children except A are statically false with respect to {u| i=T , u| i=F }. Since we only have positive predicate atom expressions, u| i=T must evaluate to true against A and also against A. On the other hand, u| i=F evaluates to false against A and must also evaluate to false against A. Therefore, A is dynamic with respect to {u| i=T , u| i=F } and a contradiction is reached.
Property 6. Let node node be a node in the predicate tree. For any step index i: This property is easy to see since BestD(node, i) only ever removes sets from BestD(parent(node), i) (by intersection or sub subtraction) and never adds any sets.
A. 3.9 Proof of Lemma 9 Lemma 9. Given a DFS ordering of predicate atoms for a predicate expression, if node node of the associated predicate tree is the child of an AND node and negatively determinable on step i, node must be complete on step i. Similarly, if node is the child of an OR node and positively determinable on step i, node must be complete on step i.

Proof.
We prove this by case analysis on the type of node. 1. If node is a leaf node, the conditions for being complete are the same as the conditions for being positively and negatively determinable, so the lemma is true.
2. If node is the child of an AND node, it must be an OR node (leaf nodes go to the first case). As an OR node, if node is negatively determinable, each child of node must also be negatively determinable by definition. A node can only be negatively determinable if at least one predicate atom descendant of it has already been applied, so all of node's children must have at least one applied predicate atom descendant each. However, we have a DFS ordering, so if node's child has one applied predicate atom descendant, all of its predicate atom descendants must be applied, marking the child as complete.
Since all of node's children are complete, node is also complete. 3. If node is the child of an OR node and positively determinable, the reasoning is the same as when node is the child of AND node and negatively determinable. As an AND node, if node is positively determinable, each child of node must also be positively determinable by definition. A node can only be positively determinable if at least one predicate atom descendant of it has already been applied, so all of node's children must have at least one applied predicate atom descendant. However, we have a DFS ordering, so if node's child has one applied predicate atom descendant, all of its predicate atom descendants must be applied, marking the child as complete. Since all of node's children are complete, node is also complete.

A.3.10 Proof of Lemma 10
Lemma 10. Given any ordering of predicate atoms for a predicate expression of depth 2 or less, if node node of the associated predicate tree is the child of an AND node and negatively determinable, then node must be complete. Similarly, if node is the child of an OR node and positively determinable, then node must be complete.
Proof. We prove this by case analysis on the type of node.
1. If node is a leaf node, the conditions for being complete are the same as the conditions for being positively and negatively determinable, so the lemma is true.
2. If node is the child of an AND node, it must be an OR node (leaf nodes go to the first case). As an OR node, if node is negatively determinable, each child of node must also be negatively determinable by definition. However, the entire predicate tree has a maximum depth of 2, so all of node's children must be leaf nodes. All leaf nodes which are negatively determinable are also complete, so node must also be complete. 3. If node is the child of an OR node and positively determinable, the reasoning is the same as when node is the child of AND node and negatively determinable. As an AND node, if node is positively determinable, each child of node must also be positively determinable by definition. However, the entire predicate tree has a maximum depth of 2, so all of node's children must be leaf nodes. All leaf nodes which are positively determinable are also complete, so node must also be complete.

A.3.11 Proof of Lemma 11
Lemma 11. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-root node in the associated predicate tree. If node's parent is an OR node, node is positively determinable on step i + 1, and Lemma 4 holds true up to step i, then for all j ≤ i: .det + ∩ BestD(parent(parent(node)), r(node, i + 1)) If node's parent is an AND node, node is negatively determinable on step i + 1, and Lemma 4 holds true up to step i, then for all j ≤ i: .det -∩ BestD(parent(parent(node)), r(node, i + 1)) Proof. We break the proof up into two parts. First, we claim that: Lemma 12. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-root node in the associated predicate tree. If node's parent is an OR node, node is positively determinable on step i + 1, and Lemma 4 holds true up to step i, then: .det + ∩ BestD(parent(parent(node)), r(node, i + 1)) If node's parent is an AND node, node is negatively determinable on step i + 1, and Lemma 4 holds true up to step i, then: .det -∩ BestD(parent(parent(node)), r(node, i + 1)) Note that the difference between Lemma 12 and Lemma 11 is that Lemma 12 only applies between consecutive steps i and i + 1. Once Lemma 12 has been shown to be true, we can show by strong induction on j that the lemma is true for all j ≤ i. Assume as the base case j = 1. This case is trivially satisfied because state 1 [node] = ∅ for any node based on initialization. Next, assume as the inductive hypothesis, the lemma holds for when j = k. For the inductive step, j = k + 1. For all r(node, i .det + ∩ BestD(parent(parent(node)), r(node, i + 1)) The inductive hypothesis states that for all j ≤ r(node, i + 1): state r(node,i+1)+1 [node].det + ⊇ state j [node].det + ∩ BestD(parent(parent(node)), r(node, r(node, i + 1))) Intersecting both sides with BestD(parent(parent(node)), r(node, i + 1)) and applying Lemma 4 yields: state r(node,i+1)+1 [node].det + ∩ BestD(parent(parent(node)), r(node, i + 1)) ⊇ state j [node].det + ∩ BestD(parent(parent(node)), r(node, i + 1)) The left-hand side of this equation is one of the cases of the right-hand side of Equation 12. Thus, for all j ≤ i: .det + ∩ BestD(parent(parent(node)), r(node, i + 1)) The exact same reasoning applies to detif node's parent is an AND node.
A. 3.12 Proof of Lemma 12 Lemma 12. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-root node in the associated predicate tree. If node's parent is an OR node, node is positively determinable on step i + 1, and Lemma 4 holds true up to step i, then: .det + ∩ BestD(parent(parent(node)), r(node, i + 1)) If node's parent is an AND node, node is negatively determinable on step i + 1, and Lemma 4 holds true up to step i, then: .det -∩ BestD(parent(parent(node)), r(node, i + 1)) Proof. Let us assume that node is positively or negatively determinable on step i if node's parent is an OR or AND node respectively. Otherwise, state i [node].det + = state i [node].det -= ∅ from initialization, and the lemma is satisfied trivially. Next, we introduce Lemma 13. Lemma 13. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a node in the associated predicate tree. If node is positively determinable on step i + 1, and Lemma 4 holds true up to step i, then for all j ≤ i: If node is negatively determinable on step i + 1, and Lemma 4 holds true up to step i, then for all j ≤ i: .det -∩ BestD(parent(node), r(node, i + 1)) Note that the relationship in Lemma 13 refers to just the parent of node, whereas Lemma 12 refers to the grandparent of node.
If node's parent is an OR node, based on Lemma 13: .det + ∩ BestD(parent(parent(node)), r(node, i + 1)) Lemma 15. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-leaf node in the associated predicate tree. Furthermore, Let c and c be two different children of node. If node is an OR node, Lemma 4 holds true up to step j max , and Lemma 14 holds true up to node's children, then for all steps i and j such that max(i, j) ≤ j max : If node is an AND node, Lemma 4 holds true up to step j max , and Lemma 14 holds true up to node's children, then for all steps i and j such that max(i, j) ≤ j max : If node's parent is an AND node, based on Lemma 13: Expanding out BestD based on Algorithm 2 gives us: .det -∩ BestD(parent(parent(node)), r(node, i + 1)) ∩   c • ∈children • (parent(node),r(node,i+1)) Lemma 15 states that the detvalues of two different node must also be mutually exclusive. Thus, all set subtraction terms can be removed once again: At this point, we establish the following relationships thanks to Algorithm 3: cmp ⊆ BestD(node, r(c • , r(node, i + 1))) If r(node, i) < r(c • , r(node, i + 1)) (meaning a predicate atom descendant of c • was applied more recently than one of node), as part of calculating BestD, the detvalues of all negatively determinable children are subtracted away. As such, node must have been one of these children: On the other hand, if r(node, i) > r(c • , r(node, i + 1)) (meaning a predicate atom descendant of node was applied more recently than one of c • ), as part of calculating BestD, an intersection with the cmp values of all complete children is performed. Since r(node, i) > r(c • , r(node, i + 1)), c • must have be one of these children: If the first case is true for any complete child node in Equation 14, then the right-hand side simplifies to the empty set, and the lemma is trivially true. If all complete children c • of belong to the second case, then state i [node].detis a subset of that intersection, and Equation 14 simplifies to: .det -∩ BestD(parent(parent(node)), r(node, i)) A. 3.13 Proof of Lemma 13 Lemma 13. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a node in the associated predicate tree. If node is positively determinable on step i + 1, and Lemma 4 holds true up to step i, then for all j ≤ i: If node is negatively determinable on step i + 1, and Lemma 4 holds true up to step i, then for all j ≤ i: Proof. Similar to the proof for Lemma 11, this proof is divided into two parts. First, we present: Lemma 14. Let [P 1 , ..., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a node in the associated predicate tree. If node is positively determinable on step i + 1, and Lemma 4 holds true up to step i, then: .det + ∩ BestD(parent(node), r(node, i + 1)) If node is negatively determinable on step i + 1, and Lemma 4 holds true up to step i, then: .det -∩ BestD(parent(node), r(node, i + 1)) Similar to before, the difference between Lemma 14 and Lemma 13 is that Lemma 14 only applies between consecutive steps i and i + 1. Once Lemma 14 has shown to be true, we can show by strong induction on j that the lemma is true for all j ≤ i. Assume as the base case j = 1. This case is trivially satisfied since state 1 [node] = ∅ for any node based on initialization. Next, assume as the inductive hypothesis, the lemma holds for when j = k. For the inductive step, j = k + 1. For all r(node, i + 1) < j ≤ i, state[node] is not updated. Hence state j [node] = state i [node] for these j, and by Lemma 14: The inductive hypothesis states that for all j ≤ r(node, i + 1): .det + ∩ BestD(parent(node), r(node, r(node, i + 1))) Intersecting both sides with BestD(parent(node), r(node, i + 1)) and applying Lemma 4 yields: state r(node,i+1)+1 [node].det + ∩ BestD(parent(node), r(node, i + 1)) ⊇ state j [node].det + ∩ BestD(parent(node), r(node, i + 1)) The left-hand side of this equation is one of the cases of the right-hand side of Equation 15. If node is negatively determinable on step i + 1, and Lemma 4 holds true up to step i, then: .det -∩ BestD(parent(node), r(node, i + 1)) Proof. We prove this by strong induction on the height of the tree referred to by node. As the base case, let node be a leaf node, which refers to P j . A leaf node's det + value is only ever updated once (at the time of its completion). If j < i, then P j has already been applied. Thus, state i+1 [node] = state j [node], and the lemma is satisfied. If j = i, then state j [node].det + = ∅ because it still holds its initialized state, and the lemma is trivially satisfied. Assume as the inductive hypothesis that the lemma holds for any node with a height of k. Next, for the inductive step, let node refer to a node with a height of k + 1. Let us also assume that P i is a descendant of node. Otherwise, node's state will not be updated and state i+1 [node] = state i [node], and the lemma is trivially true. Furthermore, we assume that node is positively and negatively determinable on step i. Otherwise, state i [node].det + = state i [node].det -= ∅ based on initialization, and the lemma is trivially satisfied once again.
If node is an AND node and positively determinable, then all of its children must be positively determinable by definition. Based on Algorithm 3: As stated in the precondition, we assume that Lemma 4 holds up to step i. Thus, BestD(parent(node), i) ⊆ BestD(parent(node), r(node, i)), and: The inductive hypothesis states that for child c * : Expanding out BestD based on Algorithm 2, we get: If we intersect both sides with X ∩ BestD(parent(node), i), the left-hand side is the same as Equation 19. Thus: det + for all complete children, so these terms can be absorbed into X. Expanding out X leaves us with: for all sets A, B, C, and D (Appendix C), we can rearrange this to: Not all children may be negatively determinable, but the detvalue of those children will be ∅ anyway based on initialization. Based on Property 4, the det + and detvalues for any node must mutually exclusive for any time step, so we can remove the set subtraction terms: If node is an OR node and positively determinable, then based on Algorithm 3: Similar to before, based on Lemma 4, Equation 22 can be intersected with BestD(parent(node), i) to get: All children of node except P i 's ancestor do not have their state values updated between steps i and i + 1. For these children state i = state i+1 . Let c * be node's child that is P i 's ancestor and let: We can rewrite Equations 21 and 23 as: The inductive hypothesis states that for child c * : Expanding out BestD based on Algorithm 2, we get: We can take the union with respect to BestD(parent(node), i) ∩ X on both sides. This results in the left-hand side being equivalent to Equation 24, and the right-hand side being equivalent to Equation 25.
If node is an AND node and negatively determinable, then based on Algorithm 3: Once again, based on Lemma 4, Equation 27 can be intersected with BestD(parent(node), i) to get: All children of node except P i 's ancestor do not have their state values updated between steps i and i + 1. For these children state i = state i+1 . Let c * be node's child that is P i 's ancestor and let: We can rewrite Equations 26 and 28 as: The inductive hypothesis states that for child c * : Expanding out BestD based on Algorithm 2, we get: Lemma 15 tells us that the detvalues of two different children are mutually exclusive, so we can remove the set subtraction terms: At this point, we establish the following relationships thanks to Algorithm 3: For c * and any complete child c • of node on step i: If r(c * , i) < r(c • , i) (meaning a predicate atom descendant of c • was applied more recently than one of c * ), as part of calculating BestD, the detvalues of all negatively determinable children are subtracted away.
Since r(c * , i) < r(c • , i), c * must be one of these children: If the first case is true for any complete child c • in Equation 31, then the right-hand side simplifies to the empty set, and the lemma is trivially true. If all complete children c • of belong to the second case, then state i [child].detmust be a subset of the intersection, and Equation 31 simplifies to: We can take the union with respect to BestD(parent(node), i) ∩ X on both sides. This results in the left-hand side being equivalent to Equation 29, and the right-hand side being equivalent to Equation 30 Since we assumed that Lemma 4 holds up to step i, BestD(parent(node), i) ⊆ BestD(parent(node), r(node, i)), and: (34) All children of node except P i 's ancestor do not have their state values updated between steps i and i + 1. For these children state i = state i+1 . Let c * be node's child that is P i 's ancestor and let: We can rewrite Equations 32 and 34 as: The inductive hypothesis states that for child c * : Expanding out BestD based on Algorithm 2, we get: for all sets A, B, C, and D (Appendix C) and expanding X, we can rearrange this to: Not all children may be positively determinable, but the det + value of those children will be ∅ anyway based on initialization. Based on Property 4, the detand det + values for any node must mutually exclusive for any time step, so we can remove the set subtraction terms:  .., P n ] be any ordering of predicate atoms for the given predicate expression, and let node be a non-leaf node in the associated predicate tree. Furthermore, Let c and c be two different children of node. If node is an OR node, Lemma 4 holds true up to step j max , and Lemma 14 holds true up to node's children, then for all steps i and j such that max(i, j) ≤ j max : If node is an AND node, Lemma 4 holds true up to step j max , and Lemma 14 holds true up to node's children, then for all steps i and j such that max(i, j) ≤ j max : We prove this by induction over the value of j max . Let us first assume node is an OR node. As the base case, i = j = 1. .det + remains unchanged between steps k and k + 1, so the inductive hypothesis can be directly applied. 4. E = F \ G: The following identities are used (Appendix C). For any sets A, B, and C: The third and sixth steps are the applications of the inductive hypothesis. Let ancestor A be an AND node. We prove by construction that for all v ∈ D i , there exists a u ∈ Γ(v, i) that evaluates to true against all incomplete children of A. Using the same notation as monotone Boolean functions, the construction of valuation u is as follows: 2. For all j in (i ≤ j ≤ n), set u j = 1.
Lemma 18 (shown below) states that an incomplete child of A that is not an ancestor of P i cannot be statically false with respect to Γ(v, i). Thus, for each incomplete child of A, there must exist at least one u ∈ Γ(v, i) that evaluates to true against that child. In other words, if we let node be the incomplete child of A, then there exists a u ∈ Γ(v, i) such that node[u ] = 1. When compared with the above constructed u, u ≤ u because u ∈ Γ(v, i). Thus, based on the property of monotone Boolean functions, if node[u ] = 1, then node[u] = 1. This reasoning holds for all incomplete children of A, so u must evaluate to true against all incomplete children of A. Lemma 18. Given a predicate expression's ordering of predicate atoms [P 1 , ..., P n ], let valuation set D i be the ith operand generated by BestD and Update. In addition, let A be an ancestor in P i 's lineage. For all v ∈ D i , an incomplete child of A which is not an ancestor of P i cannot be statically false/true with respect to Γ(v, i) if A is an AND/OR node respectively.
Similarly, if A is an OR node, we can construct a u ∈ Γ(v, i) that evaluates to false against all incomplete children of A with: 2. For all j in (i ≤ j ≤ n), set u j = 0.
Since, D i ⊆ BestD(parent(node), i), and BestD(parent(node), i) ⊆ BestD(parent(node), r(node, i)) based on Lemma 4: In other words, node is not statically true with respect to Γ(v, i), for any v ∈ D i . A. 3.19 Proof of Lemma 19 Lemma 19. Given a predicate expression's ordering of predicate atoms [P 1 , ..., P n ], let valuation set D i be the ith operand generated by BestD and Update. In addition, let node be a node in the associated predicate tree. For all v ∈ D i , if node is not positively determinable on step i, then node cannot be statically true with respect to Γ(v, i). Similarly, for all v ∈ D i , if node is not negatively determinable on step i, then node cannot be statically false with respect to Γ(v, i).
Proof. We prove this by strong induction on the height of the tree referred to by node. As the base case, let node be a leaf node which refers to predicate atom P j . If j ≥ i, then node cannot be statically true or false with respect to Γ(v, i) for any v. If j < i, then node must be complete by step i, so it must also be positively and negatively determinable by step i. Thus, the base case is trivially resolved.
As the inductive hypothesis, assume that the lemma holds for any predicate tree nodes of height k or less. Next, as the inductive step, let node have a height of k + 1. We prove the contrapositive of the lemma for node: For all v ∈ D i , if node is statically true with respect to Γ(v, i), then node is positively determinable on step i. If node is statically false with respect to Γ(v, i), then node is negatively determinable on step i.
If node is an AND node and statically true with respect to Γ(v, i), then each u ∈ Γ(v, i) must resolve to true against every child of node. Thus, all of node's children must be statically true with respect to Γ(v, i), and by the inductive hypothesis, positively determinable on step i. Therefore, by definition, node itself must also be positively determinable.
In the case that node is an AND node and statically false with respect to Γ(v, i), we claim that there exists a child of node which is statically false with respect to Γ(v, i). By the inductive hypothesis, if a child of node is statically false, it must be negatively determinable. By definition, if one of node's child is negatively determinable, node must be negatively determinable, completing the proof for this case. Assume to the contrary that all children of node are not statically false with respect to Γ(v, i). There are two cases for each child of node: (1) The child is statically true with respect to Γ(v, i). (2) The child is dynamic with respect to Γ(v, i). The first case is valid, but not all children can fall into this category because that would imply that node is statically true with respect to Γ(v, i), leading to a contradiction. Therefore, there must be at at least one child that is dynamic with respect to Γ(v, i). Now consider once again that our predicate expression is a monotone Boolean function [24]. Using the same notation as before, consider the valuation u which is constructed according to: respect to Γ(v, i). Now consider once again that our predicate expression is a monotone Boolean function. Using the same notation as before, consider the valuation u which is constructed according to: 1. For all j in (1 ≤ j ≤ i − 1), set u j = v j .
2. For all j in (i ≤ j ≤ n), set u j = 0.
Since node is statically true with respect to Γ(v, i), there must exist a child node child of node such that child[u] = 1. However, for all u ∈ Γ(v, i), u ≤ u , so based on the property of monotone Boolean functions, child[u ] = 1. However, this would mean that child is statically true with respect to Γ(v, i), leading to another contradiction.
If node is an OR node and statically false with respect to Γ(v, i), then each u ∈ Γ(v, i) must resolve to false against every child of node. Thus, all of node's children must be statically false with respect to Γ(v, i), and by the inductive hypothesis, negatively determinable on step i. Therefore, by definition, node itself must also be negatively determinable.
A. 3.20 Proof of Lemma 20 Lemma 20. Given a predicate expression's ordering of predicate atoms [P 1 , ..., P n ], let node be a node in the associated predicate tree. If node is positively determinable on step i, then state i [node].det + is the set of valuations v ∈ BestD(node, r(node, i)) such that every u ∈ Γ(v, i) evaluated against node is true: state i [node].det + = {v ∈ BestD(parent(node), r(node, i)) | ∀u ∈ Γ(v, i), node[u] = T } Similarly, if node is negatively determinable on step i, then state i [node].detis the set of valuations v ∈ BestD(node, r(node, i)) such that every u ∈ Γ(v, i) evaluated against node is false: .det -= {v ∈ BestD(parent(node), r(node, i)) | ∀u ∈ Γ(v, i), node[u] = F } Proof. We prove this by strong induction on the height of the tree referred to by node. As the base case, let node be a leaf node which refers to predicate atom P j . If node is positively determinable on step i, it must be that j < i and j = r(node, i). When det + and detwere updated at the end of step j, they were updated with: state i [node].det + = P j (BestD(parent(node), j)) state i [node].det -= BestD(parent(node), j) \ P j (BestD(parent(node), j)) These expressions expand to: As the inductive hypothesis, assume that the lemma holds for all predicate tree nodes of height k or less. For the inductive step, let node be a predicate tree node of height k + 1.
If node is an AND node and positively determinable on step i, all of its children must be positively determinable. Based on Algorithm 3: {v ∈ BestD(parent(node), r(node, i)) | ∀u ∈ Γ(v, i), c[u] = T } The expression {v ∈ BestD(parent(node), j) | ∀u ∈ Γ(v, i), c[u] = T } returns only valuations v for which child c is statically true with respect to Γ(v, i). The intersection of these valuations is the valuations v for which every child of node is statically true with respect to Γ(v, i). For an AND node, having every child be statically true with respect to a valuation set is the requirement to be statically true to the valuation set.
Thus: state i [node].det + = {v ∈ BestD(parent(node), r(node, i)) | ∀u ∈ Γ(v, i), node[u] = T } If node is an AND node and negatively determinable on step i, we prove this case by induction on step index i (henceforth referred to as the "inner" induction). For node to be negatively determinable, one of its children must be negatively determinable. Let c − be the first negatively determinable child of node, and let c − be first negatively determinable on step j + 1. The base case for the inner induction is i = j + 1. Based on Algorithm 3: None of node's children are negatively determinable nor complete on step j, so based on Algorithm 2, BestD(node, j) = BestD(parent(node), j), and the above equation reduces to: Since node is an AND node, if one of node's children is statically false with respect to Γ(v, i), then node itself must also be statically false with respect to Γ(v, i): state i [node].det -= {v ∈ BestD(parent(node), j) | ∀u ∈ Γ(v, i), node[u] = F } Thus, the base case is resolved.
Next, as the inner inductive hypothesis, assume that the lemma holds for any step i = k. For the inductive step, let us observe step i = k+1. If P k is not a descendant of node, state i = state k , and the inner inductive hypothesis applies. Thus, let us assume P k is a descendant of node and updates state[node].det -. Based on Algorithm 3: There is only one step difference between k and k + 1, so at most one of node's children can be updated with respect to P k . Let c * be this ancestor of P k . For all other negatively determinable children c − = c * , state k+1 [c − ] = state k [c − ]. Lemma 4 states that BestD(parent(node), k) ⊆ BestD(parent(node), r(node, k)), and Lemma 11 states that state k+1 [c * ].det -⊇ state k [c * ].det -∩ BestD(parent(node), k). Thus, we can write state k+1 [node].detin terms of state k [node].det -: The outer inductive hypothesis states that: If node is an OR node and positively determinable on step i, the reasoning is similar as when node is an AND node and negatively determinable on step i. We prove this case by induction on step index i (henceforth referred to as the "inner" induction). Let c + be the first positively determinable child of node, and let c + be first positively determinable on step j + 1. The reasoning for the base case of the inner induction is the exact same as the reasoning for the negatively determinable AND node's base case. The only difference is that each positively determinable child is statically true with respect to Γ(v, i) instead of statically false.
Next, as the inner inductive hypothesis, assume that the lemma holds for any step i = k. For the inductive step, let us observe step i = k+1. If P k is not a descendant of node, state i = state k , and the inner inductive hypothesis applies. Thus, let us assume P k is a descendant of node and updates state[node].det + . Based on Algorithm 3: There is only one step difference between k and k + 1, so at most one of node's children can be updated with respect to P k . Let c * be this ancestor of P k . For all other positively determinable children c + = c * , state k+1 [c + ] = state k [c + ]. Lemma 4 states that BestD(parent(node), k) ⊆ BestD(parent(node), r(node, k)), and Lemma 11 states that state k+1 [c * ].det + ⊇ state k [c * ].det + ∩ BestD(parent(node), k). Therefore, we can write state k+1 [node].det + in terms of state k [node].det + : For the reader's convenience, we provide a modern, updated version of Hanani in Algorithm 10 (next page). As mentioned, this returns the optimal ordering of predicate atoms for any Boolean predicate expression of depth 2 or less. The majority of the work is done by OrderNode, which returns the best ordering of all descendent predicate atoms for a given node. If node is a leaf node, node.P is used to refer to the predicate atom that node points to. γ P is the selectivity of P (i.e., the fraction of records which satisfy P ), and F P is the constant cost factor discussed in Cost Model 1. Since a leaf node only has one descendent predicate atom, it is the only predicate atom in the returned sequence. If node is an AND/OR node, OrderNode is called on each of its children, and the returned suborderings are sorted in increasing/decreasing selectivity respectively. Once suborderings has been sorted, OrderNodeHelper calculates the total selectivity and cost for node (using the independence assumption), flattens suborderings, and returns the combination of these values to the parent.

29:
P all ← P all + P return cost/γ