Index Types¶

What an index is, and what it costs¶

An index is a separate data structure that maps values of one or more columns to the locations of the rows containing them, so a query can find rows without reading the whole table. Every index is a trade:

All plans and sizes on this page come from one PostgreSQL 16.2 table of 2 million orders (233 MB): id, customer_id (random, ~96,000 distinct values), status (49% paid, 34% new, 16% shipped, 1% cancelled), created_at (increasing with id), amount, email, and a JSONB attrs column.

B-tree: the default¶

CREATE INDEX without USING builds a B-tree (a B+Tree — see B+Tree Index). It supports =, <, <=, >, >=, BETWEEN, IN, IS NULL, prefix LIKE 'abc%' (with the right collation or text_pattern_ops), and returns rows in sorted order, so it can also satisfy ORDER BY and min/max without sorting.

Without and with an index on customer_id:

SELECT * FROM orders WHERE customer_id = 4242;      -- 29 matching rows

no index:   Parallel Seq Scan, Rows Removed by Filter: 666657 (per worker × 3)
            Buffers: 29,850 pages read            Execution Time: 45.570 ms

B-tree:     Bitmap Index Scan on orders_customer  (Buffers: 3 index pages)
            Bitmap Heap Scan, Heap Blocks: exact=29
            Buffers: 32 pages                     Execution Time: 0.085 ms

29,850 pages versus 32: the index reads 3 index pages to find the 29 row locations, then one heap page per row. ~540x faster, and the gap grows with the table.

How the planner reaches rows: four scan types¶

As more rows match, random heap fetches lose to sequential reading:

At 5%, the index already sends the query to 97% of the table's pages, because customer_id values are scattered randomly across the table (its correlation with physical order is −0.006): each page contains a few matching rows. The index stops helping well before most rows match. Had the column been correlated with physical order (like created_at or id, correlation 1.0), the matching rows would sit on 5% of the pages.

Composite indexes¶

An index on (customer_id, created_at) is sorted by customer_id, then by created_at within each customer. It can serve:

Measured:

WHERE customer_id = 4242 AND created_at >= '2024-06-01'
  Bitmap Index Scan on orders_cust_created
    Index Cond: ((customer_id = 4242) AND (created_at >= ...))   15 rows, 0.035 ms

WHERE created_at >= '2024-06-01' AND created_at < '2024-06-02'    (second column only)
  Parallel Seq Scan on orders                                      index not used

Rules for column order:

1. Equality columns first, then the range or sort column. In (customer_id, created_at), the index jumps to one customer and scans a contiguous range of dates. In (created_at, customer_id), the range on dates comes first and customer_id can only filter within that range.
2. A query must constrain a leading prefix to seek. (PostgreSQL 18 adds "skip scan" for some cases where the leading column has few distinct values; MySQL and Oracle have had variants.)
3. An index on (a, b) makes a separate index on (a) redundant.

Expression indexes¶

An index on a column is useless for a condition on a function of the column:

WHERE lower(email) = 'user4242@ex.com'      with index on (email)
  Parallel Seq Scan, Rows Removed by Filter: 666666 ×3     125.8 ms

CREATE INDEX ON orders (lower(email));
  Index Scan using orders_lower_email                       0.034 ms

The same applies to casts, date_trunc(...), arithmetic on the column, or comparing a column to a value of a different type that forces a conversion. Write the condition so the indexed expression appears exactly, or index the expression.

Partial indexes¶

Index only the rows a query cares about:

CREATE INDEX orders_cancelled ON orders (created_at) WHERE status = 'cancelled';

The partial index answers WHERE status = 'cancelled' AND created_at > '2024-09-01' (5,946 rows) in 2.4 ms, and inserts or updates of non-cancelled rows never touch it. Typical uses: "pending" items in a queue table, non-deleted rows under soft delete (WHERE deleted_at IS NULL), and partial unique indexes (UNIQUE (email) WHERE deleted_at IS NULL).

Covering indexes and index-only scans¶

If every column a query needs is in the index, the heap can be skipped:

CREATE INDEX orders_cust_cover ON orders (customer_id) INCLUDE (amount);

SELECT customer_id, amount FROM orders WHERE customer_id BETWEEN 4000 AND 4100
  Index Only Scan using orders_cust_cover   (2,056 rows)
    Heap Fetches: 0
    Buffers: 12 pages                        Execution Time: 0.144 ms

2,056 rows from 12 pages: without the covering column, the same query would touch roughly one heap page per row. INCLUDE columns are stored in leaf entries but not in the sort key, so they don't widen inner pages or affect uniqueness.

The catch is Heap Fetches. MVCC visibility lives in the heap, so an index-only scan may skip the heap only for pages the visibility map marks all-visible — which VACUUM maintains. On a table with many recent writes and lagging vacuum, an "index only" scan fetches most rows from the heap anyway. Heap Fetches: 0 here is because the table had just been vacuumed.

Unique indexes¶

UNIQUE and PRIMARY KEY constraints are enforced by unique B-tree indexes: an insert checks for an existing live entry with the same key and waits if a concurrent uncommitted transaction inserted one (to see whether it commits). This is the only fully reliable way to enforce uniqueness under concurrency — checking with a SELECT before inserting is a write-skew race (see Isolation Levels and Anomalies). NULLs are distinct from each other by default, so a unique column can hold many NULLs (NULLS NOT DISTINCT in PostgreSQL 15+ changes that).

Hash indexes¶

CREATE INDEX ... USING hash stores a 32-bit hash of the value; it supports only equality, no ranges, no ordering, no uniqueness, no multi-column keys. Since PostgreSQL 10 it is WAL-logged and crash-safe. It can be smaller than a B-tree for long keys (it stores 4-byte hashes, not the values) but is rarely worth choosing over a B-tree. See Hash Tables and Hash Indexes for hash index structures in general.

GIN: inverted indexes¶

A GIN (generalized inverted index) indexes the elements inside a value: words in a document, keys and values inside JSONB, elements of an array. It maps each element to a sorted list (posting list) of rows containing it — the structure behind every search engine.

CREATE INDEX orders_attrs ON orders USING gin (attrs jsonb_path_ops);
SELECT count(*) FROM orders WHERE attrs @> '{"vip": true, "channel": "app"}';

Bitmap Index Scan on orders_attrs   (13,333 rows; index Buffers: 192 pages)
Bitmap Heap Scan ...                Execution Time: 32.8 ms

GIN inserts are expensive — one row adds many posting-list entries — so GIN uses a pending list (fastupdate): new entries are appended to an unsorted list and merged into the main index in bulk by VACUUM or when the list grows past gin_pending_list_limit. Reads must also scan the pending list, so a large one slows queries.

GiST and SP-GiST¶

GiST (generalized search tree) is a framework for balanced trees over data that has no total order but can be bounded: geometric shapes (R-tree-like bounding boxes in PostGIS), ranges (tsrange overlap &&), nearest-neighbor search (ORDER BY location <-> point LIMIT 10), and exclusion constraints (no two bookings for the same room overlap). SP-GiST supports space-partitioning structures such as quadtrees, k-d trees, and radix tries, for data with natural non-overlapping partitions (IP addresses, phone-number prefixes).

BRIN: block range indexes¶

A BRIN index stores, for each range of table blocks (128 pages by default), only the minimum and maximum value of the column. A query skips every block range whose [min, max] cannot contain matches.

BRIN works only when the column's values are correlated with physical row order — append-only time series, log tables, IDs from a sequence. created_at here increases with insertion order, so each block range covers a narrow time window. On a randomly distributed column like customer_id, every block range would span almost the full value range and BRIN would skip nothing.

Choosing¶

When not to index: small tables (a seq scan of a few pages is already cheap); columns where most queries match a large fraction of rows (status with 4 values, unless partial); write-heavy tables where the index is never used for reads — find those with pg_stat_user_indexes.idx_scan = 0.

Index maintenance¶

• Bloat: dead entries and half-empty pages accumulate under updates and deletes; VACUUM removes dead entries but does not merge pages. REINDEX INDEX CONCURRENTLY (PostgreSQL 12+) rebuilds without blocking writes.
• Building on a live table: CREATE INDEX blocks writes (SHARE lock) for the whole build; CREATE INDEX CONCURRENTLY doesn't, but takes longer, cannot run in a transaction, and leaves an INVALID index behind if it fails — check pg_index.indisvalid and drop it.
• Statistics: after creating an expression index, run ANALYZE so the planner gathers statistics on the expression.

Common pitfall¶

Creating an index on (a, b, c) and later adding queries that filter on b and c without a, or on lower(a), or comparing a to a differently typed parameter. Nothing fails: the query silently falls back to a sequential scan, as measured above for both the second-column-only query and the lower(email) query (125 ms instead of 0.03 ms). The index looks fine in the schema and is useless for the new query. Check every new hot query with EXPLAIN (ANALYZE, BUFFERS) and confirm which index — if any — it actually uses.