INFO20003 Chap.8 Query Optimisation
Query Optimisation
Query optimisation chooses among equivalent execution plans using statistics and cost estimates. Selections and safe projections can move closer to base relations to shrink intermediates, while join ordering and access paths change physical work.
This chapter calculates reduction factors, converts estimated tuples into pages, explains dynamic plan enumeration and identifies rewrites that are illegal because a predicate needs attributes from both sides. Logical equivalence protects the answer while physical alternatives change how it is obtained.
Selections on one base relation can often move below joins, and projections can reduce tuple width, but only if every later predicate, join key and output attribute remains available. A predicate involving both inputs cannot be evaluated before those inputs meet. Rewrites around outer joins require additional care because moving a condition can change which unmatched tuples survive.
Cardinality estimates begin with table size, distinct-value counts, key information, null fractions and histograms. Under uniformity, equality on a value with V distinct values has an estimated selectivity near one over V; range selectivity depends on the represented interval and distribution. Independence permits multiplying selectivities, but correlated attributes such as suburb and postcode violate that assumption.
Join estimates use key and containment information when available and otherwise approximate matching across value domains. Convert tuples into pages using tuple width and usable page capacity before applying page-I/O formulas. Plan enumeration treats each relation subset as a state and extends connected subplans with another relation. Dynamic programming retains low-cost representatives rather than recomputing every join tree.
It may keep a more expensive representative with an interesting output order because that order can avoid a later sort or enable merge processing. Cartesian products are normally postponed when the query graph offers connected alternatives. Cost combines access, join and materialisation choices, so a cheaper intermediate cardinality is not the only useful property. Estimation error compounds through joins.
Compare estimated and actual rows at successive operators to find the first divergence, then distinguish stale statistics, skew, correlation and parameter-sensitive predicates. The optimiser does not prove the real runtime winner; it chooses the best estimated plan inside its search space and model.
A strong explanation therefore states each assumption, preserves units, applies logical bounds and describes how new statistics or physical properties could change the ranking.
What this chapter covers
- 01
Algebraic equivalence
- 02
Selection pushdown
- 03
Projection pushdown
- 04
Reduction factors
- 05
Cardinality estimation
- 06
Tuple to page conversion
- 07
Join order
- 08
Interesting orders
Worked example · free
Estimate two filters
- 1Equality reduction for five status values is 0.20.
- 1The selected total interval has width 500, giving reduction 0.25.
- 1Combined reduction is 0.20 times 0.25, or 0.05.
- 1Estimated output is 500,000 times 0.05, or 25,000 tuples.
Key terms
- Equivalence rule
- A transformation that preserves the relational result while changing expression shape.
- Selection pushdown
- Moving a base-specific filter closer to its relation to reduce later work.
- Cardinality estimate
- The predicted tuple count emitted by an operator under statistical assumptions.
- Interesting order
- An output ordering worth retaining because it can reduce later sort or join work.
- Plan enumeration
- The search over valid join orders, access paths and physical algorithms.
- Cartesian product
- The pairing of every tuple from one input with every tuple from another.
Query Optimisation FAQ
Why can the optimiser keep a locally dearer plan?
A plan may deliver an interesting order or partitioning that saves a later sort, enables merge processing or supports grouping. Dynamic programming therefore compares plans for the same relation subset together with useful physical properties, not cost alone. The global plan can be cheaper even when one retained intermediate is not.
Can every selection be pushed to one base relation?
No. A predicate referencing attributes from both inputs cannot be evaluated by either side alone. Attribute availability determines the lowest legal position; moving it farther would change the query's meaning.
Why convert estimated tuples to pages?
Physical I/O formulas consume page counts, not row counts. After estimating cardinality, divide by the applicable tuples-per-page capacity and take a ceiling before using the intermediate in a join cost.
Why keep a plan that is not locally cheapest?
It may deliver a useful ordering or physical property that avoids a later sort or enables a cheaper join. Optimisation compares complete downstream cost, not one operator in isolation.
Exam move
Practise a three-column ledger for every plan node: estimated tuples, estimated pages and physical cost. Derive each reduction factor from the stated domain, number of distinct values or key constraint, then record assumptions such as uniformity and independence. For rewrite questions, list which attributes a predicate needs before moving it. Sketch connected join orders and explain why a Cartesian branch is excluded.
Finally, check directions: filtering cannot increase cardinality, projections cannot create attributes, and a smaller intermediate should not become more pages unless tuple width changes and that change is stated.
Working through Query Optimisation in INFO20003? Sia is AskSia’s AI Computer Science tutor — ask any INFO20003 Query Optimisation 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.