Indexes and reading a query plan

A page is slow. The interviewer asks: "What do you do?" This question is common in design rounds and in real work. A slow query is a common cause of a slow app.

A weak answer says "add an index" and stops. It does not say on which columns, in which order, or what the index costs. A strong answer first looks at how the database runs the query. Then it names the exact index, says how many rows the index saves, and says what it costs on every write.

At SDE-1 level you should explain what an index does. At SDE-2 level you should choose the columns and their order, and read how the database runs a query. At SDE-3 level you should also say how you add an index to a busy table safely, and when you would not add one.

You already know that an index is a sorted list beside a table. Think of a library with 4,000,000 books and no catalogue. To find one book, you walk past every shelf. A catalogue sorted by title lets you go straight to the right shelf. The books did not change. You only added a sorted list that tells you where they are.

Why a query without an index is slow

A database does not read single rows from disk. It reads a page: a block of fixed size. In Postgres a page is 8 KB (8,192 bytes), and many rows fit in one page. The time of a query is mostly the number of pages it must read.

In SQL, WHERE keeps only the rows that match a condition, ORDER BY sorts the result, and LIMIT 10 keeps the first 10 rows.

Suppose a query uses WHERE customer_id = 4821, and no index exists. The database must read every page of the table and check every row. This is called a sequential scan (or full table scan). The work grows with the size of the table. Ten times more rows means ten times more pages.

The B-tree

The most common index is a B-tree. It is a tree of pages. It is kept balanced, so every lookup takes the same number of steps. Postgres creates a B-tree when you do not say otherwise.

1. The top page is the root. It holds ranges of values and points to the pages below, for example "values up to 5,000 are over here".
2. Pages in the middle do the same, one level down.
3. The bottom pages are the leaves. They hold the values in sorted order, each with a pointer to its row in the table.

A lookup starts at the root and goes down one page per level. Each page holds hundreds of entries, so the tree is very short. Assumption: about 300 entries fit in one page. Then 3 levels reach 300 x 300 x 300 = 27,000,000 entries, and 4 levels reach 8,100,000,000. A lookup in a table of 40 million rows reads only 4 index pages.

Leaves are linked in sorted order. So a B-tree also answers ranges ("between these two dates") and sorted output: find the start, then walk along the leaves. It supports =, <, >, BETWEEN and ORDER BY. It cannot help with LIKE '%abc', because the start of the text is unknown.

Composite indexes

A composite index covers more than one column, for example (customer_id, created_at). The entries are sorted by customer_id first. Inside one customer, they are sorted by created_at. Think of a phone book sorted by surname, then first name. You can find "Sharma, Anil" fast, and "all Sharmas" fast. You cannot find "all Anils" fast, because they are spread everywhere.

So the order of columns matters. The index is used well by a query that fixes the leading columns:

• An index on (a, b, c) helps queries on a, on a and b, and on a, b and c.
• It helps little with a query on only b or only c, because the database cannot jump to the right place. (Postgres 18 and newer can sometimes skip the first column, but only when that column has very few different values. Do not depend on it.)
• Put the columns tested with = first. Put a range or sort column last.
• An index on (a, b) usually makes a separate index on (a) unnecessary.

When an index hurts or does not help

1. Every write pays. When you add or delete a row, the database must also update every index on the table. Ten indexes mean ten extra updates per write. A change to a column that has an index also updates that index. Indexes also take disk space and memory.
2. The query wants most of the table. If a condition keeps 95% of the rows, reading them one by one through an index costs more than a plain scan. The database then chooses the scan. This is correct behaviour, not a fault.
3. The condition hides the column. WHERE lower(email) = 'a@b.com' cannot use a plain index on email, because the index stores the original text. Create an index on lower(email) instead.
4. Tiny tables. For a few hundred rows, a scan is as fast as an index.
5. Building an index blocks writes. A plain CREATE INDEX blocks writes to the table while it builds. CREATE INDEX CONCURRENTLY does not block writes. It takes longer, it cannot run inside a transaction, and it can fail and leave an unusable index, which you must drop.

Reading a query plan

Never guess which index to add. Ask the database. EXPLAIN shows the plan: the steps the database will take to run the query. The planner is the part of the database that chooses the plan. It guesses the cost of each possible plan from statistics: stored facts about the table, such as the number of rows and how the values are spread. EXPLAIN ANALYZE also runs the query and shows what really happened. Careful: it really runs the statement, so a DELETE really deletes. Test such statements on a copy of the data, or put them between BEGIN and ROLLBACK.

How to read a plan:

• A plan is a tree of steps. The most indented steps run first. Read from the inside out.
• Seq Scan reads the whole table. Index Scan uses an index and then reads the table rows. Index Only Scan finds the answer in the index alone. Bitmap Heap Scan first collects row locations from an index, then reads the table pages in order.
• cost=0.57..75.80 is an estimate in made-up units, not milliseconds: the cost to the first row, then the cost to the last. Use it to compare plans.
• rows=20 is the estimated number of rows. With ANALYZE, actual time is in milliseconds (ms), and actual rows is the true count.
• Filter with Rows Removed by Filter shows rows that were read and thrown away. A huge number there often means a missing index.
• If the estimated rows are far from the actual rows, the statistics are often old. Run the ANALYZE command to refresh them.

Vacuum in one paragraph

When Postgres updates or deletes a row, it does not erase the old version at once, because a running query may still need it. These old versions are dead rows. They fill table pages and index pages. VACUUM finds dead rows that no query needs and frees their space for new rows (the file does not get smaller). It also updates a map that lets Index Only Scan work. Autovacuum runs this in the background by default, and it also runs ANALYZE to refresh the statistics. Do not switch it off. If it falls behind, for example because a transaction stays open for hours, tables and indexes grow larger than needed and queries slow down.

The orders table of a shopping app is slow. The query behind "my last 10 orders" is below.

The query:

SELECT * FROM orders
WHERE customer_id = 4821
ORDER BY created_at DESC
LIMIT 10;

Assumptions (made up to teach with):

• 40,000,000 orders, 200 bytes per row (we ignore small page and row headers), 2,000,000 customers. At the peak, 120 new orders arrive per second.
• A page is 8,192 bytes. A B-tree page holds 300 entries.
• A sequential scan reads 1 GB per second. A random page read takes 0.1 ms.

Step 1: no index.

• Rows per page = 8,192 / 200 = 40.96, so 40. Pages = 40,000,000 / 40 = 1,000,000 pages.
• Size = 1,000,000 x 8,192 bytes = about 8.2 GB. Time = 8.2 GB / 1 GB per second = about 8 seconds.
• Plan (shortened, numbers made up to match our assumptions):

Limit
  ->  Sort  (Sort Key: created_at DESC)
        ->  Seq Scan on orders  (cost=0.00..1500000.00 rows=20)
              Filter: (customer_id = 4821)
              Rows Removed by Filter: 39999980
Execution Time: 8200 ms

The scan reads 40,000,000 rows to return 20. That is the missing index.

Step 2: an index on customer_id only.

• Levels: 300 x 300 x 300 = 27,000,000 is less than 40,000,000, so we need 4 levels. The lookup reads 4 index pages.
• Orders per customer = 40,000,000 / 2,000,000 = 20. The 20 entries sit next to each other in one leaf. Each row is in a different table page, so we read 20 table pages.
• Total = 4 + 20 = 24 page reads, against 1,000,000. Time = 24 x 0.1 ms = 2.4 ms, against about 8,200 ms. That is about 3,400 times faster (8,200 / 2.4).
• The database still reads all 20 orders and sorts them to keep 10.

Step 3: a composite index on (customer_id, created_at).

CREATE INDEX CONCURRENTLY orders_customer_created_idx
    ON orders (customer_id, created_at);

• Inside one customer the entries are already sorted by time. The database goes to the customer, reads the 10 newest entries backwards, and stops. No sort is needed.
• Total = 4 index pages + 10 table pages = 14 reads = 1.4 ms.
• Plan (shortened):

Limit
  ->  Index Scan Backward using orders_customer_created_idx on orders
        Index Cond: (customer_id = 4821)
Execution Time: 1.4 ms

Step 4: the predict box. Query 1 fixes the leading column customer_id, so it uses the index well. Query 2 fixes only created_at, the second column. Entries for one day are spread across all customers, so the database cannot jump to them. Query 2 needs its own index on created_at, or it must scan the whole table or the whole index.

Step 5: the cost on writes. Assumption: each new row changes one table page and one page in every index. At the peak of 120 new orders per second:

• With 1 index: 120 x (1 + 1) = 240 page changes per second.
• With 6 indexes: 120 x (1 + 6) = 840 page changes per second. That is 3.5 times more (840 / 240).

Add an index only if a real query needs it.

• It solves: slow reads. The query went from 1,000,000 page reads to 14.
• It costs: extra work on every write, and disk and memory for each index. Building an index on a big table takes time and needs care.
• I would change it when: the table is write-heavy and has too many indexes. Then I drop the ones no plan uses. I would also change it when a query wants most of the table. An index will not help there, so change the query.
• Choose the column order from your queries: columns tested with = first, the range or sort column last.
• Check the result. Run EXPLAIN ANALYZE after you add the index, to see that the database uses it.

"More indexes always make the database faster." They make reads faster and writes slower. In the example, six indexes made each write cost 3.5 times more than one index.

"If an index exists, the database will use it." Not always. The database picks the cheapest plan. If a condition keeps most of the table, or the condition wraps the column in a function, it will not use the index. Look at the plan.

"An index on (a, b) is the same as an index on (b, a)." It is not. The first helps queries on a. The second helps queries on b. A query on only b gets almost no help from the first one.

1. A composite index exists on (a, b, c). Which of these queries use it well? (1) WHERE a = 1, (2) WHERE b = 2, (3) WHERE a = 1 AND b = 2, (4) WHERE a = 1 AND c = 3?
2. A table has 10,000,000 rows of 100 bytes. A page is 8,192 bytes, and a B-tree page holds 300 entries. (a) How many pages does the table have? (b) How long does a full scan take at 1 GB per second? (c) How many levels does a B-tree on one column need?
3. A table of 40,000,000 orders has an index on status. 95% of the rows have status = 'delivered'. EXPLAIN for WHERE status = 'delivered' shows a Seq Scan. A teammate says the index is broken. What do you say?