What data reduction forbids
Which reductions are impossible, and why does every escape move cost to write time or space?
What it forbids
- You cannot prune on a negative predicate. The absence of a value can be proven; the absence of everything but a value cannot.
- You cannot skip on an unsorted column with a range predicate. No summary exists, and both escapes (sorting, indexing) move the cost to write time.
- You cannot push read amplification below block size over matching rows per block. When selectivity is fine enough to isolate one row per block, more selectivity buys nothing.
- You cannot answer an aggregate from metadata unless pruning consumes the predicate entirely.
- You cannot get dynamic pruning without a scheduling barrier.
- You cannot push anything that the interface below you does not speak. The ceiling on this article is set by protocol design, not by algorithms.
The escapes, and what each costs
| Escape | Price |
|---|---|
| Finer metadata granularity | Metadata volume, until the metadata is a dataset needing its own hierarchy |
| Bloom filters | Space; they cover only equality |
| Clustering | Write-time work, and you get one ordering only; multi-column access needs space-filling curves (orderings that keep nearby points together) with their own compromises |
| Real indexes | Maintenance cost on an immutable substrate, so they are mostly absent |
| Runtime filters | A barrier: cheap or costly depending on an execution-model property you did not choose |
| Sampling | The exact answer |
| Materialized results | Storage and staleness |
Notice what unites the list: every escape moves cost to write time or to space. That is not an accident. This article consumes information produced earlier, so the only way to have more of it is to have produced more of it. Costs are moved, not removed.