Jackie-Jiang commented on code in PR #19440:
URL: https://github.com/apache/pinot/pull/19440#discussion_r3922223498
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BitmapCollection.java:
##########
@@ -26,30 +27,75 @@
/// Encapsulates a collection of bitmaps, and allows inversion without
modifying the bitmaps.
/// Provides simplified access to efficient cardinality calculation which work
regardless of
/// inversion status without computing the complement of the union of the
bitmaps.
+///
+/// The collection is two-valued by default: the true documents are the union
of the bitmaps, or its complement when
+/// inverted, and every other document is false. [#excludingNulls] attaches
the documents the predicate is UNKNOWN
+/// for, which are then neither true nor false: they are left out of the true
documents whether or not they fall in
+/// the bitmaps, and they stay UNKNOWN under inversion, since NOT of UNKNOWN
is UNKNOWN. Every cardinality and
+/// reduction honors the null bitmap.
public class BitmapCollection {
private final int _numDocs;
private boolean _inverted;
private final ImmutableRoaringBitmap[] _bitmaps;
+ @Nullable
+ private final ImmutableRoaringBitmap _nullBitmap;
public BitmapCollection(int numDocs, boolean inverted,
ImmutableRoaringBitmap... bitmaps) {
+ this(numDocs, inverted, bitmaps, null);
+ }
+
+ private BitmapCollection(int numDocs, boolean inverted,
ImmutableRoaringBitmap[] bitmaps,
+ @Nullable ImmutableRoaringBitmap nullBitmap) {
_numDocs = numDocs;
_inverted = inverted;
_bitmaps = bitmaps;
+ _nullBitmap = nullBitmap;
+ }
+
+ /// Returns a collection over the same bitmaps that treats the documents in
`nullBitmap` as UNKNOWN, or this
+ /// collection when `nullBitmap` is `null` or empty.
+ public BitmapCollection excludingNulls(@Nullable ImmutableRoaringBitmap
nullBitmap) {
+ if (nullBitmap == null || nullBitmap.isEmpty()) {
+ return this;
+ }
+ return new BitmapCollection(_numDocs, _inverted, _bitmaps, nullBitmap);
+ }
+
+ /// Returns the documents the predicate is UNKNOWN for, or `null` when there
is none.
+ @Nullable
+ public ImmutableRoaringBitmap getNullBitmap() {
+ return _nullBitmap;
}
- /// Inverts the bitmaps in constant time and space.
+ /// Inverts the bitmaps in constant time and space. The null bitmap is kept:
NOT of UNKNOWN is UNKNOWN.
/// @return this bitmap collection inverted.
public BitmapCollection invert() {
_inverted = !_inverted;
return this;
}
+ /// Returns the number of true documents.
+ public int getCardinality() {
+ ImmutableRoaringBitmap union = reduceInternal();
+ if (_nullBitmap == null) {
+ return _inverted ? _numDocs - union.getCardinality() :
union.getCardinality();
+ }
+ if (_inverted) {
+ return _numDocs - ImmutableRoaringBitmap.orCardinality(union,
_nullBitmap);
+ }
+ return union.getCardinality() -
ImmutableRoaringBitmap.andCardinality(union, _nullBitmap);
+ }
+
/// Computes the size of the intersection of the bitmaps efficiently
regardless of negation, without
- /// needing to invert inputs or materialize an intermediate bitmap.
+ /// needing to invert inputs or materialize an intermediate bitmap. When
either collection has a null bitmap, the
+ /// true documents of both are materialized instead.
///
/// @param bitmaps to intersect with
/// @return the size of the intersection of the bitmaps in this collection
and in the other collection
public int andCardinality(BitmapCollection bitmaps) {
+ if (_nullBitmap != null || bitmaps._nullBitmap != null) {
+ return ImmutableRoaringBitmap.andCardinality(reduce(), bitmaps.reduce());
Review Comment:
When either collection carries nulls, `andCardinality` and `orCardinality`
call `reduce()` on both sides. That materializes true-result bitmaps and can
also materialize a full-segment complement for an inverted input, replacing the
existing cardinality-only shortcut with one or two segment-sized allocations
per query segment. Can we extend the inversion-aware cardinality formulas to
account for each null bitmap without reducing the collections?
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/RangeIndexBasedFilterOperator.java:
##########
@@ -184,6 +184,9 @@ public boolean canOptimizeCount() {
@Override
public int getNumMatchingDocs() {
+ if (getNullBitmap() != null) {
Review Comment:
A non-empty null vector redirects every exact range-index count through
`getBitmaps()`, which materializes the matching bitmap. This drops the range
reader's cardinality-only path. Could we retain
`_rangeIndexReader.getNumMatchingDocs(...)` and adjust for null rows—e.g.
subtract the null-vector cardinality when the stored default value satisfies
the range—similar to the updated sorted-index path?
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
