propagate inverted status with BitmapDocIdIterator to avoid expensive flipping of bitmaps
diff --git a/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/AndDocIdIterator.java b/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/AndDocIdIterator.java
index 08bc89a..d32a29d 100644
--- a/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/AndDocIdIterator.java
+++ b/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/AndDocIdIterator.java
@@ -32,7 +32,7 @@
private int _nextDocId = 0;
- public AndDocIdIterator(BlockDocIdIterator[] docIdIterators) {
+ public AndDocIdIterator(BlockDocIdIterator... docIdIterators) {
_docIdIterators = docIdIterators;
}
diff --git a/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/BitmapBasedDocIdIterator.java b/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/BitmapBasedDocIdIterator.java
index 222642f..f3d62ee 100644
--- a/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/BitmapBasedDocIdIterator.java
+++ b/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/BitmapBasedDocIdIterator.java
@@ -31,4 +31,11 @@
* Returns a bitmap of the matching document ids.
*/
ImmutableRoaringBitmap getDocIds();
+
+ /**
+ * Returns true if the doc ids represent absence rather than presence and need to be handled specially
+ * */
+ default boolean isInverted() {
+ return false;
+ }
}
diff --git a/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/InvertedBitmapDocIdIterator.java b/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/InvertedBitmapDocIdIterator.java
new file mode 100644
index 0000000..d187790
--- /dev/null
+++ b/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/InvertedBitmapDocIdIterator.java
@@ -0,0 +1,75 @@
+/**
+ * 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.core.operator.dociditerators;
+
+import org.apache.pinot.segment.spi.Constants;
+import org.roaringbitmap.PeekableIntIterator;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+
+
+public class InvertedBitmapDocIdIterator implements BitmapBasedDocIdIterator {
+ private final ImmutableRoaringBitmap _docIds;
+ private final PeekableIntIterator _docIdIterator;
+ private final int _lastDoc;
+ private int _nextDocId;
+ private int _nextNonMatchingDocId;
+
+ public InvertedBitmapDocIdIterator(ImmutableRoaringBitmap docIds, int numDocs) {
+ _docIds = docIds;
+ _docIdIterator = docIds.getIntIterator();
+ _nextDocId = 0;
+
+ int currentDocIdFromChildIterator = _docIdIterator.next();
+ _nextNonMatchingDocId = currentDocIdFromChildIterator == Constants.EOF ? numDocs : currentDocIdFromChildIterator;
+ _lastDoc = numDocs - 1;
+ }
+
+ @Override
+ public int next() {
+ while (_nextDocId == _nextNonMatchingDocId && _docIdIterator.hasNext()) {
+ _nextDocId++;
+ int nextNonMatchingDocId = _docIdIterator.next();
+ _nextNonMatchingDocId = nextNonMatchingDocId == Constants.EOF ? _lastDoc : nextNonMatchingDocId;
+ }
+ if (_nextDocId >= _lastDoc) {
+ return Constants.EOF;
+ }
+ return _nextDocId++;
+ }
+
+ @Override
+ public int advance(int targetDocId) {
+ _nextDocId = targetDocId;
+ if (targetDocId > _nextNonMatchingDocId) {
+ _docIdIterator.advanceIfNeeded(targetDocId);
+ _nextNonMatchingDocId = _docIdIterator.hasNext() ? _docIdIterator.next() : _lastDoc;
+ }
+ return next();
+ }
+
+ @Override
+ public ImmutableRoaringBitmap getDocIds() {
+ return _docIds;
+ }
+
+ @Override
+ public boolean isInverted() {
+ return true;
+ }
+}
diff --git a/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/ScanBasedDocIdIterator.java b/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/ScanBasedDocIdIterator.java
index 1ed890c..cf3945f 100644
--- a/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/ScanBasedDocIdIterator.java
+++ b/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/ScanBasedDocIdIterator.java
@@ -40,6 +40,14 @@
MutableRoaringBitmap applyAnd(ImmutableRoaringBitmap docIds);
/**
+ * Applies ANDNOT operation to the given bitmap of document ids, returns a bitmap of the matching document ids.
+ */
+ default MutableRoaringBitmap applyAndNot(ImmutableRoaringBitmap docIds, int numDocs) {
+ // FIXME we're scanning anyway, so flipping a bitmap doesn't seem quite so bad, but this can be improved
+ return applyAnd(ImmutableRoaringBitmap.flip(docIds, 0L, numDocs));
+ }
+
+ /**
* Returns the number of entries (SV value contains one entry, MV value contains multiple entries) scanned during the
* iteration. This method should be called after the iteration is done.
*/
diff --git a/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/AndDocIdSet.java b/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/AndDocIdSet.java
index 8b43b7d..ae40037 100644
--- a/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/AndDocIdSet.java
+++ b/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/AndDocIdSet.java
@@ -27,6 +27,7 @@
import org.apache.pinot.core.common.BlockDocIdIterator;
import org.apache.pinot.core.operator.dociditerators.AndDocIdIterator;
import org.apache.pinot.core.operator.dociditerators.BitmapBasedDocIdIterator;
+import org.apache.pinot.core.operator.dociditerators.InvertedBitmapDocIdIterator;
import org.apache.pinot.core.operator.dociditerators.RangelessBitmapDocIdIterator;
import org.apache.pinot.core.operator.dociditerators.ScanBasedDocIdIterator;
import org.apache.pinot.core.operator.dociditerators.SortedDocIdIterator;
@@ -56,11 +57,13 @@
public final class AndDocIdSet implements FilterBlockDocIdSet {
private final List<FilterBlockDocIdSet> _docIdSets;
private final boolean _cardinalityBasedRankingForScan;
+ private final int _numDocs;
- public AndDocIdSet(List<FilterBlockDocIdSet> docIdSets, Map<String, String> queryOptions) {
+ public AndDocIdSet(List<FilterBlockDocIdSet> docIdSets, Map<String, String> queryOptions, int numDocs) {
_docIdSets = docIdSets;
_cardinalityBasedRankingForScan =
!MapUtils.isEmpty(queryOptions) && QueryOptionsUtils.isAndScanReorderingEnabled(queryOptions);
+ _numDocs = numDocs;
}
@Override
@@ -88,8 +91,16 @@
}
// evaluate the bitmaps in the order of the lowest matching num docIds comes first, so that we minimize the number
- // of containers (range) for comparison from the beginning, as will minimize the effort of bitmap AND application
- bitmapBasedDocIdIterators.sort(Comparator.comparing(x -> x.getDocIds().getCardinality()));
+ // of containers (range) for comparison from the beginning, as will minimize the effort of bitmap AND application.
+ // We also put inverted iterators last to avoid flipping them wherever possible, but if we have to flip one, we
+ // want it to be the largest one
+ bitmapBasedDocIdIterators.sort(Comparator.comparing(x -> {
+ int cardinality = x.getDocIds().getCardinality();
+ if (x.isInverted()) {
+ return Integer.MAX_VALUE - cardinality;
+ }
+ return Integer.MIN_VALUE + cardinality;
+ }));
// Evaluate the scan based operator with the highest cardinality coming first, this potentially reduce the range of
// scanning from the beginning. Automatically place N/A cardinality column (negative infinity) to the back as we
@@ -113,6 +124,7 @@
// BlockDocIdIterator, directly return the merged RangelessBitmapDocIdIterator; otherwise, construct and return
// an AndDocIdIterator with the merged RangelessBitmapDocIdIterator and the remaining BlockDocIdIterators.
+ boolean inverted = false;
ImmutableRoaringBitmap docIds;
if (numSortedDocIdIterators > 0) {
List<IntPair> docIdRanges;
@@ -132,29 +144,52 @@
mutableDocIds.add(docIdRange.getLeft(), docIdRange.getRight() + 1L);
}
for (BitmapBasedDocIdIterator bitmapBasedDocIdIterator : bitmapBasedDocIdIterators) {
- mutableDocIds.and(bitmapBasedDocIdIterator.getDocIds());
+ if (bitmapBasedDocIdIterator.isInverted()) {
+ mutableDocIds.andNot(bitmapBasedDocIdIterator.getDocIds());
+ } else {
+ mutableDocIds.and(bitmapBasedDocIdIterator.getDocIds());
+ }
}
docIds = mutableDocIds;
} else {
if (numBitmapBasedDocIdIterators == 1) {
- docIds = bitmapBasedDocIdIterators.get(0).getDocIds();
+ BitmapBasedDocIdIterator bitmapBasedDocIdIterator = bitmapBasedDocIdIterators.get(0);
+ docIds = bitmapBasedDocIdIterator.getDocIds();
+ inverted = bitmapBasedDocIdIterator.isInverted();
} else {
- MutableRoaringBitmap mutableDocIds = bitmapBasedDocIdIterators.get(0).getDocIds().toMutableRoaringBitmap();
+ BitmapBasedDocIdIterator firstBitmapBasedDocIdIterator = bitmapBasedDocIdIterators.get(0);
+ MutableRoaringBitmap mutableDocIds = firstBitmapBasedDocIdIterator.getDocIds().toMutableRoaringBitmap();
+ if (firstBitmapBasedDocIdIterator.isInverted()) {
+ // because of the sort order, this means all the filters are inverted, so this may be avoidable,
+ // but it's also the largest bitmap so we should only create a small bitmap
+ mutableDocIds.flip(0L, _numDocs);
+ }
for (int i = 1; i < numBitmapBasedDocIdIterators; i++) {
- mutableDocIds.and(bitmapBasedDocIdIterators.get(i).getDocIds());
+ BitmapBasedDocIdIterator bitmapBasedDocIdIterator = bitmapBasedDocIdIterators.get(i);
+ if (bitmapBasedDocIdIterator.isInverted()) {
+ mutableDocIds.andNot(bitmapBasedDocIdIterators.get(i).getDocIds());
+ } else {
+ mutableDocIds.and(bitmapBasedDocIdIterators.get(i).getDocIds());
+ }
}
docIds = mutableDocIds;
}
}
for (ScanBasedDocIdIterator scanBasedDocIdIterator : scanBasedDocIdIterators) {
- docIds = scanBasedDocIdIterator.applyAnd(docIds);
+ if (inverted) {
+ docIds = scanBasedDocIdIterator.applyAndNot(docIds, _numDocs);
+ inverted = false;
+ } else {
+ docIds = scanBasedDocIdIterator.applyAnd(docIds);
+ }
}
- RangelessBitmapDocIdIterator rangelessBitmapDocIdIterator = new RangelessBitmapDocIdIterator(docIds);
+ BitmapBasedDocIdIterator lastBitmapDocIdIterator =
+ inverted ? new InvertedBitmapDocIdIterator(docIds, _numDocs) : new RangelessBitmapDocIdIterator(docIds);
if (numRemainingDocIdIterators == 0) {
- return rangelessBitmapDocIdIterator;
+ return lastBitmapDocIdIterator;
} else {
BlockDocIdIterator[] docIdIterators = new BlockDocIdIterator[numRemainingDocIdIterators + 1];
- docIdIterators[0] = rangelessBitmapDocIdIterator;
+ docIdIterators[0] = lastBitmapDocIdIterator;
for (int i = 0; i < numRemainingDocIdIterators; i++) {
docIdIterators[i + 1] = remainingDocIdIterators.get(i);
}
diff --git a/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/BitmapDocIdSet.java b/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/BitmapDocIdSet.java
index a69ac00..fee9d0e 100644
--- a/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/BitmapDocIdSet.java
+++ b/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/BitmapDocIdSet.java
@@ -18,15 +18,21 @@
*/
package org.apache.pinot.core.operator.docidsets;
+import org.apache.pinot.core.operator.dociditerators.BitmapBasedDocIdIterator;
import org.apache.pinot.core.operator.dociditerators.BitmapDocIdIterator;
+import org.apache.pinot.core.operator.dociditerators.InvertedBitmapDocIdIterator;
import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
public class BitmapDocIdSet implements FilterBlockDocIdSet {
- private final BitmapDocIdIterator _iterator;
+ private final BitmapBasedDocIdIterator _iterator;
public BitmapDocIdSet(ImmutableRoaringBitmap docIds, int numDocs) {
- _iterator = new BitmapDocIdIterator(docIds, numDocs);
+ this(docIds, numDocs, false);
+ }
+
+ public BitmapDocIdSet(ImmutableRoaringBitmap docIds, int numDocs, boolean inverted) {
+ _iterator = inverted ? new InvertedBitmapDocIdIterator(docIds, numDocs) : new BitmapDocIdIterator(docIds, numDocs);
}
public BitmapDocIdSet(BitmapDocIdIterator iterator) {
@@ -34,7 +40,7 @@
}
@Override
- public BitmapDocIdIterator iterator() {
+ public BitmapBasedDocIdIterator iterator() {
return _iterator;
}
diff --git a/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/NotDocIdSet.java b/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/NotDocIdSet.java
index 1fe6462..0c5b2a1 100644
--- a/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/NotDocIdSet.java
+++ b/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/NotDocIdSet.java
@@ -33,6 +33,7 @@
@Override
public BlockDocIdIterator iterator() {
+ // FIXME if the child set is an inverted bitmap, we could just invert it again
return new NotDocIdIterator(_childDocIdSet.iterator(), _numDocs);
}
diff --git a/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/OrDocIdSet.java b/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/OrDocIdSet.java
index 6ead802..fa60f9a 100644
--- a/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/OrDocIdSet.java
+++ b/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/OrDocIdSet.java
@@ -88,7 +88,11 @@
}
}
for (BitmapBasedDocIdIterator bitmapBasedDocIdIterator : bitmapBasedDocIdIterators) {
- docIds.or(bitmapBasedDocIdIterator.getDocIds());
+ if (bitmapBasedDocIdIterator.isInverted()) {
+ docIds.orNot(bitmapBasedDocIdIterator.getDocIds(), _numDocs);
+ } else {
+ docIds.or(bitmapBasedDocIdIterator.getDocIds());
+ }
}
BitmapDocIdIterator bitmapDocIdIterator = new BitmapDocIdIterator(docIds, _numDocs);
int numRemainingDocIdIterators = remainingDocIdIterators.size();
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 de2062f..3eb5265 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
@@ -36,13 +36,16 @@
private final List<BaseFilterOperator> _filterOperators;
private final Map<String, String> _queryOptions;
- public AndFilterOperator(List<BaseFilterOperator> filterOperators, Map<String, String> queryOptions) {
+ private final int _numDocs;
+
+ public AndFilterOperator(List<BaseFilterOperator> filterOperators, Map<String, String> queryOptions, int numDocs) {
_filterOperators = filterOperators;
_queryOptions = queryOptions;
+ _numDocs = numDocs;
}
- public AndFilterOperator(List<BaseFilterOperator> filterOperators) {
- this(filterOperators, null);
+ public AndFilterOperator(List<BaseFilterOperator> filterOperators, int numDocs) {
+ this(filterOperators, null, numDocs);
}
@Override
@@ -52,7 +55,7 @@
for (BaseFilterOperator filterOperator : _filterOperators) {
filterBlockDocIdSets.add(filterOperator.nextBlock().getBlockDocIdSet());
}
- return new FilterBlock(new AndDocIdSet(filterBlockDocIdSets, _queryOptions));
+ return new FilterBlock(new AndDocIdSet(filterBlockDocIdSets, _queryOptions, _numDocs));
}
@Override
@@ -77,7 +80,6 @@
return BufferFastAggregation.andCardinality(bitmaps);
}
-
@Override
public List<Operator> getChildOperators() {
return new ArrayList<>(_filterOperators);
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 bd8fb41..5abcafe 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
@@ -65,11 +65,7 @@
@Override
protected FilterBlock getNextBlock() {
if (_docIds != null) {
- if (_exclusive) {
- return new FilterBlock(new BitmapDocIdSet(ImmutableRoaringBitmap.flip(_docIds, 0L, _numDocs), _numDocs));
- } else {
- return new FilterBlock(new BitmapDocIdSet(_docIds, _numDocs));
- }
+ return new FilterBlock(new BitmapDocIdSet(_docIds, _numDocs, _exclusive));
}
int[] dictIds = _exclusive ? _predicateEvaluator.getNonMatchingDictIds() : _predicateEvaluator.getMatchingDictIds();
@@ -79,33 +75,20 @@
}
if (numDictIds == 1) {
ImmutableRoaringBitmap docIds = _invertedIndexReader.getDocIds(dictIds[0]);
- if (_exclusive) {
- if (docIds instanceof MutableRoaringBitmap) {
- MutableRoaringBitmap mutableRoaringBitmap = (MutableRoaringBitmap) docIds;
- mutableRoaringBitmap.flip(0L, _numDocs);
- return new FilterBlock(new BitmapDocIdSet(mutableRoaringBitmap, _numDocs));
- } else {
- return new FilterBlock(new BitmapDocIdSet(ImmutableRoaringBitmap.flip(docIds, 0L, _numDocs), _numDocs));
- }
- } else {
- return new FilterBlock(new BitmapDocIdSet(docIds, _numDocs));
- }
+ return new FilterBlock(new BitmapDocIdSet(docIds, _numDocs, _exclusive));
} else {
ImmutableRoaringBitmap[] bitmaps = new ImmutableRoaringBitmap[numDictIds];
for (int i = 0; i < numDictIds; i++) {
bitmaps[i] = _invertedIndexReader.getDocIds(dictIds[i]);
}
MutableRoaringBitmap docIds = ImmutableRoaringBitmap.or(bitmaps);
- if (_exclusive) {
- docIds.flip(0L, _numDocs);
- }
InvocationRecording recording = Tracing.activeRecording();
if (recording.isEnabled()) {
recording.setColumnName(_predicateEvaluator.getPredicate().getLhs().getIdentifier());
recording.setNumDocsMatchingAfterFilter(docIds.getCardinality());
recording.setFilter(FilterType.INDEX, String.valueOf(_predicateEvaluator.getPredicateType()));
}
- return new FilterBlock(new BitmapDocIdSet(docIds, _numDocs));
+ return new FilterBlock(new BitmapDocIdSet(docIds, _numDocs, _exclusive));
}
}
diff --git a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/CombinedFilterOperator.java b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/CombinedFilterOperator.java
index 89b856d..0dab2b7 100644
--- a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/CombinedFilterOperator.java
+++ b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/CombinedFilterOperator.java
@@ -38,12 +38,14 @@
private final BaseFilterOperator _mainFilterOperator;
private final BaseFilterOperator _subFilterOperator;
private final Map<String, String> _queryOptions;
+ private final int _numDocs;
public CombinedFilterOperator(BaseFilterOperator mainFilterOperator, BaseFilterOperator subFilterOperator,
- Map<String, String> queryOptions) {
+ Map<String, String> queryOptions, int numDocs) {
_mainFilterOperator = mainFilterOperator;
_subFilterOperator = subFilterOperator;
_queryOptions = queryOptions;
+ _numDocs = numDocs;
}
@Override
@@ -61,6 +63,7 @@
Tracing.activeRecording().setNumChildren(2);
FilterBlockDocIdSet mainFilterDocIdSet = _mainFilterOperator.nextBlock().getNonScanFilterBLockDocIdSet();
FilterBlockDocIdSet subFilterDocIdSet = _subFilterOperator.nextBlock().getBlockDocIdSet();
- return new FilterBlock(new AndDocIdSet(Arrays.asList(mainFilterDocIdSet, subFilterDocIdSet), _queryOptions));
+ return new FilterBlock(
+ new AndDocIdSet(Arrays.asList(mainFilterDocIdSet, subFilterDocIdSet), _queryOptions, _numDocs));
}
}
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 c343dce..9328bf7 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
@@ -107,7 +107,7 @@
} else {
// Return the AND filter operator with re-ordered child filter operators
FilterOperatorUtils.reorderAndFilterChildOperators(queryContext, childFilterOperators);
- return new AndFilterOperator(childFilterOperators, queryContext.getQueryOptions());
+ return new AndFilterOperator(childFilterOperators, queryContext.getQueryOptions(), numDocs);
}
}
diff --git a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/ScanBasedFilterOperator.java b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/ScanBasedFilterOperator.java
index 89305d2..60f1916 100644
--- a/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/ScanBasedFilterOperator.java
+++ b/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/ScanBasedFilterOperator.java
@@ -59,7 +59,6 @@
}
}
-
@Override
public List<Operator> getChildOperators() {
return Collections.emptyList();
diff --git a/pinot-core/src/main/java/org/apache/pinot/core/plan/AggregationPlanNode.java b/pinot-core/src/main/java/org/apache/pinot/core/plan/AggregationPlanNode.java
index 1489118..181a4e2 100644
--- a/pinot-core/src/main/java/org/apache/pinot/core/plan/AggregationPlanNode.java
+++ b/pinot-core/src/main/java/org/apache/pinot/core/plan/AggregationPlanNode.java
@@ -90,7 +90,7 @@
List<Pair<AggregationFunction[], TransformOperator>> aggToTransformOpList =
AggregationFunctionUtils.buildFilteredAggTransformPairs(_indexSegment, _queryContext,
- filterOperatorPair.getRight(), transformOperator, null);
+ filterOperatorPair.getRight(), transformOperator, null, numTotalDocs);
return new FilteredAggregationOperator(_queryContext.getAggregationFunctions(), aggToTransformOpList, numTotalDocs);
}
diff --git a/pinot-core/src/main/java/org/apache/pinot/core/plan/GroupByPlanNode.java b/pinot-core/src/main/java/org/apache/pinot/core/plan/GroupByPlanNode.java
index 99fdec9..33f9212 100644
--- a/pinot-core/src/main/java/org/apache/pinot/core/plan/GroupByPlanNode.java
+++ b/pinot-core/src/main/java/org/apache/pinot/core/plan/GroupByPlanNode.java
@@ -76,7 +76,7 @@
List<Pair<AggregationFunction[], TransformOperator>> aggToTransformOpList =
AggregationFunctionUtils.buildFilteredAggTransformPairs(_indexSegment, _queryContext,
- filterOperatorPair.getRight(), transformOperator, groupByExpressions);
+ filterOperatorPair.getRight(), transformOperator, groupByExpressions, numTotalDocs);
return new FilteredGroupByOperator(_queryContext.getAggregationFunctions(), aggToTransformOpList,
_queryContext.getGroupByExpressions().toArray(new ExpressionContext[0]), numTotalDocs, _queryContext);
}
diff --git a/pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/function/AggregationFunctionUtils.java b/pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/function/AggregationFunctionUtils.java
index 0dcecb0..9083078 100644
--- a/pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/function/AggregationFunctionUtils.java
+++ b/pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/function/AggregationFunctionUtils.java
@@ -211,7 +211,7 @@
*/
public static List<Pair<AggregationFunction[], TransformOperator>> buildFilteredAggTransformPairs(
IndexSegment indexSegment, QueryContext queryContext, BaseFilterOperator mainPredicateFilterOperator,
- TransformOperator mainTransformOperator, @Nullable ExpressionContext[] groupByExpressions) {
+ TransformOperator mainTransformOperator, @Nullable ExpressionContext[] groupByExpressions, int numDocs) {
Map<FilterContext, Pair<List<AggregationFunction>, TransformOperator>> filterContextToAggFuncsMap = new HashMap<>();
List<AggregationFunction> nonFilteredAggregationFunctions = new ArrayList<>();
List<Pair<AggregationFunction, FilterContext>> aggregationFunctions =
@@ -232,7 +232,7 @@
buildFilterOperator(indexSegment, queryContext, currentFilterExpression);
BaseFilterOperator wrappedFilterOperator =
new CombinedFilterOperator(mainPredicateFilterOperator, filterPlanOpPair.getRight(),
- queryContext.getQueryOptions());
+ queryContext.getQueryOptions(), numDocs);
TransformOperator newTransformOperator =
buildTransformOperatorForFilteredAggregates(indexSegment, queryContext, wrappedFilterOperator,
groupByExpressions);
diff --git a/pinot-core/src/test/java/org/apache/pinot/core/operator/dociditerators/AndDocIdIteratorTest.java b/pinot-core/src/test/java/org/apache/pinot/core/operator/dociditerators/AndDocIdIteratorTest.java
index c556114..eb80820 100644
--- a/pinot-core/src/test/java/org/apache/pinot/core/operator/dociditerators/AndDocIdIteratorTest.java
+++ b/pinot-core/src/test/java/org/apache/pinot/core/operator/dociditerators/AndDocIdIteratorTest.java
@@ -18,8 +18,8 @@
*/
package org.apache.pinot.core.operator.dociditerators;
-import org.apache.pinot.core.common.BlockDocIdIterator;
import org.apache.pinot.segment.spi.Constants;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
import org.roaringbitmap.buffer.MutableRoaringBitmap;
import org.testng.annotations.Test;
@@ -41,10 +41,9 @@
bitmap2.add(docIds2);
MutableRoaringBitmap bitmap3 = new MutableRoaringBitmap();
bitmap3.add(docIds3);
- AndDocIdIterator andDocIdIterator = new AndDocIdIterator(new BlockDocIdIterator[]{
- new RangelessBitmapDocIdIterator(bitmap1), new RangelessBitmapDocIdIterator(bitmap2),
- new RangelessBitmapDocIdIterator(bitmap3)
- });
+ AndDocIdIterator andDocIdIterator =
+ new AndDocIdIterator(new RangelessBitmapDocIdIterator(bitmap1), new RangelessBitmapDocIdIterator(bitmap2),
+ new RangelessBitmapDocIdIterator(bitmap3));
assertEquals(andDocIdIterator.next(), 2);
assertEquals(andDocIdIterator.next(), 7);
@@ -53,4 +52,49 @@
assertEquals(andDocIdIterator.next(), 20);
assertEquals(andDocIdIterator.next(), Constants.EOF);
}
+
+ @Test
+ public void testAndDocIdIteratorWithInvertedChildren() {
+ int numDocs = 20;
+ // not = [4, 6, 8, 11, 14, 17, 19]
+ int[] docIds1 = new int[]{0, 1, 2, 3, 5, 7, 10, 12, 13, 15, 16, 18, 20};
+ // not = [0, 3, 8, 10, 14, 17, 18]
+ int[] docIds2 = new int[]{1, 2, 4, 5, 6, 7, 9, 11, 12, 13, 15, 16, 19, 20};
+ // not = [1, 5, 6, 9, 12, 14, 17, 18]
+ int[] docIds3 = new int[]{0, 2, 3, 4, 7, 8, 10, 11, 13, 15, 16, 19, 20};
+ int[] expected = new int[]{14, 17};
+
+ ImmutableRoaringBitmap bitmap1 = ImmutableRoaringBitmap.bitmapOf(docIds1);
+ ImmutableRoaringBitmap bitmap2 = ImmutableRoaringBitmap.bitmapOf(docIds2);
+ ImmutableRoaringBitmap bitmap3 = ImmutableRoaringBitmap.bitmapOf(docIds3);
+ AndDocIdIterator andDocIdIterator = new AndDocIdIterator(new InvertedBitmapDocIdIterator(bitmap1, numDocs),
+ new InvertedBitmapDocIdIterator(bitmap2, numDocs), new InvertedBitmapDocIdIterator(bitmap3, numDocs));
+
+ for (int docId : expected) {
+ assertEquals(andDocIdIterator.next(), docId);
+ }
+ assertEquals(andDocIdIterator.next(), Constants.EOF);
+ }
+
+ @Test
+ public void testAndDocIdIteratorWithMixedChildren() {
+ int numDocs = 20;
+ int[] docIds1 = new int[]{0, 1, 2, 3, 5, 7, 10, 12, 13, 14, 15, 16, 17, 18, 20};
+ // not = [0, 3, 8, 10, 14, 17, 18]
+ int[] docIds2 = new int[]{1, 2, 4, 5, 6, 7, 9, 11, 12, 13, 15, 16, 19, 20};
+ // not = [1, 5, 6, 9, 12, 14, 17, 18]
+ int[] docIds3 = new int[]{0, 2, 3, 4, 7, 8, 10, 11, 13, 15, 16, 19, 20};
+ int[] expected = new int[]{14, 17, 18};
+
+ ImmutableRoaringBitmap bitmap1 = ImmutableRoaringBitmap.bitmapOf(docIds1);
+ ImmutableRoaringBitmap bitmap2 = ImmutableRoaringBitmap.bitmapOf(docIds2);
+ ImmutableRoaringBitmap bitmap3 = ImmutableRoaringBitmap.bitmapOf(docIds3);
+ AndDocIdIterator andDocIdIterator = new AndDocIdIterator(new BitmapDocIdIterator(bitmap1, numDocs),
+ new InvertedBitmapDocIdIterator(bitmap2, numDocs), new InvertedBitmapDocIdIterator(bitmap3, numDocs));
+
+ for (int docId : expected) {
+ assertEquals(andDocIdIterator.next(), docId);
+ }
+ assertEquals(andDocIdIterator.next(), Constants.EOF);
+ }
}
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 6481ae2..c639ae3 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
@@ -22,6 +22,7 @@
import java.util.List;
import org.apache.pinot.core.common.BlockDocIdIterator;
import org.apache.pinot.segment.spi.Constants;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
import org.roaringbitmap.buffer.MutableRoaringBitmap;
import org.testng.Assert;
import org.testng.annotations.Test;
@@ -37,7 +38,7 @@
List<BaseFilterOperator> operators = new ArrayList<>();
operators.add(new TestFilterOperator(docIds1));
operators.add(new TestFilterOperator(docIds2));
- AndFilterOperator andOperator = new AndFilterOperator(operators);
+ AndFilterOperator andOperator = new AndFilterOperator(operators, 40);
BlockDocIdIterator iterator = andOperator.nextBlock().getBlockDocIdSet().iterator();
Assert.assertEquals(iterator.next(), 3);
@@ -55,7 +56,7 @@
operators.add(new TestFilterOperator(docIds1));
operators.add(new TestFilterOperator(docIds2));
operators.add(new TestFilterOperator(docIds3));
- AndFilterOperator andOperator = new AndFilterOperator(operators);
+ AndFilterOperator andOperator = new AndFilterOperator(operators, 40);
BlockDocIdIterator iterator = andOperator.nextBlock().getBlockDocIdSet().iterator();
Assert.assertEquals(iterator.next(), 3);
@@ -72,12 +73,12 @@
List<BaseFilterOperator> childOperators = new ArrayList<>();
childOperators.add(new TestFilterOperator(docIds1));
childOperators.add(new TestFilterOperator(docIds2));
- AndFilterOperator childAndOperator = new AndFilterOperator(childOperators);
+ AndFilterOperator childAndOperator = new AndFilterOperator(childOperators, 40);
List<BaseFilterOperator> operators = new ArrayList<>();
operators.add(childAndOperator);
operators.add(new TestFilterOperator(docIds3));
- AndFilterOperator andOperator = new AndFilterOperator(operators);
+ AndFilterOperator andOperator = new AndFilterOperator(operators, 40);
BlockDocIdIterator iterator = andOperator.nextBlock().getBlockDocIdSet().iterator();
Assert.assertEquals(iterator.next(), 3);
@@ -112,8 +113,8 @@
numDocs));
}
- AndFilterOperator andFilterOperator1 = new AndFilterOperator(childOperators1);
- AndFilterOperator andFilterOperator2 = new AndFilterOperator(childOperators2);
+ AndFilterOperator andFilterOperator1 = new AndFilterOperator(childOperators1, numDocs);
+ AndFilterOperator andFilterOperator2 = new AndFilterOperator(childOperators2, numDocs);
BlockDocIdIterator iterator1 = andFilterOperator1.getNextBlock().getBlockDocIdSet().iterator();
BlockDocIdIterator iterator2 = andFilterOperator2.getNextBlock().getBlockDocIdSet().iterator();
Assert.assertEquals(iterator1.next(), 0);
@@ -145,7 +146,7 @@
List<BaseFilterOperator> operators = new ArrayList<>();
operators.add(childOrOperator);
operators.add(new TestFilterOperator(docIds1));
- AndFilterOperator andOperator = new AndFilterOperator(operators);
+ AndFilterOperator andOperator = new AndFilterOperator(operators, 40);
BlockDocIdIterator iterator = andOperator.nextBlock().getBlockDocIdSet().iterator();
Assert.assertEquals(iterator.next(), 2);
@@ -154,4 +155,72 @@
Assert.assertEquals(iterator.next(), 28);
Assert.assertEquals(iterator.next(), Constants.EOF);
}
+
+ @Test
+ public void testComplexOrWithNot() {
+ int[] include1 = new int[]{2, 3, 6, 10, 15, 16, 28};
+ int[] include2 = new int[]{3, 6, 8, 20, 28};
+ int[] exclude1 = new int[]{1, 2, 3, 6, 30}; // negation = {4, 5, 7, ... 29}
+ int[] expected = new int[]{3, 6, 10, 15, 16, 28};
+
+ List<BaseFilterOperator> childOperators = new ArrayList<>();
+ childOperators.add(new BitmapBasedFilterOperator(ImmutableRoaringBitmap.bitmapOf(exclude1), true, 40));
+ childOperators.add(new BitmapBasedFilterOperator(ImmutableRoaringBitmap.bitmapOf(include2), false, 40));
+ OrFilterOperator childOrOperator = new OrFilterOperator(childOperators, 40);
+
+ List<BaseFilterOperator> operators = new ArrayList<>();
+ operators.add(childOrOperator);
+ operators.add(new TestFilterOperator(include1));
+ AndFilterOperator andOperator = new AndFilterOperator(operators, 40);
+
+ BlockDocIdIterator iterator = andOperator.nextBlock().getBlockDocIdSet().iterator();
+ for (int j : expected) {
+ Assert.assertEquals(iterator.next(), j);
+ }
+ Assert.assertEquals(iterator.next(), Constants.EOF);
+ }
+
+ @Test
+ public void testComplexAndWithNot() {
+ int[] include1 = new int[]{2, 3, 6, 10, 15, 16, 28};
+ int[] include2 = new int[]{3, 6, 8, 20, 28};
+ int[] exclude1 = new int[]{1, 2, 3, 6, 30}; // negation = {4, 5, 7, ... 29}
+ int[] expected = new int[]{28};
+
+ List<BaseFilterOperator> operators = new ArrayList<>();
+ operators.add(new BitmapBasedFilterOperator(ImmutableRoaringBitmap.bitmapOf(exclude1), true, 40));
+ operators.add(new BitmapBasedFilterOperator(ImmutableRoaringBitmap.bitmapOf(include2), false, 40));
+ operators.add(new TestFilterOperator(include1));
+ AndFilterOperator andOperator = new AndFilterOperator(operators, 40);
+
+ BlockDocIdIterator iterator = andOperator.nextBlock().getBlockDocIdSet().iterator();
+ for (int j : expected) {
+ Assert.assertEquals(iterator.next(), j);
+ }
+ Assert.assertEquals(iterator.next(), Constants.EOF);
+ }
+
+ @Test
+ public void testAndWithNot() {
+ int[] include1 = new int[]{2, 3, 6, 10, 15, 16, 28};
+ int[] include2 = new int[]{3, 6, 8, 20, 28};
+ int[] exclude1 = new int[]{1, 2, 3, 6, 30}; // negation = {4, 5, 7, ... 29}
+ int[] expected = new int[]{28};
+
+ List<BaseFilterOperator> childOperators = new ArrayList<>();
+ childOperators.add(new BitmapBasedFilterOperator(ImmutableRoaringBitmap.bitmapOf(exclude1), true, 40));
+ childOperators.add(new BitmapBasedFilterOperator(ImmutableRoaringBitmap.bitmapOf(include2), false, 40));
+ AndFilterOperator childAndOperator = new AndFilterOperator(childOperators, 40);
+
+ List<BaseFilterOperator> operators = new ArrayList<>();
+ operators.add(childAndOperator);
+ operators.add(new TestFilterOperator(include1));
+ AndFilterOperator andOperator = new AndFilterOperator(operators, 40);
+
+ BlockDocIdIterator iterator = andOperator.nextBlock().getBlockDocIdSet().iterator();
+ for (int j : expected) {
+ Assert.assertEquals(iterator.next(), j);
+ }
+ Assert.assertEquals(iterator.next(), Constants.EOF);
+ }
}
diff --git a/pinot-perf/src/main/java/org/apache/pinot/perf/BenchmarkAndDocIdIterator.java b/pinot-perf/src/main/java/org/apache/pinot/perf/BenchmarkAndDocIdIterator.java
index 6982dc5..7979f42 100644
--- a/pinot-perf/src/main/java/org/apache/pinot/perf/BenchmarkAndDocIdIterator.java
+++ b/pinot-perf/src/main/java/org/apache/pinot/perf/BenchmarkAndDocIdIterator.java
@@ -61,7 +61,8 @@
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public void benchAndFilterOperator(MyState myState, Blackhole bh) {
for (int i = 0; i < 100; i++) {
- bh.consume(new AndFilterOperator(myState._childOperators).nextBlock().getBlockDocIdSet().iterator());
+ bh.consume(new AndFilterOperator(myState._childOperators, NUM_DOCS).nextBlock()
+ .getBlockDocIdSet().iterator());
}
}
@@ -70,7 +71,8 @@
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public void benchAndFilterOperatorDegenerate(MyState myState, Blackhole bh) {
for (int i = 0; i < 100; i++) {
- bh.consume(new AndFilterOperator(myState._childOperatorsNoOrdering).nextBlock().getBlockDocIdSet().iterator());
+ bh.consume(new AndFilterOperator(myState._childOperatorsNoOrdering, NUM_DOCS).nextBlock()
+ .getBlockDocIdSet().iterator());
}
}
