Optimizing Query Predicates with Disjunctions for Column Stores https://arxiv.org/pdf/2002.00540.pdf [abstract at the end of my message]
I just googled [predicate pushdown cnf] and it's WILD to me that this paper came up in the first page of search results, and was published last year. It mentions Spark briefly as an example of a system that "does not seem to implement any additional optimizations [for disjunctions]" Before posting this I googled [spark "2002.00540"] and it didn't appear anyone in the Spark community was talking about it; forgive me if I've missed something as I've only recently joined the list! -0xe1a *Abstract* Since its inception, database research has given limited attention to optimizing predicates with disjunctions. For conjunctions, 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.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.
