Interleaved Query Evaluation and Pipelining

The ability to treat disjunctive and conjunctive constraints uniformly as collection monoids is a very important feature of CCUBE: it allows to express and implement many constraint operations through nested iterative queries, i.e. in the same language as hosting queries. For example, the satisfiability test of a disjunction of conjunctions of linear inequalities is expressed as a monoid comprehension query that iterates over the disjuncts (each being a conjunction), and tests the satisfiability of every conjunction (using the simplex algorithm).

In turn, the ability to express a constraint operation as a sub-query in the hosting query is crucial for what we call deeply interleaved optimization: it gives the flexibility to re-shuffle and interleave parts of the constraint algorithm (sub-query) with the hosting query. This re-shuffling can be done by additional global query transformations involving approximations, indexing, re-grouping, pushing cheaper selections earlier, replacing sub-queries with special-purpose algorithms, and so forth. In contrast, if constraint operations were implemented in CCUBE simply as external functions plugged into a query, the above transformations that involve parts of constraint algorithm would not be possible, which would severely restrict optimization opportunities.

presentation created by Victor E. Segal