Index types

Article.

PostgreSQL has six built-in index access methods: B-tree, Hash, GIN, GiST, SP-GiST and BRIN. Choosing between them is not a matter of taste. An index can only serve the operators its operator class supports, so the first question is which operator the query uses, and the second is what the index costs in space and in writes.

Which index can serve a given operator, at what size and write cost? Every number below is measured on PostgreSQL 18.4, on a 2,000,000-row table whose heap is 447 MB.

The capability matrix, from the server

The server reports what each access method can do:

SELECT amname,
       pg_indexam_has_property(a.oid, 'can_order')     AS ord,
       pg_indexam_has_property(a.oid, 'can_unique')    AS uniq,
       pg_indexam_has_property(a.oid, 'can_multi_col') AS multi,
       pg_indexam_has_property(a.oid, 'can_exclude')   AS excl,
       pg_indexam_has_property(a.oid, 'can_include')   AS incl
FROM pg_am a WHERE amtype = 'i';

 amname | ord | uniq | multi | excl | incl
 brin   | f   | f    | t     | f    | f
 btree  | t   | t    | t     | t    | t
 gin    | f   | f    | t     | f    | f
 gist   | f   | f    | t     | t    | t
 hash   | f   | f    | f     | t    | f
 spgist | f   | f    | f     | t    | t

Three facts worth remembering from it. Only B-tree can be UNIQUE and only B-tree returns rows in order. Hash and SP-GiST are single-column only. INCLUDE (covering columns) works on B-tree, GiST and SP-GiST.

What each serves

What each cost here

B-tree, the default

Sorted keys in a balanced tree of 8 kB pages, with duplicates compressed since PostgreSQL 13 (How a B-tree index works has the mechanism). It serves equality, ranges, IS NULL/IS NOT NULL, ORDER BY and MIN/MAX without a sort, and it is the only type that enforces UNIQUE.

Where B-tree surprises people

• LIKE 'abc%' does not use it under a non-C collation. The database here is en_US.utf8, and the prefix search ran a sequential scan. An index with text_pattern_ops turns it into a range:

  text Wrap Copy

  Index Scan using ix_tok_pattern on ix
    Index Cond: ((token ~>=~ 'abc'::text) AND (token ~<~ 'abd'::text))

• An entry is capped at 2,704 bytes, a third of a page. Indexing a long text failed with index row size 6416 exceeds btree version 4 maximum 2704; index md5(col) instead, or use a hash index for equality.

• The left-prefix rule is no longer absolute. PostgreSQL 18’s skip scan used an index on (a, b) for WHERE b = 123456 when a had four distinct values: Index Searches: 6, 22 buffers. It does one descent per value of a, so it helps only when the leading column has few distinct values.

Hash

Stores a 32-bit hash code per row, so the index size does not depend on the key’s length. That is its only advantage, and it cuts both ways: on a bigint the hash index was larger than the B-tree (64 MB against 43 MB) and slower to build; on a 64-character token it was a third of the size (64 MB against 182 MB).

It supports = only: no ranges, no ordering, no UNIQUE, no multicolumn, no index-only scans. It has been WAL-logged and crash-safe since PostgreSQL 10; older advice to avoid it dates from before that. Use it for equality lookups on long keys (URLs, tokens) after measuring.

GIN: an inverted index

GIN indexes the elements inside a value: array items, jsonb keys and values, full-text lexemes, trigrams. Each element maps to a compressed posting list of rows. It is what makes “documents containing X” fast.

CREATE INDEX ON events USING gin (metadata);                -- jsonb_ops
CREATE INDEX ON events USING gin (metadata jsonb_path_ops); -- smaller, @> only
CREATE INDEX ON articles USING gin (to_tsvector('english', body));
CREATE INDEX ON users USING gin (name gin_trgm_ops);        -- LIKE '%x%', pg_trgm

The operator must apply to the indexed column

WHERE doc -> 'tags' ? 't3'          Parallel Seq Scan
WHERE doc @> '{"tags": ["t3"]}'     Bitmap Index Scan on ix_doc_gin_path

Both ask the same question. The first applies ? to doc -> 'tags', which is not the indexed expression, so the index on doc cannot help. Rewrite as containment on doc, or index the expression (doc -> 'tags').

jsonb_path_ops hashes whole paths instead of indexing keys separately, so it is smaller and more selective for containment, and useless for ?. Here it was 125 MB against 146 MB and built in a third of the time.

Why GIN writes are expensive, and fastupdate

One row adds an entry for every element it contains. To soften that, fastupdate (on by default) appends new entries to an unsorted pending list and merges it into the main tree later: during VACUUM or autoanalyze, or by whichever insert finds it over gin_pending_list_limit (4 MB). Every search also scans the pending list.

200,000 inserts, best of three runs:

Two lessons. The cost of an index depends on what it is on: a sequential bigint added 36%, a random text key more than tripled the insert time, and GIN almost quintupled it. And fastupdate halved GIN’s total cost, but by moving it into flushes: the insert that triggers a merge pays for everyone, which is the periodic latency spike on GIN tables. fastupdate = off gives slower, predictable inserts.

GiST: overlap, containment, distance

A balanced tree in which each node stores a bounding key, a box or range covering everything below it. Searches descend into every child whose key might match, so it serves overlap (&&), containment, and nearest-neighbour ordering (ORDER BY geom <-> point LIMIT k), which GIN cannot. Keys can be lossy, in which case rows are rechecked against the heap. PostGIS and range types are built on it.

Exclusion constraints

CREATE EXTENSION btree_gist;     -- without it: "data type integer has no
                                 -- default operator class for access method gist"
ALTER TABLE bookings ADD EXCLUDE USING gist (room_id WITH =, period WITH &&);
-- second overlapping booking for room 1:
-- ERROR: conflicting key value violates exclusion constraint

The database refuses overlapping bookings for one room, which no UNIQUE can express and an application-level check cannot do without a race. The room_id WITH = part needs btree_gist, because plain integers have no GiST operator class.

GiST degrades when keys overlap heavily (wide ranges, large polygons): every search must descend into many branches.

SP-GiST: partitioned space

Space-partitioned trees: quad-trees and k-d trees for points, radix tries for text, trees for IP ranges. Unlike GiST, partitions do not overlap, so a search follows fewer paths.

• On points it was smaller than GiST (103 MB against 127 MB) and served nearest-neighbour ordering: Index Scan using ix_p_spgist, Order By: (p <-> '(500,500)'::point).
• On text it serves prefix search with ^@ (starts_with), regardless of collation. For random 64-character tokens it was 199 MB, larger than the B-tree: radix tries pay off on keys with shared prefixes (URLs, paths).

Single column only, no UNIQUE. Measure it against GiST for your data.

BRIN: a summary per block range

BRIN stores, for each range of pages_per_range heap pages (128 by default, 1 MB of table), the minimum and maximum value. A query skips ranges whose summary cannot match and reads the rest in full. It is always lossy: every row in a candidate range is rechecked.

It works only when the column’s order matches the physical order of rows, which pg_stats.correlation measures. The same one-hour query on the same data:

Ordered, the 32 kB BRIN index read 2 MB of table. Shuffled, it read the whole table, as much as a sequential scan, plus the index. Append-only events, logs and metrics correlate naturally; bulk updates or backfills destroy it.

• New ranges are not summarized until VACUUM or brin_summarize_new_values() runs, so they are always scanned. Create the index WITH (autosummarize = on) for append-heavy tables.
• minmax_multi_ops (PostgreSQL 14) keeps several ranges per block, which tolerates a few outliers; bloom_ops serves equality on unordered data.
• PostgreSQL 16 lets an update of BRIN-indexed columns stay HOT, and 17 builds BRIN in parallel.

Beyond the six

• pgvector adds HNSW and IVFFlat for embeddings; the operator class must match the distance operator (<->, <=>, <#>) or the index is unused (pgvector in production).
• btree_gin / btree_gist add scalar operator classes so one GIN or GiST index can combine a scalar column with an array or range.
• bloom (contrib) answers equality on any subset of many columns.
• Partial, covering and expression indexes are options on an index, not types (How a B-tree index works, Why your index is not being used).

Where it breaks in production

GIN pending-list spikes

p99 insert latency jumps every few minutes on a table with a GIN index on jsonb: one insert in thousands merges the 4 MB pending list. Lower gin_pending_list_limit for smaller, more frequent merges, let autovacuum flush it more often, or turn fastupdate off and accept slower inserts. pgstatginindex() shows the pending pages.

A trigram index on short patterns

pg_trgm splits text into three-character pieces. ILIKE '%ab%' has no complete trigram, so the GIN index cannot narrow anything and scans itself in full. Enforce a minimum search length of three characters.

BRIN after a backfill

A BRIN index on created_at served fast range queries until a backfill inserted a year of old events at the end of the table. Every block range now spans the whole year, and queries read everything. Check pg_stats.correlation; rebuild with CLUSTER or pg_repack, or switch to minmax_multi_ops.

An exclusion constraint added to a large table

Adding EXCLUDE USING gist builds the index and checks every pair under an ACCESS EXCLUSIVE lock. On a large bookings table that is minutes of downtime. Plan it like any blocking migration (Zero-downtime migrations).

The trade not taken

A GIN index on a whole jsonb column is the generic answer, and often the wrong one. If queries filter on one or two known keys, a B-tree expression index such as ((doc ->> 'user_id')::int) is smaller, cheaper to write, and supports ranges and ordering; GIN earns its cost when the keys queried are not known in advance.

The same reasoning applies to full text. GIN with tsvector covers search inside the database with transactional consistency; relevance tuning, typo tolerance, facets and large corpora are where Elasticsearch or OpenSearch take over, at the price of a second system to keep in sync.

Related

• How a B-tree index works - how a B-tree works; composite, partial, covering
• Why your index is not being used - the planner’s side
• Reading a query plan - reading the plans above
• PostgreSQL architecture - HOT updates and VACUUM
• MongoDB — Indexes - MongoDB’s index types
• Elasticsearch — Inverted Index Fundamentals - an inverted index at scale