Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Equality and total order

Why is hashing the cheapest index but rarely used, and what must a key's byte encoding preserve?

Equality: the degenerate case

A point predicate needs no structure preserved beyond "the same key lands in the same place". Any function that is deterministic and spreads keys well will do. That is why hashing is the cheapest possible index and appears wherever ranges are not needed. (A hash is a function that turns a key into a number, used to pick a slot.)

What matters here is not how hash tables work but what the choice costs at the index level. A is maximally specialized: it answers one predicate shape and nothing else. No ranges, no prefixes, no free ordering, no top-N, no min/max. In exchange it has no tree height, so lookup cost does not grow with N at all.

Why are hash indexes rare as user-facing database objects, although they are faster for their one job? The answer is economics, not technology. A B-tree answers equality almost as fast and also answers five other predicate shapes, so one B-tree replaces several hash indexes and costs less in total .

Total order: one run, one order

A totally ordered key domain with an order-preserving index gives the ideal case: the qualifying entries are exactly one contiguous run, found by one descent and read sequentially. Ranges, prefixes, sorted output, min/max and top-N all follow from the same property. That is why ordered indexes dominate: one structure, six predicate shapes.

The order-preservation requirement

Beyond "B-trees exist", there is a requirement that is real and often broken: the byte encoding of the key must sort the same way the logical values do. An index on a composite or non-scalar key is only range-queryable if comparing the stored bytes gives the same answer as comparing the values. Order-preserving byte encodings exist for this reason. Get it wrong and the index silently answers range queries incorrectly, or not at all. Common mistakes:

  • big-endian versus little-endian integers (little-endian bytes do not sort numerically);
  • unsigned encoding of signed values (negative numbers sort after positive ones);
  • naive concatenation of variable-length fields.

The classic failure: concatenating variable-length string fields without an escaped separator, so that the key ("ab", "c") and the key ("a", "bc") both encode to the bytes abc and are indistinguishable.

# Wrong: two different tuples, same bytes
def bad_key(a, b):  return (a + b).encode()
bad_key("ab", "c") == bad_key("a", "bc")        # True: collision

# Better: terminate each field with a byte that cannot appear inside it (0x00),
# and escape any 0x00 that does appear. Sorting the bytes now matches
# sorting the tuples.

Free ordering for the rest of the plan

An ordered index on a column also supplies an ordering to the rest of the query plan for free. (The calls this an "interesting order": sorted data that lets it skip a sort or run a merge join.) The index is where that order comes from, and it is often worth more than the . An index that removes the sort from a top-N query (ORDER BY created_at DESC LIMIT 10) can beat an index with better , because it can stop after reading 10 entries.