The same contiguous range scan — the 1000 keys [500000, 501000) over 16 shards — touches 1 shard under key-range sharding and all 16 under hash sharding. A single-key point lookup touches 1 shard under both; and a composite key (sensor#ts, hashed by the sensor prefix) keeps a range over ts within one sensor on 1 shard even under hashing.
Put 1,000,000 keys across 16 shards two ways, then run the same contiguous range scan — the 1000 keys [500000, 501000) — against each. Under key-range sharding (shard = a contiguous slice of the key space) those 1000 adjacent keys all live in one shard, so the query hits 1 shard. Under hash sharding (shard = md5(key) % 16) the same 1000 keys are smeared across all 16 shards — ~62 per shard — so the query must fan out to every shard and reassemble the answer. Same query, same data: 1 shard vs 16. That fan-out is the price hash sharding pays for its even load. The controls pin the boundary: a single-key point lookup touches exactly 1 shard under both schemes, and a composite key (sensor#ts, hashed by the sensor prefix only) keeps a range over ts within one sensor on 1 shard even under hashing.
Designing Data-Intensive Applications, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 7 — Sharding, §"Sharding by hash range" and the chapter Summary:
[Hashing the key to determine its partition] destroys the ordering of keys, making range queries inefficient.
The book contrasts key-range sharding (good for range scans, prone to hot spots) with hash sharding (even load, but you lose efficient range queries). Here you measure exactly how inefficient: the number of shards the identical range query has to touch under each scheme.
The surprise is entirely about adjacency — whether keys that are neighbors in key order are also neighbors in shard placement. These help; each line notes where it shows up.
500000, 500001) to unrelated outputs, so any structure in the key space is gone after hashing. It shows up as the 1000 adjacent keys landing on all 16 shards.WHERE k BETWEEN lo AND hi, a time range, a scan). Only the range query cares where neighbors live. It shows up as the point control touching 1 shard under both schemes while the range splits 1 vs 16.(partition_key, sort_key) where the system hashes only the first component and keeps the rest sorted within it (Cassandra's partition key + clustering columns, DynamoDB's partition key + sort key). It shows up as the sensor#ts redemption: hashing the sensor keeps one sensor's readings together and sorted by ts.500000 and 500001 land nowhere near each other. Composite keys (#3): DDIA §"Sharding by hash range" (the concatenated-index paragraph); Cassandra's docs on partition keys vs. clustering columns (datastax.com, "The partition key") for the real-world shape of the escape hatch. If only one is new, make it #1 — "the hash intentionally throws away adjacency" is the whole mechanism; everything else follows from it.
md5, never Python's per-process randomized hash(), so the numbers are byte-for-byte stable every run. Fixed layout: 1,000,000 keys (000000..999999), 16 shards; range query is the 1000 keys [500000, 501000).
Same keys, same 16 shards, same range query — only the placement rule differs.
shard = key // 62500. Shard 0 owns keys 0..62499, shard 1 owns 62500..124999, and so on: each shard is a contiguous slice of the key space. Adjacent keys share a shard, so a range scan is a slice of one (or, if it straddles a boundary, two) shards. The cost is hot spots — sequential keys (timestamps, auto-increment ids) all pile onto the newest shard.shard = md5(key) % 16. The hash scatters keys uniformly, so load is even and there are no sequential hot spots. But adjacency is gone: 500000 and 500001 hash to unrelated shards, so a range of adjacent keys is spread across every shard and a range query must ask all of them.Both are the same two-line function over the same key set; the exercise runs the identical range, point, and composite queries against each. The whole thing is one script, code/hash_kills_range_queries.py.
cd study/ddia/ch07
python3 code/hash_kills_range_queries.pyDo not read the output yet — make each prediction first.
Predict. You scan the 1000 consecutive keys [500000, 501000). Under key-range sharding, how many of the 16 shards hold at least one matching key? Under hash sharding, how many? (And roughly how many of the 1000 keys land on each shard it does touch?)
1 vs 16. Under key-range the 1000 keys are a slice of shard 8's contiguous range 500000..562499, so one shard answers the whole query. Under hashing the same 1000 keys are scattered — 52 to 72 per shard, ~62.5 on average — so every shard holds some, and the query has to fan out to all 16 and merge the results.
Predict. Now look up a single key, 500000. How many shards does that touch under key-range sharding? Under hash sharding? Is hashing bad here too?
1 shard under both. A single key hashes to a single shard, so a point lookup is a direct hit either way. Hashing costs you nothing here — the penalty in Step 1 is specific to ranges, which is exactly the query that depends on neighbors sharing a shard. (That both landed on shard 8 is a coincidence of this one key; what matters is each scheme touches exactly one.)
Predict. Keys are now f"{sensor}#{ts}", and the system hashes only the sensor prefix to pick a shard (ts is the sort key within a sensor). You range over ts in [1000, 2000) for one sensor, sensor-0042 — 1000 readings. Under hashing, how many shards does this range touch?
1 shard — the range came back. Every reading shares the same sensor-0042 prefix, so they all hash to the same shard (6) and stay sorted by ts within it. Hashing only the partition key buys even load across sensors while keeping each sensor's time-range scan local. The catch: the range must be within one partition key — a range over ts across all sensors is scattered again.
[500000, 501000) touches 1 shard under key-range sharding and all 16 shards under hash sharding.500000 touches exactly 1 shard under both schemes.ts in [1000, 2000) for one sensor) touches 1 shard even under hashing.A range query asks for keys that are adjacent in key order — every key in an interval. Whether that query is cheap or expensive comes down to a single question: are keys that are neighbors in key order also neighbors in shard placement?
Key-range sharding answers yes by construction. shard = key // 62500 is monotonic: it maps a contiguous block of keys to one shard, so the keys 500000..500999 — being inside the block 500000..562499 — are all shard 8. The answer to a range query is a slice of one shard (two only if the interval happens to straddle a shard boundary). Adjacency in the key space is adjacency in placement.
Hashing answers no on purpose. A good hash function has the avalanche property — flip one bit of the input and about half the output bits flip — so md5("500000") and md5("500001") are unrelated 128-bit numbers, and % 16 sends them to independent shards. That scattering is the whole point: it spreads sequential keys evenly and kills the hot spots key-range sharding suffers. But it destroys adjacency, so a range of adjacent keys becomes a set of unrelated hashes with no locality. With 1000 keys and 16 shards, each key is placed independently and roughly uniformly, so the expected count per shard is 1000 / 16 ≈ 62.5, and the chance a given shard gets zero of the 1000 is about (15/16)^1000 ≈ e^(−1000/16) = e^(−62.5) — astronomically small. So essentially every shard holds some matching key, and the query must fan out to all 16 and merge. The book's one line — "range queries are inefficient" — is this fan-out.
16 * (1 − (15/16)^10) ≈ 8 distinct shards, since collisions are no longer negligible), and confirm key-range still touches 1.[499990, 500010), which crosses the shard-7/shard-8 line at 500000 (437500..499999 is shard 7). Predict key-range now touches 2 shards — the one case it isn't 1 — while hash sharding is unmoved at 16.ts in [1000, 2000) across all 100 sensors instead of one. Predict the shard count jumps back toward 16, because now the keys differ in their partition component — the escape only holds within a single partition key.Sources: DDIA 2e, Ch. 7, §"Sharding by hash range" and chapter Summary · Wikipedia, "Avalanche effect" · DataStax, "The partition key".