Sort keys and Z-order

Which order should the rows be clustered by, and what does each choice of key cost?

Sort keys and clustering keys

What a sort key does

A total order on a column makes the [min, max] range of each unit disjoint (non-overlapping) and increasing from unit to unit. A range filter then intersects exactly the units that span the range. The exclusion proof is exact: there are no false positives except at the two boundary units. This is the strongest skipping available. Everything else in this article is a weaker version of it.

The composite-key rule

People get hurt by composite (multi-column) sort keys. The rule has a two-line derivation.

Sort by (a, b). Column b is ordered only inside a run of equal a values. For b's per-unit range to be tight, one value of a must fill at least one whole unit: N / C_a ≥ G, where C_a is the number of distinct values of a (its cardinality). This is the same as:

Example. Sort a table by (user_id, event_time) with 10 million users and 1,000 units. Each user has far fewer rows than one unit, so every unit contains events from all of time. event_time is decorative. Its metadata exists, looks reasonable and prunes nothing. This is probably the most common clustering mistake, and it is invisible unless you measure how much the per-unit ranges overlap.

Parcelo's version. If Kavya sorts scan_events by (parcel_id, scan_time), there are roughly 2 billion ÷ 12 ≈ 170 million distinct parcels but only 3,125 files. C_a is about 50,000 times larger than U, so scan_time would prune nothing. If she sorts by (depot_id, scan_time) with 500 depots, C_a = 500 ≤ 3,125. Each depot fills about 3,125 ÷ 500 ≈ 6 files, and the time ranges inside those 6 files are tight. The second column works.

Clustering is rent, not a price

Every insert lands somewhere and breaks the order. The order is restored only by rewriting. The decay rate is proportional to the write rate. The cost to restore it is the U/d from Mutation strategies (copy-on-write: you rewrite a whole unit to change a few rows), because reclustering is copy-on-write with a different motive.

This is the principle sortedness decays, now fully established:

Clustering has no steady state and no purchase price. It has a monthly payment proportional to your write rate. If the rent is more than the savings from skipping, the correct clustering key is none. Very few teams compute this before they choose a key.

One order per copy of the data

There is only one total order per copy of the data. A second access pattern needs a second copy. Vertica's projections (extra sorted copies of a table) are an honest implementation of that idea. This is the conserved-cost rule: the additional bet is paid for in write amplification and storage. It is never free.

Global versus local ordering

Sorting inside each file is cheap. Sorting across all files needs a global shuffle with a range partitioner (a step that sends each row to the file that owns its key range) and a sample-based boundary estimate (the engine samples the data to choose the range boundaries). The two give completely different skipping and differ by about an order of magnitude in cost. In Spark, sortWithinPartitions (local) versus a global sort is a real daily decision.

The difference matters for skipping. With local sorting only, every file still contains the whole range of keys, so every file's [min, max] is wide and the zone maps (explained below) prune nothing. Only inside a file are the row groups or pages tidy. With global sorting, the files' ranges are disjoint, and whole files can be skipped.

---

Z-order and space-filling curves

The problem

You want to keep nearby points close in d dimensions (for example depot_id, scan_time and customer_country). Storage offers only one dimension: a line. A space-filling curve maps d dimensions onto one.

The honest description of what it achieves is not "preserves locality". That is impossible. Every such curve has pairs of points that are neighbours in d-dimensional space but far apart along the curve. What the curve achieves is this:

Z-order (also called Morton order) is the common version. It builds the sort key by interleaving the bits of the column values: first bit of a, first bit of b, second bit of a, second bit of b, and so on. Hilbert curves are a smarter curve of the same family.

The derivation

Z-ordering divides space into roughly equal cube-like cells, one per unit. In coordinates scaled to the range 0 to 1, each cell has side L with L^d ≈ 1/U, so

L = U^(−1/d).

A query constrains one dimension to a slab of thickness s and leaves the other dimensions free. It touches every cell whose extent in that dimension meets the slab. That is a fraction max(s, L) of all units. Therefore the floor on units touched is U^(1−1/d), whatever s is.

Worked numbers. U = 10⁶ units.

• d = 2: no single-dimension query can touch fewer than 10⁶ ^ (1/2) = 10³ units.
• d = 4: the floor is 10⁶ ^ (3/4) = 10^4.5 ≈ 31,600 units. That is about 3% of the table, as a minimum, forever.

Z-order degrades sharply with d, and the damage is in the exponent.

Parcelo's version. With U = 3,125 and d = 2 (depot and time), the floor is √3,125 ≈ 56 files for any single-dimension query. With d = 3 it is 3,125^(2/3) ≈ 214 files.

The skip-budget rule

Now the main result. A single sort key on dimension 1 gives a skip factor of U on dimension 1 and 1 on the others. The product of the factors is U. Z-order over d dimensions gives a skip factor of U^(1/d) on each dimension. The product is again U.

(It is derived from this one calculation. Treat it as a useful rule of thumb, not as an established law.)

When should you use Z-order?

The product is fixed, and you pay the sum of the query costs. By the AM-GM inequality (the arithmetic mean of positive numbers is never less than their geometric mean), a sum with a fixed product is smallest when the terms are equal. So Z-order wins exactly when queries are spread across dimensions and the unclustered case would otherwise scan everything.

Check with two workloads: half of the queries filter dimension 1, half filter dimension 2.

• Sort key on dimension 1: cost = 0.5 × 1 + 0.5 × U ≈ 0.5·U (units read, in the relative scale of "1 means the best case").
• Z-order: cost = 0.5·√U + 0.5·√U = √U.

Z-order wins by a factor of about √U / 2. It is not better at anything. It wins because it eliminates the total-scan case, and the total-scan case dominates the sum.

So Z-order is insurance, not optimization. If 90% of your scanned bytes come through one predicate column, Z-ordering is a loss: you gave up U on the dimension that mattered to buy U^(1/d) on dimensions that rarely matter. Implementations that let you weight columns (giving one dimension the high-order bits) are doing the weighted version of the same AM-GM argument.

Two practical notes

• Morton versus Hilbert. Morton order has large jumps at bit-carry boundaries. Hilbert has none, and measurements usually show Hilbert touching fewer units. Both are U^(1−1/d) asymptotically, so the gain is a constant factor whose size depends on the workload. This is engineering reality, not a permanent constraint. The price: Hilbert encoding is more expensive and harder to compute incrementally.
• Different value ranges. Bit interleaving assumes the columns have comparable value ranges. Interleaving a column with 10 distinct values with a column of 10⁹ distinct values wastes most of the bit positions of the small column. Rank-transform or quantile-bucket the columns before interleaving.