Chapter 39 of 41

Query Processing & Optimization

When you type a SQL query, you describe what you want, not how to get it. You never tell the database "scan this table first, then use that index, then join with a hash table". Yet the same query can run in 5 milliseconds or 5 minutes depending on exactly those choices.

The part of the DBMS that turns your declarative SQL into a fast, step-by-step execution plan is the query processor, and its most important component is the query optimizer.

Query processing is the set of activities involved in extracting data from a database: translating a high-level query into low-level operations, choosing an efficient way to run them (optimization), and actually executing them (evaluation).

This chapter uses ideas from Relational Algebra, Indexing in DBMS, B-Tree & B+ Tree and Hashing in DBMS.


The Three Steps of Query Processing

   SQL query
       |
       v
+-----------------------+
| 1. Parsing and        |   check syntax, check that tables/columns exist,
|    Translation        |   check permissions, expand views,
+-----------------------+   produce a relational algebra expression
       |
       v
+-----------------------+
| 2. Optimization       |   consider many equivalent plans,
|                       |   estimate their costs using statistics
+-----------------------+   from the catalog, choose the cheapest
       |
       v
+-----------------------+
| 3. Evaluation         |   the execution engine runs the chosen
|    (Execution)        |   plan and returns the result rows
+-----------------------+
       |
       v
    Result

1. Parsing and Translation

  • The parser checks the SQL syntax (is it a valid statement?).

  • The semantic check verifies that tables and columns exist, types are compatible, and you have permission. Views are replaced by their definitions.

  • The query is translated into an internal form, typically a relational algebra expression or tree.

Example using the company_db sample database from our SQL tutorial:

SELECT e.name, d.dept_name
FROM employees e JOIN departments d ON e.dept_id = d.dept_id
WHERE d.location = 'Mumbai';

A direct translation into relational algebra:

π name, dept_name ( σ location='Mumbai' ( employees ⋈ departments ) )

2. Optimization

The same result can be produced by many equivalent expressions and, for each expression, by many different algorithms. The optimizer's job is to choose a good one. For example, this expression gives the same answer:

π name, dept_name ( employees ⋈ σ location='Mumbai' ( departments ) )

but it filters departments before joining, so the join processes 1 department instead of 5. On real tables with millions of rows, that difference is huge.

3. Evaluation

A relational algebra expression annotated with which algorithm to use for each operation (e.g. "use the index on dept_id", "use hash join") is called a query evaluation plan (or execution plan). The query execution engine runs this plan.


How Do We Measure the Cost of a Plan?

For disk-based databases the dominant cost is disk I/O. Textbooks measure it with two quantities:

  • Number of block transfers (each takes time tT)

  • Number of seeks (each takes time tS, much larger than tT on spinning disks)

Cost = (blocks transferred × tT) + (seeks × tS). In most exam problems we simply count block transfers, which is what we do below. We also usually ignore the cost of writing the final result, because it is the same for every plan.

Notation used below for a relation r:

  • nr = number of tuples in r

  • br = number of blocks containing r

  • V(A, r) = number of distinct values of attribute A in r

  • M = number of memory buffer blocks available


Algorithms for Selection

Algorithm

When usable

Approximate cost (block transfers)

Linear scan

Always

br (or br/2 on average for an equality on a key, since we can stop when found)

Binary search

File sorted on the attribute, equality condition

⌈log2 br⌉ (+ extra blocks if several records match)

Primary (clustering) B+ tree index, equality on key

Index on the ordering key

hi + 1 (tree height + 1 data block)

Secondary B+ tree index, equality on non-key

Any secondary index

hi + n (n matching records may each be in a different block)

Index range scan

Comparison conditions (<, >, BETWEEN) with a B+ tree

hi + leaf blocks scanned + data blocks fetched

Notice the last two rows: a secondary index on a condition that matches many rows can cost more than a linear scan, because each match may need a separate block read. This is why optimizers sometimes ignore an index, and why "the index exists, but MySQL is not using it" is not always a bug.


Algorithms for Join

Joins are usually the most expensive part of a query. We compare the main algorithms on one example:

  • customers: n = 2,000 tuples in b = 50 blocks

  • orders: n = 20,000 tuples in b = 500 blocks

  • Join condition: customers.customer_id = orders.customer_id

1. Nested-Loop Join

for each tuple c in customers:          -- outer relation
    for each tuple o in orders:         -- inner relation
        if c.customer_id = o.customer_id: output (c, o)

Worst case (memory holds only one block of each relation): the whole inner relation is read once per outer tuple.

Cost = n_outer * b_inner + b_outer

customers as outer: 2000 * 500 + 50  = 1,000,050 block transfers
orders as outer:    20000 * 50 + 500 = 1,000,500 block transfers

Simple, works for any join condition, and terrible for large tables.

2. Block Nested-Loop Join

Improvement: for each block of the outer relation (not each tuple), scan the inner relation once and match all tuples of that block.

Worst case (1 buffer block per relation):
Cost = b_outer * b_inner + b_outer

customers as outer: 50 * 500 + 50 = 25,050 block transfers

With M buffer blocks, use M − 2 of them for chunks of the outer relation (one block is kept for reading the inner relation and one for output):

Cost = ceil(b_outer / (M - 2)) * b_inner + b_outer

M = 12: ceil(50 / 10) * 500 + 50 = 2,550
M = 52: ceil(50 / 50) * 500 + 50 =   550   (outer fits in memory: each relation read once)

Rule of thumb: use the smaller relation as the outer relation.

3. Indexed Nested-Loop Join

If the inner relation has an index on the join attribute, replace the inner scan with an index lookup:

Cost = b_outer + n_outer * c
       (c = cost of one index lookup including fetching matching tuples)

Suppose a secondary B+ tree on orders.customer_id has height 3, and each customer has about 10 orders stored in different blocks, so c ≈ 3 + 10 = 13:

Cost = 50 + 2000 * 13 = 26,050 block transfers

Here it is worse than block nested-loop with plenty of memory, but it shines when the outer side is small (e.g. after a selective WHERE), because then only a few lookups are needed.

4. Sort-Merge Join

Sort both relations on the join attribute, then scan them together like the merge step of merge sort, matching equal values.

If both are already sorted:  Cost = b_r + b_s = 50 + 500 = 550
Otherwise add the cost of external sorting each relation.

Works only for equi-joins (and natural joins). Very good when inputs are already sorted, e.g. read through a B+ tree index on the join column.

5. Hash Join

  1. Partition both relations using the same hash function on the join attribute. Matching tuples must land in the same partition number.

  2. Build and probe: for each partition pair, load the smaller one (the build input) into an in-memory hash table and scan the other (the probe input) looking up matches.

Cost ≈ 3 * (b_r + b_s)       (read + write both while partitioning, read both again)
     = 3 * (50 + 500) = 1,650 block transfers

If the build relation fits entirely in memory, no partitioning is needed:
Cost = b_r + b_s = 550

Hash join works only for equality conditions, but it is usually the best choice for large, unsorted, unindexed equi-joins.

Join Algorithm Summary

Algorithm

Join conditions

Cost in our example

Best when

Nested-loop

Any

1,000,050

Tiny tables, or non-equality conditions with no alternative

Block nested-loop

Any

25,050 (M = 3) to 550 (outer fits)

Smaller relation fits (mostly) in memory

Indexed nested-loop

Equality (or range) with index on inner

26,050

Small outer input, indexed inner

Sort-merge

Equi-join

550 + sorting

Inputs already sorted

Hash join

Equi-join

1,650 (550 if build side fits)

Large unsorted inputs


Materialization vs Pipelining

A plan is a tree of operations. How does the output of one operation reach the next?

  • Materialization: each operation writes its full result to a temporary table on disk, and the next operation reads it. Simple, but costs extra writes and reads.

  • Pipelining: tuples are passed to the next operation as soon as they are produced, without storing the whole intermediate result. Cheaper and returns the first rows sooner.

Some operations cannot be pipelined fully: for example, sorting must see all its input before producing the first output tuple, and a hash join must finish building the hash table before probing. These are called blocking operations.


Query Optimization

There are two broad approaches, and real optimizers combine them:

  • Heuristic (rule-based) optimization: apply rules that almost always help, like "filter early".

  • Cost-based optimization: generate alternative plans, estimate the cost of each using statistics, and pick the cheapest.

Equivalence Rules

Two relational algebra expressions are equivalent if they produce the same result on every legal database instance. The optimizer rewrites expressions using rules like these (θ denotes a condition, L a list of attributes):

  1. Cascade of selections: σθ1 ∧ θ2(E) = σθ1(σθ2(E))

  2. Selections commute: σθ1(σθ2(E)) = σθ2(σθ1(E))

  3. Cascade of projections: only the last (outermost) projection matters: πL1(πL2(E)) = πL1(E) when L1 ⊆ L2

  4. Joins are commutative: E1 ⋈ E2 = E2 ⋈ E1 (up to column order)

  5. Natural joins are associative: (E1 ⋈ E2) ⋈ E3 = E1 ⋈ (E2 ⋈ E3)

  6. Selection pushdown: if θ uses only attributes of E1, then σθ(E1 ⋈ E2) = σθ(E1) ⋈ E2

  7. Projection pushdown: a projection can be pushed below a join, as long as each side keeps the attributes needed for the join and for the final result.

  8. Set operations: union and intersection are commutative and associative; selection distributes over ∪, ∩ and −.

Heuristic Optimization

Typical heuristics, in order:

  1. Break conjunctive selections into a cascade (rule 1) so each part can move independently.

  2. Push selections down the tree as far as possible (rule 6). Filtering early shrinks every later step.

  3. Perform the most restrictive selections and joins first (the ones producing the fewest tuples).

  4. Replace a Cartesian product followed by a selection with a join.

  5. Push projections down to drop unneeded columns early.

  6. Identify subtrees that can be pipelined.

Example. "Names of employees whose department is in Mumbai and who earn more than 60,000." The naive tree from the SQL:

                 π name
                   |
     σ location='Mumbai' ∧ salary>60000 ∧ e.dept_id=d.dept_id
                   |
                   ×                    (Cartesian product: 10 * 5 = 50 tuples)
                 /   \
         employees   departments

After the heuristics (split the selection, push each part down to its table, turn × + join condition into ⋈, keep only needed columns):

                        π name
                          |
                ⋈ e.dept_id = d.dept_id
               /                        \
    π name, dept_id                 π dept_id
         |                               |
  σ salary > 60000              σ location = 'Mumbai'
         |                               |
     employees                      departments

On our data: the left side keeps 7 of 10 employees (those earning more than 60,000), the right side keeps 1 of 5 departments, and the join combines 7 × 1 pairs instead of materialising 50 combinations. The final answer is the same: Sneha Kapoor and Vikram Singh.

Cost-Based Optimization

Heuristics do not tell you which join order or which algorithm is best. For that, the optimizer estimates costs using statistics stored in the system catalog: nr, br, V(A, r), and often histograms of value distributions.

Estimating result sizes (selectivity):

  • σA = v(r): about nr / V(A, r) tuples, assuming values are uniformly distributed. If orders has 20,000 rows and 5 distinct statuses, status = 'Delivered' is estimated at 20,000 / 5 = 4,000 rows.

  • Equality on a key: at most 1 tuple.

  • r ⋈ s where the join attribute is a foreign key in s referencing the primary key of r: exactly ns tuples (each s tuple matches exactly one r tuple, ignoring NULLs). For customers ⋈ orders that is 20,000.

Estimates can be wrong (data is rarely uniform), and a bad estimate can lead to a bad plan. That is why keeping statistics up to date matters.

Choosing a join order. The number of possible join orders grows explosively. For n relations there are (2(n − 1))! / (n − 1)! different join trees:

Relations n

All join trees

Left-deep join orders (n!)

3

12

6

5

1,680

120

7

665,280

5,040

10

17,643,225,600

3,628,800

Optimizers cannot try them all. Classic systems (starting with IBM's System R) use dynamic programming: find the best plan for every subset of relations once and reuse it, and often consider only left-deep trees (the right input of every join is a base table), which work well with pipelining and indexed nested-loop joins. Many optimizers switch to heuristics or randomized search when the number of tables is very large.


Seeing the Optimizer at Work in MySQL 8

EXPLAIN FORMAT=TREE prints the chosen plan as a tree (read it from the innermost, most indented lines outwards). Running our earlier query on company_db:

EXPLAIN FORMAT=TREE
SELECT e.name, d.dept_name
FROM employees e JOIN departments d ON e.dept_id = d.dept_id
WHERE d.location = 'Mumbai';
-> Nested loop inner join  (cost=1.45 rows=2)
    -> Filter: (d.location = 'Mumbai')  (cost=0.75 rows=1)
        -> Table scan on d  (cost=0.75 rows=5)
    -> Index lookup on e using dept_id (dept_id=d.dept_id)  (cost=0.7 rows=2)

Everything from this chapter is visible:

  • Selection pushdown: the filter on location is applied to departments before the join.

  • Join order: the small filtered side (1 estimated row) is the outer input.

  • Algorithm choice: an indexed nested-loop join, using the index on employees.dept_id for each outer row.

  • Estimates: rows=1 and rows=2 are the optimizer's cardinality estimates; cost is in MySQL's internal cost units (not milliseconds).

Now a join on city, which has no index on either table:

EXPLAIN FORMAT=TREE
SELECT e.name, c.name FROM employees e JOIN customers c ON e.city = c.city;
-> Inner hash join (e.city = c.city)  (cost=6 rows=5)
    -> Table scan on e  (cost=0.0704 rows=10)
    -> Hash
        -> Table scan on c  (cost=0.75 rows=5)

With no index to use, MySQL chooses a hash join: it builds a hash table on the smaller input (customers, under Hash) and probes it with each row of employees. MySQL has supported hash joins since version 8.0.18.

The optimizer also rewrites queries. This subquery:

EXPLAIN FORMAT=TREE
SELECT name FROM employees
WHERE dept_id IN (SELECT dept_id FROM departments WHERE location = 'Mumbai');
-> Nested loop inner join  (cost=1.45 rows=2)
    -> Filter: (departments.location = 'Mumbai')  (cost=0.75 rows=1)
        -> Table scan on departments  (cost=0.75 rows=5)
    -> Index lookup on employees using dept_id (dept_id=departments.dept_id)  (cost=0.7 rows=2)

was transformed into an ordinary join (MySQL can do this because dept_id is the primary key of departments, so the join cannot create duplicates). It returns Sneha Kapoor, Vikram Singh and Ananya Das. You wrote a subquery; the database ran a join.

Statistics Matter

The plans above were captured after running ANALYZE TABLE employees, departments, customers;. The plan depends on the optimizer's estimates. While preparing this chapter, the same first query on a freshly loaded copy (before ANALYZE TABLE) still chose the indexed nested-loop join, but estimated rows=5 for the index lookup instead of 2. On another copy of the same data that had been in use for a while, it chose a hash join instead. That happened because MySQL's cost model also considers things like how much of each table is already cached in memory. Same query, same data, different plan: the optimizer can only be as good as its estimates. So the cost numbers, and sometimes the plan itself, may differ on your machine.

Two more tools worth knowing:

  • EXPLAIN ANALYZE actually runs the query and shows real row counts and timings next to the estimates, so you can spot bad estimates.

  • ANALYZE TABLE refreshes index statistics; MySQL 8 can also store histograms on non-indexed columns (ANALYZE TABLE t UPDATE HISTOGRAM ON col) to improve selectivity estimates.


Common Mistakes

  • Thinking SQL runs in the order it is written. The optimizer freely reorders joins, pushes filters down, and rewrites subqueries.

  • Using the larger relation as the outer loop in nested-loop cost questions without checking. Compute both.

  • Forgetting the "+ bouter" term in nested-loop and block nested-loop formulas.

  • Using hash or sort-merge join for non-equality conditions. Both need equality on the join attribute.

  • Assuming an index always helps. For low-selectivity conditions, a scan can be cheaper.

  • Pushing a selection below a join when the condition uses attributes of both relations. That condition can only be applied at the join.


Interview Questions

1. What are the steps of query processing?

Parsing and translation (syntax and semantic checks, convert to relational algebra), optimization (choose the cheapest equivalent evaluation plan), and evaluation (the execution engine runs the plan).

2. What is a query evaluation plan?

A relational algebra tree in which every operation is annotated with the algorithm and access path to use (e.g. index lookup, hash join), plus how results flow between operations (pipelined or materialized).

3. Heuristic vs cost-based optimization?

Heuristic optimization applies rules that usually help (push selections and projections down, avoid Cartesian products). Cost-based optimization enumerates alternative plans and picks the one with the lowest estimated cost using catalog statistics. Real optimizers use both.

4. Why push selections down?

Filtering early reduces the number of tuples every later operation (especially joins) must process, which reduces I/O and CPU.

5. Compare nested-loop, sort-merge and hash join.

Nested-loop works for any condition but is slow on big inputs unless an index (indexed nested-loop) or enough memory (block nested-loop) is available. Sort-merge and hash join need equality; sort-merge is ideal for already sorted inputs, hash join for large unsorted inputs.

6. What statistics does an optimizer use?

Table row counts, number of blocks, number of distinct values per column, index heights, min/max values and histograms of value distribution.

7. How do you see the plan a query uses in MySQL?

With EXPLAIN (tabular), EXPLAIN FORMAT=TREE, or EXPLAIN ANALYZE (executes the query and reports actual rows and timing).


Summary

  • Query processing = parsing and translation → optimization → evaluation.

  • Cost is measured mainly in block transfers (and seeks).

  • Selection can use linear scan, binary search, or indexes; a non-selective index lookup can be worse than a scan.

  • Join algorithms: nested-loop, block nested-loop, indexed nested-loop, sort-merge, hash join, with very different costs.

  • Equivalence rules let the optimizer rewrite queries; the key heuristic is to push selections and projections down.

  • Cost-based optimization uses statistics to estimate result sizes and chooses join orders, usually via dynamic programming over left-deep trees.

  • In MySQL, EXPLAIN FORMAT=TREE and EXPLAIN ANALYZE show these decisions.

You write what you want; the optimizer decides how to get it, and good statistics help it decide well.