INFS2200 Chap.8 Query Optimisation and Selectivity
Query Optimisation and Selectivity
Optimisation rewrites equivalent expressions and chooses physical access with catalogue evidence. This chapter calculates selectivity and surviving rows, explains distinct-value and histogram estimates, and transforms canonical query trees through selection pushdown, join replacement, restrictive ordering and safe projection pushdown.
Three drills require the plan to change while the required relational result remains fixed.
Selectivity is the qualifying-row count divided by the relation size. A smaller fraction leaves fewer rows and therefore describes a more selective predicate. Distinct-value counts can support a uniform equality estimate, while histograms capture skew that a simple average misses.
Relation sizes, key declarations and index metadata complete the catalogue evidence used by the planner.
The rewrite sequence begins with a canonical expression. Local selections move toward their base relations, product plus equality becomes a join, restrictive joins are considered early, and lower projections retain every attribute needed above.
The chapter marks intermediate schemas so a plan never removes a join key while trying to reduce row width.
Estimates remain hypotheses. Stale statistics, skew and correlation can make actual row counts diverge from the plan. A useful diagnosis compares estimated and observed cardinality at each operator, finds the first large mismatch and improves the evidence.
Hints or forced plans are not the first response to misunderstood data distribution.
Join order matters because intermediate cardinality can grow far beyond either final input or output. Combining a tightly filtered relation with its matching partner early may constrain later work, but a small input is not automatically the best first join if it produces many matches.
Estimate each candidate intermediate using keys, distinct values and predicate evidence, then compare the physical algorithms available for that shape.
Predicate combination requires an explicit assumption. Multiplying selectivities treats conditions as independent; taking the smaller fraction may suit some containment cases, while disjoint conditions can produce no survivors.
Real attributes such as region and delivery method often correlate. Multicolumn statistics or a histogram can replace an implausible independence estimate, and actual execution counts reveal when the model needs that richer evidence.
Logical transformation and physical selection are separate decisions.
Selection pushdown changes an equivalent algebraic arrangement, while choosing an index scan, hash join or sort-merge join chooses how an operator runs. One logical tree can admit several physical plans. This distinction prevents a response from claiming that a valid rewrite alone determines the fastest algorithm without considering pages, memory or ordering.
Plan diagnosis follows a reproducible path.
Record estimated and actual rows at every node, identify the first divergence, inspect the statistic or constraint used there, and regenerate the plan after repairing evidence. Compare the new estimates before judging elapsed time. The purpose is not to force one favourite shape but to help the optimiser choose well as distributions and relation sizes change.
What this chapter covers
- 01
Cost-based and heuristic optimisation
- 02
Catalogue statistics
- 03
Selectivity and cardinality
- 04
Query-tree rewrite rules
- 05
Estimate error and plan repair
Worked example · free
Choose the more selective filter
- +1Compute 3,000 divided by 120,000.
- +1Compute 240 divided by 120,000.
- +1Choose the smaller surviving fraction.
- +1State the access-path boundary.
Key terms
- Selectivity
- The fraction of tuples that satisfy a condition.
- Cardinality
- A count of tuples or distinct values used in plan estimates.
- Histogram
- A catalogue summary of value distribution used to estimate skew.
- Projection pushdown
- Moving column reduction lower while retaining all attributes needed above.
Query Optimisation and Selectivity FAQ
Does a higher selectivity value filter more rows?
No. Under the course definition, selectivity is the surviving fraction. A smaller value leaves fewer rows and therefore represents a more selective condition. Write the survivor count beside the fraction to keep the direction clear.
Why do query estimates become inaccurate?
Statistics may be stale, values may be skewed, predicates may be correlated or the model may assume independence. Compare estimated and actual rows to identify where the mismatch begins, then improve the evidence rather than guessing at a new plan.
What is the safest optimisation sequence?
Build the canonical tree, push local selections down, replace product plus equality with joins, choose restrictive joins early and push projections only while preserving every required attribute. Verify equivalence before discussing the reduced work.
Exam move
Compute the selectivity fraction and surviving rows before discussing access. Rebuild query trees by one justified rule at a time, annotate schemas after projections and compare estimated with observed cardinality when a plan behaves unexpectedly. Create a small frequency table and calculate selectivity for a common value, a rare value and a key equality.
Predict which predicate should reduce the input most strongly, then state what index or clustering evidence could change the physical choice. For tree rewrites, label each node with estimated rows and surviving attributes. If actual execution disagrees, locate the first operator with a large estimate error and investigate statistics, skew or correlation. This method keeps optimisation evidence-led and preserves result meaning.