Introduction

SQL describes the result an application needs, but it usually does not prescribe every physical step the database must use to produce that result.

The database query optimizer examines the query, schema, indexes, constraints, and statistics. It then selects an execution strategy containing operations such as scans, seeks, joins, filters, sorts, and aggregations.

This strategy is represented by a query execution plan, also called a query plan or execution plan.

A query plan can show:

• The order in which tables are accessed
• Whether tables or indexes are scanned or searched
• The join methods selected
• The join order
• Where filters are evaluated
• How rows are sorted and grouped
• Estimated row counts
• Actual row counts when runtime information is collected
• Estimated operator costs
• Memory requirements
• Warnings, spills, lookups, or parallel operations

In your System Design curriculum, Query Plans is Topic 5.8 under Relational Data Modeling & SQL. It follows B-tree and composite indexes and precedes connection pools.

Prerequisites

What Is a Query Plan?

A query plan is a tree of physical operators the database uses to execute a SQL statement.

SQL statement
      |
      v
Parse and validate
      |
      v
Transform into logical operations
      |
      v
Evaluate candidate physical strategies
      |
      v
Choose an execution plan
      |
      v
Execute plan operators
      |
      v
Return result

The plan can specify table-access methods, join algorithms, filtering, aggregation, sorting, and data movement.

Query-processing Stages

Terminology differs between database systems, but query processing commonly involves several stages.

Query Optimizer

The query optimizer is the database component responsible for selecting an execution plan.

Optimizer inputs can include:

• The SQL query
• Tables and columns
• Available indexes
• Primary, foreign, and unique constraints
• Column and index statistics
• Data types and collations
• Query parameters
• Database configuration
• Available memory and processor resources

The optimizer considers alternative physical plans and selects one according to its cost model and search strategy.

Logical vs Physical Operations

SELECT
    o.order_number,
    c.display_name
FROM orders AS o
INNER JOIN customers AS c
    ON c.customer_id = o.customer_id;

The SQL specifies a logical inner join. The optimizer selects a suitable physical join algorithm.

Cost-based Optimization

A cost-based optimizer estimates the resources required by candidate plans.

Cost considerations can include:

• Estimated rows
• Data-page access
• CPU work
• Memory use
• Sort work
• Join work
• Parallel execution
• Repeated row lookups

Cost values are optimizer-specific estimates. A displayed cost is not necessarily elapsed time in milliseconds or a directly portable measurement between plans, servers, or database systems.

Cardinality Estimation

Cardinality estimation predicts how many rows an operator will produce.

Table rows:

1,000,000


Predicate:

order_status = 'cancelled'


Estimated matching rows:

10,000


Estimated selectivity:

1%

The estimated cardinality influences access paths, join order, join algorithm, memory allocation, and parallelism.

A simplified selectivity expression is:

\[ Selectivity = \frac{MatchingRows}{TotalRows} \]

Estimated vs Actual Plans

An actual execution plan does not necessarily mean that every displayed value is actual. Cost values and some properties can remain estimates, while row counts, executions, timing, warnings, and memory information can include runtime evidence depending on the platform.

EXPLAIN

Many database systems provide an EXPLAIN command for obtaining a planned execution strategy.

EXPLAIN
SELECT
    order_id,
    order_status,
    ordered_at
FROM orders
WHERE tenant_id = :tenant_id
  AND customer_id = :customer_id
ORDER BY
    ordered_at DESC;

Syntax and output differ between databases. Some systems support additional options for runtime statistics, buffer usage, formatting, or plan analysis.

Reading an Execution-plan Tree

A plan is commonly represented as a tree. Parent operators consume rows produced by child operators.

SELECT result
      |
      v
Sort
      |
      v
Nested-loop join
      |
      +-- Customer index seek
      |
      +-- Order index seek

Graphical plans can be displayed in different reading directions. Follow the arrows and operator relationships shown by the selected database tool.

Important Operator Information

For each meaningful operator, inspect:

• Physical operation
• Logical operation
• Object being accessed
• Predicate
• Estimated rows
• Actual rows where available
• Number of executions
• Rows read or examined
• Output columns
• Estimated or actual memory usage
• Warnings
• Parallel execution properties

Table and Index Scans

A scan examines a broader portion of a table or index.

Table scan:

Read table pages
Evaluate predicate
Return matching rows


Index scan:

Read index entries
Evaluate predicate
Return or locate matching rows

A scan can be appropriate when:

• The table is small
• The query needs a large percentage of its rows
• No suitable index exists
• The index contains all required columns
• Ordered index access avoids other work

Index Seek

An index seek navigates to a qualifying key or key range.

SELECT
    customer_id,
    display_name
FROM customers
WHERE customer_number = :customer_number;

CREATE UNIQUE INDEX ix_customers_number
ON customers
(
    customer_number
);

A seek can still process many rows when the requested range is broad. The word “seek” alone does not prove that the query is efficient.

Seek Predicates and Residual Predicates

An index operation can use one condition to navigate the index and another condition to filter rows afterward.

CREATE INDEX ix_orders_tenant_date
ON orders
(
    tenant_id,
    ordered_at
);

SELECT
    order_id
FROM orders
WHERE tenant_id = :tenant_id
  AND ordered_at >= :start_time
  AND order_status = 'pending';

The tenant and date conditions can define the index range. The status condition can remain as a residual filter when status is not part of a suitable index key.

Inspect:

• Rows retrieved from the index
• Rows removed by the residual predicate
• Rows finally returned

Key or Row Lookups

A secondary index can identify matching rows but lack columns required by the query. The database can then perform additional lookups against the underlying table or clustered structure.

Secondary index seek
        |
        v
Matching index entries
        |
        v
Lookup table row for additional columns
        |
        v
Return complete result

A few lookups can be efficient. Thousands or millions of repeated lookups can become expensive.

Lookup Example

SELECT
    order_id,
    order_status,
    total_amount,
    shipping_address
FROM orders
WHERE customer_id = :customer_id;

An index containing only customer_id and the row locator can require additional retrieval for status, total, and address.

Possible responses include:

• Accept the lookups when few rows are returned
• Reduce the selected columns
• Add carefully chosen included columns where supported
• Use a different index
• Change the access pattern

Join Operators

A query plan can use different physical algorithms to implement a logical join.

• Nested-loop join
• Hash join
• Merge join

The best algorithm depends on input sizes, indexes, ordering, predicates, memory, and estimated cardinalities.

Nested-loop Join

A nested-loop join processes rows from one input and searches the other input for matches.

Outer input row 1
      |
      +--> Find matching inner rows

Outer input row 2
      |
      +--> Find matching inner rows

Outer input row 3
      |
      +--> Find matching inner rows

A nested-loop join is commonly suitable when:

• The outer input is small
• The inner input has an efficient indexed lookup
• The query returns a relatively small result

It can become expensive when the outer input is much larger than estimated and the inner lookup executes repeatedly.

Hash Join

A hash join builds a hash structure from one input and probes it with rows from another input.

Build input
      |
      v
Create hash structure
      |
      v
Probe with other input
      |
      v
Return matching rows

A hash join can be suitable when:

• Larger inputs are joined
• The join uses equality conditions
• Useful input ordering is unavailable
• An indexed nested-loop strategy would require many lookups

Hash joins can require significant memory. Insufficient memory can cause additional temporary-storage work.

Merge Join

A merge join consumes inputs ordered by compatible join keys.

Ordered input A
        \
         \ 
          --> Merge matching keys --> Result
         /
        /
Ordered input B

A merge join can be suitable when:

• Both inputs are already ordered compatibly
• Large input sets are joined
• The join condition supports ordered comparison

If the inputs are not already ordered, the cost of sorting them can reduce the benefit.

Join-strategy Comparison

Sort Operator

A sort operator orders rows for an ORDER BY, merge operation, window function, grouping strategy, or another plan requirement.

SELECT
    order_id,
    ordered_at
FROM orders
WHERE customer_id = :customer_id
ORDER BY
    ordered_at DESC,
    order_id DESC;

A compatible composite index can sometimes provide the requested order:

CREATE INDEX ix_orders_customer_date_id
ON orders
(
    customer_id,
    ordered_at DESC,
    order_id DESC
);

A sort is not automatically inefficient. Its impact depends on row count, row width, memory, and whether it spills to temporary storage.

Aggregation Operators

The database can implement GROUP BY and aggregate calculations using different physical strategies.

Hash Aggregate

Input rows
    |
    v
Hash by grouping key
    |
    v
Maintain aggregate state
    |
    v
Return groups

Stream Aggregate

Input ordered by grouping key
        |
        v
Accumulate consecutive group
        |
        v
Return one result per group

A stream-based aggregation can benefit from appropriately ordered input. A hash-based aggregation can process unordered data but can require more memory.

Filter Operator

A filter operator removes rows that do not satisfy a predicate.

Rows read:

100,000


Rows passing filter:

100


Observation:

The plan examined far more rows
than the query returned.

A large gap between rows read and rows returned can indicate a missing or poorly ordered index, a non-sargable predicate, an implicit conversion, or a deliberately broad access pattern.

Compute-scalar Operations

Compute operations evaluate expressions such as arithmetic, conversions, conditional expressions, or generated output values.

SELECT
    quantity * unit_price
        AS line_amount
FROM order_lines
WHERE order_id = :order_id;

A scalar calculation is not automatically expensive. Its impact depends on complexity and the number of rows on which it is evaluated.

Spool or Temporary-work Operators

Some optimizers temporarily store intermediate rows so they can be reused, protected, or processed again.

Child operator produces rows
        |
        v
Temporary stored result
        |
        +--> Reused by one branch
        |
        +--> Reused by another branch

A temporary spool can be beneficial when it avoids repeatedly performing expensive work. It can also indicate repeated consumption, missing access paths, or a need for protection required by the plan.

Parallelism

Some databases can divide query work among several workers.

Large input
    |
    v
Distribute work
    |
    +-- Worker 1
    +-- Worker 2
    +-- Worker 3
    +-- Worker 4
    |
    v
Combine results

Parallelism can reduce elapsed time for suitable workloads, but it consumes additional worker and coordination resources. A parallel plan is not automatically better than a serial plan.

Memory Grants

Sorts, hash joins, and hash aggregations can request execution memory.

Estimated rows and row width
        |
        v
Optimizer estimates memory need
        |
        v
Memory grant requested
        |
        +--> Sufficient:
        |       perform operation in memory
        |
        +--> Insufficient:
                write temporary data
                to database work storage

Underestimated rows can produce a grant that is too small and cause a spill. Overestimated rows can reserve more memory than necessary and reduce concurrency.

Spills

A spill occurs when an operator such as a sort or hash operation cannot complete within its available execution memory and uses temporary storage.

Possible causes include:

• Underestimated cardinality
• Wide rows
• Large input sets
• Memory pressure
• Unsuitable join or aggregation choice
• Missing filtering opportunities

Do not respond to every spill by increasing memory. First investigate the query, estimates, predicates, indexes, statistics, and workload.

Estimated vs Actual Rows

Comparing estimated and actual rows is one of the most useful plan-analysis techniques.

A mismatch is a diagnostic clue, not a complete diagnosis. Determine why the estimate was inaccurate.

Statistics

Database statistics summarize data distribution and help the optimizer estimate cardinality.

Statistics can describe:

• Approximate row counts
• Distinct-value counts
• Value distribution
• Null frequency
• Key density
• Relationships between selected indexed values

Stale or insufficient statistics can produce inaccurate estimates and unsuitable plans.

Data Skew

Data skew occurs when values are distributed unevenly.

Order status distribution:

completed:
8,000,000 rows

pending:
25,000 rows

failed:
2,000 rows

One plan can be suitable for a rare status and unsuitable for a very common status.

Parameter-sensitive Plans

A cached plan selected using one parameter pattern can perform poorly for another parameter pattern.

SELECT
    order_id,
    ordered_at
FROM orders
WHERE tenant_id = :tenant_id
  AND order_status = :status;

Tenant A:

100 orders


Tenant B:

50,000,000 orders


Same SQL shape:

Potentially different efficient access strategy

Parameter sensitivity should be confirmed using plan and runtime evidence. Available remedies are database-specific and should be selected carefully.

Plan Caching and Reuse

Database systems can cache execution plans and reuse them for subsequent executions.

Query submitted
      |
      v
Find reusable cached plan
      |
      +--> Found:
      |       execute cached plan
      |
      +--> Not found:
              compile or optimize plan
              cache where applicable
              execute plan

Plan reuse reduces compilation work. However, schema changes, statistics updates, configuration changes, memory pressure, parameter issues, or database-specific invalidation rules can trigger a new plan.

Sargable Predicates

A sargable predicate allows the database to use an indexed value as a search argument.

SELECT
    order_id
FROM orders
WHERE DATE(ordered_at) = :order_date;

SELECT
    order_id
FROM orders
WHERE ordered_at >= :day_start
  AND ordered_at < :next_day_start;

Compare the plans and examined rows rather than assuming that every function prevents index use on every database.

Implicit Conversions

When compared values have incompatible types, the database can introduce an implicit conversion.

Indexed column:

customer_number VARCHAR


Parameter:

Integer


Potential result:

Conversion appears in the plan
and index navigation becomes less efficient.

Match application parameter types with database column types and inspect plan warnings or scalar expressions.

SELECT * and Row Width

SELECT
    *
FROM orders
WHERE customer_id = :customer_id;

SELECT
    order_id,
    order_number,
    order_status,
    ordered_at
FROM orders
WHERE customer_id = :customer_id;

Wider rows can increase data access, transfer, memory consumption, lookup cost, sorting cost, and client-processing work.

Pagination Plans

Deep offset pagination can require the database to process and discard many preceding rows.

SELECT
    order_id,
    ordered_at
FROM orders
ORDER BY
    ordered_at DESC,
    order_id DESC
LIMIT 20
OFFSET 100000;

Cursor or keyset pagination can navigate from a known ordered position:

SELECT
    order_id,
    ordered_at
FROM orders
WHERE
    ordered_at < :cursor_ordered_at
    OR
    (
        ordered_at = :cursor_ordered_at
        AND order_id < :cursor_order_id
    )
ORDER BY
    ordered_at DESC,
    order_id DESC
LIMIT 20;

Compare actual rows processed, reads, duration, and plan operations for both strategies using representative data.

Missing-index Suggestions

Some platforms can display index suggestions in execution plans.

Treat a suggestion as a candidate for analysis, not an automatic production instruction.

Before creating a suggested index, review:

• Whether a similar index already exists
• Composite column order
• Included-column width
• Write frequency
• Storage impact
• Other queries using the table
• Business uniqueness requirements
• Whether query rewriting solves the issue

Index Hints and Plan Forcing

Some databases allow index hints, join hints, or forced plans. These can override part of the optimizer's normal decision process.

Query-plan Analysis Workflow

1. Capture the exact slow query and parameter types.
2. Confirm the database, schema, and environment.
3. Record execution duration and returned rows.
4. Capture the estimated plan.
5. Capture runtime plan evidence safely where appropriate.
6. Identify large scans, repeated lookups, joins, sorts, and spills.
7. Compare estimated and actual rows.
8. Inspect predicates and implicit conversions.
9. Inspect statistics and data skew.
10. Review available indexes and composite column order.
11. Check selected columns, pagination, and query shape.
12. Make one justified change.
13. Capture the new plan and measurements.
14. Measure write and concurrency impact.
15. Retain evidence for regression testing.

Worked Example

Original Query

SELECT
    o.order_id,
    o.order_number,
    o.order_status,
    o.ordered_at,
    c.display_name
FROM orders AS o
INNER JOIN customers AS c
    ON c.customer_id = o.customer_id
WHERE
    o.tenant_id = :tenant_id
    AND o.order_status = :status
    AND DATE(o.ordered_at) = :order_date
ORDER BY
    o.ordered_at DESC;

Possible Plan Evidence

Observed plan characteristics:

- Large orders scan
- Function applied to ordered_at
- Many rows filtered after reading
- Explicit sort
- Customer lookup repeated for every matching order

Query Rewrite

SELECT
    o.order_id,
    o.order_number,
    o.order_status,
    o.ordered_at,
    c.display_name
FROM orders AS o
INNER JOIN customers AS c
    ON c.customer_id = o.customer_id
WHERE
    o.tenant_id = :tenant_id
    AND o.order_status = :status
    AND o.ordered_at >= :day_start
    AND o.ordered_at < :next_day_start
ORDER BY
    o.ordered_at DESC;

Candidate Index

CREATE INDEX ix_orders_tenant_status_date_customer
ON orders
(
    tenant_id,
    order_status,
    ordered_at DESC,
    customer_id
);

Required Validation

• Compare the old and new plans
• Compare rows read with rows returned
• Check whether the sort remains
• Check join and lookup execution counts
• Measure runtime with representative parameters
• Measure index-maintenance impact on writes

Query Plans and Production Safety

Plan investigation can impose load on a production database. Runtime plan collection can execute expensive statements or add monitoring overhead.

Use:

• Approved diagnostic procedures
• Representative lower environments where possible
• Read-only reproduction when appropriate
• Bounded query timeouts
• Controlled parameter values
• Redaction of sensitive literals and plans
• Change-management and rollback procedures

Execution plans can contain object names, predicates, parameter values, or other sensitive metadata. Store and share them according to the applicable data-handling policy.

Query-performance Observability

Useful metrics include:

• Execution count
• Average and high-percentile duration
• CPU time
• Logical and physical reads
• Rows returned
• Rows examined
• Temporary-storage usage
• Memory-grant size
• Spill count
• Compilation count
• Plan changes
• Lock-wait time
• Timeout count
• Parameter-sensitive regressions

Common Query-plan Mistakes

Recommended Test Cases

Query-plan Best Practices

Practice Exercise

Analyze and optimize query plans for the online learning platform developed in the previous lessons.

Requirements

1. Create representative learners, courses, enrollments, lessons, quizzes, and attempts.
2. Query one learner's active enrollments.
3. Query one course's learner roster.
4. Query recent quiz attempts using cursor pagination.
5. Query learners requiring inactivity reminders.
6. Capture estimated plans before adding indexes.
7. Capture safe runtime plan evidence.
8. Compare estimated and actual rows.
9. Identify scans, seeks, lookups, joins, sorts, and filters.
10. Identify one non-sargable predicate.
11. Rewrite the predicate.
12. Add one justified composite index.
13. Capture the new plan.
14. Measure read and write performance.
15. Document whether the change should be retained.

Practice Query

SELECT
    e.enrollment_id,
    e.enrollment_status,
    e.completion_percentage,
    c.course_title,
    e.enrolled_at
FROM enrollments AS e
INNER JOIN courses AS c
    ON c.course_id = e.course_id
WHERE
    e.tenant_id = :tenant_id
    AND e.learner_id = :learner_id
    AND e.enrollment_status = 'active'
ORDER BY
    e.enrolled_at DESC,
    e.enrollment_id DESC;

Candidate Index

CREATE INDEX ix_enrollments_tenant_learner_status_date_id
ON enrollments
(
    tenant_id,
    learner_id,
    enrollment_status,
    enrolled_at DESC,
    enrollment_id DESC
);

Capture and compare plan evidence before deciding whether the index is appropriate. Also verify whether the existing uniqueness and foreign-key indexes overlap with the candidate.

Plan-review Template

Frequently Asked Questions