Range Partitioning vs Hash Partitioning: Locality, Skew, and Query Routing

Learning outcomes

AtlasMart now has a partitioned order stream, but the first key design question is not “range or hash?” in isolation. The choice changes locality, skew, routing precision, split behavior, and the number of partitions touched by a query. This lesson compares both mechanisms with one key set so the tradeoff is observable rather than memorized.

1. Range partitioning: preserve order, expose boundaries

Range partitioning assigns intervals of an ordered key space to partitions—for example, order IDs 1000–1009 to R0 and 1010–1019 to R1. A range query can often be routed to one or a few adjacent partitions because order is preserved. Splitting is conceptually direct: choose a boundary within an overloaded range and create two ownership intervals.

The danger is monotonic growth. If new order IDs always increase and the final open-ended range owns all future IDs, every new write targets the same partition until the system splits or changes the key design. Range systems can automate splits, but the hotspot exists between detection and successful movement.

2. Hash partitioning: spread values, give up natural order

Hash partitioning transforms the partition key through a deterministic hash before assigning ownership. Good hashes make nearby input values land far apart, which reduces dependence on the input distribution and helps spread monotonically increasing IDs. But a business query such as “orders 1012 through 1018” no longer corresponds to one contiguous ownership interval; it may require fan-out or a separate index/materialized view.

3. Routing metadata is part of correctness

A range router needs ordered boundaries and owners; a hash router needs the hash algorithm plus slot/token ownership. Both need a versioned metadata view. If a client uses an old map after a split, a correct system must reject/redirect or safely forward the request rather than silently accepting ownership under conflicting maps.

epoch=12
range=[1000,1020) -> shard-a
range=[1020,1040) -> shard-b

# after split
epoch=13
range=[1000,1010) -> shard-a
range=[1010,1020) -> shard-c
range=[1020,1040) -> shard-b

The map says where a request should go, not whether the chosen key is semantically good. A perfectly consistent routing table can still create a disastrous hotspot.

4. AtlasMart lab — same keys, different locality

Environment: Python 3.13.5 standard library, deterministic SHA-256 hashing, four logical range partitions and four logical hash partitions. No product-specific defaults are implied.

import hashlib
from collections import Counter

keys = list(range(1000, 1040))
RANGES = [
    (1000, 1010, "R0"),
    (1010, 1020, "R1"),
    (1020, 1030, "R2"),
    (1030, 2000, "R3"),
]


def range_route(k):
    for lo, hi, name in RANGES:
        if lo <= k < hi:
            return name
    raise KeyError(k)


def hash_route(k):
    h = int.from_bytes(hashlib.sha256(str(k).encode()).digest()[:8], "big")
    return f"H{h % 4}"

range_counts = Counter(range_route(k) for k in keys)
hash_counts = Counter(hash_route(k) for k in keys)
print("INITIAL KEYS")
print("range counts:", dict(sorted(range_counts.items())))
print("hash counts:", dict(sorted(hash_counts.items())))

scan = list(range(1012, 1019))
print("\nRANGE SCAN 1012..1018")
print("range partitions touched:", sorted({range_route(k) for k in scan}))
print("hash partitions touched:", sorted({hash_route(k) for k in scan}))

new_monotonic = list(range(1040, 1080))
print("\nMONOTONIC INSERT BURST")
print("range target counts:", dict(Counter(range_route(k) for k in new_monotonic)))
print("hash target counts:", dict(sorted(Counter(hash_route(k) for k in new_monotonic).items())))
print("wrong assumption: 'ordered keys are automatically balanced' -> all new range writes hit R3")
print("tradeoff: hashing improves distribution but destroys simple ordered locality")

INITIAL KEYS
range counts: {'R0': 10, 'R1': 10, 'R2': 10, 'R3': 10}
hash counts: {'H0': 12, 'H1': 10, 'H2': 5, 'H3': 13}

RANGE SCAN 1012..1018
range partitions touched: ['R1']
hash partitions touched: ['H0', 'H1', 'H2', 'H3']

MONOTONIC INSERT BURST
range target counts: {'R3': 40}
hash target counts: {'H0': 9, 'H1': 16, 'H2': 8, 'H3': 7}
wrong assumption: 'ordered keys are automatically balanced' -> all new range writes hit R3
tradeoff: hashing improves distribution but destroys simple ordered locality

Diagnosis

The ordered scan touches one range partition but several hash partitions. The monotonic burst routes every new key to R3 under the intentionally static range map, while the hash scheme spreads the burst. That is not evidence that hashing is universally better; it is evidence that the access pattern and update distribution differ.

5. Production judgment

Use ranges when locality and ordered access dominate and you can manage split/hot-range behavior. Use hashing when point access and even distribution dominate and range locality is less important or provided by another view. Composite strategies are common—for example, tenant hash plus time bucket—but every added component changes routing and query fan-out.

Monitor per-range write rate, key-cardinality growth, split backlog, scatter-gather count, per-shard tail latency, and routing redirects. Do not publish raw tenant or customer identifiers in diagnostic labels. The next lesson replaces fixed modulo hashing with consistent hashing so adding/removing nodes does not remap most keys.

Authoritative references

• MongoDB 8.3.8 — Choose a Shard Key — current implementation example emphasizing cardinality, frequency, monotonic growth, and query patterns
• MongoDB 8.3.8 — Shard Keys — implementation example of range and hashed shard-key value spaces
• Google Bigtable — primary ordered-range/tablet design reference