Indexes and Query Performance

Table of Contents

1. Why Queries Get Slow
2. A Scratch Table with Half a Million Rows
3. Reading EXPLAIN
4. EXPLAIN ANALYZE: Real Timings
5. How a B-Tree Index Works
6. Creating an Index
7. Unique Indexes and Primary Keys
8. Composite Indexes and Column Order
9. Partial Indexes
10. Foreign Keys Are Not Indexed Automatically
11. When an Index Is Not Used
12. Indexes Are Not Free
13. The N+1 Query Problem
14. Try It Yourself

1. Why Queries Get Slow

Everything so far ran instantly because shopdb has five orders. Slow queries are invisible on small data. A table with a million rows is a different story.

When you ask for WHERE customer_id = 42, how does PostgreSQL find the matching rows? With no other information, it has only one option: read every row in the table and check each one. This is a sequential scan (seq scan). If the table has n rows, that is O(n) work, exactly the linear growth from Big-O Notation. Ten times the rows means ten times the time.

An index is a separate, sorted structure that lets the database jump straight to the matching rows. Instead of O(n), a lookup takes about O(log n) steps, the same trick as binary search. For a million rows that is roughly 20 steps instead of a million.

This chapter shows the difference with real data, so you can see it yourself instead of taking our word for it.

2. A Scratch Table with Half a Million Rows

Do not experiment on shopdb itself. Create a separate scratch table, filled with fake orders. PostgreSQL has a built-in function, generate_series, that produces a run of numbers. Combined with random() it can make as much data as you like:

CREATE TABLE scratch_orders AS
SELECT
  g                                         AS id,
  1 + floor(random() * 10000)::int          AS customer_id,
  (ARRAY['pending','paid','shipped','cancelled'])
    [1 + floor(random() * 4)::int]          AS status,
  now() - random() * 365 * interval '1 day' AS ordered_at,
  round((random() * 500)::numeric, 2)       AS total
FROM generate_series(1, 500000) AS g;

ANALYZE scratch_orders;

Step by step:

• generate_series(1, 500000) gives 500,000 rows, one per number.
• floor(random() * 10000) makes a random customer from 1 to 10,000, so each customer has about 50 orders.
• The ARRAY[...] trick picks one of four statuses at random.
• random() * 365 * interval '1 day' goes back up to a year in time.
• ANALYZE tells PostgreSQL to collect statistics about the table so its planner can make good decisions.

It takes a second or two. Check it:

SELECT count(*) FROM scratch_orders;

 count
--------
 500000
(1 row)

Because the data is random, your exact numbers below will differ from ours. The shape of the results is what matters.

3. Reading EXPLAIN

Put EXPLAIN in front of any query and PostgreSQL shows its plan, the steps it intends to take, without running it:

EXPLAIN
SELECT * FROM scratch_orders WHERE customer_id = 4242;

Typical output (the numbers will vary):

                          QUERY PLAN
--------------------------------------------------------------
 Gather  (cost=1000.00..8200.00 rows=50 width=33)
   Workers Planned: 2
   ->  Parallel Seq Scan on scratch_orders
         (cost=0.00..7195.00 rows=21 width=33)
         Filter: (customer_id = 4242)

How to read it:

Plans read from the innermost, most indented line outward. Here the scan is the real work, and Gather collects the results.

4. EXPLAIN ANALYZE: Real Timings

EXPLAIN only estimates. EXPLAIN ANALYZE actually runs the query and reports what really happened:

EXPLAIN ANALYZE
SELECT * FROM scratch_orders WHERE customer_id = 4242;

Typical output:

 Gather  (cost=1000.00..8200.00 rows=50 width=33)
         (actual time=1.8..38.5 rows=48 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   ->  Parallel Seq Scan on scratch_orders
         (cost=0.00..7195.00 rows=21 width=33)
         (actual time=4.0..34.2 rows=16 loops=3)
         Filter: (customer_id = 4242)
         Rows Removed by Filter: 166651
 Planning Time: 0.1 ms
 Execution Time: 39.0 ms

Roughly 40 ms on a typical laptop (yours could be 15 or 100). The key lines:

• actual time=... is in real milliseconds.
• rows=48 is the real count, next to the estimate of 50. When estimates and reality differ wildly, run ANALYZE on the table.
• Rows Removed by Filter: 166651 is the smell. PostgreSQL read about half a million rows (this is per worker, across three loops) to return 48. Almost all the work was wasted.

One warning: EXPLAIN ANALYZE really executes the statement. For SELECT that is harmless. For UPDATE or DELETE it changes data, so wrap it in a transaction and roll back (chapter 12), or just use plain EXPLAIN.

5. How a B-Tree Index Works

The default index in PostgreSQL is a B-tree. Think of the index at the back of a textbook: sorted terms, each with page numbers. You do not read the whole book to find "foreign key". You flip to the sorted index, find it quickly, and jump to the page.

A B-tree is that idea, arranged as a tree of sorted pages:

                    [ 2500 | 5000 | 7500 ]            <- root page
                   /        |        |       \
         [ ... ]       [ ... ]   [ ... ]    [ ... ]   <- middle pages
          /   \          ...
   [leaf: 4240 -> row pointers]
   [leaf: 4241 -> row pointers]
   [leaf: 4242 -> (row 17), (row 903), (row 12044)...] <- leaf pages

To find 4242, start at the root, follow one branch toward the right range, then another, and arrive at a leaf holding the key with pointers to the matching table rows. Each page holds hundreds of keys, so the tree is very flat: usually 3 or 4 levels, even for hundreds of millions of rows. That is the O(log n) from Big-O, with a huge base for the logarithm.

Because the leaves are sorted, a B-tree also handles <, >, BETWEEN, and ORDER BY well, not just =.

6. Creating an Index

CREATE INDEX idx_scratch_orders_customer_id
  ON scratch_orders (customer_id);

On half a million rows it takes a moment. Now run the same query again:

EXPLAIN ANALYZE
SELECT * FROM scratch_orders WHERE customer_id = 4242;

Typical output:

 Bitmap Heap Scan on scratch_orders
     (cost=5.9..200.0 rows=50 width=33)
     (actual time=0.05..0.20 rows=48 loops=1)
   Recheck Cond: (customer_id = 4242)
   Heap Blocks: exact=47
   ->  Bitmap Index Scan on idx_scratch_orders_customer_id
         (cost=0.00..5.9 rows=50 width=0)
         (actual time=0.03..0.03 rows=48 loops=1)
         Index Cond: (customer_id = 4242)
 Planning Time: 0.2 ms
 Execution Time: 0.3 ms

About 39 ms became about 0.3 ms, over a hundred times faster, and the gap grows with the table. The plan now says Index Cond instead of Filter: PostgreSQL used the index to find the rows instead of testing all of them. You may see Index Scan instead of Bitmap Heap Scan depending on how many rows match. Both mean the index was used.

The planner decides when to use an index. You never write "use this index" in a query. You create the index and the planner chooses it when it is cheaper than a seq scan.

The name idx_<table>_<column> is a convention that makes \d output easy to read.

7. Unique Indexes and Primary Keys

You have been creating indexes all along without knowing it. A PRIMARY KEY and a UNIQUE constraint each create a unique B-tree index automatically. That is how PostgreSQL checks quickly that no duplicate exists when you insert. Look at customers:

shopdb=# \d customers
...
Indexes:
    "customers_pkey" PRIMARY KEY, btree (id)
    "customers_email_key" UNIQUE CONSTRAINT, btree (email)

So WHERE id = 3 and WHERE email = 'linda@example.com' are already fast. Add a primary key to the scratch table to see it:

ALTER TABLE scratch_orders ADD PRIMARY KEY (id);

You can also create a unique index directly (CREATE UNIQUE INDEX ...). It is equivalent to a UNIQUE constraint for most uses.

8. Composite Indexes and Column Order

An index can cover more than one column. Suppose a page often asks: "the paid orders of customer 4242, newest first."

CREATE INDEX idx_scratch_orders_customer_status_date
  ON scratch_orders (customer_id, status, ordered_at);

A composite B-tree is sorted by the first column, then by the second within equal first values, then the third. Think of a phone book sorted by last name, then first name. The consequence is the leftmost prefix rule:

A phone book helps you find "Chan" or "Chan, Sokha". It does not help you find everyone named "Sokha" in any family. So column order matters: put the columns you filter with equality most often first, and range or sort columns last.

A composite index can often replace a single-column one. This index also serves WHERE customer_id = ..., so the earlier single-column index is now redundant, and you could drop it to save space.

9. Partial Indexes

Sometimes you only ever query a small slice of the data. A partial index includes only the rows that match a condition, which makes it smaller and faster:

CREATE INDEX idx_scratch_orders_pending
  ON scratch_orders (ordered_at)
  WHERE status = 'pending';

This index only contains pending orders (about a quarter of the rows here, far less in a real shop where most orders get shipped). It serves a query like "oldest pending orders", but only if the query includes the same condition:

SELECT id, ordered_at
FROM scratch_orders
WHERE status = 'pending'
ORDER BY ordered_at
LIMIT 10;

Partial indexes also solve a soft-delete problem from the last chapter: a UNIQUE index WHERE deleted_at IS NULL enforces unique emails only among active users.

10. Foreign Keys Are Not Indexed Automatically

Here is a surprise that bites many beginners. When you declare customer_id REFERENCES customers(id), PostgreSQL indexes the referenced column (customers.id, it is the primary key). It does not index the referencing column (orders.customer_id).

Yet you will filter and join on foreign keys constantly: "all orders of this customer", or JOIN orders o ON o.customer_id = c.id. Without an index, each of those scans the whole orders table. Deleting a customer is slow too, because PostgreSQL must check every order for references.

So in shopdb, add the indexes yourself. Put them in a new migration file, migrations/004_add_fk_indexes.sql:

CREATE INDEX idx_orders_customer_id      ON orders (customer_id);
CREATE INDEX idx_order_items_product_id  ON order_items (product_id);
CREATE INDEX idx_products_category_id    ON products (category_id);

You do not need one for order_items.order_id. The composite primary key (order_id, product_id) already starts with order_id, so it covers lookups by order. Apply it:

docker exec -i shopdb-pg psql -U postgres -d shopdb \
  < migrations/004_add_fk_indexes.sql

With five orders, the planner will keep using seq scans anyway, since reading one tiny page is cheaper than walking an index. The indexes pay off as data grows. Add them now and forget about it.

11. When an Index Is Not Used

Creating an index does not guarantee it is used. These are the common reasons, and each is worth knowing.

1. A function on the column. The index stores raw email values. This query cannot use it:

SELECT * FROM customers WHERE lower(email) = 'dara@example.com';

The planner would have to compute lower() for every row. Either compare the raw column, or build an expression index that stores the result:

CREATE INDEX idx_customers_email_lower ON customers (lower(email));

The same goes for math on the column: WHERE total * 2 > 100 cannot use an index on total, but WHERE total > 50 can. Move the math to the other side.

2. A leading wildcard. LIKE 'Sok%' can use a B-tree index (it is a range of sorted values), but LIKE '%ha' cannot, since the beginning is unknown. Fast text search needs other tools (full-text search or the pg_trgm extension), not a plain B-tree.

3. Low selectivity. If a condition matches a large share of the table, a seq scan really is faster. WHERE status = 'paid' returns a quarter of the rows, so the planner may prefer reading everything over bouncing between the index and the table. This is correct behavior, not a bug. Indexes are for selective conditions that return few rows.

4. Tiny tables. For a table that fits in a page or two, a seq scan is the cheapest plan. Do not be alarmed when EXPLAIN on shopdb ignores your indexes.

5. Outdated statistics. After loading lots of data, run ANALYZE so the planner knows the table's real size. (Autovacuum does this in the background, usually, but not instantly.)

6. A type mismatch between the column and the value, or an implicit cast, can also prevent index use. Keep types consistent.

When in doubt, ask the database: run EXPLAIN and read whether it says Seq Scan or Index Scan.

12. Indexes Are Not Free

If indexes make reads fast, why not index every column? Because each one has a cost:

See the size for yourself:

SELECT pg_size_pretty(pg_relation_size('scratch_orders'))  AS table_size,
       pg_size_pretty(pg_relation_size(
         'idx_scratch_orders_customer_id'))                AS index_size;

 table_size | index_size
------------+------------
 29 MB      | 11 MB
(1 row)

(Typical figures, yours will differ.) The index here is a third of the table, for one column.

A sensible approach:

1. Index the primary keys (automatic) and foreign keys.
2. Index columns that appear in WHERE, JOIN, and ORDER BY of queries you run often and that return few rows.
3. Do not guess. Find the slow query, run EXPLAIN ANALYZE, add one index, measure again.
4. Drop indexes nobody uses. PostgreSQL tracks this in the pg_stat_user_indexes view (idx_scan = 0 means never used).

Measure, do not guess. This is the same rule as in Big-O: understand the shape, then check with real numbers.

13. The N+1 Query Problem

One more performance trap is not about indexes at all. It appears when application code talks to the database. Imagine a page that lists customers with their orders. A naive program does this:

const customers = await db.query("SELECT * FROM customers");   // 1 query

for (const c of customers.rows) {
  const orders = await db.query(
    "SELECT * FROM orders WHERE customer_id = $1", [c.id]      // N queries
  );
  console.log(c.name, orders.rows.length);
}

One query to get N customers, then one more per customer: N + 1 queries. With 5 customers that is 6 round trips and nobody notices. With 5,000 customers it is 5,001 trips across the network, each with its own overhead, and the page takes seconds. ORMs make this mistake easy to write by accident.

The fix is to let the database do the work, with a join and an aggregate, in one query:

SELECT c.name, count(o.id) AS orders
FROM customers c
LEFT JOIN orders o ON o.customer_id = c.id
GROUP BY c.id, c.name
ORDER BY c.id;

    name    | orders
------------+--------
 Sokha Chan |      2
 Dara Kim   |      2
 Linda Vong |      1
 Vuthy Sok  |      0
 Maly Ros   |      0
(5 rows)

Whenever you see a query inside a loop, ask whether a join or an IN (...) list could fetch it all at once.

Finally, clean up the scratch table so it does not take space:

DROP TABLE scratch_orders;

14. Try It Yourself

1. Feel the difference. Rebuild scratch_orders (drop it first), run the lookup with EXPLAIN ANALYZE before and after creating the index on customer_id. Record the two execution times and the plan node name for each.
2. Scale it. Rebuild with 100,000 rows, then 2,000,000. Measure the un-indexed query each time. Does the time grow roughly in proportion to the size, as O(n) predicts? What about the indexed query?
3. Composite order. Create an index on (status, customer_id) and another on (customer_id, status). For WHERE customer_id = 4242 AND status = 'paid' and then for WHERE status = 'paid' alone, which index does EXPLAIN pick? Explain why.
4. Defeat an index. Index ordered_at. Show a query on a date range that uses it, then rewrite the filter with a function on the column (for example WHERE date_trunc('day', ordered_at) = '2026-01-05') and watch the plan change. How could you rewrite it to use the index again?
5. Check the foreign keys. Apply 004_add_fk_indexes.sql to shopdb, then run \d orders and \d order_items. List every index shown and which constraint or migration created it.
6. Find the wasted index. Create a deliberately useless index on status in the scratch table. Run a few queries, then query pg_stat_user_indexes for its idx_scan count. Would you keep it?

Where to go next. Your queries are correct, clean, and fast. But correct for one user at a time is not enough. What if an order is created, the stock update succeeds, and then the server crashes before the order items are saved? The final chapter, Transactions and Safe SQL, shows how to make multi-step changes all-or-nothing, how to survive two people buying the last item at once, and how to keep SQL injection out of your application.