Query Processing & Optimization

When you run a SQL query, it isn’t just “executed.” It goes through a high-precision pipeline to find the most efficient way to get your data.

The difference between a good query plan and a bad one can be 1000x in execution time.

---

Learning Objectives

After completing this chapter, you will be able to:

• Describe the query processing pipeline.
• Understand how the query optimizer works.
• Compare join algorithms and their use cases.
• Differentiate between rule-based and cost-based optimization.
• Understand how statistics and histograms guide optimization.
• Answer interview questions on query optimization.

---

The Query Processing Pipeline

SQL Query
    │
    ▼
┌─────────────┐
│   Parser    │  → Check syntax, build parse tree
└─────────────┘
    │
    ▼
┌─────────────┐
│ Translator  │  → Convert to Relational Algebra
└─────────────┘
    │
    ▼
┌─────────────┐
│  Optimizer  │  → Generate & evaluate plans (THE KEY STEP)
└─────────────┘
    │
    ▼
┌─────────────┐
│ Evaluation  │  → Execute the chosen plan
│   Engine    │
└─────────────┘
    │
    ▼
   Results

---

Step 1: Parsing & Translation

The SQL query is:

1. Parsed — checked for syntax errors
2. Validated — checked against schema (tables/columns exist)
3. Translated — converted into Relational Algebra (internal representation)

Example:

SELECT Name FROM Students WHERE Age > 20;

becomes:

π Name (σ Age > 20 (Students))

---

Step 2: Query Optimization

The “Brain” of the DBMS. The optimizer considers many equivalent Relational Algebra expressions and picks the cheapest one.

Rule-Based Optimization (RBO)

Follows fixed heuristic rules:

Rule	Description
Push Selection down	Filter rows as early as possible
Push Projection down	Remove unused columns early
Replace Cartesian Product + Selection with Join	Smaller intermediate results

These rules always apply, regardless of data size.

Cost-Based Optimization (CBO)

Estimates the actual cost of each plan:

Cost = CPU cost + Disk I/O cost + Memory cost + Network cost

Uses statistics:

• Number of rows in each table (cardinality)
• Number of distinct values in each column
• Histograms — distribution of values
• Index presence and selectivity

Example:

SELECT * FROM Orders WHERE Customer_ID = 42;

Two possible plans:

1. Full table scan — cost = total pages × I/O per page
2. Index scan — cost = (index height × I/O) + (1 page for data)

The optimizer picks the cheaper one. If 95% of customers have ID 42, a full scan might be cheaper than an index lookup.

---

Join Algorithms

How the DBMS physically joins two tables:

1. Nested Loop Join

For each row in R (outer):
    For each row in S (inner):
        If match condition:
            Output combined row

Factor	Value
Cost	O(N × M)
Best for	Small table × indexed large table
Worst for	Two large tables

2. Sort-Merge Join

1. Sort both tables by the join key
2. Merge — iterate through both sorted lists in one pass

Factor	Value
Cost	O(N log N + M log M + N + M)
Best for	Tables already sorted, or large tables with range conditions
Worst for	Unsorted tables (sorting overhead)

3. Hash Join

1. Build a hash table on the smaller table
2. Probe each row of the larger table against the hash table

Factor	Value
Cost	O(N + M)
Best for	Large tables with equality joins (most common)
Worst for	Non-equality joins (no hash possible)

Join Algorithm Comparison

Algorithm	Nested Loop	Sort-Merge	Hash Join
Time	O(N×M)	O(N log N)	O(N+M)
Memory	Low	Low	High (for hash table)
Equi-join	Yes	Yes	Yes
Non-equi join	Yes	Yes	No
Good with indexes	Yes	If pre-sorted	No

---

Using EXPLAIN

Most databases provide an EXPLAIN command to show the execution plan:

EXPLAIN SELECT Name FROM Students WHERE Age > 20;

Output (simplified):

Seq Scan on Students  (cost=0.00..35.50 rows=500 width=32)
  Filter: (age > 20)

Or with an index:

Index Scan using idx_age on Students  (cost=0.29..25.30 rows=100 width=32)
  Index Cond: (age > 20)

What to look for:

• Seq Scan on a large table → consider adding an index
• Nested Loop on two large tables → consider hash join tuning
• Sort on unindexed column → consider sorting index

---

Materialized Views

A Materialized View stores the query result physically on disk, unlike a regular view (which is just a stored query).

Feature	Regular View	Materialized View
Stores data	No (runs query every time)	Yes (cached result)
Query speed	Same as underlying query	Much faster
Freshness	Always up to date	Stale until refreshed
Storage	None	Disk space required

Use case: Expensive aggregations that don’t change frequently — daily sales summary, monthly reports.

---

Interview Deep Dive

---

Key Takeaways

• Query processing: Parse → Translate → Optimize → Evaluate.
• Optimizer is the brain — converts SQL to an efficient execution plan.
• Rule-Based: Fixed heuristics (push selection down, etc.).
• Cost-Based: Uses statistics to estimate costs and pick the cheapest plan.
• Nested Loop Join: Simple O(N×M) — good for small × indexed.
• Sort-Merge Join: Sort both, merge — good if pre-sorted.
• Hash Join: Fast O(N+M) — best for large equi-joins.
• EXPLAIN shows how the database executes your query.
• Materialized Views cache expensive query results on disk.