DPconv: Super-Polynomially Faster Join Ordering
<|reference_start|>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 $O(3^n)$. 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 super-polynomial speedup over DPccp, breaking the $O(3^n)$ time-barrier for the first time. We show that the instantiation of our framework for the $C_\max$ cost function is up to 30x faster than DPccp for large clique queries.<|reference_end|>
@article{stoian2024dpconv:,
    title={DPconv: Super-Polynomially Faster Join Ordering},
    author={Mihail Stoian, Andreas Kipf},
    journal={arXiv preprint arXiv:2409.08013},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.08013},
    primaryClass={cs.DB}
}