Review - On the Optimal Nesting Order for Computing N-Relational Joins.

Wolfgang Scheufele: Review - On the Optimal Nesting Order for Computing N-Relational Joins. ACM SIGMOD Digital Review 2: (2000) BibTeX

Review

Join ordering is a fundamental problem in query optimization. Ibaraki and Kameda were the first who analyzed the join ordering problem in depth. They determined the complexity class of the general join ordering problem and developed a dedicated polynomial-time optimization algorithm for a restricted but non-trivial class of join ordering problems. This was a major result, since by then dynamic programming was the only efficient method known to solve join ordering problems. It was not known, whether certain restricted classes can be solved more efficiently--or even in polynomial time. More exactly, Ibaraki and Kameda proved that the join ordering problem is NP-complete for general graphs and a special block-wise nested loop join cost function. Later on Cluet and Moerkotte [2] showed that this result still holds for a very simple cost function. Ibaraki and Kameda were also the first who demonstrated a connection between certain join ordering problems and certain sequencing problems. By applying a special job sequencing algorithm they obtain a polynomial time algorithm for the join ordering problem for left-deep trees without cross products, cost functions with ASI property, and acyclic join graphs. Their algorithm was subsequently improved by Krishnamurthy, Boral, and Zaniolo [3] who also discussed a heuristic extension of the algorithm to cyclic join graphs. This paper is a must-read for everyone working on query optimization.

References

[1]: Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984) BibTeX
[2]: Sophie Cluet, Guido Moerkotte: On the Complexity of Generating Optimal Left-Deep Processing Trees with Cross Products. ICDT 1995: 54-67 BibTeX
[3]: Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 BibTeX

BibTeX

Digital Review - DBLP: [Home | Search: Author, Title | Conferences | Journals]