Query Processing

Processing Stages

SQL Query
    ↓
┌──────────────┐
│   Parser     │ → Syntax check, parse tree
└──────────────┘
    ↓
┌──────────────┐
│  Optimizer   │ → Choose best execution plan
└──────────────┘
    ↓
┌──────────────┐
│  Executor    │ → Run the plan
└──────────────┘
    ↓
Results

Query Optimization

1. Rule-Based Optimization

Heuristic rules:
- Push selections down (filter early)
- Push projections down (fewer columns)
- Convert subqueries to joins

2. Cost-Based Optimization

Estimate cost for different plans:
- Table scan: N pages
- Index scan: Height + matching pages
- Join methods: Nested loop, hash, merge

Choose lowest cost plan

Join Algorithms

Algorithm	Cost	Best For
Nested Loop	O(N×M)	Small tables, indexed inner
Hash Join	O(N+M)	Equality joins, no index
Merge Join	O(N log N + M log M)	Sorted data, range joins

EXPLAIN Plan

EXPLAIN ANALYZE
SELECT * FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE c.country = 'USA';

-- Shows: Scan types, join methods, row estimates, actual times