Query Optimization

Query optimization is a function of many relational database management systems. The query optimizer attempts to determine the most efficient way to execute a given query by considering the possible query plans.

A query is a request for information from a database. It can be as simple as “finding the address of a person with SS# 123-45-6789,” or more complex like “finding the average salary of all the employed married men in California between the ages 30 to 39, that earn less than their wives.”
Queries results are generated by accessing relevant database data and manipulating it in a way that yields the requested information. Since database structures are complex, in most cases, and especially for not-very-simple queries, the needed data for a query can be collected from a database by accessing it in different ways, through different data-structures, and in different orders. Each different way typically requires different processing time. Processing times of the same query may have large variance, from a fraction of a second to hours, depending on the way selected.
The purpose of query optimization, which is an automated process, is to find the way to process a given query in minimum time. The large possible variance in time justifies performing query optimization, though finding the exact optimal way to execute a query, among all possibilities, is typically very complex, time consuming by itself, may be too costly, and often practically impossible. Thus query optimization typically tries to approximate the optimum by comparing several common-sense alternatives to provide in a reasonable time a “good enough” plan which typically does not deviate much from the best possible result.

In this lecture we discuss join ordering, usage of index structures, subquery unnesting, and basic formulas for cost estimation.

Knowledge in Database Systems and Algorithms.

• Lecture Notes
  (If “view PDF document” does not work, click “download” instead.)
• Slides
• Extra Slides on Plan Generators

 NOTE:
– If you're interested in C++ programming, I highly recommend attending the first exercise sessions in DBSII.
– If you are interested in Go programming, this 1h video and this tutorial might be a good entry point.
– Summary pdf from FSS 2021: here
– For a good discussion on IKKBZ, see https://db.in.tum.de/teaching/ws1819/queryopt/exercises/session5.pdf (starting at pdf-page 14). See here for another example run pdf.

• Runtime System
• JavaDoc for the runtime system
• TPC-D data set