bharadwaj-pendyala opened a new pull request, #11257:
URL: https://github.com/apache/arrow-rs/pull/11257
# Which issue does this PR close?
- Closes #11200.
# Rationale for this change
When the input has nulls, `FilterPredicate::filter_nulls` always filters the
validity into a new buffer and counts it, then drops the buffer if the count
comes out zero. A filter that keeps no null rows, like `x IS NOT NULL AND ...`,
pays for a bitmap it never uses.
# What changes are included in this PR?
`filter_nulls` now asks `selects_null` first and returns `None` straight
away when no selected row is null.
`selects_null` zips the 64-bit words of the mask and the validity and stops
at the first word where `keep & !valid` is non-zero. It doesn't allocate, and
it takes the offsets of both buffers into account. For an optimized `Indices`
predicate below one selected row per word, it probes those indices instead.
That's the crossover `filter_bits` already uses for `sparse_indices`. Without
it, a 1/2048 filter scans all 1024 words to check 32 rows, and above that
crossover the word scan wins. An early version probed indices for every
`Indices` predicate and took 98 µs at kept 1/4 instead of 43 µs.
`selects_null` also asserts the null buffer covers the filter. Before, a
too-short buffer panicked inside `filter_bits`. Without the assert, the sparse
index path would read only the selected rows and quietly return `None`.
# Are these changes tested?
Yes, in `arrow-select/src/filter.rs`:
- `test_filter_nulls_selecting_only_valid_rows` asserts `selects_null` is
false and the filtered array has no null buffer.
- `test_filter_nulls_selecting_one_null` asserts it's true when the only
selected null is row 0 (a full word) or row 129 (the partial last word).
Both run the lazy and optimized predicates, sliced and unsliced masks, over
values sliced at offset 1. The null patterns put the masks on both sides of the
slices threshold. `test_filter_nulls_shorter_than_filter` covers the assert.
Each of these edits turns at least one test red: dropping the trailing
partial word, ignoring the null buffer's offset, ignoring the mask's offset,
having the index probe return false, having `selects_null` return true (today's
behaviour), and removing the assert.
`cargo test -p arrow-select` is 447 passed, 0 failed. `cargo test -p parquet
--features arrow --lib arrow::arrow_reader` is 145 passed. `cargo fmt --all --
--check` and `cargo clippy -p arrow-select --all-targets --all-features -- -D
warnings` are clean.
Benchmarks are the cases from #11256. I built two release binaries, main at
`fa337f8` and this branch, and ran them alternately. M1 laptop, criterion
median, 3 rounds unless noted:
```
main
this PR
i32 w NULLs, only valid (kept 1/4) 73-135 µs
42-43 µs
i32 w NULLs, only valid high sel. (kept 1023/2048) 147-222 µs
73-74 µs
i32 w NULLs, only valid low sel. (kept 1/2048) 1.10-1.13 µs
0.63-0.66 µs
i32 w NULLs at end (kept 1/2) 219-222 µs
223-226 µs
i32 w NULLs at end high sel. (kept 1023/1024), 8 rounds ~42 µs
~45 µs
i32 w NULLs (kept 1/2), existing 221-230 µs
221-223 µs
i32 w NULLs high sel. (kept 1023/1024), existing 43-51 µs 43
µs
```
The last two nulls-at-end rows are the cost. When the only selected null
sits in the last word, the scan reads both bitmaps once before `filter_bits`
reads them again, which comes to about 7% on the dense case. With random nulls
the scan stops in the first word, and the existing cases don't move beyond
noise. Main swings a lot on the only-valid rows between runs, and this branch
doesn't, so the low end of the main range is the fair comparison.
# Are there any user-facing changes?
No API change. `filter_nulls` returns the same thing as before. A null
buffer shorter than the filter that has any nulls still panics, now with
`assertion failed: nulls.len() >= len` whatever the strategy.
# AI usage
Claude wrote the change, tests and benchmarks. Codex reviewed the diff
adversarially twice before the push. The first pass flagged the index probe
running for dense `Indices` predicates and the missing length check. The second
pass flagged that the only-valid test would pass even if `selects_null` always
returned true. I fixed all three and ran the edits above to check the tests
catch them. I also measured every number here myself.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
