englefly commented on code in PR #69322: URL: https://github.com/apache/doris/pull/69322#discussion_r4350215978
########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/HboJoinConditions.java: ########## @@ -0,0 +1,259 @@ +// 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>An expansion entry replaces the output of a join for every query which matches it, and its + * fingerprint carries no data state to guard it - so 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; such a join has no key, so it is skipped instead + * of being given a key which two different table pairs with the same aliases would share. 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> pairs = 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"; + pairs.add(name + "(col(" + canonicalFirst(join, conjunct, left.get(), right.get()) + + "),col(" + canonicalSecond(join, conjunct, left.get(), right.get()) + "))"); + } + if (pairs.isEmpty()) { + return Optional.empty(); + } + pairs.sort(String::compareTo); + List<String> residuals = new ArrayList<>(); + for (Expression conjunct : join.getOtherJoinConjuncts()) { + // a residual decides how many partner rows a row finds (`b > u.b + 1` is not `u.b + 2`), so + // its literals are part of the key and are never folded - and every slot it reads has to name + // its table like the equality operands do + Set<String> residualOperands = new TreeSet<>(); + boolean supported = supportsResidual(conjunct, residualOperands); + if (!supported) { + return Optional.empty(); + } + operands.addAll(residualOperands); + residuals.add(GroupStructInfo.normalizeExpression(conjunct, + GroupStructInfo.LiteralMode.WITH_LITERAL)); + } + residuals.sort(String::compareTo); + List<String> parts = new ArrayList<>(1 + pairs.size() + residuals.size() + 1); + parts.add(String.valueOf(join.getJoinType())); + parts.addAll(pairs); + parts.addAll(residuals); + 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()) { + if (slot instanceof SlotReference) { + operandIdentity(slot).ifPresent(identities::add); + } + } + return String.join(",", identities); + } + + /** + * The operand which is written first for a pair of the key. + * + * <p>A join whose sides are not interchangeable (an outer, semi or anti join) orders the operands by + * the side they are read from, so the join of the same table with the columns reversed + * ({@code a.k = b.v} against {@code a.v = b.k}) keeps two keys, and the same pair written in either + * order ({@code b.v = a.k} against {@code a.k = b.v}) keeps one. An inner join is commutative, so + * its operands are sorted by their identity: the optimizer may swap its children, and the count of a + * self join does not depend on which occurrence is called the left one. + */ + private static String canonicalFirst(Join join, Expression conjunct, String left, String right) { + Integer leftSide = sideOf(join, conjunct.child(0)); + Integer rightSide = sideOf(join, conjunct.child(1)); + if (isCommutative(join.getJoinType()) || leftSide == null || rightSide == null Review Comment: 因为同名表的 self join , inner join 也需要像 left join 那样调整 equal join 条件 的左右顺序. -- 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]
