Unit 4.5 · about 6 h
261 / 324Sorting, join algorithms and query plans
Assume Programming's indexes-query-plans unit. The next step is explaining join algorithms, blocking operators and repeated work inside the engine, not deriving another sequential scan or repeating its index-locality lab.
- derive
- measure
You can now
- Derive nested-loop, external-sort and partitioned-hash work with explicit buffer and spill assumptions.
- Read join, sort and aggregation nodes as a physical execution tree.
- Compare equivalent plans using actual rows, loops and buffer accesses without confusing cache reads with device I/O.
Covers
- Sorting, join algorithms and aggregation execution
- Query plans, logical work, physical work and cost drivers
Study, in this order
4 steps
- Lecture 11: Sorting & Aggregation AlgorithmsCMU 15-445/645 - database and storage core
Sections 1-3, pp. 1-3: plans, external merge sort and sorted versus hashed aggregation
- Lecture 12: Joins AlgorithmsCMU 15-445/645 - database and storage core
Sections 2-5, pp. 1-4: join output, nested loops, sort-merge and hash joins
Depth · Stop before section 6's hypothetical timing comparison. Use page-transfer models with their assumptions; those examples are not measurements on your machine.
- Planning: equivalence and statisticsCMU 15-445/645 - database and storage core
Lecture 15 notes, sections 2 and 4-6, pp. 1-4; Lecture 16 notes, sections 2-3, pp. 1-5
Depth · Skip the enumeration algorithms. Focus on logical rewrites, cardinality estimates and cost assumptions.
- PostgreSQL 18: Using EXPLAINPostgreSQL - EXPLAIN and transaction isolation lab
14.1.1 join examples; 14.1.2 actual rows, loops, sort/hash statistics and
BUFFERS; 14.1.3 Caveats
Focus on
- Block nested loops rescan the inner input per outer chunk; an indexed nested loop probes per outer tuple. A hash join builds a table and checks collisions; skew can force extra spill passes.
- External sorting forms runs then merges them. Sorting and hashing can both implement
GROUP BY; hashing need not produce key order. - Estimated cost is not milliseconds. Actual rows are per-loop averages; parent costs and buffer totals include children, so summing the whole tree double-counts work.
- A shared-buffer read can be served by the OS cache. Report logical accesses and observed buffer misses separately from physical device work; stock EXPLAIN does not prove cold NVMe reads.
Reproduce closed-book
First derive block nested-loop cost \(M+\left\lceil M/(B-2)\right\rceil\cdot N\) for \(M=1000\) outer pages, \(N=500\) inner pages and \(B=102\) frames: 6000 input-page transfers. One-level Grace hash join costs \(3(M+N)=4500\) if partitions fit, with uniform partitioning, no extra pass and output writes excluded. Then use the section PostgreSQL setup:
CREATE TABLE r AS SELECT i AS k FROM generate_series(1,1000) i; CREATE TABLE s AS SELECT i%1000+1 AS k FROM generate_series(1,10000) i; CREATE INDEX ON s(k); ANALYZE r; ANALYZE s. Set jit=off, max_parallel_workers_per_gather=0 and work_mem='4MB'. For SELECT count(*) FROM r JOIN s USING(k), save EXPLAIN (ANALYZE,BUFFERS,TIMING OFF,SUMMARY OFF) with exactly one of enable_hashjoin, enable_mergejoin, enable_nestloop on and the other two off. Each query counts 10000 joined pairs. Record the chosen operators, per-loop rows, loops, shared hits/reads and any spills; flags discourage alternatives, so inspect rather than assume. Run each plan once to warm it, then save three repetitions. Record lscpu, uname -r, SELECT version(), psql --version and all settings; report cache state as warmed, not guaranteed cold. No timing or memory value is a target.Traps
- Calling the hash formula universal. Recursive partitioning, skew, cached input and output materialization change the cost.
- Calling an
Index Only Scanheap-free without checkingHeap Fetchesand visibility state. - Reading a merge input's emitted row count as distinct base rows. Duplicate-key rescans can emit the same row repeatedly.
Practice
The section mini-project covers this: a join/filter/aggregation evidence table, one justified index change, boundary-result tests, and warm-cache plan comparisons with recorded data sizes, statistics, settings and versions.
Self-test
-
Where do the three reads/writes in \(3(M+N)\) come from?
Read both inputs and write their partitions, then read those partitions for build/probe. This excludes result writes and assumes no repartitioning. -
An inner node reports
actual rows=10,loops=1000. How many rows did it emit in total?10000, subject to display rounding. The row count is an average per loop. -
Why can smaller
work_memincrease physical work without changing the result?A sort or hash operation may spill and perform extra transfers. Its logical semantics remain the same. -
For 1000 pages and 102 sort buffers, how many passes does materialized external merge sort need?
Two: form \(\left\lceil1000/102\right\rceil=10\) runs, then merge them using at most 101 inputs. Reading and writing every page each pass costs 4000 transfers; a pipelined final output can change that accounting.
Completion criterion
Stop when
All three executions return the same count, your evidence reconciles rows with loops, and you explain a plan difference without asserting an unmeasured speedup or device-read count.
Mark passed, then open 4.6 Only mark this when you can do it without notes.Leads to
- 6.5 Queue bounds, first saturation and open-loop load Relate operator work and spill to service saturation.
Comes after
- 4.1 Relational model, relational algebra and SQL joinsChoose physical operators for the same logical result.
- 4.4 Hash indexes, B-trees, selectivity and range scansUse index probes and ordering as inputs to join algorithms.
Resources for this unit
- CMU 15-445/645 - database and storage core Use Fall 2025 Lectures 1-9, 11-18 and 20-22 with their notes: relational model, SQL, storage, buffer pools, layouts, indexes, execution, planning, concurrency, MVCC, logging and recovery. Complete the matching SQL, Storage, Indexes and Filters, Transactions and Recovery homeworks before considering a BusTub project.
- PostgreSQL - EXPLAIN and transaction isolation lab Create one normalized schema, joins, an aggregation and a window query. Compare EXPLAIN ANALYZE before and after one justified index. In two sessions, reproduce one documented isolation anomaly and prevent it with a stated database or application invariant.
Also in this section
- Designing Data-Intensive Applications, 2nd edition - storage and transactions Read only the sections on data models and query languages, storage and retrieval, encoding and evolution, and transactions that answer a live design question from the CMU route. Write one comparison table covering layout, index, isolation and recovery trade-offs.
- Operating Systems: Three Easy Pieces - persistence and integrity Use Chapters 36, 39-45 to trace devices, filesystem structures, journaling, log-structured storage, flash and integrity. Apply the crash sequence to your own append-only store rather than repeating the SYS-1 file experiment.
- CMU 15-445 - one reduced BusTub project slice If a C++ database implementation is the chosen depth lane, complete Project 1 Buffer Pool Manager or Project 2 Database Index, not both during the first pass. Follow the course publication rules and keep code private. The blank-file append-only store remains the core checkpoint.
- Point-in-time joins Read Point-in-time joins and Retrieving features as of the event time. Separate event-time eligibility from actual feature availability; implement the predicates in SQL, not a Feast installation.
- CMU Lecture 19: Timestamp Ordering Concurrency Control Section 1 only, p. 1: timestamp order as a chosen serialization order. The section pool omits Lecture 19; this fills the timestamp-ordering vocabulary gap without assigning all of OCC.
- SQLite Write-Ahead Logging Sections 1 and 3 only: rollback journaling remains the default and WAL is an opt-in mode. Correct the dated SQLite statement in CMU Lecture 21; inspect the bundled engine without running concurrent WAL writers.