Document detail
ID
oai:arXiv.org:2409.08013
Topic
Computer Science - DatabasesAuthor
Stoian, Mihail Kipf, AndreasCategory
Computer Science
Year
2024
listing date
9/18/2024
Abstract
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.
;Comment: To appear at SIGMOD 2025
Stoian, Mihail,Kipf, Andreas, 2024, DPconv: Super-Polynomially Faster Join Ordering
Shared genetic aetiology of Alzheimer’s disease and age-related macular degeneration by APOC1 and APOE genes
gene diagnostic based analysis amd ad apoe apoc1 identified genes pleiotropy
