Reproduce “DPconv: Super-Polynomially Faster Join Ordering” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Mihail Stoian, Andreas Kipf
Researchers from UTN, Nuremberg, developed DPconv, a framework that reformulates the dynamic programming for join ordering as a subset convolution problem, thereby breaking the long-standing O(3^n) time complexity barrier for exact optimization. This approach yields super-polynomial speedups, for instance, optimizing 24-relation clique queries for C_max 29 times faster than previous O(3^n) methods, and enables efficient co-optimization of query runtime and memory footprint.
Key insights
- The core dynamic programming recursion for join ordering is structurally equivalent to a subset convolution, a computationally intensive operation that can be accelerated using Fast Subset Convolution (FSC) techniques.
- For cost functions involving min/max operations, like C_max, a binary search over possible cost values combined with a feasibility check using FSC in a binary ring can yield significantly faster exact solutions than embedding methods.
- By breaking the O(3^n) barrier, advanced algorithmic theory can provide super-polynomial speedups for fundamental database optimization problems, extending the practical reach of exact algorithms.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.