DPconv: Super-Polynomially Faster Join Ordering

We revisit the join ordering problem in query optimization. The standard exact algorithm, DPccp, has a worst-case running time of 𝑂 (3 𝑛 ). This is prohibitively expensive for large queries, which are not that uncommon anymore. We develop a new algorithmic framework based on subset convolution. DPconv achieves a superpolynomial speedup over DPccp, breaking the 𝑂 (3 𝑛 ) time-barrier for the first time. We show that the instantiation of our framework for the 𝐶 max cost function is up to 30x faster than DPccp for large clique queries. CCS CONCEPTS • Information systems → Query optimization.