Course contents
On this page
Lesson plan 15: Physical operators
Trace scans, joins, sorting, and aggregation through their physical state and output behavior.
Placement: Part 3: Turning requests into execution.
Prerequisites: Lesson 14: Logical optimization, plus the earlier dependency chain.
Learning outcomes
- Trace scans, joins, sorting, and aggregation through their physical state and output behavior.
- Calculate memory requirements and external passes when data exceeds a budget.
- Choose among nested-loop, hash, and merge strategies using cardinality, ordering, skew, and spill costs.
- Separate a general mechanism, a documented implementation choice, and an illustrative numerical assumption.
Teaching sequence
- Establish the motivating situation: A hash join’s build side grows beyond its memory budget and must partition to disk.
- Introduce the vocabulary and the correctness obligation before an optimization. Define scans, nested-loop joins, hash joins.
- Develop the mechanism: Trace operator state, cardinality, blocking behavior, memory ownership, and external execution.
- Follow the complete worked example: A 1 GiB input and 64 MiB memory creates 16 initial sort runs before merge overhead. Explain the assumptions, intermediate units, and limiting interpretation.
- Extend the scenario to changed load, skew, or failure, explaining merge joins, sorting, aggregation, spilling.
- Connect the mechanism to a documented implementation and an alternative with a different workload fit. Close by stating the remaining cost and the next lesson dependency.
Required chapter material
Use a complete execution trace or worked calculation, supported by an annotated static diagram or table. Include language-neutral pseudocode or labeled SQL when it clarifies the mechanism. State preconditions, ownership, visibility, and failure boundaries for algorithms. Describe operational costs as well as the normal path. All questions raised in the narrative must be resolved in the text.
Visual explanation
A hash-join build/probe diagram and an external-sort run diagram identify retained memory, temporary files, and reread work. The accompanying prose explains the arrows, state changes, or table entries so the lesson remains understandable in a plain Markdown reader.
Editorial checks
Confirm that the numerical example agrees with its units and assumptions. Check that a faster path preserves the stated contract, or explicitly identify the changed guarantee. Keep hypothetical figures separate from product measurements. Explain both an appropriate use and a limitation of the case design. Check terminology against the glossary and links against the course index.