jamesstarr commented on code in PR #3760: URL: https://github.com/apache/calcite/pull/3760#discussion_r1569177166
########## core/src/main/java/org/apache/calcite/rel/rules/JoinDeriveEquivalenceFilterRule.java: ########## @@ -0,0 +1,380 @@ +/* + * 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.RelOptPredicateList; +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.rel.core.JoinRelType; +import org.apache.calcite.rel.logical.LogicalFilter; +import org.apache.calcite.rel.logical.LogicalJoin; +import org.apache.calcite.rex.RexBuilder; +import org.apache.calcite.rex.RexCall; +import org.apache.calcite.rex.RexInputRef; +import org.apache.calcite.rex.RexLiteral; +import org.apache.calcite.rex.RexNode; +import org.apache.calcite.rex.RexShuttle; +import org.apache.calcite.rex.RexSimplify; +import org.apache.calcite.rex.RexUtil; +import org.apache.calcite.sql.SqlKind; +import org.apache.calcite.sql.fun.SqlStdOperatorTable; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.LinkedHashMultimap; +import com.google.common.collect.Multimap; +import com.google.common.collect.Sets; + +import org.immutables.value.Value; + +import java.util.List; +import java.util.Set; +import java.util.stream.Collectors; + +/** + * Planner rule that derives more equivalent predicates from inner + * {@link Join} and creates {@link Filter} with those predicates. + * Then {@link FilterJoinRule} will try to push these new predicates down. + * (So if you enable this rule, please make sure to enable {@link FilterJoinRule} also). + * <p>The basic idea is that, for example, in the query + * <blockquote>SELECT * FROM ta INNER JOIN tb ON ta.x = tb.y WHERE ta.x > 10</blockquote> + * we can infer condition tb.y > 10 and push it down to the table tb. + * In this way, maybe we can reduce the amount of data involved in the {@link Join}. + * <p>For example, the query plan + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[>($0, 10)]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p> will convert to + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[>($1, 20)]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[>($0, 20)]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p>the query plan + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[SEARCH($1, Sarg[(10..30)])]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[SEARCH($0, Sarg[(20..40)])]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p> will convert to + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[SEARCH($1, Sarg[(20..30)])]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[SEARCH($0, Sarg[(20..30)])]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p>Currently, the rule has some limitations: + * <p>1. only handle partial predicates (comparison), but this can be extended to + * support more predicates such as 'LIKE', 'RLIKE' and 'SIMILAR' in the future. + * <p>2. only support simple condition inference, such as: {$1 = $2, $2 = 10} => {$1 = 10}, + * can not handle complex condition inference, such as conditions with functions, like + * {a = b, b = abs(c), c = 1} => {a = abs(1)} + * <p>3. only support discomposed literal, for example + * it can infer {$1 = $2, $1 = 10} => {$2 = 10} + * it can not infer {$1 = $2, $1 = 10 + 10} => {$2 = 10 + 10} + */ + [email protected] +public class JoinDeriveEquivalenceFilterRule + extends RelRule<JoinDeriveEquivalenceFilterRule.Config> implements TransformationRule { + + public JoinDeriveEquivalenceFilterRule(Config config) { + super(config); + } + + @Override public void onMatch(RelOptRuleCall call) { Review Comment: This should use the RelMetaDataQuery for extracting filters from below. Please look at RelMetadataQuery::getPulledUpPredicates usage in ReduceExpressionsRule. ########## core/src/main/java/org/apache/calcite/rel/rules/JoinDeriveEquivalenceFilterRule.java: ########## @@ -0,0 +1,380 @@ +/* + * 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.RelOptPredicateList; +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.rel.core.JoinRelType; +import org.apache.calcite.rel.logical.LogicalFilter; +import org.apache.calcite.rel.logical.LogicalJoin; +import org.apache.calcite.rex.RexBuilder; +import org.apache.calcite.rex.RexCall; +import org.apache.calcite.rex.RexInputRef; +import org.apache.calcite.rex.RexLiteral; +import org.apache.calcite.rex.RexNode; +import org.apache.calcite.rex.RexShuttle; +import org.apache.calcite.rex.RexSimplify; +import org.apache.calcite.rex.RexUtil; +import org.apache.calcite.sql.SqlKind; +import org.apache.calcite.sql.fun.SqlStdOperatorTable; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.LinkedHashMultimap; +import com.google.common.collect.Multimap; +import com.google.common.collect.Sets; + +import org.immutables.value.Value; + +import java.util.List; +import java.util.Set; +import java.util.stream.Collectors; + +/** + * Planner rule that derives more equivalent predicates from inner Review Comment: You can transitively generate predicates for the null generating sides or left and right joins. ########## core/src/main/java/org/apache/calcite/rel/rules/JoinDeriveEquivalenceFilterRule.java: ########## @@ -0,0 +1,380 @@ +/* + * 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.RelOptPredicateList; +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.rel.core.JoinRelType; +import org.apache.calcite.rel.logical.LogicalFilter; +import org.apache.calcite.rel.logical.LogicalJoin; +import org.apache.calcite.rex.RexBuilder; +import org.apache.calcite.rex.RexCall; +import org.apache.calcite.rex.RexInputRef; +import org.apache.calcite.rex.RexLiteral; +import org.apache.calcite.rex.RexNode; +import org.apache.calcite.rex.RexShuttle; +import org.apache.calcite.rex.RexSimplify; +import org.apache.calcite.rex.RexUtil; +import org.apache.calcite.sql.SqlKind; +import org.apache.calcite.sql.fun.SqlStdOperatorTable; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.LinkedHashMultimap; +import com.google.common.collect.Multimap; +import com.google.common.collect.Sets; + +import org.immutables.value.Value; + +import java.util.List; +import java.util.Set; +import java.util.stream.Collectors; + +/** + * Planner rule that derives more equivalent predicates from inner + * {@link Join} and creates {@link Filter} with those predicates. + * Then {@link FilterJoinRule} will try to push these new predicates down. + * (So if you enable this rule, please make sure to enable {@link FilterJoinRule} also). + * <p>The basic idea is that, for example, in the query + * <blockquote>SELECT * FROM ta INNER JOIN tb ON ta.x = tb.y WHERE ta.x > 10</blockquote> + * we can infer condition tb.y > 10 and push it down to the table tb. + * In this way, maybe we can reduce the amount of data involved in the {@link Join}. + * <p>For example, the query plan + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[>($0, 10)]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p> will convert to + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[>($1, 20)]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[>($0, 20)]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p>the query plan + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[SEARCH($1, Sarg[(10..30)])]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[SEARCH($0, Sarg[(20..40)])]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p> will convert to + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[SEARCH($1, Sarg[(20..30)])]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[SEARCH($0, Sarg[(20..30)])]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p>Currently, the rule has some limitations: + * <p>1. only handle partial predicates (comparison), but this can be extended to + * support more predicates such as 'LIKE', 'RLIKE' and 'SIMILAR' in the future. + * <p>2. only support simple condition inference, such as: {$1 = $2, $2 = 10} => {$1 = 10}, + * can not handle complex condition inference, such as conditions with functions, like + * {a = b, b = abs(c), c = 1} => {a = abs(1)} + * <p>3. only support discomposed literal, for example + * it can infer {$1 = $2, $1 = 10} => {$2 = 10} + * it can not infer {$1 = $2, $1 = 10 + 10} => {$2 = 10 + 10} + */ + [email protected] +public class JoinDeriveEquivalenceFilterRule + extends RelRule<JoinDeriveEquivalenceFilterRule.Config> implements TransformationRule { + + public JoinDeriveEquivalenceFilterRule(Config config) { + super(config); + } + + @Override public void onMatch(RelOptRuleCall call) { + final Filter filter = call.rel(0); + final Join join = call.rel(1); + + final RexBuilder rexBuilder = join.getCluster().getRexBuilder(); + final RexSimplify simplify = + new RexSimplify(rexBuilder, RelOptPredicateList.EMPTY, RexUtil.EXECUTOR); + + final RexNode originalCondition = + prepare(rexBuilder, filter.getCondition(), join.getCondition()); + + final RexNode newCondition = + deriveEquivalenceCondition(simplify, rexBuilder, originalCondition); + + if (arePredicatesEquivalent(rexBuilder, simplify, originalCondition, newCondition)) { Review Comment: This is not sufficient to prevent infinite loops once generalized to pull up predicates. ########## core/src/main/java/org/apache/calcite/rel/rules/JoinDeriveEquivalenceFilterRule.java: ########## @@ -0,0 +1,380 @@ +/* + * 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.RelOptPredicateList; +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.rel.core.JoinRelType; +import org.apache.calcite.rel.logical.LogicalFilter; +import org.apache.calcite.rel.logical.LogicalJoin; +import org.apache.calcite.rex.RexBuilder; +import org.apache.calcite.rex.RexCall; +import org.apache.calcite.rex.RexInputRef; +import org.apache.calcite.rex.RexLiteral; +import org.apache.calcite.rex.RexNode; +import org.apache.calcite.rex.RexShuttle; +import org.apache.calcite.rex.RexSimplify; +import org.apache.calcite.rex.RexUtil; +import org.apache.calcite.sql.SqlKind; +import org.apache.calcite.sql.fun.SqlStdOperatorTable; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.LinkedHashMultimap; +import com.google.common.collect.Multimap; +import com.google.common.collect.Sets; + +import org.immutables.value.Value; + +import java.util.List; +import java.util.Set; +import java.util.stream.Collectors; + +/** + * Planner rule that derives more equivalent predicates from inner + * {@link Join} and creates {@link Filter} with those predicates. + * Then {@link FilterJoinRule} will try to push these new predicates down. + * (So if you enable this rule, please make sure to enable {@link FilterJoinRule} also). + * <p>The basic idea is that, for example, in the query + * <blockquote>SELECT * FROM ta INNER JOIN tb ON ta.x = tb.y WHERE ta.x > 10</blockquote> + * we can infer condition tb.y > 10 and push it down to the table tb. + * In this way, maybe we can reduce the amount of data involved in the {@link Join}. + * <p>For example, the query plan + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[>($0, 10)]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p> will convert to + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[>($1, 20)]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[>($0, 20)]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p>the query plan + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[SEARCH($1, Sarg[(10..30)])]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[SEARCH($0, Sarg[(20..40)])]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p> will convert to + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[SEARCH($1, Sarg[(20..30)])]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[SEARCH($0, Sarg[(20..30)])]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p>Currently, the rule has some limitations: + * <p>1. only handle partial predicates (comparison), but this can be extended to + * support more predicates such as 'LIKE', 'RLIKE' and 'SIMILAR' in the future. + * <p>2. only support simple condition inference, such as: {$1 = $2, $2 = 10} => {$1 = 10}, + * can not handle complex condition inference, such as conditions with functions, like + * {a = b, b = abs(c), c = 1} => {a = abs(1)} + * <p>3. only support discomposed literal, for example + * it can infer {$1 = $2, $1 = 10} => {$2 = 10} + * it can not infer {$1 = $2, $1 = 10 + 10} => {$2 = 10 + 10} + */ + [email protected] +public class JoinDeriveEquivalenceFilterRule + extends RelRule<JoinDeriveEquivalenceFilterRule.Config> implements TransformationRule { + + public JoinDeriveEquivalenceFilterRule(Config config) { + super(config); + } + + @Override public void onMatch(RelOptRuleCall call) { + final Filter filter = call.rel(0); + final Join join = call.rel(1); + + final RexBuilder rexBuilder = join.getCluster().getRexBuilder(); + final RexSimplify simplify = + new RexSimplify(rexBuilder, RelOptPredicateList.EMPTY, RexUtil.EXECUTOR); + + final RexNode originalCondition = + prepare(rexBuilder, filter.getCondition(), join.getCondition()); + + final RexNode newCondition = + deriveEquivalenceCondition(simplify, rexBuilder, originalCondition); + + if (arePredicatesEquivalent(rexBuilder, simplify, originalCondition, newCondition)) { + // if originalCondition and newCondition are equivalent, it means that the current + // Filter has either been derived or there is no room for derivation. if so, + // then we can stop. + return; + } + + final Filter newFilter = filter.copy(filter.getTraitSet(), filter.getInput(), newCondition); + + call.transformTo(newFilter); + + // after derivation, the original filter can be pruned + call.getPlanner().prune(filter); Review Comment: I am pretty sure we do not want to do this. If their is a large tree, then this could cause problems. ########## core/src/main/java/org/apache/calcite/rex/RexUtil.java: ########## @@ -3191,4 +3231,75 @@ private static class SearchExpandingShuttle extends RexShuttle { } } } + + /** + * Reorders some of the operands in this expression so structural comparison. + * + * <p>This is mostly the same as {@link SubstitutionVisitor#canonizeNode}, except + * that comparator is based on the {@link SqlKind}'s ordinal rather than string + * representation lexicographic order, which allows constant to always be on the + * right side of the expression. See {@link RexNormalize#reorderOperands} for details. + */ + public static RexNode canonizeNode(RexBuilder rexBuilder, RexNode expression) { Review Comment: I think it preferable to have helper functions for interacting with the existing nodes then creating a copy. ########## core/src/main/java/org/apache/calcite/rel/rules/JoinDeriveEquivalenceFilterRule.java: ########## @@ -0,0 +1,380 @@ +/* + * 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.RelOptPredicateList; +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.rel.core.JoinRelType; +import org.apache.calcite.rel.logical.LogicalFilter; +import org.apache.calcite.rel.logical.LogicalJoin; +import org.apache.calcite.rex.RexBuilder; +import org.apache.calcite.rex.RexCall; +import org.apache.calcite.rex.RexInputRef; +import org.apache.calcite.rex.RexLiteral; +import org.apache.calcite.rex.RexNode; +import org.apache.calcite.rex.RexShuttle; +import org.apache.calcite.rex.RexSimplify; +import org.apache.calcite.rex.RexUtil; +import org.apache.calcite.sql.SqlKind; +import org.apache.calcite.sql.fun.SqlStdOperatorTable; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.LinkedHashMultimap; +import com.google.common.collect.Multimap; +import com.google.common.collect.Sets; + +import org.immutables.value.Value; + +import java.util.List; +import java.util.Set; +import java.util.stream.Collectors; + +/** + * Planner rule that derives more equivalent predicates from inner + * {@link Join} and creates {@link Filter} with those predicates. + * Then {@link FilterJoinRule} will try to push these new predicates down. + * (So if you enable this rule, please make sure to enable {@link FilterJoinRule} also). + * <p>The basic idea is that, for example, in the query + * <blockquote>SELECT * FROM ta INNER JOIN tb ON ta.x = tb.y WHERE ta.x > 10</blockquote> + * we can infer condition tb.y > 10 and push it down to the table tb. + * In this way, maybe we can reduce the amount of data involved in the {@link Join}. + * <p>For example, the query plan + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[>($0, 10)]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p> will convert to + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[>($1, 20)]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[>($0, 20)]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p>the query plan + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[SEARCH($1, Sarg[(10..30)])]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[SEARCH($0, Sarg[(20..40)])]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p> will convert to + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[SEARCH($1, Sarg[(20..30)])]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[SEARCH($0, Sarg[(20..30)])]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p>Currently, the rule has some limitations: + * <p>1. only handle partial predicates (comparison), but this can be extended to + * support more predicates such as 'LIKE', 'RLIKE' and 'SIMILAR' in the future. + * <p>2. only support simple condition inference, such as: {$1 = $2, $2 = 10} => {$1 = 10}, + * can not handle complex condition inference, such as conditions with functions, like + * {a = b, b = abs(c), c = 1} => {a = abs(1)} + * <p>3. only support discomposed literal, for example + * it can infer {$1 = $2, $1 = 10} => {$2 = 10} + * it can not infer {$1 = $2, $1 = 10 + 10} => {$2 = 10 + 10} + */ + [email protected] +public class JoinDeriveEquivalenceFilterRule Review Comment: This name is misleading since it is not just equivalency, no? ########## core/src/main/java/org/apache/calcite/rel/rules/JoinDeriveEquivalenceFilterRule.java: ########## @@ -0,0 +1,380 @@ +/* + * 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.RelOptPredicateList; +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.rel.core.JoinRelType; +import org.apache.calcite.rel.logical.LogicalFilter; +import org.apache.calcite.rel.logical.LogicalJoin; +import org.apache.calcite.rex.RexBuilder; +import org.apache.calcite.rex.RexCall; +import org.apache.calcite.rex.RexInputRef; +import org.apache.calcite.rex.RexLiteral; +import org.apache.calcite.rex.RexNode; +import org.apache.calcite.rex.RexShuttle; +import org.apache.calcite.rex.RexSimplify; +import org.apache.calcite.rex.RexUtil; +import org.apache.calcite.sql.SqlKind; +import org.apache.calcite.sql.fun.SqlStdOperatorTable; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.LinkedHashMultimap; +import com.google.common.collect.Multimap; +import com.google.common.collect.Sets; + +import org.immutables.value.Value; + +import java.util.List; +import java.util.Set; +import java.util.stream.Collectors; + +/** + * Planner rule that derives more equivalent predicates from inner + * {@link Join} and creates {@link Filter} with those predicates. + * Then {@link FilterJoinRule} will try to push these new predicates down. + * (So if you enable this rule, please make sure to enable {@link FilterJoinRule} also). + * <p>The basic idea is that, for example, in the query + * <blockquote>SELECT * FROM ta INNER JOIN tb ON ta.x = tb.y WHERE ta.x > 10</blockquote> + * we can infer condition tb.y > 10 and push it down to the table tb. + * In this way, maybe we can reduce the amount of data involved in the {@link Join}. + * <p>For example, the query plan + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[>($0, 10)]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p> will convert to + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[>($1, 20)]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[>($0, 20)]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p>the query plan + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[SEARCH($1, Sarg[(10..30)])]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[SEARCH($0, Sarg[(20..40)])]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p> will convert to + * <blockquote><pre>{@code + * LogicalJoin(condition=[=($1, $5)], joinType=[inner]) + * LogicalFilter(condition=[SEARCH($1, Sarg[(20..30)])]) + * LogicalTableScan(table=[[hr, emps]]) + * LogicalFilter(condition=[SEARCH($0, Sarg[(20..30)])]) + * LogicalTableScan(table=[[hr, depts]]) + * }</pre></blockquote> + * <p>Currently, the rule has some limitations: + * <p>1. only handle partial predicates (comparison), but this can be extended to + * support more predicates such as 'LIKE', 'RLIKE' and 'SIMILAR' in the future. + * <p>2. only support simple condition inference, such as: {$1 = $2, $2 = 10} => {$1 = 10}, + * can not handle complex condition inference, such as conditions with functions, like + * {a = b, b = abs(c), c = 1} => {a = abs(1)} + * <p>3. only support discomposed literal, for example + * it can infer {$1 = $2, $1 = 10} => {$2 = 10} + * it can not infer {$1 = $2, $1 = 10 + 10} => {$2 = 10 + 10} + */ + [email protected] +public class JoinDeriveEquivalenceFilterRule + extends RelRule<JoinDeriveEquivalenceFilterRule.Config> implements TransformationRule { + + public JoinDeriveEquivalenceFilterRule(Config config) { + super(config); + } + + @Override public void onMatch(RelOptRuleCall call) { + final Filter filter = call.rel(0); + final Join join = call.rel(1); + + final RexBuilder rexBuilder = join.getCluster().getRexBuilder(); + final RexSimplify simplify = + new RexSimplify(rexBuilder, RelOptPredicateList.EMPTY, RexUtil.EXECUTOR); + + final RexNode originalCondition = + prepare(rexBuilder, filter.getCondition(), join.getCondition()); + + final RexNode newCondition = + deriveEquivalenceCondition(simplify, rexBuilder, originalCondition); + + if (arePredicatesEquivalent(rexBuilder, simplify, originalCondition, newCondition)) { + // if originalCondition and newCondition are equivalent, it means that the current + // Filter has either been derived or there is no room for derivation. if so, + // then we can stop. + return; + } + + final Filter newFilter = filter.copy(filter.getTraitSet(), filter.getInput(), newCondition); Review Comment: I think it preferable to generate: ``` FILTER JOIN FILTER .... FILTER .... ``` -- 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]
