# Query Processing, Join Algorithms and EXPLAIN — Database Fundamentals

Source: https://www.skillbyai.com/en/database-fundamentals/s-query

> Describe how queries are parsed, optimised and executed, and read execution plans.

## From SQL text to results

A query passes through stages: **parsing** checks syntax and builds a tree; **rewriting** expands views and simplifies expressions; the **optimiser** generates alternative **execution plans** (which indexes, which join order, which algorithms) and estimates their **cost** from **statistics** such as table sizes, value distributions and histograms; the **executor** runs the chosen plan. The main **join algorithms**: **nested loop join** (for each outer row, look up matching inner rows, efficient when the outer side is small and the inner side has an index); **hash join** (build a hash table on the smaller input, probe it with the larger one, good for large equality joins); and **sort-merge join** (sort both inputs on the join key and merge, useful when inputs are already sorted or for range-like joins). Use **`EXPLAIN`** to see the plan and **`EXPLAIN ANALYZE`** (in PostgreSQL) to run it and compare estimated with actual rows. Large mismatches between estimates and reality point to stale statistics, so run `ANALYZE`; sequential scans on large tables for selective queries suggest a missing index.

## Reading a plan

Run it, then check the plan for the points listed in the comments.

```sql
EXPLAIN ANALYZE
SELECT s.name, m.score
FROM students s
JOIN marks m ON m.roll_no = s.roll_no
WHERE m.subject = 'DBMS' AND m.score >= 90;

-- what to look for in the plan:
--   Hash Join / Nested Loop / Merge Join   -> which join algorithm was chosen
--   Seq Scan on marks                      -> whole table read: index on (subject, score)?
--   Index Scan using idx_...               -> index used
--   rows=... (estimated) vs actual rows=... -> big gaps mean stale statistics (run ANALYZE)
--   actual time=...                        -> where the time is really spent
```

## Measure, then index

Do not guess which index to add. Run EXPLAIN ANALYZE on the slow query, find the expensive node, and design an index for that access path. Then confirm the plan and timing improved.

**Quiz:** Which join algorithm builds an in-memory table on the smaller input and probes it with rows from the larger input?

- [ ] Nested loop join
- [ ] Sort-merge join
- [x] Hash join
- [ ] Cartesian product

*Answer:* Hash join. Hash joins build a hash table on one input and probe it with the other, efficient for large equality joins.