silundong commented on code in PR #4324:
URL: https://github.com/apache/calcite/pull/4324#discussion_r2065169285
##########
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:
I've seen other places use it through subclass extends, maybe that makes it
easier to understand why the exception is thrown. There's an OverflowError in
CnfHelper, which also prevents combinatorial explosion. Maybe a common
exception can be abstracted under RexUtil, which can be used by both CnfHelper
and ExpandDisjunctionHelper?
##########
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've seen other places use it through subclass extends, maybe that makes it
easier to understand why the exception is thrown. There's an OverflowError in
CnfHelper, which also prevents combinatorial explosion. Maybe a common
exception can be abstracted under RexUtil, which can be used by both CnfHelper
and ExpandDisjunctionHelper?
--
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]
