Additional Issues Related to Query Optimization
Cost formulas and join ordering form the core of query optimization, but a practical optimizer must also expose its decisions, estimate the sizes of many other relational operations, reuse plans safely, and exploit queries that need only a small prefix of their result.
19.7.1 Displaying the System's Query Execution Plan
Most commercial DBMSs provide an explain plan facility. It exposes the plan selected by the optimizer so that a database administrator or developer can inspect:
- table scans and index access paths;
- join order and join algorithms;
- estimated cardinality and cost at each operator;
- sorting, grouping, materialization, and parallel operators;
- predicates applied by each operator.
The general interaction is:
SQL statement
↓
query optimizer + catalog statistics
↓
estimated physical execution plan
↓
optional execution and actual measurementsThe textbook gives representative commands from several systems:
Oracle
EXPLAIN PLAN FOR
SELECT ...;The plan is written to PLAN_TABLE and can then be queried or displayed through the system's plan-display utilities.
IBM Db2
EXPLAIN PLAN SELECTION
FOR SELECT ...;Additional options control which explanation information is stored in the explain tables.
SQL Server
SET SHOWPLAN_TEXT ON;
-- or SHOWPLAN_XML / SHOWPLAN_ALLThe selected form returns the plan as text, XML, or more detailed text.
PostgreSQL
EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
SELECT ...;Options such as COSTS, BUFFERS, and TIMING control the reported information. ANALYZE executes the statement and reports measurements rather than showing estimates alone.
Estimated plan versus actual execution
A plain explain normally reports the optimizer's predictions. An execution-enabled form can run the query and report actual rows and timing, and therefore may change data when applied to INSERT, UPDATE, or DELETE. Syntax and behavior are DBMS- and version-specific.
The most useful diagnostic is often the difference between estimated and actual cardinality. A large difference can reveal stale statistics, skew, correlated predicates, or an assumption of uniform distribution that does not match the data.
19.7.2 Size Estimation of Other Operations
The optimizer needs the output cardinality of every operator because that result becomes an input to its parent. In addition to SELECT and JOIN, common estimates are needed for projection, set operations, aggregation, and outer joins.
Projection
SQL normally preserves duplicates. A projection without DISTINCT therefore changes row width but not row count:
For a single projected attribute with duplicate elimination:
For several attributes, an independence-based estimate is bounded by the input size:
Correlation among the projected attributes can make the product estimate inaccurate.
Projection can still reduce I/O even when it does not reduce cardinality. Narrower records increase the blocking factor, so the same number of rows may occupy fewer blocks.
Set Operations
When both inputs are selections over the same relation, equivalence rules can reduce set operations to predicate estimation:
The conjunction, disjunction, and negation selectivity formulas can then estimate the result. Without useful overlap statistics, safe upper bounds are:
These bounds do not say how much the inputs actually overlap; histograms or multicolumn statistics can give better estimates.
Aggregation and Grouping
For grouping on attribute
An aggregate without GROUP BY produces one result row, including when its input is empty under normal SQL aggregate semantics:
For multiple grouping attributes, the optimizer can use the bounded product estimate used for multicolumn DISTINCT, unless it has joint statistics.
Outer Joins
An inner join contributes all matching pairs. A left outer join also preserves the rows of
A full outer join additionally preserves unmatched rows from
These formulas make the semi-join and anti-join estimates from Section 19.5.1 directly useful to outer-join costing.
| Operation | Main cardinality estimate |
|---|---|
Projection without DISTINCT | $ |
DISTINCT A | |
| Intersection upper bound | $\min( |
| Union upper bound | $ |
| Group by | |
| Left outer join | Inner join + unmatched rows of |
| Full outer join | Inner join + unmatched rows from both inputs |
19.7.3 Plan Caching
Applications often submit the same statement repeatedly with different parameter values. Optimizing it from scratch every time wastes CPU and increases response time. With plan caching, the DBMS stores a compiled plan and reuses it for later executions of the same parameterized statement.
first execution
SQL + parameters → parse → optimize → cache plan → execute
later execution
SQL + new parameters ───────────→ reuse plan → executeThis works well for predictable point lookups, such as retrieving a bank account by its account number. The same index plan is likely to remain appropriate across parameter values.
The difficulty is that different values can have very different selectivities. Consider:
SELECT *
FROM ORDERS
WHERE order_date BETWEEN :start_date AND :end_date;A one-day range may favor an index, whereas a five-year range may favor a table scan. Reusing a plan optimized for the first parameter set can be expensive for later values.
Parametric query optimization addresses this problem by retaining several plans for different parameter regions. At execution time, the DBMS compares the actual parameters with those regions and selects the cheapest applicable cached plan.
| Strategy | Optimization overhead | Runtime adaptability |
|---|---|---|
| Reoptimize every execution | High | High |
| Cache one generic plan | Low | Low |
| Cache parameter-sensitive plans | Medium | Medium to high |
A cached plan may also need invalidation after schema changes, index changes, or sufficiently large changes in statistics. Plan reuse is therefore a tradeoff between compilation cost and sensitivity to the current data and parameters.
19.7.4 Top-k Results Optimization
Some queries conceptually produce a large ordered result even though the user needs only the first
SELECT product_id, revenue
FROM PRODUCT_SALES
ORDER BY revenue DESC
FETCH FIRST 10 ROWS ONLY;The naive plan computes every qualifying row, sorts the entire result, and discards everything after the first 10. Top-k optimization tries to avoid work that cannot affect the requested prefix.
Ordered access with early termination
If an index supplies the required order, the executor can scan it from the appropriate end and stop after finding
ordered index scan → test predicates → emit row
└────────────→ stop after k rowsThis can avoid both a full scan and an explicit sort.
Bounded Top-k heap
When no useful ordering exists, the executor can scan the input while retaining only the best
rather than the
Threshold and predicate strategies
For some queries, the optimizer can derive an additional threshold predicate from the current
Top-k is more than output truncation
A row limit improves execution only when the physical plan can exploit it. If all rows must still be aggregated, deduplicated, or inspected before the order is known, the optimizer may not be able to stop early.
The value of
Summary
- Explain-plan facilities make optimizer decisions visible, while execution-enabled variants compare estimates with actual behavior.
- Cardinality estimation extends beyond selection and join to projection, set operations, grouping, and outer joins.
- Plan caching reduces repeated optimization work but can choose poorly when parameter selectivity varies.
- Parametric optimization retains different plans for different parameter regions.
- Top-k optimization uses ordering, bounded memory, and early termination to avoid producing and sorting an unnecessary full result.