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 717940b Introduce OR Predicate Execution On Star Tree Index (#7184)
717940b is described below
commit 717940b5d1c0b9aa0fea149384f12c77b31cefd7
Author: Atri Sharma <[email protected]>
AuthorDate: Tue Jul 27 10:42:35 2021 +0530
Introduce OR Predicate Execution On Star Tree Index (#7184)
Allows OR predicates to be executed on Star Tree indices. We only allow a
single dimension to
be present in the OR predicate in order to be qualified for execution on
Star Tree node. This is to ensure
that we do not double count pre aggregated documents while traversing the
tree for two dimensions.
---
.../plan/AggregationGroupByOrderByPlanNode.java | 5 +-
.../core/plan/AggregationGroupByPlanNode.java | 4 +-
.../pinot/core/plan/AggregationPlanNode.java | 5 +-
.../core/startree/CompositePredicateEvaluator.java | 57 ++++++++
.../apache/pinot/core/startree/StarTreeUtils.java | 151 +++++++++++++++++----
.../startree/operator/StarTreeFilterOperator.java | 117 ++++++++++------
.../startree/plan/StarTreeDocIdSetPlanNode.java | 7 +-
.../core/startree/plan/StarTreeFilterPlanNode.java | 9 +-
.../startree/plan/StarTreeProjectionPlanNode.java | 4 +-
.../startree/plan/StarTreeTransformPlanNode.java | 5 +-
.../pinot/core/startree/v2/BaseStarTreeV2Test.java | 28 +++-
11 files changed, 302 insertions(+), 90 deletions(-)
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/plan/AggregationGroupByOrderByPlanNode.java
b/pinot-core/src/main/java/org/apache/pinot/core/plan/AggregationGroupByOrderByPlanNode.java
index 915eb5e..47df15a 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/plan/AggregationGroupByOrderByPlanNode.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/plan/AggregationGroupByOrderByPlanNode.java
@@ -22,17 +22,18 @@ import java.util.List;
import java.util.Map;
import java.util.Set;
import org.apache.pinot.common.request.context.ExpressionContext;
-import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
import org.apache.pinot.core.operator.query.AggregationGroupByOrderByOperator;
import org.apache.pinot.core.query.aggregation.function.AggregationFunction;
import
org.apache.pinot.core.query.aggregation.function.AggregationFunctionUtils;
import org.apache.pinot.core.query.request.context.QueryContext;
+import org.apache.pinot.core.startree.CompositePredicateEvaluator;
import org.apache.pinot.core.startree.StarTreeUtils;
import org.apache.pinot.core.startree.plan.StarTreeTransformPlanNode;
import org.apache.pinot.segment.spi.IndexSegment;
import
org.apache.pinot.segment.spi.index.startree.AggregationFunctionColumnPair;
import org.apache.pinot.segment.spi.index.startree.StarTreeV2;
+
/**
* The <code>AggregationGroupByOrderByPlanNode</code> class provides the
execution plan for aggregation group-by order-by query on a
* single segment.
@@ -67,7 +68,7 @@ public class AggregationGroupByOrderByPlanNode implements
PlanNode {
AggregationFunctionColumnPair[] aggregationFunctionColumnPairs =
StarTreeUtils.extractAggregationFunctionPairs(_aggregationFunctions);
if (aggregationFunctionColumnPairs != null) {
- Map<String, List<PredicateEvaluator>> predicateEvaluatorsMap =
+ Map<String, List<CompositePredicateEvaluator>> predicateEvaluatorsMap =
StarTreeUtils.extractPredicateEvaluatorsMap(indexSegment,
queryContext.getFilter());
if (predicateEvaluatorsMap != null) {
for (StarTreeV2 starTreeV2 : starTrees) {
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/plan/AggregationGroupByPlanNode.java
b/pinot-core/src/main/java/org/apache/pinot/core/plan/AggregationGroupByPlanNode.java
index 25db1dd..9554bc9 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/plan/AggregationGroupByPlanNode.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/plan/AggregationGroupByPlanNode.java
@@ -22,11 +22,11 @@ import java.util.List;
import java.util.Map;
import java.util.Set;
import org.apache.pinot.common.request.context.ExpressionContext;
-import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
import org.apache.pinot.core.operator.query.AggregationGroupByOperator;
import org.apache.pinot.core.query.aggregation.function.AggregationFunction;
import
org.apache.pinot.core.query.aggregation.function.AggregationFunctionUtils;
import org.apache.pinot.core.query.request.context.QueryContext;
+import org.apache.pinot.core.startree.CompositePredicateEvaluator;
import org.apache.pinot.core.startree.StarTreeUtils;
import org.apache.pinot.core.startree.plan.StarTreeTransformPlanNode;
import org.apache.pinot.segment.spi.IndexSegment;
@@ -64,7 +64,7 @@ public class AggregationGroupByPlanNode implements PlanNode {
AggregationFunctionColumnPair[] aggregationFunctionColumnPairs =
StarTreeUtils.extractAggregationFunctionPairs(_aggregationFunctions);
if (aggregationFunctionColumnPairs != null) {
- Map<String, List<PredicateEvaluator>> predicateEvaluatorsMap =
+ Map<String, List<CompositePredicateEvaluator>> predicateEvaluatorsMap =
StarTreeUtils.extractPredicateEvaluatorsMap(indexSegment,
queryContext.getFilter());
if (predicateEvaluatorsMap != null) {
for (StarTreeV2 starTreeV2 : starTrees) {
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 a31ec13..ec47d8e 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
@@ -22,11 +22,11 @@ import java.util.List;
import java.util.Map;
import java.util.Set;
import org.apache.pinot.common.request.context.ExpressionContext;
-import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
import org.apache.pinot.core.operator.query.AggregationOperator;
import org.apache.pinot.core.query.aggregation.function.AggregationFunction;
import
org.apache.pinot.core.query.aggregation.function.AggregationFunctionUtils;
import org.apache.pinot.core.query.request.context.QueryContext;
+import org.apache.pinot.core.startree.CompositePredicateEvaluator;
import org.apache.pinot.core.startree.StarTreeUtils;
import org.apache.pinot.core.startree.plan.StarTreeTransformPlanNode;
import org.apache.pinot.segment.spi.IndexSegment;
@@ -55,13 +55,14 @@ public class AggregationPlanNode implements PlanNode {
AggregationFunctionColumnPair[] aggregationFunctionColumnPairs =
StarTreeUtils.extractAggregationFunctionPairs(_aggregationFunctions);
if (aggregationFunctionColumnPairs != null) {
- Map<String, List<PredicateEvaluator>> predicateEvaluatorsMap =
+ Map<String, List<CompositePredicateEvaluator>> predicateEvaluatorsMap =
StarTreeUtils.extractPredicateEvaluatorsMap(indexSegment,
queryContext.getFilter());
if (predicateEvaluatorsMap != null) {
for (StarTreeV2 starTreeV2 : starTrees) {
if (StarTreeUtils.isFitForStarTree(starTreeV2.getMetadata(),
aggregationFunctionColumnPairs, null,
predicateEvaluatorsMap.keySet())) {
_transformPlanNode = null;
+
_starTreeTransformPlanNode =
new StarTreeTransformPlanNode(starTreeV2,
aggregationFunctionColumnPairs, null,
predicateEvaluatorsMap, queryContext.getDebugOptions());
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/startree/CompositePredicateEvaluator.java
b/pinot-core/src/main/java/org/apache/pinot/core/startree/CompositePredicateEvaluator.java
new file mode 100644
index 0000000..9424bc0
--- /dev/null
+++
b/pinot-core/src/main/java/org/apache/pinot/core/startree/CompositePredicateEvaluator.java
@@ -0,0 +1,57 @@
+/**
+ * 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.startree;
+
+import java.util.List;
+import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
+
+
+/**
+ * Represents a composite predicate.
+ *
+ * A composite predicate evaluator represents a single predicate evaluator or
multiple predicate evaluators conjoined
+ * with OR.
+ * Consider the given predicate: (d1 > 10 OR d1 < 50). A composite predicate
will represent two predicates -- (d1 > 10)
+ * and (d1 < 50) and represent that they are related by the operator OR.
+ */
+public class CompositePredicateEvaluator {
+ private final List<PredicateEvaluator> _predicateEvaluators;
+
+ public CompositePredicateEvaluator(List<PredicateEvaluator>
predicateEvaluators) {
+ assert !predicateEvaluators.isEmpty();
+ _predicateEvaluators = predicateEvaluators;
+ }
+
+ public List<PredicateEvaluator> getPredicateEvaluators() {
+ return _predicateEvaluators;
+ }
+
+ /**
+ * Applies a dictionary id to the composite predicate evaluator. Returns
{@code true} if the dictionary id matches any
+ * predicate evaluator, {@code false} otherwise.
+ */
+ public boolean apply(int dictId) {
+ for (PredicateEvaluator predicateEvaluator : _predicateEvaluators) {
+ if (predicateEvaluator.applySV(dictId)) {
+ return true;
+ }
+ }
+ return false;
+ }
+}
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 e80d5e3..15fa414 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
@@ -28,6 +28,7 @@ import java.util.Map;
import java.util.Queue;
import java.util.Set;
import javax.annotation.Nullable;
+import org.apache.commons.lang3.tuple.Pair;
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;
@@ -84,15 +85,20 @@ public class StarTreeUtils {
/**
* Extracts a map from the column to a list of {@link PredicateEvaluator}s
for it. Returns {@code null} if the filter
* cannot be solved by the star-tree.
+ *
+ * A predicate can be simple (d1 > 10) or composite (d1 > 10 AND d2 < 50) or
multi levelled
+ * (d1 > 50 AND (d2 > 10 OR d2 < 35)).
+ * This method represents a list of CompositePredicates per dimension. For
each dimension, all CompositePredicates in
+ * the list are implicitly ANDed together. Any OR predicates are nested
within a CompositePredicate.
*/
@Nullable
- public static Map<String, List<PredicateEvaluator>>
extractPredicateEvaluatorsMap(IndexSegment indexSegment,
+ public static Map<String, List<CompositePredicateEvaluator>>
extractPredicateEvaluatorsMap(IndexSegment indexSegment,
@Nullable FilterContext filter) {
if (filter == null) {
return Collections.emptyMap();
}
- Map<String, List<PredicateEvaluator>> predicateEvaluatorsMap = new
HashMap<>();
+ Map<String, List<CompositePredicateEvaluator>> predicateEvaluatorsMap =
new HashMap<>();
Queue<FilterContext> queue = new LinkedList<>();
queue.add(filter);
FilterContext filterNode;
@@ -102,40 +108,26 @@ public class StarTreeUtils {
queue.addAll(filterNode.getChildren());
break;
case OR:
- // Star-tree does not support OR filter
- return null;
- case PREDICATE:
- Predicate predicate = filterNode.getPredicate();
- ExpressionContext lhs = predicate.getLhs();
- if (lhs.getType() != ExpressionContext.Type.IDENTIFIER) {
- // Star-tree does not support non-identifier expression
- return null;
- }
- String column = lhs.getIdentifier();
- DataSource dataSource = indexSegment.getDataSource(column);
- Dictionary dictionary = dataSource.getDictionary();
- if (dictionary == null) {
- // Star-tree does not support non-dictionary encoded dimension
+ Pair<String, List<PredicateEvaluator>> pair =
isOrClauseValidForStarTree(indexSegment, filterNode);
+ if (pair == null) {
return null;
}
- switch (predicate.getType()) {
- // Do not use star-tree for the following predicates because:
- // - REGEXP_LIKE: Need to scan the whole dictionary to gather
the matching dictionary ids
- // - TEXT_MATCH/IS_NULL/IS_NOT_NULL: No way to gather the
matching dictionary ids
- case REGEXP_LIKE:
- case TEXT_MATCH:
- case IS_NULL:
- case IS_NOT_NULL:
- return null;
+ List<PredicateEvaluator> predicateEvaluators = pair.getRight();
+ // NOTE: Empty list means always true
+ if (!predicateEvaluators.isEmpty()) {
+ predicateEvaluatorsMap.computeIfAbsent(pair.getLeft(), k -> new
ArrayList<>())
+ .add(new CompositePredicateEvaluator(predicateEvaluators));
}
- PredicateEvaluator predicateEvaluator = PredicateEvaluatorProvider
- .getPredicateEvaluator(predicate, dictionary,
dataSource.getDataSourceMetadata().getDataType());
- if (predicateEvaluator.isAlwaysFalse()) {
- // Do not use star-tree if there is no matching record
+ break;
+ case PREDICATE:
+ Predicate predicate = filterNode.getPredicate();
+ PredicateEvaluator predicateEvaluator =
getPredicateEvaluatorForPredicate(indexSegment, predicate);
+ if (predicateEvaluator == null) {
return null;
}
if (!predicateEvaluator.isAlwaysTrue()) {
- predicateEvaluatorsMap.computeIfAbsent(column, k -> new
ArrayList<>()).add(predicateEvaluator);
+
predicateEvaluatorsMap.computeIfAbsent(predicate.getLhs().getIdentifier(), k ->
new ArrayList<>())
+ .add(new
CompositePredicateEvaluator(Collections.singletonList(predicateEvaluator)));
}
break;
default:
@@ -179,4 +171,103 @@ public class StarTreeUtils {
// Check predicate columns
return starTreeDimensions.containsAll(predicateColumns);
}
+
+ /**
+ * Evaluates whether the given OR clause is valid for StarTree processing.
+ * StarTree supports OR predicates on a single dimension only (d1 < 10 OR d1
> 50).
+ *
+ * @return The pair of single identifier and predicate evaluators applied to
it if true; {@code null} if the OR clause
+ * cannot be solved with star-tree; empty predicate evaluator list
if the OR clause always evaluates to true.
+ */
+ @Nullable
+ private static Pair<String, List<PredicateEvaluator>>
isOrClauseValidForStarTree(IndexSegment indexSegment,
+ FilterContext filter) {
+ assert filter.getType() == FilterContext.Type.OR;
+
+ List<Predicate> predicates = new ArrayList<>();
+ extractOrClausePredicates(filter, predicates);
+
+ String identifier = null;
+ List<PredicateEvaluator> predicateEvaluators = new ArrayList<>();
+ for (Predicate predicate : predicates) {
+ PredicateEvaluator predicateEvaluator =
getPredicateEvaluatorForPredicate(indexSegment, predicate);
+ if (predicateEvaluator == null) {
+ // The predicate cannot be solved with star-tree
+ return null;
+ }
+ if (predicateEvaluator.isAlwaysTrue()) {
+ // Use empty predicate evaluators to represent always true
+ return Pair.of(null, Collections.emptyList());
+ }
+ if (!predicateEvaluator.isAlwaysFalse()) {
+ String predicateIdentifier = predicate.getLhs().getIdentifier();
+ if (identifier == null) {
+ identifier = predicateIdentifier;
+ } else {
+ if (!identifier.equals(predicateIdentifier)) {
+ // The predicates are applied to multiple columns
+ return null;
+ }
+ }
+ predicateEvaluators.add(predicateEvaluator);
+ }
+ }
+ return Pair.of(identifier, predicateEvaluators);
+ }
+
+ /**
+ * Extracts the predicates under the given OR clause, returns {@code false}
if there is nested AND under OR clause.
+ */
+ private static boolean extractOrClausePredicates(FilterContext filter,
List<Predicate> predicates) {
+ assert filter.getType() == FilterContext.Type.OR;
+
+ for (FilterContext child : filter.getChildren()) {
+ switch (child.getType()) {
+ case AND:
+ return false;
+ case OR:
+ if (!extractOrClausePredicates(child, predicates)) {
+ return false;
+ }
+ case PREDICATE:
+ predicates.add(child.getPredicate());
+ break;
+ default:
+ throw new IllegalStateException();
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Returns the predicate evaluator for the given predicate, or {@code null}
if the predicate cannot be solved with
+ * star-tree.
+ */
+ @Nullable
+ private static PredicateEvaluator
getPredicateEvaluatorForPredicate(IndexSegment indexSegment, Predicate
predicate) {
+ ExpressionContext lhs = predicate.getLhs();
+ if (lhs.getType() != ExpressionContext.Type.IDENTIFIER) {
+ // Star-tree does not support non-identifier expression
+ return null;
+ }
+ String column = lhs.getIdentifier();
+ DataSource dataSource = indexSegment.getDataSource(column);
+ Dictionary dictionary = dataSource.getDictionary();
+ if (dictionary == null) {
+ // Star-tree does not support non-dictionary encoded dimension
+ return null;
+ }
+ switch (predicate.getType()) {
+ // Do not use star-tree for the following predicates because:
+ // - REGEXP_LIKE: Need to scan the whole dictionary to gather the
matching dictionary ids
+ // - TEXT_MATCH/IS_NULL/IS_NOT_NULL: No way to gather the matching
dictionary ids
+ case REGEXP_LIKE:
+ case TEXT_MATCH:
+ case IS_NULL:
+ case IS_NOT_NULL:
+ return null;
+ }
+ return PredicateEvaluatorProvider
+ .getPredicateEvaluator(predicate, dictionary,
dataSource.getDataSourceMetadata().getDataType());
+ }
}
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/startree/operator/StarTreeFilterOperator.java
b/pinot-core/src/main/java/org/apache/pinot/core/startree/operator/StarTreeFilterOperator.java
index 2872edb..20b1558 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/startree/operator/StarTreeFilterOperator.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/startree/operator/StarTreeFilterOperator.java
@@ -40,6 +40,7 @@ import
org.apache.pinot.core.operator.filter.BitmapBasedFilterOperator;
import org.apache.pinot.core.operator.filter.EmptyFilterOperator;
import org.apache.pinot.core.operator.filter.FilterOperatorUtils;
import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
+import org.apache.pinot.core.startree.CompositePredicateEvaluator;
import org.apache.pinot.segment.spi.datasource.DataSource;
import org.apache.pinot.segment.spi.index.startree.StarTree;
import org.apache.pinot.segment.spi.index.startree.StarTreeNode;
@@ -53,7 +54,8 @@ import org.roaringbitmap.buffer.MutableRoaringBitmap;
* <p>High-level algorithm:
* <ul>
* <li>
- * Traverse the filter tree and generate a map from column to a list of
{@link PredicateEvaluator}s applied to it
+ * Traverse the filter tree and generate a map from column to a list of
{@link CompositePredicateEvaluator}s applied
+ * to it
* </li>
* <li>
* Traverse the star tree index, try to match as many predicates as
possible, add the matching documents into a
@@ -75,7 +77,7 @@ import org.roaringbitmap.buffer.MutableRoaringBitmap;
* </ul>
* </li>
* <li>
- * For each remaining predicate columns, use the list of {@link
PredicateEvaluator}s to generate separate
+ * For each remaining predicate columns, use the list of {@link
CompositePredicateEvaluator}s to generate separate
* {@link BaseFilterOperator}s for it
* </li>
* <li>Conjoin all {@link BaseFilterOperator}s with AND if we have multiple
of them</li>
@@ -119,15 +121,17 @@ public class StarTreeFilterOperator extends
BaseFilterOperator {
// Star-tree
private final StarTreeV2 _starTreeV2;
// Map from column to predicate evaluators
- private final Map<String, List<PredicateEvaluator>> _predicateEvaluatorsMap;
+ private final Map<String, List<CompositePredicateEvaluator>>
_predicateEvaluatorsMap;
// Set of group-by columns
private final Set<String> _groupByColumns;
private final Map<String, String> _debugOptions;
+
boolean _resultEmpty = false;
- public StarTreeFilterOperator(StarTreeV2 starTreeV2, Map<String,
List<PredicateEvaluator>> predicateEvaluatorsMap,
- Set<String> groupByColumns, @Nullable Map<String, String> debugOptions) {
+ public StarTreeFilterOperator(StarTreeV2 starTreeV2,
+ Map<String, List<CompositePredicateEvaluator>> predicateEvaluatorsMap,
Set<String> groupByColumns,
+ @Nullable Map<String, String> debugOptions) {
_starTreeV2 = starTreeV2;
_predicateEvaluatorsMap = predicateEvaluatorsMap;
_debugOptions = debugOptions;
@@ -183,10 +187,26 @@ public class StarTreeFilterOperator extends
BaseFilterOperator {
// Add remaining predicates
for (String remainingPredicateColumn :
starTreeResult._remainingPredicateColumns) {
- List<PredicateEvaluator> predicateEvaluators =
_predicateEvaluatorsMap.get(remainingPredicateColumn);
+ List<CompositePredicateEvaluator> compositePredicateEvaluators =
+ _predicateEvaluatorsMap.get(remainingPredicateColumn);
DataSource dataSource =
_starTreeV2.getDataSource(remainingPredicateColumn);
- for (PredicateEvaluator predicateEvaluator : predicateEvaluators) {
-
childFilterOperators.add(FilterOperatorUtils.getLeafFilterOperator(predicateEvaluator,
dataSource, numDocs));
+ for (CompositePredicateEvaluator compositePredicateEvaluator :
compositePredicateEvaluators) {
+ List<PredicateEvaluator> predicateEvaluators =
compositePredicateEvaluator.getPredicateEvaluators();
+ int numPredicateEvaluators = predicateEvaluators.size();
+ if (numPredicateEvaluators == 1) {
+ // Single predicate evaluator
+ childFilterOperators
+
.add(FilterOperatorUtils.getLeafFilterOperator(predicateEvaluators.get(0),
dataSource, numDocs));
+ } else {
+ // Predicate evaluators conjoined with OR
+ List<BaseFilterOperator> orChildFilterOperators = new
ArrayList<>(numPredicateEvaluators);
+ for (PredicateEvaluator childPredicateEvaluator :
predicateEvaluators) {
+ orChildFilterOperators
+
.add(FilterOperatorUtils.getLeafFilterOperator(childPredicateEvaluator,
dataSource, numDocs));
+ }
+ childFilterOperators
+
.add(FilterOperatorUtils.getOrFilterOperator(orChildFilterOperators, numDocs,
_debugOptions));
+ }
}
}
@@ -306,61 +326,69 @@ public class StarTreeFilterOperator extends
BaseFilterOperator {
}
/**
- * Helper method to get a set of matching dictionary ids from a list of
predicate evaluators conjoined with AND.
+ * Helper method to get a set of matching dictionary ids from a list of
composite predicate evaluators conjoined with
+ * AND.
+ * <p>When there are multiple composite predicate evaluators:
* <ul>
* <li>
- * We sort all predicate evaluators with priority: EQ > IN > RANGE >
NOT_IN/NEQ > REGEXP_LIKE so that we process
- * less dictionary ids.
+ * We sort all composite predicate evaluators with priority: EQ > IN >
RANGE > NOT_IN/NEQ > REGEXP_LIKE > multiple
+ * predicate evaluators conjoined with OR so that we process less
dictionary ids.
* </li>
* <li>
- * For the first predicate evaluator, we get all the matching dictionary
ids, then apply them to other predicate
- * evaluators to get the final set of matching dictionary ids.
+ * For the first composite predicate evaluator, we get all the matching
dictionary ids, then apply them to other
+ * composite predicate evaluators to get the final set of matching
dictionary ids.
* </li>
* </ul>
*/
- private IntSet getMatchingDictIds(List<PredicateEvaluator>
predicateEvaluators) {
+ private IntSet getMatchingDictIds(List<CompositePredicateEvaluator>
compositePredicateEvaluators) {
+ int numCompositePredicateEvaluators = compositePredicateEvaluators.size();
+ if (numCompositePredicateEvaluators == 1) {
+ return getMatchingDictIds(compositePredicateEvaluators.get(0));
+ }
+
// Sort the predicate evaluators so that we process less dictionary ids
- predicateEvaluators.sort(new Comparator<PredicateEvaluator>() {
+ compositePredicateEvaluators.sort(new
Comparator<CompositePredicateEvaluator>() {
@Override
- public int compare(PredicateEvaluator o1, PredicateEvaluator o2) {
+ public int compare(CompositePredicateEvaluator o1,
CompositePredicateEvaluator o2) {
return getPriority(o1) - getPriority(o2);
}
- int getPriority(PredicateEvaluator predicateEvaluator) {
- switch (predicateEvaluator.getPredicateType()) {
- case EQ:
- return 1;
- case IN:
- return 2;
- case RANGE:
- return 3;
- case NOT_EQ:
- case NOT_IN:
- return 4;
- default:
- throw new UnsupportedOperationException();
+ int getPriority(CompositePredicateEvaluator compositePredicateEvaluator)
{
+ List<PredicateEvaluator> predicateEvaluators =
compositePredicateEvaluator.getPredicateEvaluators();
+ if (predicateEvaluators.size() == 1) {
+ switch (predicateEvaluators.get(0).getPredicateType()) {
+ case EQ:
+ return 1;
+ case IN:
+ return 2;
+ case RANGE:
+ return 3;
+ case NOT_EQ:
+ case NOT_IN:
+ return 4;
+ default:
+ throw new UnsupportedOperationException();
+ }
+ } else {
+ // Process OR at last
+ return 5;
}
}
});
// Initialize matching dictionary ids with the first predicate evaluator
- IntSet matchingDictIds = new IntOpenHashSet();
- PredicateEvaluator firstPredicateEvaluator = predicateEvaluators.get(0);
- for (int matchingDictId : firstPredicateEvaluator.getMatchingDictIds()) {
- matchingDictIds.add(matchingDictId);
- }
+ IntSet matchingDictIds =
getMatchingDictIds(compositePredicateEvaluators.get(0));
// Process other predicate evaluators
- int numPredicateEvaluators = predicateEvaluators.size();
- for (int i = 1; i < numPredicateEvaluators; i++) {
+ for (int i = 1; i < numCompositePredicateEvaluators; i++) {
// We don't need to apply other predicate evaluators if all matching
dictionary ids have already been removed
if (matchingDictIds.isEmpty()) {
return matchingDictIds;
}
- PredicateEvaluator predicateEvaluator = predicateEvaluators.get(i);
+ CompositePredicateEvaluator compositePredicateEvaluator =
compositePredicateEvaluators.get(i);
IntIterator iterator = matchingDictIds.iterator();
while (iterator.hasNext()) {
- if (!predicateEvaluator.applySV(iterator.nextInt())) {
+ if (!compositePredicateEvaluator.apply(iterator.nextInt())) {
iterator.remove();
}
}
@@ -368,4 +396,17 @@ public class StarTreeFilterOperator extends
BaseFilterOperator {
return matchingDictIds;
}
+
+ /**
+ * Returns the matching dictionary ids for the given composite predicate
evaluator.
+ */
+ private IntSet getMatchingDictIds(CompositePredicateEvaluator
compositePredicateEvaluator) {
+ IntSet matchingDictIds = new IntOpenHashSet();
+ for (PredicateEvaluator predicateEvaluator :
compositePredicateEvaluator.getPredicateEvaluators()) {
+ for (int matchingDictId : predicateEvaluator.getMatchingDictIds()) {
+ matchingDictIds.add(matchingDictId);
+ }
+ }
+ return matchingDictIds;
+ }
}
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeDocIdSetPlanNode.java
b/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeDocIdSetPlanNode.java
index a463bcd..a27e524 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeDocIdSetPlanNode.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeDocIdSetPlanNode.java
@@ -23,17 +23,18 @@ import java.util.Map;
import java.util.Set;
import javax.annotation.Nullable;
import org.apache.pinot.core.operator.DocIdSetOperator;
-import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
import org.apache.pinot.core.plan.DocIdSetPlanNode;
import org.apache.pinot.core.plan.PlanNode;
+import org.apache.pinot.core.startree.CompositePredicateEvaluator;
import org.apache.pinot.segment.spi.index.startree.StarTreeV2;
public class StarTreeDocIdSetPlanNode implements PlanNode {
private final StarTreeFilterPlanNode _starTreeFilterPlanNode;
- public StarTreeDocIdSetPlanNode(StarTreeV2 starTreeV2, Map<String,
List<PredicateEvaluator>> predicateEvaluatorsMap,
- @Nullable Set<String> groupByColumns, @Nullable Map<String, String>
debugOptions) {
+ public StarTreeDocIdSetPlanNode(StarTreeV2 starTreeV2,
+ Map<String, List<CompositePredicateEvaluator>> predicateEvaluatorsMap,
@Nullable Set<String> groupByColumns,
+ @Nullable Map<String, String> debugOptions) {
_starTreeFilterPlanNode =
new StarTreeFilterPlanNode(starTreeV2, predicateEvaluatorsMap,
groupByColumns, debugOptions);
}
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeFilterPlanNode.java
b/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeFilterPlanNode.java
index b7e38be..78a0aa4 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeFilterPlanNode.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeFilterPlanNode.java
@@ -22,20 +22,21 @@ import java.util.List;
import java.util.Map;
import java.util.Set;
import javax.annotation.Nullable;
-import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
import org.apache.pinot.core.plan.PlanNode;
+import org.apache.pinot.core.startree.CompositePredicateEvaluator;
import org.apache.pinot.core.startree.operator.StarTreeFilterOperator;
import org.apache.pinot.segment.spi.index.startree.StarTreeV2;
public class StarTreeFilterPlanNode implements PlanNode {
private final StarTreeV2 _starTreeV2;
- private final Map<String, List<PredicateEvaluator>> _predicateEvaluatorsMap;
+ private final Map<String, List<CompositePredicateEvaluator>>
_predicateEvaluatorsMap;
private final Set<String> _groupByColumns;
private final Map<String, String> _debugOptions;
- public StarTreeFilterPlanNode(StarTreeV2 starTreeV2, Map<String,
List<PredicateEvaluator>> predicateEvaluatorsMap,
- @Nullable Set<String> groupByColumns, @Nullable Map<String, String>
debugOptions) {
+ public StarTreeFilterPlanNode(StarTreeV2 starTreeV2,
+ Map<String, List<CompositePredicateEvaluator>> predicateEvaluatorsMap,
@Nullable Set<String> groupByColumns,
+ @Nullable Map<String, String> debugOptions) {
_starTreeV2 = starTreeV2;
_predicateEvaluatorsMap = predicateEvaluatorsMap;
_groupByColumns = groupByColumns;
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeProjectionPlanNode.java
b/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeProjectionPlanNode.java
index 9ab5262..b27ebcd 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeProjectionPlanNode.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeProjectionPlanNode.java
@@ -24,8 +24,8 @@ import java.util.Map;
import java.util.Set;
import javax.annotation.Nullable;
import org.apache.pinot.core.operator.ProjectionOperator;
-import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
import org.apache.pinot.core.plan.PlanNode;
+import org.apache.pinot.core.startree.CompositePredicateEvaluator;
import org.apache.pinot.segment.spi.datasource.DataSource;
import org.apache.pinot.segment.spi.index.startree.StarTreeV2;
@@ -35,7 +35,7 @@ public class StarTreeProjectionPlanNode implements PlanNode {
private final StarTreeDocIdSetPlanNode _starTreeDocIdSetPlanNode;
public StarTreeProjectionPlanNode(StarTreeV2 starTreeV2, Set<String>
projectionColumns,
- Map<String, List<PredicateEvaluator>> predicateEvaluatorsMap, @Nullable
Set<String> groupByColumns,
+ Map<String, List<CompositePredicateEvaluator>> predicateEvaluatorsMap,
@Nullable Set<String> groupByColumns,
@Nullable Map<String, String> debugOptions) {
_dataSourceMap = new HashMap<>();
for (String projectionColumn : projectionColumns) {
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeTransformPlanNode.java
b/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeTransformPlanNode.java
index 8be3e13..e7aeaef 100644
---
a/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeTransformPlanNode.java
+++
b/pinot-core/src/main/java/org/apache/pinot/core/startree/plan/StarTreeTransformPlanNode.java
@@ -26,9 +26,9 @@ import java.util.Map;
import java.util.Set;
import javax.annotation.Nullable;
import org.apache.pinot.common.request.context.ExpressionContext;
-import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
import org.apache.pinot.core.operator.transform.TransformOperator;
import org.apache.pinot.core.plan.PlanNode;
+import org.apache.pinot.core.startree.CompositePredicateEvaluator;
import
org.apache.pinot.segment.spi.index.startree.AggregationFunctionColumnPair;
import org.apache.pinot.segment.spi.index.startree.StarTreeV2;
@@ -39,7 +39,8 @@ public class StarTreeTransformPlanNode implements PlanNode {
public StarTreeTransformPlanNode(StarTreeV2 starTreeV2,
AggregationFunctionColumnPair[] aggregationFunctionColumnPairs,
@Nullable ExpressionContext[] groupByExpressions,
- Map<String, List<PredicateEvaluator>> predicateEvaluatorsMap, @Nullable
Map<String, String> debugOptions) {
+ Map<String, List<CompositePredicateEvaluator>> predicateEvaluatorsMap,
+ @Nullable Map<String, String> debugOptions) {
Set<String> projectionColumns = new HashSet<>();
for (AggregationFunctionColumnPair aggregationFunctionColumnPair :
aggregationFunctionColumnPairs) {
projectionColumns.add(aggregationFunctionColumnPair.toColumnName());
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 2e9de2b..648934e 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
@@ -33,12 +33,12 @@ import org.apache.commons.io.FileUtils;
import org.apache.pinot.common.request.context.ExpressionContext;
import org.apache.pinot.common.request.context.FilterContext;
import org.apache.pinot.core.common.BlockDocIdIterator;
-import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
import org.apache.pinot.core.plan.FilterPlanNode;
import org.apache.pinot.core.plan.PlanNode;
import org.apache.pinot.core.query.aggregation.function.AggregationFunction;
import org.apache.pinot.core.query.request.context.QueryContext;
import
org.apache.pinot.core.query.request.context.utils.QueryContextConverterUtils;
+import org.apache.pinot.core.startree.CompositePredicateEvaluator;
import org.apache.pinot.core.startree.StarTreeUtils;
import org.apache.pinot.core.startree.plan.StarTreeFilterPlanNode;
import org.apache.pinot.segment.local.aggregator.ValueAggregator;
@@ -94,7 +94,15 @@ abstract class BaseStarTreeV2Test<R, A> {
private static final String DIMENSION_D2 = "d2";
private static final int DIMENSION_CARDINALITY = 100;
private static final String METRIC = "m";
- private static final String QUERY_FILTER = " WHERE d1 = 0 AND d2 < 10";
+ private static final String QUERY_FILTER_AND = " WHERE d1 = 0 AND d2 < 10";
+ // StarTree supports OR predicates only on a single dimension
+ private static final String QUERY_FILTER_OR = " WHERE d1 > 10 OR d1 < 50";
+ private static final String QUERY_FILTER_COMPLEX_OR_MULTIPLE_DIMENSIONS = "
WHERE d2 < 95 AND (d1 > 10 OR d1 < 50)";
+ private static final String
QUERY_FILTER_COMPLEX_AND_MULTIPLE_DIMENSIONS_THREE_PREDICATES =
+ " WHERE d2 < 95 AND d2 > 25 AND (d1 > 10 OR d1 < 50)";
+ private static final String
QUERY_FILTER_COMPLEX_OR_MULTIPLE_DIMENSIONS_THREE_PREDICATES =
+ " WHERE (d2 > 95 OR d2 < 25) AND (d1 > 10 OR d1 < 50)";
+ private static final String QUERY_FILTER_COMPLEX_OR_SINGLE_DIMENSION = "
WHERE d1 = 95 AND (d1 > 90 OR d1 < 100)";
private static final String QUERY_GROUP_BY = " GROUP BY d2";
private ValueAggregator _valueAggregator;
@@ -170,9 +178,19 @@ abstract class BaseStarTreeV2Test<R, A> {
String baseQuery = String.format("SELECT %s FROM %s", aggregation,
TABLE_NAME);
testQuery(baseQuery);
- testQuery(baseQuery + QUERY_FILTER);
+ testQuery(baseQuery + QUERY_FILTER_AND);
+ testQuery(baseQuery + QUERY_FILTER_OR);
+ testQuery(baseQuery + QUERY_FILTER_COMPLEX_OR_MULTIPLE_DIMENSIONS);
+ testQuery(baseQuery +
QUERY_FILTER_COMPLEX_AND_MULTIPLE_DIMENSIONS_THREE_PREDICATES);
+ testQuery(baseQuery +
QUERY_FILTER_COMPLEX_OR_MULTIPLE_DIMENSIONS_THREE_PREDICATES);
+ testQuery(baseQuery + QUERY_FILTER_COMPLEX_OR_SINGLE_DIMENSION);
testQuery(baseQuery + QUERY_GROUP_BY);
- testQuery(baseQuery + QUERY_FILTER + QUERY_GROUP_BY);
+ testQuery(baseQuery + QUERY_FILTER_AND + QUERY_GROUP_BY);
+ testQuery(baseQuery + QUERY_FILTER_OR + QUERY_GROUP_BY);
+ testQuery(baseQuery + QUERY_FILTER_COMPLEX_OR_MULTIPLE_DIMENSIONS +
QUERY_GROUP_BY);
+ testQuery(baseQuery +
QUERY_FILTER_COMPLEX_OR_MULTIPLE_DIMENSIONS_THREE_PREDICATES + QUERY_GROUP_BY);
+ testQuery(baseQuery +
QUERY_FILTER_COMPLEX_AND_MULTIPLE_DIMENSIONS_THREE_PREDICATES + QUERY_GROUP_BY);
+ testQuery(baseQuery + QUERY_FILTER_COMPLEX_OR_SINGLE_DIMENSION +
QUERY_GROUP_BY);
}
@AfterClass
@@ -207,7 +225,7 @@ abstract class BaseStarTreeV2Test<R, A> {
// Filter
FilterContext filter = queryContext.getFilter();
- Map<String, List<PredicateEvaluator>> predicateEvaluatorsMap =
+ Map<String, List<CompositePredicateEvaluator>> predicateEvaluatorsMap =
StarTreeUtils.extractPredicateEvaluatorsMap(_indexSegment, filter);
assertNotNull(predicateEvaluatorsMap);
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
