A column has a hash index on it. Explain why that index can serve a lookup for one exact value but cannot serve a range filter such as "created_at greater than a given timestamp", a prefix match such as "name starts with A", or a request for rows sorted by that column.
answer
- uniform scatter = no locality
- prefix hashes to something unrelated
- bucket order ≠ key order
- no sort avoidance, no merge join, no min/max
- equality on the full key only
basics
~20 sA hash function deliberately scatters keys: values that are adjacent in sort order land in unrelated buckets, and a prefix hashes to something unrelated to the whole value. The index stores no ordering, so ranges, prefixes, and sorted output are impossible without reading every bucket.
solid answer
~50 sA hash index maps a *whole* key value to a bucket address via a function designed to distribute values uniformly. Uniform distribution is exactly the property that destroys locality: `2026-01-01` and `2026-01-02` hash to unrelated buckets, so there is no way to walk "everything after this value" — you would have to read all buckets and filter, which is worse than a table scan. Prefix matching fails for the same reason plus one more: the hash is computed on the complete value, and `h("Ann")` has no computable relationship to `h("A...")`, so you cannot even locate the starting point. Sorted output fails because bucket order is not key order; producing sorted rows would require reading the whole index and sorting anyway. That also rules out using the index to avoid a sort, to feed a merge join, or to answer minimum/maximum shortcuts. A B+tree, by contrast, keeps keys in sorted order in linked leaves, which is why it serves equality *and* all of the above.
go deeper
State that hashing scatters values so nothing is stored in order, therefore equality only.
Explain the mechanism for each shape — range needs a start point plus ordered walk, prefix is a range, ordering needs physical key order — and that the whole key must be supplied.
Add the operational consequence: an index that quietly stops being used when a predicate evolves, and the loss of merge joins, top-N early stop, and min/max shortcuts.
Position it as a query-shape contract: choosing hash narrows the set of plans the optimiser can ever produce for that column, which is a commitment about future workload, not just current latency.
## The property that makes hashing fast is the property that kills ranges A good hash function scatters inputs uniformly across the bucket space. That uniformity is what keeps buckets short and lookups constant-cost. It is also, by construction, the destruction of order: the function is chosen so that similar inputs land far apart, avoiding clustering. Order-preserving hash functions exist in theory, but they cluster real-world data badly and are not what relational engines use. So for a hash index, the following is true: knowing the bucket of key `X` tells you nothing about where keys slightly greater than `X` live. ## Range predicates To answer "all rows with a value above a bound", an access method must be able to (a) find the first qualifying entry and (b) enumerate the rest cheaply. A B+tree does both: it descends to the leaf containing the bound, then walks the linked leaf pages in key order, stopping when it passes the upper bound. Cost is proportional to the number of matching rows. A hash index can do neither. There is no "first qualifying entry" — qualifying entries are spread arbitrarily. The only way to answer the range is to scan every bucket and test each entry, which reads the whole index *and* then still needs row fetches. A full table scan is strictly cheaper. Planners therefore never consider a hash index for a range predicate; the index is simply invisible for that query shape. ## Prefix and pattern matching A prefix match is a range in disguise: values beginning with `A` form a contiguous interval in sort order, which is precisely why B+trees serve anchored prefix patterns as a range scan. Hashing breaks this twice over. First, the same ordering argument applies. Second, the hash is computed over the complete stored value, and hash functions are avalanche-designed — changing or truncating one character changes the output unpredictably. There is no arithmetic relationship between `h(prefix)` and `h(full value)`, so you cannot even derive a candidate bucket. The same reasoning explains why a hash index cannot support a leading-column lookup on a multi-column key: the hash covers all columns together, so a query supplying only some of them cannot compute the bucket at all. This is an all-or-nothing structure. ## Ordering and sort avoidance One underrated use of an ordered index is *not* filtering but ordering: a query that wants rows sorted by a column can read an ordered index in key order and skip the sort step entirely, which also lets it stop early when only the first rows are wanted. It can likewise feed a merge join, or answer a minimum or maximum by reading one end of the index. All of those depend on physical key ordering. Bucket order is essentially random with respect to key order, so none of them are available. Even a query with an equality filter that also wants ordered output gets only the filtering from a hash index; a sort still follows. ## What is left The hash index serves exactly one shape: an equality comparison against the complete indexed key. Two adjacent cases are worth knowing: - **Multiple matching rows** are fine — duplicates of the same key share a bucket, so a key with many rows is served normally. - **A set of discrete values** (several equality probes combined) is fine in principle — each value is a separate probe — though whether a given planner will do that depends on the engine. - **Inequality against a single value** ("not equal to") is not served, because it is the complement of one bucket, i.e. everything else. ## The practical takeaway When you choose an index type you are choosing which query shapes become cheap. A B+tree buys equality, ranges, prefixes, ordering, and min/max for a logarithmic descent. A hash index buys equality only, for a constant probe. That asymmetry is why B+trees are the default and hash indexes are a deliberate, narrow optimisation — and why adding a hash index to a column whose queries later grow a range filter leaves you with an index the planner silently stops using.
- If a query has an equality filter and also asks for the results ordered by that same column, does the hash index help?It helps only with the filter. Because the equality already pins one value of that column, the ordering on it is trivial anyway; but if the ordering is on a different column, the engine must still sort the fetched rows. A hash index can never eliminate a sort step, since it has no physical key order to exploit.
- Could a hash index be built so that it preserves order?Order-preserving hash functions exist, but they map similar inputs to nearby buckets, which reintroduces exactly the clustering that hashing exists to avoid — skewed data creates hot, overflowing buckets and the constant-cost property degrades. Relational engines do not use them; if you want order you use a B+tree, which is already good at both.
Sorting books by title lets you find every title starting with "Cat" by walking the shelf. Assigning each book a locker by a scrambled code from its title makes one exact title instant, and every 'starts with' or 'between' question hopeless.
saying these in an interview costs you the question
- Saying the engine can scan buckets in order to satisfy a range "a bit more slowly"
- Claiming a prefix match works because the prefix hashes into the same region
- Thinking a hash index on multiple columns still supports a leading-column lookup
- Believing the index can at least avoid a sort even if it cannot filter
- Assuming the planner will fall back to the hash index for a range instead of ignoring it