Access Path Selection in a Relational Database Management System
Price every way of answering a query in one made-up unit, from five numbers about the data, and keep only the cheapest plan for each set of tables and each useful order.
Read the original ↗Every database that picks a plan for you descends from these twelve pages. Read them for the arithmetic, which is still how a planner thinks, and for the honesty: the authors print their guesses as guesses, and the guesses are still in your database.
Included with a plan
This discussion is included with a plan. The first three lessons of every track are free, with their boards and videos. A plan unlocks every lesson, board, video, lab and paper for one price.
Related on chalk
The same idea as a board, lab, video or lesson.
- BoardThe Query Plannerthe tip sheet, the bet and the three scans: this paper's cost model as Postgres runs it today
- BoardB-Tree on Diskthe B-tree index whose chained leaves give the paper its index scan and its interesting orders
- BoardThe Query Layera pull-model query layer built by hand, with no optimizer: the job this paper automates
- BoardData Models and Query Languagesthe declarative-query bargain that makes an optimizer necessary in the first place
- LabThe selectivity crossoverthree plans priced in cost units and the fraction of the table where the winner flips, which is this paper's arithmetic with a dial on it
- LessonThe Query PlannerUses the board The Query Planner
- LessonThe sentence that says whatUses the board The Query Planner
- LessonThe plan, runningUses the board The Query Planner
- LessonBuild sort and aggregate with a memory limitUses the board The Query Planner
- LessonB-Tree on DiskUses the board B-Tree on Disk
- LessonWhich shortcut to buildUses the board B-Tree on Disk
- LessonBuild three ways to joinUses the board B-Tree on Disk
- LessonDatabase 07: The Query LayerUses the board The Query Layer
- LessonData Models and Query LanguagesUses the board Data Models and Query Languages
Further reading
Read the original for the full argument and its evidence.
- The paper (PDF) ↗SIGMOD 1979, pages 23-34. Section 4 and Table 1 are the cost model and the guesses; section 5 is the join-order search. Twelve pages, two columns, readable in an evening.
- PostgreSQL: How the Planner Uses Statistics ↗Later work: the same selectivity arithmetic with most-common-value lists and histograms added, worked through on real numbers.
- PostgreSQL: CREATE STATISTICS ↗Later work: the declared escape from the independence line under Table 1's AND rule.
- PostgreSQL: Genetic Query Optimizer ↗Later work: what a production planner does once the paper's subset search gets too expensive to run.
- How Good Are Query Optimizers, Really? (Leis et al., PVLDB 9, 2015) ↗Later work: the Join Order Benchmark puts this paper's three parts to the test and finds the estimates, not the search or the cost formula, are where plans go wrong.