SELECT says what rows are required, not how to obtain them. For a tenant’s failed deliveries, a database may scan a table, probe an index, hash a small relation, sort before aggregation, or stream groups in order. All correct plans return the same logical bag under the same SQL semantics; their intermediate cardinalities, memory pressure, and I/O differ radically.
Readiness refresh: selectivity and simple estimatesExpandCollapse
Selectivity is the fraction of rows that survive a predicate: a 5% predicate on 10,000 rows first estimates 500 rows. For two predicates, multiplying selectivities is an independence assumption, not a fact about correlated data. Tree height, hash access, and page I/O use the same bounded models introduced in storage; every estimate below names what it ignores.
An operator tree carries relations upward
Read the tree bottom-up. The orders access produces rows; the filter reduces them; the join attaches customer attributes; the aggregate changes the grain to one row per customer. “Hash join” alone does not establish quality. Building a hash table on 10,000 filtered orders can fit memory; building one on 500 million customers may spill or fail the cost budget.
Prediction — join result grain
orders has one row per order and order_line has one row per line. A join on order_id followed by SUM(line.amount) has what grain immediately before the aggregate?
HintExpandCollapse
A one-to-many join repeats the order fields once per matching line.
Worked solutionExpandCollapse
The joined stream has one row per matching order line, not one per order. Grouping by customer then sums line amounts at customer grain. If an order-level amount is joined and summed after this join, it is duplicated once per line; aggregate it at order grain first or use a different construction.
Cost begins with cardinality, not a magic constant
For a relation with rows and a predicate with selectivity a simple estimate is For an equijoin, an independence-based first estimate is often where is the distinct-count estimate. These are models to test, not laws of the data.
For a relation with rows and a predicate with selectivity a simple estimate is For an equijoin, an independence-based first estimate is often where is the distinct-count estimate. These are models to test, not laws of the data.
Suppose orders contains 10,000,000 rows and 1% are failed. The filter estimate is 100,000 rows. If 80% of failures belong to one enterprise tenant, treating tenant_id and status as independent can underestimate that tenant’s result by nearly two orders of magnitude. That error can turn a nested loop chosen for a tiny outer input into repeated expensive probes.
Change selectivity; inspect the plan’s I/O model
Estimate a join between filtered Orders and a 100-page Customers relation. Selectivity determines the number of clustered Orders pages that survive the predicate.
Model scope: page I/O dominates; the Orders index is clustered; hash memory is sufficient; one qualifying Orders page drives one nested-loop scan of Customers. It omits CPU, buffer residency, duplicate keys, non-clustered lookups, skew, parallelism, and stale statistics. Treat it as a reasoning model, not an optimizer prediction.
With 1,000 Orders pages and a 5% filter, 50 clustered pages qualify. Compare the three candidate plans under the same stated assumptions.
Static state: low selectivity lets a clustered index avoid most Orders pages; the index-assisted hash plan costs 153 I/Os, versus 1,100 for the scan/hash plan and 5,053 for this nested-loops model.
Vary selectivity and page count, then predict before revealing a plan. The model exposes a bounded scan/index/join trade-off; it does not claim a real DBMS uses its exact coefficients. Its value is making the hidden assumption visible: a selective access path becomes worse when the matching set approaches a scan.
Worked example — two plans
Assume a 1,000-page orders table, a 20-page customer table, and a predicate that returns 2 orders. A nested-loop plan that probes an index for two customers may be excellent. If stale statistics estimate 2 but actual rows are 200,000, the same plan can perform 200,000 probes; a hash join with a 20-page customer build may dominate. The logical query did not change. The cardinality claim did.
Physical algorithms expose different failure modes
| Operator choice | Strong case | Dangerous assumption | Observable warning |
|---|---|---|---|
| Sequential scan | high selectivity loss / most pages needed | index navigation is always faster | index plan visits most heap pages randomly |
| Index scan | few qualifying rows, useful order | predicate matches an index range | actual rows approach table cardinality |
| Hash join | modest build input, equality join | build fits memory | batches/spills or unexpectedly huge build |
| Merge join | inputs ordered or cheap to sort | order cost is recovered later | both inputs sort only for one join |
| Nested loop | tiny outer plus indexed inner | outer cardinality is truly tiny | probes explode after a misestimate |
Application — predicate placement changes both semantics and cost
An outer join must retain every customer, even those with no failed order. Where does order.status = 'failed' belong: in WHERE after a left join or in the join condition / filtered right input?
Worked solutionExpandCollapse
Place it in the right input or ON condition. A WHERE order.status = 'failed' filter after the left join removes null-extended rows and turns the result into an inner-join-like result. The optimizer may push a semantically valid filter down, but only after preserving outer-join null behavior. Correct cardinality starts with correct semantics.
The optimizer searches a space of equivalent plans
System R’s Selinger-style optimizer builds left-deep join trees bottom-up. For each subset of relations it keeps the cheapest plan for each interesting order, then extends that set by one relation and discards dominated alternatives. With relations there are subsets, so dynamic programming avoids enumerating orders, but the retained plan is only as good as its cardinality estimates and cost model.
Worked search. Let have 100 rows, 1,000 rows, and 10 rows. Assume all relevant equality joins exist, and use the deliberately simplified cost per hash join, with both inputs scanned once and all intermediate results fitting memory. Ignore output production, ordering, and access-path differences.
| Candidate | First intermediate | First join cost | Second join cost | Total |
|---|---|---|---|---|
| 50 rows | 1,100 | 60 | 1,160 | |
| 100 rows | 1,010 | 200 | 1,210 | |
| unknown | 110 |
The first two plans differ because both the first join’s input work and the intermediate size matter. The third is cheaper than 1,160 only if under these assumptions. In a real engine, selectivity estimates, memory, useful ordering, and physical access paths can reverse this result. A hash join may build on the smaller input; the intermediate size is not automatically the build-side size.
Volcano/Cascades optimizers search top-down instead. A memo stores equivalence classes of logical expressions; transformation rules generate equivalent logical alternatives, implementation rules produce physical alternatives, and branch-and-bound pruning discards alternatives whose lower bound exceeds the best known cost. This can explore bushy trees that a left-deep-only search excludes and can track required physical properties, at the cost of more complex rule interaction and search control. System R also tracked interesting orders; this is not unique to Cascades. Engines choose different search and cost strategies.
Search strategy versus cost model diagnosis
A query plan selects a nested loop with index probe. The planner estimates 50 outer rows, but execution observes 50,000 outer rows, causing severe probe degradation. Evaluate which diagnostic conclusions are sound:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Plans must be read as conditional evidence
EXPLAIN (ANALYZE, BUFFERS)
SELECT customer_id, count(*)
FROM orders
WHERE tenant_id = 12 AND status = 'failed'
GROUP BY customer_id;
For each node, record estimated rows, actual rows, loops, buffer reads/hits, and whether the node changed the expected grain. Test an empty tenant, a tenant with skewed failed rows, and a fresh-cached versus warm-cached run. A forced index plan is a diagnostic experiment, not a general remedy.
Transfer — an estimate that lies politely
A table has independent-looking global statistics: 1% status='failed', 1% region='north'. In north, however, 90% of rows have failed. A query filters both predicates. What should the optimizer or designer learn from a large estimate error?
HintExpandCollapse
The missing fact is correlation, not arithmetic competence.
Worked solutionExpandCollapse
Global independence predicts about of rows, while the north subset predicts about if north is 1% of the table. The response can include richer/multivariate statistics, a partition-aware estimate, a targeted index only if the workload supports it, and a regression query against the skew. Hard-coding one plan hides the data-distribution cause.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 3.3.1: Attribute Independence Assumption Failure in Cardinality Estimation
Referring to Proposition 3.3.1
HintExpandCollapse
Multiplying independent probabilities understates joint selectivity when values co-occur.
Worked solutionExpandCollapse
The product rule assumes statistical independence. If attribute implies or strongly concentrates attribute (e.g. city and zip code), joint occurrences are vastly higher than their independent product, causing the optimizer to severely underestimate cardinality. Creating multivariate extended statistics (such as n-distinct or dependency statistics) provides joint distribution frequencies directly to the planner.
Exercise 3.3.2: Index vs. Sequential Scan Cost Crossover Analysis
As visualized in the selectivity-cost crossover curve, describe the physical hardware reasons why an unclustered index scan becomes more expensive than a sequential heap scan once selectivity exceeds approximately 2% to 5%.
HintExpandCollapse
Compare sequential read throughput with random page lookup overhead.
Worked solutionExpandCollapse
Sequential table scans read contiguous disk blocks with sequential read-ahead buffering and predictable page cache replacement. An unclustered index scan must dereference heap tuple IDs randomly across table pages. Once selectivity exceeds a few percent, the number of random heap page fetches approaches or exceeds the total pages in the relation, making the sequential scan faster.
Exercise 3.3.3: Dynamic Programming Join Order Cost Calculation
Given relations (100 rows), (1,000 rows), and (10 rows), with and cost formula Calculate and compare the total join cost of plan versus
HintExpandCollapse
Sum the cost of the first join and the subsequent join on the intermediate result.
Worked solutionExpandCollapse
- Plan 1: First join has cost emitting 50 rows. Second join has cost Total cost =
- Plan 2: First join has cost emitting 100 rows. Second join has cost Total cost = Plan 1 is cheaper by 50 units because its first join generates a smaller intermediate cardinality.
References & Further Reading
- Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, R. A., & Price, T. G. (1979). Access Path Selection in a Relational Database Management System. ACM SIGMOD, 23–34. (System R dynamic-programming join enumeration.)
- Graefe, G. (1995). The Cascades Framework for Query Optimization. IEEE Data Engineering Bulletin, 18(3), 19–29. (Rule-driven top-down search and memo.)
- PostgreSQL: Using EXPLAIN
- PostgreSQL: Planner Statistics
- CMU 15-445/645 Database Systems