Indexes and Execution Plans

Almost every performance problem you will meet in SQL falls into one of two buckets: the database read far more data than it needed to, or it did so far more often than it needed to. Indexes address the first one. Execution plans are how you find out which one you have.

The course tables are too small to show any of this. Eleven rows fit in one page, and the planner will always read all of them. So build a table big enough for the problem to be real.

A table worth tuning#

CREATE TABLE big_orders AS
SELECT g                                                       AS order_id,
       (random() * 99999)::int + 1                             AS customer_id,
       DATE '2023-01-01' + (random() * 700)::int               AS order_date,
       (ARRAY['pending','paid','shipped','delivered','cancelled'])[1 + (random() * 4)::int] AS status,
       ROUND((random() * 500)::numeric, 2)                     AS total
FROM generate_series(1, 1000000) AS g;

ANALYZE big_orders;

One million rows, roughly ten orders per customer. ANALYZE collects the statistics the planner depends on. Results will vary because of random(), so treat the plans below as shapes, not exact numbers.

What an index is#

Without an index, finding one customer's orders means reading every page of the table, a sequential scan. An index is a separate, sorted structure that maps column values to the location of their rows.

PostgreSQL's default is the B-tree. Picture a tree whose leaves hold the sorted keys with pointers into the table.

                       [ 300 | 600 ]                          root
                     /       |        \
          [100 | 200]    [400 | 500]    [700 | 800]            internal pages
          /    |    \       /   |   \      /   |   \
       leaf  leaf  leaf  leaf  leaf  leaf  leaf  leaf  leaf    leaf pages
        |
        +--> sorted keys, each with a pointer (page, row) into the table
             and leaf pages are chained left to right for range scans

A lookup starts at the root, follows one branch per level, and lands on the right leaf. Each page holds hundreds of keys, so even a billion-row table needs only four or five levels. That is why index lookups take milliseconds regardless of table size.

Because the leaves are sorted and chained, the same structure serves equality (= 4242), ranges (BETWEEN, >), ORDER BY and MIN/MAX.

CREATE INDEX idx_big_orders_customer ON big_orders (customer_id);

Reading a plan#

EXPLAIN shows the plan the planner chose without running the query. EXPLAIN ANALYZE runs it and adds the real timings.

Before the index (illustrative output):

EXPLAIN ANALYZE SELECT * FROM big_orders WHERE customer_id = 4242;

 Gather  (cost=1000.00..13500.00 rows=10 width=34) (actual time=2.9..48.0 rows=11 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   ->  Parallel Seq Scan on big_orders  (cost=0.00..12500.00 rows=4 width=34)
                                        (actual time=6.1..40.2 rows=4 loops=3)
         Filter: (customer_id = 4242)
         Rows Removed by Filter: 333330
 Planning Time: 0.1 ms
 Execution Time: 48.4 ms

After:

 Index Scan using idx_big_orders_customer on big_orders
        (cost=0.42..48.00 rows=10 width=34) (actual time=0.03..0.06 rows=11 loops=1)
   Index Cond: (customer_id = 4242)
 Planning Time: 0.1 ms
 Execution Time: 0.09 ms

Roughly three orders of magnitude faster, because it read a handful of pages instead of the whole table.

How to read any plan:

• It is a tree. Read from the most indented line outward. Children feed their parent.
• cost=a..b is the planner's estimate in arbitrary units: a to produce the first row, b for all rows. Compare costs within one plan, never against other databases or machines.
• rows= is the estimate. actual ... rows= is the truth. A big gap, such as an estimate of 10 and an actual 500,000, means the statistics are wrong or stale. Run ANALYZE, and many bad plans fix themselves.
• loops= says how many times the node ran. Multiply the per-loop time by the loops when the node is inside a nested loop.
• Rows Removed by Filter is wasted work. A huge number next to a tiny result is the sign of a missing index.

Add BUFFERS to see how many pages came from cache and from disk:

EXPLAIN (ANALYZE, BUFFERS) SELECT ...;

One warning. EXPLAIN ANALYZE actually executes the statement. Used on an UPDATE or DELETE, it changes your data. Wrap it:

BEGIN;
EXPLAIN ANALYZE UPDATE big_orders SET status = 'paid' WHERE customer_id = 4242;
ROLLBACK;

Scan and join node types#

A sequential scan is not a failure. When a query needs a large share of the table, reading it in order is the cheapest plan, and the planner knows. The question is always whether a scan is reading far more than it keeps.

Composite indexes#

An index can cover several columns. Column order matters, because the index is sorted by the first column, then by the second within it, like a phone book sorted by surname then first name.

CREATE INDEX idx_big_orders_cust_date ON big_orders (customer_id, order_date);

It helps queries that filter on customer_id, or on customer_id and order_date, and it can also deliver rows already sorted by date for one customer. It does not help a query filtering on order_date alone, since the second column is not sorted globally. This is the leftmost prefix rule.

Guidance for ordering columns: put equality conditions first, then the range or sort column. WHERE customer_id = 4242 AND order_date >= '2024-01-01' fits (customer_id, order_date) perfectly.

Covering indexes#

If the index already contains every column the query needs, PostgreSQL can skip the table. INCLUDE adds payload columns to the leaves without making them part of the search key.

CREATE INDEX idx_big_orders_cust_cover ON big_orders (customer_id) INCLUDE (total);

SELECT customer_id, SUM(total) FROM big_orders WHERE customer_id = 4242 GROUP BY customer_id;
-- Index Only Scan

Index-only scans depend on the visibility map, which VACUUM maintains. On a table with heavy churn and lagging vacuum, the planner may still have to visit the table.

Partial indexes#

Index only the rows you search for.

CREATE INDEX idx_big_orders_open ON big_orders (order_date) WHERE status IN ('pending', 'paid');

If open orders are 5% of the table, the index is about 5% of the size, cheaper to maintain and faster to scan. The query's WHERE must imply the index's WHERE for the planner to use it.

Expression indexes#

Case-insensitive email lookups are a classic. A normal index on email is useless for WHERE LOWER(email) = ..., since the search value is not the stored value.

CREATE INDEX idx_customers_email_lower ON customers (LOWER(email));
SELECT * FROM customers WHERE LOWER(email) = 'aisha@example.com';

The function must be IMMUTABLE.

Other index types#

Why the planner ignores your index#

A new index that is never used is a common puzzle. The usual causes:

• A function or expression on the column. WHERE EXTRACT(YEAR FROM order_date) = 2024 cannot use a plain index on order_date. Rewrite as a range, or create an expression index.
• A leading wildcard. LIKE '%smith' has no sorted starting point.
• Mismatched types. Comparing a text column to a number forces a cast on every row.
• Low selectivity. If status = 'delivered' matches 20% of rows, reading the table sequentially beats jumping around through an index.
• Stale statistics. The planner thinks the table has 100 rows. Run ANALYZE.
• A tiny table. On 11 rows, the sequential scan is correct.
• The leftmost-prefix rule. Filtering on the second column only.

You can test whether the planner could use an index with SET enable_seqscan = off; in a session. It only discourages the plan, so it is a diagnostic tool, never a setting for production.

Indexes are not free#

Every index must be updated on each INSERT, UPDATE of an indexed column and DELETE. Ten indexes on a table means ten writes per row. They also use disk and memory.

Index what you query by: foreign keys (as the constraints lesson said), columns in frequent WHERE, JOIN and ORDER BY clauses. Find the dead weight with:

SELECT relname, indexrelname, idx_scan
FROM pg_stat_user_indexes
ORDER BY idx_scan ASC;

An index with idx_scan = 0 over weeks of real traffic is a candidate to drop (check that it does not enforce a unique constraint first).

On a live table, build with CREATE INDEX CONCURRENTLY. It takes longer, but does not block writes.

Common mistakes#

Indexing every column "just in case". Writes slow down and nothing gets faster.

Wrong column order in a composite index. (order_date, customer_id) does not serve a lookup by customer.

Wrapping an indexed column in a function. The index sits unused.

Tuning from guesses instead of plans. Read the plan first.

Trusting EXPLAIN without ANALYZE. The estimates may be far from the actual row counts.

Running EXPLAIN ANALYZE on a write without a rollback.

Practice#

1. Build big_orders, run EXPLAIN ANALYZE for one customer before and after creating the index. Note the scan type and execution time.
2. Query by order_date alone with only the (customer_id, order_date) index in place. Which scan do you get, and why?
3. Create a partial index for open orders and write a query that uses it. Confirm with EXPLAIN, then change the WHERE so it can no longer use it.
4. Compare plans for WHERE EXTRACT(YEAR FROM order_date) = 2024 and the equivalent range filter.
5. Find the estimated and actual row counts for WHERE status = 'delivered'. If they differ widely, run ANALYZE and look again.