SQL operates as a declarative language, meaning users specify the desired results rather than the execution method. The database management system must transform SQL statements into executable query plans. Since different execution strategies can vary in efficiency by orders of magnitude—comparing Simple Nested Loop Join against Hash Join reveals differences like 1.3 hours versus 0.45 seconds—the DBMS requires mechanisms to identify optimal execution strategies. This responsibility falls to the Query Optimizer.

The Query Optimizer originated in IBM System R, challenging the contemporary belief that human-specified query plans would always outperform system-generated ones. Many principles from System R's optimizer remain relevant in modern database systems.

SQL Query Processing Pipeline

A SQL statement traverses through Parser, Binder, Planner, Optimizer, and Executors stages. After parsing, the binder resolves identifiers to concrete entities, the planner generates an initial query plan, the optimizer refines it, and finally the executor constructs an operator execution tree.

Parser Stage

The parser transforms raw SQL text into an Abstract Syntax Tree (AST). Since parsing is neither a core database component nor a performance bottleneck, most systems utilize third-party libraries. BusTub employs libpg_query for this transformation.

Binder Stage

The binder traverses the AST and resolves all identifiers into unambiguous entities, consulting the catalog to map table names to concrete objects and expanding wildcards into explicit column lists.

EXPLAIN (binder) SELECT * FROM sample_table;
=== BINDER ===
BoundSelect {
  table=BoundBaseTableRef { table=sample_table, oid=0 },
  columns=[sample_table.colA, sample_table.colB],
  groupBy=[],
  having=,
  where=,
  limit=,
  offset=,
  order_by=[],
  is_distinct=false,
}

Planner Stage

The planner converts the bound semantic tree into a logical execution plan. Various plan node types exist (Scan, Join, Projection), each representing operations in the execution tree. Data flows bottom-up from leaf nodes toward the root, where results emerge.

Optimizer Stage

The optimizer transforms the initial query plan into an optimized physical execution plan through two primary approaches:

1. Rule-based Optimization: Applies hardcoded transformation rules without examining actual data content. Examples include merging Limit with Sort into TopN, predicate pushdown, projection pushdown, and column pruning.
2. Cost-based Optimization: Estimates and compares costs across multiple equivalent plans, selecting the minimum-cost alternative. This approach requires statistical models to predict costs of different execution strategies.

The BusTub optimizer implements rule-based optimization, sequentially applying transformation rules to produce the final plan. Typically, planners generate Logical Plan Nodes representing abstract operations, while optimizers produce Physical Plan Nodes specifying concrete execution methods. For instance, a logical Join node becomes HashJoin or NestedIndexJoin in the physical plan.

Executor Stage

After optimization, the system generates executors by traversing the plan tree and replacing each PlanNode with its corresponding Executor implementation.

Query Rewriting Techniques

Two relational algebra expressions are equivalent if they produce identical tuple sets. DBMS applies heuristics and rules to transform expressions into lower-cost equivalents.

Predicate Pushdown

Predicates typically exhibit high selectivity, filtering substantial data portions. Pushing predicates toward the plan's base enables early filtering. Key principles include:

• Filter data as early as possible
• Reorder predicates to place highly selective ones first
• Decompose complex predicates for independent pushdown (e.g., transforming X=Y AND Y=3 into X=3 AND Y=3)

Projection Pushdown

In row-store databases, eliminating unused columns early reduces intermediate result sizes. This technique is less applicable to column-store architectures.

Subquery Optimization

DBMS treats nested subqueries in WHERE clauses as functions accepting parameters and returning values. Two optimization strategies exist:

1. Rewrite queries by decorrelating or flattening nested subqueries
2. Decompose complex queries into blocks, processing each sequentially and storing intermediate results in temporary tables

Additional Rewriting Rules

• Split join predicates and replace Cartesian products with joins
• Eliminate impossible or redundant predicates
• Merge compatible predicates
• Remove unnecessary joins through heuristic analysis

Cost-based Query Optimization

Operations like joins—commutative and associative—generate vast numbers of equivalent expressions, requiring cost estimation to select optimal configurations.

Cost Estimation Factors

Query duration depends on CPU cycles, disk block transfers, memory consumption, and network messages. Fundamentally, cost correlates with tuple throughput. DBMS maintains statistics including tuple counts, distinct value counts per attribute, and value ranges to enable cost prediction.

Selection Statistics

Statistical estimation relies on assumptions: uniform data distribution, predicate independence, and join key overlap. For any table R, DBMS tracks:

• N_R: total tuple count
• V(A, R): distinct values for attribute A
• A_max, A_min: attribute value boundaries

Selection cardinality SC(A, R) = N_R / V(A, R) represents average records per value under uniformity assumptions.

Selectivity Calculations

Equality Predicate:

SELECT * FROM users WHERE age = 25;

Selectivity = 1 / V(age, users)

Range Predicate:

SELECT * FROM users WHERE age >= 25;

Selectivity = (A_max - value) / (A_max - A_min)

Negation:

Selectivity = 1 - sel(original_predicate)

Conjunction (assuming independence):

sel(P1 AND P2) = sel(P1) × sel(P2)

Disjunction:

sel(P1 OR P2) = sel(P1) + sel(P2) - sel(P1) × sel(P2)

Join Size Estimation

For join attribute A shared between tables R and S (non-primary key):

Estimated size ≈ N_R × N_S / max(V(A, R), V(A, S))

Advanced Statistics

Real data violates idealized assumptions. Modern DBMS employs:

Histograms

Equi-width histograms partition values into buckets with equal value ranges. Equi-depth histograms maintain approximately equal counts per bucket, better capturing skewed distributions.

Sketches

Probabilistic data structures provide approximate statistics:

• Count-Min Sketch: estimates element frequencies
• HyperLogLog: approximates distinct element counts

Sampling

Maintaining small table subsets enables selectivity estimation without full scans. DBMS refreshes samples when underlying data changes significantly.

Query Optimization Strategies

Single-Relation Plans

Key decisions include access method selection (sequential scan, binary search on clustered indexes, index scan) and predicate ordering. OLTP queries typically exhibit search argumentable patterns with obvious index choices and foreign key joins.

Multi-Relation Plans

Join order possibilities grow rapidly with table count. Two search approaches exist:

Bottom-up (System R approach)

Begins with base tables, incrementally constructing plans through dynamic programming. Generates logical operators for query blocks, enumerates physical implementations, and constructs left-deep trees minimizing estimated work.

Top-down (Volcano approach)

Starts from desired output, performing branch-and-bound search through the plan space while tracking the globally optimal plan. Physical properties like sort order receive first-class treatment during optimization.

Nested Subquery Handling

Strategies include query rewriting through decorrelation and block-oriented decomposition with temporary result materialization.