You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pinot.apache.org by ja...@apache.org on 2023/07/20 17:48:35 UTC
[pinot] branch master updated: Separate BitmapBasedFilterOperator into two filter operators. (#11137)
This is an automated email from the ASF dual-hosted git repository.
jackie 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 ead75229af Separate BitmapBasedFilterOperator into two filter operators. (#11137)
ead75229af is described below
commit ead75229af648e260c68ad991fb80a6f81af5712
Author: Shen Yu <sh...@startree.ai>
AuthorDate: Thu Jul 20 10:48:29 2023 -0700
Separate BitmapBasedFilterOperator into two filter operators. (#11137)
---
.../operator/filter/BitmapBasedFilterOperator.java | 122 ++-------------------
.../core/operator/filter/FilterOperatorUtils.java | 4 +-
...rator.java => InvertedIndexFilterOperator.java} | 101 ++++++-----------
3 files changed, 45 insertions(+), 182 deletions(-)
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 bd8fb41ce1..91cb33879b 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
@@ -20,43 +20,20 @@ package org.apache.pinot.core.operator.filter;
import java.util.Collections;
import java.util.List;
-import org.apache.pinot.common.request.context.predicate.Predicate;
import org.apache.pinot.core.common.Operator;
-import org.apache.pinot.core.operator.blocks.EmptyFilterBlock;
import org.apache.pinot.core.operator.blocks.FilterBlock;
import org.apache.pinot.core.operator.docidsets.BitmapDocIdSet;
-import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
-import org.apache.pinot.segment.spi.datasource.DataSource;
-import org.apache.pinot.segment.spi.index.reader.InvertedIndexReader;
-import org.apache.pinot.spi.trace.FilterType;
-import org.apache.pinot.spi.trace.InvocationRecording;
-import org.apache.pinot.spi.trace.Tracing;
import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
-import org.roaringbitmap.buffer.MutableRoaringBitmap;
-@SuppressWarnings("rawtypes")
public class BitmapBasedFilterOperator extends BaseFilterOperator {
- private static final String EXPLAIN_NAME = "FILTER_INVERTED_INDEX";
+ private static final String EXPLAIN_NAME = "FILTER_BITMAP";
- private final PredicateEvaluator _predicateEvaluator;
- private final InvertedIndexReader<ImmutableRoaringBitmap> _invertedIndexReader;
private final ImmutableRoaringBitmap _docIds;
private final boolean _exclusive;
private final int _numDocs;
- @SuppressWarnings("unchecked")
- BitmapBasedFilterOperator(PredicateEvaluator predicateEvaluator, DataSource dataSource, int numDocs) {
- _predicateEvaluator = predicateEvaluator;
- _invertedIndexReader = (InvertedIndexReader<ImmutableRoaringBitmap>) dataSource.getInvertedIndex();
- _docIds = null;
- _exclusive = predicateEvaluator.isExclusive();
- _numDocs = numDocs;
- }
-
public BitmapBasedFilterOperator(ImmutableRoaringBitmap docIds, boolean exclusive, int numDocs) {
- _predicateEvaluator = null;
- _invertedIndexReader = null;
_docIds = docIds;
_exclusive = exclusive;
_numDocs = numDocs;
@@ -64,48 +41,10 @@ public class BitmapBasedFilterOperator extends BaseFilterOperator {
@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));
- }
- }
-
- int[] dictIds = _exclusive ? _predicateEvaluator.getNonMatchingDictIds() : _predicateEvaluator.getMatchingDictIds();
- int numDictIds = dictIds.length;
- if (numDictIds == 0) {
- return EmptyFilterBlock.getInstance();
- }
- 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));
- }
+ if (_exclusive) {
+ return new FilterBlock(new BitmapDocIdSet(ImmutableRoaringBitmap.flip(_docIds, 0L, _numDocs), _numDocs));
} 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));
}
}
@@ -116,36 +55,7 @@ public class BitmapBasedFilterOperator extends BaseFilterOperator {
@Override
public int getNumMatchingDocs() {
- int count = 0;
- if (_docIds == null) {
- int[] dictIds = _exclusive
- ? _predicateEvaluator.getNonMatchingDictIds()
- : _predicateEvaluator.getMatchingDictIds();
- switch (dictIds.length) {
- case 0:
- break;
- case 1: {
- count = _invertedIndexReader.getDocIds(dictIds[0]).getCardinality();
- break;
- }
- case 2: {
- count = ImmutableRoaringBitmap.orCardinality(_invertedIndexReader.getDocIds(dictIds[0]),
- _invertedIndexReader.getDocIds(dictIds[1]));
- break;
- }
- default: {
- // this could be optimised if the bitmaps are known to be disjoint (as in a single value bitmap index)
- MutableRoaringBitmap bitmap = new MutableRoaringBitmap();
- for (int dictId : dictIds) {
- bitmap.or(_invertedIndexReader.getDocIds(dictId));
- }
- count = bitmap.getCardinality();
- break;
- }
- }
- } else {
- count = _docIds.getCardinality();
- }
+ int count = _docIds.getCardinality();
return _exclusive ? _numDocs - count : count;
}
@@ -156,34 +66,18 @@ public class BitmapBasedFilterOperator extends BaseFilterOperator {
@Override
public BitmapCollection getBitmaps() {
- if (_docIds == null) {
- int[] dictIds = _exclusive
- ? _predicateEvaluator.getNonMatchingDictIds()
- : _predicateEvaluator.getMatchingDictIds();
- ImmutableRoaringBitmap[] bitmaps = new ImmutableRoaringBitmap[dictIds.length];
- for (int i = 0; i < dictIds.length; i++) {
- bitmaps[i] = _invertedIndexReader.getDocIds(dictIds[i]);
- }
- return new BitmapCollection(_numDocs, _exclusive, bitmaps);
- } else {
- return new BitmapCollection(_numDocs, _exclusive, _docIds);
- }
+ return new BitmapCollection(_numDocs, _exclusive, _docIds);
}
@Override
+ @SuppressWarnings("rawtypes")
public List<Operator> getChildOperators() {
return Collections.emptyList();
}
@Override
public String toExplainString() {
- StringBuilder stringBuilder = new StringBuilder(EXPLAIN_NAME).append("(indexLookUp:inverted_index");
- Predicate predicate = _predicateEvaluator != null ? _predicateEvaluator.getPredicate() : null;
- if (predicate != null) {
- stringBuilder.append(",operator:").append(predicate.getType());
- stringBuilder.append(",predicate:").append(predicate.toString());
- }
- return stringBuilder.append(')').toString();
+ return EXPLAIN_NAME;
}
}
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 f81cc9bc80..7e00400eee 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
@@ -96,7 +96,7 @@ public class FilterOperatorUtils {
return new SortedIndexBasedFilterOperator(predicateEvaluator, dataSource, numDocs);
}
if (dataSource.getFSTIndex() != null && dataSource.getInvertedIndex() != null) {
- return new BitmapBasedFilterOperator(predicateEvaluator, dataSource, numDocs);
+ return new InvertedIndexFilterOperator(predicateEvaluator, dataSource, numDocs);
}
return new ScanBasedFilterOperator(predicateEvaluator, dataSource, numDocs, nullHandlingEnabled);
} else {
@@ -104,7 +104,7 @@ public class FilterOperatorUtils {
return new SortedIndexBasedFilterOperator(predicateEvaluator, dataSource, numDocs);
}
if (dataSource.getInvertedIndex() != null) {
- return new BitmapBasedFilterOperator(predicateEvaluator, dataSource, numDocs);
+ return new InvertedIndexFilterOperator(predicateEvaluator, dataSource, numDocs);
}
if (RangeIndexBasedFilterOperator.canEvaluate(predicateEvaluator, dataSource)) {
return new RangeIndexBasedFilterOperator(predicateEvaluator, dataSource, 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/InvertedIndexFilterOperator.java
similarity index 62%
copy from pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BitmapBasedFilterOperator.java
copy to pinot-core/src/main/java/org/apache/pinot/core/operator/filter/InvertedIndexFilterOperator.java
index bd8fb41ce1..8f617417a3 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/InvertedIndexFilterOperator.java
@@ -35,43 +35,26 @@ import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
import org.roaringbitmap.buffer.MutableRoaringBitmap;
-@SuppressWarnings("rawtypes")
-public class BitmapBasedFilterOperator extends BaseFilterOperator {
+public class InvertedIndexFilterOperator extends BaseFilterOperator {
private static final String EXPLAIN_NAME = "FILTER_INVERTED_INDEX";
private final PredicateEvaluator _predicateEvaluator;
private final InvertedIndexReader<ImmutableRoaringBitmap> _invertedIndexReader;
- private final ImmutableRoaringBitmap _docIds;
private final boolean _exclusive;
private final int _numDocs;
- @SuppressWarnings("unchecked")
- BitmapBasedFilterOperator(PredicateEvaluator predicateEvaluator, DataSource dataSource, int numDocs) {
+ InvertedIndexFilterOperator(PredicateEvaluator predicateEvaluator, DataSource dataSource, int numDocs) {
_predicateEvaluator = predicateEvaluator;
- _invertedIndexReader = (InvertedIndexReader<ImmutableRoaringBitmap>) dataSource.getInvertedIndex();
- _docIds = null;
+ @SuppressWarnings("unchecked")
+ InvertedIndexReader<ImmutableRoaringBitmap> invertedIndexReader =
+ (InvertedIndexReader<ImmutableRoaringBitmap>) dataSource.getInvertedIndex();
+ _invertedIndexReader = invertedIndexReader;
_exclusive = predicateEvaluator.isExclusive();
_numDocs = numDocs;
}
- public BitmapBasedFilterOperator(ImmutableRoaringBitmap docIds, boolean exclusive, int numDocs) {
- _predicateEvaluator = null;
- _invertedIndexReader = null;
- _docIds = docIds;
- _exclusive = exclusive;
- _numDocs = numDocs;
- }
-
@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));
- }
- }
-
int[] dictIds = _exclusive ? _predicateEvaluator.getNonMatchingDictIds() : _predicateEvaluator.getMatchingDictIds();
int numDictIds = dictIds.length;
if (numDictIds == 0) {
@@ -117,34 +100,28 @@ public class BitmapBasedFilterOperator extends BaseFilterOperator {
@Override
public int getNumMatchingDocs() {
int count = 0;
- if (_docIds == null) {
- int[] dictIds = _exclusive
- ? _predicateEvaluator.getNonMatchingDictIds()
- : _predicateEvaluator.getMatchingDictIds();
- switch (dictIds.length) {
- case 0:
- break;
- case 1: {
- count = _invertedIndexReader.getDocIds(dictIds[0]).getCardinality();
- break;
- }
- case 2: {
- count = ImmutableRoaringBitmap.orCardinality(_invertedIndexReader.getDocIds(dictIds[0]),
- _invertedIndexReader.getDocIds(dictIds[1]));
- break;
- }
- default: {
- // this could be optimised if the bitmaps are known to be disjoint (as in a single value bitmap index)
- MutableRoaringBitmap bitmap = new MutableRoaringBitmap();
- for (int dictId : dictIds) {
- bitmap.or(_invertedIndexReader.getDocIds(dictId));
- }
- count = bitmap.getCardinality();
- break;
+ int[] dictIds = _exclusive ? _predicateEvaluator.getNonMatchingDictIds() : _predicateEvaluator.getMatchingDictIds();
+ switch (dictIds.length) {
+ case 0:
+ break;
+ case 1: {
+ count = _invertedIndexReader.getDocIds(dictIds[0]).getCardinality();
+ break;
+ }
+ case 2: {
+ count = ImmutableRoaringBitmap.orCardinality(_invertedIndexReader.getDocIds(dictIds[0]),
+ _invertedIndexReader.getDocIds(dictIds[1]));
+ break;
+ }
+ default: {
+ // this could be optimised if the bitmaps are known to be disjoint (as in a single value bitmap index)
+ MutableRoaringBitmap bitmap = new MutableRoaringBitmap();
+ for (int dictId : dictIds) {
+ bitmap.or(_invertedIndexReader.getDocIds(dictId));
}
+ count = bitmap.getCardinality();
+ break;
}
- } else {
- count = _docIds.getCardinality();
}
return _exclusive ? _numDocs - count : count;
}
@@ -156,22 +133,16 @@ public class BitmapBasedFilterOperator extends BaseFilterOperator {
@Override
public BitmapCollection getBitmaps() {
- if (_docIds == null) {
- int[] dictIds = _exclusive
- ? _predicateEvaluator.getNonMatchingDictIds()
- : _predicateEvaluator.getMatchingDictIds();
- ImmutableRoaringBitmap[] bitmaps = new ImmutableRoaringBitmap[dictIds.length];
- for (int i = 0; i < dictIds.length; i++) {
- bitmaps[i] = _invertedIndexReader.getDocIds(dictIds[i]);
- }
- return new BitmapCollection(_numDocs, _exclusive, bitmaps);
- } else {
- return new BitmapCollection(_numDocs, _exclusive, _docIds);
+ int[] dictIds = _exclusive ? _predicateEvaluator.getNonMatchingDictIds() : _predicateEvaluator.getMatchingDictIds();
+ ImmutableRoaringBitmap[] bitmaps = new ImmutableRoaringBitmap[dictIds.length];
+ for (int i = 0; i < dictIds.length; i++) {
+ bitmaps[i] = _invertedIndexReader.getDocIds(dictIds[i]);
}
+ return new BitmapCollection(_numDocs, _exclusive, bitmaps);
}
-
@Override
+ @SuppressWarnings("rawtypes")
public List<Operator> getChildOperators() {
return Collections.emptyList();
}
@@ -179,11 +150,9 @@ public class BitmapBasedFilterOperator extends BaseFilterOperator {
@Override
public String toExplainString() {
StringBuilder stringBuilder = new StringBuilder(EXPLAIN_NAME).append("(indexLookUp:inverted_index");
- Predicate predicate = _predicateEvaluator != null ? _predicateEvaluator.getPredicate() : null;
- if (predicate != null) {
- stringBuilder.append(",operator:").append(predicate.getType());
- stringBuilder.append(",predicate:").append(predicate.toString());
- }
+ Predicate predicate = _predicateEvaluator.getPredicate();
+ stringBuilder.append(",operator:").append(predicate.getType());
+ stringBuilder.append(",predicate:").append(predicate.toString());
return stringBuilder.append(')').toString();
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org