Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 90 ยท Indexes

BRIN, Hash and SP-GiST Indexes

Learn the specialist PostgreSQL index types: tiny BRIN indexes for time-series, hash for equality, SP-GiST for tries and points, and pgvector's HNSW and IVFFlat.

You now know the generalist, the B-tree, and the two flexible frameworks for many-valued and overlapping data, GIN and GiST. PostgreSQL has three more built-in index types that each do one thing unusually well: BRIN gives you an index a thousand times smaller than a B-tree for data that arrives in order, hash answers equality lookups on large keys, and SP-GiST indexes data that divides naturally into non-overlapping regions, such as text prefixes or points on a map. Beyond the built-ins, extensions add index types of their own, and the one you are most likely to meet today is pgvector, for similarity search over embeddings.

This is mostly a lesson about choosing: knowing what each type is for, and just as importantly when it is the wrong tool. All the index definitions here are read-only, because these structures are PostgreSQL-specific. Each type has a live stand-in built from ordinary SQL, so you can poke at the underlying idea in your browser. Earlier lessons give the background: How Indexes Work in PostgreSQL and GIN and GiST Indexes.

BRIN: summaries of block ranges

BRIN stands for Block Range INdex. Instead of storing one entry per row, it divides the table into ranges of adjacent heap pages (128 pages, or 1 MB, by default) and stores a tiny summary for each range, by default the minimum and maximum value of the column in those pages. A search checks the summaries and skips every range whose min/max cannot contain the value.

SQL
CREATE INDEX events_created_brin ON events USING brin (created_at);

-- Smaller block ranges give a finer, slightly bigger index
CREATE INDEX events_created_brin32 ON events USING brin (created_at)
  WITH (pages_per_range = 32);

That is why a BRIN index on a billion-row table can be a few hundred kilobytes where a B-tree needs tens of gigabytes: it stores one small summary per megabyte of table. It is also nearly free to maintain, because most inserts only extend the summary of the last range.

The catch is absolute: BRIN only works when the column's values are physically correlated with row position. Think of an append-only log where created_at always grows. Rows inserted on the same day sit in neighbouring pages, so each range covers a narrow slice of time. If the values are scattered randomly across the table, every range's min and max span nearly everything, and the index rules out nothing. BRIN is also lossy: it can only tell PostgreSQL which block ranges might hold matches, so the plan always shows a Bitmap Heap Scan that rechecks each row.

BRIN in one picture

Block range A run of neighbouring heap pages.
Min and max One tiny summary per range.
Skip Ranges that cannot match are never read.

It works when value order matches physical order.

1 / 2

The easiest way to feel this is to compute the summaries yourself. This stand-in treats every 10 consecutive orders as a "block range" and records the minimum and maximum of two columns: the order date, which grows steadily because orders were entered in sequence, and the customer id, which is unrelated to the order of entry:

SQL BRIN summaries by hand: correlated vs scattered ยท database: shop

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

The date ranges form a neat staircase: each block covers its own stretch of the year, so a search for June needs only 2 of the 12 ranges. The customer ranges all span roughly 1 to 34, so a search for customer 30 must read 10 of the 12 and skips almost nothing. That is the difference between a column BRIN suits and one it does not. (A real BRIN works on page ranges, not counts of rows, but the principle is identical.)

BRIN has a few options worth knowing. New block ranges are summarized lazily, by VACUUM or when you set autosummarize = on. Operator classes beyond the default min/max include minmax_multi_ops (PostgreSQL 14), which keeps several value intervals per range and tolerates loosely correlated data, and bloom_ops for equality on columns with no order at all. For a table of events, a good pattern is a B-tree on whatever you filter by exactly, plus a BRIN on the timestamp for range queries, as the Time-Series, Queues and Caching in PostgreSQL lesson shows.

Hash indexes

A hash index stores a 32-bit hash of the key and finds rows by hashing the search value, so it supports only equality (=). It cannot do ranges, sorting, ORDER BY or uniqueness, and it works on a single column only.

SQL
CREATE INDEX sessions_token_hash ON sessions USING hash (token);

SELECT * FROM sessions WHERE token = 'f1e2d3c4b5a6';   -- can use it
SELECT * FROM sessions WHERE token > 'f';              -- cannot

Hash indexes had a bad reputation because before PostgreSQL 10 they were not crash-safe. That was fixed, so today they are a legitimate option. Their one real advantage is that the stored entry is a fixed-size hash, not the key, so for long keys (URLs, long tokens, large text) the index can be smaller than a B-tree. In practice a B-tree is almost always just as fast, supports far more queries, and can enforce uniqueness, so you reach for hash only after measuring a benefit on equality-only workloads with big keys.

The mechanism is easy to model. This toy hash sorts product names into four buckets, and a lookup computes the bucket of the search value and reads only that bucket. Real hash functions spread keys far more evenly, but the shape is the same:

SQL A toy hash index: equality via buckets ยท database: shop

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

The 26 products split 6, 4, 9 and 7 across the buckets. The equality lookup reads bucket 1 only and finds Yoga Mat (id 23). The last query shows why hashing cannot do ranges: it just lists the names starting with Y (here only Yoga Mat), and two names that share a prefix (Chef Knife 20 cm and Camping Hammock) land in unrelated buckets, so no bucket order means "alphabetical".

SP-GiST: space-partitioned trees

SP-GiST (Space-Partitioned GiST) supports trees that split the data into non-overlapping regions, such as radix trees (tries) for strings, quadtrees and k-d trees for points. Unlike GiST, whose regions can overlap, SP-GiST regions never overlap, so each value belongs to exactly one branch. The trees are allowed to be unbalanced, which suits data that clusters unevenly.

SQL
-- Text prefixes: a radix tree over names
CREATE INDEX products_name_spgist ON products USING spgist (name);

SELECT name FROM products WHERE name ^@ 'Ca';          -- starts with "Ca"

-- Points: a quadtree
CREATE INDEX shops_location_spgist ON shops USING spgist (location);

SELECT name FROM shops WHERE location <@ box '((0,0),(10,10))';
SELECT name FROM shops ORDER BY location <-> point '(3,4)' LIMIT 5;   -- nearest neighbours

It also serves IP addresses (inet) and range types. It does not support unique constraints, but it is a good fit for large sets of text with shared prefixes, and for point data with uneven density. The trie idea is easy to see by grouping names by their growing prefixes:

SQL A trie in SQL: prefixes narrow the search ยท database: shop

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

Three names start with C. At depth 2 they split into Ca (2 names) and Ch (1), and at depth 3 into Cam, Cas and Che, one name each. A prefix search walks down these branches and ignores the rest, which is how an SP-GiST radix tree answers ^@ 'Ca' without looking at the other 24 names.

Vector indexes with pgvector

Embeddings from machine-learning models are long lists of numbers, and "find the items most similar to this one" is a nearest-neighbour search in hundreds or thousands of dimensions. The pgvector extension adds a vector type and two index types for it. Both are approximate: they return very close neighbours quickly instead of the exact closest ones, trading a little recall for large speed-ups.

SQL
CREATE EXTENSION vector;

CREATE TABLE documents (id bigserial PRIMARY KEY, body text, embedding vector(1536));

-- HNSW: a layered graph. Fast queries, slower build, more memory.
CREATE INDEX documents_embedding_hnsw
  ON documents USING hnsw (embedding vector_cosine_ops);

-- IVFFlat: clusters the vectors into lists. Build it after loading data.
CREATE INDEX documents_embedding_ivf
  ON documents USING ivfflat (embedding vector_cosine_ops) WITH (lists = 100);

SELECT id FROM documents ORDER BY embedding <=> '[0.12, -0.4, ...]' LIMIT 5;

The distance operator in the query must match the index's operator class: <-> for L2 distance (vector_l2_ops), <=> for cosine distance (vector_cosine_ops) and <#> for negative inner product (vector_ip_ops). HNSW usually gives the better speed-versus-accuracy trade and needs no training data, while IVFFlat builds faster and smaller but needs data present when you create it, and you tune how many lists to search per query. A full tour, including PostGIS for geographic data, is in pgvector and PostGIS.

Choosing an index type

You need Use Notes
Equality, ranges, sorting, uniqueness B-tree The default for good reason
Contains/overlaps on jsonb, arrays, text search GIN Read-heavy data
Ranges, geometry, exclusion, nearest neighbour GiST Regions may overlap
Huge append-only tables filtered by a correlated column BRIN Tiny, lossy, needs physical order
Equality on very long keys only Hash Measure first; B-tree is usually fine
Prefix trees, uneven point data SP-GiST Non-overlapping partitions
Nearest neighbours of embeddings HNSW / IVFFlat (pgvector) Approximate results

Start with a B-tree, and let a real slow query, shown by EXPLAIN, tell you when a specialist is worth its extra care. Once indexes exist they need looking after, which Index Maintenance and Bloat covers.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which column is the best fit for a BRIN index?

    BRIN stores min/max per block range, so it only helps when values correlate with physical row position. A steadily growing timestamp in an append-only table does.
  2. 2. What can a hash index do?

    A hash index stores hashes, so it only supports equality on a single column. Ranges, ordering and uniqueness need a B-tree.
  3. 3. Why does a BRIN scan always show a bitmap heap scan with a recheck?

    A block-range summary can only rule ranges out. Inside a range that might match, PostgreSQL must read the rows and test the condition itself.
  4. 4. Which statement about pgvector indexes is correct?

    HNSW and IVFFlat are approximate and come with the pgvector extension. A cosine index (vector_cosine_ops) serves the <=> operator, not <->.

Summary

  • BRIN keeps a min/max summary per block range. It is tiny and cheap, but only works for columns whose values follow physical row order, and it is lossy.
  • Hash indexes support only equality on one column. A B-tree is usually just as good; consider hash for very long keys after measuring.
  • SP-GiST indexes non-overlapping partitions: text prefix trees, quadtrees and k-d trees for uneven data.
  • pgvector adds approximate nearest-neighbour indexes: HNSW (better recall, slower build) and IVFFlat (needs data first, tunable lists), with operator classes matching <->, <=> and <#>.
  • Default to B-tree, add GIN or GiST for containment and overlap, and use the specialists when a measured query needs them.

Next: Index Maintenance and Bloat, where you learn to find unused indexes and keep the useful ones healthy.