Part 3 · 1 chapters · ~8 min

Query Processing Theory

Query equivalence and containment, conjunctive queries and the homomorphism theorem, join ordering as an NP-hard problem with dynamic programming and heuristics, cardinality estimation theory and its failure modes, multi-column statistics, worst-case optimal joins and the AGM bound, and I/O-centric versus CPU-centric cost models.

Containment, ordering and estimation

code

-- containment: Q1 ⊆ Q2, so the join to accounts in Q1 adds nothing if Q2 already restricts the same way
Q1: SELECT t.id FROM transfers t JOIN accounts a ON a.id = t.acct JOIN accounts b ON b.id = t.acct
Q2: SELECT t.id FROM transfers t JOIN accounts a ON a.id = t.acct
-- a homomorphism maps Q2's body into Q1's (a→a), and Q1's into Q2's (a→a, b→a): equivalent, the b join is redundant

-- how many bushy join trees for n tables: (2n-2)! / (n-1)!
--   n = 4: 120 · n = 6: 30,240 · n = 10: 17,643,225,600
SHOW geqo_threshold;              -- 12 in Postgres: switch from exhaustive DP to genetic search

-- correlated columns break independence assumptions; tell the planner
CREATE STATISTICS addr_dep (dependencies, ndistinct) ON city, postcode FROM customers;
ANALYZE customers;

Cost models: classic optimisers counted page reads (I/O-centric, from disks where seeks dominated); modern in-memory and columnar engines model CPU, cache misses and vector width instead. When hardware changes, cost constants (random_page_cost on SSDs) should change too (Postgres course).

QUERY PROCESSING THEORY

why optimisers work, and why they fail

swipe the figure sideways, or tap expand for full screen

1/4

containment

If one query's results are always a subset of another's, an optimiser can drop redundant joins or reuse a materialised view. For conjunctive (select-project-join) queries this is decidable via homomorphisms.

decidable for SPJ queriesChandra and Merlin, 1977