Hash Indexes vs B-Tree for Equality #

A pages table keys rows by URL — averaging 180 characters. The B-tree on that column is 4.8 GB, larger than half the table, and every lookup is an exact-match query; nothing ever ranges or sorts by URL. A hash index on the same column is 1.1 GB. Whether that saving is worth having depends on what else the column is used for, because hash indexes give up nearly everything a B-tree offers besides equality.

Access-method trade-offs are summarised in BRIN and hash indexes. This page is the concrete comparison for equality workloads.

The Index Condition #

A hash index stores a 32-bit hash of each key in buckets, with the row pointer. A lookup hashes the search value, reads one bucket, and rechecks the actual value against the heap row. The consequences:

Since PostgreSQL 10 hash indexes are WAL-logged, crash-safe and replicated, which is what made them a real option. Before that they were not recommended, and much of the advice on the internet still reflects that era.

The comparison is therefore narrow: hash wins when keys are long, the workload is equality-only, and you do not need uniqueness, ordering or index-only scans on that column. When keys are short — integers, UUIDs stored as uuid — a B-tree is about the same size and strictly more capable.

Hash versus B-tree on a 180-character key A comparison table. Both support equality lookups. Only the B-tree supports ranges, ordering, uniqueness, multicolumn keys and index-only scans. The hash index is 1.1 gigabytes against the B-tree's 4.8 gigabytes for the same 34 million rows. hash B-tree equality lookup yes yes range and ORDER BY no yes unique constraint no yes multicolumn no yes index-only scan no yes size (34M long keys) 1.1 GB 4.8 GB hash trades every capability except equality for size

Annotated EXPLAIN Evidence #

CREATE INDEX pages_url_btree ON pages (url);
CREATE INDEX pages_url_hash  ON pages USING hash (url);

SELECT indexrelid::regclass, pg_size_pretty(pg_relation_size(indexrelid))
FROM pg_index WHERE indrelid = 'pages'::regclass;
   indexrelid    | pg_size_pretty
-----------------+----------------
 pages_url_btree | 4823 MB
 pages_url_hash  | 1104 MB

Equality lookup with each:

-- B-tree
Index Scan using pages_url_btree on pages  (actual time=0.04..0.04 rows=1 loops=1)
  Index Cond: (url = 'https://example.com/a/very/long/path?with=params&more=1'::text)
  Buffers: shared hit=5

-- hash
Index Scan using pages_url_hash on pages  (actual time=0.03..0.03 rows=1 loops=1)
  Index Cond: (url = 'https://example.com/a/very/long/path?with=params&more=1'::text)
  Buffers: shared hit=4

Where the hash index cannot help:

EXPLAIN SELECT id FROM pages WHERE url LIKE 'https://example.com/%' LIMIT 10;
Seq Scan on pages  Filter: (url ~~ 'https://example.com/%'::text)
-- prefix match: the B-tree (with text_pattern_ops) could serve this; hash cannot

EXPLAIN SELECT url FROM pages ORDER BY url LIMIT 100;
Limit → Sort → Seq Scan on pages
-- no ordering from a hash index
Where the two differ in practice Three items are annotated. Nearly identical buffer counts for an equality lookup. A sequential scan for a prefix pattern that only a B-tree could serve. A sort for an ordered query, because hash indexes provide no ordering. hash 4 buffers vs btree 5 equality: essentially equal LIKE 'prefix%' → Seq Scan hash cannot serve patterns ORDER BY url → Sort hash provides no ordering the size difference is the only reason to prefer hash

Step-by-Step Resolution #

  1. Inventory the column’s uses. Search the application and pg_stat_statements for every predicate on the column: equality, patterns, ranges, ordering, joins, and any unique constraint.

  2. Stop here if anything but equality appears. A B-tree is the answer; the size saving is not worth losing capabilities.

  3. Measure both indexes’ sizes on real data before deciding — build them side by side on a copy:

    CREATE INDEX CONCURRENTLY pages_url_hash ON pages USING hash (url);

  4. Compare lookup performance on the real query mix. Expect them to be close; hash is not dramatically faster, it is smaller.

  5. Consider the alternative: a B-tree on a hash expression, which keeps uniqueness and works everywhere:

    CREATE UNIQUE INDEX CONCURRENTLY pages_url_digest_uidx ON pages (md5(url));
-- query: WHERE md5(url) = md5($1) AND url = $1

    This is smaller than a B-tree on the full key, supports uniqueness (of the digest), and keeps a second exact comparison for safety against collisions.

  6. Keep only one index on the column unless different queries genuinely need different capabilities.

Index size for 34 million long URLs A B-tree on the full URL occupies 4,823 megabytes. A hash index occupies 1,104 megabytes. A B-tree on an md5 digest occupies 1,640 megabytes and supports uniqueness. A B-tree on the full URL with deduplication after a rebuild occupies 4,102 megabytes. btree on url 4,823 MB hash on url 1,104 MB btree on md5(url) 1,640 MB btree, rebuilt (dedup) 4,102 MB the digest index keeps uniqueness at a size close to hash

Before and After #

-- BEFORE: B-tree on a 180-character URL column, equality-only workload
Index Scan using pages_url_btree  Buffers: shared hit=5     index size 4,823 MB

-- AFTER: hash index
Index Scan using pages_url_hash   Buffers: shared hit=4     index size 1,104 MB

Why hash indexes stay a niche choice #

Storage is cheap, and the capabilities a B-tree provides — ordering, ranges, uniqueness, index-only scans, multicolumn keys — are exactly the things requirements grow into. A column that is equality-only today acquires a prefix search tomorrow, and the hash index becomes dead weight next to the B-tree someone has to add. The digest-expression approach avoids that trap: it is still a B-tree, so a second index is never needed for ordering, and the expression can be dropped or changed without touching the data.

There is one workload where hash indexes are clearly attractive: very wide keys in write-heavy tables where index size directly limits cache residency. A 4.8 GB index competing for shared buffers against the table itself pushes more of both out of cache; a 1.1 GB index may stay resident. If the equality-only constraint genuinely holds — and can be expected to hold — that cache effect is a real, measurable win beyond the storage saving.

Finally, note what the two share: neither avoids the heap fetch. Both verify the actual value against the row, so a lookup costs an index access plus a heap access either way.

Migrating between the two safely #

Swapping a B-tree for a hash index is a two-step operation, and the order matters. Build the new index concurrently first, verify from pg_stat_user_indexes over a full traffic cycle that it is being chosen, and only then drop the old one — also concurrently. Dropping first leaves the workload without any index for the duration of the build, which on a 34-million-row table means minutes of sequential scans on a hot lookup path.

Watch for the case where the planner keeps choosing the B-tree after the hash index exists. That usually means some query on the column is not pure equality, which is the signal to abandon the migration rather than force it: the planner is telling you the capability is still in use.

Common Pitfalls #

Assuming hash indexes are unsafe. That advice predates PostgreSQL 10. Diagnostic signal: reviews rejecting hash indexes on principle. Fix: check the version; they are WAL-logged and replicated from 10 onward.

Needing uniqueness later. Hash cannot enforce it. Diagnostic signal: a unique constraint request on a hash-indexed column. Fix: a B-tree, possibly on a digest expression.

Short keys. No meaningful size saving. Diagnostic signal: hash index within 10% of the B-tree’s size. Fix: keep the B-tree.

Forgetting the second comparison with a digest index. Hash collisions are rare but possible. Diagnostic signal: a query matching on the digest alone. Fix: always add the exact comparison on the original column.

Frequently Asked Questions #

Are hash indexes faster than B-tree indexes for equality? #

Marginally at best. Their real advantage is size on long keys, because they store a fixed-size hash rather than the whole value. Lookup performance is similar.

Can a hash index enforce a unique constraint? #

No. Unique constraints and primary keys require a B-tree index. If you need uniqueness on a long key, consider a unique B-tree on a digest expression combined with an exact comparison in the query.

When should I prefer a B-tree even for equality-only queries? #

Whenever the column might need ordering, ranges, pattern matching, uniqueness, multicolumn indexing or index-only scans — and whenever the keys are short enough that the size difference is small.

Up: BRIN and Hash Indexes