Skip to content

CONCEPT Cited by 1 source

Fragment pruning

Fragment pruning is the design pattern of pushing per-file (per- "fragment", per-"row-group", per-"SSTable") summary metadata up the stack so that a query engine can skip entire files without fetching or scanning them, based on the query predicate alone.

It's the design lever behind the read-side payoff of concepts/lsm-compaction and most columnar lake formats (concepts/columnar-storage-format).

The design axis

From weakest to strongest:

  1. Range metadata. Per-column min/max per row group (Parquet's baseline). Skips the row group if the predicate value lies outside [min,max].
  2. Bloom filters. Probabilistic set membership per column per row group. No false negatives; some false positives.
  3. Trimmed FSAs → regex (Husky's variant). A finite-state automaton that accepts at least the values in the column, trimmed to a bounded size; converted mechanically to a regex and stored in metadata. Evaluated against the query predicate. No false negatives; more precise than range, typically smaller than a Bloom for low-cardinality tag columns. See patterns/trimmed-automaton-predicate-filter.
  4. Inverted indexes / exact value sets per column per fragment — precise but storage-expensive.

Why range metadata alone isn't enough

The further a sort-column sits from the front of the row key, the looser its effective min/max constraint is, because the sort is lexicographic across the entire key. A mid-key column's [min, max] window spans too much of its alphabet to be selective.

Husky's worked example: a fragment whose service column contains compactor, reader, writer. A query for service:metadata is correctly skipped by a regex ^(compactor|reader|writer)$, but would wrongly be scanned by a min/max filter because metadata sorts inside [compactor, writer].

Locality compaction multiplies pruning's payoff

Leveled / locality compaction (see concepts/lsm-compaction) produces fragments whose per-column value sets get narrower at higher levels (the level's key space is divided among more disjoint fragments as level size grows). So the same pruning mechanism gets more selective the older the data gets — exactly the opposite of the usual "old data is expensive to query" problem.

Datadog reports this combination — locality compaction + FSA-regex pruning — produced a 30% reduction in the query-worker fleet at Husky rollout. (Source: sources/2025-01-29-datadog-husky-efficient-compaction-at-datadog-scale)

Failure mode: high-cardinality tags

The pruning mechanism's bang-for-buck depends on low or structured column cardinality. Husky calls this out explicitly: "service may only have tens or hundreds of values … status a handful … env just prod/staging/dev". For columns with millions of unique values per fragment, the regex/Bloom either grows unbounded or degrades to near-everything-matches.

Where the metadata lives

Husky stores the per-fragment pruning regexes in its FDB-backed metadata service (systems/foundationdb); the query planner fetches metadata for all fragments in the time-bucket range the query intersects, evaluates regexes against predicates, and only then decides which fragments to GET from object storage. This is structurally the same pattern as Parquet footer metadata + predicate pushdown, just with a richer per-column skip predicate.

Seen in

Last updated · 200 distilled / 1,178 read