# Query Optimization (Part 1: Reading a Query Plan)

## 1. `EXPLAIN`: Ask the Planner What It's Going to Do

`01-database_indexes/` and `02-b_tree/` covered how to build the right index. This topic is about verifying the engine actually uses it, and diagnosing when it doesn't. `EXPLAIN` shows the plan the query planner has chosen, without running the query:

```sql
EXPLAIN SELECT * FROM orders WHERE customer_id = 42;
```
```
Seq Scan on orders  (cost=0.00..1834.00 rows=12 width=64)
  Filter: (customer_id = 42)
```

`EXPLAIN ANALYZE` actually *runs* the query and reports real timing alongside the plan — essential when the planner's cost estimate and reality diverge:

```sql
EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 42;
```
```
Seq Scan on orders  (cost=0.00..1834.00 rows=12 width=64) (actual time=0.02..8.41 rows=11 loops=1)
  Filter: (customer_id = 42)
  Rows Removed by Filter: 49989
Planning Time: 0.08 ms
Execution Time: 8.44 ms
```

## 2. Sequential Scan vs. Index Scan vs. Index-Only Scan

```sql
CREATE INDEX idx_orders_customer ON orders (customer_id);
EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 42;
```
```
Index Scan using idx_orders_customer on orders  (cost=0.29..8.31 rows=12 width=64) (actual time=0.015..0.019 rows=11 loops=1)
  Index Cond: (customer_id = 42)
```

- **Seq Scan**: reads every row in the table, filtering as it goes — cost grows linearly with table size, regardless of how selective the filter is.
- **Index Scan**: uses an index (`01-database_indexes/`) to find matching rows directly, then fetches each matching row from the table itself — one extra trip per match compared to reading straight off the index.
- **Index-Only Scan**: the index alone contains every column the query needs (a covering index, `01-database_indexes/` section 6), so the engine never touches the table at all.

## 3. Join Algorithms, at a Conceptual Level

```sql
SELECT o.id, c.name FROM orders o JOIN customers c ON o.customer_id = c.id;
```

The planner picks one of several strategies for combining two row sets, based on their estimated sizes and whether useful indexes exist:

- **Nested Loop**: for each row in the outer set, scan (or index-lookup into) the inner set. Cheap when one side is small, or when an index makes the inner lookup fast per row — expensive (quadratic) when both sides are large and unindexed.
- **Hash Join**: build an in-memory hash table from the smaller side, then scan the larger side probing that hash table. Good for large, unsorted inputs with no useful index — pays a memory cost to build the hash table.
- **Merge Join**: if both inputs are already sorted on the join key (or can be cheaply sorted), walk both in lockstep like a zipper. Good when both sides are pre-sorted (e.g. arriving from index scans on the join column) and large.

None of these is universally "best" — the planner picks based on estimated row counts and available indexes for the specific query at hand, which is exactly what the plan output tells you when you read it.

## 4. Reading Cost Numbers

```
Seq Scan on orders  (cost=0.00..1834.00 rows=12 width=64)
                          ^       ^        ^        ^
                     startup   total   estimated  avg row
                      cost     cost    row count    size
```

The two cost numbers are **arbitrary planner units**, not milliseconds — they're only meaningful for *comparing* candidate plans against each other, which is literally how the planner chooses: it estimates the cost of several possible plans for the same query and picks the cheapest one. `startup cost` is the estimated cost before the first row can be returned (near-zero for a sequential scan, higher for a plan that needs to sort or build a hash table first); `total cost` is the estimated cost to return every row.

![An EXPLAIN ANALYZE plan read bottom-up, with a sequential scan removing many rows signalling a missing index and estimate versus actual mismatches signalling stale statistics](diagrams/01-reading-explain.svg)

## 5. Quick Reference

```
EXPLAIN          -> shows the chosen plan, does NOT run the query
EXPLAIN ANALYZE   -> runs the query, shows plan + real timing + actual row counts

Seq Scan          -> reads the whole table, cost grows with table size
Index Scan         -> index finds matches, then fetches each row from the table
Index-Only Scan    -> answered entirely from a covering index, fastest

Nested Loop  -> good: one side small, or indexed inner lookup
Hash Join    -> good: large unsorted inputs, no useful index
Merge Join   -> good: both inputs already sorted on the join key

cost=X..Y -> arbitrary planner units for COMPARING plans, not real time
actual time=X..Y (from ANALYZE) -> real milliseconds, the ground truth
```