This is an automated email from the ASF dual-hosted git repository. jackie pushed a commit to branch range_opt in repository https://gitbox.apache.org/repos/asf/incubator-pinot.git
commit 5fafcb0ca7918292f8338387481e947af34c563b Author: Xiaotian (Jackie) Jiang <[email protected]> AuthorDate: Tue Nov 20 17:43:40 2018 -0800 Optimize all filter predicates by adding isAlwaysTrue() When filter predicate is always evaluated to true, we can optimize the filter operator by replacing it with MatchAllFilterOperator. This is especially useful for range filters on time column which spans a very long time range. Also added method isResultMatchingAll() in BaseFilterOperator for the optimization. --- .../core/operator/filter/AndFilterOperator.java | 11 +---- .../core/operator/filter/BaseFilterOperator.java | 13 +++++- .../operator/filter/BitmapBasedFilterOperator.java | 7 +-- .../core/operator/filter/EmptyFilterOperator.java | 8 ++-- .../core/operator/filter/FilterOperatorUtils.java | 12 +++-- .../operator/filter/MatchAllFilterOperator.java | 8 ++-- .../core/operator/filter/OrFilterOperator.java | 11 +---- .../operator/filter/ScanBasedFilterOperator.java | 7 +-- .../SortedInvertedIndexBasedFilterOperator.java | 7 +-- .../BaseDictionaryBasedPredicateEvaluator.java | 12 +++++ .../BaseRawValueBasedPredicateEvaluator.java | 15 ++++-- .../predicate/EqualsPredicateEvaluatorFactory.java | 9 ++-- .../predicate/InPredicateEvaluatorFactory.java | 14 +++--- .../NotEqualsPredicateEvaluatorFactory.java | 9 ++-- .../predicate/NotInPredicateEvaluatorFactory.java | 16 ++++--- .../filter/predicate/PredicateEvaluator.java | 5 ++ .../predicate/RangePredicateEvaluatorFactory.java | 33 ++++++------- .../RegexpLikePredicateEvaluatorFactory.java | 5 -- .../linkedin/pinot/core/plan/FilterPlanNode.java | 54 ++++++++++++++++------ .../startree/operator/StarTreeFilterOperator.java | 37 ++++++++------- ...ngeOfflineDictionaryPredicateEvaluatorTest.java | 44 ++++++++++++++---- 21 files changed, 199 insertions(+), 138 deletions(-) diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/AndFilterOperator.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/AndFilterOperator.java index 978e727..6621ecb 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/AndFilterOperator.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/AndFilterOperator.java @@ -28,6 +28,7 @@ public class AndFilterOperator extends BaseFilterOperator { private final List<BaseFilterOperator> _filterOperators; public AndFilterOperator(List<BaseFilterOperator> filterOperators) { + // NOTE: EmptyFilterOperator and MatchAllFilterOperator should not be passed into the AndFilterOperator _filterOperators = filterOperators; } @@ -41,16 +42,6 @@ public class AndFilterOperator extends BaseFilterOperator { } @Override - public boolean isResultEmpty() { - for (BaseFilterOperator filterOperator : _filterOperators) { - if (filterOperator.isResultEmpty()) { - return true; - } - } - return false; - } - - @Override public String getOperatorName() { return OPERATOR_NAME; } diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/BaseFilterOperator.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/BaseFilterOperator.java index 6c0f287..d5b6021 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/BaseFilterOperator.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/BaseFilterOperator.java @@ -25,7 +25,16 @@ import com.linkedin.pinot.core.operator.blocks.FilterBlock; public abstract class BaseFilterOperator extends BaseOperator<FilterBlock> { /** - * Returns {@code true} if the result is always empty (without calling {@link #nextBlock()}), {@code false} otherwise. + * Returns {@code true} if the result is always empty, {@code false} otherwise. */ - public abstract boolean isResultEmpty(); + public boolean isResultEmpty() { + return false; + } + + /** + * Returns {@code true} if the result matches all the records, {@code false} otherwise. + */ + public boolean isResultMatchingAll() { + return false; + } } diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/BitmapBasedFilterOperator.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/BitmapBasedFilterOperator.java index 55f0def..37cade7 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/BitmapBasedFilterOperator.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/BitmapBasedFilterOperator.java @@ -42,6 +42,8 @@ public class BitmapBasedFilterOperator extends BaseFilterOperator { public BitmapBasedFilterOperator(PredicateEvaluator predicateEvaluator, DataSource dataSource, int startDocId, int endDocId) { + // NOTE: predicate that is always false or true should not be passed into the ScanBasedFilterOperator + assert !predicateEvaluator.isAlwaysFalse() && !predicateEvaluator.isAlwaysTrue(); _predicateEvaluator = predicateEvaluator; _dataSource = dataSource; _bitmaps = null; @@ -91,11 +93,6 @@ public class BitmapBasedFilterOperator extends BaseFilterOperator { } @Override - public boolean isResultEmpty() { - return _predicateEvaluator != null && _predicateEvaluator.isAlwaysFalse(); - } - - @Override public String getOperatorName() { return OPERATOR_NAME; } diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/EmptyFilterOperator.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/EmptyFilterOperator.java index 3068585..e60e0e3 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/EmptyFilterOperator.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/EmptyFilterOperator.java @@ -34,13 +34,13 @@ public final class EmptyFilterOperator extends BaseFilterOperator { } @Override - protected FilterBlock getNextBlock() { - return EmptyFilterBlock.getInstance(); + public final boolean isResultEmpty() { + return true; } @Override - public boolean isResultEmpty() { - return true; + protected FilterBlock getNextBlock() { + return EmptyFilterBlock.getInstance(); } @Override diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/FilterOperatorUtils.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/FilterOperatorUtils.java index a66d4c4..2d77c0e 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/FilterOperatorUtils.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/FilterOperatorUtils.java @@ -37,10 +37,14 @@ public class FilterOperatorUtils { * Returns the leaf filter operator (i.e. not {@link AndFilterOperator} or {@link OrFilterOperator}). */ public static BaseFilterOperator getLeafFilterOperator(PredicateEvaluator predicateEvaluator, DataSource dataSource, - int startDocId, int endDocId) { - if (predicateEvaluator.isAlwaysFalse()) { - return EmptyFilterOperator.getInstance(); - } + int numDocs) { + // NOTE: predicate that is always false or true should be handled outside of this method + assert !predicateEvaluator.isAlwaysFalse() && !predicateEvaluator.isAlwaysTrue(); + + int startDocId = 0; + // NOTE: end document Id is inclusive + // TODO: make it exclusive + int endDocId = numDocs - 1; // Use inverted index if the predicate type is not RANGE or REGEXP_LIKE for efficiency DataSourceMetadata dataSourceMetadata = dataSource.getDataSourceMetadata(); diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/MatchAllFilterOperator.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/MatchAllFilterOperator.java index 89e24fd..4de4faf 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/MatchAllFilterOperator.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/MatchAllFilterOperator.java @@ -29,13 +29,13 @@ public class MatchAllFilterOperator extends BaseFilterOperator { } @Override - protected FilterBlock getNextBlock() { - return new FilterBlock(new SizeBasedDocIdSet(_maxDocId)); + public final boolean isResultMatchingAll() { + return true; } @Override - public boolean isResultEmpty() { - return false; + protected FilterBlock getNextBlock() { + return new FilterBlock(new SizeBasedDocIdSet(_maxDocId)); } @Override diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/OrFilterOperator.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/OrFilterOperator.java index 3df7ba6..e78cdc4 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/OrFilterOperator.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/OrFilterOperator.java @@ -28,6 +28,7 @@ public class OrFilterOperator extends BaseFilterOperator { private List<BaseFilterOperator> _filterOperators; public OrFilterOperator(List<BaseFilterOperator> filterOperators) { + // NOTE: EmptyFilterOperator and MatchAllFilterOperator should not be passed into the OrFilterOperator _filterOperators = filterOperators; } @@ -41,16 +42,6 @@ public class OrFilterOperator extends BaseFilterOperator { } @Override - public boolean isResultEmpty() { - for (BaseFilterOperator filterOperator : _filterOperators) { - if (!filterOperator.isResultEmpty()) { - return false; - } - } - return true; - } - - @Override public String getOperatorName() { return OPERATOR_NAME; } diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/ScanBasedFilterOperator.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/ScanBasedFilterOperator.java index 389ad50..3ae0ad9 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/ScanBasedFilterOperator.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/ScanBasedFilterOperator.java @@ -39,6 +39,8 @@ public class ScanBasedFilterOperator extends BaseFilterOperator { public ScanBasedFilterOperator(PredicateEvaluator predicateEvaluator, DataSource dataSource, int startDocId, int endDocId) { + // NOTE: predicate that is always false or true should not be passed into the ScanBasedFilterOperator + assert !predicateEvaluator.isAlwaysFalse() && !predicateEvaluator.isAlwaysTrue(); _predicateEvaluator = predicateEvaluator; _dataSource = dataSource; _startDocId = startDocId; @@ -68,11 +70,6 @@ public class ScanBasedFilterOperator extends BaseFilterOperator { } @Override - public boolean isResultEmpty() { - return _predicateEvaluator.isAlwaysFalse(); - } - - @Override public String getOperatorName() { return OPERATOR_NAME; } diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/SortedInvertedIndexBasedFilterOperator.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/SortedInvertedIndexBasedFilterOperator.java index 912b0ef..018b4ca 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/SortedInvertedIndexBasedFilterOperator.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/SortedInvertedIndexBasedFilterOperator.java @@ -38,6 +38,8 @@ public class SortedInvertedIndexBasedFilterOperator extends BaseFilterOperator { public SortedInvertedIndexBasedFilterOperator(PredicateEvaluator predicateEvaluator, DataSource dataSource, int startDocId, int endDocId) { + // NOTE: predicate that is always false or true should not be passed into the ScanBasedFilterOperator + assert !predicateEvaluator.isAlwaysFalse() && !predicateEvaluator.isAlwaysTrue(); _predicateEvaluator = predicateEvaluator; _dataSource = dataSource; _startDocId = startDocId; @@ -147,11 +149,6 @@ public class SortedInvertedIndexBasedFilterOperator extends BaseFilterOperator { } @Override - public boolean isResultEmpty() { - return _predicateEvaluator.isAlwaysFalse(); - } - - @Override public String getOperatorName() { return OPERATOR_NAME; } diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/BaseDictionaryBasedPredicateEvaluator.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/BaseDictionaryBasedPredicateEvaluator.java index 08835a8..703ab32 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/BaseDictionaryBasedPredicateEvaluator.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/BaseDictionaryBasedPredicateEvaluator.java @@ -16,6 +16,18 @@ package com.linkedin.pinot.core.operator.filter.predicate; public abstract class BaseDictionaryBasedPredicateEvaluator extends BasePredicateEvaluator { + protected boolean _alwaysFalse; + protected boolean _alwaysTrue; + + @Override + public boolean isAlwaysFalse() { + return _alwaysFalse; + } + + @Override + public boolean isAlwaysTrue() { + return _alwaysTrue; + } @Override public final boolean isDictionaryBased() { diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/BaseRawValueBasedPredicateEvaluator.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/BaseRawValueBasedPredicateEvaluator.java index f32df69..713015b 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/BaseRawValueBasedPredicateEvaluator.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/BaseRawValueBasedPredicateEvaluator.java @@ -23,18 +23,23 @@ public abstract class BaseRawValueBasedPredicateEvaluator extends BasePredicateE } @Override - public final int[] getMatchingDictIds() { - throw new UnsupportedOperationException(); + public final boolean isAlwaysFalse() { + return false; } @Override - public final int[] getNonMatchingDictIds() { + public final boolean isAlwaysTrue() { + return false; + } + + @Override + public final int[] getMatchingDictIds() { throw new UnsupportedOperationException(); } @Override - public boolean isAlwaysFalse() { - return false; + public final int[] getNonMatchingDictIds() { + throw new UnsupportedOperationException(); } /** diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/EqualsPredicateEvaluatorFactory.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/EqualsPredicateEvaluatorFactory.java index 5ed998b..38f46d7 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/EqualsPredicateEvaluatorFactory.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/EqualsPredicateEvaluatorFactory.java @@ -73,8 +73,12 @@ public class EqualsPredicateEvaluatorFactory { _matchingDictId = dictionary.indexOf(eqPredicate.getEqualsValue()); if (_matchingDictId >= 0) { _matchingDictIds = new int[]{_matchingDictId}; + if (dictionary.length() == 1) { + _alwaysTrue = true; + } } else { _matchingDictIds = new int[0]; + _alwaysFalse = true; } } @@ -84,11 +88,6 @@ public class EqualsPredicateEvaluatorFactory { } @Override - public boolean isAlwaysFalse() { - return _matchingDictId < 0; - } - - @Override public boolean applySV(int dictId) { return _matchingDictId == dictId; } diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/InPredicateEvaluatorFactory.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/InPredicateEvaluatorFactory.java index f99329e..1d399b3 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/InPredicateEvaluatorFactory.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/InPredicateEvaluatorFactory.java @@ -79,6 +79,7 @@ public class InPredicateEvaluatorFactory { private static final class DictionaryBasedInPredicateEvaluator extends BaseDictionaryBasedPredicateEvaluator { final IntSet _matchingDictIdSet; + final int _numMatchingDictIds; int[] _matchingDictIds; DictionaryBasedInPredicateEvaluator(InPredicate inPredicate, Dictionary dictionary) { @@ -90,6 +91,12 @@ public class InPredicateEvaluatorFactory { _matchingDictIdSet.add(dictId); } } + _numMatchingDictIds = _matchingDictIdSet.size(); + if (_numMatchingDictIds == 0) { + _alwaysFalse = true; + } else if (dictionary.length() == _numMatchingDictIds) { + _alwaysTrue = true; + } } @Override @@ -98,18 +105,13 @@ public class InPredicateEvaluatorFactory { } @Override - public boolean isAlwaysFalse() { - return _matchingDictIdSet.isEmpty(); - } - - @Override public boolean applySV(int dictId) { return _matchingDictIdSet.contains(dictId); } @Override public int getNumMatchingDictIds() { - return _matchingDictIdSet.size(); + return _numMatchingDictIds; } @Override diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/NotEqualsPredicateEvaluatorFactory.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/NotEqualsPredicateEvaluatorFactory.java index ce27adb..e2deef5 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/NotEqualsPredicateEvaluatorFactory.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/NotEqualsPredicateEvaluatorFactory.java @@ -75,8 +75,12 @@ public class NotEqualsPredicateEvaluatorFactory { _nonMatchingDictId = dictionary.indexOf(nEqPredicate.getNotEqualsValue()); if (_nonMatchingDictId >= 0) { _nonMatchingDictIds = new int[]{_nonMatchingDictId}; + if (dictionary.length() == 1) { + _alwaysFalse = true; + } } else { _nonMatchingDictIds = new int[0]; + _alwaysTrue = true; } _dictionary = dictionary; } @@ -87,11 +91,6 @@ public class NotEqualsPredicateEvaluatorFactory { } @Override - public boolean isAlwaysFalse() { - return _nonMatchingDictIds.length == _dictionary.length(); - } - - @Override public boolean applySV(int dictId) { return _nonMatchingDictId != dictId; } diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/NotInPredicateEvaluatorFactory.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/NotInPredicateEvaluatorFactory.java index b16b85c..4d55aee 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/NotInPredicateEvaluatorFactory.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/NotInPredicateEvaluatorFactory.java @@ -79,6 +79,7 @@ public class NotInPredicateEvaluatorFactory { public static final class DictionaryBasedNotInPredicateEvaluator extends BaseDictionaryBasedPredicateEvaluator { final IntSet _nonMatchingDictIdSet; + final int _numNonMatchingDictIds; final Dictionary _dictionary; int[] _matchingDictIds; int[] _nonMatchingDictIds; @@ -92,6 +93,12 @@ public class NotInPredicateEvaluatorFactory { _nonMatchingDictIdSet.add(dictId); } } + _numNonMatchingDictIds = _nonMatchingDictIdSet.size(); + if (_numNonMatchingDictIds == 0) { + _alwaysTrue = true; + } else if (dictionary.length() == _numNonMatchingDictIds) { + _alwaysFalse = true; + } _dictionary = dictionary; } @@ -101,11 +108,6 @@ public class NotInPredicateEvaluatorFactory { } @Override - public boolean isAlwaysFalse() { - return _nonMatchingDictIdSet.size() == _dictionary.length(); - } - - @Override public boolean applySV(int dictId) { return !_nonMatchingDictIdSet.contains(dictId); } @@ -114,7 +116,7 @@ public class NotInPredicateEvaluatorFactory { public int[] getMatchingDictIds() { if (_matchingDictIds == null) { int dictionarySize = _dictionary.length(); - _matchingDictIds = new int[dictionarySize - _nonMatchingDictIdSet.size()]; + _matchingDictIds = new int[dictionarySize - _numNonMatchingDictIds]; int index = 0; for (int dictId = 0; dictId < dictionarySize; dictId++) { if (!_nonMatchingDictIdSet.contains(dictId)) { @@ -127,7 +129,7 @@ public class NotInPredicateEvaluatorFactory { @Override public int getNumNonMatchingDictIds() { - return _nonMatchingDictIdSet.size(); + return _numNonMatchingDictIds; } @Override diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/PredicateEvaluator.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/PredicateEvaluator.java index 2385cee..649c053 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/PredicateEvaluator.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/PredicateEvaluator.java @@ -44,6 +44,11 @@ public interface PredicateEvaluator { boolean isAlwaysFalse(); /** + * Return whether the predicate will always be evaluated as true. + */ + boolean isAlwaysTrue(); + + /** * Apply a single-value entry to the predicate. * * @param value Dictionary id or raw value diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/RangePredicateEvaluatorFactory.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/RangePredicateEvaluatorFactory.java index 6184e20..b688563 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/RangePredicateEvaluatorFactory.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/RangePredicateEvaluatorFactory.java @@ -115,7 +115,13 @@ public class RangePredicateEvaluatorFactory { } } } + _numMatchingDictIds = _endDictId - _startDictId; + if (_numMatchingDictIds <= 0) { + _alwaysFalse = true; + } else if (dictionary.length() == _numMatchingDictIds) { + _alwaysTrue = true; + } } @Override @@ -124,11 +130,6 @@ public class RangePredicateEvaluatorFactory { } @Override - public boolean isAlwaysFalse() { - return _startDictId >= _endDictId; - } - - @Override public boolean applySV(int dictId) { return _startDictId <= dictId && _endDictId > dictId; } @@ -157,6 +158,7 @@ public class RangePredicateEvaluatorFactory { private static final class RealtimeDictionaryBasedRangePredicateEvaluator extends BaseDictionaryBasedPredicateEvaluator { final IntSet _matchingDictIdSet; + final int _numMatchingDictIds; int[] _matchingDictIds; RealtimeDictionaryBasedRangePredicateEvaluator(RangePredicate rangePredicate, MutableDictionary dictionary) { @@ -164,6 +166,8 @@ public class RangePredicateEvaluatorFactory { int dictionarySize = dictionary.length(); if (dictionarySize == 0) { + _numMatchingDictIds = 0; + _alwaysFalse = true; return; } @@ -184,6 +188,13 @@ public class RangePredicateEvaluatorFactory { _matchingDictIdSet.add(dictId); } } + + _numMatchingDictIds = _matchingDictIdSet.size(); + if (_numMatchingDictIds == 0) { + _alwaysFalse = true; + } else if (dictionarySize == _numMatchingDictIds) { + _alwaysTrue = true; + } } @Override @@ -198,7 +209,7 @@ public class RangePredicateEvaluatorFactory { @Override public int getNumMatchingDictIds() { - return _matchingDictIdSet.size(); + return _numMatchingDictIds; } @Override @@ -208,16 +219,6 @@ public class RangePredicateEvaluatorFactory { } return _matchingDictIds; } - - @Override - public int[] getNonMatchingDictIds() { - throw new UnsupportedOperationException(); - } - - @Override - public boolean isAlwaysFalse() { - return _matchingDictIdSet.isEmpty(); - } } private static final class IntRawValueBasedRangePredicateEvaluator extends BaseRawValueBasedPredicateEvaluator { diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/RegexpLikePredicateEvaluatorFactory.java b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/RegexpLikePredicateEvaluatorFactory.java index d6ac01a..037c40f 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/RegexpLikePredicateEvaluatorFactory.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/operator/filter/predicate/RegexpLikePredicateEvaluatorFactory.java @@ -75,11 +75,6 @@ public class RegexpLikePredicateEvaluatorFactory { } @Override - public boolean isAlwaysFalse() { - return false; - } - - @Override public boolean applySV(int dictId) { return _pattern.matcher(_dictionary.getStringValue(dictId)).find(); } diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/plan/FilterPlanNode.java b/pinot-core/src/main/java/com/linkedin/pinot/core/plan/FilterPlanNode.java index 226f1fc..893d1fe 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/plan/FilterPlanNode.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/plan/FilterPlanNode.java @@ -59,49 +59,77 @@ public class FilterPlanNode implements PlanNode { */ private static BaseFilterOperator constructPhysicalOperator(FilterQueryTree filterQueryTree, IndexSegment segment, @Nullable Map<String, String> debugOptions) { + int numDocs = segment.getSegmentMetadata().getTotalRawDocs(); if (filterQueryTree == null) { - return new MatchAllFilterOperator(segment.getSegmentMetadata().getTotalRawDocs()); + return new MatchAllFilterOperator(numDocs); } // For non-leaf node, recursively create the child filter operators FilterOperator filterType = filterQueryTree.getOperator(); if (filterType == FilterOperator.AND || filterType == FilterOperator.OR) { + // Non-leaf filter operator List<FilterQueryTree> childFilters = filterQueryTree.getChildren(); - List<BaseFilterOperator> childFilterOperators = new ArrayList<>(childFilters.size()); + List<BaseFilterOperator> childFilterOperators = new ArrayList<>(); if (filterType == FilterOperator.AND) { + // AND operator for (FilterQueryTree childFilter : childFilters) { BaseFilterOperator childFilterOperator = constructPhysicalOperator(childFilter, segment, debugOptions); if (childFilterOperator.isResultEmpty()) { + // Return empty filter operator if any of the child filter operator's result is empty return EmptyFilterOperator.getInstance(); + } else if (!childFilterOperator.isResultMatchingAll()) { + // Remove child filter operators that match all records + childFilterOperators.add(childFilterOperator); } - childFilterOperators.add(childFilterOperator); } - FilterOperatorUtils.reorderAndFilterChildOperators(childFilterOperators, debugOptions); - return new AndFilterOperator(childFilterOperators); + int numChildFilterOperators = childFilterOperators.size(); + if (numChildFilterOperators == 0) { + // Return match all filter operator if all child filter operators match all records + return new MatchAllFilterOperator(numDocs); + } else if (numChildFilterOperators == 1) { + // Return the child filter operator if only one left + return childFilterOperators.get(0); + } else { + // Return the AND filter operator with re-ordered child filter operators + FilterOperatorUtils.reorderAndFilterChildOperators(childFilterOperators, debugOptions); + return new AndFilterOperator(childFilterOperators); + } } else { + // OR operator for (FilterQueryTree childFilter : childFilters) { BaseFilterOperator childFilterOperator = constructPhysicalOperator(childFilter, segment, debugOptions); - if (!childFilterOperator.isResultEmpty()) { + if (childFilterOperator.isResultMatchingAll()) { + // Return match all filter operator if any of the child filter operator matches all records + return new MatchAllFilterOperator(numDocs); + } else if (!childFilterOperator.isResultEmpty()) { + // Remove child filter operators whose result is empty childFilterOperators.add(childFilterOperator); } } - if (childFilterOperators.isEmpty()) { + int numChildFilterOperators = childFilterOperators.size(); + if (numChildFilterOperators == 0) { + // Return empty filter operator if all child filter operators's result is empty return EmptyFilterOperator.getInstance(); - } else if (childFilterOperators.size() == 1) { + } else if (numChildFilterOperators == 1) { + // Return the child filter operator if only one left return childFilterOperators.get(0); } else { + // Return the OR filter operator with child filter operators return new OrFilterOperator(childFilterOperators); } } } else { + // Leaf filter operator Predicate predicate = Predicate.newPredicate(filterQueryTree); DataSource dataSource = segment.getDataSource(filterQueryTree.getColumn()); PredicateEvaluator predicateEvaluator = PredicateEvaluatorProvider.getPredicateEvaluator(predicate, dataSource); - int startDocId = 0; - // TODO: make it exclusive - // NOTE: end is inclusive - int endDocId = segment.getSegmentMetadata().getTotalRawDocs() - 1; - return FilterOperatorUtils.getLeafFilterOperator(predicateEvaluator, dataSource, startDocId, endDocId); + if (predicateEvaluator.isAlwaysFalse()) { + return EmptyFilterOperator.getInstance(); + } else if (predicateEvaluator.isAlwaysTrue()) { + return new MatchAllFilterOperator(numDocs); + } else { + return FilterOperatorUtils.getLeafFilterOperator(predicateEvaluator, dataSource, numDocs); + } } } diff --git a/pinot-core/src/main/java/com/linkedin/pinot/core/startree/operator/StarTreeFilterOperator.java b/pinot-core/src/main/java/com/linkedin/pinot/core/startree/operator/StarTreeFilterOperator.java index 3e008b8..eec4a9a 100644 --- a/pinot-core/src/main/java/com/linkedin/pinot/core/startree/operator/StarTreeFilterOperator.java +++ b/pinot-core/src/main/java/com/linkedin/pinot/core/startree/operator/StarTreeFilterOperator.java @@ -137,21 +137,17 @@ public class StarTreeFilterOperator extends BaseFilterOperator { _debugOptions = debugOptions; if (rootFilterNode != null) { + _predicateEvaluatorsMap = new HashMap<>(); + _matchingDictIdsMap = new HashMap<>(); + // Process the filter tree and get a map from column to a list of predicates applied to it Map<String, List<Predicate>> predicatesMap = getPredicatesMap(rootFilterNode); - // Remove columns with predicates from group-by columns because we won't use star node for that column - _groupByColumns.removeAll(predicatesMap.keySet()); - - int numColumnsInPredicates = predicatesMap.size(); - _predicateEvaluatorsMap = new HashMap<>(numColumnsInPredicates); - _matchingDictIdsMap = new HashMap<>(numColumnsInPredicates); - // Initialize the predicate evaluators map for (Map.Entry<String, List<Predicate>> entry : predicatesMap.entrySet()) { String columnName = entry.getKey(); List<Predicate> predicates = entry.getValue(); - List<PredicateEvaluator> predicateEvaluators = new ArrayList<>(predicates.size()); + List<PredicateEvaluator> predicateEvaluators = new ArrayList<>(); DataSource dataSource = starTreeV2.getDataSource(columnName); for (Predicate predicate : predicates) { @@ -161,11 +157,17 @@ public class StarTreeFilterOperator extends BaseFilterOperator { if (predicateEvaluator.isAlwaysFalse()) { _resultEmpty = true; return; + } else if (!predicateEvaluator.isAlwaysTrue()) { + predicateEvaluators.add(predicateEvaluator); } - predicateEvaluators.add(predicateEvaluator); } - _predicateEvaluatorsMap.put(columnName, predicateEvaluators); + if (!predicateEvaluators.isEmpty()) { + _predicateEvaluatorsMap.put(columnName, predicateEvaluators); + } } + + // Remove columns with predicates from group-by columns because we won't use star node for that column + _groupByColumns.removeAll(_predicateEvaluatorsMap.keySet()); } else { _predicateEvaluatorsMap = Collections.emptyMap(); _matchingDictIdsMap = Collections.emptyMap(); @@ -218,6 +220,11 @@ public class StarTreeFilterOperator extends BaseFilterOperator { } @Override + public boolean isResultMatchingAll() { + return false; + } + + @Override public String getOperatorName() { return OPERATOR_NAME; } @@ -237,16 +244,13 @@ public class StarTreeFilterOperator extends BaseFilterOperator { return Collections.emptyList(); } + int numDocs = _starTreeV2.getMetadata().getNumDocs(); List<BaseFilterOperator> childFilterOperators = new ArrayList<>(1 + starTreeResult._remainingPredicateColumns.size()); - int startDocId = 0; - // Inclusive end document id - int endDocId = _starTreeV2.getMetadata().getNumDocs() - 1; - // Add the bitmap of matching documents from star tree childFilterOperators.add( - new BitmapBasedFilterOperator(new ImmutableRoaringBitmap[]{starTreeResult._matchedDocIds}, startDocId, endDocId, + new BitmapBasedFilterOperator(new ImmutableRoaringBitmap[]{starTreeResult._matchedDocIds}, 0, numDocs - 1, false)); // Add remaining predicates @@ -254,8 +258,7 @@ public class StarTreeFilterOperator extends BaseFilterOperator { List<PredicateEvaluator> predicateEvaluators = _predicateEvaluatorsMap.get(remainingPredicateColumn); DataSource dataSource = _starTreeV2.getDataSource(remainingPredicateColumn); for (PredicateEvaluator predicateEvaluator : predicateEvaluators) { - childFilterOperators.add( - FilterOperatorUtils.getLeafFilterOperator(predicateEvaluator, dataSource, startDocId, endDocId)); + childFilterOperators.add(FilterOperatorUtils.getLeafFilterOperator(predicateEvaluator, dataSource, numDocs)); } } diff --git a/pinot-core/src/test/java/com/linkedin/pinot/core/predicate/RangeOfflineDictionaryPredicateEvaluatorTest.java b/pinot-core/src/test/java/com/linkedin/pinot/core/predicate/RangeOfflineDictionaryPredicateEvaluatorTest.java index 10516e1..14d1815 100644 --- a/pinot-core/src/test/java/com/linkedin/pinot/core/predicate/RangeOfflineDictionaryPredicateEvaluatorTest.java +++ b/pinot-core/src/test/java/com/linkedin/pinot/core/predicate/RangeOfflineDictionaryPredicateEvaluatorTest.java @@ -32,13 +32,14 @@ public class RangeOfflineDictionaryPredicateEvaluatorTest { public void testRanges() { int rangeStart, rangeEnd; { - // (2,5) + // [2, 5] rangeStart = 2; rangeEnd = 5; ImmutableDictionaryReader reader = createReader(rangeStart, rangeEnd); RangePredicate predicate = createPredicate(rangeStart, true, rangeEnd, true); PredicateEvaluator evaluator = RangePredicateEvaluatorFactory.newDictionaryBasedEvaluator(predicate, reader); Assert.assertFalse(evaluator.isAlwaysFalse()); + Assert.assertFalse(evaluator.isAlwaysTrue()); Assert.assertTrue(evaluator.applySV(rangeStart)); Assert.assertTrue(evaluator.applySV(rangeEnd)); Assert.assertTrue(evaluator.applySV(rangeStart + 1)); @@ -52,13 +53,14 @@ public class RangeOfflineDictionaryPredicateEvaluatorTest { verifyDictId(dictIds, rangeStart, rangeEnd); } { - // [2,5) + // (2, 5] rangeStart = 2; rangeEnd = 5; ImmutableDictionaryReader reader = createReader(rangeStart, rangeEnd); RangePredicate predicate = createPredicate(rangeStart, false, rangeEnd, true); PredicateEvaluator evaluator = RangePredicateEvaluatorFactory.newDictionaryBasedEvaluator(predicate, reader); Assert.assertFalse(evaluator.isAlwaysFalse()); + Assert.assertFalse(evaluator.isAlwaysTrue()); Assert.assertFalse(evaluator.applySV(rangeStart)); Assert.assertTrue(evaluator.applySV(rangeEnd)); Assert.assertTrue(evaluator.applySV(rangeStart + 1)); @@ -72,13 +74,14 @@ public class RangeOfflineDictionaryPredicateEvaluatorTest { verifyDictId(dictIds, rangeStart + 1, rangeEnd); } { - // (2,5] + // [2, 5) rangeStart = 2; rangeEnd = 5; ImmutableDictionaryReader reader = createReader(rangeStart, rangeEnd); RangePredicate predicate = createPredicate(rangeStart, true, rangeEnd, false); PredicateEvaluator evaluator = RangePredicateEvaluatorFactory.newDictionaryBasedEvaluator(predicate, reader); Assert.assertFalse(evaluator.isAlwaysFalse()); + Assert.assertFalse(evaluator.isAlwaysTrue()); Assert.assertTrue(evaluator.applySV(rangeStart)); Assert.assertFalse(evaluator.applySV(rangeEnd)); Assert.assertTrue(evaluator.applySV(rangeStart + 1)); @@ -92,13 +95,14 @@ public class RangeOfflineDictionaryPredicateEvaluatorTest { verifyDictId(dictIds, rangeStart, rangeEnd - 1); } { - // [2,5] + // (2, 5) rangeStart = 2; rangeEnd = 5; ImmutableDictionaryReader reader = createReader(rangeStart, rangeEnd); RangePredicate predicate = createPredicate(rangeStart, false, rangeEnd, false); PredicateEvaluator evaluator = RangePredicateEvaluatorFactory.newDictionaryBasedEvaluator(predicate, reader); Assert.assertFalse(evaluator.isAlwaysFalse()); + Assert.assertFalse(evaluator.isAlwaysTrue()); Assert.assertFalse(evaluator.applySV(rangeStart)); Assert.assertFalse(evaluator.applySV(rangeEnd)); Assert.assertTrue(evaluator.applySV(rangeStart + 1)); @@ -124,13 +128,14 @@ public class RangeOfflineDictionaryPredicateEvaluatorTest { public void testBoundaries() { int rangeStart, rangeEnd; { - // (0,5] + // [0, 5) rangeStart = 0; rangeEnd = 5; ImmutableDictionaryReader reader = createReader(rangeStart, rangeEnd); RangePredicate predicate = createPredicate(rangeStart, true, rangeEnd, false); PredicateEvaluator evaluator = RangePredicateEvaluatorFactory.newDictionaryBasedEvaluator(predicate, reader); Assert.assertFalse(evaluator.isAlwaysFalse()); + Assert.assertFalse(evaluator.isAlwaysTrue()); Assert.assertTrue(evaluator.applySV(rangeStart)); Assert.assertFalse(evaluator.applySV(rangeEnd)); Assert.assertTrue(evaluator.applySV(rangeStart + 1)); @@ -143,26 +148,28 @@ public class RangeOfflineDictionaryPredicateEvaluatorTest { verifyDictId(dictIds, rangeStart, rangeEnd - 1); } { - // (0,5) + // [0, 5] rangeStart = 0; rangeEnd = 5; ImmutableDictionaryReader reader = createReader(rangeStart, rangeEnd); RangePredicate predicate = createPredicate(rangeStart, true, rangeEnd, true); PredicateEvaluator evaluator = RangePredicateEvaluatorFactory.newDictionaryBasedEvaluator(predicate, reader); Assert.assertFalse(evaluator.isAlwaysFalse()); + Assert.assertFalse(evaluator.isAlwaysTrue()); Assert.assertTrue(evaluator.applySV(rangeStart)); Assert.assertTrue(evaluator.applySV(rangeEnd)); Assert.assertTrue(evaluator.applySV(rangeStart + 1)); Assert.assertFalse(evaluator.applySV(rangeEnd + 1)); } { - // (6, DICT_LEN-1) + // [6, DICT_LEN-1] rangeStart = 6; rangeEnd = DICT_LEN - 1; ImmutableDictionaryReader reader = createReader(rangeStart, rangeEnd); RangePredicate predicate = createPredicate(rangeStart, true, rangeEnd, true); PredicateEvaluator evaluator = RangePredicateEvaluatorFactory.newDictionaryBasedEvaluator(predicate, reader); Assert.assertFalse(evaluator.isAlwaysFalse()); + Assert.assertFalse(evaluator.isAlwaysTrue()); Assert.assertTrue(evaluator.applySV(rangeStart)); Assert.assertTrue(evaluator.applySV(rangeEnd)); Assert.assertTrue(evaluator.applySV(rangeStart + 1)); @@ -175,30 +182,47 @@ public class RangeOfflineDictionaryPredicateEvaluatorTest { verifyDictId(dictIds, rangeStart, rangeEnd); } { - // [6, DICT_LEN-1) + // (6, DICT_LEN-1] rangeStart = 6; rangeEnd = DICT_LEN - 1; ImmutableDictionaryReader reader = createReader(rangeStart, rangeEnd); RangePredicate predicate = createPredicate(rangeStart, false, rangeEnd, true); PredicateEvaluator evaluator = RangePredicateEvaluatorFactory.newDictionaryBasedEvaluator(predicate, reader); Assert.assertFalse(evaluator.isAlwaysFalse()); + Assert.assertFalse(evaluator.isAlwaysTrue()); Assert.assertFalse(evaluator.applySV(rangeStart)); Assert.assertTrue(evaluator.applySV(rangeEnd)); Assert.assertTrue(evaluator.applySV(rangeStart + 1)); Assert.assertFalse(evaluator.applySV(rangeStart - 1)); } + { + // [0, DICT_LEN-1] + rangeStart = 0; + rangeEnd = DICT_LEN - 1; + ImmutableDictionaryReader reader = createReader(rangeStart, rangeEnd); + RangePredicate predicate = createPredicate(rangeStart, true, rangeEnd, true); + PredicateEvaluator evaluator = RangePredicateEvaluatorFactory.newDictionaryBasedEvaluator(predicate, reader); + Assert.assertFalse(evaluator.isAlwaysFalse()); + Assert.assertTrue(evaluator.isAlwaysTrue()); + Assert.assertTrue(evaluator.applySV(rangeStart)); + Assert.assertTrue(evaluator.applySV(rangeEnd)); + Assert.assertTrue(evaluator.applySV(rangeStart + 1)); + Assert.assertFalse(evaluator.applySV(rangeStart - 1)); + } } @Test public void testZeroRange() { int rangeStart, rangeEnd; { + // (4, 5) rangeStart = 4; rangeEnd = 5; ImmutableDictionaryReader reader = createReader(rangeStart, rangeEnd); RangePredicate predicate = createPredicate(rangeStart, false, rangeEnd, false); PredicateEvaluator evaluator = RangePredicateEvaluatorFactory.newDictionaryBasedEvaluator(predicate, reader); Assert.assertTrue(evaluator.isAlwaysFalse()); + Assert.assertFalse(evaluator.isAlwaysTrue()); Assert.assertFalse(evaluator.applySV(rangeStart)); Assert.assertFalse(evaluator.applySV(rangeEnd)); Assert.assertFalse(evaluator.applySV(rangeStart + 1)); @@ -225,11 +249,11 @@ public class RangeOfflineDictionaryPredicateEvaluatorTest { when(predicate.includeLowerBoundary()).thenReturn(inclLower); when(predicate.includeUpperBoundary()).thenReturn(inclUpper); String lowerStr = "lower"; - if (lower == 0) { + if (lower == 0 && inclLower) { lowerStr = "*"; } String upperStr = "upper"; - if (upper == DICT_LEN - 1) { + if (upper == DICT_LEN - 1 && inclUpper) { upperStr = "*"; } when(predicate.getLowerBoundary()).thenReturn(lowerStr); --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
