Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 90 ยท Indexes

How Indexes Work in PostgreSQL

See how a PostgreSQL index points into the heap with TIDs, why the planner picks a sequential, index or bitmap scan, and what every index costs on writes.

An index is a second data structure, kept next to your table, that lets PostgreSQL find rows without reading all of them. You probably know the one-line version: "an index makes lookups fast." That is true, but it hides the interesting part. PostgreSQL does not always use an index even when one exists, an index can make the same query slower, and every index you add taxes every write. To use indexes well you need a picture of what is actually stored and how the planner decides.

This lesson builds that picture: the heap that holds your rows, the TID that connects an index entry to a row, the three ways PostgreSQL can fetch rows (sequential, index and bitmap scans), and the cost side of indexing. The PostgreSQL commands appear in read-only blocks, and the live examples use SQLite's EXPLAIN QUERY PLAN to show the same ideas in your browser. If you have not met indexes at all yet, SQL Indexes is the gentle introduction, and Reading Query Plans explains plan output in general.

The heap and the TID

A PostgreSQL table is stored as a heap: a file divided into 8 kB pages, each holding rows (called tuples) in no particular order. New rows go wherever there is free space. There is no "first row" in a heap, only a physical position.

That position is the TID (tuple identifier), a pair (page number, slot within the page). You can see it through the hidden ctid column:

SQL
SELECT ctid, id, title FROM books LIMIT 3;
--  ctid  | id |      title
-- -------+----+-----------------
--  (0,1) |  1 | The Salt Road
--  (0,2) |  2 | Rivers of Glass
--  (0,3) |  3 | Northern Ledger

An index is a separate structure that stores key values together with TIDs. An index on books (author_id) is a sorted list of (author_id, TID) pairs. To answer WHERE author_id = 4, PostgreSQL searches the index for 4, collects the TIDs, and then visits each heap page named by a TID to read the actual row. The index never holds the row itself, only the address of the row.

An index points into the heap

Heap Rows in 8 kB pages, in no particular order.
Index Sorted keys, each with a TID.
TID Page number plus slot, the row's address.

Lookup = search the index, then jump to the heap page.

1 / 2

SQLite is a useful contrast, because its table is itself a B-tree ordered by a hidden rowid, so a lookup by rowid (or an INTEGER PRIMARY KEY) is a direct search with no separate heap. In PostgreSQL even the primary key is an ordinary index that points into the heap. Run this to see an index search in SQLite:

SQL Scan, search and rowid lookup ยท database: shop

Press Run (or Ctrl + Enter) to see the result here.

The first plan says SCAN order_items, the second says SEARCH order_items USING INDEX order_items_product_idx (product_id=?), and the third says SEARCH order_items USING INTEGER PRIMARY KEY (rowid=?). The PostgreSQL equivalents are Seq Scan, Index Scan using ... and, for a primary key, also Index Scan using order_items_pkey.

Three ways to fetch rows

When you run a query, the planner estimates the cost of each strategy and picks the cheapest. For a filter such as WHERE customer_id = 8 there are three main choices.

Sequential scan reads the whole heap from start to end. It is cheap per page because the reads are sequential, and it needs no index. It is the right choice when a query needs a large share of the table, and also for small tables, where reading two pages is faster than descending an index.

Index scan walks the index, and for each matching entry visits the heap page for that TID. Each visit may be a random read, which is much more expensive than a sequential one on spinning disks and still costlier on SSDs. It wins when few rows match, and it can also return rows already in index order, which helps ORDER BY ... LIMIT.

Bitmap scan is the middle path. PostgreSQL first scans the index and builds an in-memory bitmap of heap pages that contain matches, then reads those pages once each, in physical order. It turns many scattered random reads into fewer, ordered ones, and it can combine several indexes with AND and OR. In a plan it appears as two nodes:

TEXT
Bitmap Heap Scan on orders  (cost=12.30..95.10 rows=410 width=40)
  Recheck Cond: (customer_id = 8)
  ->  Bitmap Index Scan on orders_customer_id_idx  (cost=0.00..12.20 rows=410 width=0)
        Index Cond: (customer_id = 8)

(Output shape is typical; the numbers vary with your data and settings.) Recheck Cond appears because a bitmap can be lossy: when memory is short it remembers only which pages might match, so each row on those pages is checked again against the condition.

A fourth variant, the index-only scan, answers a query entirely from the index without visiting the heap. It needs every selected column to be in the index and the page to be marked all-visible, which B-tree Indexes explains.

Why the planner sometimes ignores your index

New users are often puzzled: "I created an index and the plan still says Seq Scan." Usually the planner is right. Three factors drive the choice.

Selectivity is the fraction of rows a condition keeps. WHERE id = 5 on a primary key keeps one row in millions (very selective), so an index wins. WHERE status = 'delivered' when most orders are delivered keeps a large fraction, so reading the table once beats thousands of heap visits. The usual rule of thumb is that an index pays off when a query returns a few percent of the table or less, but the real threshold depends on the next factor.

Physical correlation is how closely the order of the rows on disk matches the order of the index. If the matching rows sit together on a few pages, an index scan visits few pages and is cheap. If they are scattered across the whole table, it visits many. PostgreSQL records this in pg_stats.correlation.

Cost settings encode your hardware. Reading a page sequentially costs seq_page_cost (1.0 by default) and a random read costs random_page_cost (4.0 by default, a figure tuned for spinning disks). On SSDs people commonly lower it to about 1.1 so the planner stops overpaying for random access.

The planner relies on statistics that ANALYZE collects (autovacuum runs it for you). With stale statistics it can pick a bad plan, which is the subject of Statistics and the Query Planner. SQLite keeps similar numbers in sqlite_stat1, and you can see them and the selectivity yourself:

SQL Selectivity and statistics ยท database: shop

Press Run (or Ctrl + Enter) to see the result here.

You will see that each status covers between 14 and 48 percent of the orders, and sqlite_stat1 reports 120 30: 120 rows, and on average 30 rows per distinct status. A condition keeping a fifth to nearly half of the table is a poor index candidate in PostgreSQL, where it would likely produce a bitmap or sequential scan. Compare a condition on a unique column, which keeps exactly one row per value. An index on status pays off only for the rare values (a status that applies to 1 percent of rows), and Partial and Expression Indexes shows how to index just those.

What every index costs

An index is not free, and the bill arrives on every write.

  • INSERT: PostgreSQL adds an entry to every index on the table. A table with seven indexes does eight writes (one heap row, seven index entries) for one insert.
  • UPDATE: PostgreSQL never changes a row in place. It writes a new version of the row (see MVCC: How PostgreSQL Keeps Versions). If the update changes an indexed column, or there is no room on the page for a HOT (heap-only tuple) update, every index gets a new entry too.
  • DELETE and old versions: dead index entries stay until VACUUM removes them.
  • Space and cache: indexes take disk, and indexes you rarely use still compete for memory.
  • Build time: creating an index on a big table takes a while and, without CONCURRENTLY, blocks writes (see Schema Changes and Migrations).

You can watch the count of structures grow in SQLite, which also updates each index on every write:

SQL More indexes, more to maintain ยท database: shop

Press Run (or Ctrl + Enter) to see the result here.

Before there are no indexes on orders (0), afterwards the three you made are listed, and one insert has to touch the table and all three. That is invisible with 120 rows and very visible with ten thousand inserts per second. The practical advice: index the columns your real queries filter, join and sort on, then use pg_stat_user_indexes to find indexes that are never used and drop them (see Index Maintenance and Bloat).

A decision checklist

When a query is slow, ask in this order:

  1. Does it return a small share of the rows? If it returns most of the table, no index will help.
  2. Is there an index whose leading column matches the filter or join? If not, consider one.
  3. Does the planner use it? Check with EXPLAIN (EXPLAIN and EXPLAIN ANALYZE). If not, look at statistics and at whether the query wraps the column in a function.
  4. Is the cost worth it? Weigh the write overhead against how often the query runs.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a PostgreSQL index entry store?

    An index maps key values to TIDs. The row itself stays in the heap, which is why a normal index scan visits heap pages after searching the index.
  2. 2. A query returns about 60 percent of a large table. Which plan is the planner most likely to choose?

    When a large share of rows match, visiting the heap through an index costs more than reading the table in order. Selectivity decides, not the mere existence of an index.
  3. 3. What does a bitmap heap scan do differently from a plain index scan?

    A bitmap scan turns scattered random reads into ordered page reads and can combine several indexes. Index-only scans are the ones that skip the heap.
  4. 4. A table has six indexes. What happens on a single INSERT?

    Every index must contain an entry for every live row, so each insert pays for each index. That is why unused indexes should be dropped.

Summary

  • A table is a heap of 8 kB pages; a row's address is its TID (page, slot), visible as ctid.
  • An index stores key values with TIDs. A lookup searches the index and then visits the heap.
  • The three main fetch strategies are sequential scan, index scan and bitmap scan; index-only scans skip the heap.
  • The planner chooses by estimated cost using selectivity, physical correlation, statistics and settings such as random_page_cost.
  • Every index adds work to every INSERT, most UPDATEs and to VACUUM, plus disk and memory.
  • Create indexes for real, selective queries, check them with EXPLAIN, and drop the unused ones.

Next: B-tree Indexes, the default index type and the one you will use most.