INFO20003 Chap.7 Query Processing and Join Costs
Query Processing and Join Costs
A declarative query becomes a physical tree of scans, filters, projections and joins. This chapter follows the path from parser and optimiser to executor, then compares join algorithms using page I/O. The main quantitative method labels relation pages, available buffers, usable outer-block capacity and the number of outer blocks before calculating repeated inner scans.
Pipelining and blocking behaviour add latency and materialisation considerations. Parsing checks the statement and resolves names; translation creates a logical representation; optimisation selects access paths, join orders and physical operators; execution requests tuples from the resulting tree. Iterator-style operators expose an open, next and close interface so a parent can pull rows from children.
A pipelined operator can pass a row upward without writing a complete intermediate, improving early response and reducing temporary storage. A blocking sort must consume its input before producing ordered output, while a hash join must at least build its hash table before probing. Those behaviours matter even when total I/O estimates are close.
Course cost models emphasise page transfers because they dominate simple in-memory comparisons under the stated abstraction. Page nested loops with R outer costs B(R) plus B(R) scans of S. Block nested loops reserves input and output buffers, typically making M minus two pages available for each outer block; its cost is B(R) plus the ceiling of B(R) divided by M minus two, multiplied by B(S).
The ceiling represents a partially filled final block that still causes a complete inner scan. Both orientations should be computed because changing the outer changes the block count. A two-pass hash estimate of three times the sum of the input pages represents partition and probe I/O only when the smaller partitions fit the memory assumption. Sort-merge feasibility likewise depends on run generation and merge fan-in.
Before ranking algorithms, rule out infeasible formulas or account for additional passes. Keep tuple counts, page counts, buffer pages, block counts and page I/Os as separate units. Sanity bounds help: a full-scan join reads each required input at least once, added buffers should not worsen block nested loops, and an index-assisted plan must state which scan it avoids.
Physical properties such as output order can also make a locally dearer operator valuable to a later grouping, merge or ORDER BY.
What this chapter covers
- 01
Parsing and compilation
- 02
Physical operators
- 03
Iterator execution
- 04
Pipelining
- 05
Blocking operators
- 06
Page nested loops
- 07
Block nested loops
- 08
Hash join
Worked example · free
Cost block nested loops
- 1Usable outer-block capacity is 100 pages.
- 1Outer blocks equal ceiling of 1,000 divided by 100, which is 10.
- 1Block nested loops costs 1,000 plus 10 times 20,000, or 201,000 I/Os.
- 1Hash estimate is three times 21,000, or 63,000 I/Os.
- 1Hash is cheaper when its partitioning assumptions hold.
Key terms
- Physical operator
- An executable algorithm implementing a logical relational operation.
- Iterator
- An operator interface through which parents request tuples from child operators.
- Pipelining
- Passing tuples between operators without materialising a complete intermediate result.
- Blocking operator
- An operator that must consume substantial input before returning output.
- Outer block
- The group of outer relation pages held in memory for one inner scan.
- Page I/O
- One transfer of a database page between storage and memory in the cost model.
Query Processing and Join Costs FAQ
Why must join feasibility be checked before cost?
Compact formulas assume enough memory for a stated number of passes or partitions. If a hash partition does not fit or a sort needs another merge pass, the printed estimate omits real I/O. State the memory condition, reject an infeasible candidate or add its extra passes, and only then rank algorithms.
Why does the course count page I/O?
Page transfers dominate the simplified cost comparison and provide a consistent unit across scans and joins. CPU, caching and network work still exist, but the model focuses on the principal cost needed for the taught calculations.
Why is the ceiling needed in block nested loops?
A partially filled final outer block still causes one complete inner scan. Rounding the block count down omits that scan and can understate the result by the full size of the inner relation.
Can the larger relation be the outer input?
It can, but the cost must be recomputed. Block nested loops repeats the inner scan once per outer block, so choosing the relation that yields fewer blocks often changes the total substantially.
Exam move
Write a unit beside every number before applying a formula. Practise converting tuples into pages and pages into outer blocks with the memory minus two rule. Recompute both outer choices for several relation sizes so the asymmetry is intuitive. Add a two-pass hash estimate only when the question permits its assumptions.
For conceptual questions, compare pipelining with materialisation by naming early output, memory pressure and temporary writes. Use sanity bounds: required inputs must be read, more buffers should not increase block nested loops cost, and a ceiling can only stay the same or raise the block count.
Working through Query Processing and Join Costs in INFO20003? Sia is AskSia’s AI Computer Science tutor — ask any INFO20003 Query Processing and Join Costs question and get a clear, step-by-step explanation grounded in how INFO20003 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.