Course contents
On this page
Hash indexes and query tradeoffs
Deeper reading after the guided lesson: hash indexes and query tradeoffs.
Start with the guided lesson. These sections develop the mechanisms and tradeoffs beyond that first example.
Hash indexes and their constraints
Hashing maps a key to a bucket. It can provide efficient equality lookup when the hash function distributes keys well and buckets remain manageable. It does not inherently preserve key order, so range queries need another structure or a broader scan.
Collisions require resolution, such as bucket chains or open addressing. Growing a hash table can involve expensive reallocation or an incremental migration protocol. A persistent concurrent hash index must coordinate readers with growth and recover safely after interrupted changes. Expected constant-time lookup is not a complete implementation specification.
Skew can arise even with a good hash function if many requests target the same key. Hashing distributes different keys; it does not divide one key’s authoritative update across independent buckets. An attacker can also exploit weak hashing or expensive equality comparisons unless the trust model and implementation account for it.
Hash growth and collision handling
A hash table computes a bucket from the key and compares actual keys among candidates. A hash match alone is not equality. With separate chaining, collisions create a bucket chain; with open addressing, probing examines alternate locations under a defined rule. Deletion in an open-addressed table may require a tombstone marker so later searches do not stop before a displaced key.
Growth changes the mapping. Doubling buckets can reassign many keys and temporarily require both old and new tables. An incremental migration protocol lets each operation consult the correct location while buckets move. It must prevent a key from being lost between tables or inserted independently into both. Persistence adds recoverable migration metadata, and concurrency adds publication and lifetime requirements.
A good hash function distributes distinct keys under expected input, but hot-key traffic still targets one logical entry. Adversarial input can also challenge a weak hash function. A service accepting untrusted strings must account for worst-case comparison work and collision attacks through suitable hashing and resource limits. Expected constant-time complexity is conditional on distribution and implementation assumptions.
A comparison using the same query family
Assume a constructed workload performs 90% exact item-ID lookups and 10% scans over a tenant’s newest hundred events. A hash index on item ID can serve the equality family, but it does not provide tenant/time order. A B+ tree on item ID also serves equality while supporting ranges over that identifier, which may have little product value. A separate ordered tenant/time index serves the feed family.
The choice is not necessarily one global structure. An engine can maintain different structures for different keys, at the cost of maintenance and memory. A memory-only hash lookup may be cheaper than a tree traversal for one workload; a persistent hash structure with collisions and growth can have different tail behavior. A B+ tree’s predictable ordered traversal can matter more when range access or recovery simplicity dominates.
PostgreSQL 18’s multicolumn documentation explicitly describes circumstances in which skip scanning can use later key constraints. The basic lesson remains lexicographic locality: missing a leading equality does not imply an index is unusable, but it changes the ranges and repeated searches required. PostgreSQL multicolumn indexes