18 Beyond the B-tree

Two indexes on the same column of the same two-million-row table. Both turn a 35,000-page sequential scan into a few hundred pages or less. One is an eighteen-hundredth the size of the other:

        relname        | pg_size_pretty
-----------------------+----------------
 events_created_brin   | 24 kB
 events_created_btree  | 43 MB

The small one is a BRIN index, and whether it’s brilliant or useless depends entirely on how your rows sit on disk. That’s the whole chapter in one example. Every index type answers one question. Ask it that question and it’s the fastest thing in the building. Ask it another and it’s dead weight you pay for on every write.

The B-tree answers “which rows have this value, in order?” Postgres ships five other index types:

As in the B-tree chapter, the evidence is the Buffers: line: 8 KB pages (Buffers are the evidence).

GIN is fast to search and expensive to update

A B-tree has one entry per row, which is useless when you search inside a value: a key in a jsonb document, a tag in an array, a word in a comment. A GIN (Generalized Inverted iNdex) stores one entry per distinct element, followed by the rows that contain it, like the index at the back of a book:

  rows                                 GIN index
  ────────────────────────────         ──────────────────────────────
  (0,1) {region: ams, status: ok}      "ams"     → (0,1) (0,7) ...
  (0,2) {region: iad, status: failed}  "failed"  → (0,2) (0,5) ...
  (0,3) {region: iad, status: ok}      "iad"     → (0,2) (0,3) ...
  ...                                  "ok"      → (0,1) (0,3) ...
                                       "region"  → every row
                                       "status"  → every row

The catch runs the other way: one row produces many entries, so GIN is fast to search and expensive to update.

For containment, jsonb_path_ops beats the default

payload holds documents like {"region": "syd", "status": "failed", "duration_ms": 4242}. Find one duration in one region:

select id from events
where payload @> '{"duration_ms": 4242, "region": "syd"}';

@> means “contains”. GIN has two operator classes for jsonb, and the choice matters:

The default indexes keys and values separately, so this query reads the lists for "region" and "duration_ms", which appear in every row. jsonb_path_ops (using gin (payload jsonb_path_ops)) hashes each value with its path, so duration_ms = 4242 is one rare element.

select lab.prove(
  'with jsonb_path_ops, the index reads about 121 pages for the same query',
  lab.node_pages($$ select id from events
                where payload @> '{"duration_ms": 4242, "region": "syd"}' $$,
             'Bitmap Index Scan') between 90 and 160);

The price: it serves containment and jsonpath (@>, @?, @@) but not key existence (? and friends). Keep the default only if you ask “does this key exist?”

 Bitmap Heap Scan on events
   Recheck Cond: (payload @? '$."duration_ms"?(@ == 4242)'::jsonpath)
   ->  Bitmap Index Scan on events_payload_pathops

 Gather
   Workers Planned: 2
   ->  Parallel Seq Scan on events
         Filter: (payload ? 'seen'::text)

select lab.prove(
  'the default jsonb_ops GIN index is about 20 MB',
  pg_relation_size('events_payload_gin') between 18e6 and 23e6);

select lab.prove(
  'with jsonb_ops, the index alone reads about 987 pages for 81 rows',
  lab.node_pages($$ select id from events
                where payload @> '{"duration_ms": 4242, "region": "syd"}' $$,
             'Bitmap Index Scan') between 850 and 1150);

select lab.prove(
  'the jsonb_path_ops index is about 14 MB',
  pg_relation_size('events_payload_pathops') between 12.5e6 and 16e6);

GIN doesn’t help unselective queries

An index is a shortcut to a few rows. payload @> '{"status": "failed", "region": "syd"}' matches about 100,000 events, 5% of the table, and they sat on 33,343 of its 35,173 pages (Heap Blocks: exact=33343). The “index scan” read nearly everything and was slower than the sequential scan it replaced. “Failures per region” wants a sequential scan, a summary table, or a partial B-tree on the slice you care about.

select lab.prove(
  'those rows sit on about 33,343 of the 35,173 heap pages (over 90 percent)',
  lab.node_sum($$ select count(*) from events
              where payload @> '{"status": "failed", "region": "syd"}' $$,
           'Bitmap Heap Scan', 'Exact Heap Blocks')
    > 0.9 * (select relpages from pg_class where relname = 'events'));

Arrays: spell it as containment

GIN works the same way on arrays: on a tags text[] column of projects, tags @> '{gdpr}' read 53 pages instead of 507. The trap is the spelling. 'gdpr' = any (tags) isn’t a GIN operator, so it’s a sequential scan. Write tags @> array['gdpr'] (or && for “any of”).

alter table projects add column tags text[] not null default '{}';
-- 1 to 4 random tags per project from a list of 20, plus 'gdpr' on 50 projects
-- (the lab has the exact update)
create index projects_tags_idx on projects using gin (tags);

 Bitmap Heap Scan on projects (actual ... rows=50.00 loops=1)
   Heap Blocks: exact=50
   Buffers: shared hit=53
   ->  Bitmap Index Scan on projects_tags_idx (actual ... rows=50.00 loops=1)
         Buffers: shared hit=3

 Seq Scan on projects
   Filter: ('gdpr'::text = ANY (tags))

select lab.prove(
  'with a GIN index on tags, the index reads 3 pages and the heap one page per match: 53 in all',
  lab.node_pages($$ select id from projects where tags @> '{gdpr}' $$, 'Bitmap Index Scan') <= 4
  and lab.buffers($$ select id from projects where tags @> '{gdpr}' $$) between 45 and 56);

select lab.prove(
  '''gdpr'' = any (tags) cannot use the GIN index: a sequential scan',
  lab.nodes($$ select id from projects where 'gdpr' = any (tags) $$) = '{Seq Scan}');

A full-text GIN search read 51 pages, not 6,671

Full-text search turns text into a tsvector, a sorted list of normalized words (lexemes: “The deploys failed” becomes 'deploy' 'fail'), and GIN indexes the lexemes. On a test table of a quarter-million short comments, a search for “deadlock” read 51 pages instead of all 6,671. The recipe is a stored tsvector column, a GIN index, and @@ to match. Parsing what users type (websearch_to_tsquery) and ranking (which reads every match) belong to Search without a search engine.

create table comments (
  id        bigint generated always as identity primary key,
  event_id  bigint not null references events (id),
  body      text not null,
  search    tsvector generated always as (to_tsvector('english', body)) stored
);
-- one per comment event: 249,934 comments of 6 to 15 words,
-- 49 of them mention "deadlock" (the lab has the generator)

create index comments_search_idx on comments using gin (search);

 Bitmap Heap Scan on comments (actual ... rows=49.00 loops=1)
   Heap Blocks: exact=49
   Buffers: shared hit=27 read=24
   ->  Bitmap Index Scan on comments_search_idx (actual ... rows=49.00 loops=1)
         Buffers: shared hit=2

select lab.prove(
  'without an index, a search reads every page of comments (about 6,700)',
  lab.buffers($$ select id, body from comments
                 where search @@ to_tsquery('english', 'deadlock') $$) between 6400 and 7000);

create index comments_search_idx on comments using gin (search);

select lab.prove(
  'with a GIN index, the search finds all 49 and the index reads under 5 pages',
  lab.node_sum($$ select id, body from comments where search @@ to_tsquery('english', 'deadlock') $$,
           'Bitmap Heap Scan', 'Actual Rows') = 49
  and lab.node_pages($$ select id, body from comments where search @@ to_tsquery('english', 'deadlock') $$,
                 'Bitmap Index Scan') < 5);

select lab.prove(
  'the full-text index is about 2.4 MB for a quarter-million comments',
  pg_relation_size('comments_search_idx') between 2.0e6 and 3.0e6);

The pending list makes one insert pay for many

GIN parks new entries in an unsorted pending list and merges them in bulk. The list is on by default (fastupdate) and grows to gin_pending_list_limit, 4 MB. Whichever insert overflows it pays to merge all four megabytes. The symptom: fast inserts, and the occasional one that takes hundreds of milliseconds. The fix: a smaller gin_pending_list_limit on that index, or fastupdate = off to pay a steady cost instead of a spiky one.

 version | pending_pages | pending_tuples
---------+---------------+----------------
       2 |            37 |           5000

select lab.prove(
  'after 5,000 inserts the pending list holds 5,000 tuples on a few dozen pages',
  (select pending_tuples = 5000 and pending_pages between 25 and 60
   from pgstatginindex('events_payload_pathops')));

select lab.prove(
  'every search now scans the pending pages too (121 index pages became about 158)',
  lab.node_pages($$ select id from events
                where payload @> '{"duration_ms": 4242, "region": "syd"}' $$,
             'Bitmap Index Scan')
    - :pages_before >= (select pending_pages - 2 from pgstatginindex('events_payload_pathops')));

pg_trgm makes a leading wildcard indexable

A B-tree is sorted from the start of the string, so at best it serves a prefix like like 'user42%' (and only with the right operator class, as the next section shows), never like '%r4242@%'. The pg_trgm extension makes substring search indexable by breaking strings into trigrams, every three-character sequence (show_trgm('user4242')):

 {"  u"," us",242,"42 ",424,er4,r42,ser,use}

A string containing r4242@ must contain that fragment’s trigrams, so the index intersects their lists and rechecks the few candidates. Without it, searching by an email fragment read all 1,126 pages of users. With it:

create index users_email_trgm_gin on users using gin (email gin_trgm_ops);

 Bitmap Heap Scan on users (actual time=0.025..0.025 rows=1.00 loops=1)
   Recheck Cond: (email ~~* '%R4242@%'::text)
   Buffers: shared hit=10

Ten pages, and that was ilike (~~*): the same index serves case-insensitive matches and regular expressions. A pattern needs three fixed characters to have a trigram to look up.

Prefix search needs the right operator class

Even like 'user4242@%' couldn’t use a plain B-tree on email. Under a non-C collation like this database’s en_US.utf8, B-tree order isn’t byte order, so a prefix isn’t guaranteed to be one contiguous range. Build the index with text_pattern_ops (byte-wise order) and the prefix becomes a range:

 Index Scan using users_email_pattern on users (actual ... rows=1.00 loops=1)
   Index Cond: ((email ~>=~ 'user4242@'::text) AND (email ~<~ 'user4242A'::text))

That index can’t serve <, >, or order by in the database collation. Need both? Build both, or use the C collation on the column.

GIN filters trigrams; GiST ranks by similarity

pg_trgm also has a GiST operator class. For like and regex, GIN wins outright: the GiST index was three times the size (11 MB against 3,504 KB) and read 163 pages where GIN read 10.

But GiST does one thing GIN can’t: return rows in order of similarity (order by email <-> 'usr4242@exmaple.com' limit 5), the “did you mean” query. That’s a nearest-neighbor search, walking the tree in distance order (PostGIS does the same for geography). GIN for filtering, GiST for nearest-match ordering.

select email, round((email <-> 'usr4242@exmaple.com')::numeric, 3) as dist
from users
order by email <-> 'usr4242@exmaple.com'
limit 5;

         email         | dist
-----------------------+-------
 user4242@example.com  | 0.481
 user42424@example.com | 0.536
 user24242@example.com | 0.536
 ...

 Limit (actual time=14.166..14.184 rows=5.00 loops=1)
   Buffers: shared hit=1427
   ->  Index Scan using users_email_trgm_gist on users (actual rows=5.00 loops=1)
         Order By: (email <-> 'usr4242@exmaple.com'::text)

select lab.prove(
  'trigram GiST on email is about 11 MB, over 2.5 times the GIN',
  pg_relation_size('users_email_trgm_gist') between 10e6 and 13.5e6
  and pg_relation_size('users_email_trgm_gist')::numeric
      / pg_relation_size('users_email_trgm_gin') > 2.5);

select lab.prove(
  'with GiST, the similarity search is an index scan ordered by distance',
  lab.nodes($$ select email from users order by email <-> 'usr4242@exmaple.com' limit 5 $$)
    = '{Limit,Index Scan}');

GiST indexes values that have no order

A B-tree needs a total order, and many types don’t have one: which comes first, 9:00 to 17:00 or 12:00 to 13:00? GiST (Generalized Search Tree) indexes them anyway. Each internal entry stores a bounding value covering everything beneath it, and a search descends into every child whose bound could match.

Its best-known job is enforcing “no two of these may overlap”, the exclusion constraint, which builds a GiST index to check every insert against. Say projects can declare deploy freezes, at most one at a time per project:

create extension if not exists btree_gist;  -- lets GiST compare plain bigints

create table deploy_freezes (
  id          bigint generated always as identity primary key,
  project_id  bigint not null references projects (id),
  during      tstzrange not null,
  reason      text not null,
  exclude using gist (project_id with =, during with &&)
);

That index hides a lesson. With 480,000 freezes loaded, “which projects were frozen at this moment?” read 7,188 pages through the constraint’s index, which leads with project_id: more than a sequential scan’s 4,548. A GiST index on during alone needed 460, only 7 of them in the index. The index behind a constraint isn’t automatically a good index for your queries.

 Bitmap Heap Scan on deploy_freezes (actual time=81.942..84.276 rows=470.00 ...)
   Buffers: shared hit=35 read=7153
   ->  Bitmap Index Scan on deploy_freezes_project_id_during_excl (actual ...)
         Index Cond: (during @> (now() - '100 days'::interval))
         Buffers: shared read=6735

 Bitmap Heap Scan on deploy_freezes (actual time=1.418..9.701 rows=470.00 loops=1)
   Buffers: shared read=460
   ->  Bitmap Index Scan on deploy_freezes_during_idx (actual rows=470.00 loops=1)
         Buffers: shared read=7

do $$
begin
  insert into deploy_freezes (project_id, during, reason)
  values (4242, tstzrange('2026-12-31', '2027-01-02'), 'new year');
  raise exception 'NOT PROVED: the overlapping freeze was accepted';
exception when exclusion_violation then
  perform set_config('lab.freeze_rejected', 'yes', false);
end $$;
select lab.prove(
  'an overlapping freeze for the same project is rejected (exclusion_violation)',
  current_setting('lab.freeze_rejected', true) = 'yes');

select lab.prove(
  'the constraint''s index, led by project_id, reads more pages than the sequential scan',
  lab.buffers($$ select project_id, reason from deploy_freezes
                 where during @> now() - interval '100 days' $$) > :seq_pages);

create index deploy_freezes_during_idx on deploy_freezes using gist (during);

select lab.prove(
  'a GiST index on the range alone answers in about 7 index pages',
  lab.node_pages($$ select project_id, reason from deploy_freezes
                where during @> now() - interval '100 days' $$, 'Bitmap Index Scan') < 20);

You’ll rarely need SP-GiST

Where SP-GiST fits, a B-tree or GiST usually does about as well, and you already know how those behave. SP-GiST (space-partitioned GiST) is for data that splits into non-overlapping regions (prefixes, points, IP networks), so a search follows one path. On users.email it answered a starts-with query (email ^@ 'user4242@') in 5 pages from a 4,672 KB index, about a B-tree’s size. For inet containment and ranges it’s an alternative to GiST; benchmark both.

BRIN keeps one summary per range of pages

Back to the opening. events is append-only: rows arrive in created_at order and never move. pg_stats.correlation measures how well a column’s order matches the physical row order: 1 for created_at and id, about 0.003 for project_id.

A BRIN (Block Range INdex) cashes in on it. It stores one summary per range of pages_per_range pages (128 by default): the smallest and largest value. Think of labels on moving boxes. A query for one day skips every box whose label can’t match, opens the one or two that might, and checks every row inside.

  heap pages     0..127   128..255  256..383  ...  34944..35071 35072..
               ┌────────┬─────────┬─────────┬─────┬────────────┬──────┐
  BRIN entry   │ Oct 06 │ Oct 07  │ Oct 08  │ ... │  Oct 04    │Oct 05│
               │ -Oct 07│ -Oct 08 │ -Oct 09 │     │  -Oct 05   │-06   │
               └────────┴─────────┴─────────┴─────┴────────────┴──────┘
  query "May 1": skip, skip, skip, ..., read 2 ranges, ..., skip

Each label covers about a day and a third of events. About 275 labels for 35,000 pages: hence 24 KB.

A thousandth of the size, nearly the same pages

A per-kind summary of one day of events:

The B-tree wins on pages, narrowly. But it’s 1,800 times larger than the default BRIN, competes with your data for cache, and every insert descends it. BRIN at 32 pages per range comes within 20 pages of it at under a nine-hundredth of the size. Smaller ranges stop paying: at 8 pages per range, the index itself read 26 pages instead of the 5 it read at 32 pages per range, nearly cancelling the 24 heap pages it saved.

 HashAggregate (actual time=2.638..2.640 rows=5.00 loops=1)
   Buffers: shared hit=261
   ->  Bitmap Heap Scan on events (actual ... rows=5480.00 loops=1)
         Rows Removed by Index Recheck: 9078
         Heap Blocks: lossy=256
         ->  Bitmap Index Scan on events_created_brin (actual rows=2560.00 loops=1)
               Buffers: shared hit=5

 blknum |                           value
--------+------------------------------------------------------------
      0 | {2025-10-06 00:00:15.768+00 .. 2025-10-07 07:52:39.504+00}
    128 | {2025-10-07 07:52:55.272+00 .. 2025-10-08 15:46:06.312+00}
    ...

select lab.prove(
  'with BRIN (128 pages per range), the one-day summary reads about 261 pages',
  lab.buffers(:'day_query') between 200 and 320);

select lab.prove(
  'BRIN at 32 pages per range gets within 20 pages of the B-tree',
  :brin32_pages - :btree_pages <= 20);

select lab.prove(
  'the B-tree is over 1,000 times larger than the BRIN (about 1,800)',
  pg_relation_size('events_created_btree')::numeric / pg_relation_size('events_created_brin') > 1000);

select lab.prove(
  'the BRIN node''s "rows" is ten per matching page, not a row count',
  lab.node_sum(:'day_query', 'Bitmap Index Scan', 'Actual Rows')
    = 10 * lab.node_sum(:'day_query', 'Bitmap Heap Scan', 'Lossy Heap Blocks'));

BRIN is useless without physical order

On project_id, whose correlation is zero, every box holds nearly every project, so every box “might match”. Force a BRIN index there and it reads every page of the table anyway (Buffers: shared hit=50 read=35266).

Use BRIN for columns that track insertion order: timestamps on append-only tables, sequence ids, log offsets (Partition for the delete pairs it with time partitions). Protect the order: rows moved by updates, backfilled old data, and new rows reusing freed space all widen the labels until the index stops pruning.

A hash index wins only on equality over long keys

Use a hash index for equality on long random values like tokens and content hashes. Everywhere else, use a B-tree.

A hash index stores a 32-bit hash of each key and supports exactly one operator: =. No ranges, ordering, uniqueness, or index-only scans. In exchange, its size doesn’t depend on the key’s width. On a 128-character API key, the B-tree was 16 MB and the hash index 4,112 KB, and a lookup touched 3 pages instead of 5. On email, about 20 characters, the hash index was the same 4,112 KB and the B-tree smaller. Hash indexes have been crash-safe since PostgreSQL 10; their bad reputation is older.

alter table users add column api_key text;
-- 128 hex characters
update users set api_key = encode(sha512(('key' || id)::bytea), 'hex');
create index users_api_key_btree on users (api_key);
create index users_api_key_hash  on users using hash (api_key);

select lab.prove(
  'on the long key, the hash index is about a quarter of the B-tree',
  pg_relation_size('users_api_key_hash')::numeric / pg_relation_size('users_api_key_btree')
    between 0.2 and 0.3);

select lab.prove(
  'the hash index size does not depend on key width: same size on email',
  pg_relation_size('users_email_hash') = pg_relation_size('users_api_key_hash'));

select lab.prove(
  'a hash lookup on api_key touches 3 pages (metapage, bucket, heap)',
  lab.buffers($$ select id from users where api_key = encode(sha512('key4242'::bytea), 'hex') $$) = 3);

The operator picks the index type

Whichever you pick, measure pages before and after. Every one of these, GIN most of all, makes writes more expensive, so keep only the ones that earn an order of magnitude.

The short version

• GIN indexes the elements inside a value. Fast to search, expensive to update; spiky insert latency means the pending list.
• For jsonb containment use jsonb_path_ops: 121 index pages instead of 987. GIN can’t serve payload->>'key' = 'x'.
• For like '%x%' use a trigram GIN index; trigram GiST only for similarity ordering.
• GiST handles overlap and distance. The index behind a constraint isn’t automatically a good one for your queries.
• BRIN on a naturally ordered column is tiny (24 KB against a 43 MB B-tree) and nearly as good for ranges; on an uncorrelated column it reads the whole table.
• Hash indexes are worth it only for equality on long keys.
• Any index helps only selective queries: a GIN lookup matching 5% of the rows still read 95% of the pages.

Further reading

• Index Types, PostgreSQL documentation. The official overview of every access method and its operators.
• GIN Indexes, GiST Indexes, SP-GiST Indexes, BRIN Indexes, and Hash Indexes, PostgreSQL documentation. One reference page per type, including the built-in operator classes.
• src/backend/access/brin/README, PostgreSQL source. How the range map and summaries are laid out, and why a summarizing index can be so small.
• pg_trgm, PostgreSQL documentation. Trigram operators, similarity thresholds, and the GIN and GiST operator classes.
• jsonb Indexing, PostgreSQL documentation. jsonb_ops versus jsonb_path_ops, with the operators each supports.
• Operator Classes and Operator Families, PostgreSQL documentation. Where text_pattern_ops and friends are explained.