Query Optimization and Execution

When you run a SQL query, the database does not simply execute it as written. It evaluates millions of possible execution strategies and picks the fastest one.

This chapter covers how the query optimizer works, join algorithms, execution plans, and how to read EXPLAIN output to tune queries.

---

Learning Objectives

After completing this chapter, you will be able to:

• Describe the query processing pipeline.
• Understand how the optimizer works.
• Compare join algorithms and their use cases.
• Read and interpret EXPLAIN plans.
• Understand cost-based vs rule-based optimization.
• Use indexes and statistics for query tuning.
• Answer optimization interview questions.

---

Query Processing Pipeline

Every SQL query goes through this pipeline:

SQL Query
    ↓
Parser (syntax check, parse tree)
    ↓
Preprocessor (semantic check, view expansion)
    ↓
Query Optimizer (multiple plans, cost estimation)
    ↓
Execution Plan (chosen plan)
    ↓
Query Executor (run the plan, return results)

---

Step 1: Parsing

The parser checks the SQL for syntax errors and converts it into a parse tree.

SELECT e.Name, d.Dept_Name
FROM Employees e
JOIN Departments d ON e.Dept_ID = d.Dept_ID
WHERE e.Salary > 50000;

The parser identifies:

• SELECT clause: e.Name, d.Dept_Name
• FROM clause: Employees (alias e), Departments (alias d)
• JOIN condition: e.Dept_ID = d.Dept_ID
• WHERE condition: e.Salary > 50000

---

Step 2: Preprocessing

The preprocessor:

• Resolves table and column names against the catalog.
• Expands views (the view’s defining query replaces the view name).
• Performs semantic checks (do all referenced columns exist?).

---

Step 3: Optimization

The optimizer generates multiple execution plans and picks the cheapest one.

Logical vs Physical Plans

Plan Type	Description
Logical	Relational algebra operators (σ, π, ⋈) — order of operations, no implementation details
Physical	Concrete algorithms (hash join, index scan, sort-merge)

Optimization Techniques

• Join reordering: The optimizer tries different join orders (e.g., join the smaller table first).
• Predicate pushdown: Filter as early as possible to reduce data early in the pipeline.
• Index selection: Choose between index scan and full table scan based on selectivity.
• Join algorithm selection: Pick the best join method (nested loop, hash, sort-merge).
• Materialization decision: Whether to materialize intermediate results.

---

Join Algorithms

How the database actually performs a join.

Nested Loop Join

For each row R in outer table:
    For each row S in inner table:
        If R.key = S.key → output combined row

Complexity

O(N × M) — but with an index on the inner table, becomes O(N × log M).

When to Use

• One table is small (the outer table).
• The inner table has a highly selective index.
• Nested loop is the only option for non-equi joins (θ-joins).

---

Hash Join

1. Build phase: Scan the smaller table, create a hash table on the join key.
2. Probe phase: Scan the larger table, look up each row in the hash table.

Complexity

O(N + M) — linear.

When to Use

• Joining large tables with no useful indexes.
• The smaller table fits in memory.
• Equi-joins only.

---

Sort-Merge Join

1. Sort both tables on the join key.
2. Merge: walk through both sorted lists simultaneously, matching keys.

Complexity

O(N log N + M log M + N + M) — dominated by sort cost.

When to Use

• Both tables are already sorted on the join key (e.g., from a previous operation or an index scan).
• Range joins or inequality conditions (<, >, BETWEEN).
• The data is too large for a hash table.

---

Join Algorithm Comparison

Algorithm	Complexity	Use Case
Nested Loop	O(N × M)	Small outer table, indexed inner table
Hash Join	O(N + M)	Large tables, equi-join, no index
Sort-Merge	O(N log N + M log M)	Already sorted, range joins

---

Cost-Based Optimization (CBO)

The optimizer estimates the cost of each plan and chooses the cheapest.

Cost Components

Component	Unit	Example
CPU cost	Processing time	Evaluating WHERE conditions
I/O cost	Disk reads/writes	Reading pages from disk
Memory cost	Buffer pool usage	Hash table size for hash join
Network cost	Data transfer (distributed)	Moving data between nodes

Statistics Used by the Optimizer

-- PostgreSQL
ANALYZE users;

-- Statistics collected:
SELECT tablename, attname, null_frac, n_distinct, most_common_vals
FROM pg_stats WHERE tablename = 'users';

Statistic	What It Tells
Row count	Table size
Null fraction	How many rows have NULL in a column
Distinct count	How many unique values
Most common values	Value distribution (histogram)
Correlation	How ordered the data is (for index scans)

---

Cardinality Estimation

The optimizer estimates how many rows each operation will return.

Example

SELECT * FROM Users WHERE City = 'Mumbai';

• Total rows: 1,000,000
• Distinct cities: 50
• Estimated rows: 1,000,000 / 50 = 20,000

Problems with Estimation

Issue	Impact
Outdated statistics	Optimizer picks wrong plan
Correlated columns	WHERE City = 'Mumbai' AND Status = 'Active' — assumes independence
Complex predicates	WHERE function(column) = value — cannot estimate selectivity

---

Reading EXPLAIN Plans

EXPLAIN ANALYZE
SELECT e.Name, d.Dept_Name
FROM Employees e
JOIN Departments d ON e.Dept_ID = d.Dept_ID
WHERE e.Salary > 50000;

PostgreSQL Output

Hash Join  (cost=12.34..45.67 rows=100 width=68)
  Hash Cond: (e.dept_id = d.dept_id)
  → Seq Scan on employees e  (cost=0.00..30.00 rows=500 width=36)
        Filter: (salary > 50000)
  → Hash  (cost=10.00..10.00 rows=200 width=36)
        → Seq Scan on departments d  (cost=0.00..10.00 rows=200 width=36)

Reading the Output

Part	Meaning
Hash Join	The join algorithm used
cost=12.34..45.67	Estimated cost (startup..total)
rows=100	Estimated output rows
width=68	Estimated row width in bytes
Seq Scan	Full table scan (no index used)
Filter	WHERE condition applied during scan

---

Common Optimizations

1. Index for WHERE Clauses

-- Slow: seq scan on 1M rows
EXPLAIN SELECT * FROM Users WHERE Email = 'test@mail.com';
-- Seq Scan (cost=0.00..15000.00 rows=1 width=100)

-- Fast: index scan
CREATE INDEX idx_email ON Users (Email);
EXPLAIN SELECT * FROM Users WHERE Email = 'test@mail.com';
-- Index Scan using idx_email (cost=0.42..8.44 rows=1 width=100)

2. Covering Indexes

CREATE INDEX idx_covering ON Users (City) INCLUDE (Name, Email);

SELECT Name, Email FROM Users WHERE City = 'Mumbai';
-- Index Only Scan (no table access needed)

3. Reduce Columns in SELECT

-- Slow: Fetching all columns
SELECT * FROM Orders WHERE Customer_ID = 101;

-- Faster: Only needed columns
SELECT Order_ID, Amount FROM Orders WHERE Customer_ID = 101;

4. Avoid Functions in WHERE

-- Bad: Function prevents index use
SELECT * FROM Orders WHERE YEAR(Order_Date) = 2024;

-- Good: Range query uses index
SELECT * FROM Orders WHERE Order_Date >= '2024-01-01' AND Order_Date < '2025-01-01';

---

Interview Deep Dive

---

Key Takeaways

• The query pipeline: Parser → Preprocessor → Optimizer → Executor.
• The optimizer generates many plans and picks the cheapest using cost estimates.
• Join algorithms: Nested Loop (small + indexed), Hash Join (large + equi), Sort-Merge (sorted data).
• Cost-based optimization uses table statistics (row count, distinct values, histograms).
• Outdated statistics lead to poor query performance.
• Use EXPLAIN to understand execution plans and identify bottlenecks.
• Indexes speed up WHERE clauses; covering indexes eliminate table access.
• Avoid wrapping indexed columns in functions inside WHERE.
• A sequential scan can be faster than an index scan for queries returning many rows.