jamesstarr commented on code in PR #3760: URL: https://github.com/apache/calcite/pull/3760#discussion_r1581544227
########## 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: If we had a better extraction method, then we would see an infinite loop. This is my concern with such a partial solution. It will be difficult to build on top. ``` SELECT * FROM t1, t2 WHERE t1.c1 = t2.c1 AND ((t1.c1, t2.c1) IN ((1, 2), (3, 4), (5, 6), (7, 8), (9, 10)) OR (t1.c2, t2.c1) IN ((3, 4), (5, 6), (7, 8)) ``` Given the above example ideally you would get something like the following tree: ``` FILTER ((t1.c1, t2.c1) IN ((1, 2), (3, 4), (5, 6), (7, 8), (9, 10)) OR (t1.c2, t2.c1) IN ((3, 4), (5, 6), (7, 8))) JOIN on t1.c1 = t2.c1 SCAN t1 FILTER t2.c1 IN (2, 4, 6, 8, 10) SCAN t2 ``` -- 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]
