mihaibudiu commented on code in PR #4324:
URL: https://github.com/apache/calcite/pull/4324#discussion_r2064160316
##########
core/src/main/java/org/apache/calcite/rex/RexUtil.java:
##########
@@ -2799,6 +2800,175 @@ private RexNode or(Iterable<? extends RexNode> nodes) {
}
}
+ /**
+ * Helper class that expands predicates from disjunctions (splited by K).
+ *
+ * @param <K> The dimension used to split predicates in disjunctions. If you
want to expand
+ * predicates that can be pushed down to a single table from the
disjunction, K is
+ * {@link RelTableRef}; if you want to expand predicates that can
be pushed down to
+ * Join inputs from the disjunction, K is string whose value is
'left' or 'right'.
+ */
+ public abstract static class ExpandDisjunctionHelper<K> {
+ private final RelBuilder relBuilder;
+
+ private final int maxNodeCount;
+
+ // Used to record the number of redundant expressions expanded.
Review Comment:
Is this the increase of the expression size?
Maybe that's what it should be called "expressionIncreaseAmount"
##########
core/src/main/java/org/apache/calcite/rel/rules/ExpandDisjunctionForTableRule.java:
##########
@@ -207,86 +204,35 @@ private static void
matchJoin(ExpandDisjunctionForTableRule rule, RelOptRuleCall
/**
* Helper class to expand predicates.
*/
- private static class ExpandDisjunctionForTableHelper {
+ private static class ExpandDisjunctionForTableHelper
+ extends RexUtil.ExpandDisjunctionHelper<RexTableInputRef.RelTableRef> {
private final Map<Integer, RexTableInputRef.RelTableRef>
inputRefToTableRef;
- private final RelBuilder relBuilder;
-
- private final int maxNodeCount;
-
- // Used to record the number of redundant expressions expanded.
- private int currentCount;
-
private ExpandDisjunctionForTableHelper(
Map<Integer, RexTableInputRef.RelTableRef> inputRefToTableRef,
RelBuilder relBuilder,
int maxNodeCount) {
+ super(relBuilder, maxNodeCount);
this.inputRefToTableRef = inputRefToTableRef;
- this.relBuilder = relBuilder;
- this.maxNodeCount = maxNodeCount;
}
- private Map<RexTableInputRef.RelTableRef, RexNode> expand(RexNode
condition) {
- try {
- this.currentCount = 0;
- return expandDeep(condition);
- } catch (OverLimitException e) {
- return new HashMap<>();
- }
- }
-
- /**
- * Expand predicates recursively that can be pushed down to single table.
- *
- * @param condition Predicate to be expanded
- * @return A map from a table to a (combined) predicate that can be
pushed down
- * and only depends on columns of the table
- */
- private Map<RexTableInputRef.RelTableRef, RexNode> expandDeep(RexNode
condition) {
- Map<RexTableInputRef.RelTableRef, RexNode> additionalConditions = new
HashMap<>();
-
+ @Override protected boolean canEarlyReturn(
Review Comment:
canReturnEarly sounds a little better.
##########
core/src/main/java/org/apache/calcite/rex/RexUtil.java:
##########
@@ -2799,6 +2800,175 @@ private RexNode or(Iterable<? extends RexNode> nodes) {
}
}
+ /**
+ * Helper class that expands predicates from disjunctions (splited by K).
+ *
+ * @param <K> The dimension used to split predicates in disjunctions. If you
want to expand
+ * predicates that can be pushed down to a single table from the
disjunction, K is
+ * {@link RelTableRef}; if you want to expand predicates that can
be pushed down to
+ * Join inputs from the disjunction, K is string whose value is
'left' or 'right'.
+ */
+ public abstract static class ExpandDisjunctionHelper<K> {
+ private final RelBuilder relBuilder;
+
+ private final int maxNodeCount;
+
+ // Used to record the number of redundant expressions expanded.
+ private int currentCount;
+
+ public ExpandDisjunctionHelper(RelBuilder relBuilder, int maxNodeCount) {
+ this.relBuilder = relBuilder;
+ this.maxNodeCount = maxNodeCount;
+ }
+
+ public Map<K, RexNode> expand(RexNode condition) {
+ try {
+ this.currentCount = 0;
+ return expandDeep(condition);
+ } catch (OverLimitException e) {
+ return new HashMap<>();
+ }
+ }
+
+ /**
+ * Expand predicates recursively that can be pushed down to a single K.
+ *
+ * @param condition Predicate to be expanded
+ * @return A map from a K to a (combined) predicate that can be pushed
down
+ * and only depends on columns of K.
+ */
+ private Map<K, RexNode> expandDeep(RexNode condition) {
+ final Map<K, RexNode> additionalConditions = new HashMap<>();
+
+ if (canEarlyReturn(condition, additionalConditions)) {
+ return additionalConditions;
+ }
+
+ // Recursively expand the expression according to whether it is a
conjunction
+ // or a disjunction. If it is neither a disjunction nor a conjunction,
it cannot
+ // be expanded further and an empty Map is returned.
+ switch (condition.getKind()) {
+ case AND:
+ List<RexNode> andOperands = RexUtil.flattenAnd(((RexCall)
condition).getOperands());
+ for (RexNode andOperand : andOperands) {
+ Map<K, RexNode> operandResult = expandDeep(andOperand);
+ combinePredicatesUsingAnd(additionalConditions, operandResult);
+ }
+ break;
+ case OR:
+ List<RexNode> orOperands = RexUtil.flattenOr(((RexCall)
condition).getOperands());
+ additionalConditions.putAll(expandDeep(orOperands.get(0)));
+ for (int i = 1; i < orOperands.size(); i++) {
+ Map<K, RexNode> operandResult = expandDeep(orOperands.get(i));
+ combinePredicatesUsingOr(additionalConditions, operandResult);
+
+ if (additionalConditions.isEmpty()) {
+ break;
+ }
+ }
+ break;
+ default:
+ break;
+ }
+
+ return additionalConditions;
+ }
+
+ // If condition already belongs to a certain K, return early.
+ protected abstract boolean canEarlyReturn(RexNode condition,
+ Map<K, RexNode> additionalConditions);
+
+ /**
+ * Combine predicates that depend on the same K using conjunctions.
+ * The result is returned by modifying baseMap. For example:
+ *
+ * <p>baseMap: {k1: p1, k2: p2}
+ *
+ * <p>forMergeMap: {k1: p11, k3: p3}
+ *
+ * <p>result: {k1: p1 AND p11, k2: p2, k3: p3}
+ *
+ * @param baseMap Additional predicates that current conjunction has
already saved
+ * @param forMergeMap Additional predicates that current operand has
expanded
+ */
+ private void combinePredicatesUsingAnd(
+ Map<K, RexNode> baseMap,
+ Map<K, RexNode> forMergeMap) {
+ for (Map.Entry<K, RexNode> entry : forMergeMap.entrySet()) {
+ RexNode mergedRex =
+ relBuilder.and(
+ entry.getValue(),
+ baseMap.getOrDefault(entry.getKey(),
relBuilder.literal(true)));
+ int oriCount = entry.getValue().nodeCount()
Review Comment:
originalCount?
##########
core/src/main/java/org/apache/calcite/rex/RexUtil.java:
##########
@@ -2799,6 +2800,175 @@ private RexNode or(Iterable<? extends RexNode> nodes) {
}
}
+ /**
+ * Helper class that expands predicates from disjunctions (splited by K).
+ *
+ * @param <K> The dimension used to split predicates in disjunctions. If you
want to expand
+ * predicates that can be pushed down to a single table from the
disjunction, K is
+ * {@link RelTableRef}; if you want to expand predicates that can
be pushed down to
+ * Join inputs from the disjunction, K is string whose value is
'left' or 'right'.
+ */
+ public abstract static class ExpandDisjunctionHelper<K> {
+ private final RelBuilder relBuilder;
+
+ private final int maxNodeCount;
+
+ // Used to record the number of redundant expressions expanded.
+ private int currentCount;
+
+ public ExpandDisjunctionHelper(RelBuilder relBuilder, int maxNodeCount) {
+ this.relBuilder = relBuilder;
+ this.maxNodeCount = maxNodeCount;
+ }
+
+ public Map<K, RexNode> expand(RexNode condition) {
+ try {
+ this.currentCount = 0;
+ return expandDeep(condition);
+ } catch (OverLimitException e) {
+ return new HashMap<>();
+ }
+ }
+
+ /**
+ * Expand predicates recursively that can be pushed down to a single K.
+ *
+ * @param condition Predicate to be expanded
Review Comment:
can you add a java doc for K?
I know it's present above, but it's worth repeating.
##########
core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java:
##########
@@ -10447,4 +10447,41 @@ private void
checkLoptOptimizeJoinRule(LoptOptimizeJoinRule rule) {
.withRule(CoreRules.MINUS_TO_FILTER)
.check();
}
+
+ @Test void testExpandFilterDisjunctionForJoinInput() {
Review Comment:
this could really benefit from some quidem tests, using the new capability
of specifying optimizations
##########
core/src/main/java/org/apache/calcite/rex/RexUtil.java:
##########
@@ -2799,6 +2800,175 @@ private RexNode or(Iterable<? extends RexNode> nodes) {
}
}
+ /**
+ * Helper class that expands predicates from disjunctions (splited by K).
+ *
+ * @param <K> The dimension used to split predicates in disjunctions. If you
want to expand
+ * predicates that can be pushed down to a single table from the
disjunction, K is
+ * {@link RelTableRef}; if you want to expand predicates that can
be pushed down to
+ * Join inputs from the disjunction, K is string whose value is
'left' or 'right'.
+ */
+ public abstract static class ExpandDisjunctionHelper<K> {
+ private final RelBuilder relBuilder;
+
+ private final int maxNodeCount;
+
+ // Used to record the number of redundant expressions expanded.
+ private int currentCount;
+
+ public ExpandDisjunctionHelper(RelBuilder relBuilder, int maxNodeCount) {
+ this.relBuilder = relBuilder;
+ this.maxNodeCount = maxNodeCount;
+ }
+
+ public Map<K, RexNode> expand(RexNode condition) {
+ try {
+ this.currentCount = 0;
+ return expandDeep(condition);
+ } catch (OverLimitException e) {
+ return new HashMap<>();
+ }
+ }
+
+ /**
+ * Expand predicates recursively that can be pushed down to a single K.
+ *
+ * @param condition Predicate to be expanded
+ * @return A map from a K to a (combined) predicate that can be pushed
down
+ * and only depends on columns of K.
+ */
+ private Map<K, RexNode> expandDeep(RexNode condition) {
+ final Map<K, RexNode> additionalConditions = new HashMap<>();
+
+ if (canEarlyReturn(condition, additionalConditions)) {
+ return additionalConditions;
+ }
+
+ // Recursively expand the expression according to whether it is a
conjunction
+ // or a disjunction. If it is neither a disjunction nor a conjunction,
it cannot
+ // be expanded further and an empty Map is returned.
+ switch (condition.getKind()) {
+ case AND:
+ List<RexNode> andOperands = RexUtil.flattenAnd(((RexCall)
condition).getOperands());
+ for (RexNode andOperand : andOperands) {
+ Map<K, RexNode> operandResult = expandDeep(andOperand);
+ combinePredicatesUsingAnd(additionalConditions, operandResult);
+ }
+ break;
+ case OR:
+ List<RexNode> orOperands = RexUtil.flattenOr(((RexCall)
condition).getOperands());
+ additionalConditions.putAll(expandDeep(orOperands.get(0)));
+ for (int i = 1; i < orOperands.size(); i++) {
+ Map<K, RexNode> operandResult = expandDeep(orOperands.get(i));
+ combinePredicatesUsingOr(additionalConditions, operandResult);
+
+ if (additionalConditions.isEmpty()) {
+ break;
+ }
+ }
+ break;
+ default:
+ break;
+ }
+
+ return additionalConditions;
+ }
+
+ // If condition already belongs to a certain K, return early.
+ protected abstract boolean canEarlyReturn(RexNode condition,
+ Map<K, RexNode> additionalConditions);
+
+ /**
+ * Combine predicates that depend on the same K using conjunctions.
+ * The result is returned by modifying baseMap. For example:
+ *
+ * <p>baseMap: {k1: p1, k2: p2}
+ *
+ * <p>forMergeMap: {k1: p11, k3: p3}
+ *
+ * <p>result: {k1: p1 AND p11, k2: p2, k3: p3}
+ *
+ * @param baseMap Additional predicates that current conjunction has
already saved
+ * @param forMergeMap Additional predicates that current operand has
expanded
+ */
+ private void combinePredicatesUsingAnd(
+ Map<K, RexNode> baseMap,
+ Map<K, RexNode> forMergeMap) {
+ for (Map.Entry<K, RexNode> entry : forMergeMap.entrySet()) {
+ RexNode mergedRex =
+ relBuilder.and(
+ entry.getValue(),
+ baseMap.getOrDefault(entry.getKey(),
relBuilder.literal(true)));
+ int oriCount = entry.getValue().nodeCount()
+ + (baseMap.containsKey(entry.getKey())
+ ? baseMap.get(entry.getKey()).nodeCount()
+ : 0);
+ checkExpandCount(mergedRex.nodeCount() - oriCount);
+ baseMap.put(entry.getKey(), mergedRex);
+ }
+ }
+
+ /**
+ * Combine predicates that depend on the same K using disjunctions.
+ * The result is returned by modifying baseMap. For example:
+ *
+ * <p>baseMap: {k1: p1, k2: p2}
+ *
+ * <p>forMergeMap: {k1: p11, k3: p3}
+ *
+ * <p>result: {k1: p1 OR p11}
+ *
+ * @param baseMap Additional predicates that current disjunction has
already saved
+ * @param forMergeMap Additional predicates that current operand has
expanded
+ */
+ private void combinePredicatesUsingOr(
+ Map<K, RexNode> baseMap,
+ Map<K, RexNode> forMergeMap) {
+ if (baseMap.isEmpty()) {
+ return;
+ }
+
+ Iterator<Map.Entry<K, RexNode>> iterator =
+ baseMap.entrySet().iterator();
+ while (iterator.hasNext()) {
+ int forMergeNodeCount = 0;
+
+ Map.Entry<K, RexNode> entry = iterator.next();
+ if (!forMergeMap.containsKey(entry.getKey())) {
+ checkExpandCount(-entry.getValue().nodeCount());
+ iterator.remove();
+ continue;
+ } else {
+ forMergeNodeCount = forMergeMap.get(entry.getKey()).nodeCount();
+ }
+ RexNode mergedRex =
+ relBuilder.or(
+ entry.getValue(),
+ forMergeMap.get(entry.getKey()));
+ int oriCount = entry.getValue().nodeCount() + forMergeNodeCount;
+ checkExpandCount(mergedRex.nodeCount() - oriCount);
+ baseMap.put(entry.getKey(), mergedRex);
+ }
+ }
+
+ /**
+ * Check whether the number of redundant expressions generated in the
expansion
+ * exceeds the limit.
+ */
+ protected void checkExpandCount(int changeCount) {
+ currentCount += changeCount;
+ if (maxNodeCount > 0 && currentCount > maxNodeCount) {
+ throw OverLimitException.INSTANCE;
+ }
+ }
+
+ /** Exception to catch when we pass the limit. */
+ private static class OverLimitException extends ControlFlowException {
Review Comment:
I think I saw similar exception used elsewhere. Is there a public version
you could use?
private is fine, but if we can reuse something, maybe we should.
Why do you need to subclass ControlFlowException and you can't just reuse
it? Could be thrown elsewhere?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
