INFS2200 Chap.7 Query Processing and Join Costs
Query Processing and Join Costs
Query processing carries declarative SQL through parsing, planning and execution. This chapter locates errors in the correct pipeline stage, compares nested-loop, indexed, hash and sort-merge access patterns, and applies the lecture sort-merge cost model with labelled assumptions.
Three practice cards distinguish semantic validity from physical efficiency and keep estimated model units separate from elapsed time.
The parser checks syntax, resolves catalogue names, verifies types and permissions, and forms an internal relational representation. Only then can the planner compare equivalent logical arrangements and physical algorithms.
The executor runs the selected operators through storage and buffer components. A missing column is therefore a parsing problem, while a poor cardinality estimate is a planning problem and slow page access is observed during execution.
Join algorithms differ by access pattern.
A nested loop repeatedly uses an inner input, an indexed variant turns those visits into targeted probes, a hash join builds and probes equality buckets, and sort-merge orders both inputs before advancing through matching keys.
Input size, indexes, ordering, memory and predicate type activate the choice.
The quantitative section applies the lecture relationship N(1 + log N) + M(1 + log M) and reports the result as model units. It states the logarithm base and input-order assumptions, then identifies which term dominates.
The estimate supports comparison; it is not silently relabelled as seconds or exact page reads.
A plain nested loop can be sensible when the outer input is tiny, even though its worst-looking formulation repeatedly scans the inner input. An index nested loop improves those visits only if the inner join key has a useful access path and the resulting row fetches are affordable.
The cost argument should therefore name which input is outer, how many probes occur and whether those probes reach clustered or scattered pages.
A hash join suits an equality condition because equal keys map to corresponding buckets. The build input is normally chosen to fit available memory; insufficient memory can partition work and add I/O.
A sort-merge join can exploit already ordered inputs and naturally advances through duplicate key groups, but otherwise pays for sorting. Range or inequality conditions require algorithms whose comparison behaviour actually supports them.
Pipelining and materialisation affect intermediates. A pipelined operator can pass tuples onward without writing the whole result, reducing delay and temporary storage.
Blocking operations such as a full sort must consume enough input before producing ordered output. Memory limits, reuse and operator dependencies decide whether an intermediate is streamed, buffered or written out, so logical row counts are only part of the execution story.
Cost formula answers must preserve their model boundary.
State whether N and M count tuples, blocks or another unit, identify the logarithm base if the exercise requires it, and compare like quantities. A model can rank alternatives under shared assumptions without predicting wall-clock time. After execution, observed pages, rows and time become evidence for revisiting the estimates rather than retroactively changing the formula's units.
What this chapter covers
- 01
SQL parsing and semantic checks
- 02
Internal relational form
- 03
Query execution plans
- 04
Physical join algorithms
- 05
Sort-merge cost and estimation
Worked example · free
Cost a sort-merge join
- +1State the logarithm base and input sizes.
- +1Compute the first input term.
- +1Compute the second input term.
- +1Add in model units.
- +1Interpret which input dominates.
Key terms
- Query processing
- The path from SQL validation through planning and physical execution.
- Query execution plan
- The chosen physical operator sequence for a query.
- Nested-loop join
- A join that tests inner access for tuples from an outer input.
- Sort-merge join
- A join that orders inputs on the key and merges matching runs.
Query Processing and Join Costs FAQ
What happens before query optimisation?
The DBMS parses the statement, resolves names, checks types and permissions, and forms an internal relational representation. Plan comparison requires a valid query meaning first. A physical access path cannot repair an unresolved or unauthorised reference.
When can an index nested loop work well?
It can be attractive when the filtered outer input is small and the inner relation has a useful index on the join key, making each inner access a targeted probe. Clustering and cache behaviour still affect the observed cost.
What does the sort-merge cost formula measure?
It is a comparative model for sorting both inputs and merging them. Unless a question defines physical units, the calculated value should not be reported as seconds or exact block reads. State the logarithm base and ordering assumptions.
Exam move
Draw the processing pipeline, then practise one join decision per session. State input sizes, access structures and model assumptions. Keep semantic errors at parsing separate from cost choices at planning and observed resource use during execution. Build a comparison card for nested loop, indexed nested loop, hash and sort-merge that records predicate type, required structure and dominant cost.
For numeric work, calculate each input term on a separate line and label the result as model units. Then change the larger input after a safe selection and recompute the effect. Finish by naming the catalogue statistic or index evidence a planner would need. This keeps algorithms connected to the actual plan conditions rather than memorised rankings.