This is an automated email from the ASF dual-hosted git repository.
Jackie-Jiang pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/pinot.git
The following commit(s) were added to refs/heads/master by this push:
new 92360684523 Make filter count and bitmap shortcuts three-valued under
null handling (#19440)
92360684523 is described below
commit 92360684523ab24998d9f104596a3de3f9452528
Author: Xiaotian (Jackie) Jiang <[email protected]>
AuthorDate: Mon Sep 14 22:37:07 2026 -0700
Make filter count and bitmap shortcuts three-valued under null handling
(#19440)
---
.../core/operator/filter/AndFilterOperator.java | 80 +++++---
.../operator/filter/BaseColumnFilterOperator.java | 66 ++++---
.../core/operator/filter/BaseFilterOperator.java | 65 +++++--
.../operator/filter/BitmapBasedFilterOperator.java | 45 ++++-
.../core/operator/filter/BitmapCollection.java | 127 +++++++++++--
.../operator/filter/ExpressionFilterOperator.java | 25 ++-
.../core/operator/filter/FilterOperatorUtils.java | 43 ++++-
.../filter/InvertedIndexFilterOperator.java | 24 ++-
.../core/operator/filter/MapFilterOperator.java | 10 +
.../core/operator/filter/NotFilterOperator.java | 33 +++-
.../core/operator/filter/OrFilterOperator.java | 77 +++++---
.../filter/RangeIndexBasedFilterOperator.java | 35 +++-
.../filter/SortedIndexBasedFilterOperator.java | 19 +-
.../apache/pinot/core/startree/StarTreeUtils.java | 46 +++--
.../operator/filter/AndFilterOperatorTest.java | 111 +++++++++++
.../core/operator/filter/BitmapCollectionTest.java | 91 +++++++++
.../filter/InvertedIndexFilterOperatorTest.java | 64 ++++++-
.../operator/filter/NotFilterOperatorTest.java | 81 +++++++-
.../core/operator/filter/OrFilterOperatorTest.java | 68 +++++++
.../pinot/core/startree/v2/BaseStarTreeV2Test.java | 4 +-
.../queries/NullHandlingEnabledQueriesTest.java | 210 +++++++++++++++++++++
.../queries/StarTreeNullHandlingQueriesTest.java | 210 +++++++++++++++++++++
.../tests/NullHandlingIntegrationTest.java | 6 +-
23 files changed, 1389 insertions(+), 151 deletions(-)
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/AndFilterOperator.java
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/AndFilterOperator.java
index 53ed6e4b53f..fca2858a5ed 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/AndFilterOperator.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/AndFilterOperator.java
@@ -28,12 +28,11 @@ import org.apache.pinot.core.common.Operator;
import org.apache.pinot.core.operator.docidsets.AndDocIdSet;
import org.apache.pinot.core.operator.docidsets.EmptyDocIdSet;
import org.apache.pinot.core.operator.docidsets.MatchAllDocIdSet;
-import org.apache.pinot.core.operator.docidsets.NotDocIdSet;
-import org.apache.pinot.core.operator.docidsets.OrDocIdSet;
import org.apache.pinot.core.operator.docidsets.ShortCircuitingDocIdSet;
import org.apache.pinot.spi.trace.Tracing;
import org.roaringbitmap.buffer.BufferFastAggregation;
import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
public class AndFilterOperator extends BaseFilterOperator {
@@ -72,33 +71,29 @@ public class AndFilterOperator extends BaseFilterOperator {
return new AndDocIdSet(blockDocIdSets, _queryOptions);
}
+ /// A conjunction is not false where no child is false: the intersection of
the children's not-false documents.
@Override
- protected BlockDocIdSet getFalses() {
- List<BlockDocIdSet> blockDocIdSets = new
ArrayList<>(_filterOperators.size());
+ protected BlockDocIdSet getNotFalses() {
+ List<BlockDocIdSet> notFalses = new ArrayList<>(_filterOperators.size());
for (BaseFilterOperator filterOperator : _filterOperators) {
- BlockDocIdSet trues = filterOperator.getTrues();
- if (trues instanceof EmptyDocIdSet) {
- return new MatchAllDocIdSet(_numDocs);
+ BlockDocIdSet childNotFalses = filterOperator.getNotFalses();
+ if (childNotFalses instanceof EmptyDocIdSet) {
+ return EmptyDocIdSet.getInstance();
}
- if (trues instanceof MatchAllDocIdSet) {
+ if (childNotFalses instanceof MatchAllDocIdSet) {
continue;
}
- if (_nullHandlingEnabled) {
- BlockDocIdSet nulls = filterOperator.getNulls();
- if (!(nulls instanceof EmptyDocIdSet)) {
- blockDocIdSets.add(new OrDocIdSet(Arrays.asList(trues, nulls),
_numDocs));
- continue;
- }
- }
- blockDocIdSets.add(trues);
- }
- if (blockDocIdSets.isEmpty()) {
- return EmptyDocIdSet.getInstance();
+ notFalses.add(childNotFalses);
}
- if (blockDocIdSets.size() == 1) {
- return new NotDocIdSet(blockDocIdSets.get(0), _numDocs);
+ if (notFalses.isEmpty()) {
+ return new MatchAllDocIdSet(_numDocs);
}
- return new NotDocIdSet(new AndDocIdSet(blockDocIdSets, _queryOptions),
_numDocs);
+ return notFalses.size() == 1 ? notFalses.get(0) : new
AndDocIdSet(notFalses, _queryOptions);
+ }
+
+ @Override
+ protected BlockDocIdSet getNulls() {
+ return mayHaveNulls() ? deriveNulls(_queryOptions) :
EmptyDocIdSet.getInstance();
}
@Override
@@ -129,13 +124,46 @@ public class AndFilterOperator extends BaseFilterOperator
{
return true;
}
+ /// The true documents are those true for every child. When a child has
UNKNOWN documents, so has the result: a
+ /// document is UNKNOWN when no child is false for it and some child is
UNKNOWN, which is the intersection of the
+ /// children's not-false documents minus the intersection of their true ones.
@Override
public BitmapCollection getBitmaps() {
- ImmutableRoaringBitmap[] bitmaps = new
ImmutableRoaringBitmap[_filterOperators.size()];
- for (int i = 0; i < _filterOperators.size(); i++) {
- bitmaps[i] = _filterOperators.get(i).getBitmaps().reduce();
+ int numChildren = _filterOperators.size();
+ ImmutableRoaringBitmap[] trues = new ImmutableRoaringBitmap[numChildren];
+ ImmutableRoaringBitmap[] notFalses = null;
+ for (int i = 0; i < numChildren; i++) {
+ BitmapCollection childBitmaps = _filterOperators.get(i).getBitmaps();
+ trues[i] = childBitmaps.reduce();
+ ImmutableRoaringBitmap childNulls = childBitmaps.getNullBitmap();
+ if (childNulls != null) {
+ if (notFalses == null) {
+ notFalses = Arrays.copyOf(trues, numChildren);
+ }
+ notFalses[i] = ImmutableRoaringBitmap.or(trues[i], childNulls);
+ } else if (notFalses != null) {
+ notFalses[i] = trues[i];
+ }
+ }
+ MutableRoaringBitmap andTrues = BufferFastAggregation.and(trues);
+ if (notFalses == null) {
+ return new BitmapCollection(_numDocs, false, andTrues);
+ }
+ MutableRoaringBitmap nulls = BufferFastAggregation.and(notFalses);
+ nulls.andNot(andTrues);
+ return new BitmapCollection(_numDocs, false,
andTrues).excludingNulls(nulls);
+ }
+
+ @Override
+ public boolean mayHaveNulls() {
+ if (_nullHandlingEnabled) {
+ for (BaseFilterOperator filterOperator : _filterOperators) {
+ if (filterOperator.mayHaveNulls()) {
+ return true;
+ }
+ }
}
- return new BitmapCollection(_numDocs, false,
BufferFastAggregation.and(bitmaps));
+ return false;
}
@Override
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BaseColumnFilterOperator.java
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BaseColumnFilterOperator.java
index 7b31b13d445..e74da0edb5c 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BaseColumnFilterOperator.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BaseColumnFilterOperator.java
@@ -18,64 +18,86 @@
*/
package org.apache.pinot.core.operator.filter;
-import java.util.Arrays;
+import java.util.List;
import javax.annotation.Nullable;
import org.apache.pinot.core.common.BlockDocIdSet;
import org.apache.pinot.core.operator.docidsets.AndDocIdSet;
import org.apache.pinot.core.operator.docidsets.BitmapDocIdSet;
import org.apache.pinot.core.operator.docidsets.EmptyDocIdSet;
+import org.apache.pinot.core.operator.docidsets.OrDocIdSet;
import org.apache.pinot.core.query.request.context.QueryContext;
import org.apache.pinot.segment.spi.datasource.DataSource;
-import org.apache.pinot.segment.spi.index.reader.NullValueVectorReader;
import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
public abstract class BaseColumnFilterOperator extends BaseFilterOperator {
protected final QueryContext _queryContext;
protected final DataSource _dataSource;
+ @Nullable
+ private final ImmutableRoaringBitmap _nullBitmap;
protected BaseColumnFilterOperator(QueryContext queryContext, DataSource
dataSource, int numDocs) {
super(numDocs, queryContext.isNullHandlingEnabled());
_queryContext = queryContext;
_dataSource = dataSource;
+ _nullBitmap = _nullHandlingEnabled ?
FilterOperatorUtils.getNullBitmap(dataSource) : null;
}
protected abstract BlockDocIdSet getNextBlockWithoutNullHandling();
@Override
protected BlockDocIdSet getTrues() {
- if (_nullHandlingEnabled) {
- ImmutableRoaringBitmap nullBitmap = getNullBitmap();
- if (nullBitmap != null && !nullBitmap.isEmpty()) {
- return excludeNulls(getNextBlockWithoutNullHandling(), nullBitmap);
- }
+ if (_nullBitmap != null) {
+ return excludeNulls(getNextBlockWithoutNullHandling(), _nullBitmap);
}
return getNextBlockWithoutNullHandling();
}
@Override
protected BlockDocIdSet getNulls() {
- ImmutableRoaringBitmap nullBitmap = getNullBitmap();
- if (nullBitmap != null && !nullBitmap.isEmpty()) {
- return new BitmapDocIdSet(nullBitmap, _numDocs);
- } else {
- return EmptyDocIdSet.getInstance();
+ return _nullBitmap != null ? new BitmapDocIdSet(_nullBitmap, _numDocs) :
EmptyDocIdSet.getInstance();
+ }
+
+ /// The not-false documents are the ones matching the predicate over the
stored values together with the null ones.
+ /// The default implementation reads [#getTrues], which takes the null rows
out of the match, only to put them back.
+ @Override
+ protected BlockDocIdSet getNotFalses() {
+ BlockDocIdSet matches = getNextBlockWithoutNullHandling();
+ if (_nullBitmap == null) {
+ return matches;
}
+ return new OrDocIdSet(List.of(matches, new BitmapDocIdSet(_nullBitmap,
_numDocs)), _numDocs);
}
- private BlockDocIdSet excludeNulls(BlockDocIdSet blockDocIdSet,
ImmutableRoaringBitmap nullBitmap) {
- return new AndDocIdSet(Arrays.asList(blockDocIdSet,
- new BitmapDocIdSet(ImmutableRoaringBitmap.flip(nullBitmap, 0, (long)
_numDocs), _numDocs)),
- _queryContext.getQueryOptions());
+ @Override
+ public boolean mayHaveNulls() {
+ return _nullBitmap != null;
}
+ /// Returns the documents the predicate is UNKNOWN for, or `null` when there
is none: null handling is disabled, or
+ /// the column has no null row. The bitmap is read once, at construction, so
that every view of the operator agrees
+ /// on the same documents even on a consuming segment, whose vector hands
out a fresh copy on each read. An
+ /// implementation with a count or bitmap shortcut attaches it to its
[BitmapCollection] so that those leave the null
+ /// documents out too.
@Nullable
- private ImmutableRoaringBitmap getNullBitmap() {
- NullValueVectorReader nullValueVector = _dataSource.getNullValueVector();
- if (nullValueVector != null) {
- return nullValueVector.getNullBitmap();
- } else {
- return null;
+ protected ImmutableRoaringBitmap getNullBitmap() {
+ return _nullBitmap;
+ }
+
+ /// Returns how many documents are true when the index finds
`numMatchingDocs` documents matching the predicate's
+ /// values, `numMatchingNulls` of which are null rows and so UNKNOWN rather
than true. When `exclusive`, the index
+ /// found the documents that do not match, and the true documents are the
rest minus the null rows among the rest.
+ protected int toNumTrueDocs(int numMatchingDocs, int numMatchingNulls,
boolean exclusive) {
+ if (exclusive) {
+ int numNulls = _nullBitmap != null ? _nullBitmap.getCardinality() : 0;
+ return _numDocs - numMatchingDocs - (numNulls - numMatchingNulls);
}
+ return numMatchingDocs - numMatchingNulls;
+ }
+
+ private BlockDocIdSet excludeNulls(BlockDocIdSet blockDocIdSet,
ImmutableRoaringBitmap nullBitmap) {
+ return new AndDocIdSet(List.of(blockDocIdSet,
+ new BitmapDocIdSet(ImmutableRoaringBitmap.flip(nullBitmap, 0, (long)
_numDocs), _numDocs)),
+ _queryContext.getQueryOptions());
}
}
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BaseFilterOperator.java
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BaseFilterOperator.java
index e45c2f47545..0293a003d9a 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BaseFilterOperator.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BaseFilterOperator.java
@@ -18,12 +18,14 @@
*/
package org.apache.pinot.core.operator.filter;
-import java.util.Arrays;
+import java.util.List;
+import java.util.Map;
import javax.annotation.Nullable;
import org.apache.pinot.core.common.BlockDocIdIterator;
import org.apache.pinot.core.common.BlockDocIdSet;
import org.apache.pinot.core.operator.BaseOperator;
import org.apache.pinot.core.operator.blocks.FilterBlock;
+import org.apache.pinot.core.operator.docidsets.AndDocIdSet;
import org.apache.pinot.core.operator.docidsets.EmptyDocIdSet;
import org.apache.pinot.core.operator.docidsets.MatchAllDocIdSet;
import org.apache.pinot.core.operator.docidsets.NotDocIdSet;
@@ -70,11 +72,20 @@ public abstract class BaseFilterOperator extends
BaseOperator<FilterBlock> {
return false;
}
- /// @return bitmaps of matching docIds
+ /// Returns the true documents as bitmaps. The collection leaves out the
documents the filter is UNKNOWN for and
+ /// carries them, so that its inversion leaves them out as well.
public BitmapCollection getBitmaps() {
throw new UnsupportedOperationException();
}
+ /// Returns whether some documents may be UNKNOWN to this filter, that is
whether [#getNulls] may be non-empty. The
+ /// answer comes from metadata rather than from evaluating the filter, so it
may be pessimistic, and it is `false`
+ /// whenever null handling is disabled, since every document then reads as a
value. A parent that derives its result
+ /// from the two-valued shortcuts alone, such as a negation counting the
complement, consults this before doing so.
+ public boolean mayHaveNulls() {
+ return _nullHandlingEnabled;
+ }
+
/// Exact filtered docIds for the operator. `null` indicates match-all.
public static final class FilteredDocIds {
@Nullable
@@ -139,22 +150,52 @@ public abstract class BaseFilterOperator extends
BaseOperator<FilterBlock> {
return EmptyDocIdSet.getInstance();
}
- /// @return document IDs in which the predicate evaluates to false.
- protected BlockDocIdSet getFalses() {
+ /// Returns the document IDs in which the predicate does not evaluate to
false: the true ones and, with null
+ /// handling enabled, the NULL ones. The result is a [MatchAllDocIdSet] when
the predicate is true everywhere and an
+ /// [EmptyDocIdSet] when it is false everywhere, so that a parent can
short-circuit on either.
+ protected BlockDocIdSet getNotFalses() {
BlockDocIdSet trues = getTrues();
- if (trues instanceof MatchAllDocIdSet) {
+ if (!_nullHandlingEnabled || trues instanceof MatchAllDocIdSet) {
+ return trues;
+ }
+ BlockDocIdSet nulls = getNulls();
+ if (nulls instanceof EmptyDocIdSet) {
+ return trues;
+ }
+ return trues instanceof EmptyDocIdSet ? nulls : new
OrDocIdSet(List.of(trues, nulls), _numDocs);
+ }
+
+ /// Returns the document IDs in which the predicate evaluates to NULL,
derived as the ones that are neither false
+ /// nor true.
+ ///
+ /// Only for operators that override [#getNotFalses]. The default
[#getNotFalses] reads [#getNulls], so an operator
+ /// that keeps it would recurse; a leaf returns its UNKNOWN documents
directly instead.
+ protected BlockDocIdSet deriveNulls(@Nullable Map<String, String>
queryOptions) {
+ BlockDocIdSet notFalses = getNotFalses().getOptimizedDocIdSet();
+ if (notFalses instanceof EmptyDocIdSet) {
return EmptyDocIdSet.getInstance();
}
- if (_nullHandlingEnabled) {
- BlockDocIdSet nulls = getNulls();
- if (!(nulls instanceof EmptyDocIdSet)) {
- return new NotDocIdSet(new OrDocIdSet(Arrays.asList(trues, nulls),
_numDocs),
- _numDocs);
- }
+ BlockDocIdSet trues = getTrues().getOptimizedDocIdSet();
+ if (trues instanceof MatchAllDocIdSet) {
+ return EmptyDocIdSet.getInstance();
}
if (trues instanceof EmptyDocIdSet) {
+ return notFalses;
+ }
+ BlockDocIdSet notTrues = new NotDocIdSet(trues, _numDocs);
+ return notFalses instanceof MatchAllDocIdSet ? notTrues
+ : new AndDocIdSet(List.of(notFalses, notTrues), queryOptions);
+ }
+
+ /// @return document IDs in which the predicate evaluates to false.
+ protected BlockDocIdSet getFalses() {
+ BlockDocIdSet notFalses = getNotFalses();
+ if (notFalses instanceof MatchAllDocIdSet) {
+ return EmptyDocIdSet.getInstance();
+ }
+ if (notFalses instanceof EmptyDocIdSet) {
return new MatchAllDocIdSet(_numDocs);
}
- return new NotDocIdSet(trues, _numDocs);
+ return new NotDocIdSet(notFalses, _numDocs);
}
}
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BitmapBasedFilterOperator.java
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BitmapBasedFilterOperator.java
index da9073eec88..3fbcf1f5944 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BitmapBasedFilterOperator.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BitmapBasedFilterOperator.java
@@ -19,22 +19,54 @@
package org.apache.pinot.core.operator.filter;
import java.util.List;
+import javax.annotation.Nullable;
import org.apache.pinot.core.common.BlockDocIdSet;
import org.apache.pinot.core.common.Operator;
import org.apache.pinot.core.operator.docidsets.BitmapDocIdSet;
+import org.apache.pinot.core.operator.docidsets.EmptyDocIdSet;
import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+/// Filter over a fixed set of documents.
+///
+/// `docIds` are the documents the predicate is true for or, when `exclusive`,
the documents it is not true for, so
+/// that it is true for every other one. Without a null bitmap the predicate
is two-valued: the false documents are
+/// the complement of the true ones, and [#getNulls] is empty.
+///
+/// A null bitmap adds the documents the predicate is UNKNOWN for. The true,
false and null documents must partition
+/// the whole, so the null bitmap has to be disjoint from the true documents:
contained in `docIds` when `exclusive`,
+/// disjoint from `docIds` otherwise. The caller guarantees it; the operator
only asserts it. The two bitmaps are
+/// otherwise independent, and [#getNulls] returns the null bitmap as given.
The count and the bitmaps leave the null
+/// documents out as well, and the bitmaps carry them so that an inversion
leaves them out too.
public class BitmapBasedFilterOperator extends BaseFilterOperator {
private static final String EXPLAIN_NAME = "FILTER_BITMAP";
private final ImmutableRoaringBitmap _docIds;
private final boolean _exclusive;
+ @Nullable
+ private final ImmutableRoaringBitmap _nullBitmap;
public BitmapBasedFilterOperator(ImmutableRoaringBitmap docIds, boolean
exclusive, int numDocs) {
- super(numDocs, false);
+ this(docIds, exclusive, numDocs, null);
+ }
+
+ /// Creates a filter over the given documents that also knows the documents
the predicate is UNKNOWN for, so that
+ /// its complement leaves them out: NOT of UNKNOWN is UNKNOWN, not true.
+ ///
+ /// `nullBitmap` must be disjoint from the documents the predicate is true
for, as described on the class. A
+ /// predicate that is true on every non-null document is `(nullBitmap, true,
numDocs, nullBitmap)`, and one that is
+ /// true on none is `(empty, false, numDocs, nullBitmap)`.
+ public BitmapBasedFilterOperator(ImmutableRoaringBitmap docIds, boolean
exclusive, int numDocs,
+ @Nullable ImmutableRoaringBitmap nullBitmap) {
+ super(numDocs, nullBitmap != null);
+ assert nullBitmap == null
+ || (exclusive
+ ? ImmutableRoaringBitmap.andNotCardinality(nullBitmap, docIds) == 0
+ : !ImmutableRoaringBitmap.intersects(docIds, nullBitmap))
+ : "The null bitmap must be disjoint from the trues";
_docIds = docIds;
_exclusive = exclusive;
+ _nullBitmap = nullBitmap;
}
@Override
@@ -46,6 +78,11 @@ public class BitmapBasedFilterOperator extends
BaseFilterOperator {
}
}
+ @Override
+ protected BlockDocIdSet getNulls() {
+ return _nullBitmap != null ? new BitmapDocIdSet(_nullBitmap, _numDocs) :
EmptyDocIdSet.getInstance();
+ }
+
@Override
public boolean canOptimizeCount() {
return true;
@@ -53,6 +90,9 @@ public class BitmapBasedFilterOperator extends
BaseFilterOperator {
@Override
public int getNumMatchingDocs() {
+ if (_nullBitmap != null) {
+ return getBitmaps().getCardinality();
+ }
int count = _docIds.getCardinality();
return _exclusive ? _numDocs - count : count;
}
@@ -64,10 +104,9 @@ public class BitmapBasedFilterOperator extends
BaseFilterOperator {
@Override
public BitmapCollection getBitmaps() {
- return new BitmapCollection(_numDocs, _exclusive, _docIds);
+ return new BitmapCollection(_numDocs, _exclusive,
_docIds).excludingNulls(_nullBitmap);
}
-
@Override
@SuppressWarnings("rawtypes")
public List<Operator> getChildOperators() {
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BitmapCollection.java
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BitmapCollection.java
index 7ba6f1e5428..4b59289140a 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BitmapCollection.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BitmapCollection.java
@@ -18,6 +18,7 @@
*/
package org.apache.pinot.core.operator.filter;
+import javax.annotation.Nullable;
import org.roaringbitmap.buffer.BufferFastAggregation;
import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
import org.roaringbitmap.buffer.MutableRoaringBitmap;
@@ -26,54 +27,145 @@ import org.roaringbitmap.buffer.MutableRoaringBitmap;
/// 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() {
+ return getCardinality(reduceInternal());
+ }
+
+ private int getCardinality(ImmutableRoaringBitmap union) {
+ 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. The
UNKNOWN documents of either collection are
+ /// taken out through bitmaps no larger than the null bitmaps themselves.
///
/// @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) {
- ImmutableRoaringBitmap left = reduceInternal();
- ImmutableRoaringBitmap right = bitmaps.reduceInternal();
+ return andCardinality(reduceInternal(), bitmaps.reduceInternal(), bitmaps);
+ }
+
+ private int andCardinality(ImmutableRoaringBitmap left,
ImmutableRoaringBitmap right, BitmapCollection bitmaps) {
+ int cardinality;
if (!_inverted) {
if (!bitmaps._inverted) {
- return ImmutableRoaringBitmap.andCardinality(left, right);
+ cardinality = ImmutableRoaringBitmap.andCardinality(left, right);
+ } else {
+ cardinality = ImmutableRoaringBitmap.andNotCardinality(left, right);
}
- return ImmutableRoaringBitmap.andNotCardinality(left, right);
} else {
if (!bitmaps._inverted) {
- return ImmutableRoaringBitmap.andNotCardinality(right, left);
+ cardinality = ImmutableRoaringBitmap.andNotCardinality(right, left);
+ } else {
+ cardinality = _numDocs - ImmutableRoaringBitmap.orCardinality(left,
right);
}
- return _numDocs - ImmutableRoaringBitmap.orCardinality(left, right);
}
+ ImmutableRoaringBitmap nulls = unionOfNulls(bitmaps);
+ if (nulls != null) {
+ // A document UNKNOWN to either side is not true on that side, so it
leaves the intersection
+ cardinality -= andCardinalityWithin(nulls, left, _inverted, right,
bitmaps._inverted);
+ }
+ return cardinality;
+ }
+
+ /// Returns the size of the intersection of the two unions, each
complemented when inverted, restricted to
+ /// `within`. Only bitmaps no larger than `within` are materialized.
+ private static int andCardinalityWithin(ImmutableRoaringBitmap within,
ImmutableRoaringBitmap left,
+ boolean leftInverted, ImmutableRoaringBitmap right, boolean
rightInverted) {
+ if (!leftInverted) {
+ MutableRoaringBitmap leftWithin = ImmutableRoaringBitmap.and(left,
within);
+ return rightInverted
+ ? ImmutableRoaringBitmap.andNotCardinality(leftWithin, right)
+ : ImmutableRoaringBitmap.andCardinality(leftWithin, right);
+ }
+ if (!rightInverted) {
+ return
ImmutableRoaringBitmap.andNotCardinality(ImmutableRoaringBitmap.and(right,
within), left);
+ }
+ // Both complemented: what is left of `within` once the documents of
either union are removed
+ return within.getCardinality() -
ImmutableRoaringBitmap.orCardinality(ImmutableRoaringBitmap.and(left, within),
+ ImmutableRoaringBitmap.and(right, within));
+ }
+
+ /// Returns the documents UNKNOWN to either collection, or `null` when there
is none.
+ @Nullable
+ private ImmutableRoaringBitmap unionOfNulls(BitmapCollection bitmaps) {
+ if (_nullBitmap == null) {
+ return bitmaps._nullBitmap;
+ }
+ if (bitmaps._nullBitmap == null) {
+ return _nullBitmap;
+ }
+ return ImmutableRoaringBitmap.or(_nullBitmap, bitmaps._nullBitmap);
}
/// Computes the size of the union of the bitmaps efficiently regardless of
negation, without
/// needing to invert inputs or materialize an intermediate bitmap. If
either this collection
- /// or the other collection has more than one bitmap, the union will be
materialized.
+ /// or the other collection has more than one bitmap, the union will be
materialized. When either collection has a
+ /// null bitmap, the size follows from the two cardinalities and the
intersection, so nothing larger than the null
+ /// bitmaps is materialized.
///
/// @param bitmaps to intersect with
/// @return the size of the union of the bitmaps in this collection and in
the other collection
public int orCardinality(BitmapCollection bitmaps) {
ImmutableRoaringBitmap left = reduceInternal();
ImmutableRoaringBitmap right = bitmaps.reduceInternal();
+ if (_nullBitmap != null || bitmaps._nullBitmap != null) {
+ return getCardinality(left) + bitmaps.getCardinality(right) -
andCardinality(left, right, bitmaps);
+ }
if (!_inverted) {
if (!bitmaps._inverted) {
return ImmutableRoaringBitmap.orCardinality(left, right);
@@ -94,17 +186,22 @@ public class BitmapCollection {
return BufferFastAggregation.or(_bitmaps);
}
- /// Reduces the bitmaps to a single bitmap. In common cases, when the
collection
- /// is not inverted and only has one bitmap, this operation is cheap.
However,
+ /// Reduces the bitmaps to a single bitmap of the true documents. In common
cases, when the collection
+ /// is not inverted, only has one bitmap and no null bitmap, this operation
is cheap. However,
/// this may be a costly operation: a new bitmap may be allocated, one or
many
- /// bitmaps may need to be inverted. Prefer {@see andCardinality} or {@see
orCardinality}
+ /// bitmaps may need to be inverted, and the null bitmap subtracted. Prefer
[#andCardinality] or [#orCardinality]
/// when appropriate.
/// @return a bitmap
public ImmutableRoaringBitmap reduce() {
- if (!_inverted) {
- return reduceInternal();
+ if (_nullBitmap == null) {
+ return _inverted ? invertedOr() : reduceInternal();
+ }
+ if (_inverted) {
+ MutableRoaringBitmap complement = invertedOr();
+ complement.andNot(_nullBitmap);
+ return complement;
}
- return invertedOr();
+ return ImmutableRoaringBitmap.andNot(reduceInternal(), _nullBitmap);
}
private MutableRoaringBitmap invertedOr() {
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/ExpressionFilterOperator.java
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/ExpressionFilterOperator.java
index cf68c484a49..91715f99080 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/ExpressionFilterOperator.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/ExpressionFilterOperator.java
@@ -32,6 +32,7 @@ import org.apache.pinot.core.common.Operator;
import org.apache.pinot.core.operator.ColumnContext;
import org.apache.pinot.core.operator.ExplainAttributeBuilder;
import
org.apache.pinot.core.operator.dociditerators.ExpressionScanDocIdIterator;
+import org.apache.pinot.core.operator.docidsets.EmptyDocIdSet;
import org.apache.pinot.core.operator.docidsets.ExpressionDocIdSet;
import org.apache.pinot.core.operator.docidsets.NotDocIdSet;
import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
@@ -81,17 +82,33 @@ public class ExpressionFilterOperator extends
BaseFilterOperator {
@Override
protected BlockDocIdSet getTrues() {
if (_predicateType == Predicate.Type.IS_NULL) {
- return getNulls();
+ return getExpressionNulls();
} else if (_predicateType == Predicate.Type.IS_NOT_NULL) {
- return new NotDocIdSet(getNulls(), _numDocs);
+ return new NotDocIdSet(getExpressionNulls(), _numDocs);
} else {
return new ExpressionDocIdSet(_transformFunction, _predicateEvaluator,
_dataSourceMap, _numDocs,
ExpressionScanDocIdIterator.PredicateEvaluationResult.TRUE,
_queryContext);
}
}
+ /// `IS NULL` and `IS NOT NULL` are two-valued: a null expression makes them
true or false, never UNKNOWN. Every other
+ /// predicate is UNKNOWN where the expression is null.
@Override
protected BlockDocIdSet getNulls() {
+ return isNullCheck() ? EmptyDocIdSet.getInstance() : getExpressionNulls();
+ }
+
+ @Override
+ public boolean mayHaveNulls() {
+ return _nullHandlingEnabled && !isNullCheck();
+ }
+
+ private boolean isNullCheck() {
+ return _predicateType == Predicate.Type.IS_NULL || _predicateType ==
Predicate.Type.IS_NOT_NULL;
+ }
+
+ /// Returns the documents the expression evaluates to null for.
+ private BlockDocIdSet getExpressionNulls() {
return new ExpressionDocIdSet(_transformFunction, null, _dataSourceMap,
_numDocs,
ExpressionScanDocIdIterator.PredicateEvaluationResult.NULL,
_queryContext);
}
@@ -99,9 +116,9 @@ public class ExpressionFilterOperator extends
BaseFilterOperator {
@Override
protected BlockDocIdSet getFalses() {
if (_predicateType == Predicate.Type.IS_NULL) {
- return new NotDocIdSet(getNulls(), _numDocs);
+ return new NotDocIdSet(getExpressionNulls(), _numDocs);
} else if (_predicateType == Predicate.Type.IS_NOT_NULL) {
- return getNulls();
+ return getExpressionNulls();
} else {
return new ExpressionDocIdSet(_transformFunction, _predicateEvaluator,
_dataSourceMap, _numDocs,
ExpressionScanDocIdIterator.PredicateEvaluationResult.FALSE,
_queryContext);
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/FilterOperatorUtils.java
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/FilterOperatorUtils.java
index bab63d0d0db..29b98784aef 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/FilterOperatorUtils.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/FilterOperatorUtils.java
@@ -22,6 +22,7 @@ import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.OptionalInt;
+import javax.annotation.Nullable;
import org.apache.pinot.common.request.context.predicate.Predicate;
import
org.apache.pinot.core.operator.filter.predicate.BaseDictIdBasedRegexpLikePredicateEvaluator;
import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
@@ -30,6 +31,7 @@ import org.apache.pinot.segment.spi.datasource.DataSource;
import org.apache.pinot.segment.spi.index.reader.NullValueVectorReader;
import org.apache.pinot.spi.config.table.FieldConfig;
import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
public class FilterOperatorUtils {
@@ -61,21 +63,46 @@ public class FilterOperatorUtils {
BaseFilterOperator getNotFilterOperator(QueryContext queryContext,
BaseFilterOperator filterOperator, int numDocs);
}
+ /// Returns the null rows of the column in this segment, or `null` when
there is none.
+ ///
+ /// A column reports nulls through its null value vector, which is absent
when the segment has none for the column
+ /// and can also be present but empty. Under null handling these are the
rows a predicate on the column is UNKNOWN
+ /// over, and the reason a verdict of always true or always false over the
column's values does not cover every row.
+ /// A consuming segment hands out a copy of its vector on each read, so
callers read it once and keep the result.
+ @Nullable
+ public static ImmutableRoaringBitmap getNullBitmap(DataSource dataSource) {
+ NullValueVectorReader nullValueVector = dataSource.getNullValueVector();
+ if (nullValueVector != null) {
+ ImmutableRoaringBitmap nullBitmap = nullValueVector.getNullBitmap();
+ if (!nullBitmap.isEmpty()) {
+ return nullBitmap;
+ }
+ }
+ return null;
+ }
+
+ /// Returns whether the column holds any null value in this segment, see
[#getNullBitmap].
+ public static boolean hasNulls(DataSource dataSource) {
+ return getNullBitmap(dataSource) != null;
+ }
+
public static class DefaultImplementation implements Implementation {
@Override
public BaseFilterOperator getLeafFilterOperator(QueryContext queryContext,
PredicateEvaluator predicateEvaluator,
DataSource dataSource, int numDocs) {
+ // The evaluator's verdicts are over the column's real values. With null
handling enabled a null row is UNKNOWN
+ // under either verdict, so it is selected by neither the predicate nor
its negation: the leaf has to carry the
+ // null rows for the negation to leave them out, instead of collapsing
to a constant that knows nothing of them.
if (predicateEvaluator.isAlwaysFalse()) {
+ ImmutableRoaringBitmap nullBitmap =
queryContext.isNullHandlingEnabled() ? getNullBitmap(dataSource) : null;
+ if (nullBitmap != null) {
+ return new BitmapBasedFilterOperator(new MutableRoaringBitmap(),
false, numDocs, nullBitmap);
+ }
return EmptyFilterOperator.getInstance();
} else if (predicateEvaluator.isAlwaysTrue()) {
- if (queryContext.isNullHandlingEnabled()) {
- NullValueVectorReader nullValueVectorReader =
dataSource.getNullValueVector();
- if (nullValueVectorReader != null) {
- ImmutableRoaringBitmap nullBitmap =
nullValueVectorReader.getNullBitmap();
- if (nullBitmap != null && !nullBitmap.isEmpty()) {
- return new BitmapBasedFilterOperator(nullBitmap, true, numDocs);
- }
- }
+ ImmutableRoaringBitmap nullBitmap =
queryContext.isNullHandlingEnabled() ? getNullBitmap(dataSource) : null;
+ if (nullBitmap != null) {
+ return new BitmapBasedFilterOperator(nullBitmap, true, numDocs,
nullBitmap);
}
return new MatchAllFilterOperator(numDocs);
}
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/InvertedIndexFilterOperator.java
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/InvertedIndexFilterOperator.java
index 07a41028b08..af9d817b447 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/InvertedIndexFilterOperator.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/InvertedIndexFilterOperator.java
@@ -103,15 +103,31 @@ public class InvertedIndexFilterOperator extends
BaseColumnFilterOperator {
@Override
public int getNumMatchingDocs() {
+ ImmutableRoaringBitmap nullBitmap = getNullBitmap();
+ if (nullBitmap != null && !_isSingleValue) {
+ // Per-dictId bitmaps overlap on a multi-value column, so the null rows
among the matches can only be counted on
+ // the materialized union
+ return getBitmaps().getCardinality();
+ }
int[] dictIds = _exclusive ? _predicateEvaluator.getNonMatchingDictIds() :
_predicateEvaluator.getMatchingDictIds();
int count;
+ // Null rows among the matches are UNKNOWN rather than true
+ int numNulls = 0;
if (_isSingleValue) {
// On a single-value column, per-dictId bitmaps partition the docId
space (each docId has exactly one
// dictId), so the union cardinality equals the sum of per-bitmap
cardinalities. No scratch bitmap is
// allocated and no OR pass is performed.
count = 0;
- for (int dictId : dictIds) {
- count += _invertedIndexReader.getDocIds(dictId).getCardinality();
+ if (nullBitmap == null) {
+ for (int dictId : dictIds) {
+ count += _invertedIndexReader.getDocIds(dictId).getCardinality();
+ }
+ } else {
+ for (int dictId : dictIds) {
+ ImmutableRoaringBitmap docIds =
_invertedIndexReader.getDocIds(dictId);
+ count += docIds.getCardinality();
+ numNulls += ImmutableRoaringBitmap.andCardinality(docIds,
nullBitmap);
+ }
}
} else {
// TODO: For MV column, per-dictId bitmaps may overlap, so we must
materialize the union to count.
@@ -137,7 +153,7 @@ public class InvertedIndexFilterOperator extends
BaseColumnFilterOperator {
break;
}
}
- return _exclusive ? _numDocs - count : count;
+ return toNumTrueDocs(count, numNulls, _exclusive);
}
@Override
@@ -152,7 +168,7 @@ public class InvertedIndexFilterOperator extends
BaseColumnFilterOperator {
for (int i = 0; i < dictIds.length; i++) {
bitmaps[i] = _invertedIndexReader.getDocIds(dictIds[i]);
}
- return new BitmapCollection(_numDocs, _exclusive, bitmaps);
+ return new BitmapCollection(_numDocs, _exclusive,
bitmaps).excludingNulls(getNullBitmap());
}
@Override
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/MapFilterOperator.java
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/MapFilterOperator.java
index 9c62e3d2466..eb2d4f8152e 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/MapFilterOperator.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/MapFilterOperator.java
@@ -278,6 +278,11 @@ public class MapFilterOperator extends BaseFilterOperator {
return _delegate.getFalses();
}
+ @Override
+ protected BlockDocIdSet getNotFalses() {
+ return _delegate.getNotFalses();
+ }
+
@Override
public boolean canOptimizeCount() {
return _delegate.canOptimizeCount();
@@ -298,6 +303,11 @@ public class MapFilterOperator extends BaseFilterOperator {
return _delegate.getBitmaps();
}
+ @Override
+ public boolean mayHaveNulls() {
+ return _delegate.mayHaveNulls();
+ }
+
@Override
public List<Operator> getChildOperators() {
return List.of();
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/NotFilterOperator.java
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/NotFilterOperator.java
index b0b1cbc2905..56037a91e5a 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/NotFilterOperator.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/NotFilterOperator.java
@@ -23,7 +23,9 @@ import java.util.List;
import javax.annotation.Nullable;
import org.apache.pinot.core.common.BlockDocIdSet;
import org.apache.pinot.core.common.Operator;
+import org.apache.pinot.core.operator.docidsets.EmptyDocIdSet;
import org.apache.pinot.core.operator.docidsets.MatchAllDocIdSet;
+import org.apache.pinot.core.operator.docidsets.NotDocIdSet;
public class NotFilterOperator extends BaseFilterOperator {
@@ -61,13 +63,37 @@ public class NotFilterOperator extends BaseFilterOperator {
return _filterOperator.getTrues();
}
+ /// NOT of UNKNOWN is UNKNOWN: a negation is UNKNOWN exactly where its child
is.
+ @Override
+ protected BlockDocIdSet getNulls() {
+ return _filterOperator.getNulls();
+ }
+
+ /// A negation is not false where its child is not true.
+ @Override
+ protected BlockDocIdSet getNotFalses() {
+ BlockDocIdSet childTrues = _filterOperator.getTrues();
+ if (childTrues instanceof MatchAllDocIdSet) {
+ return EmptyDocIdSet.getInstance();
+ }
+ if (childTrues instanceof EmptyDocIdSet) {
+ return new MatchAllDocIdSet(_numDocs);
+ }
+ return new NotDocIdSet(childTrues, _numDocs);
+ }
+
+ /// The complement of the child's count is its false documents only when
none is UNKNOWN. Otherwise the count comes
+ /// from the child's bitmaps, which know the UNKNOWN documents and keep them
out of the inversion.
@Override
public boolean canOptimizeCount() {
- return _filterOperator.canOptimizeCount();
+ return _filterOperator.mayHaveNulls() ?
_filterOperator.canProduceBitmaps() : _filterOperator.canOptimizeCount();
}
@Override
public int getNumMatchingDocs() {
+ if (_filterOperator.mayHaveNulls()) {
+ return getBitmaps().getCardinality();
+ }
return _numDocs - _filterOperator.getNumMatchingDocs();
}
@@ -81,6 +107,11 @@ public class NotFilterOperator extends BaseFilterOperator {
return _filterOperator.getBitmaps().invert();
}
+ @Override
+ public boolean mayHaveNulls() {
+ return _filterOperator.mayHaveNulls();
+ }
+
public BaseFilterOperator getChildFilterOperator() {
return _filterOperator;
}
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/OrFilterOperator.java
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/OrFilterOperator.java
index e2c92bfd0c0..ed1d0ac75e1 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/OrFilterOperator.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/OrFilterOperator.java
@@ -19,7 +19,6 @@
package org.apache.pinot.core.operator.filter;
import java.util.ArrayList;
-import java.util.Arrays;
import java.util.List;
import java.util.Map;
import javax.annotation.Nullable;
@@ -27,12 +26,12 @@ import org.apache.pinot.core.common.BlockDocIdSet;
import org.apache.pinot.core.common.Operator;
import org.apache.pinot.core.operator.docidsets.EmptyDocIdSet;
import org.apache.pinot.core.operator.docidsets.MatchAllDocIdSet;
-import org.apache.pinot.core.operator.docidsets.NotDocIdSet;
import org.apache.pinot.core.operator.docidsets.OrDocIdSet;
import org.apache.pinot.core.operator.docidsets.ShortCircuitingDocIdSet;
import org.apache.pinot.spi.trace.Tracing;
import org.roaringbitmap.buffer.BufferFastAggregation;
import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
public class OrFilterOperator extends BaseFilterOperator {
@@ -71,33 +70,29 @@ public class OrFilterOperator extends BaseFilterOperator {
return new OrDocIdSet(blockDocIdSets, _numDocs);
}
+ /// A disjunction is not false where some child is not false: the union of
the children's not-false documents.
@Override
- protected BlockDocIdSet getFalses() {
- List<BlockDocIdSet> blockDocIdSets = new
ArrayList<>(_filterOperators.size());
+ protected BlockDocIdSet getNotFalses() {
+ List<BlockDocIdSet> notFalses = new ArrayList<>(_filterOperators.size());
for (BaseFilterOperator filterOperator : _filterOperators) {
- BlockDocIdSet trues = filterOperator.getTrues();
- if (trues instanceof MatchAllDocIdSet) {
- return EmptyDocIdSet.getInstance();
+ BlockDocIdSet childNotFalses = filterOperator.getNotFalses();
+ if (childNotFalses instanceof MatchAllDocIdSet) {
+ return new MatchAllDocIdSet(_numDocs);
}
- if (trues instanceof EmptyDocIdSet) {
+ if (childNotFalses instanceof EmptyDocIdSet) {
continue;
}
- if (_nullHandlingEnabled) {
- BlockDocIdSet nulls = filterOperator.getNulls();
- if (!(nulls instanceof EmptyDocIdSet)) {
- blockDocIdSets.add(new OrDocIdSet(Arrays.asList(trues, nulls),
_numDocs));
- continue;
- }
- }
- blockDocIdSets.add(trues);
- }
- if (blockDocIdSets.isEmpty()) {
- return new MatchAllDocIdSet(_numDocs);
+ notFalses.add(childNotFalses);
}
- if (blockDocIdSets.size() == 1) {
- return new NotDocIdSet(blockDocIdSets.get(0), _numDocs);
+ if (notFalses.isEmpty()) {
+ return EmptyDocIdSet.getInstance();
}
- return new NotDocIdSet(new OrDocIdSet(blockDocIdSets, _numDocs), _numDocs);
+ return notFalses.size() == 1 ? notFalses.get(0) : new
OrDocIdSet(notFalses, _numDocs);
+ }
+
+ @Override
+ protected BlockDocIdSet getNulls() {
+ return mayHaveNulls() ? deriveNulls(_queryOptions) :
EmptyDocIdSet.getInstance();
}
@Override
@@ -137,12 +132,42 @@ public class OrFilterOperator extends BaseFilterOperator {
return true;
}
+ /// The true documents are those true for some child. When a child has
UNKNOWN documents, so may the result: a
+ /// document is UNKNOWN when no child is true for it and some child is
UNKNOWN, which is the union of the children's
+ /// UNKNOWN documents minus the union of their true ones.
@Override
public BitmapCollection getBitmaps() {
- ImmutableRoaringBitmap[] bitmaps = new
ImmutableRoaringBitmap[_filterOperators.size()];
- for (int i = 0; i < _filterOperators.size(); i++) {
- bitmaps[i] = _filterOperators.get(i).getBitmaps().reduce();
+ int numChildren = _filterOperators.size();
+ ImmutableRoaringBitmap[] trues = new ImmutableRoaringBitmap[numChildren];
+ MutableRoaringBitmap nulls = null;
+ for (int i = 0; i < numChildren; i++) {
+ BitmapCollection childBitmaps = _filterOperators.get(i).getBitmaps();
+ trues[i] = childBitmaps.reduce();
+ ImmutableRoaringBitmap childNulls = childBitmaps.getNullBitmap();
+ if (childNulls != null) {
+ if (nulls == null) {
+ nulls = new MutableRoaringBitmap();
+ }
+ nulls.or(childNulls);
+ }
+ }
+ MutableRoaringBitmap orTrues = BufferFastAggregation.or(trues);
+ if (nulls == null) {
+ return new BitmapCollection(_numDocs, false, orTrues);
+ }
+ nulls.andNot(orTrues);
+ return new BitmapCollection(_numDocs, false,
orTrues).excludingNulls(nulls);
+ }
+
+ @Override
+ public boolean mayHaveNulls() {
+ if (_nullHandlingEnabled) {
+ for (BaseFilterOperator filterOperator : _filterOperators) {
+ if (filterOperator.mayHaveNulls()) {
+ return true;
+ }
+ }
}
- return new BitmapCollection(_numDocs, false,
BufferFastAggregation.or(bitmaps));
+ return false;
}
}
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/RangeIndexBasedFilterOperator.java
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/RangeIndexBasedFilterOperator.java
index 34471ccf9e6..4dda6267e9b 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/RangeIndexBasedFilterOperator.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/RangeIndexBasedFilterOperator.java
@@ -182,8 +182,41 @@ public class RangeIndexBasedFilterOperator extends
BaseColumnFilterOperator {
return _rangeIndexReader.isExact();
}
+ /// The index counts the documents whose stored value satisfies the
predicate. A null row stores the column's default
+ /// null value, so the null rows are either all among those documents or all
outside them, depending on whether that
+ /// value satisfies the predicate: the index's count is kept, and the null
rows are subtracted when it does.
@Override
public int getNumMatchingDocs() {
+ int numMatchingDocs = getNumMatchingDocsFromIndex();
+ ImmutableRoaringBitmap nullBitmap = getNullBitmap();
+ if (nullBitmap != null && matchesDefaultNullValue()) {
+ numMatchingDocs -= nullBitmap.getCardinality();
+ }
+ return numMatchingDocs;
+ }
+
+ /// Returns whether the predicate holds for the column's default null value,
the value a null row is stored under.
+ private boolean matchesDefaultNullValue() {
+ Object defaultNullValue =
_dataSource.getDataSourceMetadata().getFieldSpec().getDefaultNullValue();
+ if (_predicateEvaluator.isDictionaryBased()) {
+ int dictId =
_dataSource.getDictionary().indexOf(FieldSpec.getStringValue(defaultNullValue));
+ return dictId >= 0 && _predicateEvaluator.applySV(dictId);
+ }
+ switch (_parameterType) {
+ case INT:
+ return _predicateEvaluator.applySV(((Number)
defaultNullValue).intValue());
+ case LONG:
+ return _predicateEvaluator.applySV(((Number)
defaultNullValue).longValue());
+ case FLOAT:
+ return _predicateEvaluator.applySV(((Number)
defaultNullValue).floatValue());
+ case DOUBLE:
+ return _predicateEvaluator.applySV(((Number)
defaultNullValue).doubleValue());
+ default:
+ throw unsupportedDataType(_parameterType);
+ }
+ }
+
+ private int getNumMatchingDocsFromIndex() {
switch (_parameterType) {
case INT:
if (_predicateEvaluator instanceof IntValue) {
@@ -225,7 +258,7 @@ public class RangeIndexBasedFilterOperator extends
BaseColumnFilterOperator {
@Override
public BitmapCollection getBitmaps() {
- return new BitmapCollection(_numDocs, false, getMatchingDocIds());
+ return new BitmapCollection(_numDocs, false,
getMatchingDocIds()).excludingNulls(getNullBitmap());
}
@Override
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/SortedIndexBasedFilterOperator.java
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/SortedIndexBasedFilterOperator.java
index 8991034ad2a..8ecaa207647 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/SortedIndexBasedFilterOperator.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/SortedIndexBasedFilterOperator.java
@@ -22,6 +22,7 @@ import com.google.common.base.CaseFormat;
import com.google.common.base.Preconditions;
import java.util.ArrayList;
import java.util.List;
+import javax.annotation.Nullable;
import org.apache.pinot.core.common.BlockDocIdSet;
import org.apache.pinot.core.common.Operator;
import org.apache.pinot.core.operator.ExplainAttributeBuilder;
@@ -32,6 +33,7 @@ import
org.apache.pinot.core.query.request.context.QueryContext;
import org.apache.pinot.segment.spi.datasource.DataSource;
import org.apache.pinot.segment.spi.index.reader.SortedIndexReader;
import org.apache.pinot.spi.utils.Pairs.IntPair;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
import org.roaringbitmap.buffer.MutableRoaringBitmap;
@@ -137,7 +139,11 @@ public class SortedIndexBasedFilterOperator extends
BaseColumnFilterOperator {
@Override
public int getNumMatchingDocs() {
+ ImmutableRoaringBitmap nullBitmap = getNullBitmap();
int count = 0;
+ // Null rows within the counted ranges are UNKNOWN rather than true; they
are counted per range so that no bitmap
+ // has to be materialized
+ int numNulls = 0;
boolean exclusive = _predicateEvaluator.isExclusive();
if (_predicateEvaluator instanceof
SortedDictionaryBasedRangePredicateEvaluator) {
// For RANGE predicate, use start/end document id to construct a new
document id range
@@ -147,6 +153,7 @@ public class SortedIndexBasedFilterOperator extends
BaseColumnFilterOperator {
// NOTE: End dictionary id is exclusive in
OfflineDictionaryBasedRangePredicateEvaluator.
int endDocId =
_sortedIndexReader.getDocIds(rangePredicateEvaluator.getEndDictId() -
1).getRight();
count = endDocId - startDocId + 1;
+ numNulls = countNulls(nullBitmap, startDocId, endDocId);
} else {
int[] dictIds =
exclusive ? _predicateEvaluator.getNonMatchingDictIds() :
_predicateEvaluator.getMatchingDictIds();
@@ -156,6 +163,7 @@ public class SortedIndexBasedFilterOperator extends
BaseColumnFilterOperator {
if (numDictIds == 1) {
IntPair docIdRange = _sortedIndexReader.getDocIds(dictIds[0]);
count = docIdRange.getRight() - docIdRange.getLeft() + 1;
+ numNulls = countNulls(nullBitmap, docIdRange.getLeft(),
docIdRange.getRight());
} else {
IntPair lastDocIdRange = _sortedIndexReader.getDocIds(dictIds[0]);
for (int i = 1; i < numDictIds; i++) {
@@ -164,13 +172,20 @@ public class SortedIndexBasedFilterOperator extends
BaseColumnFilterOperator {
lastDocIdRange.setRight(docIdRange.getRight());
} else {
count += lastDocIdRange.getRight() - lastDocIdRange.getLeft() + 1;
+ numNulls += countNulls(nullBitmap, lastDocIdRange.getLeft(),
lastDocIdRange.getRight());
lastDocIdRange = docIdRange;
}
}
count += lastDocIdRange.getRight() - lastDocIdRange.getLeft() + 1;
+ numNulls += countNulls(nullBitmap, lastDocIdRange.getLeft(),
lastDocIdRange.getRight());
}
}
- return exclusive ? _numDocs - count : count;
+ return toNumTrueDocs(count, numNulls, exclusive);
+ }
+
+ /// Returns how many null rows fall in the inclusive document id range, or 0
without a null bitmap.
+ private static int countNulls(@Nullable ImmutableRoaringBitmap nullBitmap,
int startDocId, int endDocId) {
+ return nullBitmap != null ? (int) nullBitmap.rangeCardinality(startDocId,
endDocId + 1L) : 0;
}
@Override
@@ -213,7 +228,7 @@ public class SortedIndexBasedFilterOperator extends
BaseColumnFilterOperator {
bitmap.add(lastDocIdRange.getLeft(), lastDocIdRange.getRight() + 1L);
}
}
- return new BitmapCollection(_numDocs, exclusive, bitmap);
+ return new BitmapCollection(_numDocs, exclusive,
bitmap).excludingNulls(getNullBitmap());
}
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/startree/StarTreeUtils.java
b/pinot-core/src/main/java/org/apache/pinot/core/startree/StarTreeUtils.java
index e9352c5799f..25954a97fbb 100644
--- a/pinot-core/src/main/java/org/apache/pinot/core/startree/StarTreeUtils.java
+++ b/pinot-core/src/main/java/org/apache/pinot/core/startree/StarTreeUtils.java
@@ -34,6 +34,7 @@ import
org.apache.pinot.common.request.context.ExpressionContext;
import org.apache.pinot.common.request.context.FilterContext;
import org.apache.pinot.common.request.context.predicate.Predicate;
import org.apache.pinot.core.operator.BaseProjectOperator;
+import org.apache.pinot.core.operator.filter.FilterOperatorUtils;
import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
import
org.apache.pinot.core.operator.filter.predicate.PredicateEvaluatorProvider;
import org.apache.pinot.core.query.aggregation.function.AggregationFunction;
@@ -88,9 +89,14 @@ public class StarTreeUtils {
/// the list are implicitly ANDed together. Any OR and NOT predicates are
nested within a CompositePredicate.
///
/// A map from predicates to their evaluators is passed in to accelerate the
computation.
+ ///
+ /// A predicate that is always true over a column's values is left out of
the map, unless null handling is enabled
+ /// and the column holds nulls: a null row is UNKNOWN rather than true, so
the predicate is kept, and the column stays
+ /// visible to the null checks that decide whether a star-tree can serve the
query.
@Nullable
public static Map<String, List<CompositePredicateEvaluator>>
extractPredicateEvaluatorsMap(IndexSegment indexSegment,
- @Nullable FilterContext filter, List<Pair<Predicate,
PredicateEvaluator>> predicateEvaluatorMapping) {
+ @Nullable FilterContext filter, List<Pair<Predicate,
PredicateEvaluator>> predicateEvaluatorMapping,
+ boolean nullHandlingEnabled) {
if (filter == null) {
return Map.of();
}
@@ -106,7 +112,7 @@ public class StarTreeUtils {
break;
case OR:
Pair<String, CompositePredicateEvaluator> pair =
- isOrClauseValidForStarTree(indexSegment, filterNode,
predicateEvaluatorMapping);
+ isOrClauseValidForStarTree(indexSegment, filterNode,
predicateEvaluatorMapping, nullHandlingEnabled);
if (pair == null) {
return null;
}
@@ -133,7 +139,8 @@ public class StarTreeUtils {
return null;
}
// Skip adding always true predicate
- if ((predicateEvaluator.isAlwaysTrue() && !negated) ||
(predicateEvaluator.isAlwaysFalse() && negated)) {
+ if (isAlwaysTrue(predicateEvaluator, negated, indexSegment,
predicate.getLhs().getIdentifier(),
+ nullHandlingEnabled)) {
break;
}
predicateEvaluatorsMap.computeIfAbsent(predicate.getLhs().getIdentifier(), k ->
new ArrayList<>())
@@ -157,7 +164,8 @@ public class StarTreeUtils {
if (predicateEvaluator == null ||
predicateEvaluator.isAlwaysFalse()) {
return null;
}
- if (!predicateEvaluator.isAlwaysTrue()) {
+ if (!isAlwaysTrue(predicateEvaluator, false, indexSegment,
predicate.getLhs().getIdentifier(),
+ nullHandlingEnabled)) {
predicateEvaluatorsMap.computeIfAbsent(predicate.getLhs().getIdentifier(), k ->
new ArrayList<>())
.add(new
CompositePredicateEvaluator(List.of(ObjectBooleanPair.of(predicateEvaluator,
false))));
}
@@ -215,7 +223,8 @@ public class StarTreeUtils {
/// clause cannot be solved with star-tree; a pair of nulls if the
OR clause always evaluates to true.
@Nullable
private static Pair<String, CompositePredicateEvaluator>
isOrClauseValidForStarTree(IndexSegment indexSegment,
- FilterContext filter, List<Pair<Predicate, PredicateEvaluator>>
predicateEvaluatorMapping) {
+ FilterContext filter, List<Pair<Predicate, PredicateEvaluator>>
predicateEvaluatorMapping,
+ boolean nullHandlingEnabled) {
assert filter.getType() == FilterContext.Type.OR;
List<ObjectBooleanPair<Predicate>> predicates = new ArrayList<>();
@@ -234,7 +243,8 @@ public class StarTreeUtils {
}
boolean negated = predicate.rightBoolean();
// Use a pair of null values to represent always true
- if ((predicateEvaluator.isAlwaysTrue() && !negated) ||
(predicateEvaluator.isAlwaysFalse() && negated)) {
+ if (isAlwaysTrue(predicateEvaluator, negated, indexSegment,
predicate.left().getLhs().getIdentifier(),
+ nullHandlingEnabled)) {
return Pair.of(null, null);
}
// Skip the always false predicate
@@ -302,6 +312,18 @@ public class StarTreeUtils {
return true;
}
+ /// Returns whether the predicate is always true for the query, so that the
star-tree filter can drop it.
+ ///
+ /// The evaluator's verdict is over the column's real values. With null
handling enabled a null row is UNKNOWN rather
+ /// than true, so the predicate is only always true when the column holds no
null. Kept in the map otherwise, the
+ /// column reaches the null checks that decide whether a star-tree can serve
the query.
+ private static boolean isAlwaysTrue(PredicateEvaluator predicateEvaluator,
boolean negated, IndexSegment indexSegment,
+ String column, boolean nullHandlingEnabled) {
+ boolean alwaysTrueOverValues = negated ?
predicateEvaluator.isAlwaysFalse() : predicateEvaluator.isAlwaysTrue();
+ return alwaysTrueOverValues
+ && !(nullHandlingEnabled &&
FilterOperatorUtils.hasNulls(indexSegment.getDataSource(column)));
+ }
+
/// Returns the predicate evaluator for the given predicate, or `null` if
the predicate cannot be solved with
/// star-tree.
@Nullable
@@ -373,7 +395,7 @@ public class StarTreeUtils {
}
Map<String, List<CompositePredicateEvaluator>> predicateEvaluatorsMap =
- extractPredicateEvaluatorsMap(indexSegment, filter,
predicateEvaluators);
+ extractPredicateEvaluatorsMap(indexSegment, filter,
predicateEvaluators, queryContext.isNullHandlingEnabled());
if (predicateEvaluatorsMap == null) {
return null;
}
@@ -394,9 +416,7 @@ public class StarTreeUtils {
if (!inputExpressions.isEmpty()) {
if (inputExpressions.get(0).getType() ==
ExpressionContext.Type.IDENTIFIER) {
DataSource dataSource =
indexSegment.getDataSource(inputExpressions.get(0).getIdentifier());
- if (dataSource.getNullValueVector() != null &&
!dataSource.getNullValueVector()
- .getNullBitmap()
- .isEmpty()) {
+ if (FilterOperatorUtils.hasNulls(dataSource)) {
return null;
}
}
@@ -411,7 +431,7 @@ public class StarTreeUtils {
LOGGER.debug("Cannot use star-tree index because aggregation column:
'{}' does not exist", column);
return null;
}
- if (dataSource.getNullValueVector() != null &&
!dataSource.getNullValueVector().getNullBitmap().isEmpty()) {
+ if (FilterOperatorUtils.hasNulls(dataSource)) {
LOGGER.debug("Cannot use star-tree index because aggregation column:
'{}' has null values", column);
return null;
}
@@ -423,7 +443,7 @@ public class StarTreeUtils {
LOGGER.debug("Cannot use star-tree index because filter column: '{}'
does not exist", column);
return null;
}
- if (dataSource.getNullValueVector() != null &&
!dataSource.getNullValueVector().getNullBitmap().isEmpty()) {
+ if (FilterOperatorUtils.hasNulls(dataSource)) {
LOGGER.debug("Cannot use star-tree index because filter column: '{}'
has null values", column);
return null;
}
@@ -441,7 +461,7 @@ public class StarTreeUtils {
LOGGER.debug("Cannot use star-tree index because group-by column:
'{}' does not exist", column);
return null;
}
- if (dataSource.getNullValueVector() != null &&
!dataSource.getNullValueVector().getNullBitmap().isEmpty()) {
+ if (FilterOperatorUtils.hasNulls(dataSource)) {
LOGGER.debug("Cannot use star-tree index because group-by column:
'{}' has null values", column);
return null;
}
diff --git
a/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/AndFilterOperatorTest.java
b/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/AndFilterOperatorTest.java
index a939447a41f..5a975d64664 100644
---
a/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/AndFilterOperatorTest.java
+++
b/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/AndFilterOperatorTest.java
@@ -29,6 +29,7 @@ import org.testng.annotations.Test;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
+import static org.testng.Assert.assertNull;
import static org.testng.Assert.assertTrue;
@@ -325,6 +326,116 @@ public class AndFilterOperatorTest {
assertEquals(andOperator.getBitmaps().reduce().toArray(), new int[]{3, 6});
}
+ @Test
+ public void testGetBitmapsWithNullChild() {
+ int numDocs = 10;
+ // The second child is UNKNOWN on {4, 5, 6}. The AND is UNKNOWN only where
no child is false: on 4, where the other
+ // children are true, while 5 and 6 are false through the first child
+ AndFilterOperator andOperator = new
AndFilterOperator(List.of(bitmapOp(numDocs, false, 2, 3, 4, 7),
+ new BitmapBasedFilterOperator(MutableRoaringBitmap.bitmapOf(0, 1, 2,
3), false, numDocs,
+ MutableRoaringBitmap.bitmapOf(4, 5, 6)), bitmapOp(numDocs, false,
2, 4, 8)), null, numDocs, true);
+
+ assertTrue(andOperator.canProduceBitmaps());
+ assertTrue(andOperator.mayHaveNulls());
+ BitmapCollection bitmaps = andOperator.getBitmaps();
+ assertEquals(bitmaps.reduce().toArray(), new int[]{2});
+ assertEquals(bitmaps.getNullBitmap().toArray(), new int[]{4});
+ assertEquals(andOperator.getNumMatchingDocs(), 1);
+
+ NotFilterOperator notOperator = new NotFilterOperator(andOperator,
numDocs, true);
+ assertTrue(notOperator.canOptimizeCount());
+ assertEquals(notOperator.getNumMatchingDocs(), 8);
+ assertEquals(notOperator.getBitmaps().reduce().toArray(), new int[]{0, 1,
3, 5, 6, 7, 8, 9});
+ assertEquals(TestUtils.getDocIds(notOperator.getTrues()), List.of(0, 1, 3,
5, 6, 7, 8, 9));
+ }
+
+ @Test
+ public void testGetBitmapsWithoutNullChild() {
+ int numDocs = 10;
+ AndFilterOperator andOperator = new AndFilterOperator(
+ List.of(bitmapOp(numDocs, false, 2, 3, 4, 7), bitmapOp(numDocs, false,
2, 4, 8)), null, numDocs, true);
+
+ assertFalse(andOperator.mayHaveNulls());
+ assertNull(andOperator.getBitmaps().getNullBitmap());
+ assertEquals(andOperator.getNumMatchingDocs(), 2);
+ }
+
+ @Test
+ public void testGetNulls() {
+ int numDocs = 10;
+ // The first child is UNKNOWN on {4, 5, 6}; the AND is UNKNOWN only on 4,
where the second child is true, since 5
+ // and 6 are false through it
+ AndFilterOperator andFilterOperator = new AndFilterOperator(
+ List.of(new TestFilterOperator(new int[]{0, 1, 2, 3}, new int[]{4, 5,
6}, numDocs),
+ new TestFilterOperator(new int[]{2, 3, 4, 7}, numDocs)), null,
numDocs, true);
+
+ assertTrue(andFilterOperator.mayHaveNulls());
+ assertEquals(TestUtils.getDocIds(andFilterOperator.getTrues()), List.of(2,
3));
+ assertEquals(TestUtils.getDocIds(andFilterOperator.getNulls()),
List.of(4));
+ assertEquals(TestUtils.getDocIds(andFilterOperator.getFalses()),
List.of(0, 1, 5, 6, 7, 8, 9));
+ }
+
+ @Test
+ public void testChildTrueNowhereButUnknownSomewhere() {
+ int numDocs = 5;
+ // The first child is true nowhere and UNKNOWN on {1, 2}; the AND is
UNKNOWN on 1, where the second child is
+ // true, and false everywhere else
+ AndFilterOperator andFilterOperator = new AndFilterOperator(
+ List.of(new TestFilterOperator(new int[0], new int[]{1, 2}, numDocs),
+ new TestFilterOperator(new int[]{1, 3}, numDocs)), null, numDocs,
true);
+
+ assertEquals(TestUtils.getDocIds(andFilterOperator.getTrues()), List.of());
+ assertEquals(TestUtils.getDocIds(andFilterOperator.getNulls()),
List.of(1));
+ assertEquals(TestUtils.getDocIds(andFilterOperator.getFalses()),
List.of(0, 2, 3, 4));
+ }
+
+ @Test
+ public void testGetNullsWhenNeverFalse() {
+ int numDocs = 3;
+ // The negated child is true nowhere and UNKNOWN on 1, so its negation is
true on {0, 2}, UNKNOWN on 1 and false
+ // nowhere. The conjunction with a match-all is then never false either,
yet still UNKNOWN on 1
+ NotFilterOperator notFilterOperator =
+ new NotFilterOperator(new TestFilterOperator(new int[0], new int[]{1},
numDocs), numDocs, true);
+ AndFilterOperator andFilterOperator = new AndFilterOperator(
+ List.of(notFilterOperator, new MatchAllFilterOperator(numDocs)), null,
numDocs, true);
+
+ assertEquals(TestUtils.getDocIds(andFilterOperator.getTrues()), List.of(0,
2));
+ assertEquals(TestUtils.getDocIds(andFilterOperator.getNulls()),
List.of(1));
+ assertEquals(TestUtils.getDocIds(andFilterOperator.getFalses()),
List.of());
+ }
+
+ @Test
+ public void testGetNullsPropagateThroughNestedOr() {
+ int numDocs = 8;
+ // The OR is UNKNOWN on {1, 2}, where its first child is UNKNOWN and its
second false; the AND above it inherits
+ // that where its own other child is true, and the outer negation has to
leave those documents out
+ OrFilterOperator orFilterOperator = new OrFilterOperator(
+ List.of(new TestFilterOperator(new int[]{0}, new int[]{1, 2}, numDocs),
+ new TestFilterOperator(new int[]{3}, numDocs)), null, numDocs,
true);
+ AndFilterOperator andFilterOperator = new AndFilterOperator(
+ List.of(new TestFilterOperator(new int[]{0, 1, 2, 3, 4}, numDocs),
orFilterOperator), null, numDocs, true);
+
+ assertEquals(TestUtils.getDocIds(andFilterOperator.getNulls()), List.of(1,
2));
+ NotFilterOperator notFilterOperator = new
NotFilterOperator(andFilterOperator, numDocs, true);
+ assertEquals(TestUtils.getDocIds(notFilterOperator.getTrues()), List.of(4,
5, 6, 7));
+ }
+
+ @Test
+ public void testGetNumMatchingDocsWithNullChild() {
+ int numDocs = 10;
+ // The second child is exclusive, so true on all but {0, 1, 4}; the AND is
true on {2, 3} and UNKNOWN on {5, 6},
+ // where the first child is UNKNOWN and the second true
+ AndFilterOperator andOperator = new AndFilterOperator(List.of(
+ new BitmapBasedFilterOperator(MutableRoaringBitmap.bitmapOf(0, 1, 2,
3), false, numDocs,
+ MutableRoaringBitmap.bitmapOf(4, 5, 6)), bitmapOp(numDocs, true,
0, 1, 4)), null, numDocs, true);
+
+ assertTrue(andOperator.canOptimizeCount());
+ assertEquals(andOperator.getNumMatchingDocs(), 2);
+ BitmapCollection bitmaps = andOperator.getBitmaps();
+ assertEquals(bitmaps.reduce().toArray(), new int[]{2, 3});
+ assertEquals(bitmaps.getNullBitmap().toArray(), new int[]{5, 6});
+ }
+
private static BitmapBasedFilterOperator bitmapOp(int numDocs, boolean
exclusive, int... docIds) {
MutableRoaringBitmap bitmap = new MutableRoaringBitmap();
bitmap.add(docIds);
diff --git
a/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/BitmapCollectionTest.java
b/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/BitmapCollectionTest.java
index 5224b35f9d7..98d2a1f7786 100644
---
a/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/BitmapCollectionTest.java
+++
b/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/BitmapCollectionTest.java
@@ -23,6 +23,8 @@ import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;
import static org.testng.Assert.assertEquals;
+import static org.testng.Assert.assertNull;
+import static org.testng.Assert.assertSame;
public class BitmapCollectionTest {
@@ -225,6 +227,95 @@ public class BitmapCollectionTest {
new BitmapCollection(numDocs, rightInverted, split(right))), expected);
}
+ @Test
+ public void testExcludingNulls() {
+ int numDocs = 10;
+ ImmutableRoaringBitmap docIds = ImmutableRoaringBitmap.bitmapOf(0, 5);
+ ImmutableRoaringBitmap nullBitmap = ImmutableRoaringBitmap.bitmapOf(5, 7);
+
+ BitmapCollection bitmaps = new BitmapCollection(numDocs, false,
docIds).excludingNulls(nullBitmap);
+ assertSame(bitmaps.getNullBitmap(), nullBitmap);
+ assertEquals(bitmaps.getCardinality(), 1);
+ assertEquals(bitmaps.reduce().toArray(), new int[]{0});
+
+ // NOT of UNKNOWN is UNKNOWN: the inversion is the complement of the union
minus the null documents
+ bitmaps.invert();
+ assertSame(bitmaps.getNullBitmap(), nullBitmap);
+ assertEquals(bitmaps.getCardinality(), 7);
+ assertEquals(bitmaps.reduce().toArray(), new int[]{1, 2, 3, 4, 6, 8, 9});
+
+ BitmapCollection splitBitmaps = new BitmapCollection(numDocs, true,
split(docIds)).excludingNulls(nullBitmap);
+ assertEquals(splitBitmaps.getCardinality(), 7);
+ assertEquals(splitBitmaps.reduce().toArray(), new int[]{1, 2, 3, 4, 6, 8,
9});
+ }
+
+ @Test
+ public void testExcludingNoNulls() {
+ BitmapCollection bitmaps = new BitmapCollection(10, false,
ImmutableRoaringBitmap.bitmapOf(0, 5));
+ assertSame(bitmaps.excludingNulls(null), bitmaps);
+ assertSame(bitmaps.excludingNulls(ImmutableRoaringBitmap.bitmapOf()),
bitmaps);
+ assertNull(bitmaps.getNullBitmap());
+ assertEquals(bitmaps.getCardinality(), 2);
+ assertEquals(bitmaps.invert().getCardinality(), 8);
+ }
+
+ @Test
+ public void testAndOrCardinalityWithNulls() {
+ int numDocs = 10;
+ // True on {0, 1}
+ BitmapCollection left = new BitmapCollection(numDocs, false,
ImmutableRoaringBitmap.bitmapOf(0, 1, 5))
+ .excludingNulls(ImmutableRoaringBitmap.bitmapOf(5, 7));
+ // True on {0, 4, 5, 6, 7, 8, 9}
+ BitmapCollection right = new BitmapCollection(numDocs, true,
ImmutableRoaringBitmap.bitmapOf(1, 2))
+ .excludingNulls(ImmutableRoaringBitmap.bitmapOf(3));
+ // True on {1, 5, 9}
+ BitmapCollection plain = new BitmapCollection(numDocs, false,
ImmutableRoaringBitmap.bitmapOf(1, 5, 9));
+
+ assertEquals(left.andCardinality(right), 1);
+ assertEquals(left.orCardinality(right), 8);
+ assertEquals(left.andCardinality(plain), 1);
+ assertEquals(plain.andCardinality(left), 1);
+ assertEquals(left.orCardinality(plain), 4);
+ assertEquals(plain.orCardinality(left), 4);
+ }
+
+ /// Checks the cardinalities against the materialized true documents over
every combination of inversion and null
+ /// bitmaps on either side, with nulls inside and outside the unions and
shared between the sides.
+ @Test
+ public void testCardinalitiesMatchMaterializedTrues() {
+ int numDocs = 12;
+ ImmutableRoaringBitmap leftDocIds = ImmutableRoaringBitmap.bitmapOf(0, 1,
5, 6, 9);
+ ImmutableRoaringBitmap rightDocIds = ImmutableRoaringBitmap.bitmapOf(1, 2,
6, 10);
+ ImmutableRoaringBitmap[] nullBitmaps = {
+ null, ImmutableRoaringBitmap.bitmapOf(1, 5, 7),
ImmutableRoaringBitmap.bitmapOf(2, 7, 9, 11)
+ };
+ for (boolean leftInverted : new boolean[]{false, true}) {
+ for (boolean rightInverted : new boolean[]{false, true}) {
+ for (ImmutableRoaringBitmap leftNulls : nullBitmaps) {
+ for (ImmutableRoaringBitmap rightNulls : nullBitmaps) {
+ BitmapCollection left =
+ new BitmapCollection(numDocs, leftInverted,
split(leftDocIds)).excludingNulls(leftNulls);
+ BitmapCollection right =
+ new BitmapCollection(numDocs, rightInverted,
rightDocIds).excludingNulls(rightNulls);
+ ImmutableRoaringBitmap leftTrues = left.reduce();
+ ImmutableRoaringBitmap rightTrues = right.reduce();
+ String description = String.format("leftInverted=%s
rightInverted=%s leftNulls=%s rightNulls=%s",
+ leftInverted, rightInverted, leftNulls, rightNulls);
+
+ assertEquals(left.getCardinality(), leftTrues.getCardinality(),
description);
+ assertEquals(right.getCardinality(), rightTrues.getCardinality(),
description);
+ int andCardinality =
ImmutableRoaringBitmap.andCardinality(leftTrues, rightTrues);
+ assertEquals(left.andCardinality(right), andCardinality,
description);
+ assertEquals(right.andCardinality(left), andCardinality,
description);
+ int orCardinality =
ImmutableRoaringBitmap.orCardinality(leftTrues, rightTrues);
+ assertEquals(left.orCardinality(right), orCardinality,
description);
+ assertEquals(right.orCardinality(left), orCardinality,
description);
+ }
+ }
+ }
+ }
+ }
+
private ImmutableRoaringBitmap[] split(ImmutableRoaringBitmap bitmap) {
if (bitmap.isEmpty()) {
return new ImmutableRoaringBitmap[]{bitmap};
diff --git
a/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/InvertedIndexFilterOperatorTest.java
b/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/InvertedIndexFilterOperatorTest.java
index affc3fed8ba..7582b585b7a 100644
---
a/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/InvertedIndexFilterOperatorTest.java
+++
b/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/InvertedIndexFilterOperatorTest.java
@@ -18,11 +18,13 @@
*/
package org.apache.pinot.core.operator.filter;
+import javax.annotation.Nullable;
import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
import org.apache.pinot.core.query.request.context.QueryContext;
import org.apache.pinot.segment.spi.datasource.DataSource;
import org.apache.pinot.segment.spi.datasource.DataSourceMetadata;
import org.apache.pinot.segment.spi.index.reader.InvertedIndexReader;
+import org.apache.pinot.segment.spi.index.reader.NullValueVectorReader;
import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
import org.roaringbitmap.buffer.MutableRoaringBitmap;
import org.testng.annotations.Test;
@@ -30,10 +32,13 @@ import org.testng.annotations.Test;
import static org.mockito.Mockito.mock;
import static org.mockito.Mockito.when;
import static org.testng.Assert.assertEquals;
+import static org.testng.Assert.assertFalse;
+import static org.testng.Assert.assertTrue;
-/// Targeted tests for [InvertedIndexFilterOperator#getNumMatchingDocs()].
Five tests cover every
-/// distinct code branch (SV loop, MV switch arms {0, 2, default}, and
exclusive arithmetic)
+/// Targeted tests for [InvertedIndexFilterOperator#getNumMatchingDocs()]. The
two-valued tests cover every
+/// distinct code branch (SV loop, MV switch arms {0, 2, default}, and
exclusive arithmetic); the null handling ones
+/// check that null rows are left out of the count and the bitmaps.
public class InvertedIndexFilterOperatorTest {
private static final int NUM_DOCS = 1000;
@@ -89,6 +94,47 @@ public class InvertedIndexFilterOperatorTest {
assertEquals(operator.getNumMatchingDocs(), NUM_DOCS);
}
+ // Null handling: null rows are UNKNOWN, so they are left out of the count
and the bitmaps on both sides of exclusive
+ @Test
+ public void testNullRowsAreExcluded() {
+ ImmutableRoaringBitmap b0 = bitmap(0, 1, 2, 3);
+ ImmutableRoaringBitmap b1 = bitmap(4, 5, 6);
+ ImmutableRoaringBitmap nullBitmap = bitmap(3, 100);
+ InvertedIndexFilterOperator operator =
+ newOperator(true, false, new int[]{0, 1}, new
ImmutableRoaringBitmap[]{b0, b1}, nullBitmap);
+ assertTrue(operator.mayHaveNulls());
+ assertEquals(operator.getNumMatchingDocs(), 6);
+ assertEquals(operator.getBitmaps().reduce().toArray(), new int[]{0, 1, 2,
4, 5, 6});
+
+ operator = newOperator(true, true, new int[]{0, 1}, new
ImmutableRoaringBitmap[]{b0, b1}, nullBitmap);
+ assertEquals(operator.getNumMatchingDocs(), NUM_DOCS - 8);
+ assertFalse(operator.getBitmaps().reduce().contains(100));
+ }
+
+ // Multi-value postings overlap, so the null rows among the matches are
counted on the union
+ @Test
+ public void testNullRowsAreExcludedOnMultiValueColumn() {
+ ImmutableRoaringBitmap b0 = bitmap(0, 1, 2, 3, 4);
+ ImmutableRoaringBitmap b1 = bitmap(3, 4, 5, 6);
+ ImmutableRoaringBitmap nullBitmap = bitmap(3, 100);
+ InvertedIndexFilterOperator operator =
+ newOperator(false, false, new int[]{0, 1}, new
ImmutableRoaringBitmap[]{b0, b1}, nullBitmap);
+ assertEquals(operator.getNumMatchingDocs(), 6);
+
+ operator = newOperator(false, true, new int[]{0, 1}, new
ImmutableRoaringBitmap[]{b0, b1}, nullBitmap);
+ assertEquals(operator.getNumMatchingDocs(), NUM_DOCS - 8);
+ }
+
+ // An empty null vector leaves the two-valued shortcuts in place
+ @Test
+ public void testEmptyNullBitmapIsIgnored() {
+ ImmutableRoaringBitmap b0 = bitmap(0, 1, 2, 3);
+ InvertedIndexFilterOperator operator =
+ newOperator(true, false, new int[]{0}, new
ImmutableRoaringBitmap[]{b0}, bitmap());
+ assertFalse(operator.mayHaveNulls());
+ assertEquals(operator.getNumMatchingDocs(), 4);
+ }
+
// ----- helpers -----
private static ImmutableRoaringBitmap bitmap(int... docIds) {
@@ -99,11 +145,16 @@ public class InvertedIndexFilterOperatorTest {
return bitmap;
}
- @SuppressWarnings({"unchecked", "rawtypes"})
private static InvertedIndexFilterOperator newOperator(boolean singleValue,
boolean exclusive, int[] dictIds,
ImmutableRoaringBitmap[] perDictIdBitmaps) {
+ return newOperator(singleValue, exclusive, dictIds, perDictIdBitmaps,
null);
+ }
+
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ private static InvertedIndexFilterOperator newOperator(boolean singleValue,
boolean exclusive, int[] dictIds,
+ ImmutableRoaringBitmap[] perDictIdBitmaps, @Nullable
ImmutableRoaringBitmap nullBitmap) {
QueryContext queryContext = mock(QueryContext.class);
- when(queryContext.isNullHandlingEnabled()).thenReturn(false);
+ when(queryContext.isNullHandlingEnabled()).thenReturn(nullBitmap != null);
DataSourceMetadata metadata = mock(DataSourceMetadata.class);
when(metadata.isSingleValue()).thenReturn(singleValue);
@@ -116,6 +167,11 @@ public class InvertedIndexFilterOperatorTest {
DataSource dataSource = mock(DataSource.class);
when(dataSource.getDataSourceMetadata()).thenReturn(metadata);
when(dataSource.getInvertedIndex()).thenReturn(reader);
+ if (nullBitmap != null) {
+ NullValueVectorReader nullValueVector =
mock(NullValueVectorReader.class);
+ when(nullValueVector.getNullBitmap()).thenReturn(nullBitmap);
+ when(dataSource.getNullValueVector()).thenReturn(nullValueVector);
+ }
PredicateEvaluator predicateEvaluator = mock(PredicateEvaluator.class);
when(predicateEvaluator.isExclusive()).thenReturn(exclusive);
diff --git
a/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/NotFilterOperatorTest.java
b/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/NotFilterOperatorTest.java
index d130d603577..f291252efe5 100644
---
a/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/NotFilterOperatorTest.java
+++
b/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/NotFilterOperatorTest.java
@@ -23,9 +23,13 @@ import java.util.Iterator;
import java.util.List;
import org.apache.pinot.core.common.BlockDocIdIterator;
import org.apache.pinot.segment.spi.Constants;
-import org.testng.Assert;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
import org.testng.annotations.Test;
+import static org.testng.Assert.assertEquals;
+import static org.testng.Assert.assertFalse;
+import static org.testng.Assert.assertTrue;
+
public class NotFilterOperatorTest {
@@ -38,7 +42,7 @@ public class NotFilterOperatorTest {
BlockDocIdIterator iterator =
notFilterOperator.nextBlock().getBlockDocIdSet().iterator();
int docId;
while ((docId = iterator.next()) != Constants.EOF) {
- Assert.assertEquals(docId, expectedIterator.next().intValue());
+ assertEquals(docId, expectedIterator.next().intValue());
}
}
@@ -51,8 +55,73 @@ public class NotFilterOperatorTest {
NotFilterOperator notFilterOperator =
new NotFilterOperator(new TestFilterOperator(docIds, nullDocIds,
numDocs), numDocs, true);
- Assert.assertEquals(TestUtils.getDocIds(notFilterOperator.getTrues()),
List.of(7, 8, 9));
- Assert.assertEquals(TestUtils.getDocIds(notFilterOperator.getFalses()),
List.of(0, 1, 2, 3));
+ assertEquals(TestUtils.getDocIds(notFilterOperator.getTrues()), List.of(7,
8, 9));
+ assertEquals(TestUtils.getDocIds(notFilterOperator.getFalses()),
List.of(0, 1, 2, 3));
+ }
+
+ @Test
+ public void testNotPropagatesNulls() {
+ int numDocs = 6;
+ NotFilterOperator notFilterOperator =
+ new NotFilterOperator(new TestFilterOperator(new int[]{0, 1}, new
int[]{2, 3}, numDocs), numDocs, true);
+ assertTrue(notFilterOperator.mayHaveNulls());
+ assertEquals(TestUtils.getDocIds(notFilterOperator.getNulls()), List.of(2,
3));
+
+ // A parent reads the nulls of its children when deriving its falses: doc
2 is UNKNOWN through the negation while
+ // the other child is true, so it is UNKNOWN for the AND and stays out of
the outer negation
+ AndFilterOperator andFilterOperator =
+ new AndFilterOperator(List.of(notFilterOperator, new
TestFilterOperator(new int[]{0, 2, 4}, numDocs)), null,
+ numDocs, true);
+ NotFilterOperator outerNotFilterOperator = new
NotFilterOperator(andFilterOperator, numDocs, true);
+ assertEquals(TestUtils.getDocIds(outerNotFilterOperator.getTrues()),
List.of(0, 1, 3, 5));
+ }
+
+ @Test
+ public void testNotCountAndBitmapsWithNull() {
+ int numDocs = 10;
+ ImmutableRoaringBitmap docIds = ImmutableRoaringBitmap.bitmapOf(0, 1, 2,
3);
+ ImmutableRoaringBitmap nullBitmap = ImmutableRoaringBitmap.bitmapOf(4, 5,
6);
+
+ BitmapBasedFilterOperator child = new BitmapBasedFilterOperator(docIds,
false, numDocs, nullBitmap);
+ assertTrue(child.canOptimizeCount());
+ assertEquals(child.getNumMatchingDocs(), 4);
+ assertEquals(child.getBitmaps().reduce().toArray(), new int[]{0, 1, 2, 3});
+
+ NotFilterOperator notFilterOperator = new NotFilterOperator(child,
numDocs, true);
+ assertTrue(notFilterOperator.mayHaveNulls());
+ assertTrue(notFilterOperator.canOptimizeCount());
+ assertEquals(notFilterOperator.getNumMatchingDocs(), 3);
+ assertTrue(notFilterOperator.canProduceBitmaps());
+ assertEquals(notFilterOperator.getBitmaps().reduce().toArray(), new
int[]{7, 8, 9});
+ assertEquals(TestUtils.getDocIds(notFilterOperator.getTrues()), List.of(7,
8, 9));
+ }
+
+ @Test
+ public void testNotCountAndBitmapsWithNullOnExclusiveChild() {
+ int numDocs = 10;
+ // The child is true on every document but {0, 1, 2, 3}, of which {2, 3}
are UNKNOWN rather than false
+ ImmutableRoaringBitmap docIds = ImmutableRoaringBitmap.bitmapOf(0, 1, 2,
3);
+ ImmutableRoaringBitmap nullBitmap = ImmutableRoaringBitmap.bitmapOf(2, 3);
+
+ BitmapBasedFilterOperator child = new BitmapBasedFilterOperator(docIds,
true, numDocs, nullBitmap);
+ assertEquals(child.getNumMatchingDocs(), 6);
+ assertEquals(child.getBitmaps().reduce().toArray(), new int[]{4, 5, 6, 7,
8, 9});
+
+ NotFilterOperator notFilterOperator = new NotFilterOperator(child,
numDocs, true);
+ assertEquals(notFilterOperator.getNumMatchingDocs(), 2);
+ assertEquals(notFilterOperator.getBitmaps().reduce().toArray(), new
int[]{0, 1});
+ assertEquals(TestUtils.getDocIds(notFilterOperator.getTrues()), List.of(0,
1));
+ }
+
+ @Test
+ public void testNotCountWithoutNull() {
+ int numDocs = 10;
+ NotFilterOperator notFilterOperator = new NotFilterOperator(
+ new BitmapBasedFilterOperator(ImmutableRoaringBitmap.bitmapOf(0, 1, 2,
3), false, numDocs), numDocs, true);
+
+ assertFalse(notFilterOperator.mayHaveNulls());
+ assertTrue(notFilterOperator.canOptimizeCount());
+ assertEquals(notFilterOperator.getNumMatchingDocs(), 6);
}
@Test
@@ -61,7 +130,7 @@ public class NotFilterOperatorTest {
NotFilterOperator notFilterOperator = new
NotFilterOperator(EmptyFilterOperator.getInstance(), numDocs, true);
- Assert.assertEquals(TestUtils.getDocIds(notFilterOperator.getTrues()),
List.of(0, 1, 2, 3, 4));
- Assert.assertEquals(TestUtils.getDocIds(notFilterOperator.getFalses()),
List.of());
+ assertEquals(TestUtils.getDocIds(notFilterOperator.getTrues()), List.of(0,
1, 2, 3, 4));
+ assertEquals(TestUtils.getDocIds(notFilterOperator.getFalses()),
List.of());
}
}
diff --git
a/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/OrFilterOperatorTest.java
b/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/OrFilterOperatorTest.java
index 7c95bd9e683..4a98c60e616 100644
---
a/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/OrFilterOperatorTest.java
+++
b/pinot-core/src/test/java/org/apache/pinot/core/operator/filter/OrFilterOperatorTest.java
@@ -276,6 +276,74 @@ public class OrFilterOperatorTest {
assertEquals(orOperator.getBitmaps().reduce().toArray(), new int[]{1, 2,
3, 6, 8, 30});
}
+ @Test
+ public void testGetBitmapsWithNullChild() {
+ int numDocs = 8;
+ // The second child is UNKNOWN on {4, 5, 6}. The OR is UNKNOWN only where
no child is true: 4 is true through the
+ // first child, so only 5 and 6 stay UNKNOWN
+ OrFilterOperator orOperator = new
OrFilterOperator(List.of(bitmapOp(numDocs, false, 1, 2, 4),
+ new BitmapBasedFilterOperator(MutableRoaringBitmap.bitmapOf(0, 1),
false, numDocs,
+ MutableRoaringBitmap.bitmapOf(4, 5, 6))), null, numDocs, true);
+
+ assertTrue(orOperator.canProduceBitmaps());
+ assertTrue(orOperator.mayHaveNulls());
+ BitmapCollection bitmaps = orOperator.getBitmaps();
+ assertEquals(bitmaps.reduce().toArray(), new int[]{0, 1, 2, 4});
+ assertEquals(bitmaps.getNullBitmap().toArray(), new int[]{5, 6});
+ assertEquals(orOperator.getNumMatchingDocs(), 4);
+
+ NotFilterOperator notOperator = new NotFilterOperator(orOperator, numDocs,
true);
+ assertTrue(notOperator.canOptimizeCount());
+ assertEquals(notOperator.getNumMatchingDocs(), 2);
+ assertEquals(notOperator.getBitmaps().reduce().toArray(), new int[]{3, 7});
+ assertEquals(TestUtils.getDocIds(notOperator.getTrues()), List.of(3, 7));
+ }
+
+ @Test
+ public void testGetNulls() {
+ int numDocs = 8;
+ // The second child is UNKNOWN on {4, 5, 6}; the OR is UNKNOWN only on 5
and 6, since 4 is true through the first
+ // child
+ OrFilterOperator orFilterOperator = new OrFilterOperator(
+ List.of(new TestFilterOperator(new int[]{1, 2, 4}, numDocs),
+ new TestFilterOperator(new int[]{0, 1}, new int[]{4, 5, 6},
numDocs)), null, numDocs, true);
+
+ assertTrue(orFilterOperator.mayHaveNulls());
+ assertEquals(TestUtils.getDocIds(orFilterOperator.getTrues()), List.of(0,
1, 2, 4));
+ assertEquals(TestUtils.getDocIds(orFilterOperator.getNulls()), List.of(5,
6));
+ assertEquals(TestUtils.getDocIds(orFilterOperator.getFalses()), List.of(3,
7));
+ }
+
+ @Test
+ public void testChildTrueNowhereButUnknownSomewhere() {
+ int numDocs = 5;
+ // The first child is true nowhere and UNKNOWN on {1, 2}; the OR is
UNKNOWN on 2, where the second child is
+ // false, and false on {0, 4}
+ OrFilterOperator orFilterOperator = new OrFilterOperator(
+ List.of(new TestFilterOperator(new int[0], new int[]{1, 2}, numDocs),
+ new TestFilterOperator(new int[]{1, 3}, numDocs)), null, numDocs,
true);
+
+ assertEquals(TestUtils.getDocIds(orFilterOperator.getTrues()), List.of(1,
3));
+ assertEquals(TestUtils.getDocIds(orFilterOperator.getNulls()), List.of(2));
+ assertEquals(TestUtils.getDocIds(orFilterOperator.getFalses()), List.of(0,
4));
+ }
+
+ @Test
+ public void testGetNullsPropagateThroughNestedAnd() {
+ int numDocs = 6;
+ // The AND is UNKNOWN on 3, where its first child is UNKNOWN and its
second true; the OR above it inherits that
+ // where its own other child is false, and the outer negation has to leave
that document out
+ AndFilterOperator andFilterOperator = new AndFilterOperator(
+ List.of(new TestFilterOperator(new int[]{1, 2}, new int[]{3, 4},
numDocs),
+ new TestFilterOperator(new int[]{2, 3, 5}, numDocs)), null,
numDocs, true);
+ OrFilterOperator orFilterOperator = new OrFilterOperator(
+ List.of(new TestFilterOperator(new int[]{0}, numDocs),
andFilterOperator), null, numDocs, true);
+
+ assertEquals(TestUtils.getDocIds(orFilterOperator.getNulls()), List.of(3));
+ NotFilterOperator notFilterOperator = new
NotFilterOperator(orFilterOperator, numDocs, true);
+ assertEquals(TestUtils.getDocIds(notFilterOperator.getTrues()), List.of(1,
4, 5));
+ }
+
private static BitmapBasedFilterOperator bitmapOp(int numDocs, boolean
exclusive, int... docIds) {
MutableRoaringBitmap bitmap = new MutableRoaringBitmap();
bitmap.add(docIds);
diff --git
a/pinot-core/src/test/java/org/apache/pinot/core/startree/v2/BaseStarTreeV2Test.java
b/pinot-core/src/test/java/org/apache/pinot/core/startree/v2/BaseStarTreeV2Test.java
index 4896b6865dd..79ac5a7dd29 100644
---
a/pinot-core/src/test/java/org/apache/pinot/core/startree/v2/BaseStarTreeV2Test.java
+++
b/pinot-core/src/test/java/org/apache/pinot/core/startree/v2/BaseStarTreeV2Test.java
@@ -249,7 +249,7 @@ abstract class BaseStarTreeV2Test<R, A> {
filterPlanNode.run();
Map<String, List<CompositePredicateEvaluator>> predicateEvaluatorsMap =
StarTreeUtils.extractPredicateEvaluatorsMap(_indexSegment,
queryContext.getFilter(),
- filterPlanNode.getPredicateEvaluators());
+ filterPlanNode.getPredicateEvaluators(),
queryContext.isNullHandlingEnabled());
assertNull(predicateEvaluatorsMap);
}
@@ -281,7 +281,7 @@ abstract class BaseStarTreeV2Test<R, A> {
filterPlanNode.run();
Map<String, List<CompositePredicateEvaluator>> predicateEvaluatorsMap =
StarTreeUtils.extractPredicateEvaluatorsMap(_indexSegment,
queryContext.getFilter(),
- filterPlanNode.getPredicateEvaluators());
+ filterPlanNode.getPredicateEvaluators(),
queryContext.isNullHandlingEnabled());
assertNotNull(predicateEvaluatorsMap);
// Extract values with star-tree
diff --git
a/pinot-core/src/test/java/org/apache/pinot/queries/NullHandlingEnabledQueriesTest.java
b/pinot-core/src/test/java/org/apache/pinot/queries/NullHandlingEnabledQueriesTest.java
index 0afe4ef6ad3..cb48a2e910a 100644
---
a/pinot-core/src/test/java/org/apache/pinot/queries/NullHandlingEnabledQueriesTest.java
+++
b/pinot-core/src/test/java/org/apache/pinot/queries/NullHandlingEnabledQueriesTest.java
@@ -23,11 +23,14 @@ import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
+import java.util.Set;
import javax.annotation.Nullable;
import org.apache.commons.io.FileUtils;
import org.apache.pinot.common.response.broker.ResultTable;
import org.apache.pinot.core.plan.DocIdSetPlanNode;
import
org.apache.pinot.segment.local.indexsegment.immutable.ImmutableSegmentLoader;
+import org.apache.pinot.segment.local.indexsegment.mutable.MutableSegmentImpl;
+import
org.apache.pinot.segment.local.indexsegment.mutable.MutableSegmentImplTestUtils;
import
org.apache.pinot.segment.local.segment.creator.impl.SegmentIndexCreationDriverImpl;
import org.apache.pinot.segment.local.segment.readers.GenericRowRecordReader;
import org.apache.pinot.segment.spi.ImmutableSegment;
@@ -66,6 +69,15 @@ public class NullHandlingEnabledQueriesTest extends
BaseQueriesTest {
new TableConfigBuilder(TableType.OFFLINE).setTableName(RAW_TABLE_NAME)
.setInvertedIndexColumns(List.of(COLUMN1))
.build();
+ private static final TableConfig TABLE_CONFIG_WITH_RANGE_INDEX_COLUMN =
+ new TableConfigBuilder(TableType.OFFLINE).setTableName(RAW_TABLE_NAME)
+ .setRangeIndexColumns(List.of(COLUMN1))
+ .build();
+ private static final TableConfig TABLE_CONFIG_WITH_RAW_RANGE_INDEX_COLUMN =
+ new TableConfigBuilder(TableType.OFFLINE).setTableName(RAW_TABLE_NAME)
+ .setNoDictionaryColumns(List.of(COLUMN1))
+ .setRangeIndexColumns(List.of(COLUMN1))
+ .build();
private static final int NUM_OF_SEGMENT_COPIES = 4;
private static final Map<String, String> QUERY_OPTIONS =
Map.of("enableNullHandling", "true");
@@ -192,6 +204,204 @@ public class NullHandlingEnabledQueriesTest extends
BaseQueriesTest {
assertEquals(rows.get(2), new Object[]{null, (long) 3 *
NUM_OF_SEGMENT_COPIES});
}
+ /// A predicate that no real value fails is true for every non-null row and
UNKNOWN for a null one, so it selects
+ /// the non-null rows and its negation selects nothing. A column with a null
therefore has no predicate that is
+ /// always true or always false for the query, whatever the evaluator
concludes over the dictionary's values.
+ @Test
+ public void testPredicateOverEveryRealValueExcludesNulls()
+ throws Exception {
+ initializeRows();
+ insertRow(1);
+ insertRow(null);
+ insertRow(2);
+ Schema schema = schemaBuilder().addSingleValueDimension(COLUMN1,
DataType.INT).build();
+ setUpSegments(TABLE_CONFIG, schema);
+
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
%s <> 99999", COLUMN1)).get(0)[0],
+ (long) 2 * NUM_OF_SEGMENT_COPIES);
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
NOT (%s <> 99999)", COLUMN1)).get(0)[0],
+ 0L, "NOT of UNKNOWN is UNKNOWN, so the null row must not be selected");
+ }
+
+ /// The mirror image: a predicate that no real value satisfies selects
nothing, and its negation selects the non-null
+ /// rows only, rather than every row.
+ @Test
+ public void testPredicateOverNoRealValueExcludesNullsWhenNegated()
+ throws Exception {
+ initializeRows();
+ insertRow(1);
+ insertRow(null);
+ insertRow(2);
+ Schema schema = schemaBuilder().addSingleValueDimension(COLUMN1,
DataType.INT).build();
+ setUpSegments(TABLE_CONFIG, schema);
+
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
%s = 99999", COLUMN1)).get(0)[0], 0L);
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
NOT (%s = 99999)", COLUMN1)).get(0)[0],
+ (long) 2 * NUM_OF_SEGMENT_COPIES, "The null row is UNKNOWN under the
negation too, and must stay out");
+ }
+
+ @DataProvider(name = "IndexedTableConfigs")
+ public static Object[][] getIndexedTableConfigs() {
+ return new Object[][]{{TABLE_CONFIG_WITH_INVERTED_INDEX_COLUMN},
{TABLE_CONFIG_WITH_SORTED_COLUMN}};
+ }
+
+ /// A lone `COUNT(*)` takes its count straight from the index, so an
index-based filter has to leave the null rows
+ /// out of that count too: when the predicate is exclusive, when it matches
the default value a null row is stored
+ /// under, and when it is negated.
+ @Test(dataProvider = "IndexedTableConfigs")
+ public void testFastFilteredCountExcludesNulls(TableConfig tableConfig)
+ throws Exception {
+ initializeRows();
+ insertRow(null);
+ insertRow(1);
+ insertRow(2);
+ Schema schema = schemaBuilder().addSingleValueDimension(COLUMN1,
DataType.INT).build();
+ setUpSegments(tableConfig, schema);
+
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
%s <> 1", COLUMN1)).get(0)[0],
+ (long) NUM_OF_SEGMENT_COPIES);
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
%s = %d", COLUMN1,
+ FieldSpec.DEFAULT_DIMENSION_NULL_VALUE_OF_INT)).get(0)[0], 0L);
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
NOT (%s = 1)", COLUMN1)).get(0)[0],
+ (long) NUM_OF_SEGMENT_COPIES);
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
%s IN (1, 2)", COLUMN1)).get(0)[0],
+ (long) 2 * NUM_OF_SEGMENT_COPIES);
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
%s < 5", COLUMN1)).get(0)[0],
+ (long) 2 * NUM_OF_SEGMENT_COPIES);
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
NOT (%s > 1)", COLUMN1)).get(0)[0],
+ (long) NUM_OF_SEGMENT_COPIES);
+ }
+
+ /// Both range index configurations crossed with every numeric type, with
the values 1 and 2 of that type.
+ @DataProvider(name = "RangeIndexedTableConfigsAndNumericTypes")
+ public static Object[][] getRangeIndexedTableConfigsAndNumericTypes() {
+ TableConfig[] tableConfigs = {TABLE_CONFIG_WITH_RANGE_INDEX_COLUMN,
TABLE_CONFIG_WITH_RAW_RANGE_INDEX_COLUMN};
+ Object[][] typedValues = {
+ {DataType.INT, 1, 2}, {DataType.LONG, 1L, 2L}, {DataType.FLOAT, 1f,
2f}, {DataType.DOUBLE, 1d, 2d}
+ };
+ List<Object[]> cases = new ArrayList<>();
+ for (TableConfig tableConfig : tableConfigs) {
+ for (Object[] typed : typedValues) {
+ cases.add(new Object[]{tableConfig, typed[0], typed[1], typed[2]});
+ }
+ }
+ return cases.toArray(new Object[0][]);
+ }
+
+ /// The range index stores the null row under the default value like any
other, so a range that covers the default
+ /// would count it, whether the index is over dictionary ids or raw values.
Every numeric type's default null value
+ /// lies below 1, so `< 5` covers it and `> 1` does not.
+ @Test(dataProvider = "RangeIndexedTableConfigsAndNumericTypes")
+ public void testFastFilteredCountExcludesNullsWithRangeIndex(TableConfig
tableConfig, DataType dataType,
+ Object value1, Object value2)
+ throws Exception {
+ initializeRows();
+ insertRow(null);
+ insertRow(value1);
+ insertRow(value2);
+ Schema schema = schemaBuilder().addSingleValueDimension(COLUMN1,
dataType).build();
+ setUpSegments(tableConfig, schema);
+
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
%s < 5", COLUMN1)).get(0)[0],
+ (long) 2 * NUM_OF_SEGMENT_COPIES);
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
%s > 1", COLUMN1)).get(0)[0],
+ (long) NUM_OF_SEGMENT_COPIES);
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
NOT (%s > 1)", COLUMN1)).get(0)[0],
+ (long) NUM_OF_SEGMENT_COPIES);
+ }
+
+ /// `IS NULL` and `IS NOT NULL` are two-valued even on an expression that is
null there: the null makes them true or
+ /// false, never UNKNOWN, so a boolean tree above them must not treat the
null rows as UNKNOWN.
+ @Test
+ public void testIsNullPredicatesOnExpressionsAreTwoValued()
+ throws Exception {
+ initializeRows();
+ insertRowWithTwoColumns(null, 1);
+ insertRowWithTwoColumns(1, 1);
+ insertRowWithTwoColumns(2, 2);
+ Schema schema = schemaBuilder()
+ .addSingleValueDimension(COLUMN1, DataType.INT)
+ .addSingleValueDimension(COLUMN2, DataType.INT)
+ .build();
+ setUpSegments(TABLE_CONFIG, schema);
+
+ // The null row makes the IS NOT NULL false, so the conjunction is false
there and its negation selects the row
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
NOT (add(%s, 0) IS NOT NULL AND %s = 1)",
+ COLUMN1, COLUMN2)).get(0)[0], (long) 2 * NUM_OF_SEGMENT_COPIES);
+ // Likewise through a disjunction whose other branch is false on the null
row
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
NOT (add(%s, 0) IS NOT NULL OR %s = 2)",
+ COLUMN1, COLUMN2)).get(0)[0], (long) NUM_OF_SEGMENT_COPIES);
+ }
+
+ /// A multi-value column's null row is stored as a single default value, and
its posting lists overlap across values,
+ /// so the count is taken over their union.
+ @Test
+ public void testFastFilteredCountExcludesNullsOnMultiValueColumn()
+ throws Exception {
+ initializeRows();
+ insertRow(new Object[]{1, 2});
+ insertRow(null);
+ insertRow(new Object[]{2, 3});
+ Schema schema = schemaBuilder().addMultiValueDimension(COLUMN1,
DataType.INT).build();
+ setUpSegments(TABLE_CONFIG_WITH_INVERTED_INDEX_COLUMN, schema);
+
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
%s <> 1", COLUMN1)).get(0)[0],
+ (long) NUM_OF_SEGMENT_COPIES);
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
%s = %d", COLUMN1,
+ FieldSpec.DEFAULT_DIMENSION_NULL_VALUE_OF_INT)).get(0)[0], 0L);
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
%s IN (2, 3)", COLUMN1)).get(0)[0],
+ (long) 2 * NUM_OF_SEGMENT_COPIES);
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
NOT (%s = 2)", COLUMN1)).get(0)[0], 0L);
+ }
+
+ /// A consuming segment reports its null rows through a vector that grows
with ingestion and hands out a copy on each
+ /// read. The filter takes that copy once, and the index-based count has to
leave those rows out as on a sealed
+ /// segment.
+ @Test
+ public void testFastFilteredCountExcludesNullsOnMutableSegment()
+ throws Exception {
+ Schema schema = schemaBuilder().addSingleValueDimension(COLUMN1,
DataType.INT).build();
+ MutableSegmentImpl mutableSegment =
+ MutableSegmentImplTestUtils.createMutableSegmentImpl(schema, Set.of(),
Set.of(), Set.of(COLUMN1), false, true);
+ for (Integer value : new Integer[]{null, 1, 2}) {
+ GenericRow row = new GenericRow();
+ if (value != null) {
+ row.putValue(COLUMN1, value);
+ } else {
+ row.putDefaultNullValue(COLUMN1,
FieldSpec.DEFAULT_DIMENSION_NULL_VALUE_OF_INT);
+ }
+ mutableSegment.index(row, null);
+ }
+ _indexSegment = mutableSegment;
+ _indexSegments = List.of(mutableSegment, mutableSegment);
+
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
%s <> 1", COLUMN1)).get(0)[0],
+ (long) NUM_OF_SEGMENT_COPIES);
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
%s = %d", COLUMN1,
+ FieldSpec.DEFAULT_DIMENSION_NULL_VALUE_OF_INT)).get(0)[0], 0L);
+ assertEquals(getRows(String.format("SELECT COUNT(*) FROM testTable WHERE
NOT (%s = 1)", COLUMN1)).get(0)[0],
+ (long) NUM_OF_SEGMENT_COPIES);
+ }
+
+ /// The index-based distinct takes the filter's bitmap as its set of rows,
so the null row has to be gone from the
+ /// bitmap already, or it would surface as a distinct `null`.
+ @Test(dataProvider = "IndexedTableConfigs")
+ public void testIndexBasedDistinctExcludesNulls(TableConfig tableConfig)
+ throws Exception {
+ initializeRows();
+ insertRow(null);
+ insertRow(1);
+ insertRow(2);
+ Schema schema = schemaBuilder().addSingleValueDimension(COLUMN1,
DataType.INT).build();
+ setUpSegments(tableConfig, schema);
+ Map<String, String> queryOptions = Map.of("enableNullHandling", "true",
"useIndexBasedDistinctOperator", "true");
+
+ List<Object[]> rows =
+ getRows(String.format("SELECT DISTINCT %s FROM testTable WHERE %s <>
1", COLUMN1, COLUMN1), queryOptions);
+ assertEquals(rows.size(), 1);
+ assertEquals(rows.get(0)[0], 2);
+ }
+
/// A row holding the column's default null value must not join the null
group.
///
/// Ingestion stores that default in the forward index for a null row, so
both share a dictionary id and only the
diff --git
a/pinot-core/src/test/java/org/apache/pinot/queries/StarTreeNullHandlingQueriesTest.java
b/pinot-core/src/test/java/org/apache/pinot/queries/StarTreeNullHandlingQueriesTest.java
new file mode 100644
index 00000000000..e28d30ff6a8
--- /dev/null
+++
b/pinot-core/src/test/java/org/apache/pinot/queries/StarTreeNullHandlingQueriesTest.java
@@ -0,0 +1,210 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.pinot.queries;
+
+import java.io.File;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+import org.apache.commons.io.FileUtils;
+import org.apache.pinot.common.response.broker.BrokerResponseNative;
+import
org.apache.pinot.segment.local.indexsegment.immutable.ImmutableSegmentLoader;
+import
org.apache.pinot.segment.local.segment.creator.impl.SegmentIndexCreationDriverImpl;
+import org.apache.pinot.segment.local.segment.readers.GenericRowRecordReader;
+import org.apache.pinot.segment.local.startree.v2.builder.MultipleTreesBuilder;
+import org.apache.pinot.segment.spi.ImmutableSegment;
+import org.apache.pinot.segment.spi.IndexSegment;
+import org.apache.pinot.segment.spi.creator.SegmentGeneratorConfig;
+import org.apache.pinot.spi.config.table.StarTreeIndexConfig;
+import org.apache.pinot.spi.config.table.TableConfig;
+import org.apache.pinot.spi.config.table.TableType;
+import org.apache.pinot.spi.data.FieldSpec.DataType;
+import org.apache.pinot.spi.data.Schema;
+import org.apache.pinot.spi.data.readers.GenericRow;
+import org.apache.pinot.spi.utils.ReadMode;
+import org.apache.pinot.spi.utils.builder.TableConfigBuilder;
+import org.testng.annotations.AfterClass;
+import org.testng.annotations.BeforeClass;
+import org.testng.annotations.Test;
+
+import static org.testng.Assert.assertEquals;
+import static org.testng.Assert.assertTrue;
+
+
+/// Star-tree usage for queries that enable null handling.
+///
+/// A star-tree folds a null row into the column's default value and counts
it, which is the answer null handling
+/// disabled asks for and the wrong answer when it is enabled. So a star-tree
may only serve a null handling query
+/// when nothing the query touches actually holds a null, and the interesting
cases are the ones where that check
+/// could be skipped.
+public class StarTreeNullHandlingQueriesTest extends BaseQueriesTest {
+ private static final File INDEX_DIR = new File(FileUtils.getTempDirectory(),
"StarTreeNullHandlingQueriesTest");
+ private static final String RAW_TABLE_NAME = "testTable";
+ private static final String SEGMENT_NAME = "testSegment";
+ /// Holds a null value.
+ private static final String NULLABLE_DIMENSION = "d1";
+ /// Holds no null value.
+ private static final String DIMENSION = "d2";
+ private static final String METRIC = "m";
+
+ private static final Map<String, String> QUERY_OPTIONS =
Map.of("enableNullHandling", "true");
+
+ /// `_indexSegments` holds two copies and the harness queries two instances,
so every aggregate is scaled by this.
+ private static final int SEGMENT_COPIES = 4;
+ private static final int NUM_ROWS = 4;
+
+ /// A value no row holds, so a `<>` against it is always true over the real
values and is dropped from the star-tree
+ /// predicate map. It is not true over a null, where it is UNKNOWN and the
row is not selected.
+ private static final int ABSENT_VALUE = 99999;
+
+ private static final Integer[] NULLABLE_DIMENSION_VALUES = {1, null, 2, 2};
+ private static final int[] DIMENSION_VALUES = {5, 5, 6, 6};
+ private static final int[] METRIC_VALUES = {10, 20, 30, 40};
+ private static final int SUM_OF_ALL_ROWS = 10 + 20 + 30 + 40;
+ private static final int NUM_ROWS_WITH_A_NON_NULL_DIMENSION = 3;
+ private static final int SUM_OF_ROWS_WITH_A_NON_NULL_DIMENSION = 10 + 30 +
40;
+
+ private IndexSegment _indexSegment;
+ private List<IndexSegment> _indexSegments;
+
+ @Override
+ protected String getFilter() {
+ return "";
+ }
+
+ @Override
+ protected IndexSegment getIndexSegment() {
+ return _indexSegment;
+ }
+
+ @Override
+ protected List<IndexSegment> getIndexSegments() {
+ return _indexSegments;
+ }
+
+ @BeforeClass
+ public void setUp()
+ throws Exception {
+ FileUtils.deleteDirectory(INDEX_DIR);
+
+ Schema schema = new Schema.SchemaBuilder().setSchemaName(RAW_TABLE_NAME)
+ .addSingleValueDimension(NULLABLE_DIMENSION, DataType.INT)
+ .addSingleValueDimension(DIMENSION, DataType.INT)
+ .addMetric(METRIC, DataType.INT)
+ .build();
+ TableConfig tableConfig = new
TableConfigBuilder(TableType.OFFLINE).setTableName(RAW_TABLE_NAME).build();
+
+ List<GenericRow> rows = new ArrayList<>(NUM_ROWS);
+ for (int i = 0; i < NUM_ROWS; i++) {
+ GenericRow row = new GenericRow();
+ row.putValue(NULLABLE_DIMENSION, NULLABLE_DIMENSION_VALUES[i]);
+ row.putValue(DIMENSION, DIMENSION_VALUES[i]);
+ row.putValue(METRIC, METRIC_VALUES[i]);
+ rows.add(row);
+ }
+
+ SegmentGeneratorConfig segmentGeneratorConfig = new
SegmentGeneratorConfig(tableConfig, schema);
+ segmentGeneratorConfig.setSegmentName(SEGMENT_NAME);
+ segmentGeneratorConfig.setDefaultNullHandlingEnabled(true);
+ segmentGeneratorConfig.setOutDir(INDEX_DIR.getPath());
+ SegmentIndexCreationDriverImpl driver = new
SegmentIndexCreationDriverImpl();
+ driver.init(segmentGeneratorConfig, new GenericRowRecordReader(rows));
+ driver.build();
+
+ File indexDir = new File(INDEX_DIR, SEGMENT_NAME);
+ StarTreeIndexConfig starTreeIndexConfig =
+ new StarTreeIndexConfig(List.of(NULLABLE_DIMENSION, DIMENSION), null,
List.of("SUM__" + METRIC), null, 1);
+ try (MultipleTreesBuilder builder = new
MultipleTreesBuilder(List.of(starTreeIndexConfig), false, indexDir,
+ MultipleTreesBuilder.BuildMode.OFF_HEAP)) {
+ builder.build();
+ }
+
+ ImmutableSegment segment = ImmutableSegmentLoader.load(indexDir,
ReadMode.mmap);
+ _indexSegment = segment;
+ _indexSegments = List.of(segment, segment);
+ }
+
+ @AfterClass
+ public void tearDown()
+ throws IOException {
+ _indexSegment.destroy();
+ FileUtils.deleteDirectory(INDEX_DIR);
+ }
+
+ /// A predicate that is always true over a column's real values is UNKNOWN
over a null, so with null handling it is
+ /// only truly always true for a column without nulls. Dropped anyway, the
column would escape the null checks and
+ /// the star-tree would answer with the null row folded into the column's
default value.
+ @Test
+ public void testAlwaysTruePredicateOnANullableColumnRefusesTheStarTree() {
+ String query = String.format("SELECT SUM(%s) FROM testTable WHERE %s <>
%d", METRIC, NULLABLE_DIMENSION,
+ ABSENT_VALUE);
+
+ BrokerResponseNative brokerResponse = getBrokerResponse(query,
QUERY_OPTIONS);
+
+ assertEquals(brokerResponse.getResultTable().getRows().get(0)[0],
+ (double) SUM_OF_ROWS_WITH_A_NON_NULL_DIMENSION * SEGMENT_COPIES,
+ "A null makes the predicate UNKNOWN, so the row must not be
aggregated");
+ assertEquals(brokerResponse.getNumDocsScanned(), (long)
NUM_ROWS_WITH_A_NON_NULL_DIMENSION * SEGMENT_COPIES,
+ "The rows the filter selects should be scanned one by one, because the
star-tree cannot answer this query");
+ }
+
+ /// A negated predicate that is always false over the real values is the
same verdict reached through the NOT
+ /// branch, and has to follow the same rule.
+ @Test
+ public void
testNegatedAlwaysFalsePredicateOnANullableColumnRefusesTheStarTree() {
+ String query = String.format("SELECT SUM(%s) FROM testTable WHERE NOT (%s
= %d)", METRIC, NULLABLE_DIMENSION,
+ ABSENT_VALUE);
+
+ BrokerResponseNative brokerResponse = getBrokerResponse(query,
QUERY_OPTIONS);
+
+ assertEquals(brokerResponse.getResultTable().getRows().get(0)[0],
+ (double) SUM_OF_ROWS_WITH_A_NON_NULL_DIMENSION * SEGMENT_COPIES);
+ assertEquals(brokerResponse.getNumDocsScanned(), (long)
NUM_ROWS_WITH_A_NON_NULL_DIMENSION * SEGMENT_COPIES);
+ }
+
+ /// An OR clause is dropped as a whole when one of its branches is always
true, which is the same decision made on
+ /// a different path, and has to follow the same rule.
+ @Test
+ public void testAlwaysTrueOrClauseOnANullableColumnRefusesTheStarTree() {
+ String query = String.format("SELECT SUM(%s) FROM testTable WHERE %s = 1
OR %s <> %d", METRIC, NULLABLE_DIMENSION,
+ NULLABLE_DIMENSION, ABSENT_VALUE);
+
+ BrokerResponseNative brokerResponse = getBrokerResponse(query,
QUERY_OPTIONS);
+
+ assertEquals(brokerResponse.getResultTable().getRows().get(0)[0],
+ (double) SUM_OF_ROWS_WITH_A_NON_NULL_DIMENSION * SEGMENT_COPIES);
+ assertEquals(brokerResponse.getNumDocsScanned(), (long)
NUM_ROWS_WITH_A_NON_NULL_DIMENSION * SEGMENT_COPIES);
+ }
+
+ /// The same shape over a column that holds no null keeps the star-tree:
nothing the query touches can turn the
+ /// predicate UNKNOWN, so folding is not a risk and the optimization stands.
+ @Test
+ public void testAlwaysTruePredicateOnANonNullableColumnKeepsTheStarTree() {
+ String query =
+ String.format("SELECT SUM(%s) FROM testTable WHERE %s <> %d", METRIC,
DIMENSION, ABSENT_VALUE);
+
+ BrokerResponseNative brokerResponse = getBrokerResponse(query,
QUERY_OPTIONS);
+
+ assertEquals(brokerResponse.getResultTable().getRows().get(0)[0],
+ (double) SUM_OF_ALL_ROWS * SEGMENT_COPIES);
+ assertTrue(brokerResponse.getNumDocsScanned() < (long) NUM_ROWS *
SEGMENT_COPIES,
+ "Expected the star-tree to answer from pre-aggregated documents, but
every row was scanned");
+ }
+}
diff --git
a/pinot-integration-tests/src/test/java/org/apache/pinot/integration/tests/NullHandlingIntegrationTest.java
b/pinot-integration-tests/src/test/java/org/apache/pinot/integration/tests/NullHandlingIntegrationTest.java
index c158d6913cf..873bc9aa413 100644
---
a/pinot-integration-tests/src/test/java/org/apache/pinot/integration/tests/NullHandlingIntegrationTest.java
+++
b/pinot-integration-tests/src/test/java/org/apache/pinot/integration/tests/NullHandlingIntegrationTest.java
@@ -539,7 +539,9 @@ public class NullHandlingIntegrationTest extends
BaseClusterIntegrationTestSet
+ " PinotLogicalAggregate(group=[{0}], agg#0=[COUNT()],
agg#1=[COUNT() FILTER $1], aggType=[LEAF])\n"
+ " LogicalProject(city=[$10], $f1=[IS TRUE(=($12,
_UTF-8'unknown'))])\n"
+ " PinotLogicalTableScan(table=[[default, mytable]])\n");
- // IS_TRUE should be trimmed off, then the filter becomes always false
in the server execution plan
+ // IS_TRUE should be trimmed off. The predicate matches no value, but
the column has null rows, which are UNKNOWN
+ // under null handling rather than false, so the server plan keeps a
bitmap filter over them instead of an empty
+ // one: its negation must leave them out too
explainAskingServers(query,
"Execution Plan\n"
+ "PinotLogicalAggregate(group=[{0}], agg#0=[COUNT($1)],
agg#1=[COUNT($2)], aggType=[FINAL])\n"
@@ -550,7 +552,7 @@ public class NullHandlingIntegrationTest extends
BaseClusterIntegrationTestSet
+ " GroupByFiltered(groupKeys=[[city]],
aggregations=[[count(*), count(*)]])\n"
+ " Project(columns=[[city]])\n"
+ " DocIdSet(maxDocs=[20000])\n"
- + " FilterEmpty\n"
+ + " FilterBitmap\n"
+ " Project(columns=[[city]])\n"
+ " DocIdSet(maxDocs=[20000])\n"
+ " FilterMatchEntireSegment(numDocs=[100])\n"
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
