englefly commented on code in PR #69322: URL: https://github.com/apache/doris/pull/69322#discussion_r4361008801
########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/HboJoinConditions.java: ########## @@ -0,0 +1,249 @@ +// 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.doris.nereids.stats; + +import org.apache.doris.nereids.trees.expressions.EqualTo; +import org.apache.doris.nereids.trees.expressions.ExprId; +import org.apache.doris.nereids.trees.expressions.Expression; +import org.apache.doris.nereids.trees.expressions.NullSafeEqual; +import org.apache.doris.nereids.trees.expressions.Slot; +import org.apache.doris.nereids.trees.expressions.SlotReference; +import org.apache.doris.nereids.trees.plans.JoinType; +import org.apache.doris.nereids.trees.plans.Plan; +import org.apache.doris.nereids.trees.plans.algebra.Join; + +import com.google.common.hash.Hashing; + +import java.util.ArrayList; +import java.util.List; +import java.util.Optional; +import java.util.Set; +import java.util.TreeSet; + +/** + * Canonical description and fingerprint of the equality conditions of a join, used as the key of + * manually injected join expansion entries ({@code HBO SET EXPANSION}). + * + * <p>The join type and the residual (non equality) conditions take part in the key next to the hash + * (equality) conjuncts, because the injected factor replaces the output rows of the whole join: an + * inner join which matches nothing and a left outer join of the same columns produce very different + * row counts, and a selective residual predicate changes the output by orders of magnitude. The + * shape of both sub trees is still excluded, so one injected entry stays reusable by every query + * which joins the same columns with the same join type and the same residual conditions. + * + * <p>The canonical form is {@code JE{<join type>;EqualTo(...);...}} with the pairs and the residual + * conditions sorted; a pair is rendered by {@link GroupStructInfo#normalizeExpression(Expression)} + * which already sorts the two operands of an equality (equality is commutative), so {@code a = b} + * and {@code b = a} collapse. A residual condition is rendered with its literal in both modes, + * because it decides how many partner rows a row finds ({@code b > c + 1} is not {@code b > c + 2}). + */ +public class HboJoinConditions { + private static final String PREFIX = "JE{"; + private static final String SEP = ";"; + + private HboJoinConditions() { + } + + /** True when the injected expansion of this join type is applicable at all. */ + public static boolean isExpansionApplicable(JoinType joinType) { + // semi / anti / mark style joins can never produce more rows than their left input, and + // asof joins match at most one row per left row, so expansion can not happen there + return joinType == JoinType.INNER_JOIN + || joinType == JoinType.LEFT_OUTER_JOIN + || joinType == JoinType.RIGHT_OUTER_JOIN + || joinType == JoinType.FULL_OUTER_JOIN; + } + + /** + * Canonical string of the conditions of a join, empty when the join has no expansion key at all. + * + * <p>The key describes the <b>equality</b> conditions only: the factor is the fan out of the equi + * join, and the non equality conditions are applied by the estimator on top of it (see + * {@code JoinEstimation}), so a join with a residual predicate uses the factor of its equality pair + * and the residual keeps its own selectivity. The operands have to name the columns of the tables + * themselves: an operand which is not a direct slot of a catalog table (a computed column, an + * aggregate output, a cast) cannot name its table, so such a join has no key. A null safe equality + * ({@code <=>}) is a hash conjunct as well and takes part like a plain equality. + */ + public static Optional<String> canonicalOf(Join join) { + return keyParts(join).map(parts -> PREFIX + String.join(SEP, parts) + "}"); + } + + /** + * The key of the expansion entry of a join: the sha256 of its structural identity, empty when the + * join has no expansion key (see {@link #canonicalOf}). The canonical string is the readable form of + * the same parts: it is printed by EXPLAIN and stored as the struct of the entry, and the key is not + * derived from the text. + */ + public static Optional<String> fingerprintOf(Join join) { + return keyParts(join).map(parts -> { + ShapeKeyWriter key = new ShapeKeyWriter(); + key.tag(0); + for (String part : parts) { + key.text(part); + } + return Hashing.sha256().hashBytes(key.toByteArray()).toString(); + }); + } + + /** + * The identity of a join expansion: its type, the equality pairs, the residual conditions and the + * columns of the tables the join reads. The identity is the same while a group is estimated (its + * children are group references there) and while the chosen plan is printed, because the operands are + * read from the slots themselves. + */ + private static Optional<List<String>> keyParts(Join join) { + Set<String> operands = new TreeSet<>(); + List<String> forward = new ArrayList<>(); + List<String> backward = new ArrayList<>(); + for (Expression conjunct : join.getHashJoinConjuncts()) { + if (!(conjunct instanceof EqualTo) && !(conjunct instanceof NullSafeEqual)) { + return Optional.empty(); + } + Optional<String> left = operandIdentity(conjunct.child(0)); + Optional<String> right = operandIdentity(conjunct.child(1)); + if (!left.isPresent() || !right.isPresent()) { + return Optional.empty(); + } + operands.add(left.get()); + operands.add(right.get()); + String name = conjunct instanceof NullSafeEqual ? "NullSafeEqual" : "EqualTo"; + Integer leftSide = sideOf(join, conjunct.child(0)); + Integer rightSide = sideOf(join, conjunct.child(1)); + if (leftSide == null || rightSide == null || leftSide.equals(rightSide)) { + String first = left.get().compareTo(right.get()) <= 0 ? left.get() : right.get(); + String second = first.equals(left.get()) ? right.get() : left.get(); + String pair = name + "(col(" + first + "),col(" + second + "))"; + forward.add(pair); + backward.add(pair); + } else { + forward.add(leftSide == 0 + ? name + "(col(" + left.get() + "),col(" + right.get() + "))" + : name + "(col(" + right.get() + "),col(" + left.get() + "))"); + backward.add(leftSide == 0 + ? name + "(col(" + right.get() + "),col(" + left.get() + "))" + : name + "(col(" + left.get() + "),col(" + right.get() + "))"); + } + } + if (forward.isEmpty()) { + return Optional.empty(); + } + forward.sort(String::compareTo); + backward.sort(String::compareTo); + // An inner join is commutative, so one global orientation of its two sides is chosen: the pairs are + // ordered by side all together, and the lexicographically smaller orientation is the key. Ordering + // each pair on its own would lose the incidence of a self join (which operands share a column), + // and flipping each pair on its own would lose commutativity. An outer join preserves a side, so + // its orientation is fixed (the operand of the left child first). + List<String> pairs = isCommutative(join.getJoinType()) + && String.join(SEP, backward).compareTo(String.join(SEP, forward)) < 0 + ? backward : forward; + if (pairs.isEmpty()) { + return Optional.empty(); + } + List<String> parts = new ArrayList<>(2 + pairs.size()); + parts.add(String.valueOf(join.getJoinType())); + parts.addAll(pairs); + parts.add("operands:[" + String.join(",", operands) + "]"); + if (join.getJoinType() != JoinType.INNER_JOIN) { + // an outer join preserves one side, so the side a relation is on is part of the key: it names + // the columns each side produces, which are the same while a group is estimated and while the + // chosen plan is printed (the slots carry the tables they come from) + Plan joinPlan = (Plan) join; + parts.add("sides:[" + sideOperands(joinPlan.child(0)) + "|" + sideOperands(joinPlan.child(1)) + "]"); + } + return Optional.of(parts); + } + + /** The columns one side of an outer join produces, sorted: which side a relation is on is identity. */ + private static String sideOperands(Plan side) { + Set<String> identities = new TreeSet<>(); + for (Slot slot : side.getOutput()) { Review Comment: Fixed: an outer join now orders each equality pair by side (left child operand first) and writes no output columns, so column pruning cannot change the key. A pair whose two operands come from one child, or name the same column, is refused (no key); the sides/sideOperands output-column scan is gone. Added paired tests for the side ordering, both refusal cases, and a key-only project below each child. -- 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] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
