Technical Perspective: DPconv: Super-Polynomially Faster Join Ordering

On the floors of database conferences, one can often listen to database researchers talking about the join ordering problem. However, the join ordering problem does not exist! In fact, depending on the properties of the query graph, the cardinality estimation method, the cost function, and the resulting output join tree, there exist multiple join ordering problems. For example, if the query graph is connected and acyclic, the cardinality estimator uses the independence assumption, the cost function has the ASI property, and the resulting join tree is a left-deep tree without cross products, then the problem can be solved in polynomial time 3. The join ordering problem discussed in the paper is specified by no restriction on the query graph (it can even have no edges), no restriction on the cardinality estimation method, and for the resulting join trees can be bushy with cross products. The framework DPconv transforms the join ordering problem to some kind of subset space, solves the problem therein, and transforms the solution back; this is similar in spirit to discrete FFT. Thereby, DPconv exhibits a reduced complexity compared to traditional ones working on the same join ordering problem (such as DPsub): It is the first approach to beat the O(3n) complexity barrier.