apache / apache/arrow-rs

parquet: add Decoder::scan_filtered for miniblock-level predicate pushdown in DeltaBitPackDecoder

Open
#9,785 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
3.6k
Forks
1.3k
Avg merge
2d 18h
Merged PRs (30d)
169

Description

Range predicates (e.g. `value >= X`) applied to DELTA_BINARY_PACKED columns
currently require decoding every value before filtering. The DELTA format's
per-miniblock headers (`min_delta`, `bit_width`) make it possible to compute a
conservative `[lo, hi]` range for an entire miniblock without decoding
individual values — if the predicate rejects the range, the miniblock can be
skipped in O(1).

**Proposed addition:** A new provided method `Decoder::scan_filtered(num_values,
out, predicate)` on the `Decoder` trait. The default implementation ignores the
predicate and decodes everything (safe fallback for all encodings that don't
carry per-region metadata). `DeltaBitPackDecoder` overrides it to:

1. Check `first_value` as a point range `[v, v]` before entering the miniblock loop.
2. Per miniblock, compute a conservative `[lo, hi]` using `last_value`,
`min_delta`, `bit_width`, and the count of values in the miniblock.
3. If the predicate rejects `[lo, hi]`, skip the miniblock (O(1) for bw=0;
decode-to-track-last_value for mid-stream bw>0 misses; bit-skip for terminal
bw>0 misses).
4. If the predicate accepts, decode and emit the miniblock normally.

Returns `(values_emitted, values_consumed)`.

**Measured improvement:**
- Wall-time scan on 1M-row monotone DELTA column: 1.96ms → 470µs (4.2x)

**Note:** `scan_filtered` is intentionally conservative — a range miss on a
miniblock is always safe (false positives are possible, false negatives are not).
Callers that need exact per-value filtering should apply a second pass on the
emitted values.

Contributor guide

Open the contributing guide

Research direction

Start with the Decoder trait and DeltaBitPackDecoder, then trace the existing miniblock loop and its per-miniblock headers. Implement the conservative scan behavior described for first values, rejected miniblocks, and accepted miniblocks, preserving the default fallback and tuple result. Done means range misses never omit matching values and emitted and consumed counts are correct.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.