Basis Lab

Answers · Where the data lives

Why can't a hash index handle a range query like created_at > '2024-01-01'?

In shortA hash index finds only exact keys: it scrambles key order to pick a bucket, so there is no way to seek to the start of a range and walk forward.

A hash index cannot answer created_at > '2024-01-01' because it has no ordered position to seek to. It maps each complete key to a bucket, and the bucket tells you where that one key is or that it is absent; it does not tell you where the next key in date order is, or whether any bucket contains keys before or after a boundary. A B-tree can do the range because its leaves are sorted: one descent finds the first row at or after the boundary, then a leaf scan continues forward. A hash index has no first row to find.

h(d)=d mod 8,d=5,6,…,12  ↦  5,6,7,0,1,2,3,4.h(d)=d\bmod 8,\qquad d=5,6,\dots,12 \;\mapsto\; 5,6,7,0,1,2,3,4.
FIG 1
day numberbucket h(d)=d mod 8
55
66
77
80
91
102
113
124

On a real table the same thing happens at a larger scale. Suppose 1,000,000 rows and a range containing 10,000 of them. The hash index can only answer by taking each of the 10,000 keys in the range and probing h(key). That is 10,000 bucket reads, and the database has to know the keys first, which means it already has the rows or another ordered index. Even if it enumerates them, the work is proportional to the number of rows returned, not to a short descent. A B-tree with fanout 100 over 1,000,000 rows has depth 3 because 100^3=1,000,000; it reads three pages to reach the leaf at the boundary, then walks the leaves in order. The range's size is paid once in the leaf scan, not once per bucket probe.

The natural guess is that the hash of a date just after the boundary might be just after the hash of the boundary, so the index could start there and move upward. The mod 8 example kills that: day 7 hashes to 7 and day 8 hashes to 0, so increasing the date by one moves the bucket from the end of the range to the start. A hash function is chosen precisely so that such neighbours do not collide into nearby buckets; changing one bit of the key should change the bucket. The bucket number is an address for one key, not a coordinate in key order.

hash probes for a<k≤b  =  ∣{k∈K:a<k≤b}∣,B-tree reads  =  O(log⁡Fn+m).\text{hash probes for } a<k\le b \;=\; |\{k\in K: a<k\le b\}|,\qquad \text{B-tree reads} \;=\; O(\log_F n + m).

Scanning every bucket does not rescue it. Each bucket holds many keys, and within a bucket there is no order either. To answer the range by scanning buckets you must read every entry in the index and test created_at on each, which is a full index scan. That is worse than a table scan if the table is already sorted by time, and the planner will normally choose the tree or a scan instead. A hash index on created_at is therefore close to dead weight for this query: it costs writes and space and the planner ignores it.

What changes is the predicate, not the structure. A hash index remains right for equality: WHERE id = 42, an IN list of known ids, a join on an identifier, a cache keyed by exact key. If the range is small and you write every value explicitly, the database can turn it into several equality probes, but that is a list of exact lookups, not a range. The same limit applies to prefix queries on text and to composite keys: a hash on (tenant_id, created_at) helps only when both columns are supplied by equality. A range on created_at inside one tenant still needs a tree, or a write-ordered store whose runs are sorted and merged. An order-preserving function would no longer be a hash index in this sense; it would be a sorted structure with extra steps.

So the index is not failing because the database is badly implemented. It is failing because created_at > '2024-01-01' asks for a boundary and then a walk, and a hash index stores neither a boundary nor a walk. It stores a scatter function and one bucket per exact key.

Worth keeping

  • A hash index can answer equality on a complete key in one bucket read, and nothing else.
  • A range query needs an ordered structure because finding the boundary and walking forward are both order operations.
  • If a range has m rows, a hash index would need m exact probes, while a sorted index pays a short descent plus a leaf scan.

Where this goes next

This question is one step of How an Index Actually Works, a course that works through its subject from the beginning. The page that teaches this part of it is The Other Two Shapes, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that pageThe whole course

Other questions people ask about this

  1. How does a B-tree find one row among millions in just a few reads?A B-tree finds a row by reading only a few pages: each page holds hundreds of pointers, so the tree stays three or four levels deep.
  2. Why is a log-structured store faster for writes than a B-tree?Because a B-tree finds a page and then rewrites it in place for every insert, while a log-structured store only appends, and appending in order is far cheaper than jumping about the disk.
  3. What does it mean for an index to cover a query?A covering index holds every column a query needs, so the database can answer from the index without reading the table row.
  4. Why does inserting a single row sometimes cost many page writes?A row insert usually writes one page, but when the target page is full it splits in half and the split can climb to the root, so rare inserts write several pages for each index.
  5. Why is the date off by one day after I save it and read it back?You saved a calendar date as if it were a precise moment, so showing it in another time zone can move it to the day before or after.
  6. Is UTF-8 the same thing as Unicode, or what's the difference?No: Unicode assigns a number to each character, while UTF-8 is a way of writing those numbers as bytes, using one to four bytes per character.

Read alongside