Query Processing & Optimization

The first step in processing a query is transforming the SQL string into a structured internal representation. The database parser builds an abstract syntax tree (AST) from the SQL text, then a binder resolves table and column names against the catalog (the system's metadata store). The result is a logical query plan — a tree of relational algebra operators.

Relational algebra gives us a closed set of operators over relations (tables):

• σ (select/filter): keeps rows matching a predicate. σ_{gpa > 3.8}(Students)
• π (project): keeps only specified columns. π_{name}(Students)
• ⋈ (join): combines rows from two relations matching a condition.
• γ (group-by/aggregate): groups rows and computes aggregate functions.
• δ (distinct): removes duplicate rows.
• τ (sort): orders rows.

The logical plan tree for SELECT s.name FROM Students s, Courses c WHERE s.sid = c.sid AND s.gpa > 3.8 would look like: π_{name} on top, then σ_{gpa>3.8}, then ⋈_{s.sid=c.sid}, then the two leaf scans of Students and Courses.

This logical plan is algebraically correct but says nothing about how to physically execute — it does not specify which join algorithm to use, which indexes to consult, or in what order. That is the optimizer's job. The separation between logical and physical plans is crucial: it lets the optimizer explore many physical implementations of the same logical computation.

-- SQL:
SELECT s.name
FROM Students s
JOIN Enrollments e ON s.sid = e.sid
WHERE s.gpa > 3.8;

-- Logical plan tree (pseudocode notation):
Project(name)
  Filter(gpa > 3.8)
    Join(s.sid = e.sid)
      Scan(Students)
      Scan(Enrollments)

The iterator model, introduced by Goetz Graefe in his 1994 Volcano paper, is the dominant execution model for query processing. Every operator in the plan tree implements a uniform three-method interface:

• open(): initialize the operator, recursively open children
• next(): produce the next output tuple (or EOF)
• close(): release resources, recursively close children

The root operator drives execution: the client calls root.next() repeatedly until EOF. Each call pulls a single tuple up through the tree — operators are lazy, computing only as much as needed to produce the next output.

Think of it like Unix pipes: cat file | grep pattern | sort | head -10. Each stage consumes from the stage below, one record at a time. The memory footprint is bounded by pipeline stages, not total data size.

The beauty of the iterator model is composability: any operator can sit below any other operator. Adding a new operator (say, a window function) requires only implementing the three-method interface. The rest of the system works automatically.

Pipelining vs. blocking operators: Most operators are pipelined — they produce output tuples one at a time as they receive input. But some operators are blocking (or pipeline breakers): they must consume their entire input before producing any output. Sort and hash-join build phases are classic examples. Blocking operators are important for memory planning: once you hit a blocker, you need enough memory to hold all the data at that point.

Modern columnar databases (DuckDB, MonetDB) use vectorized execution: instead of one tuple at a time, next() returns a vector of 1024–8192 tuples. This dramatically reduces function-call overhead and improves CPU cache behavior, often giving 10–100× speedups on analytical queries.

class Operator:
    def open(self): ...
    def next(self) -> tuple | None: ...
    def close(self): ...

class SeqScan(Operator):
    def open(self):
        self.page_iter = buffer_pool.scan(self.table)
        self.slot_iter = iter([])
    def next(self):
        while True:
            tup = next(self.slot_iter, None)
            if tup is not None:
                return tup
            page = next(self.page_iter, None)
            if page is None:
                return None  # EOF
            self.slot_iter = iter(page.tuples())
    def close(self):
        self.page_iter.close()

class Filter(Operator):
    def open(self):
        self.child.open()
    def next(self):
        while True:
            tup = self.child.next()
            if tup is None:
                return None
            if self.predicate(tup):
                return tup
    def close(self):
        self.child.close()

# Execution loop (client side):
root.open()
while (tup := root.next()) is not None:
    emit(tup)
root.close()

The simplest join algorithm tries every pair of tuples from the two relations. For each tuple r in the outer relation R, scan the entire inner relation S looking for tuples that satisfy the join predicate.

Simple NLJ: O(|R| × |S|) tuple comparisons. Catastrophically slow for large tables — if both relations have 1 million rows, that's 10^12 comparisons.

Page-oriented NLJ: Instead of iterating tuple-by-tuple, iterate page-by-page. For each page of R, load it, then for each page of S, try all pairs within those pages. Cost: B(R) + B(R)×B(S) I/Os, where B(T) is the number of pages in T. Still quadratic in pages.

Block NLJ (the key optimization): Use all available buffer memory! If you have B buffer pages, use B-2 pages as a block buffer for R, 1 page for S, 1 page for output. Cost becomes B(R) + ⌈B(R)/(B-2)⌉ × B(S). If R fits entirely in memory, the entire inner scan happens only once: cost = B(R) + B(S). This is why the smaller relation should always be the outer (in NLJ).

Index NLJ: If there is an index on the join attribute of S, instead of scanning all of S for each outer tuple, we can probe the index. Cost: B(R) + |R| × (index probe cost). For clustered indexes, the probe cost can be as low as a few I/Os. Index NLJ is often the optimizer's first choice when indexes exist.

When is NLJ the right choice? When one relation is very small (fits in a few pages), when an index exists on the inner relation, or when the join result is needed immediately (no blocking). NLJ is always correct and never requires a presort.

# Block Nested Loop Join
def block_nlj(R, S, predicate, buffer_pages):
    """R, S are iterators over pages of tuples.
       buffer_pages: total available buffer frames.
    """
    block_size = buffer_pages - 2  # 1 for S pages, 1 for output
    results = []
    r_block = []
    for r_page in R:
        r_block.extend(r_page)
        if len(r_block) >= block_size * PAGE_SIZE:
            for s_page in S:               # full scan of S per block
                for s_tuple in s_page:
                    for r_tuple in r_block:
                        if predicate(r_tuple, s_tuple):
                            results.append((r_tuple, s_tuple))
            r_block = []
            S.reset()  # restart S scan
    # handle last partial block
    if r_block:
        for s_page in S:
            for s_tuple in s_page:
                for r_tuple in r_block:
                    if predicate(r_tuple, s_tuple):
                        results.append((r_tuple, s_tuple))
    return results

Sort-merge join exploits sorted order to join two relations in O(N log N) time — dominated by the sort cost if the data is not already sorted. The insight: if both relations are sorted on the join key, you can merge them in a single linear pass, like merging two sorted lists.

Algorithm:

1. Sort phase: Sort R on the join attribute(s). Sort S on the join attribute(s). Use external merge sort if the relations don't fit in memory.
2. Merge phase: Use two pointers, one into sorted R and one into sorted S. Advance the pointer on the smaller key. When keys match, output all matching pairs.

Cost: 2×B(R)×(1 + ⌈log_{B-1}(⌈B(R)/B⌉)⌉) for external sort of R, similarly for S, plus B(R) + B(S) for the merge. Total is roughly 3×(B(R) + B(S)) if both fit in 2-pass sort.

Duplicates and the refinement: When there are many duplicates on the join key (e.g., a foreign key with many matching rows), the merge phase must emit the cross-product of all matching tuples. In the worst case (all keys equal) this degenerates to O(|R|×|S|). The optimizer must consider this when estimating cost.

When SMJ wins: When the data is already sorted on the join key (from a prior sort or an index scan in sorted order), the sort phase is free, and SMJ costs just B(R) + B(S). This happens naturally in pipelined plans where an earlier sort feeds into the join. SMJ also produces sorted output on the join key, which can eliminate a downstream sort — the optimizer's cost model should credit this.

Connection to external sort: External merge sort is a prerequisite here. In a B-buffer-page sort: (1) create ⌈N/B⌉ sorted runs; (2) repeatedly merge B-1 runs at a time until one sorted run remains. Number of passes: 1 + ⌈log_{B-1}(⌈N/B⌉)⌉.

def sort_merge_join(R, S, key):
    """In-memory version for clarity."""
    R_sorted = sorted(R, key=key)
    S_sorted = sorted(S, key=key)
    results = []
    i, j = 0, 0
    while i < len(R_sorted) and j < len(S_sorted):
        r_key = key(R_sorted[i])
        s_key = key(S_sorted[j])
        if r_key < s_key:
            i += 1
        elif r_key > s_key:
            j += 1
        else:
            # Emit cross-product of all matching tuples
            i0 = i
            while i < len(R_sorted) and key(R_sorted[i]) == r_key:
                j2 = j
                while j2 < len(S_sorted) and key(S_sorted[j2]) == r_key:
                    results.append((R_sorted[i], S_sorted[j2]))
                    j2 += 1
                i += 1
            j = j2  # advance S past this key group
    return results

Hash join is typically the fastest general-purpose join algorithm when no useful index or sort order exists. It runs in O(N) expected time using hashing.

Classic two-phase hash join:

Phase 1 — Build: Choose the smaller relation as the build side (say R). Scan R and insert every tuple into an in-memory hash table keyed on the join attribute. This is a blocking phase: it must complete before Phase 2 starts.

Phase 2 — Probe: Scan the larger relation S (the probe side) tuple by tuple. For each S tuple, probe the hash table for matching R tuples and emit all matches.

Cost: B(R) + B(S) I/Os (if R fits in memory). This is optimal — you read each relation exactly once.

Grace hash join (for relations that don't fit in memory):

1. Partition phase: Hash both R and S into B-1 partitions using hash function h1. Matching tuples must land in the same partition (same hash value → same partition). Write all partitions to disk. Cost: 2×(B(R) + B(S)) I/Os.
2. Join phase: For each partition pair (Ri, Si), load Ri into memory (build), probe with Si. Cost: B(R) + B(S) I/Os. Total: 3×(B(R) + B(S)) I/Os — same order as SMJ, but no sorting.

Requirement: Each partition must fit in memory during the join phase. Partition Ri ≤ B pages ⟹ B(R) ≤ B² (roughly). So with B buffer pages, hash join handles relations up to B² pages — which is enormous in practice (1000 buffer pages → 10^6 page tables).

Hash join vs. sort-merge: Hash join requires no order, generalizes trivially to equi-joins, and is often faster. SMJ is preferred when output must be sorted on the join key (avoiding a downstream sort), when data is already sorted, or when the join has inequality predicates (hash join only works for equi-joins).

Skew and the rehashing trick: If one partition is too large (data skew on the join key), recursively hash it with a different hash function. This is called recursive partitioning.

def hash_join(R, S, key):
    """Simple in-memory hash join."""
    # Build phase: hash R into a hash table
    ht = {}
    for r in R:
        k = key(r)
        ht.setdefault(k, []).append(r)
    
    # Probe phase: probe with S
    results = []
    for s in S:
        k = key(s)
        if k in ht:
            for r in ht[k]:
                results.append((r, s))
    return results

# Grace hash join partition phase (pseudocode)
def grace_partition(relation, key, n_partitions, hash_fn):
    partitions = [[] for _ in range(n_partitions)]
    for tup in relation:
        bucket = hash_fn(key(tup)) % n_partitions
        partitions[bucket].append(tup)
    return partitions  # write each to disk in real impl

A query optimizer's job is to find the best physical execution plan from an enormous space of alternatives. The search space has three dimensions:

1. Join order: For N tables, the number of distinct join trees is the Nth Catalan number — it grows faster than exponential. For N=10, there are over 17 million distinct join orderings. Exhaustive search is feasible up to N ≈ 10–12; above that, heuristics or randomized search (simulated annealing, genetic algorithms) are used.

2. Join algorithm: For each join in the plan, the optimizer can choose NLJ, SMJ, or hash join (and their variants). This multiplies the search space by a constant factor per join.

3. Access method: For each table scan, the optimizer can choose a sequential scan or any applicable index (B+ tree, hash index, bitmap index). Choosing the right access method is often the single most impactful decision.

The System R dynamic programming algorithm (Selinger et al., 1979) is the foundation of modern optimizers. It exploits the principle of optimality: an optimal plan for a k-table join must use optimal subplans for all sub-joins. This allows bottom-up DP:

• Start: for each single table, find the cheapest access method.
• Level 2: for each pair of tables, find the cheapest join of those two, given optimal single-table plans.
• Level k: for each k-table subset, find the cheapest join using optimal (k-1)-table subplans.

The DP table has 2^N entries (one per subset of tables). For N=10, that's 1024 entries — entirely manageable. For each entry, we store the cheapest plan and any interesting sort orders (sorted output that might eliminate downstream sorts).

Interesting orders are a crucial refinement: sometimes a slightly more expensive plan that produces sorted output is preferable because it eliminates a downstream sort operation. The optimizer must track not just the cheapest plan per subset, but the cheapest plan per interesting sort order.

Left-deep vs. bushy trees: System R only considered left-deep join trees (where the right child of every join is always a base table). Left-deep trees have the nice property that the inner relation of every NLJ is a base table (index-NLJ is applicable). Bushy trees (where subjoins can be inner inputs) are more general but complicate implementation. Most commercial optimizers explore some bushy trees.

# System R DP join enumeration (sketch)
def dp_join_order(tables, cost_model):
    n = len(tables)
    best = {}  # subset -> (cost, plan)
    
    # Base case: single tables
    for t in tables:
        best[frozenset([t])] = cost_model.best_access(t)
    
    # Build up from size 2 to n
    for size in range(2, n + 1):
        for subset in combinations(tables, size):
            s = frozenset(subset)
            best_cost = float('inf')
            for t in subset:
                rest = s - {t}
                if rest not in best:
                    continue
                left_plan = best[rest]
                # Try all join algorithms
                for algo in [NLJ, SMJ, HashJoin]:
                    cost = (left_plan.cost +
                            cost_model.join_cost(algo, left_plan, t))
                    if cost < best_cost:
                        best_cost = cost
                        best[s] = Plan(algo, left_plan, t, cost)
    return best[frozenset(tables)]

The optimizer compares plans by estimating their cost. The dominant cost metric in traditional databases is I/O cost — the number of disk page reads and writes — because disk I/O is orders of magnitude slower than CPU. Modern databases with SSDs and large RAM sometimes use CPU cost or a weighted combination, but the principles are the same.

Cost formulas for key operators:

Selectivity estimation: The most critical — and most uncertain — part of cost estimation is predicting how many tuples pass through each operator. For a predicate col = value, the selectivity (fraction of tuples matching) is estimated as 1/NDV(col), where NDV is the number of distinct values. This assumes uniform distribution, which is almost always wrong but tractable.

Histograms capture the actual distribution of column values. An equi-width histogram divides the value range into B buckets of equal width and counts tuples in each. An equi-depth histogram divides so each bucket contains the same number of tuples (better for skewed distributions). For range predicates, estimate by interpolating within the matching bucket(s).

Statistics collection: Statistics are collected by running ANALYZE (PostgreSQL) or UPDATE STATISTICS (SQL Server), which samples the table and computes column statistics. Statistics can become stale as data changes, leading to bad plan choices. Autovacuum/auto-analyze daemons refresh them periodically.

The independence assumption: When estimating selectivity for multiple predicates (e.g., age > 30 AND city = 'NYC'), the standard assumption is that predicates are independent: selectivity(A AND B) ≈ sel(A) × sel(B). This is often wrong (age and salary are correlated), leading to underestimation of result size and suboptimal plans. Multi-dimensional histograms and column-group statistics (PostgreSQL's CREATE STATISTICS) address this.

-- PostgreSQL: examine what the optimizer sees
EXPLAIN (ANALYZE, BUFFERS) 
SELECT s.name
FROM students s
JOIN enrollments e ON s.id = e.student_id
WHERE s.gpa > 3.8;

-- Sample output:
-- Hash Join  (cost=45.20..89.40 rows=120 width=32)
--            (actual time=1.2..3.4 rows=118 loops=1)
--   Hash Cond: (e.student_id = s.id)
--   Buffers: shared hit=42
--   ->  Seq Scan on enrollments e
--         (cost=0..31.0 rows=2100 width=8)
--         (actual rows=2100)
--   ->  Hash  (cost=38.00..38.00 rows=120 width=40)
--         Buckets: 1024  Batches: 1
--         ->  Seq Scan on students s
--               Filter: (gpa > 3.8)
--               Rows Removed by Filter: 880

Before the optimizer searches the physical plan space, it often applies logical rewrites — transformations that produce an equivalent logical plan that is structurally cheaper to execute. These rewrites are based on mathematical identities of relational algebra.

Key identities:

1. Predicate pushdown (most important): σ_{p}(R ⋈ S) ≡ σ_{p}(R) ⋈ S, when predicate p only references attributes of R. Push filters as close to the leaves (base table scans) as possible. This reduces the size of intermediate results.

2. Join commutativity: R ⋈ S ≡ S ⋈ R. The logical result is the same; physical cost differs.

3. Join associativity: (R ⋈ S) ⋈ T ≡ R ⋈ (S ⋈ T). Enables exploring different join orderings.

4. Projection pushdown: π_{A,B}(σ_{p}(R)) — push projections down to eliminate unneeded columns early, reducing tuple width and I/O.

5. Subquery unnesting: Correlated subqueries (queries referencing the outer query in a WHERE clause) are often rewritten as joins. SELECT x FROM R WHERE x.id IN (SELECT y.id FROM S WHERE ...) → JOIN-based plan.

6. Decorrelation of EXISTS/IN: Similar to above; converting correlated subqueries to semi-joins or anti-joins enables hash/SMJ strategies.

The optimizer's rule-based rewriter applies a fixed set of these transformations exhaustively (or until convergence) before the cost-based search begins. This is sometimes called the heuristic optimizer phase, or in modern systems, a cascade/Volcano-style rule application framework.

Why predicate pushdown is so powerful: If a filter eliminates 99% of rows, pushing it before a join means joining only 1% of the rows — a 10,000× reduction in join cost. Failing to push predicates is one of the most common causes of catastrophically slow queries.

-- Without predicate pushdown (bad):
SELECT s.name
FROM students s
JOIN enrollments e ON s.id = e.student_id
WHERE s.gpa > 3.8;
-- Naive plan: join ALL students with ALL enrollments, THEN filter
-- Cost: join of 10000 students × 50000 enrollments = 500M comparisons

-- With predicate pushdown (good):
-- Filter students FIRST, then join smaller intermediate result
-- Logical rewrite:
-- π_{name}( (σ_{gpa>3.8}(Students)) ⋈_{id=student_id} Enrollments )
-- σ applied before ⋈ reduces Students from 10000 to ~120 rows
-- Cost: 120 × 50000 = 6M comparisons (83× faster)

-- The optimizer does this automatically, but understanding it
-- helps you write queries that are easier to optimize:
SELECT s.name
FROM (
    SELECT id, name FROM students WHERE gpa > 3.8  -- push manually
) s
JOIN enrollments e ON s.id = e.student_id;

The optimizer's cost model is only as good as its estimates of cardinality — the number of tuples produced by each operator. Cardinality estimation is the hardest and most consequential part of query optimization; wrong estimates cascade through the plan tree and can cause the optimizer to choose plans that are orders of magnitude slower than optimal.

Statistics the database maintains per column:

• n_distinct (NDV): number of distinct values. Used for col = const selectivity: 1/NDV.
• null_frac: fraction of NULLs.
• avg_width: average byte width of values.
• correlation: statistical correlation between physical row order and column order (important for index scan cost).
• histogram_bounds: bucket boundaries for range selectivity.
• most_common_values (MCV): list of most frequent values and their frequencies. Critically important for skewed data (e.g., a status column with 90% 'active').

Selectivity formulas:

• col = const: use MCV if const is in the list; otherwise 1/NDV (uniform assumption)
• col > const: interpolate from histogram
• col BETWEEN a AND b: histogram interpolation
• col IS NULL: null_frac
• conjunction (AND): product of individual selectivities (independence assumption)
• disjunction (OR): inclusion-exclusion: sel(A) + sel(B) - sel(A)×sel(B)

Join cardinality estimation: For R ⋈_{R.a=S.b} S, the classic formula is: |R| × |S| / max(NDV(R.a), NDV(S.b)). This assumes the join key of the smaller NDV is a foreign key into the larger. It is wrong in many real scenarios.

Modern learned cardinality estimation: A major research area is replacing hand-crafted formulas with learned models — either query-driven (train on past query results) or data-driven (build joint distributions over columns). Systems like Naru, NeuroCard, and PostgreSQL's upcoming ML-based estimator show 100–1000× reduction in estimation error. This is an active frontier in database research.

-- PostgreSQL statistics inspection
SELECT
  attname,
  n_distinct,
  null_frac,
  avg_width,
  correlation
FROM pg_stats
WHERE tablename = 'students';

-- Force stats refresh:
ANALYZE students;

-- Create extended statistics for correlated columns:
CREATE STATISTICS students_age_salary
    ON age, salary
    FROM students;
-- Now the optimizer can estimate P(age>30 AND salary>100000)
-- using the joint distribution rather than independence assumption

-- Check histogram bounds:
SELECT histogram_bounds
FROM pg_stats
WHERE tablename='students' AND attname='gpa';
-- Result: {1.2,2.0,2.5,2.8,3.0,3.2,3.5,3.8,4.0}
-- 8 buckets, each covering ~12.5% of students

The optimizer's choice of access method for each base table scan is often the single most impactful decision in the entire plan. The main options are:

Sequential scan (SeqScan/TableScan): Reads every page of the table. Always applicable. Cost = B(T). Preferred when selectivity is high (many matching rows) — typically above 10–20% of the table.

Index scan (clustered B+ tree): A clustered (or primary) index stores rows in sorted order on the index key. For a range predicate, find the first matching key in the B+ tree (O(log N) cost), then scan sequentially through the leaf pages. Cost ≈ B(T) × selectivity + log(N). Preferred for low-to-moderate selectivity on the indexed column.

Index scan (unclustered B+ tree): A non-clustered (secondary) index stores pointers to rows but rows are not sorted by the index key. For each matching index entry, we may need a separate random I/O to fetch the row. Cost ≈ |T| × selectivity (up to one I/O per matching tuple). Only preferred for very low selectivity (<1–5%).

Bitmap index scan (PostgreSQL): A two-phase approach for unclustered indexes. Phase 1: scan the index and build a bitmap of matching page numbers. Phase 2: read only those pages (in sequential order). Avoids redundant I/Os when multiple index entries point to the same page. Extremely efficient for medium selectivity (1–20%). Also enables bitmap AND/OR: combine multiple bitmap indexes for multi-predicate queries.

Index-only scan: If all columns needed by the query are in the index (a covering index), no table page access is needed at all. Cost = pure index traversal cost. Creating covering indexes for hot queries is a key performance tuning technique.

The optimizer's access method decision depends on the estimated selectivity (from statistics), the page count of the table, buffer pool size (cached pages reduce I/O), and whether the index is clustered. The classic rule of thumb: clustered index scan beats sequential scan below ~30% selectivity; unclustered index scan only beats sequential scan below ~5–10% selectivity.

-- Demonstrate access method selection in PostgreSQL

-- Table with 1,000,000 rows, B+ tree index on gpa
CREATE INDEX idx_students_gpa ON students(gpa);

-- Very selective: index scan wins
EXPLAIN SELECT * FROM students WHERE gpa > 3.95;
-- -> Index Scan using idx_students_gpa on students
--    Index Cond: (gpa > 3.95)
--    (estimated 500 rows = 0.05% of table)

-- Low selectivity: sequential scan wins
EXPLAIN SELECT * FROM students WHERE gpa > 2.0;
-- -> Seq Scan on students
--    Filter: (gpa > 2.0)
--    (estimated 700,000 rows = 70% of table)

-- Covering index: index-only scan
CREATE INDEX idx_cover ON students(gpa) INCLUDE (name);
EXPLAIN SELECT name FROM students WHERE gpa > 3.9;
-- -> Index Only Scan using idx_cover on students
--    (no heap access needed — name is in the index)

Modern databases have pushed query optimization far beyond the Selinger DP model in two key directions: parallel execution and modern optimizer architectures.

Parallel query execution: Large analytical queries are parallelized across multiple CPU cores (intra-query parallelism). The plan tree is divided into pipeline fragments connected by exchange operators:

• Gather: a single thread collects results from N parallel workers.
• Repartition (redistribute): hash-partition data across N workers so matching join keys land on the same worker.
• Broadcast: replicate a small relation to all workers.

For a parallel hash join: partition both relations across N workers using the join key hash. Each worker independently builds/probes its local partition. Perfect linear scaling if data is not skewed.

The Cascades/Volcano optimizer framework (Graefe, 1995): Rather than separating logical and physical optimization into phases, Cascades uses a unified rule-based search. Logical equivalence rules (commutativity, associativity) and physical implementation rules (logical join → hash join / SMJ / NLJ) are applied together in a top-down, memoized search. Cascades uses a memo structure that compactly represents all equivalent plans explored so far. SQL Server's Query Optimizer, CockroachDB's optimizer, and many others are built on this framework.

Query rewrite and view merging: Before the optimizer searches for a plan, a rewrite phase handles subquery unnesting, view merging (inlining view definitions), common table expression (CTE) inlining, and predicate simplification. This is crucial for real SQL workloads that use many views and subqueries.

Adaptive query processing: Traditional optimizers commit to a plan before execution. Adaptive systems re-optimize mid-execution when estimates prove wrong. PostgreSQL 14+ uses adaptive join strategies; Orca (Greenplum) and some commercial systems perform full plan re-optimization at pipeline boundaries when cardinality deviates significantly from estimates.

-- Parallel query in PostgreSQL
SET max_parallel_workers_per_gather = 4;

EXPLAIN SELECT dept, AVG(salary)
FROM employees
GROUP BY dept;

-- Output (parallel plan):
-- Finalize HashAggregate
--   ->  Gather (workers=4)
--         ->  Partial HashAggregate  [each worker]
--               ->  Parallel Seq Scan on employees
-- 
-- Each worker scans 1/4 of the table, computes partial aggregates,
-- Gather collects them, Finalize combines partial results.
-- Wall time: ~4x faster than serial on 4 cores.

-- Exchange operator types (conceptual):
-- Broadcast join (small dimension table):
--   Hash Join
--     Broadcast(small_table) -> all workers get full copy
--     Parallel Scan(large_table) -> each worker scans a partition
-- Repartition join (both tables large):
--   Hash Join
--     Repartition(R, hash(R.key) % N) -> redistribute R
--     Repartition(S, hash(S.key) % N) -> redistribute S