SQL & Query Planning

SQL is a declarative, set-based language over relational algebra. The query optimizer translates a SQL statement into a concrete execution plan (a tree of operators) and the executor evaluates it. This page covers the compilation and execution of queries.

Authoritative sources

Database System Concepts, Ch. 11–12 (Silberschatz, Korth, Sudarshan)

The PostgreSQL Query Planner

SQL as relational algebra

A SELECT … FROM … WHERE … corresponds to $\pi(\sigma(R))$ ; a JOIN corresponds to $\bowtie$ (see Relational Algebra for the formal definitions of $\sigma$ , $\pi$ , $\bowtie$ , and the other algebra operators).

SELECT col FROM t WHERE pred → $\pi_{\text{col}}(\sigma_{\text{pred}}(t))$
SELECT * FROM a JOIN b ON a.x = b.y → $a \bowtie_{a.x = b.y} b$
SELECT DISTINCT col FROM t → $\pi_{\text{col}}(t)$ (set semantics)
SELECT col FROM t ORDER BY col LIMIT k → top- $k$ selection (not pure relational algebra; requires ordering)

Details

Declarative vs. imperative: SQL specifies what to compute, not how. The optimizer is free to reorder joins, push predicates, choose indexes, and parallelize. This is analogous to how a compiler optimizes an imperative program: the semantics are fixed, the execution strategy is not.

Subqueries and CTEs: WHERE x IN (SELECT y FROM t) is a semi-join. WITH cte AS (SELECT …) SELECT … FROM cte is a named subexpression that the optimizer may inline or materialize.

NULL semantics: SQL uses three-valued logic (true, false, unknown). NULL = NULL is unknown, not true. This affects WHERE (unknown is treated as false) and JOIN (NULLs do not match in equi-joins).

Worked example: is SELECT name FROM users WHERE age > 30 OR city = 'Paris' expressible in pure relational algebra?

Solution

Yes: $\pi_{\text{name}}(\sigma_{\text{age} > 30 \,\lor\, \text{city} = \text{'Paris'}}(\text{users}))$ . The OR is a single selection predicate (algebra allows arbitrary boolean formulas), so no union is needed. Only DISTINCT, ORDER BY, LIMIT, and aggregation fall outside the pure algebra.

Join algorithms

A join of relations $R$ and $S$ can be executed by three physical algorithms. The optimizer picks one per join, based on sizes, indexes, and sort order.

Nested-loop join: for each tuple of $R$ , probe $S$ . With an index on the join column of $S$ (index nested-loop), each probe is $O(\log |S|)$ . No sorting, no hashing; works for any join predicate, including range conditions.
Hash join: build an in-memory hash table on the smaller relation, probe it with the other. Equi-joins only; expected linear time, no index needed.
Sort-merge join: sort both inputs on the join key (or read them pre-sorted from an index), then merge. If both inputs are already sorted, it is linear and its output is sorted on the join key — which can make a downstream ORDER BY free.

Algorithm	Time (no index, unsorted)	Extra memory	Join predicate	Output sorted?
Nested-loop (block)	O(\|R\| × \|S\|)	O(1)–O(1 page)	any	no
Index nested-loop	O(\|R\| · log \|S\|)	index on inner	any (index-supported)	no
Hash	O(\|R\| + \|S\|) expected	O(min(\|R\|, \|S\|))	equality only	no
Sort-merge	O(\|R\| log \|R\| + \|S\| log \|S\|); O(\|R\| + \|S\|) if pre-sorted	sort runs	equality and ranges	yes, on join key

Details

How the optimizer chooses: a hash join wins for large unsorted inputs with an equality predicate and no useful index. An index nested-loop wins when the outer relation is small (or highly selective after filtering) and the inner has an index — the cost is one index probe per outer row. A sort-merge wins when the inputs are already sorted (via indexes or a required sort downstream), or for range joins. See Relational Algebra for the algebraic definition of the join operator itself.

Worked example: orders has 10M rows, customers has 100k rows, and the query is SELECT * FROM orders o JOIN customers c ON o.customer_id = c.id WHERE c.country = 'FR'. Which algorithm is likely cheapest?

Solution

The filter c.country = 'FR' is applied first, leaving perhaps 2k rows of c. The optimizer then picks an index nested-loop join: for each of the ~2k French customers, probe the index on orders(customer_id) — cost ≈ $2\,000 \times \log(10^7)$ index probes, far cheaper than hashing 10M orders or sorting both sides. If the filter were absent (all 100k customers), a hash join on the smaller relation (customers) would typically win.

Query optimizer

The query optimizer translates a relational-algebra expression into a concrete execution plan. It uses table statistics (row counts, column histograms, index availability) to estimate the cost of each candidate plan, then selects the cheapest.

Cost model: cost = I/O cost (pages read) + CPU cost (rows processed). The optimizer compares:

Sequential scan: read all pages of the table. Cost ≈ number of pages.
Index scan: seek to the relevant B-tree range. Cost ≈ $\log n$ + number of matching rows.
Index-only scan: read only the index (no table lookup). Cheaper if the index covers all needed columns.

The decisive quantity is selectivity: the fraction of rows a predicate keeps. A sequential scan wins when selectivity is high (many rows match); an index scan wins when it is low. The chart below compares the two for a 10M-row table (100,000 pages, random-I/O cost 4× a sequential page read):

Join order: for $k$ tables, the number of possible join orders (all binary tree shapes × all permutations of the tables) is the $(k-1)$ -th Catalan number times $k!$ :

C_{k-1} \cdot k! = \frac{(2(k-1))!}{(k-1)!}

This grows super-exponentially: 12 orders for $k = 3$ , 665,280 for $k = 7$ . No optimizer enumerates them all for large $k$ :

PostgreSQL: dynamic programming over subsets of tables — exhaustive for small joins, and it switches to a greedy genetic search above geqo_threshold (default 12) tables.
MySQL: greedy incremental search — it builds the plan one table at a time, at each step picking the table with the lowest estimated incremental cost (with exhaustive search for small joins, controlled by optimizer_search_depth).

Index usage in planning: the optimizer compares the cost of an index scan against a sequential scan using the selectivity estimates above, and chooses the join algorithm accordingly (see Join algorithms for the per-algorithm complexities). For the index types available (B-tree, hash, composite, covering) and the principles for choosing which indexes to build, see Schema.

Parallel query: modern optimizers can split a scan or join across multiple CPU cores. The cost model is adjusted: cost / number of workers (with a setup overhead).

Details

Selectivity estimation: the optimizer uses histograms, most-common-value lists, and distinct-count statistics per column; for conjunctive predicates (AND) it multiplies selectivities, assuming independence — an assumption that fails for correlated columns and is a classic source of plan misestimates. ANALYZE (PostgreSQL) or ANALYZE TABLE (MySQL) refreshes the statistics.

Worked example: WHERE status = 'active' matches 95% of rows; there is a B-tree index on status. Which scan does the optimizer pick?

Solution

The sequential scan. Index scan cost ≈ $\log n + 0.95n$ random-I/O page reads (each matching row costs a random heap fetch), which is far more than reading the $n$ pages once sequentially. An index only pays off for low selectivity — this is why an unused index on a low-cardinality column is not a bug, and why the crossover point in the chart above sits at a few percent.

EXPLAIN

EXPLAIN shows the chosen plan as a tree of operators. Both PostgreSQL and MySQL support it; EXPLAIN ANALYZE additionally executes the query and reports actual row counts and timing (PostgreSQL; MySQL 8.0.18+).

Reading an EXPLAIN plan:

The top operator is the output; children are inputs.
Each node shows: operator type, estimated rows, estimated cost, and (with ANALYZE) actual rows and timing.
A Seq Scan on a large table with a tight WHERE usually signals a missing index.
A Sort node above a join means the join did not produce sorted output (a sort-merge join would avoid this).

For a three-table join, the plan is a tree whose leaves are access paths (scans) and whose internal nodes are join and sort operators:

Details

PostgreSQL EXPLAIN example:

Limit  (cost=0.42..8.43 rows=20 width=36)
  ->  Index Scan using idx_orders_cust_created on orders  (cost=0.42..843.21 rows=1000 width=36)
        Index Cond: (customer_id = 42)

This shows: the plan is an index scan (not a seq scan), the index condition is customer_id = 42, and the LIMIT 20 stops after 20 rows. The cost 0.42 is the startup cost (seek to the first matching entry); 8.43 is the total cost for 20 rows.

EXPLAIN ANALYZE adds actual timing:

Limit  (cost=0.42..8.43 rows=20) (actual time=0.051..0.112 rows=20 loops=1)
  ->  Index Scan using idx_orders_cust_created on orders  (cost=0.42..843.21 rows=1000) (actual time=0.048..0.108 rows=20 loops=1)

If actual rows differs greatly from estimated rows, the statistics are stale — run ANALYZE.

Worked example: an EXPLAIN ANALYZE line reads Seq Scan on orders (cost=0..120000 rows=10) (actual rows=9800000). What went wrong and what is the fix?

Solution

The optimizer estimated 10 matching rows but 9.8M actually matched — a selectivity misestimate of three orders of magnitude, so it wrongly preferred an index scan over a sequential scan. Fix: run ANALYZE orders to refresh statistics (and check for correlated columns, which break the independence assumption). See Transactions for how concurrent writes can also make statistics stale.

Example problem

Quizz

Problem: A table orders(id, customer_id, amount, created_at) has 10M rows. The query SELECT * FROM orders WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20 is slow. Design an index and explain why.

Solution

Index: a composite B-tree index on (customer_id, created_at DESC).

Why it works:

The B-tree index allows an $O(\log_F n)$ seek to the first entry with customer_id = 42, where $F$ is the fanout (entries per page). The log base is the fanout, not 2: for 10M rows at fanout ≈ 200, the tree depth is $\log_{200}(10^7) \approx 3.3$ , i.e. ~4 page reads — not $\log_2(10^7) \approx 23$ .
Within that range, entries are already sorted by created_at DESC, so the ORDER BY is free (no sort step).
The LIMIT 20 stops after 20 entries.

Total cost: ~4 page reads for the tree descent + ~20 leaf-entry reads ≈ 24 I/O operations, versus 100,000 pages for a sequential scan.

Without the index: the planner would either (a) scan the entire table and filter, or (b) use a single-column index on customer_id and then sort the matching rows by created_at. Both are far more expensive.

Write cost: every INSERT, UPDATE, or DELETE on orders must also update the index. For a write-heavy workload, this is a trade-off. See Key-Value Stores for B-tree vs. LSM-tree write characteristics, and Schema for index design principles (composite column ordering, covering indexes).

SQL & Query Planning §

SQL as relational algebra §

Join algorithms §

Query optimizer §

EXPLAIN §

Example problem §

SQL & Query Planning

SQL as relational algebra

Join algorithms

Query optimizer

EXPLAIN

Example problem