Clustering: matching file contents to the questions

When does sorting beat a space-filling curve, and how do you measure clustering health?

Arrival order is a fact about when. Query predicates are facts about what. Only a rewrite can reconcile them.

Which order to restore is the layout's choice: a sort on one column prunes almost perfectly on that column and nothing on the others, while a space-filling curve such as Z-order spreads mediocre pruning across several columns and only pays when predicates really are spread. Maintenance's question is how far the table has drifted from that order, and when to pay to restore it.

The right health metric: overlap depth

The useful question is not "is the table sorted?" but overlap depth: pick a random value on the clustering column, and count how many files have a min/max range that contains it.

• Depth 1 is perfect: exactly one file can hold the value.
• Depth N is worthless: every file might hold it.

Small example. Five files with ranges on customer_id: [1-100], [1-100], [50-150], [120-200], [1-200]. For the value 60, four files contain it ([1-100], [1-100], [50-150], [1-200]). Depth 4 means the query reads four files for one customer.

Incremental clustering never reaches depth 1. It reaches an equilibrium where the drift rate (new data arriving out of order) equals the repair rate. This has the same steady-state shape as SSD garbage collection. It is the third appearance of the "immutable layer grows a collector" pattern: erase block, then SSTable (an immutable sorted file in an LSM-tree), then table file; one collector per substrate.