Reading EXPLAIN: scans and joins

Part of the free LogicWiz SQL & Databases course, Module 14: Indexes and query plans. The queries and practice run in the app on real Postgres.

Meher adds an index, runs the query, and EXPLAIN says Bitmap Heap Scan. Did her index work or not? And why does the big report use a Hash Join while the single-customer page uses a Nested Loop?

You'll learn to

Read a plan tree from the inside out
Tell Seq Scan, Index Scan, Index Only Scan and Bitmap scans apart
Know when Postgres picks a nested loop, hash or merge join
Use EXPLAIN ANALYZE safely

Learn

A plan with its costs

EXPLAIN
SELECT * FROM orders WHERE amount > 1500;

Each line is a node. cost=0.00..619.00 is the planner's estimate in made-up units: startup cost (before the first row) and total cost. rows is how many rows it expects, width the average row size in bytes. These come from the statistics ANALYZE collected. Practice items use EXPLAIN (COSTS OFF) so only the shape is shown.

Three ways to use an index

EXPLAIN (COSTS OFF)
SELECT * FROM orders WHERE order_id = 42;
EXPLAIN (COSTS OFF)
SELECT order_id FROM orders WHERE order_id < 50;
EXPLAIN (COSTS OFF)
SELECT * FROM orders WHERE customer_id = 42;

Click through the three plans: an Index Scan (one order by its key), an Index Only Scan (the index alone has order_id, so the table is never read) and a Bitmap Heap Scan fed by a Bitmap Index Scan (customer 42's 5 orders, spread across the table).

The scan types

Plan node	What it does	Picked when
Seq Scan	Reads every page of the table in order	No useful index, or a big share of rows match
Index Scan	Walks the index, fetches each matching row from the table	Few rows match, or rows are wanted in index order
Index Only Scan	Answers from the index alone	Every column the query needs is in the index
Bitmap Index Scan + Bitmap Heap Scan	First collects all matching row addresses into a bitmap (a list of pages), then reads those pages once each, in disk order	A moderate number of rows, scattered over many pages; or two indexes combined with AND/OR

Bitmap scans are index scans. They just batch the lookups so that each table page is read once, not once per row. So yes, Meher's index worked.

Reading the tree

A plan is a tree printed with indentation. Each -> is a child node that feeds rows to the line above it.

Start at the most indented lines: those run first (scans of tables).
Move outwards: joins combine their two children, then Sort, Aggregate or Limit work on the result.
Index Cond means the index is used to find rows. Filter means rows are read and then checked one by one. Recheck Cond belongs to bitmap scans.

For a slow query, look for a Seq Scan on a big table with a Filter that keeps few rows: that is usually the missing index.

The three join algorithms

Join	How it works	Best when
Nested Loop	For each row of the outer side, look up matches in the inner side (ideally with an index)	The outer side is small: one customer and their orders
Hash Join	Build a hash table on the smaller input, then scan the bigger one and probe it	Big inputs, equality join, no useful order: a full report
Merge Join	Read both inputs sorted on the join key and zip them together	Both sides are already sorted (by indexes) or the output must be sorted anyway

One join, three plans

-- every order with its customer: Hash Join
EXPLAIN (COSTS OFF)
SELECT c.name, o.amount
FROM customers c
JOIN orders o ON o.customer_id = c.customer_id;
-- one customer: Nested Loop
EXPLAIN (COSTS OFF)
SELECT c.name, o.amount
FROM customers c
JOIN orders o ON o.customer_id = c.customer_id
WHERE c.customer_id = 7;
-- sorted by customer: Merge Join
EXPLAIN (COSTS OFF)
SELECT c.name, o.order_id
FROM customers c
JOIN orders o ON o.customer_id = c.customer_id
ORDER BY c.customer_id;

Same tables, same join condition. The planner picks the algorithm from the estimated row counts and available indexes. For the merge join, both indexes already give rows in customer_id order, so no sort is needed.

EXPLAIN ANALYZE: run it and measure

EXPLAIN ANALYZE
SELECT city, COUNT(*)
FROM orders
WHERE status = 'pending'
GROUP BY city;

EXPLAIN ANALYZE runs the query and adds the real actual time and rows to each node. Compare estimated rows with actual rows: a big gap means stale statistics (run ANALYZE). Times change run to run, so practice never checks them.

EXPLAIN ANALYZE really executes the statement. EXPLAIN ANALYZE DELETE FROM orders … deletes the rows. To measure a write safely, wrap it: BEGIN; EXPLAIN ANALYZE DELETE …; ROLLBACK;

Join costs for inputs of M and N rows: nested loop O(M × N), or O(M log N) with an index on the inner side; hash join O(M + N) but needs memory for the hash table; merge join O(M log M + N log N) for sorting, or O(M + N) if already sorted. Exams also ask for block-transfer counts for nested-loop joins: with b_r, b_s blocks, a simple nested loop costs n_r × b_s + b_r.

In one line

Read plans inside-out; Index/Index Only/Bitmap scans use indexes, Seq Scan reads everything; nested loop for small outer sides, hash for big unsorted inputs, merge for sorted ones.

Interview corner

How do you find out why a query is slow?

Run EXPLAIN ANALYZE on it. Look for a Seq Scan on a large table with a selective filter (missing index), estimated rows far from actual rows (stale stats: run ANALYZE), big sorts or hashes spilling to disk, and nested loops over many outer rows.

Index Scan vs Bitmap Index Scan vs Index Only Scan?

An Index Scan fetches table rows one by one in index order. A Bitmap scan first collects all matching row addresses, then reads each table page once in physical order: better for many scattered rows, and it can combine indexes with AND/OR. An Index Only Scan never touches the table because the index has every needed column.

Explain nested loop, hash and merge joins.

Nested loop: for each outer row, look up the inner side; great when the outer side is small and the inner is indexed. Hash join: build a hash table on the smaller input, probe with the larger; best for big unsorted equality joins. Merge join: walk two inputs sorted on the key; best when both are already sorted.