Hash Index

Hook: A hash index is the database version of a locker with a secret code: if you know the exact code, you go straight to the right locker, but it is terrible when you need the lockers in order.

Question: What is a hash index in SQL, and when would you use one?

Answer: A hash index stores a hashed version of the indexed value so the database can jump quickly to matching rows for exact equality searches like WHERE email = 'a@x.com'. It is fast for = comparisons, but it does not help with ranges, sorting, or prefix searches because the values are not kept in order. In PostgreSQL, hash indexes are a real feature, but B-tree is still the default because it is more flexible.

Interview-Ready Answer: I think of a hash index as a lookup table for exact matches. The database runs the column value through a hash function, jumps to the bucket for that hash, and checks only the rows there, so equality lookups are usually close to constant time on average. The tradeoff is that hash indexes do not support range queries or ordering, and collisions can still happen, so I would use them only when the workload is mostly exact-match lookups and I do not need ORDER BY, BETWEEN, or prefix searches.

What it is

A hash index is an index structure built around a hash function, which is a deterministic way to turn a value like an email address or ID into a fixed-size number. The key idea is simple: values that are equal should map to the same hash, so the database can find exact matches without walking through a sorted tree. This is not a core SQL-standard feature; it is an engine feature. In PostgreSQL, for example, you can create one with USING HASH.

How it works under the hood

1. When a row is inserted or updated, the database takes the indexed column value and runs it through the hash function.
2. That hash is mapped to a bucket, which is a storage area inside the index. Think of a bucket as a small bin for rows that share the same hash region.
3. The index stores row pointers, not the full row, so it stays smaller than the table and can jump straight to candidate rows.
4. When you run WHERE email = 'grace@example.com', the engine hashes the search value the same way and goes directly to the matching bucket.
5. If more than one value lands in the same bucket, that is a collision. The engine keeps the candidates together and compares the real values one by one so the answer is still correct.
6. As the index grows, the engine may add or split buckets and manage overflow pages, which are extra pages used when a bucket becomes full. The goal is to keep lookups close to constant time on average.

When to use it

• Use it for exact-match lookups on high-cardinality columns, meaning columns with many distinct values, such as user_id, email, or session_token.
• Use it when you almost never need ordering, range filtering, or prefix matching on that column.
• Use it when the application does lots of point lookups and the workload is stable enough that equality search is the main pattern.

Hash index vs B-tree

For most systems, B-tree wins as the default because it is versatile: it supports equality, ranges, sorting, and often index-only access patterns. Hash is narrower but can be good when the workload is almost entirely = comparisons.

Performance notes that matter in interviews

Average lookup time is close to constant, but that does not mean magical speed in every case. If the table is huge and the data is not in memory, you still pay random I/O to read the bucket pages; the difference is that you read far fewer pages than a full scan. On a warm cache, the gain is usually fewer comparisons and less CPU work. On a million-row table with a well-distributed key, a successful equality lookup might touch one bucket page and maybe one overflow page; with bad collisions, it can get slower quickly.

Space usage depends on bucket count, key size, and overflow chains. Hash indexes can be efficient, but they are not free: more buckets and overflow pages mean more maintenance, and a poorly chosen index can waste space without helping the query plan.

Important edge cases and gotchas

• Not for ranges: BETWEEN, >, <, and sorted output are a bad fit because hashes destroy order.
• Not automatically unique: In PostgreSQL, hash indexes do not support unique constraints; collisions mean the engine must still compare the real values.
• Low-selectivity columns are poor candidates: A boolean or tiny status column usually has too few distinct values, so the index helps less and may be ignored.
• Version matters: In PostgreSQL 10 and later, hash indexes are WAL-logged and crash-safe; older versions had a historically bad reputation because crash recovery was not reliable.
• Engine-specific behavior: Different databases support hash indexing differently, so do not assume one engine's rules apply everywhere.

Memory in one line: if you know the exact code, a hash index takes you straight there; if you need order or a range, it is the wrong map.

Real-world story

Imagine a payment reconciliation service in an e-commerce app. The team stores tens of millions of payment records and frequently looks them up by provider_charge_id, which is an exact external reference from the payment gateway. A hash index on that column is a good fit because the application usually asks, show me the row for this exact charge id, not show me the last 100 charges in order.

Now for the bug: a developer sees the hash index and assumes it will also help a dashboard query like WHERE created_at > now() - interval '15 minutes'. It does not. The query gets slower as traffic rises, the database starts doing sequential scans, and the logs show long-running queries with Seq Scan and sort steps. Users notice delayed payment status updates, support tickets spike, and the on-call engineer finds that the index choice was based on the wrong mental model: hash indexes are for exact matches, not time windows or reports.

Follow-up & Tricky Questions

• Why would you choose a B-tree instead of a hash index? B-tree is the safer default because it supports equality, range searches, sorting, and usually more query patterns with one index. If I only need exact matches, hash can work; otherwise B-tree is usually the better trade.
• Can a hash index enforce uniqueness? In PostgreSQL, no. Two different values can hash to the same bucket, so the engine cannot rely on hash alone for uniqueness constraints the way a B-tree can.
• What happens when two different values collide? They land in the same bucket, and the database compares the real values after the hash check. Collisions hurt speed, but they do not break correctness.
• Are hash indexes safe in modern PostgreSQL? Yes, from PostgreSQL 10 onward they are WAL-logged and crash-safe. Older versions had a historical durability problem, which is one reason many engineers still reach for B-tree first.
• When would a hash index be a bad idea even for equality? When the column has very low selectivity, such as a status flag with only a few values, or when the workload also needs sorting, reporting, or range filters.
• Tricky: Is a hash index always faster than a B-tree for =? No. B-tree is often just as fast or faster in practice because it is heavily optimized, more cache-friendly for many workloads, and much more versatile.
• Tricky: Can a hash index speed up ORDER BY or MIN/MAX? No. Those operations need order, and hash indexes intentionally destroy order.
• Tricky: If the query uses LOWER(email), will a hash index on email help? Not by itself. The expression changes the search key, so you would need an index on the expression itself, and even then engine support matters.

Common Mistakes:

• Using hash for ranges: Candidates say it helps any lookup. Correction: it only helps exact equality searches; ranges and ordering need B-tree or another ordered structure.
• Assuming uniqueness: People think a hash index makes values unique because hashes are different. Correction: collisions exist, so uniqueness needs different support, usually a B-tree unique index.
• Ignoring the workload: Some pick hash because it sounds faster. Correction: choose based on real predicates in the app, not on theory alone.
• Forgetting engine differences: Not every database treats hash indexes the same. Correction: always name the engine, and in PostgreSQL mention the v10 WAL/crash-safety change.

Memory Hook: Hash index = locker code; B-tree = library shelf. If you know the exact code, the locker opens instantly. If you need the books in order, you need the shelf.

Cheat Sheet:

• Best for exact-match queries like WHERE id = ? or WHERE email = ?.
• Not good for BETWEEN, >, <, ORDER BY, or prefix search.
• Average lookup is near O(1), but worst case can degrade to O(n) with collisions.
• In PostgreSQL, hash indexes are crash-safe since version 10, but B-tree is still the default choice.
• High-cardinality columns are the best candidates; low-cardinality columns usually are not.

Practice Tasks:

• Create a table with a million rows, add a hash index on an ID column, and compare EXPLAIN for equality versus range queries.
• Build the same lookup with a B-tree and compare which queries each index can support.
• Take a report query that uses ORDER BY or BETWEEN and explain why a hash index would not help it.