apache / apache/arrow-rs

Lazily compute the null count of `Array` to reduce cpu cost in `high cardinality aggr`

Open
#6,146 1 comment 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Rust
Stars
3.6k
Forks
1.3k
Avg merge
2d 14h
Merged PRs (30d)
167

Description

**Is your feature request related to a problem or challenge? Please describe what you are trying to do.**

When `group by` columns are of very high cardinality, like clickbench q32, the computation of null count in `slice` function has the non-trivial cpu cost actually(see flamegraph in additional context).
Actually, the null count in `arrow-cpp` will be computed lazily in the scenario that we need to scan the null buffer to get it (such as slice case).
https://github.com/apache/arrow/blob/187197c369058f7d1377c1b161c469a9e4542caf/cpp/src/arrow/array/data.cc#L206-L218

Should `arrow-rust` make `null count` a lazy computation to reduce the cost of `slice`, too?

**Describe the solution you'd like**

Make the `null_count` in `NullBuffer` an `AtomicI64` like `arrow-cpp`.
But I worry other related function calling `null_count` will suffer the performance regression due to introducing the atomic...

**Describe alternatives you've considered**

Maybe we can optimize the `slice()` function in `NullBuffer` only, we check the inputs and found low cost to calculate the new `null_count`.
For example,
- original offset:0, original len: 10
- new offset: 0, new len: 9
We calculate the `null_count in [9, 10)` and the needed `null_count in [0, 9)` = `original null count` - `null_count in [9, 10)`.

**Additional context**

![flame](https://raw.githubusercontent.com/Rachelint/drawio-store/main/dperf.072801.svg)

Contributor guide

Open the contributing guide

Research direction

Start by locating Rust's NullBuffer and its slice() implementation, then compare the proposed behavior with the referenced C++ implementation in cpp/src/arrow/array/data.cc. Measure null-count and slice costs for high-cardinality group-by workloads before choosing between lazy computation and slice-specific calculation. Done means an agreed approach is implemented without unacceptable regression in callers of null_count.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.