Search Knowledge

© 2026 LIBREUNI PROJECT

Database Systems/Storage, access, and execution
Page 11 of 20

Query Execution and Optimization

Turn declarative SQL into operator trees, cardinality estimates, and falsifiable physical-plan choices.

Lesson briefStorage, access, and execution · 8 h · 4 outcomes

Required knowledge

  • Relational algebra, SQL joins and aggregation, and bag versus set semantics
  • Indexes, pages, selectivity, and asymptotic cost reasoning
  • Basic probability: conditional probability, independence assumptions, and histograms

Learning outcomes

  • Read an operator tree bottom-up and state the relation, cardinality, and physical work produced at each node.
  • Compare scan, join, sort, and aggregation alternatives using cardinality and I/O assumptions rather than operator names.
  • Diagnose a bad plan from estimated-versus-actual rows and propose the next measurement or statistics repair.
  • Use an explain plan as evidence while separating semantic equivalence from performance estimates.

Assessment target

Given an unseen SQL query, table statistics, and two candidate plans, derive intermediate cardinalities, reject an unjustified plan choice, and explain how a changed data distribution reverses the decision.

Scope boundary

  • A complete memo implementation, adaptive re-optimization, vectorized-engine internals, and vendor-specific cost constants are deferred; the two dominant optimizer search strategies are taught at the level needed to read their behavior.
  • Distributed query planning is considered only through its added data-movement cost.

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 estimatesExpand

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

Code
rectangle "Aggregate\ncount by customer" as G
rectangle "Hash join\norders.customer_id = customer.id" as J
rectangle "Filter\nstatus = 'failed'" as F
rectangle "Index / table access\norders" as O
rectangle "Scan\ncustomer" as C
O --> F
F --> J
C --> J
J --> G
note right of J
Build one input; probe with
the other. Which side is small?
end note
Aggregatecount by customerHash joinorders.customer_id =customer.idFilterstatus = 'failed'Index / table accessordersScancustomerBuild one input; probe withthe other. Which side is small?

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?

HintExpand

A one-to-many join repeats the order fields once per matching line.

Worked solutionExpand

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

Proposition 3.3.1A first selectivity estimate

For a relation RR with ∣R∣|R| rows and a predicate with selectivity ss a simple estimate is ∣σp(R)∣≈s∣R∣|\sigma_p(R)| \approx s|R| For an equijoin, an independence-based first estimate is often ∣R⋈S∣≈∣R∣∣S∣/max⁡(V(R,a),V(S,a))|R \bowtie S| \approx |R||S|/\max(V(R,a), V(S,a)) where V(R,a)V(R,a) 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.

Estimated I/O cost as a function of predicate selectivity $s$. The unclustered index scan dominates for small $s$ but exceeds the full sequential table scan at the crossover threshold $s^* \approx 2.4\%$. Query execution cost model comparing sequential heap scan with unclustered index scan as selectivity varies, showing the crossover threshold at approximately 2.4 percent selectivity. s* ≈ 2.4% B=1000
Figure 3.3.1: Estimated I/O cost as a function of predicate selectivity ss. The unclustered index scan dominates for small ss but exceeds the full sequential table scan at the crossover threshold s∗≈2.4%s^* \approx 2.4\%.
Interactive exploration

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.

Sequential scan + hash join estimates 1,100 page I/Os. This model favors Clustered index selection + hash join instead.
Qualifying Orders pages50
Customers pages100
Index height3
Sequential scan + hash join1,100 I/OsSelected
Clustered index selection + hash join153 I/Os
Clustered index selection + nested loops5,053 I/Os

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.

Change selectivity; inspect the plan’s I/O model

With 1,000 Orders pages and a 5% filter, 50 clustered pages qualify. Compare the three candidate plans under the same stated assumptions.

Sequential scan + hash join1,100 I/Os
Clustered index selection + hash join153 I/Os
Clustered index selection + nested loops5,053 I/Os

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 choiceStrong caseDangerous assumptionObservable warning
Sequential scanhigh selectivity loss / most pages neededindex navigation is always fasterindex plan visits most heap pages randomly
Index scanfew qualifying rows, useful orderpredicate matches an index rangeactual rows approach table cardinality
Hash joinmodest build input, equality joinbuild fits memorybatches/spills or unexpectedly huge build
Merge joininputs ordered or cheap to sortorder cost is recovered laterboth inputs sort only for one join
Nested looptiny outer plus indexed innerouter cardinality is truly tinyprobes 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 solutionExpand

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 nn relations there are 2n2^n subsets, so dynamic programming avoids enumerating n!n! orders, but the retained plan is only as good as its cardinality estimates and cost model.

Worked search. Let AA have 100 rows, BB 1,000 rows, and CC 10 rows. Assume all relevant equality joins exist, ∣A⋈B∣=50|A \bowtie B|=50 ∣B⋈C∣=100|B \bowtie C|=100 and use the deliberately simplified cost ∣L∣+∣R∣|L|+|R| per hash join, with both inputs scanned once and all intermediate results fitting memory. Ignore output production, ordering, and access-path differences.

CandidateFirst intermediateFirst join costSecond join costTotal
(A⋈B)⋈C(A \bowtie B) \bowtie C50 rows1,100601,160
(B⋈C)⋈A(B \bowtie C) \bowtie A100 rows1,0102001,210
(A⋈C)⋈B(A \bowtie C) \bowtie Bunknown1101,000+∣A⋈C∣1,000+\lvert A\bowtie C\rvert1,110+∣A⋈C∣1,110+\lvert A\bowtie C\rvert

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 ∣A⋈C∣<50|A\bowtie C|<50 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

0 / 4 answered

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.

1
The execution degradation proves that the optimizer search engine lacks support for standard left-deep join tree enumeration.
2
This performance anomaly indicates the relational query is semantically ambiguous and must be converted into a UNION construct.
3
The cost model was applied to an input cardinality estimate that the actual data distribution severely contradicts.
4
Correlated predicates or data skew across tenant attributes can cause standard single-column statistics to misestimate selectivity.

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?

HintExpand

The missing fact is correlation, not arithmetic competence.

Worked solutionExpand

Global independence predicts about 0.01%0.01\% of rows, while the north subset predicts about 0.9%0.9\% 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.

Section Exercises

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

Verificationapplication

Referring to Proposition 3.3.1, explain why estimating ∣σA=a∧B=b(R)∣|\sigma_{A=a \land B=b}(R)| as sA⋅sB⋅∣R∣s_A \cdot s_B \cdot |R| fails severely when AA and BB are strongly correlated, and describe how extended multivariate statistics repair the calculation.

HintExpand

Multiplying independent probabilities understates joint selectivity when values co-occur.

Worked solutionExpand

The product rule sA⋅sBs_A \cdot s_B assumes statistical independence. If attribute AA implies or strongly concentrates attribute BB (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

Descriptionrecall

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%.

HintExpand

Compare sequential read throughput with random page lookup overhead.

Worked solutionExpand

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

Constructionapplication

Given relations AA (100 rows), BB (1,000 rows), and CC (10 rows), with ∣A⋈B∣=50|A \bowtie B| = 50 ∣B⋈C∣=100|B \bowtie C| = 100 and cost formula Cost(L⋈R)=∣L∣+∣R∣\text{Cost}(L \bowtie R) = |L| + |R| Calculate and compare the total join cost of plan (A⋈B)⋈C(A \bowtie B) \bowtie C versus (B⋈C)⋈A(B \bowtie C) \bowtie A

HintExpand

Sum the cost of the first join and the subsequent join on the intermediate result.

Worked solutionExpand
  1. Plan 1: First join A⋈BA \bowtie B has cost 100+1,000=1,100100 + 1{,}000 = 1{,}100 emitting 50 rows. Second join (A⋈B)⋈C(A \bowtie B) \bowtie C has cost 50+10=6050 + 10 = 60 Total cost = 1,100+60=1,1601{,}100 + 60 = 1{,}160
  2. Plan 2: First join B⋈CB \bowtie C has cost 1,000+10=1,0101{,}000 + 10 = 1{,}010 emitting 100 rows. Second join (B⋈C)⋈A(B \bowtie C) \bowtie A has cost 100+100=200100 + 100 = 200 Total cost = 1,010+200=1,2101{,}010 + 200 = 1{,}210 Plan 1 is cheaper by 50 units because its first join generates a smaller intermediate cardinality.

Exercise 3.3.4: Multivariate Statistics and Skewed Tenant Distribution Transfer

Generalisationtransfer

A multi-tenant database contains 10,000,000 orders where tenant 42 owns 80% of all orders and 90% of all failed orders. Standard planner histograms treat tenant_id and status as uniformly distributed and independent. Predict the planner’s access path choice under naive statistics versus observed execution, and propose the architectural resolution.

HintExpand

Contrast the cost of nested loops using index probes against hash joins under massive skew.

Worked solutionExpand

Under naive independence, the planner predicts 0.01×0.01×10,000,000=1,0000.01 \times 0.01 \times 10{,}000{,}000 = 1{,}000 rows, selecting a nested loop join with index lookup. In reality, tenant 42 generates over 7,000,000 rows, turning the index probe into an catastrophic loop of millions of random disk reads. The resolution is to collect multivariate tenant-frequency statistics (CREATE STATISTICS) or partition the relation by tenant so large tenants receive dedicated, accurate local statistics.

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