Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Open
Rachelint opened this issue Jul 28, 2024 · 1 comment
Open

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

Rachelint opened this issue Jul 28, 2024 · 1 comment
Labels
enhancement Any new improvement worthy of a entry in the changelog

Comments

@Rachelint
Copy link
Contributor

Rachelint commented Jul 28, 2024 •
edited
Loading

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
@Rachelint Rachelint added the enhancement Any new improvement worthy of a entry in the changelog label Jul 28, 2024
@Rachelint
Copy link
Contributor Author

Rachelint commented Jul 28, 2024 •
edited
Loading

I have made a poc that impl it in the atomic way and introduce it to datafusion:
https://github.com/Rachelint/arrow-datafusion/tree/try-opt-agg

And the q32 in clickbench seems 10~15% faster.
Other querys' time cost seems roughly the same?

┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query        ┃       main ┃ try-opt-agg ┃        Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━━━╇━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ QQuery 0     │     0.81ms │      0.79ms │     no change │
│ QQuery 1     │    69.11ms │     70.56ms │     no change │
│ QQuery 2     │   169.47ms │    168.31ms │     no change │
│ QQuery 3     │   182.60ms │    187.44ms │     no change │
│ QQuery 4     │  1589.41ms │   1604.52ms │     no change │
│ QQuery 5     │  1597.02ms │   1587.10ms │     no change │
│ QQuery 6     │    57.92ms │     63.17ms │  1.09x slower │
│ QQuery 7     │    72.33ms │     71.48ms │     no change │
│ QQuery 8     │  2415.02ms │   2434.26ms │     no change │
│ QQuery 9     │  1928.42ms │   1918.16ms │     no change │
│ QQuery 10    │   544.39ms │    547.84ms │     no change │
│ QQuery 11    │   605.79ms │    602.19ms │     no change │
│ QQuery 12    │  1767.57ms │   1758.03ms │     no change │
│ QQuery 13    │  4073.33ms │   4077.78ms │     no change │
│ QQuery 14    │  2583.14ms │   2605.21ms │     no change │
│ QQuery 15    │  1784.13ms │   1792.49ms │     no change │
│ QQuery 16    │  5028.55ms │   5087.98ms │     no change │
│ QQuery 17    │  4956.14ms │   4939.23ms │     no change │
│ QQuery 18    │ 10436.51ms │  10515.59ms │     no change │
│ QQuery 19    │   144.11ms │    149.23ms │     no change │
│ QQuery 20    │  3310.77ms │   3299.29ms │     no change │
│ QQuery 21    │  3887.09ms │   3892.00ms │     no change │
│ QQuery 22    │  9398.96ms │   9370.21ms │     no change │
│ QQuery 23    │ 23087.26ms │  23049.61ms │     no change │
│ QQuery 24    │  1168.15ms │   1174.31ms │     no change │
│ QQuery 25    │  1046.92ms │   1046.00ms │     no change │
│ QQuery 26    │  1352.80ms │   1362.05ms │     no change │
│ QQuery 27    │  4711.92ms │   4694.96ms │     no change │
│ QQuery 28    │ 21891.92ms │  21818.50ms │     no change │
│ QQuery 29    │   920.19ms │    897.67ms │     no change │
│ QQuery 30    │  2075.81ms │   2077.62ms │     no change │
│ QQuery 31    │  2961.03ms │   2934.88ms │     no change │
│ QQuery 32    │ 16167.05ms │  14340.64ms │ +1.13x faster │
│ QQuery 33    │  9418.20ms │   9414.53ms │     no change │
│ QQuery 34    │  9388.74ms │   9394.28ms │     no change │
│ QQuery 35    │  3108.34ms │   3117.84ms │     no change │
│ QQuery 36    │   270.02ms │    273.27ms │     no change │
│ QQuery 37    │   166.63ms │    170.44ms │     no change │
│ QQuery 38    │   158.33ms │    155.67ms │     no change │
│ QQuery 39    │   834.47ms │    837.39ms │     no change │
│ QQuery 40    │    63.22ms │     63.04ms │     no change │
│ QQuery 41    │    59.97ms │     58.82ms │     no change │
│ QQuery 42    │    70.34ms │     69.78ms │     no change │
└──────────────┴────────────┴─────────────┴───────────────┘

@Rachelint Rachelint changed the title Lazily compute the null count of Array Lazily compute the null count of Array to reduce cpu cost in slice case Jul 28, 2024
@Rachelint Rachelint changed the title Lazily compute the null count of Array to reduce cpu cost in slice case Lazily compute the null count of Array to reduce cpu cost of slice function Jul 28, 2024
@Rachelint Rachelint changed the title Lazily compute the null count of Array to reduce cpu cost of slice function Lazily compute the null count of Array to reduce cpu cost in high cardinality aggr Jul 29, 2024
@Rachelint Rachelint mentioned this issue Jul 29, 2024
Closed
@alamb alamb mentioned this issue Aug 8, 2024
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement Any new improvement worthy of a entry in the changelog
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

lazily compute for null count(seems help to high cardinality aggr) Rachelint/arrow-rs
1 participant
@Rachelint