Cost-based optimisation and join ordering

Cost-based optimisation chooses a plan by pricing the alternatives: for every candidate plan the optimiser estimates the rows each step will produce, turns them into a cost with its cost model, and keeps the cheapest. The candidates differ in the access path for each table, the method of each join and, the largest part of the search, in join ordering, the order in which the tables are joined. Intermediate results can differ by factors of thousands between orders, and the number of orders grows faster than exponentially, so no optimiser tries them all. The standard method comes from IBM’s System R, published by Selinger and colleagues in 1979: dynamic programming over subsets of tables. PostgreSQL searches near-exhaustively below 12 FROM items and switches to a genetic search at 12; SQLite runs a bounded search of its own.

Why join ordering decides the cost, with numbers

A placement portal stores students, their applications, jobs and the companies that offer them. A query asks for the 2027 batch’s applications to SDE jobs at Bengaluru companies: after their filters, 12,500 students, 400,000 applications, 200 jobs and 60 companies, linked in a chain. The program counts the possible orders, then prices each left-deep order of the four tables by C_out, the rows every intermediate result holds:

# How many join orders there are, and how much the choice matters, for a
# placement portal: students apply to jobs offered by companies.
from itertools import permutations
from math import factorial

print(f"{'tables':>6}{'left-deep orders':>20}{'all join trees':>28}")
for n in (2, 3, 4, 5, 6, 8, 10, 12, 15):
    bushy = factorial(2 * n - 2) // factorial(n - 1)        # binary trees with ordered leaves
    print(f"{n:>6}{factorial(n):>20,}{bushy:>28,}")

# Table sizes after their filters, and the selectivity of each join condition.
rows = {"S": 50_000 * 0.25,      # students of the 2027 batch
        "A": 400_000,            # applications
        "J": 2_000 * 0.10,       # jobs for the SDE role
        "C": 300 * 0.20}         # companies in Bengaluru
join_sel = {frozenset("SA"): 1 / 50_000, frozenset("AJ"): 1 / 2_000, frozenset("JC"): 1 / 300}


def size(tables):
    """Estimated rows of the join of these tables: product of sizes and of the selectivities that apply."""
    n = 1.0
    for t in tables:
        n *= rows[t]
    for pair, s in join_sel.items():
        if pair <= set(tables):
            n *= s
    return n


def cost(order):
    """C_out: the rows of every intermediate result a left-deep plan builds."""
    return sum(size(order[:k]) for k in range(2, len(order) + 1))


orders = sorted(permutations("SAJC"), key=cost)
print(f"\n{len(orders)} left-deep orders for S JOIN A JOIN J JOIN C; rows built by each plan:")
for o in orders[:3] + orders[-3:]:
    print(f"  {' -> '.join(o)}{cost(o):>18,.0f}")
print(f"the worst builds {cost(orders[-1]) / cost(orders[0]):,.0f} times as many rows as the best")

tables    left-deep orders              all join trees
     2                   2                           2
     3                   6                          12
     4                  24                         120
     5                 120                       1,680
     6                 720                      30,240
     8              40,320                  17,297,280
    10           3,628,800              17,643,225,600
    12         479,001,600          28,158,588,057,600
    15   1,307,674,368,000   3,497,296,636,753,920,000

24 left-deep orders for S JOIN A JOIN J JOIN C; rows built by each plan:
  J -> C -> A -> S            10,040
  C -> J -> A -> S            10,040
  A -> J -> C -> S            50,000
  C -> A -> J -> S        24,010,000
  A -> C -> S -> J        30,002,000
  C -> A -> S -> J        30,002,000
the worst builds 2,988 times as many rows as the best

The best orders join the 60 companies to the 200 jobs first, keeping 40 rows, then the 8,000 applications to those jobs, then the 2,000 from the 2027 batch. The worst orders begin by pairing every application with every company, a cross product of 24 million rows, and build 2,988 times as many rows. Every order returns the same answer; cost-based optimisation is the choice between them.

The first table counts the candidates. A left-deep plan adds one table at a time, so there are n! of them. A bushy plan may also join two intermediate results, and counting every binary tree with its tables in order gives (2n − 2)! ÷ (n − 1)!: at 10 tables, 3.6 million left-deep orders and 17.6 billion trees. Join ordering by trying each one stops being possible after a handful of tables.

Dynamic programming over subsets, in brief

Selinger’s method rests on one observation. With a cost such as C_out, the rows of a join depend only on which tables it contains, not on the order inside it, so the cheapest way to join a set of tables is also part of the cheapest way to join any larger set that extends it. The optimiser therefore computes the best plan for every pair of tables, then for every triple built from the best pairs, and so on, keeping one plan per subset. The System R paper adds one refinement: a plan whose output is sorted in a way a later step can use is kept as well.

For three tables the method compares three ways to build the full set, each extending the best plan of a pair. For n tables it compares about n × 2ⁿ⁻¹ candidates instead of n! orders: 5,110 instead of 3,628,800 at 10 tables. Around it, real optimisers add a few named refinements:

• Interesting orders keep a costlier plan of a subset when its sort order saves a later sort.
• Greedy search builds one order step by step, always adding the table that looks cheapest next.
• GEQO, PostgreSQL’s genetic query optimizer, recombines random join orders once a query has 12 or more FROM items.
• join_collapse_limit and from_collapse_limit cap how many tables PostgreSQL reorders together.
• Generic and custom plans are a prepared statement planned without or with its parameter values.

SQLite reorders joins; CROSS JOIN fixes the order

SQLite plans every join as nested loops and chooses the order of the loops itself. Its documentation says inner joins may be reordered freely by the optimiser, with one exception it keeps on purpose: it never reorders the tables of a CROSS JOIN. The same portal, with 40,000 applications and statistics from ANALYZE:

-- A placement portal: 300 companies, 2,000 jobs, 5,000 students and 40,000 applications,
-- spread over the tables by multiplicative hashing so that every run builds the same data.
CREATE TABLE companies (id INTEGER PRIMARY KEY, city TEXT NOT NULL);
CREATE TABLE jobs (id INTEGER PRIMARY KEY, company_id INTEGER NOT NULL, role TEXT NOT NULL);
CREATE TABLE students (id INTEGER PRIMARY KEY, batch INTEGER NOT NULL);
CREATE TABLE applications (student_id INTEGER NOT NULL, job_id INTEGER NOT NULL, PRIMARY KEY (student_id, job_id));
CREATE INDEX companies_city ON companies (city);
CREATE INDEX jobs_company ON jobs (company_id);
CREATE INDEX applications_job ON applications (job_id);
WITH RECURSIVE n(i) AS (SELECT 1 UNION ALL SELECT i + 1 FROM n WHERE i < 300)
INSERT INTO companies SELECT i, CASE i % 5 WHEN 0 THEN 'Bengaluru' WHEN 1 THEN 'Pune' WHEN 2 THEN 'Chennai' WHEN 3 THEN 'Hyderabad' ELSE 'Noida' END FROM n;
WITH RECURSIVE n(i) AS (SELECT 1 UNION ALL SELECT i + 1 FROM n WHERE i < 2000)
INSERT INTO jobs SELECT i, 1 + (i * 2654435761) % 4294967296 % 300,
  CASE WHEN (i * 40503) % 65536 % 10 = 0 THEN 'SDE' ELSE 'other' END FROM n;
WITH RECURSIVE n(i) AS (SELECT 1 UNION ALL SELECT i + 1 FROM n WHERE i < 5000)
INSERT INTO students SELECT i, 2024 + (i * 69069) % 4294967296 % 4 FROM n;
WITH RECURSIVE n(i) AS (SELECT 1 UNION ALL SELECT i + 1 FROM n WHERE i < 40000)
INSERT OR IGNORE INTO applications
SELECT 1 + (i * 2654435761) % 4294967296 % 5000, 1 + ((i + 17) * 40503) % 65521 % 2000 FROM n;
ANALYZE;

-- 2027 students' applications to SDE jobs at Bengaluru companies.
SELECT count(*) AS applications
FROM students AS s JOIN applications AS a ON a.student_id = s.id
JOIN jobs AS j ON j.id = a.job_id JOIN companies AS c ON c.id = j.company_id
WHERE s.batch = 2027 AND j.role = 'SDE' AND c.city = 'Bengaluru';

-- The plan for the query as written ...
EXPLAIN QUERY PLAN
SELECT count(*) FROM students AS s JOIN applications AS a ON a.student_id = s.id
JOIN jobs AS j ON j.id = a.job_id JOIN companies AS c ON c.id = j.company_id
WHERE s.batch = 2027 AND j.role = 'SDE' AND c.city = 'Bengaluru';

-- ... and with the tables listed the other way round: the same plan.
EXPLAIN QUERY PLAN
SELECT count(*) FROM companies AS c JOIN jobs AS j ON c.id = j.company_id
JOIN applications AS a ON j.id = a.job_id JOIN students AS s ON a.student_id = s.id
WHERE s.batch = 2027 AND j.role = 'SDE' AND c.city = 'Bengaluru';

-- CROSS JOIN tells SQLite to keep the written order: students first.
EXPLAIN QUERY PLAN
SELECT count(*) FROM students AS s CROSS JOIN applications AS a CROSS JOIN jobs AS j CROSS JOIN companies AS c
WHERE a.student_id = s.id AND j.id = a.job_id AND c.id = j.company_id
  AND s.batch = 2027 AND j.role = 'SDE' AND c.city = 'Bengaluru';

┌──────────────┐
│ applications │
├──────────────┤
│ 208          │
└──────────────┘
┌────┬────────┬─────────┬───────────────────────────────────────────────────────┐
│ id │ parent │ notused │                        detail                         │
├────┼────────┼─────────┼───────────────────────────────────────────────────────┤
│ 8  │ 0      │ 76      │ SEARCH c USING COVERING INDEX companies_city (city=?) │
│ 12 │ 0      │ 55      │ SEARCH j USING INDEX jobs_company (company_id=?)      │
│ 19 │ 0      │ 70      │ SEARCH a USING INDEX applications_job (job_id=?)      │
│ 25 │ 0      │ 0       │ BLOOM FILTER ON s (id=?)                              │
│ 33 │ 0      │ 39      │ SEARCH s USING INTEGER PRIMARY KEY (rowid=?)          │
└────┴────────┴─────────┴───────────────────────────────────────────────────────┘
┌────┬────────┬─────────┬───────────────────────────────────────────────────────┐
│ id │ parent │ notused │                        detail                         │
├────┼────────┼─────────┼───────────────────────────────────────────────────────┤
│ 8  │ 0      │ 76      │ SEARCH c USING COVERING INDEX companies_city (city=?) │
│ 12 │ 0      │ 55      │ SEARCH j USING INDEX jobs_company (company_id=?)      │
│ 19 │ 0      │ 70      │ SEARCH a USING INDEX applications_job (job_id=?)      │
│ 25 │ 0      │ 0       │ BLOOM FILTER ON s (id=?)                              │
│ 33 │ 0      │ 39      │ SEARCH s USING INTEGER PRIMARY KEY (rowid=?)          │
└────┴────────┴─────────┴───────────────────────────────────────────────────────┘
┌────┬────────┬─────────┬──────────────────────────────────────────────────────────────────────────────┐
│ id │ parent │ notused │                                    detail                                    │
├────┼────────┼─────────┼──────────────────────────────────────────────────────────────────────────────┤
│ 6  │ 0      │ 138     │ SCAN s                                                                       │
│ 10 │ 0      │ 53      │ SEARCH a USING COVERING INDEX sqlite_autoindex_applications_1 (student_id=?) │
│ 15 │ 0      │ 0       │ BLOOM FILTER ON j (id=?)                                                     │
│ 23 │ 0      │ 38      │ SEARCH j USING INTEGER PRIMARY KEY (rowid=?)                                 │
│ 31 │ 0      │ 0       │ BLOOM FILTER ON c (id=?)                                                     │
│ 39 │ 0      │ 35      │ SEARCH c USING INTEGER PRIMARY KEY (rowid=?)                                 │
└────┴────────┴─────────┴──────────────────────────────────────────────────────────────────────────────┘

Both queries that use JOIN get the same plan, whatever their FROM order: start from the Bengaluru companies through the index on city, find their jobs, the applications to those jobs, then each applicant by key. With CROSS JOIN the written order wins, so SQLite scans all 5,000 students and looks up their applications, jobs and companies, filtering at every step. The answer, 208 applications, does not depend on the order; only the work does. SQLite’s documentation recommends this manual control only as a last resort, after ANALYZE and PRAGMA optimize.

Check yourself

Exercise

"""Join ordering by dynamic programming over subsets of tables.

rows    table name -> its rows after its own filters, for example {"S": 12500, "A": 400000}
sel     frozenset({"S", "A"}) -> the selectivity of the join condition between two tables;
        two tables without a condition between them form a cross product (selectivity 1)

The cost of a left-deep order is C_out: the estimated rows of every intermediate result it builds, the final
result included and the base tables not counted.
"""
from itertools import combinations


def size(tables, rows, sel):
    """Estimated rows of the join of these tables."""
    n = 1.0
    for t in tables:
        n *= rows[t]
    for pair, s in sel.items():
        if pair <= set(tables):
            n *= s
    return n


def cost(order, rows, sel):
    """C_out of a left-deep order (a tuple of table names)."""
    return sum(size(order[:k], rows, sel) for k in range(2, len(order) + 1))


def best_order(rows, sel):
    """The cheapest left-deep order and its cost, as (cost, order)."""
    # Replace this line with your code.
    order = tuple(rows)
    return cost(order, rows, sel), order

from itertools import permutations

from join_order import best_order, cost


def brute_force(rows, sel):
    return min(cost(o, rows, sel) for o in permutations(rows))


def chain(sizes, selectivities):
    names = [chr(ord("A") + i) for i in range(len(sizes))]
    rows = dict(zip(names, sizes))
    sel = {frozenset(names[i:i + 2]): s for i, s in enumerate(selectivities)}
    return rows, sel


def test_three_tables():
    """the 3-table table of the lesson: start with the pair that joins to the fewest rows"""
    rows = {"S": 12_500, "A": 400_000, "J": 200}
    sel = {frozenset("SA"): 1 / 50_000, frozenset("AJ"): 1 / 2_000}
    c, order = best_order(rows, sel)
    assert abs(c - brute_force(rows, sel)) < 1e-6
    assert abs(cost(order, rows, sel) - c) < 1e-6
    assert set(order[:2]) == {"A", "J"}


def test_the_placement_portal():
    """four tables, with costs that range from 10,040 to 30 million"""
    rows = {"S": 12_500, "A": 400_000, "J": 200, "C": 60}
    sel = {frozenset("SA"): 1 / 50_000, frozenset("AJ"): 1 / 2_000, frozenset("JC"): 1 / 300}
    c, order = best_order(rows, sel)
    assert abs(c - 10_040) < 1e-6
    assert len(order) == 4 and set(order) == set(rows)


def test_the_smallest_table_is_not_always_first():
    """greedy from the smallest table costs 20,100 here; the best order costs 210"""
    rows, sel = chain([100, 1_000, 10_000, 100], [1 / 10, 1 / 10_000, 1 / 10_000])
    c, order = best_order(rows, sel)
    assert abs(c - 210) < 1e-6
    assert abs(cost(order, rows, sel) - 210) < 1e-6


def test_ten_tables_in_time():
    """3,628,800 orders are too many to try one by one in the time limit; subsets are not"""
    rows, sel = chain([500, 20_000, 300, 80_000, 1_000, 50_000, 40, 9_000, 700, 2_000],
                      [1 / 400, 1 / 20_000, 1 / 300, 1 / 80_000, 1 / 1_000, 1 / 50_000, 1 / 40, 1 / 9_000, 1 / 700])
    c, order = best_order(rows, sel)
    assert len(order) == 10 and set(order) == set(rows)
    assert abs(cost(order, rows, sel) - c) < 1e-6 * c
    assert abs(c - EXPECTED_TEN) < 1e-6 * EXPECTED_TEN


EXPECTED_TEN = 8_275

Selinger's dynamic programming, traced and measured against the alternatives Pro: opens with a Pro, Premium or Ultimate pass

How PostgreSQL bounds the search, and when a cached plan goes wrong Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Join orders differ by factors of thousands in the rows they build; the portal query ranges from 10,040 to 30 million.
• n tables have n! left-deep orders and far more bushy plans, so optimisers search instead of trying them all.
• Dynamic programming keeps the best plan of every subset of tables and needs about n × 2ⁿ⁻¹ comparisons.