You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "neilconway (via GitHub)" <gi...@apache.org> on 2026/09/08 14:17:00 UTC
[PR] perf: compute `cardinality` from list/map offsets [datafusion]
neilconway opened a new pull request, #25079:
URL: https://github.com/apache/datafusion/pull/25079
## Which issue does this PR close?
- Closes #25078
## Rationale for this change
`cardinality` was implemented by iterating over the `values` of the input `GenericListArray`, creating a slice for each logical row, and then fetching the length of the slice. This incurs a lot of unnecessary per-row overhead; we can instead determine the cardinality of each list by looking at the `OffsetBuffer`. This is roughly 100x-500x faster.
For non-nested lists, this is straightforward. It would be possible to use a similar approach to compute the cardinality of nested lists, but for now this PR falls back to the previous approach for that case.
Benchmarks: (M4 Max)
list/valid/8192x32, 203.951 µs → 0.984 µs, -99.52%
large_list/nullable/8192x32, 172.699 µs → 1.049 µs, -99.39%
map/valid/8192x32, 471.074 µs → 0.958 µs, -99.80%
## What changes are included in this PR?
* Add optimized implementation of `cardinality` for non-nested lists/maps
* Add unit tests
* Add benchmark
## What is the testing strategy for this PR?
Existing tests pass; new tests added.
## Are there any user-facing changes?
No.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: compute `cardinality` from list/map offsets [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #25079:
URL: https://github.com/apache/datafusion/pull/25079#issuecomment-5590100007
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/25079?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `96.72131%` with `2 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 81.74%. Comparing base ([`a5c809f`](https://app.codecov.io/gh/apache/datafusion/commit/a5c809f98dedcf4b22f5d317ea8efe0720834925?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`6951d8a`](https://app.codecov.io/gh/apache/datafusion/commit/6951d8af5aebe92778f8ca99d144a48ad9b9cf9e?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
| [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/25079?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [datafusion/functions-nested/src/cardinality.rs](https://app.codecov.io/gh/apache/datafusion/pull/25079?src=pr&el=tree&filepath=datafusion%2Ffunctions-nested%2Fsrc%2Fcardinality.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9mdW5jdGlvbnMtbmVzdGVkL3NyYy9jYXJkaW5hbGl0eS5ycw==) | 96.72% | [0 Missing and 2 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/25079?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #25079 +/- ##
==========================================
- Coverage 81.74% 81.74% -0.01%
==========================================
Files 1128 1128
Lines 416644 416698 +54
Branches 416644 416698 +54
==========================================
+ Hits 340592 340635 +43
- Misses 55995 56000 +5
- Partials 20057 20063 +6
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/25079?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: compute `cardinality` from list/map offsets [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #25079:
URL: https://github.com/apache/datafusion/pull/25079#issuecomment-5633286710
@AdamGS thanks for the review!
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: compute `cardinality` from list/map offsets [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway merged PR #25079:
URL: https://github.com/apache/datafusion/pull/25079
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org