silundong commented on code in PR #4619: URL: https://github.com/apache/calcite/pull/4619#discussion_r2570444000
########## core/src/main/java/org/apache/calcite/sql2rel/TopDownGeneralDecorrelator.java: ########## @@ -0,0 +1,1009 @@ +/* + * 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.sql2rel; + +import org.apache.calcite.plan.RelOptUtil; +import org.apache.calcite.plan.Strong; +import org.apache.calcite.plan.hep.HepPlanner; +import org.apache.calcite.plan.hep.HepProgram; +import org.apache.calcite.rel.RelCollation; +import org.apache.calcite.rel.RelNode; +import org.apache.calcite.rel.core.Aggregate; +import org.apache.calcite.rel.core.AggregateCall; +import org.apache.calcite.rel.core.Correlate; +import org.apache.calcite.rel.core.CorrelationId; +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.core.Project; +import org.apache.calcite.rel.core.SetOp; +import org.apache.calcite.rel.core.Sort; +import org.apache.calcite.rel.rules.CoreRules; +import org.apache.calcite.rel.type.RelDataType; +import org.apache.calcite.rex.RexCall; +import org.apache.calcite.rex.RexCorrelVariable; +import org.apache.calcite.rex.RexFieldAccess; +import org.apache.calcite.rex.RexInputRef; +import org.apache.calcite.rex.RexNode; +import org.apache.calcite.rex.RexShuttle; +import org.apache.calcite.rex.RexUtil; +import org.apache.calcite.rex.RexWindow; +import org.apache.calcite.sql.SqlAggFunction; +import org.apache.calcite.sql.SqlKind; +import org.apache.calcite.sql.fun.SqlCountAggFunction; +import org.apache.calcite.sql.fun.SqlStdOperatorTable; +import org.apache.calcite.sql2rel.RelDecorrelator.CorDef; +import org.apache.calcite.sql2rel.RelDecorrelator.Frame; +import org.apache.calcite.tools.RelBuilder; +import org.apache.calcite.util.ImmutableBitSet; +import org.apache.calcite.util.Litmus; +import org.apache.calcite.util.Pair; +import org.apache.calcite.util.ReflectUtil; +import org.apache.calcite.util.ReflectiveVisitor; +import org.apache.calcite.util.mapping.Mappings; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; + +import org.checkerframework.checker.nullness.qual.Nullable; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.NavigableMap; +import java.util.NavigableSet; +import java.util.Set; +import java.util.TreeMap; +import java.util.TreeSet; +import java.util.stream.IntStream; + +import static java.util.Objects.requireNonNull; + +/** + * A top‑down, generic decorrelation algorithm that can handle deep nestings of correlated + * subqueries and that generalizes to complex query constructs. More details are in paper: + * <a href="https://dl.gi.de/items/b9df4765-d1b0-4267-a77c-4ce4ab0ee62d";> + * Improving Unnesting of Complex Queries</a> + */ +public class TopDownGeneralDecorrelator implements ReflectiveVisitor { + + private final RelBuilder builder; + + // record the CorDef in the current context (including those in the parent Correlate). + private final NavigableSet<CorDef> corDefs; + + // a map from RelNode to whether existing correlated expressions (according to corDefs). + private final Map<RelNode, Boolean> hasCorrelatedExpressions; + + // a map from RelNode to its UnnestQuery. + private final Map<RelNode, UnnestQuery> mapRelToUnnestQuery; + + private final boolean hasParent; + + // whether allow empty output resulting from decorrelate rewriting. + private boolean emptyOutputDisable; + + // the domain of the free variables (i.e. corDefs) D, it's duplicate free. + private DedupFreeVarsNode dedupFreeVarsNode; + + @SuppressWarnings("method.invocation.invalid") + private final ReflectUtil.MethodDispatcher<RelNode> dispatcher = + ReflectUtil.createMethodDispatcher( + RelNode.class, getVisitor(), "unnestInternal", RelNode.class); + + @SuppressWarnings("initialization.fields.uninitialized") + public TopDownGeneralDecorrelator( + RelBuilder builder, + boolean hasParent, + boolean emptyOutputDisable, + @Nullable Set<CorDef> parentCorDefs, + @Nullable Map<RelNode, Boolean> parentHasCorrelatedExpressions, + @Nullable Map<RelNode, UnnestQuery> parentMapRelToUnnestInfo) { + this.builder = builder; + this.hasParent = hasParent; + this.emptyOutputDisable = emptyOutputDisable; + this.corDefs = new TreeSet<>(); + if (parentCorDefs != null) { + this.corDefs.addAll(parentCorDefs); + } + this.hasCorrelatedExpressions = parentHasCorrelatedExpressions == null + ? new HashMap<>() + : parentHasCorrelatedExpressions; + this.mapRelToUnnestQuery = parentMapRelToUnnestInfo == null + ? new HashMap<>() + : parentMapRelToUnnestInfo; + } + + private static TopDownGeneralDecorrelator createEmptyDecorrelator(RelBuilder builder) { + return new TopDownGeneralDecorrelator(builder, false, false, null, null, null); + } + + private TopDownGeneralDecorrelator createSubDecorrelator() { + TopDownGeneralDecorrelator subDecorrelator = + new TopDownGeneralDecorrelator( + builder, + true, + emptyOutputDisable, + corDefs, + hasCorrelatedExpressions, + mapRelToUnnestQuery); + subDecorrelator.dedupFreeVarsNode = this.dedupFreeVarsNode; + return subDecorrelator; + } + + /** + * Decorrelates a query. This is the entry point for this class. + * + * @param rel Root node of the query + * @param builder RelBuilder + * @return Equivalent node without correlation + */ + public static RelNode decorrelateQuery(RelNode rel, RelBuilder builder) { + HepProgram preProgram = HepProgram.builder() + .addRuleCollection( + ImmutableList.of( + CoreRules.FILTER_PROJECT_TRANSPOSE, + CoreRules.FILTER_INTO_JOIN, + CoreRules.FILTER_CORRELATE)) + .build(); + HepPlanner prePlanner = new HepPlanner(preProgram); + prePlanner.setRoot(rel); + RelNode preparedRel = prePlanner.findBestExp(); + + // start decorrelating + TopDownGeneralDecorrelator decorrelator = createEmptyDecorrelator(builder); + RelNode decorrelateNode = rel; + try { + decorrelateNode = decorrelator.correlateElimination(preparedRel); + } catch (UnsupportedOperationException e) { + // if the correlation exists in an unsupported operator, retain the original plan. + } + + HepProgram postProgram = HepProgram.builder() + .addRuleCollection( + ImmutableList.of( + CoreRules.FILTER_PROJECT_TRANSPOSE, + CoreRules.FILTER_INTO_JOIN, + CoreRules.MARK_TO_SEMI_OR_ANTI_JOIN_RULE, + CoreRules.PROJECT_MERGE, + CoreRules.PROJECT_REMOVE)) + .build(); + HepPlanner postPlanner = new HepPlanner(postProgram); + postPlanner.setRoot(decorrelateNode); + return postPlanner.findBestExp(); + } + + /** + * Eliminates Correlate. + * + * @param rel RelNode + * @return Equivalent RelNode without Correlate + */ + private RelNode correlateElimination(RelNode rel) { + if (rel instanceof Correlate) { + final Correlate correlate = (Correlate) rel; + final RelNode newLeft; + if (hasParent) { + // if the current decorrelator has a parent, it means that the Correlate must have + // correlation from above. + assert hasCorrelatedExpressions.containsKey(correlate) + && hasCorrelatedExpressions.get(correlate); + newLeft = unnest(correlate.getLeft()); + } else { + // otherwise, start a new decorrelation for the left side. + newLeft = decorrelateQuery(correlate.getLeft(), builder); + } + + // create or update UnnestQuery of left side and corDefs of this decorrelator. + UnnestQuery leftInfo = mapRelToUnnestQuery.get(correlate.getLeft()); + TreeMap<CorDef, Integer> corDefOutputs = new TreeMap<>(); + Map<Integer, Integer> oldToNewOutputs = new HashMap<>(); + for (int i = 0; i < correlate.getLeft().getRowType().getFieldCount(); i++) { + int newColumnIndex = leftInfo == null ? i : requireNonNull(leftInfo.oldToNewOutputs.get(i)); + oldToNewOutputs.put(i, newColumnIndex); + if (correlate.getRequiredColumns().get(i)) { + CorDef corDef = new CorDef(correlate.getCorrelationId(), i); + corDefs.add(corDef); + corDefOutputs.put(corDef, newColumnIndex); + } + } + if (leftInfo != null) { + corDefOutputs.putAll(leftInfo.corDefOutputs); + } + leftInfo = new UnnestQuery(correlate.getLeft(), newLeft, corDefOutputs, oldToNewOutputs); + dedupFreeVarsNode = generateDedupFreeVarsNode(newLeft, leftInfo); + + // decorrelate right side + detectCorrelatedExpressions(correlate.getRight()); + emptyOutputDisable |= correlate.getJoinType() == JoinRelType.MARK; + RelNode newRight = unnest(correlate.getRight()); + UnnestQuery rightInfo = requireNonNull(mapRelToUnnestQuery.get(correlate.getRight())); + + // rewrite condition, adding the natural join condition between the left side and + // the domain D that in right side. + // + // Correlate(condition=[p]) + // / \ + // L ... with correlation + // \ + // R + // => + // Join(condition=[p AND (L is not distinct from D)]) + // / \ + // L ... without correlation + // \ + // x + // / \ + // D R + builder.push(newLeft).push(newRight); + RexNode unnestedJoinCondition = + createUnnestedJoinCondition(correlate.getCondition(), leftInfo, rightInfo, true); + RelNode unnestedRel = builder.join(correlate.getJoinType(), unnestedJoinCondition).build(); + + if (!hasParent) { + // ensure that the fields are in the same order as in the original plan. + builder.push(unnestedRel); + UnnestQuery unnestQuery = + createJoinUnnestInfo( + leftInfo, + rightInfo, + correlate, + unnestedRel, + correlate.getJoinType()); + List<RexNode> projects + = builder.fields(new ArrayList<>(unnestQuery.oldToNewOutputs.values())); + unnestedRel = builder.project(projects).build(); + } + return unnestedRel; + } else { + for (int i = 0; i < rel.getInputs().size(); i++) { + rel.replaceInput(i, correlateElimination(rel.getInput(i))); + } + } + return rel; + } + + /** + * Generate the domain of the free variables D. + * + * @param newLeft the left side (without correlation) of Correlate + * @param leftInfo the UnnestQuery of the left side of Correlate + * @return the domain of the free variables D + */ + private DedupFreeVarsNode generateDedupFreeVarsNode(RelNode newLeft, UnnestQuery leftInfo) { + List<Integer> columnIndexes = new ArrayList<>(); + for (CorDef corDef : corDefs) { + int fieldIndex = requireNonNull(leftInfo.corDefOutputs.get(corDef)); + columnIndexes.add(fieldIndex); + } + List<RexNode> inputRefs = builder.push(newLeft) + .fields(columnIndexes); + RelNode rel = builder.project(inputRefs).distinct().build(); + return new DedupFreeVarsNode(rel); + } + + /** + * Detects whether existing correlated expressions in the RelNode (according to corDefs). + * + * @param rel RelNode + * @return true when there are correlated expressions + */ + private boolean detectCorrelatedExpressions(RelNode rel) { + boolean hasCorrelation = false; Review Comment: Check the map `hasCorrelatedExpressions` first may benefit, however, this might only apply when there are no parent decorrelations (`hasParent` is FALSE). For example: ``` Correlate0 => cor0 / \ r1 r2 \ Correlate1 => cor1 / \ r3 with cor0 r5 with cor1 / \ r4 r6 ``` For the parent decorrelator-0 of Correlate0, r5 doesn't have correlation. However, for the decorrelator-1 of Correlate1, its construction merge information from the parent decorrelation-0, at this point, r5 still doesn't have correlation. Once the decorrelator-1 completes the decorrelation on the left side of Correlate1, it need to detect the correlation on Correlate1 right side (based on cor0 and cor1). Now r5 has correlation, and the value in `hasCorrelatedExpressions` will change from FALSE to TRUE. Therefore, perhaps a safer approach would be to first check the value of `hasCorrelatedExpressions` when `hasParent` is FALSE? -- 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]
