asolimando commented on code in PR #4324: URL: https://github.com/apache/calcite/pull/4324#discussion_r2055973338
########## core/src/main/java/org/apache/calcite/rel/rules/ExpandDisjunctionForJoinInputsRule.java: ########## @@ -0,0 +1,388 @@ +/* + * 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.calcite.rel.rules; + +import org.apache.calcite.plan.RelOptRuleCall; +import org.apache.calcite.plan.RelOptUtil; +import org.apache.calcite.plan.RelRule; +import org.apache.calcite.rel.core.Filter; +import org.apache.calcite.rel.core.Join; +import org.apache.calcite.rex.RexCall; +import org.apache.calcite.rex.RexNode; +import org.apache.calcite.rex.RexUtil; +import org.apache.calcite.tools.RelBuilder; +import org.apache.calcite.util.ControlFlowException; +import org.apache.calcite.util.ImmutableBitSet; + +import org.immutables.value.Value; + +import java.util.HashMap; +import java.util.Iterator; +import java.util.List; +import java.util.Map; + +/** + * Rule to expand disjunction for join inputs in condition of a {@link Filter} or {@link Join}. + * For example: + * + * <blockquote><pre>{@code + * select t1.id from t1, t2, t3 + * where t1.id = t2.id + * and t1.id = t3.id + * and ( + * (t1.age < 50 and t3.age > 20) + * or + * (t2.weight > 70 and t3.height < 180) + * ) + * }</pre></blockquote> + * + * <p>we can expand to obtain the condition + * + * <blockquote><pre>{@code + * select t1.id from t1, t2, t3 + * where t1.id = t2.id + * and t1.id = t3.id + * and ( + * (t1.age < 50 and t3.age > 20) + * or + * (t2.weight > 70 and t3.height < 180) + * ) + * and (t1.age < 50 or t2.weight > 70) + * and (t3.age > 20 or t3.height < 180) + * }</pre></blockquote> + * + * <p>new generated predicates are redundant, but they could be pushed down to + * join inputs([t1, t2], [t3]) and reduce the cardinality. + * + * <p>Note: This rule is similar to the {@link ExpandDisjunctionForTableRule}, + * but this rule divides the predicates by Join inputs. + * + * @see CoreRules#EXPAND_FILTER_DISJUNCTION_LOCAL + * @see CoreRules#EXPAND_JOIN_DISJUNCTION_LOCAL + */ [email protected] +public class ExpandDisjunctionForJoinInputsRule + extends RelRule<ExpandDisjunctionForJoinInputsRule.Config> + implements TransformationRule { + + /** + * Creates a ExpandDisjunctionForJoinInputsRule. + */ + protected ExpandDisjunctionForJoinInputsRule(Config config) { + super(config); + } + + @Override public void onMatch(RelOptRuleCall call) { + config.matchHandler().accept(this, call); + } + + private static void matchFilter(ExpandDisjunctionForJoinInputsRule rule, RelOptRuleCall call) { + Filter filter = call.rel(0); + Join join = call.rel(1); + RelBuilder builder = call.builder(); + + ExpandDisjunctionForJoinInputsHelper helper = + new ExpandDisjunctionForJoinInputsHelper( + join.getLeft().getRowType().getFieldCount(), + join.getRight().getRowType().getFieldCount(), + join.getJoinType().canPushLeftFromAbove(), + join.getJoinType().canPushRightFromAbove(), + builder, + rule.config.bloat()); + Map<String, RexNode> expandResult = helper.expand(filter.getCondition()); + + RexNode newCondition = + builder.and( + filter.getCondition(), + expandResult.getOrDefault(helper.LEFT_KEY, builder.literal(true)), + expandResult.getOrDefault(helper.RIGHT_KEY, builder.literal(true))); + if (newCondition.equals(filter.getCondition())) { + return; + } + Filter newFilter = filter.copy(filter.getTraitSet(), join, newCondition); + call.transformTo(newFilter); + } + + private static void matchJoin(ExpandDisjunctionForJoinInputsRule rule, RelOptRuleCall call) { + Join join = call.rel(0); + RelBuilder builder = call.builder(); + + ExpandDisjunctionForJoinInputsHelper helper = + new ExpandDisjunctionForJoinInputsHelper( + join.getLeft().getRowType().getFieldCount(), + join.getRight().getRowType().getFieldCount(), + join.getJoinType().canPushLeftFromWithin(), + join.getJoinType().canPushRightFromWithin(), + builder, + rule.config.bloat()); + Map<String, RexNode> expandResult = helper.expand(join.getCondition()); + + RexNode newCondition = + call.builder().and( + join.getCondition(), + expandResult.getOrDefault(helper.LEFT_KEY, builder.literal(true)), + expandResult.getOrDefault(helper.RIGHT_KEY, builder.literal(true))); + if (newCondition.equals(join.getCondition())) { + return; + } + Join newJoin = + join.copy( + join.getTraitSet(), + newCondition, + join.getLeft(), + join.getRight(), + join.getJoinType(), + join.isSemiJoinDone()); + call.transformTo(newJoin); + } + + /** + * Helper class to expand predicates. + */ + private static class ExpandDisjunctionForJoinInputsHelper { + + private final ImmutableBitSet leftBitmap; + + private final ImmutableBitSet rightBitmap; + + private final boolean canPushLeft; + + private final boolean canPushRight; + + private final RelBuilder relBuilder; + + private final int maxNodeCount; + + // Used to record the number of redundant expressions expanded. + private int currentCount; + + private static final String LEFT_KEY = "left"; + + private static final String RIGHT_KEY = "right"; + + private ExpandDisjunctionForJoinInputsHelper( + int leftFieldCount, + int rightFieldCount, + boolean canPushLeft, + boolean canPushRight, + RelBuilder relBuilder, + int maxNodeCount) { + this.leftBitmap = ImmutableBitSet.range(0, leftFieldCount); + this.rightBitmap = ImmutableBitSet.range(leftFieldCount, leftFieldCount + rightFieldCount); + this.canPushLeft = canPushLeft; + this.canPushRight = canPushRight; + this.relBuilder = relBuilder; + this.maxNodeCount = maxNodeCount; + } + + private Map<String, 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 Join inputs. + * + * @param condition Predicate to be expanded + * @return A map from Join left/right input to a (combined) predicate that can be pushed down + * and only depends on columns of the join inputs. Review Comment: Maybe the extra "one" makes it more precise? ```suggestion * and only depends on columns of one the join inputs. ``` ########## core/src/main/java/org/apache/calcite/rel/rules/ExpandDisjunctionForJoinInputsRule.java: ########## @@ -0,0 +1,388 @@ +/* + * 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.calcite.rel.rules; + +import org.apache.calcite.plan.RelOptRuleCall; +import org.apache.calcite.plan.RelOptUtil; +import org.apache.calcite.plan.RelRule; +import org.apache.calcite.rel.core.Filter; +import org.apache.calcite.rel.core.Join; +import org.apache.calcite.rex.RexCall; +import org.apache.calcite.rex.RexNode; +import org.apache.calcite.rex.RexUtil; +import org.apache.calcite.tools.RelBuilder; +import org.apache.calcite.util.ControlFlowException; +import org.apache.calcite.util.ImmutableBitSet; + +import org.immutables.value.Value; + +import java.util.HashMap; +import java.util.Iterator; +import java.util.List; +import java.util.Map; + +/** + * Rule to expand disjunction for join inputs in condition of a {@link Filter} or {@link Join}. + * For example: + * + * <blockquote><pre>{@code + * select t1.id from t1, t2, t3 + * where t1.id = t2.id + * and t1.id = t3.id + * and ( + * (t1.age < 50 and t3.age > 20) + * or + * (t2.weight > 70 and t3.height < 180) + * ) + * }</pre></blockquote> + * + * <p>we can expand to obtain the condition + * + * <blockquote><pre>{@code + * select t1.id from t1, t2, t3 + * where t1.id = t2.id + * and t1.id = t3.id + * and ( + * (t1.age < 50 and t3.age > 20) + * or + * (t2.weight > 70 and t3.height < 180) + * ) + * and (t1.age < 50 or t2.weight > 70) + * and (t3.age > 20 or t3.height < 180) + * }</pre></blockquote> + * + * <p>new generated predicates are redundant, but they could be pushed down to + * join inputs([t1, t2], [t3]) and reduce the cardinality. + * + * <p>Note: This rule is similar to the {@link ExpandDisjunctionForTableRule}, + * but this rule divides the predicates by Join inputs. + * + * @see CoreRules#EXPAND_FILTER_DISJUNCTION_LOCAL + * @see CoreRules#EXPAND_JOIN_DISJUNCTION_LOCAL + */ [email protected] +public class ExpandDisjunctionForJoinInputsRule + extends RelRule<ExpandDisjunctionForJoinInputsRule.Config> + implements TransformationRule { + + /** + * Creates a ExpandDisjunctionForJoinInputsRule. + */ + protected ExpandDisjunctionForJoinInputsRule(Config config) { + super(config); + } + + @Override public void onMatch(RelOptRuleCall call) { + config.matchHandler().accept(this, call); + } + + private static void matchFilter(ExpandDisjunctionForJoinInputsRule rule, RelOptRuleCall call) { + Filter filter = call.rel(0); + Join join = call.rel(1); + RelBuilder builder = call.builder(); + + ExpandDisjunctionForJoinInputsHelper helper = + new ExpandDisjunctionForJoinInputsHelper( + join.getLeft().getRowType().getFieldCount(), + join.getRight().getRowType().getFieldCount(), + join.getJoinType().canPushLeftFromAbove(), + join.getJoinType().canPushRightFromAbove(), + builder, + rule.config.bloat()); + Map<String, RexNode> expandResult = helper.expand(filter.getCondition()); + + RexNode newCondition = + builder.and( + filter.getCondition(), + expandResult.getOrDefault(helper.LEFT_KEY, builder.literal(true)), + expandResult.getOrDefault(helper.RIGHT_KEY, builder.literal(true))); + if (newCondition.equals(filter.getCondition())) { + return; + } + Filter newFilter = filter.copy(filter.getTraitSet(), join, newCondition); + call.transformTo(newFilter); + } + + private static void matchJoin(ExpandDisjunctionForJoinInputsRule rule, RelOptRuleCall call) { + Join join = call.rel(0); + RelBuilder builder = call.builder(); + + ExpandDisjunctionForJoinInputsHelper helper = + new ExpandDisjunctionForJoinInputsHelper( + join.getLeft().getRowType().getFieldCount(), + join.getRight().getRowType().getFieldCount(), + join.getJoinType().canPushLeftFromWithin(), + join.getJoinType().canPushRightFromWithin(), + builder, + rule.config.bloat()); + Map<String, RexNode> expandResult = helper.expand(join.getCondition()); + + RexNode newCondition = + call.builder().and( + join.getCondition(), + expandResult.getOrDefault(helper.LEFT_KEY, builder.literal(true)), + expandResult.getOrDefault(helper.RIGHT_KEY, builder.literal(true))); + if (newCondition.equals(join.getCondition())) { + return; + } + Join newJoin = + join.copy( + join.getTraitSet(), + newCondition, + join.getLeft(), + join.getRight(), + join.getJoinType(), + join.isSemiJoinDone()); + call.transformTo(newJoin); + } + + /** + * Helper class to expand predicates. + */ + private static class ExpandDisjunctionForJoinInputsHelper { + + private final ImmutableBitSet leftBitmap; + + private final ImmutableBitSet rightBitmap; + + private final boolean canPushLeft; + + private final boolean canPushRight; + + private final RelBuilder relBuilder; + + private final int maxNodeCount; + + // Used to record the number of redundant expressions expanded. + private int currentCount; + + private static final String LEFT_KEY = "left"; + + private static final String RIGHT_KEY = "right"; + + private ExpandDisjunctionForJoinInputsHelper( + int leftFieldCount, + int rightFieldCount, + boolean canPushLeft, + boolean canPushRight, + RelBuilder relBuilder, + int maxNodeCount) { + this.leftBitmap = ImmutableBitSet.range(0, leftFieldCount); + this.rightBitmap = ImmutableBitSet.range(leftFieldCount, leftFieldCount + rightFieldCount); + this.canPushLeft = canPushLeft; + this.canPushRight = canPushRight; + this.relBuilder = relBuilder; + this.maxNodeCount = maxNodeCount; + } + + private Map<String, 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 Join inputs. + * + * @param condition Predicate to be expanded + * @return A map from Join left/right input to a (combined) predicate that can be pushed down + * and only depends on columns of the join inputs. + */ + private Map<String, RexNode> expandDeep(RexNode condition) { + final Map<String, RexNode> additionalConditions = new HashMap<>(); + boolean earlyReturn = false; + + ImmutableBitSet inputRefs = RelOptUtil.InputFinder.bits(condition); + if (inputRefs.isEmpty()) { + earlyReturn = true; + } + if (!inputRefs.isEmpty() && leftBitmap.contains(inputRefs)) { + earlyReturn = true; + if (canPushLeft) { + // The condition already belongs to the left input and it can be pushed down. + checkExpandCount(condition.nodeCount()); + additionalConditions.put(LEFT_KEY, condition); + } + } + if (!inputRefs.isEmpty() && rightBitmap.contains(inputRefs)) { + earlyReturn = true; + if (canPushRight) { + // The condition already belongs to the right input and it can be pushed down. + checkExpandCount(condition.nodeCount()); + additionalConditions.put(RIGHT_KEY, condition); + } + } + if (earlyReturn) { + return additionalConditions; + } + + switch (condition.getKind()) { + case AND: + List<RexNode> andOperands = RexUtil.flattenAnd(((RexCall) condition).getOperands()); + for (RexNode andOperand : andOperands) { + Map<String, 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<String, RexNode> operandResult = expandDeep(orOperands.get(i)); + combinePredicatesUsingOr(additionalConditions, operandResult); + + if (additionalConditions.isEmpty()) { + break; + } + } + break; + default: + break; + } + + return additionalConditions; + } + + /** + * Combine predicates that depend on the same side of Join inputs using conjunctions. + * The result is returned by modifying baseMap. For example: + * + * <p>baseMap: {left: p1, right: p2} + * + * <p>forMergeMap: {left: p3, right: p4} + * + * <p>result: {left: p1 and p3, right: p2 and p4} + * + * @param baseMap Additional predicates that current conjunction has already saved + * @param forMergeMap Additional predicates that current operand has expanded + */ + private void combinePredicatesUsingAnd( + Map<String, RexNode> baseMap, + Map<String, RexNode> forMergeMap) { + for (Map.Entry<String, 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 side of Join inputs using disjunctions. + * The result is returned by modifying baseMap. For example: + * + * <p>baseMap: {left: p1, right: p2} + * + * <p>forMergeMap: {left: p3} + * + * <p>result: {left: p1 or p3} + * + * @param baseMap Additional predicates that current disjunction has already saved + * @param forMergeMap Additional predicates that current operand has expanded + */ + private void combinePredicatesUsingOr( + Map<String, RexNode> baseMap, + Map<String, RexNode> forMergeMap) { + if (baseMap.isEmpty()) { + return; + } + + Iterator<Map.Entry<String, RexNode>> iterator = + baseMap.entrySet().iterator(); + while (iterator.hasNext()) { + int forMergeNodeCount = 0; + + Map.Entry<String, 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; Review Comment: Nit: originalCount isn't much longer and makes it more readable IMO ########## core/src/main/java/org/apache/calcite/rel/rules/ExpandDisjunctionForJoinInputsRule.java: ########## @@ -0,0 +1,388 @@ +/* + * 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.calcite.rel.rules; + +import org.apache.calcite.plan.RelOptRuleCall; +import org.apache.calcite.plan.RelOptUtil; +import org.apache.calcite.plan.RelRule; +import org.apache.calcite.rel.core.Filter; +import org.apache.calcite.rel.core.Join; +import org.apache.calcite.rex.RexCall; +import org.apache.calcite.rex.RexNode; +import org.apache.calcite.rex.RexUtil; +import org.apache.calcite.tools.RelBuilder; +import org.apache.calcite.util.ControlFlowException; +import org.apache.calcite.util.ImmutableBitSet; + +import org.immutables.value.Value; + +import java.util.HashMap; +import java.util.Iterator; +import java.util.List; +import java.util.Map; + +/** + * Rule to expand disjunction for join inputs in condition of a {@link Filter} or {@link Join}. Review Comment: Can you try to rephrase this sentence? -- 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]
