Jackie-Jiang commented on code in PR #19440:
URL: https://github.com/apache/pinot/pull/19440#discussion_r3927838442
##########
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:
Done. `andCardinality` and `orCardinality` no longer reduce. The
intersection is the existing inversion-aware formula minus the intersection
restricted to the union of the two null bitmaps, and that restricted term is
computed through bitmaps no larger than the null union (`and(X, N)` then one
cardinality call, four inversion cases in `andCardinalityWithin`). The union
size follows from the two cardinalities and the intersection. The no-null path
is byte-for-byte unchanged. `testCardinalitiesMatchMaterializedTrues`
brute-forces every inversion / null combination on both sides against the
materialized true sets.
##########
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:
Done. The range operator keeps `_rangeIndexReader.getNumMatchingDocs(...)`
and subtracts the null vector's cardinality when the column's default null
value satisfies the predicate, evaluated once via `applySV` on the default's
dictionary id (or the typed default for raw columns). The Javadoc states the
invariant this rests on: a null row is stored under the default null value, so
the null rows are all inside or all outside the matched set. The query test now
runs over both a dictionary and a raw range-indexed column so both branches are
exercised.
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/AndFilterOperator.java:
##########
@@ -101,6 +102,16 @@ protected BlockDocIdSet getFalses() {
return new NotDocIdSet(new AndDocIdSet(blockDocIdSets, _queryOptions),
_numDocs);
}
+ /// A conjunction is UNKNOWN where it is neither true nor false: where no
child is false and some child is UNKNOWN.
+ @Override
+ protected BlockDocIdSet getNulls() {
+ if (!mayHaveNulls()) {
+ return EmptyDocIdSet.getInstance();
+ }
+ return new AndDocIdSet(
Review Comment:
Correction to the above: a `BlockDocIdSet` is single-use (`AndDocIdSet` /
`OrDocIdSet` drop their children after the first `iterator()`), so the AND
cannot feed one true-set into both intersections; it asks a child for its trues
a second time when both are needed. The latest push also replaces the
hand-built "trues plus nulls" set in the default `getFalses()` and both
composite `getFalses()` with one `BaseFilterOperator.getNotFalses()`, which the
AND `getNulls()` reuses.
--
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]
