|
Technical perspective : DPconv: super-polynomially faster join ordering
Moerkotte, Guido
|
DOI:
|
https://doi.org/10.1145/3810900.3810901
|
|
URL:
|
https://dl.acm.org/doi/abs/10.1145/3810900.3810901
|
|
Additional URL:
|
https://sigmodrecord.org/2026/04/01/technical-pers...
|
|
Document Type:
|
Article
|
|
Year of publication:
|
2026
|
|
The title of a journal, publication series:
|
SIGMOD Record
|
|
Volume:
|
55
|
|
Issue number:
|
1
|
|
Page range:
|
7
|
|
Place of publication:
|
New York, NY
|
|
Publishing house:
|
ACM
|
|
ISSN:
|
0163-5808 , 1943-5835
|
|
Publication language:
|
English
|
|
Institution:
|
School of Business Informatics and Mathematics > Practical Computer Science III (Moerkotte 1996-)
|
|
Subject:
|
004 Computer science, internet
|
|
Abstract:
|
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.
|
 | Dieser Eintrag ist Teil der Universitätsbibliographie. |
 Search Authors in
You have found an error? Please let us know about your desired correction here: E-Mail
Actions (login required)
 |
Show item |
|
|
