Query Optimization: Past to Present Immanuel Haffner, Prof. Jens Dittrich

Query Optimization: Past to Present

Block Seminar

 

Overview

In the Database Systems core lecture we taught you about query optimization. In particular, you learned to compute optimal join orders under some cost model using dynamic programming.  In this seminar, we will take a much closer look at query optimization. We will learn that there are different optimization goals, and hence cost models, and that for some cost models the optimization problem is NP-hard. We will learn about an algebraic cost model C_out that is a generalization of cost models for which the optimization problem is actually NP-hard. We will discuss different algorithms to compute join orders, including various bottom-up and top-down dynamic programming algorithms. We will also be looking at specialized algorithms that take the topology of the query graph into account to compute optimal join orders for particular kinds of queries in polynomial time. Sometimes, computing an optimal solution is not possible within a given time budget or simply not required.  Therefore, we will also discuss algorithms for computing suboptimal join orders.  Finally, we take a look at a recent work that tackles join order optimization as a graph search problem.

Preliminaries

To succeed in this seminar, you must have passed our core lecture Database Systems. The knowledge that you acquired in this lecture enables you to comprehend and professionally present your assigned paper(s).

Schedule

• Every student is assigned one to two papers to present at the end of the term¹. The presentation is expected to take 20 minutes to present the contents of the paper plus around 10 minutes of an in-depth discussion of the algorithm presented in the paper². The presentation makes 80% of your final seminar grade.
• We form "peer groups" of 2-3 students.
• Every student must write a summary of each of their peer's papers. Summaries must be 1-2 pages, DIN A4, 11pt; not less, not more. These summaries must be submitted during the lecture period. Summaries are graded and make 20% of your final seminar grade. Writing the summaries is mandatory to pass the seminar. The summaries are made accessible to all other students of the seminar and aid your peers in preparing their presentation.
• Students must submit a draft of their slides 4 weeks prior to their presentation. The final version of the slides must be submitted 2 weeks before the presentation.
• We will have three mandatory meetings during the lecture period:

1. the kick-off meeting, where we provide an overview of the papers,
2. a meeting to get to know your peers and by which you must have read the paper assigned to you,
3. a meeting after you have submitted your peer reviews, where you can interact with your peers to resolve open questions.

¹ We only assign two papers to a student where the papers are closely related and overlapping in content. When you achieved an understanding of either paper, you understand the other as well. Two papers does not mean twice as much work! You will still give a single presentation of 20 minutes.

² Most papers discussed in this seminar propose a new algorithm for join ordering. Almost all of them have been implemented in mutable.  You are expected to give an in-depth discussion of the algorithm along the implementation in mutable. For the few papers that do not propose an algorithm we expect an in-depth discussion of the theory presented in the paper, e.g. complexity analysis. 

 

Papers

Below follows the list of papers that we will discuss in this seminar. The list is ordered by publication date. This is not necessarily the order in which you will present the papers.

• Selinger et al. - Access Path Selection in a Relational Database Management System (1979)
• Ibaraki, Kameda - On the Optimal Nesting Order for Computing N-Relational Joins (1984) / Krishnamurthy, Boral, Zaniolo - Optimization of Nonrecursive Queries (1986)
• Ono, Lohman - Measuring the Complexity of Join Enumeration in Query Optimization (1990)
• Cluet, Moerkotte - On the Complexity of Generating Optimal Left-Deep Processing Trees with Cross Products (1995)
• Vance, Maier - Rapid Bushy Join-order Optimization with Cartesian Products (1996)
• Steinbrunn, Moerkotte, Kemper - Heuristic and Randomized Optimization for the Join Ordering Problem (1997)
• Moerkotte, Neumann - Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products (2006)
• DeHaan, Tompa - Optimal Top-Down Join Enumeration (2007)
• Neumann - Query Simplification: Graceful Degradation for Join-Order Optimization (2009)
• Fender, Moerkotte - A New, Highly Efficient, and Easy to Implement Top-Down Join Enumeration Algorithm (2011)
• Neumann, Radke - Adaptive Optimization of Very Large Join Queries (2018)
• Haffner, Dittrich - Efficiently Computing Join Orders with Heuristic Search (2023)

Optional Papers

• Chaudhuri et al. - Optimizing Queries with Materialized Views (1995)
• Fender, Moerkotte - Reassessing Top-Down Join Enumeration (2011)

All papers are available in our "Semesterapparat", that is provided by the Math & Informatics library. The papers can be accessed from within the University Intranet.