You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pinot.apache.org by "siddharthteotia (via GitHub)" <gi...@apache.org> on 2026/05/20 15:45:10 UTC
[PR] Avoid materializing the full bitmap for count aggregation with filter on column with inverted index [pinot]
siddharthteotia opened a new pull request, #18543:
URL: https://github.com/apache/pinot/pull/18543
### Improvement Summary
- Optimizes `InvertedIndexFilterOperator.getNumMatchingDocs()` for single-value columns by replacing the materialized-union approach with a sum of per-dictId bitmap cardinalitie
- Eliminates MutableRoaringBitmap allocation on the hot count path and yields speedups
- Addresses an old TODO in the code referring to this optimization.
- Multi-value path is unchanged in this PR — an approach was prototyped and benchmarked but regressed at the edges. Will do a follow-up PR for thisthreshold-aware MV optimization will follow in a separate PR.
### Functional Testing
- Added new unit test focused on specific code paths for 100% coverage
- All existing SV and MV query tests that exercise this code path are passing. No new e2e query tests should be needed
### Performance Testing
See BenchmarkInvertedIndexGetNumMatchingDocs
- JMH, numDocs=5M, Used -prof GC option with JMH
- JDK 21, macOS Apple Silicon (re ran on x86 as well to cross check)
- Dictionary cardinality ∈ {1024, 100K, 1M}
- NumMatcingDictIDs (K) ∈ {4, 16, 64, 256, 1K, 10K, 100K}
**SV Results**
#### dict cardinality = 1K
| K | current | new | speedup | current alloc| new alloc |
|------:|---------:|----------:|--------:|--------------:|---------------:|
| 4 | 44.71 µs | 90 ns | 499x | 137.4 KB | 0 B |
| 16 | 738 µs | 530 ns | 1392x | 565.5 KB | 0 B |
| 64 | 8.39 ms | 4.12 µs | 2035x | 3.36 MB | 0 B |
| 256 | 9.65 ms | 16.57 µs | 582x | 3.41 MB | 0 B |
| 1,000 | 14.10 ms | 66.77 µs | 211x | 3.41 MB | 0 B |
dict cardinality = 100K
| K | current | new | speedup | current alloc | new alloc |
|--------:|----------:|----------:|--------:|--------------:|---------------:|
| 4 | 3.51 µs | 63 ns | 56x | 13.1 KB | 0 B |
| 16 | 19.53 µs | 339 ns | 58x | 33.1 KB | 0 B |
| 64 | 103.73 µs | 3.05 µs | 34x | 63.4 KB | 0 B |
| 256 | 1.20 ms | 14.39 µs | 84x | 183.0 KB | 0 B |
| 1,000 | 11.77 ms | 64.41 µs | 183x | 547.9 KB | 0 B |
| 10,000 | 223.15 ms | 3.50 ms | 64x | 3.82 MB | 0 B |
| 100,000 | 428.49 ms | 36.62 ms | 12x | 3.85 MB | 0 B |
dict cardinality = 1M
| K | current | new | speedup | current alloc | new alloc |
|--------:|----------:|----------:|--------:|--------------:|---------------:|
| 4 | 1.39 µs | 25 ns | 55x | 5.3 KB | 0 B |
| 16 | 6.17 µs | 120 ns | 51x | 12.8 KB | 0 B |
| 64 | 23.08 µs | 618 ns | 37x | 30.7 KB | 0 B |
| 256 | 132.59 µs | 3.81 µs | 35x | 53.8 KB | 0 B |
| 1,000 | 996.64 µs | 24.31 µs | 41x | 137.8 KB | 0 B |
| 10,000 | 44.85 ms | 260.38 µs | 172x | 1016.4 KB | 0 B |
| 100,000 | 342.36 ms | 9.36 ms | 37x | 4.00 MB | 32 B |
Note
- Allocation is allocation per query (per segment per server).
- 3.36MB for a query touching 100 segments at 1000QPS is 336GB/sec of young gen pressure.
**MV Results (MV Implementation not changed in this PR but bench test has MV POC code)*
- Tried with . BufferFastAggregation.orCardinality
- This also allocates internally a scratch bitmap
- Does a two-pass scan over all input bitmaps (pass 1 collects union container keys; pass 2 ORs the matching container from each input into a reused scratch container, per key)
- At low K with tiny per-bitmap cardinality (sparse columns) the fixed scratch cost is unamortized. At very high K with high cardinality, the per-key bitmap walk dominates.
- So the results were mixed (upto 7x faster but also 2x slower in some cases).
### Backwards Compatibility
- Compatible
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Avoid materializing the full bitmap for count aggregation with filter on column with inverted index [pinot]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #18543:
URL: https://github.com/apache/pinot/pull/18543#issuecomment-4500606161
## [Codecov](https://app.codecov.io/gh/apache/pinot/pull/18543?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 `82.35294%` with `3 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 56.73%. Comparing base ([`2910445`](https://app.codecov.io/gh/apache/pinot/commit/29104455383b5b81581db6098cd9bf34020c64b9?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`e1f00b8`](https://app.codecov.io/gh/apache/pinot/commit/e1f00b8ac1fe2dc48f376abf29bb1cd218846328?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 15 commits behind head on master.
| [Files with missing lines](https://app.codecov.io/gh/apache/pinot/pull/18543?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [...e/operator/filter/InvertedIndexFilterOperator.java](https://app.codecov.io/gh/apache/pinot/pull/18543?src=pr&el=tree&filepath=pinot-core%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fpinot%2Fcore%2Foperator%2Ffilter%2FInvertedIndexFilterOperator.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9vcGVyYXRvci9maWx0ZXIvSW52ZXJ0ZWRJbmRleEZpbHRlck9wZXJhdG9yLmphdmE=) | 82.35% | [2 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/pinot/pull/18543?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
> :exclamation: There is a different number of reports uploaded between BASE (2910445) and HEAD (e1f00b8). Click for more details.
>
> <details><summary>HEAD has 16 uploads less than BASE</summary>
>
>| Flag | BASE (2910445) | HEAD (e1f00b8) |
>|------|------|------|
>|java-21|5|1|
>|unittests|2|1|
>|temurin|5|1|
>|unittests2|1|0|
>|integration|3|0|
>|integration1|1|0|
>|integration2|1|0|
>|custom-integration1|1|0|
></details>
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## master #18543 +/- ##
============================================
- Coverage 63.75% 56.73% -7.02%
============================================
Files 3292 2561 -731
Lines 201470 148597 -52873
Branches 31316 24022 -7294
============================================
- Hits 128442 84311 -44131
+ Misses 62735 57119 -5616
+ Partials 10293 7167 -3126
```
| [Flag](https://app.codecov.io/gh/apache/pinot/pull/18543/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Coverage Δ | |
|---|---|---|
| [custom-integration1](https://app.codecov.io/gh/apache/pinot/pull/18543/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [integration](https://app.codecov.io/gh/apache/pinot/pull/18543/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [integration1](https://app.codecov.io/gh/apache/pinot/pull/18543/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [integration2](https://app.codecov.io/gh/apache/pinot/pull/18543/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [java-21](https://app.codecov.io/gh/apache/pinot/pull/18543/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `56.73% <82.35%> (-7.02%)` | :arrow_down: |
| [temurin](https://app.codecov.io/gh/apache/pinot/pull/18543/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `56.73% <82.35%> (-7.02%)` | :arrow_down: |
| [unittests](https://app.codecov.io/gh/apache/pinot/pull/18543/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `56.73% <82.35%> (-7.02%)` | :arrow_down: |
| [unittests1](https://app.codecov.io/gh/apache/pinot/pull/18543/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `56.73% <82.35%> (+0.93%)` | :arrow_up: |
| [unittests2](https://app.codecov.io/gh/apache/pinot/pull/18543/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#carryforward-flags-in-the-pull-request-comment) to find out more.
</details>
[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/apache/pinot/pull/18543?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>
- :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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Avoid materializing the full bitmap for count aggregation with filter on column with inverted index [pinot]
Posted by "Jackie-Jiang (via GitHub)" <gi...@apache.org>.
Jackie-Jiang merged PR #18543:
URL: https://github.com/apache/pinot/pull/18543
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org