Query Optimization & Join Methods

01 · Motivation

What the optimizer actually does

You wrote what you want. The optimizer decides how — and the same query can be executed in many ways whose costs differ by factors of thousands.

The query optimizer receives a query written in SQL and produces a program in an internal format that uses the data access methods. It runs in five phases:

1. Lexical, syntactic and semantic analysis — is the query well formed, and do its tables and columns exist?
2. Translation into an internal representation — something close to an algebraic tree.
3. Algebraic optimization — rewriting the tree into an equivalent, cheaper one.
4. Cost-based optimization — choosing access methods, join order and join algorithms using statistics.
5. Code generation.

Phase 3 is the classical part and one example carries it. Given

SELECT LastName, FirstName
FROM Student, Exam
WHERE Student.ID = Exam.SID AND Exam.CourseID = 'DB2'

the naive tree computes the Cartesian product of Student and Exam, then filters. With 18 000 students each enrolled in about 10 exams, and only 200 taking DB2:

naive:      Student × Exam            = 18 000 × 180 000 = 3 240 000 000 rows
            then filter to               200
pushed:     filter Exam to CourseID='DB2'  →  200 rows
            then × Student            = 18 000 × 200     = 3 600 000 rows

Pushing the selection below the product shrinks the intermediate result by three orders of magnitude. The heuristic generalises to apply first the operations that reduce the size of intermediate results — and it is a heuristic, not a guarantee of optimality.

02 · Statistics

Profiles and selectivity

Every cost estimate in this course begins by turning the given statistics into derived ones. Getting this line right is most of the exercise.

The data dictionary stores a relation profile for each table:

• the cardinality — number of tuples $T$;
• the size in bytes of each attribute $A_j$;
• the number of distinct values of each attribute, written $\mathrm{val}(A_j)$;
• the minimum and maximum value of each attribute.

These are recomputed periodically by an explicit command (update statistics and friends), not maintained continuously. They enable two things: some queries can be answered from the dictionary alone (select count(*) from T, or a comparison against the recorded min/max), and — the important one — the optimizer can estimate the size of intermediate results.

The selectivity of a predicate is the probability that a row satisfies it. Under the uniform distribution assumption — which the course applies whenever no distribution data is given — an equality predicate on an attribute with $N$ distinct values has

so the number of tuples surviving it is $T / \mathrm{val}(A)$.

The derived quantities you will need, from a typical exercise:

Given:  Hotel   500 K tuples, 12 K blocks, val(Country)=100, val(Stars)=5
        Booking  20 M tuples, 200 K blocks, val(RoomType)=10, val(Channel)=4
                 3% of bookings are in July 2025

Derive: hotels in Italy with 4 stars   = 500 K / (100 × 5)  = 1 000
        bookings matching all three    = 20 M × 3% / (10×4) = 15 000
        bookings per hotel             = 20 M / 500 K       = 40

Three lines, and the rest of the exercise is arithmetic on them.

03 · Joins

The four join methods

Joins are the most frequent and most expensive operation a DBMS performs, so they get four distinct algorithms with sharply different cost profiles.

Throughout, $b_{ext}$ and $b_{int}$ are the block counts of the external (outer) and internal (inner) tables, $t_{ext}$ the tuple count of the external one.

Two refinements to the nested loop matter in exercises. If one table is small enough to fit in the buffer, cache it and the cost collapses to $b_{ext} + b_{int}$ — the lectures’ example joins 1.7 K blocks of STUDENT with a 10-block CITIES table for ≈ 1.7 K I/O rather than 17 000. And note the asymmetry in scan & lookup: the multiplier is $t_{ext}$, the number of tuples, not $b_{ext}$, the number of blocks. That single distinction is worth a factor of the block factor — often 100×.

04 · Joins

Picking the driving side

When both tables carry filters, the plan has a choice: which table to scan first and filter, and which to probe. The wrong choice can cost thirty times more.

The lectures set it up with STUDENT ⋈ EXAM filtered by City='Milan' AND Grade='30', given $\mathrm{val}(City) = 150$ and $\mathrm{val}(Grade) = 17$:

Option 1 — scan STUDENT, filter Milan, look up EXAM
  read 1.7 K blocks; 150 K / 150 = 1 000 Milan students survive
  for each, scan EXAM's 5.3 K blocks
  C = 1.7 K + 1 000 × 5.3 K  ≈  5.3 M I/O

Option 2 — scan EXAM, filter Grade=30, look up STUDENT
  read 5.3 K blocks; 1.8 M / 17 = 106 K exams survive
  for each, scan STUDENT's 1.7 K blocks
  C = 5.3 K + 106 K × 1.7 K  ≈  180 M I/O

Same query, same data, a factor of 34 between them — decided entirely by which filter is more selective. The rule: drive from the side whose predicate leaves fewer rows, because that count is the multiplier.

Now add a secondary hash index on EXAM(SID) and option 1 improves dramatically. Each of the 1 000 Milan students costs one hash access plus the 1.8 M / 150 K = 12 exams to fetch:

C = 1.7 K + 1 000 × (1 + 12) = 14.7 K I/O

and if the query only needs to know that a match exists rather than reading the exam rows, the 12 disappears and it falls to 2.7 K.

The September 2025 paper adds a twist worth knowing, because it is the only place in the bank where a join can be removed rather than reordered:

05 · Operators

External merge sort

Sorting data too large for memory — needed for ORDER BY, for GROUP BY, and to make merge-scan joins possible.

To sort $N$ blocks using $B$ buffer pages:

• Pass 1 reads $B$ blocks at a time, sorts them in memory, and writes them back as a sorted chunk. That produces $\lceil N/B \rceil$ chunks.
• Every later pass uses $B-1$ pages for input chunks and 1 for output, merging $B-1$ chunks into one. Each pass reduces the chunk count by a factor of $B-1$ and lengthens chunks by the same factor.

Repeat until one chunk remains:

The $2N$ is because every pass reads and writes every block. With $B = 5$ and $N = 40$: pass 1 makes 8 chunks of 5 pages, pass 2 merges 4 at a time into 2 chunks of 20, pass 3 merges those into one — $1 + \lceil \log_4 8 \rceil = 3$ passes, $2 \times 40 \times 3 = 240$ I/O.

The formula degrades gently: sorting a billion blocks with 129 buffers takes 5 passes.

06 · Optimization

Cost-based plan choice

With profiles and formulas in hand, the optimizer searches. Three decisions, combinatorially many combinations.

The decisions are: which data access operations to execute (scan versus index access), in what order (crucially, the join order), and with which implementation option for each operation (which join method). The search is organised as a decision tree — each node a choice, each leaf a complete execution plan — and each leaf is priced by

though in this course $n_{I/O}$ is all that is counted. The tree is explored with operations-research techniques (branch and bound), and — the honest part — optimizers aim for a good solution in a very short time, not the optimal one. Exhaustive search over join orders is factorial; spending longer optimizing than executing would be self-defeating.

Two execution strategies follow:

• Compile and store — the query is compiled once and executed many times (a prepared statement). The internal code is stored alongside the catalog versions it depends on; a relevant catalog change invalidates it and forces recompilation.
• Compile and go — immediate execution, no storage, though the code may survive briefly in memory for reuse.

PREPARE my_query1 FROM 'SELECT * FROM students WHERE id = ?';
EXECUTE my_query1 USING 54;
EXECUTE my_query1 USING 2;
DEALLOCATE PREPARE my_query1;

07 · Practice

Buffer pool, EXPLAIN, and a real plan

A short look at the live system, both to make the model concrete and to see where it is idealised.

When a query executes, the DBMS loads the pages it needs into the buffer pool. A page already there is a cache hit; otherwise a cache miss forces a disk read. The pool holds data pages, index pages, and in some systems execution plans. When it fills, pages are evicted by LRU or a variant — least recently used first.

That is precisely the mechanism our cost model ignores when it assumes no caching. The assumption is deliberate and conservative: it gives an upper bound and keeps the arithmetic checkable. Exercises that want the other number ask for it explicitly.

Every major system exposes the chosen plan through EXPLAIN / EXPLAIN PLAN. Here is a genuine one, from Politecnico’s own student-records database — a five-way join returning seven rows:

| Id | Operation                          | Name                | Cost | A-Rows |
|  0 | SELECT STATEMENT                   |                     |   19 |      7 |
|  1 |  NESTED LOOPS                      |                     |   19 |      7 |
|  2 |   NESTED LOOPS                     |                     |   19 |      7 |
|  3 |    NESTED LOOPS                    |                     |   10 |      7 |
|  6 |     TABLE ACCESS BY INDEX ROWID    | AUNICA              |    3 |      1 |
|* 7 |      INDEX UNIQUE SCAN             | UK_AUNICA           |    2 |      1 |
|  8 |     TABLE ACCESS BY INDEX ROWID    | CARRIERA            |    4 |      1 |
|* 9 |      INDEX RANGE SCAN              | NU_CARR_ID_STUDENTE |    2 |      1 |

Read it inside-out and the vocabulary is exactly this chapter’s: nested loops, index unique scan for the equality on a key, index range scan for the non-unique foreign key, table access by rowid to fetch the tuple once the index gave its address. The optimizer drives from the most selective predicate — the single person id — and the whole query costs 19 units and about a millisecond.

08 · Exam

Writing a full cost formula

The exercise does not ask for a number. It asks for a plan description, the block counts with their derivations, and the complete formula — cached and uncached where both apply.

Here is the drill on a real paper, February 2026, worked end to end.