Skip to content

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:

text
SQL statement
      ↓
query optimizer + catalog statistics
      ↓
estimated physical execution plan
      ↓
optional execution and actual measurements

The textbook gives representative commands from several systems:

Oracle ​

sql
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 ​

sql
EXPLAIN PLAN SELECTION
FOR SELECT ...;

Additional options control which explanation information is stored in the explain tables.

SQL Server ​

sql
SET SHOWPLAN_TEXT ON;
-- or SHOWPLAN_XML / SHOWPLAN_ALL

The selected form returns the plan as text, XML, or more detailed text.

PostgreSQL ​

sql
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:

|πList(R)|=|R|

For a single projected attribute with duplicate elimination:

|πADISTINCT(R)|=NDV(A,R)

For several attributes, an independence-based estimate is bounded by the input size:

|πA1,…,AkDISTINCT(R)|≈min(|R|,∏i=1kNDV(Ai,R))

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:

σc1(R)∩σc2(R)=σc1∧c2(R)σc1(R)∪σc2(R)=σc1∨c2(R)σc1(R)−σc2(R)=σc1∧¬c2(R)

The conjunction, disjunction, and negation selectivity formulas can then estimate the result. Without useful overlap statistics, safe upper bounds are:

|R∩S|≤min(|R|,|S|)|R∪S|≤|R|+|S||R−S|≤|R|

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 G, the expected number of output rows is the number of distinct group values:

|γG;f(A)(R)|=NDV(G,R)

An aggregate without GROUP BY produces one result row, including when its input is empty under normal SQL aggregate semantics:

|γf(A)(R)|=1

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 R with no match in S:

|RLEFT OUTER JOINS|=|R⋈S|+|RANTI-JOINS|

A full outer join additionally preserves unmatched rows from S:

|RFULL OUTER JOINS|=|R⋈S|+|RANTI-JOINS|+|SANTI-JOINR|

These formulas make the semi-join and anti-join estimates from Section 19.5.1 directly useful to outer-join costing.

OperationMain cardinality estimate
Projection without DISTINCT$
DISTINCT ANDV(A,R)
Intersection upper bound$\min(
Union upper bound$
Group by GNDV(G,R)
Left outer joinInner join + unmatched rows of R
Full outer joinInner 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.

text
first execution
SQL + parameters → parse → optimize → cache plan → execute

later execution
SQL + new parameters ───────────→ reuse plan → execute

This 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:

sql
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.

StrategyOptimization overheadRuntime adaptability
Reoptimize every executionHighHigh
Cache one generic planLowLow
Cache parameter-sensitive plansMediumMedium 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 k rows:

sql
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 k qualifying rows:

text
ordered index scan → test predicates → emit row
                         └────────────→ stop after k rows

This 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 k rows in a bounded priority queue. Its memory use is proportional to k, and its comparison cost is approximately:

O(nlog⁡k)

rather than the O(nlog⁡n) comparisons of a full comparison sort.

Threshold and predicate strategies ​

For some queries, the optimizer can derive an additional threshold predicate from the current kth-best value. Data that cannot improve the result is then skipped. Distributed and multi-source systems can similarly stop requesting input when the remaining sources cannot beat the current threshold.

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 k, ordering direction, predicate selectivity, available indexes, and whether ties must be returned all influence the best Top-k strategy.

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.

Built with ❤️ and curiosity