englefly commented on code in PR #67549: URL: https://github.com/apache/doris/pull/67549#discussion_r4238198575
########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/GroupStructInfo.java: ########## @@ -0,0 +1,902 @@ +// 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.memo.Group; +import org.apache.doris.nereids.memo.GroupExpression; +import org.apache.doris.nereids.trees.expressions.And; +import org.apache.doris.nereids.trees.expressions.EqualTo; +import org.apache.doris.nereids.trees.expressions.Expression; +import org.apache.doris.nereids.trees.expressions.Or; +import org.apache.doris.nereids.trees.expressions.SlotReference; +import org.apache.doris.nereids.trees.expressions.literal.Literal; +import org.apache.doris.nereids.trees.plans.AbstractPlan; +import org.apache.doris.nereids.trees.plans.JoinType; +import org.apache.doris.nereids.trees.plans.Plan; +import org.apache.doris.nereids.trees.plans.logical.LogicalAggregate; +import org.apache.doris.nereids.trees.plans.logical.LogicalFilter; +import org.apache.doris.nereids.trees.plans.logical.LogicalJoin; +import org.apache.doris.nereids.trees.plans.logical.LogicalOlapScan; +import org.apache.doris.nereids.trees.plans.logical.LogicalProject; +import org.apache.doris.nereids.util.MutableState; +import org.apache.doris.qe.ConnectContext; + +import com.google.common.hash.Hashing; +import org.apache.logging.log4j.LogManager; +import org.apache.logging.log4j.Logger; + +import java.nio.charset.StandardCharsets; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.TreeSet; +import java.util.stream.Collectors; + +/** + * Simplified struct info of a memo {@link Group}, used by History Based Optimization (HBO). + * + * <p>The struct info is a property of the <b>group</b>, not of one of its group expressions: all + * expressions of a group are logically equivalent, so they describe the same set of relations with + * the same predicates, and the canonical form below is deliberately insensitive to which expression + * is picked. + * <ul> + * <li>join commutativity: children of a join are canonicalized by sorting;</li> + * <li>join associativity: a whole inner / cross join chain is emitted as one node + * ({@code J{inner,c:[...]}(...;...)}) whose children are the chain leaves sorted by their + * canonical form and whose conditions are the sorted union of every condition of the chain, + * so {@code (A join B) join C} and {@code A join (B join C)} produce the same descriptor;</li> + * <li>aggregation: only the group by keys and the child participate, because the output row count + * of an aggregation is the number of groups and cannot be changed by the aggregate functions + * or by the output expressions;</li> + * <li>project is transparent for structure matching.</li> + * </ul> + * This mirrors what the MV oriented {@code rules.exploration.mv.StructInfo} does (it identifies a + * sub tree by its relation set and by level independent - shuttled - predicates), with every MV + * specific field dropped: no hyper graph, no shuttle map, no equivalence class, no lineage. + * + * <p>What the canonical form keeps: + * <ul> + * <li>for each scan: the table qualifier and - as an annotation only - the data state of the scan + * (its visible version, the rows it reads and how many of the table partitions it selects, + * see {@link HboScanDescriptor});</li> + * <li>for filter / join / aggregate: the normalized predicates / join conditions / grouping keys, + * i.e. the structural pattern only (slot and expression ids are stripped by + * {@link #normalizeExpression}).</li> + * </ul> + * The string contains no per-query identifier, so it is reproducible across runs and queries for + * structurally identical sub trees, and its sha256 is used as the HBO cache key (fingerprint). + * + * <p>The sha256 is taken over the canonical string <b>without</b> the scan baselines + * ({@link #stripScanBaseline}): a hbo key identifies a plan pattern and the relation it reads, not a + * data state, so an entry whose table simply keeps growing stays matchable instead of silently never + * matching again. Whether an entry may still be applied is decided on the read side, by comparing + * the baseline of the entry with the data state of the current query (see + * {@link HboStructFreshness}). + * + * <p>The descriptor is derived from the group's logical expression and its child groups (memo level + * traversal, with a visited set to guard shared sub graphs such as CTE). Groups whose content is not + * supported (e.g. contains TVF / CTE consumer, or the head operator is not one of the supported + * kinds) are {@link #isValid() invalid} and callers must fall back to the legacy behavior. + */ +public class GroupStructInfo { + private static final List<HboScanDescriptor> INVALID_SCANS = Collections.emptyList(); + + /** Shared invalid instance: the group content is not supported by the simplified struct info. */ + public static final GroupStructInfo INVALID = new GroupStructInfo(false, "", "", "", INVALID_SCANS); + /** + * Shared instance for a failure which is not a property of the plan: the table state could not be + * read (e.g. the visible version of a cloud table could not be fetched). Unlike + * {@link #INVALID} it is not cached by the memo (see {@code Group#getOrComputeHboStructInfo}), so + * the next lookup of the same group retries instead of disabling hbo struct info for the whole + * query. + */ + public static final GroupStructInfo TRANSIENT_FAILURE = + new GroupStructInfo(false, "", "", "", INVALID_SCANS); + + private static final String SEP = ";"; + private static final Logger LOG = LogManager.getLogger(GroupStructInfo.class); + + /** + * Whether literal values participate in the canonical string / fingerprint. + * <ul> + * <li>{@link #WITH_LITERAL} keeps the literal value ({@code lit(10:int)}): the fingerprint is + * bound to the exact constants, used for filter roots where the constant changes the + * output row count;</li> + * <li>{@link #NO_LITERAL} replaces every literal value with {@code *} ({@code lit(*)}): the + * fingerprint is constant agnostic, used for join / aggregate roots and for the + * constant-free filter shape.</li> + * </ul> + * The literal data type is intentionally not kept: nereids inserts an explicit {@code Cast} + * for mismatching operand types, so two semantically different literal forms already differ by + * the cast node, while equivalent forms (e.g. {@code d > 1} and {@code d > 1.0} on a decimal + * column) are allowed to collapse. + */ + public enum LiteralMode { + WITH_LITERAL, + NO_LITERAL + } + + private final boolean valid; + private final String canonicalString; + /** The canonical string without the scan baselines: the fingerprint input. */ + private final String shapeString; + private final String fingerprint; + /** The scans of the sub tree, in the order their tokens appear in the canonical string. */ + private final List<HboScanDescriptor> scans; + /** Why no struct info was built, when it was refused by a limit instead of being unsupported. */ + private final String skipReason; + + private GroupStructInfo(boolean valid, String canonicalString, String shapeString, String fingerprint, + List<HboScanDescriptor> scans) { + this(valid, canonicalString, shapeString, fingerprint, scans, ""); + } + + private GroupStructInfo(boolean valid, String canonicalString, String shapeString, String fingerprint, + List<HboScanDescriptor> scans, String skipReason) { + this.valid = valid; + this.canonicalString = canonicalString; + this.shapeString = shapeString; + this.fingerprint = fingerprint; + this.scans = scans; + this.skipReason = skipReason; + } + + /** The reason the struct info was refused by a limit, or empty. Only for diagnostics. */ + public String getSkipReason() { + return skipReason; + } + + public boolean isValid() { + return valid; + } + + public String getCanonicalString() { + return canonicalString; + } + + /** + * The fingerprint input: the canonical string with the baseline of every scan token removed + * ({@code S{db.t}}). It is built from the traversal itself and not by parsing the canonical + * string, so no text inside a table name or a literal can be mistaken for a scan token. + */ + public String getShapeString() { + return shapeString; + } + + /** + * The row count and partition selection of every scan of the sub tree, in the order the scan + * tokens appear in the canonical string (i.e. the order a user sees when pasting the struct + * info). Empty when the struct info is invalid. + */ + public List<HboScanDescriptor> getScans() { + return scans; + } + + public String getFingerprint() { + return fingerprint; + } + + /** + * Resolve the fingerprint of the memo group that {@code planNode} belongs to, when the node + * still carries its {@link GroupExpression} back reference (memo inner plans, or plans from + * {@code chooseBestPlan}). Empty when the group content is unsupported (invalid struct info). + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode) { + return fingerprintOfPlanNode(planNode, LiteralMode.WITH_LITERAL); + } + + /** + * Resolve the group fingerprint of a plan node in the given literal mode. + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode, LiteralMode mode) { + return fingerprintOfGroup(planNode.getGroupExpression() + .map(GroupExpression::getOwnerGroup).orElse(null), mode); + } + + /** + * Resolve the fingerprint of the group that {@code planNode} belongs to, with a fallback to + * the {@link MutableState#KEY_GROUP} group-id state that post processors propagate to their + * rewritten copies (see {@code copyStatsAndGroupIdFrom}). {@code groupsById} maps memo group + * id to group, and is looked up only when the back reference is absent. + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode, Map<Integer, Group> groupsById) { + return fingerprintOfPlanNode(planNode, groupsById, LiteralMode.WITH_LITERAL); + } + + /** + * Resolve the group fingerprint of a plan node in the given literal mode, with the + * {@link MutableState#KEY_GROUP} fallback for post-processed copies. + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode, Map<Integer, Group> groupsById, + LiteralMode mode) { + return structInfoOfPlanNode(planNode, groupsById, mode).map(GroupStructInfo::getFingerprint); + } + + private static Optional<String> fingerprintOfGroup(Group group, LiteralMode mode) { + return structInfoOfGroup(group, mode).map(GroupStructInfo::getFingerprint); + } + + /** + * Resolve the {@link GroupStructInfo} (with canonical string and fingerprint) of the group a + * plan node belongs to, using the group-expression back reference or the KEY_GROUP group-id + * state propagated by post processors (see {@link #fingerprintOfPlanNode}). + */ + public static Optional<GroupStructInfo> structInfoOfPlanNode(AbstractPlan planNode, + Map<Integer, Group> groupsById) { + return structInfoOfPlanNode(planNode, groupsById, LiteralMode.WITH_LITERAL); + } + + /** + * Resolve the struct info of the group a plan node belongs to, in the given literal mode. + */ + public static Optional<GroupStructInfo> structInfoOfPlanNode(AbstractPlan planNode, + Map<Integer, Group> groupsById, LiteralMode mode) { + Group group = planNode.getGroupExpression().map(GroupExpression::getOwnerGroup).orElse(null); + if (group == null) { + Optional<Object> groupState = planNode.getMutableState(MutableState.KEY_GROUP); + if (groupState.isPresent() && groupsById != null) { + try { + group = groupsById.get(Integer.valueOf(groupState.get().toString())); + } catch (NumberFormatException ignored) { + group = null; + } + } + } + return structInfoOfGroup(group, mode); + } + + private static Optional<GroupStructInfo> structInfoOfGroup(Group group, LiteralMode mode) { + if (group == null) { + return Optional.empty(); + } + GroupStructInfo structInfo = group.getOrComputeHboStructInfo(mode); + return structInfo.isValid() ? Optional.of(structInfo) : Optional.empty(); + } + + /** + * The struct info of the group a plan node belongs to, computed now instead of being taken from + * the per-group cache. The fingerprint does not depend on any data state, so the cached struct + * info is the right source for a lookup; its <b>baseline</b> (the visible version and the row + * counts of its scans) is however a snapshot of the moment it was computed, which may be well + * before the query is planned. Whoever displays that baseline (EXPLAIN prints it as the + * {@code struct=} a user pastes into {@code HBO SET STATISTICS}) or compares it (the drift + * verdict) must therefore ask for it here, so that the whole query reports one data state. + */ + public static Optional<GroupStructInfo> dataStateOfPlanNode(AbstractPlan planNode, + Map<Integer, Group> groupsById, LiteralMode mode) { + Group group = planNode.getGroupExpression().map(GroupExpression::getOwnerGroup).orElse(null); + if (group == null) { + Optional<Object> groupState = planNode.getMutableState(MutableState.KEY_GROUP); + if (groupState.isPresent() && groupsById != null) { + try { + group = groupsById.get(Integer.valueOf(groupState.get().toString())); + } catch (NumberFormatException ignored) { + group = null; + } + } + } + if (group == null) { + return Optional.empty(); + } + GroupStructInfo structInfo = of(group, mode); + return structInfo.isValid() ? Optional.of(structInfo) : Optional.empty(); + } + + /** + * Compute the simplified struct info (and its fingerprint) of a memo group, by traversing the + * group's logical expression and its child groups. + */ + public static GroupStructInfo of(Group group) { + return of(group, LiteralMode.WITH_LITERAL); + } + + /** + * Compute the simplified struct info of a memo group in the given literal mode. + */ + public static GroupStructInfo of(Group group, LiteralMode mode) { + HboStructSummary summary = group.getOrComputeHboStructSummary(); + int maxScansPerGroup = hboMaxScansPerGroup(); + if (maxScansPerGroup > 0 && summary.getScanCount() > maxScansPerGroup) { + // The canonical string of a group describes its whole sub tree, and for a chain of joins + // it is built once per group of that chain, so a cheap structural summary is used as a + // gate: a sub tree with more scan tokens than hbo_max_scans_per_group is not described at + // all (the read side falls back to the optimizer estimation and EXPLAIN reports why). + return new GroupStructInfo(false, "", "", "", INVALID_SCANS, "subtree scans=" + + summary.getScanCount() + " > hbo_max_scans_per_group=" + maxScansPerGroup); + } + Ctx ctx = new Ctx(mode); + try { + Canonical out = new Canonical(); + visit(group, out, ctx); + if (!ctx.valid) { + return INVALID; + } + String canonicalString = out.annotated.toString(); + String shapeString = out.shape.toString(); + String fingerprint = Hashing.sha256() + .hashString(shapeString, StandardCharsets.UTF_8).toString(); + return new GroupStructInfo(true, canonicalString, shapeString, fingerprint, + new ArrayList<>(out.getScans())); + } catch (RuntimeException e) { + // memo content not supported by the simplified struct info: treat as invalid and + // fall back to legacy behavior instead of failing the optimizer on the hot path + LOG.debug("failed to compute hbo struct info for group {}", group.getGroupId(), e); + return ctx.retryable ? TRANSIENT_FAILURE : INVALID; + } + } + + /** + * Visit a group and append its canonical description to {@code sb}. + */ + private static void visit(Group group, Canonical out, Ctx ctx) { + if (!ctx.valid) { + return; + } + if (!ctx.visited.add(group)) { + // shared sub graph (e.g. CTE / repeated child group): cannot be expressed by a single + // canonical tree, mark invalid so that callers fall back to legacy behavior + invalid(ctx); + return; + } + // Use the first logical expression to know the kind of the group head. The canonical forms + // below are insensitive to which expression is picked, so this choice cannot change the + // fingerprint of the group (see the class comment). + GroupExpression ge = group.getFirstLogicalExpression(); + if (ge == null) { + invalid(ctx); + return; + } + appendPlan(ge.getPlan(), ge, out, ctx); + } + + private static void appendPlan(Plan plan, GroupExpression ge, Canonical out, Ctx ctx) { + if (!ctx.valid) { + return; + } + if (plan instanceof LogicalOlapScan) { + appendScan((LogicalOlapScan) plan, out, ctx); + } else if (plan instanceof LogicalFilter) { + LogicalFilter<?> filter = (LogicalFilter<?>) plan; + out.append("F{").append(normalizedSorted(filter.getConjuncts(), ctx.mode)).append("}("); + appendChild(ge, 0, out, ctx); + out.append(")"); + } else if (plan instanceof LogicalProject) { Review Comment: 认可问题存在：project 在结构匹配里是透明的，Agg(Project(a%2 AS x)) 只渲染 col(x)，确实丢了 x 的定义。但把 project 表达式并入 canonical 会改变这类 group 的指纹（现存注入与 learned 条目的 key 全变），不适合混在本次“生成成本闸门”的提交里。计划单独提交：把非 forwarding project 的表达式并入 canonical，或对这类 group 直接判 INVALID（如果你要更窄的语义，我现在就按后者实现）。 ########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/GroupStructInfo.java: ########## @@ -0,0 +1,902 @@ +// 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.memo.Group; +import org.apache.doris.nereids.memo.GroupExpression; +import org.apache.doris.nereids.trees.expressions.And; +import org.apache.doris.nereids.trees.expressions.EqualTo; +import org.apache.doris.nereids.trees.expressions.Expression; +import org.apache.doris.nereids.trees.expressions.Or; +import org.apache.doris.nereids.trees.expressions.SlotReference; +import org.apache.doris.nereids.trees.expressions.literal.Literal; +import org.apache.doris.nereids.trees.plans.AbstractPlan; +import org.apache.doris.nereids.trees.plans.JoinType; +import org.apache.doris.nereids.trees.plans.Plan; +import org.apache.doris.nereids.trees.plans.logical.LogicalAggregate; +import org.apache.doris.nereids.trees.plans.logical.LogicalFilter; +import org.apache.doris.nereids.trees.plans.logical.LogicalJoin; +import org.apache.doris.nereids.trees.plans.logical.LogicalOlapScan; +import org.apache.doris.nereids.trees.plans.logical.LogicalProject; +import org.apache.doris.nereids.util.MutableState; +import org.apache.doris.qe.ConnectContext; + +import com.google.common.hash.Hashing; +import org.apache.logging.log4j.LogManager; +import org.apache.logging.log4j.Logger; + +import java.nio.charset.StandardCharsets; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.TreeSet; +import java.util.stream.Collectors; + +/** + * Simplified struct info of a memo {@link Group}, used by History Based Optimization (HBO). + * + * <p>The struct info is a property of the <b>group</b>, not of one of its group expressions: all + * expressions of a group are logically equivalent, so they describe the same set of relations with + * the same predicates, and the canonical form below is deliberately insensitive to which expression + * is picked. + * <ul> + * <li>join commutativity: children of a join are canonicalized by sorting;</li> + * <li>join associativity: a whole inner / cross join chain is emitted as one node + * ({@code J{inner,c:[...]}(...;...)}) whose children are the chain leaves sorted by their + * canonical form and whose conditions are the sorted union of every condition of the chain, + * so {@code (A join B) join C} and {@code A join (B join C)} produce the same descriptor;</li> + * <li>aggregation: only the group by keys and the child participate, because the output row count + * of an aggregation is the number of groups and cannot be changed by the aggregate functions + * or by the output expressions;</li> + * <li>project is transparent for structure matching.</li> + * </ul> + * This mirrors what the MV oriented {@code rules.exploration.mv.StructInfo} does (it identifies a + * sub tree by its relation set and by level independent - shuttled - predicates), with every MV + * specific field dropped: no hyper graph, no shuttle map, no equivalence class, no lineage. + * + * <p>What the canonical form keeps: + * <ul> + * <li>for each scan: the table qualifier and - as an annotation only - the data state of the scan + * (its visible version, the rows it reads and how many of the table partitions it selects, + * see {@link HboScanDescriptor});</li> + * <li>for filter / join / aggregate: the normalized predicates / join conditions / grouping keys, + * i.e. the structural pattern only (slot and expression ids are stripped by + * {@link #normalizeExpression}).</li> + * </ul> + * The string contains no per-query identifier, so it is reproducible across runs and queries for + * structurally identical sub trees, and its sha256 is used as the HBO cache key (fingerprint). + * + * <p>The sha256 is taken over the canonical string <b>without</b> the scan baselines + * ({@link #stripScanBaseline}): a hbo key identifies a plan pattern and the relation it reads, not a + * data state, so an entry whose table simply keeps growing stays matchable instead of silently never + * matching again. Whether an entry may still be applied is decided on the read side, by comparing + * the baseline of the entry with the data state of the current query (see + * {@link HboStructFreshness}). + * + * <p>The descriptor is derived from the group's logical expression and its child groups (memo level + * traversal, with a visited set to guard shared sub graphs such as CTE). Groups whose content is not + * supported (e.g. contains TVF / CTE consumer, or the head operator is not one of the supported + * kinds) are {@link #isValid() invalid} and callers must fall back to the legacy behavior. + */ +public class GroupStructInfo { + private static final List<HboScanDescriptor> INVALID_SCANS = Collections.emptyList(); + + /** Shared invalid instance: the group content is not supported by the simplified struct info. */ + public static final GroupStructInfo INVALID = new GroupStructInfo(false, "", "", "", INVALID_SCANS); + /** + * Shared instance for a failure which is not a property of the plan: the table state could not be + * read (e.g. the visible version of a cloud table could not be fetched). Unlike + * {@link #INVALID} it is not cached by the memo (see {@code Group#getOrComputeHboStructInfo}), so + * the next lookup of the same group retries instead of disabling hbo struct info for the whole + * query. + */ + public static final GroupStructInfo TRANSIENT_FAILURE = + new GroupStructInfo(false, "", "", "", INVALID_SCANS); + + private static final String SEP = ";"; + private static final Logger LOG = LogManager.getLogger(GroupStructInfo.class); + + /** + * Whether literal values participate in the canonical string / fingerprint. + * <ul> + * <li>{@link #WITH_LITERAL} keeps the literal value ({@code lit(10:int)}): the fingerprint is + * bound to the exact constants, used for filter roots where the constant changes the + * output row count;</li> + * <li>{@link #NO_LITERAL} replaces every literal value with {@code *} ({@code lit(*)}): the + * fingerprint is constant agnostic, used for join / aggregate roots and for the + * constant-free filter shape.</li> + * </ul> + * The literal data type is intentionally not kept: nereids inserts an explicit {@code Cast} + * for mismatching operand types, so two semantically different literal forms already differ by + * the cast node, while equivalent forms (e.g. {@code d > 1} and {@code d > 1.0} on a decimal + * column) are allowed to collapse. + */ + public enum LiteralMode { + WITH_LITERAL, + NO_LITERAL + } + + private final boolean valid; + private final String canonicalString; + /** The canonical string without the scan baselines: the fingerprint input. */ + private final String shapeString; + private final String fingerprint; + /** The scans of the sub tree, in the order their tokens appear in the canonical string. */ + private final List<HboScanDescriptor> scans; + /** Why no struct info was built, when it was refused by a limit instead of being unsupported. */ + private final String skipReason; + + private GroupStructInfo(boolean valid, String canonicalString, String shapeString, String fingerprint, + List<HboScanDescriptor> scans) { + this(valid, canonicalString, shapeString, fingerprint, scans, ""); + } + + private GroupStructInfo(boolean valid, String canonicalString, String shapeString, String fingerprint, + List<HboScanDescriptor> scans, String skipReason) { + this.valid = valid; + this.canonicalString = canonicalString; + this.shapeString = shapeString; + this.fingerprint = fingerprint; + this.scans = scans; + this.skipReason = skipReason; + } + + /** The reason the struct info was refused by a limit, or empty. Only for diagnostics. */ + public String getSkipReason() { + return skipReason; + } + + public boolean isValid() { + return valid; + } + + public String getCanonicalString() { + return canonicalString; + } + + /** + * The fingerprint input: the canonical string with the baseline of every scan token removed + * ({@code S{db.t}}). It is built from the traversal itself and not by parsing the canonical + * string, so no text inside a table name or a literal can be mistaken for a scan token. + */ + public String getShapeString() { + return shapeString; + } + + /** + * The row count and partition selection of every scan of the sub tree, in the order the scan + * tokens appear in the canonical string (i.e. the order a user sees when pasting the struct + * info). Empty when the struct info is invalid. + */ + public List<HboScanDescriptor> getScans() { + return scans; + } + + public String getFingerprint() { + return fingerprint; + } + + /** + * Resolve the fingerprint of the memo group that {@code planNode} belongs to, when the node + * still carries its {@link GroupExpression} back reference (memo inner plans, or plans from + * {@code chooseBestPlan}). Empty when the group content is unsupported (invalid struct info). + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode) { + return fingerprintOfPlanNode(planNode, LiteralMode.WITH_LITERAL); + } + + /** + * Resolve the group fingerprint of a plan node in the given literal mode. + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode, LiteralMode mode) { + return fingerprintOfGroup(planNode.getGroupExpression() + .map(GroupExpression::getOwnerGroup).orElse(null), mode); + } + + /** + * Resolve the fingerprint of the group that {@code planNode} belongs to, with a fallback to + * the {@link MutableState#KEY_GROUP} group-id state that post processors propagate to their + * rewritten copies (see {@code copyStatsAndGroupIdFrom}). {@code groupsById} maps memo group + * id to group, and is looked up only when the back reference is absent. + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode, Map<Integer, Group> groupsById) { + return fingerprintOfPlanNode(planNode, groupsById, LiteralMode.WITH_LITERAL); + } + + /** + * Resolve the group fingerprint of a plan node in the given literal mode, with the + * {@link MutableState#KEY_GROUP} fallback for post-processed copies. + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode, Map<Integer, Group> groupsById, + LiteralMode mode) { + return structInfoOfPlanNode(planNode, groupsById, mode).map(GroupStructInfo::getFingerprint); + } + + private static Optional<String> fingerprintOfGroup(Group group, LiteralMode mode) { + return structInfoOfGroup(group, mode).map(GroupStructInfo::getFingerprint); + } + + /** + * Resolve the {@link GroupStructInfo} (with canonical string and fingerprint) of the group a + * plan node belongs to, using the group-expression back reference or the KEY_GROUP group-id + * state propagated by post processors (see {@link #fingerprintOfPlanNode}). + */ + public static Optional<GroupStructInfo> structInfoOfPlanNode(AbstractPlan planNode, + Map<Integer, Group> groupsById) { + return structInfoOfPlanNode(planNode, groupsById, LiteralMode.WITH_LITERAL); + } + + /** + * Resolve the struct info of the group a plan node belongs to, in the given literal mode. + */ + public static Optional<GroupStructInfo> structInfoOfPlanNode(AbstractPlan planNode, + Map<Integer, Group> groupsById, LiteralMode mode) { + Group group = planNode.getGroupExpression().map(GroupExpression::getOwnerGroup).orElse(null); + if (group == null) { + Optional<Object> groupState = planNode.getMutableState(MutableState.KEY_GROUP); + if (groupState.isPresent() && groupsById != null) { + try { + group = groupsById.get(Integer.valueOf(groupState.get().toString())); + } catch (NumberFormatException ignored) { + group = null; + } + } + } + return structInfoOfGroup(group, mode); + } + + private static Optional<GroupStructInfo> structInfoOfGroup(Group group, LiteralMode mode) { + if (group == null) { + return Optional.empty(); + } + GroupStructInfo structInfo = group.getOrComputeHboStructInfo(mode); + return structInfo.isValid() ? Optional.of(structInfo) : Optional.empty(); + } + + /** + * The struct info of the group a plan node belongs to, computed now instead of being taken from + * the per-group cache. The fingerprint does not depend on any data state, so the cached struct + * info is the right source for a lookup; its <b>baseline</b> (the visible version and the row + * counts of its scans) is however a snapshot of the moment it was computed, which may be well + * before the query is planned. Whoever displays that baseline (EXPLAIN prints it as the + * {@code struct=} a user pastes into {@code HBO SET STATISTICS}) or compares it (the drift + * verdict) must therefore ask for it here, so that the whole query reports one data state. + */ + public static Optional<GroupStructInfo> dataStateOfPlanNode(AbstractPlan planNode, + Map<Integer, Group> groupsById, LiteralMode mode) { + Group group = planNode.getGroupExpression().map(GroupExpression::getOwnerGroup).orElse(null); + if (group == null) { + Optional<Object> groupState = planNode.getMutableState(MutableState.KEY_GROUP); + if (groupState.isPresent() && groupsById != null) { + try { + group = groupsById.get(Integer.valueOf(groupState.get().toString())); + } catch (NumberFormatException ignored) { + group = null; + } + } + } + if (group == null) { + return Optional.empty(); + } + GroupStructInfo structInfo = of(group, mode); + return structInfo.isValid() ? Optional.of(structInfo) : Optional.empty(); + } + + /** + * Compute the simplified struct info (and its fingerprint) of a memo group, by traversing the + * group's logical expression and its child groups. + */ + public static GroupStructInfo of(Group group) { + return of(group, LiteralMode.WITH_LITERAL); + } + + /** + * Compute the simplified struct info of a memo group in the given literal mode. + */ + public static GroupStructInfo of(Group group, LiteralMode mode) { + HboStructSummary summary = group.getOrComputeHboStructSummary(); + int maxScansPerGroup = hboMaxScansPerGroup(); + if (maxScansPerGroup > 0 && summary.getScanCount() > maxScansPerGroup) { + // The canonical string of a group describes its whole sub tree, and for a chain of joins + // it is built once per group of that chain, so a cheap structural summary is used as a + // gate: a sub tree with more scan tokens than hbo_max_scans_per_group is not described at + // all (the read side falls back to the optimizer estimation and EXPLAIN reports why). + return new GroupStructInfo(false, "", "", "", INVALID_SCANS, "subtree scans=" + + summary.getScanCount() + " > hbo_max_scans_per_group=" + maxScansPerGroup); + } + Ctx ctx = new Ctx(mode); + try { + Canonical out = new Canonical(); + visit(group, out, ctx); + if (!ctx.valid) { + return INVALID; + } + String canonicalString = out.annotated.toString(); + String shapeString = out.shape.toString(); + String fingerprint = Hashing.sha256() + .hashString(shapeString, StandardCharsets.UTF_8).toString(); + return new GroupStructInfo(true, canonicalString, shapeString, fingerprint, + new ArrayList<>(out.getScans())); + } catch (RuntimeException e) { + // memo content not supported by the simplified struct info: treat as invalid and + // fall back to legacy behavior instead of failing the optimizer on the hot path + LOG.debug("failed to compute hbo struct info for group {}", group.getGroupId(), e); + return ctx.retryable ? TRANSIENT_FAILURE : INVALID; + } + } + + /** + * Visit a group and append its canonical description to {@code sb}. + */ + private static void visit(Group group, Canonical out, Ctx ctx) { + if (!ctx.valid) { + return; + } + if (!ctx.visited.add(group)) { + // shared sub graph (e.g. CTE / repeated child group): cannot be expressed by a single + // canonical tree, mark invalid so that callers fall back to legacy behavior + invalid(ctx); + return; + } + // Use the first logical expression to know the kind of the group head. The canonical forms + // below are insensitive to which expression is picked, so this choice cannot change the + // fingerprint of the group (see the class comment). + GroupExpression ge = group.getFirstLogicalExpression(); + if (ge == null) { + invalid(ctx); + return; + } + appendPlan(ge.getPlan(), ge, out, ctx); + } + + private static void appendPlan(Plan plan, GroupExpression ge, Canonical out, Ctx ctx) { + if (!ctx.valid) { + return; + } + if (plan instanceof LogicalOlapScan) { + appendScan((LogicalOlapScan) plan, out, ctx); + } else if (plan instanceof LogicalFilter) { + LogicalFilter<?> filter = (LogicalFilter<?>) plan; + out.append("F{").append(normalizedSorted(filter.getConjuncts(), ctx.mode)).append("}("); + appendChild(ge, 0, out, ctx); + out.append(")"); + } else if (plan instanceof LogicalProject) { + // project is transparent for structure matching + if (ge.arity() == 1) { + appendChild(ge, 0, out, ctx); + } else { + invalid(ctx); + } + } else if (plan instanceof LogicalJoin) { + appendJoin((LogicalJoin<?, ?>) plan, ge, out, ctx); + } else if (plan instanceof LogicalAggregate) { + appendAggregate((LogicalAggregate<?>) plan, ge, out, ctx); + } else { + // unsupported head operator (sort/topn/limit/window/union/cte/tvf/...) + invalid(ctx); + } + } + + private static void appendJoin(LogicalJoin<?, ?> join, GroupExpression ge, Canonical out, Ctx ctx) { + if (isFlattenableJoinType(join.getJoinType())) { + appendJoinChain(join, ge, out, ctx); + return; + } + // Outer / semi / anti / asof joins: the two sides are semantically different and the join + // cannot be reassociated, so the memo order of the children and the join type are kept. + out.append("J{").append(join.getJoinType().toString()); + out.append(",c:[").append(normalizedJoinConditions(join, ctx.mode)).append("]}("); + appendChild(ge, 0, out, ctx); + out.append(SEP); + appendChild(ge, 1, out, ctx); + out.append(")"); + } + + /** + * Append the canonical form of a whole inner / cross join chain as a single node. + * + * <p>Inner and cross joins are associative and commutative, so the grouping of the chain is an + * artifact of the explored expression and must not be part of the fingerprint: the chain is + * emitted as {@code J{inner,c:[...]}(leaf;leaf;...)} with the conditions of every join of the + * chain merged into one sorted set and the leaves (scans, filters, aggregations, non + * flattenable joins) sorted by their canonical form. Every expression of a group therefore + * produces the same descriptor. Cross joins are merged with inner joins because a cross join is + * exactly an inner join without condition, and both have the same output row count. + */ + private static void appendJoinChain(LogicalJoin<?, ?> join, GroupExpression ge, Canonical out, Ctx ctx) { + TreeSet<String> conditions = new TreeSet<>(); + List<Leaf> leaves = new ArrayList<>(); + collectJoinConditions(join, conditions, ctx.mode); + for (int i = 0; i < ge.arity(); i++) { + collectJoinChain(ge.child(i), conditions, leaves, ctx); + } + if (!ctx.valid) { + return; + } + // the leaves are ordered by their fingerprint input (their own shape, i.e. without the data + // state of their scans): the order is part of the fingerprint, so it must not depend on a + // data state which the fingerprint deliberately ignores + leaves.sort(Comparator.comparing(Leaf::getShape)); + out.append("J{inner,c:[").append(String.join(SEP, conditions)).append("]}("); + for (int i = 0; i < leaves.size(); i++) { + if (i > 0) { + out.append(SEP); + } + out.append(leaves.get(i).getCanonical()); + } + out.append(")"); + } + + /** + * Collect one member of an inner / cross join chain: either descend into another join of the + * chain (associativity), or append the canonical form of the whole sub tree as one chain leaf. + * The group of {@code ge} is already marked visited by the caller. + */ + private static void collectJoinChain(Group group, TreeSet<String> conditions, List<Leaf> leaves, Ctx ctx) { + if (!ctx.valid) { + return; + } + if (!ctx.visited.add(group)) { + invalid(ctx); + return; + } + GroupExpression ge = group.getFirstLogicalExpression(); + if (ge == null) { + invalid(ctx); + return; + } + Plan plan = ge.getPlan(); + if (plan instanceof LogicalJoin && isFlattenableJoinType(((LogicalJoin<?, ?>) plan).getJoinType())) { + collectJoinConditions((LogicalJoin<?, ?>) plan, conditions, ctx.mode); + for (int i = 0; i < ge.arity(); i++) { + collectJoinChain(ge.child(i), conditions, leaves, ctx); + } + return; + } + if (plan instanceof LogicalProject && ge.arity() == 1) { + // keep descending through projects so that a project between two joins cannot break the + // chain in one expression and not in another + collectJoinChain(ge.child(0), conditions, leaves, ctx); + return; + } + Canonical leaf = new Canonical(); + appendPlan(plan, ge, leaf, ctx); + if (ctx.valid) { + leaves.add(new Leaf(leaf)); + } + } + + /** One leaf of a flattened join chain: both of its canonical forms and its scans. */ + private static class Leaf { + private final Canonical canonical; + + Leaf(Canonical canonical) { + this.canonical = canonical; + } + + Canonical getCanonical() { + return canonical; + } + + String getShape() { + return canonical.shape.toString(); + } + } + + /** Inner and cross joins may be reordered, reassociated and therefore flattened. */ + private static boolean isFlattenableJoinType(JoinType joinType) { + return joinType == JoinType.INNER_JOIN || joinType == JoinType.CROSS_JOIN; + } + + private static void appendAggregate(LogicalAggregate<?> agg, GroupExpression ge, Canonical out, Ctx ctx) { + // Only the grouping keys and the child take part: the output row count of an aggregation is + // the number of groups, which the aggregate functions and the output expressions cannot + // change, so keeping them would only split one plan pattern into several cache entries. + out.append("A{gb:").append(normalizedSorted(agg.getGroupByExpressions(), ctx.mode)); + out.append("}("); + appendChild(ge, 0, out, ctx); + out.append(")"); + } + + private static void invalid(Ctx ctx) { + ctx.valid = false; + } + + /** Mark the struct info invalid because the table state could not be read (retryable). */ + private static void transientFailure(Ctx ctx) { + ctx.valid = false; + ctx.retryable = true; + } + + private static void appendScan(LogicalOlapScan scan, Canonical out, Ctx ctx) { + try { + // the scan token is the table plus the data state of the scan (baseline). Its shape form + // is the table alone and is written by this very call, so the fingerprint input is never + // derived by parsing the canonical string: no table name and no literal value can be + // mistaken for a scan token. + HboScanDescriptor descriptor = HboScanDescriptor.of(scan); + if (descriptor.getTable().indexOf(',') >= 0 || descriptor.getTable().indexOf('}') >= 0) { + // the token delimiters cannot appear in a table name: the printed struct info could + // not be read back, and a pasted one could resolve to another table + LOG.debug("scan table {} contains a struct info delimiter, hbo is disabled for it", + descriptor.getTable()); + invalid(ctx); + return; + } + out.annotated.append("S{").append(descriptor.render()).append('}'); + out.shape.append("S{").append(descriptor.getTable()).append('}'); + out.getScans().add(descriptor); + } catch (org.apache.doris.rpc.RpcException e) { + // the table version may not be readable (e.g. a cloud rpc failure): the group stays + // invalid for this lookup, but the failure is retried by the next one + LOG.debug("failed to get visible version for scan {}", scan.getTable().getNameWithFullQualifiers(), e); + transientFailure(ctx); + } + } + + /** + * Remove the baseline of every scan token of a canonical string ({@code S{db.t,v3,r1000,p1/5}} + * becomes {@code S{db.t}}), i.e. the data state of the scan - visible version, scanned rows and + * pruned partition count. + * + * <p>The fingerprint of a plan and the sort key of a join chain leaf are built by the traversal + * itself, which knows where every scan token starts and ends. This text based variant is only for + * the struct info a user pasted into {@code HBO SET STATISTICS}, whose sha256 has to match the + * fingerprint the user copied. A literal value which looks like a scan token (a string which + * starts like one and contains a comma) cannot be told apart from one there, so such a struct + * info is rejected: that statement cannot be used for that node, in either literal mode + * (there is no workaround). That is a rejected statement, never a wrong key - the fingerprint of + * a plan is not computed by this method. A table name which contains the delimiters is not + * printed at all, because such a canonical form could not be read back (see the scan token in + * {@code appendScan}). + */ + public static String stripScanBaseline(String canonicalString) { + StringBuilder sb = new StringBuilder(canonicalString.length()); + int index = 0; + while (true) { + int start = HboScanDescriptor.nextScanTokenStart(canonicalString, index); + int end = start < 0 ? -1 : canonicalString.indexOf('}', start); + if (end < 0) { + sb.append(canonicalString, index, canonicalString.length()); + break; + } + String header = canonicalString.substring(start + 2, end); + int comma = header.indexOf(','); + sb.append(canonicalString, index, start).append("S{") + .append(comma < 0 ? header : header.substring(0, comma)).append('}'); + index = end + 1; + } + return sb.toString(); + } + + private static void appendChild(GroupExpression ge, int index, Canonical out, Ctx ctx) { + if (!ctx.valid) { + return; + } + // the child is built on its own form, so that its scans are appended in the order its tokens + // appear in the parent string + Canonical child = new Canonical(); + visit(ge.child(index), child, ctx); + out.append(child); + } + + // ----------------------------------------------------------------------------------- + // expression normalization: strip slot/expr ids, keep qualifier + column + literal value + // ----------------------------------------------------------------------------------- + + private static String normalizedSorted(Set<Expression> conjuncts, LiteralMode mode) { + return conjuncts.stream().map(e -> normalizeExpression(e, mode)).sorted() + .collect(Collectors.joining(SEP)); + } + + private static String normalizedSorted(List<Expression> conjuncts, LiteralMode mode) { + return conjuncts.stream().map(e -> normalizeExpression(e, mode)).sorted() + .collect(Collectors.joining(SEP)); + } + + /** + * Render all conditions of one join node (hash and other conjuncts) as one sorted, de + * duplicated set: whether a given conjunct is classified as a hash conjunct or as an other + * conjunct depends on the grouping of the chain, so that classification cannot be part of a + * canonical form that has to be insensitive to the grouping. + */ + private static String normalizedJoinConditions(LogicalJoin<?, ?> join, LiteralMode mode) { + TreeSet<String> conditions = new TreeSet<>(); + collectJoinConditions(join, conditions, mode); + return String.join(SEP, conditions); + } + + private static void collectJoinConditions(LogicalJoin<?, ?> join, Set<String> conditions, LiteralMode mode) { + for (Expression conjunct : join.getHashJoinConjuncts()) { + conditions.add(normalizeExpression(conjunct, mode)); + } + for (Expression conjunct : join.getOtherJoinConjuncts()) { + conditions.add(normalizeExpression(conjunct, mode)); + } + } + + /** + * Rewrite every literal of a canonical string into its constant agnostic form ({@code lit(*)}), + * i.e. turn a WITH_LITERAL canonical string into the NO_LITERAL one. Used to accept a struct info + * which a user copied from a filter node of EXPLAIN for the constant agnostic fingerprint of the + * same node. + * + * <p>A literal value is not quoted in the canonical form and a data type may even contain + * parentheses ({@code lit(abc:VARCHAR(10))}), so the closing parenthesis is found by counting + * instead of by a regular expression; a value with balanced parentheses + * ({@code lit(IL (north))}) is therefore folded correctly. Only an <b>unbalanced</b> parenthesis + * in a value (e.g. {@code where city = 'IL)'}) makes the fold consume too much, and the pasted + * struct info is then rejected by the fingerprint check of {@code HBO SET STATISTICS} with the + * generic "does not match the fingerprint" message; there is no workaround, because the check + * runs in both literal modes. The constant agnostic struct info printed by EXPLAIN is built by the + * group traversal itself (see {@link #dataStateOfPlanNode}), so it has no such limitation. + */ + public static String toNoLiteral(String canonicalString) { + StringBuilder sb = new StringBuilder(canonicalString.length()); + int index = 0; + while (index < canonicalString.length()) { + int start = canonicalString.indexOf("lit(", index); + if (start < 0) { + sb.append(canonicalString, index, canonicalString.length()); + break; + } + sb.append(canonicalString, index, start).append("lit(*)"); + int depth = 0; + int cursor = start + 3; + while (cursor < canonicalString.length()) { + char c = canonicalString.charAt(cursor); + if (c == '(') { + depth++; + } else if (c == ')') { + depth--; + if (depth == 0) { + cursor++; + break; + } + } + cursor++; + } + index = cursor; + } + return sb.toString(); + } + + /** + * Normalize a single expression into its canonical component (slot -> {@code col(qualifier.name)}, + * literal -> {@code lit(value:type)} / {@code lit(*)}, other nodes -> {@code ClassName(children)}). + * Shared with the hbo join-condition canonicalizer. + */ + public static String normalizeExpression(Expression expression) { + return normalizeExpression(expression, LiteralMode.WITH_LITERAL); + } + + private static String normalizeExpression(Expression expression, LiteralMode mode) { + if (expression instanceof SlotReference) { + SlotReference slot = (SlotReference) expression; + return "col(" + String.join(".", slot.getQualifier()) + "." + slot.getName() + ")"; + } else if (expression instanceof Literal) { + if (mode == LiteralMode.NO_LITERAL) { + return "lit(*)"; + } + Literal literal = (Literal) expression; + return "lit(" + literal.getValue() + ":" + literal.getDataType() + ")"; + } else if (expression.children().isEmpty()) { + return expression.getClass().getSimpleName(); + } else { + List<Expression> children = expression.children(); + List<String> normalizedChildren = children.stream() + .map(e -> normalizeExpression(e, mode)).collect(Collectors.toList()); + if (isOrderInsensitive(expression)) { + // only order-insensitive operators (equal-to / and / or) may have their operands + // sorted; ordered comparisons (e.g. '<') must keep the original order, otherwise + // `col < 5` and `5 < col` would collapse to the same descriptor (review B2). + normalizedChildren.sort(String::compareTo); + } + String childrenStr = String.join(",", normalizedChildren); + return expression.getClass().getSimpleName() + "(" + childrenStr + ")"; Review Comment: 认可。Cast 走 ClassName(children) 渲染，targetType/strict 不在 children 里，CAST(a AS TINYINT) 与 CAST(a AS BIGINT) 同 key。修法很小，但会改 filter WITH_LITERAL 的指纹，属于 key 语义变更；本 PR 未合入，可以做，请确认接受 key 变更后我补提交。 ########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/GroupStructInfo.java: ########## @@ -0,0 +1,902 @@ +// 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.memo.Group; +import org.apache.doris.nereids.memo.GroupExpression; +import org.apache.doris.nereids.trees.expressions.And; +import org.apache.doris.nereids.trees.expressions.EqualTo; +import org.apache.doris.nereids.trees.expressions.Expression; +import org.apache.doris.nereids.trees.expressions.Or; +import org.apache.doris.nereids.trees.expressions.SlotReference; +import org.apache.doris.nereids.trees.expressions.literal.Literal; +import org.apache.doris.nereids.trees.plans.AbstractPlan; +import org.apache.doris.nereids.trees.plans.JoinType; +import org.apache.doris.nereids.trees.plans.Plan; +import org.apache.doris.nereids.trees.plans.logical.LogicalAggregate; +import org.apache.doris.nereids.trees.plans.logical.LogicalFilter; +import org.apache.doris.nereids.trees.plans.logical.LogicalJoin; +import org.apache.doris.nereids.trees.plans.logical.LogicalOlapScan; +import org.apache.doris.nereids.trees.plans.logical.LogicalProject; +import org.apache.doris.nereids.util.MutableState; +import org.apache.doris.qe.ConnectContext; + +import com.google.common.hash.Hashing; +import org.apache.logging.log4j.LogManager; +import org.apache.logging.log4j.Logger; + +import java.nio.charset.StandardCharsets; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.TreeSet; +import java.util.stream.Collectors; + +/** + * Simplified struct info of a memo {@link Group}, used by History Based Optimization (HBO). + * + * <p>The struct info is a property of the <b>group</b>, not of one of its group expressions: all + * expressions of a group are logically equivalent, so they describe the same set of relations with + * the same predicates, and the canonical form below is deliberately insensitive to which expression + * is picked. + * <ul> + * <li>join commutativity: children of a join are canonicalized by sorting;</li> + * <li>join associativity: a whole inner / cross join chain is emitted as one node + * ({@code J{inner,c:[...]}(...;...)}) whose children are the chain leaves sorted by their + * canonical form and whose conditions are the sorted union of every condition of the chain, + * so {@code (A join B) join C} and {@code A join (B join C)} produce the same descriptor;</li> + * <li>aggregation: only the group by keys and the child participate, because the output row count + * of an aggregation is the number of groups and cannot be changed by the aggregate functions + * or by the output expressions;</li> + * <li>project is transparent for structure matching.</li> + * </ul> + * This mirrors what the MV oriented {@code rules.exploration.mv.StructInfo} does (it identifies a + * sub tree by its relation set and by level independent - shuttled - predicates), with every MV + * specific field dropped: no hyper graph, no shuttle map, no equivalence class, no lineage. + * + * <p>What the canonical form keeps: + * <ul> + * <li>for each scan: the table qualifier and - as an annotation only - the data state of the scan + * (its visible version, the rows it reads and how many of the table partitions it selects, + * see {@link HboScanDescriptor});</li> + * <li>for filter / join / aggregate: the normalized predicates / join conditions / grouping keys, + * i.e. the structural pattern only (slot and expression ids are stripped by + * {@link #normalizeExpression}).</li> + * </ul> + * The string contains no per-query identifier, so it is reproducible across runs and queries for + * structurally identical sub trees, and its sha256 is used as the HBO cache key (fingerprint). + * + * <p>The sha256 is taken over the canonical string <b>without</b> the scan baselines + * ({@link #stripScanBaseline}): a hbo key identifies a plan pattern and the relation it reads, not a + * data state, so an entry whose table simply keeps growing stays matchable instead of silently never + * matching again. Whether an entry may still be applied is decided on the read side, by comparing + * the baseline of the entry with the data state of the current query (see + * {@link HboStructFreshness}). + * + * <p>The descriptor is derived from the group's logical expression and its child groups (memo level + * traversal, with a visited set to guard shared sub graphs such as CTE). Groups whose content is not + * supported (e.g. contains TVF / CTE consumer, or the head operator is not one of the supported + * kinds) are {@link #isValid() invalid} and callers must fall back to the legacy behavior. + */ +public class GroupStructInfo { + private static final List<HboScanDescriptor> INVALID_SCANS = Collections.emptyList(); + + /** Shared invalid instance: the group content is not supported by the simplified struct info. */ + public static final GroupStructInfo INVALID = new GroupStructInfo(false, "", "", "", INVALID_SCANS); + /** + * Shared instance for a failure which is not a property of the plan: the table state could not be + * read (e.g. the visible version of a cloud table could not be fetched). Unlike + * {@link #INVALID} it is not cached by the memo (see {@code Group#getOrComputeHboStructInfo}), so + * the next lookup of the same group retries instead of disabling hbo struct info for the whole + * query. + */ + public static final GroupStructInfo TRANSIENT_FAILURE = + new GroupStructInfo(false, "", "", "", INVALID_SCANS); + + private static final String SEP = ";"; + private static final Logger LOG = LogManager.getLogger(GroupStructInfo.class); + + /** + * Whether literal values participate in the canonical string / fingerprint. + * <ul> + * <li>{@link #WITH_LITERAL} keeps the literal value ({@code lit(10:int)}): the fingerprint is + * bound to the exact constants, used for filter roots where the constant changes the + * output row count;</li> + * <li>{@link #NO_LITERAL} replaces every literal value with {@code *} ({@code lit(*)}): the + * fingerprint is constant agnostic, used for join / aggregate roots and for the + * constant-free filter shape.</li> + * </ul> + * The literal data type is intentionally not kept: nereids inserts an explicit {@code Cast} + * for mismatching operand types, so two semantically different literal forms already differ by + * the cast node, while equivalent forms (e.g. {@code d > 1} and {@code d > 1.0} on a decimal + * column) are allowed to collapse. + */ + public enum LiteralMode { + WITH_LITERAL, + NO_LITERAL + } + + private final boolean valid; + private final String canonicalString; + /** The canonical string without the scan baselines: the fingerprint input. */ + private final String shapeString; + private final String fingerprint; + /** The scans of the sub tree, in the order their tokens appear in the canonical string. */ + private final List<HboScanDescriptor> scans; + /** Why no struct info was built, when it was refused by a limit instead of being unsupported. */ + private final String skipReason; + + private GroupStructInfo(boolean valid, String canonicalString, String shapeString, String fingerprint, + List<HboScanDescriptor> scans) { + this(valid, canonicalString, shapeString, fingerprint, scans, ""); + } + + private GroupStructInfo(boolean valid, String canonicalString, String shapeString, String fingerprint, + List<HboScanDescriptor> scans, String skipReason) { + this.valid = valid; + this.canonicalString = canonicalString; + this.shapeString = shapeString; + this.fingerprint = fingerprint; + this.scans = scans; + this.skipReason = skipReason; + } + + /** The reason the struct info was refused by a limit, or empty. Only for diagnostics. */ + public String getSkipReason() { + return skipReason; + } + + public boolean isValid() { + return valid; + } + + public String getCanonicalString() { + return canonicalString; + } + + /** + * The fingerprint input: the canonical string with the baseline of every scan token removed + * ({@code S{db.t}}). It is built from the traversal itself and not by parsing the canonical + * string, so no text inside a table name or a literal can be mistaken for a scan token. + */ + public String getShapeString() { + return shapeString; + } + + /** + * The row count and partition selection of every scan of the sub tree, in the order the scan + * tokens appear in the canonical string (i.e. the order a user sees when pasting the struct + * info). Empty when the struct info is invalid. + */ + public List<HboScanDescriptor> getScans() { + return scans; + } + + public String getFingerprint() { + return fingerprint; + } + + /** + * Resolve the fingerprint of the memo group that {@code planNode} belongs to, when the node + * still carries its {@link GroupExpression} back reference (memo inner plans, or plans from + * {@code chooseBestPlan}). Empty when the group content is unsupported (invalid struct info). + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode) { + return fingerprintOfPlanNode(planNode, LiteralMode.WITH_LITERAL); + } + + /** + * Resolve the group fingerprint of a plan node in the given literal mode. + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode, LiteralMode mode) { + return fingerprintOfGroup(planNode.getGroupExpression() + .map(GroupExpression::getOwnerGroup).orElse(null), mode); + } + + /** + * Resolve the fingerprint of the group that {@code planNode} belongs to, with a fallback to + * the {@link MutableState#KEY_GROUP} group-id state that post processors propagate to their + * rewritten copies (see {@code copyStatsAndGroupIdFrom}). {@code groupsById} maps memo group + * id to group, and is looked up only when the back reference is absent. + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode, Map<Integer, Group> groupsById) { + return fingerprintOfPlanNode(planNode, groupsById, LiteralMode.WITH_LITERAL); + } + + /** + * Resolve the group fingerprint of a plan node in the given literal mode, with the + * {@link MutableState#KEY_GROUP} fallback for post-processed copies. + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode, Map<Integer, Group> groupsById, + LiteralMode mode) { + return structInfoOfPlanNode(planNode, groupsById, mode).map(GroupStructInfo::getFingerprint); + } + + private static Optional<String> fingerprintOfGroup(Group group, LiteralMode mode) { + return structInfoOfGroup(group, mode).map(GroupStructInfo::getFingerprint); + } + + /** + * Resolve the {@link GroupStructInfo} (with canonical string and fingerprint) of the group a + * plan node belongs to, using the group-expression back reference or the KEY_GROUP group-id + * state propagated by post processors (see {@link #fingerprintOfPlanNode}). + */ + public static Optional<GroupStructInfo> structInfoOfPlanNode(AbstractPlan planNode, + Map<Integer, Group> groupsById) { + return structInfoOfPlanNode(planNode, groupsById, LiteralMode.WITH_LITERAL); + } + + /** + * Resolve the struct info of the group a plan node belongs to, in the given literal mode. + */ + public static Optional<GroupStructInfo> structInfoOfPlanNode(AbstractPlan planNode, + Map<Integer, Group> groupsById, LiteralMode mode) { + Group group = planNode.getGroupExpression().map(GroupExpression::getOwnerGroup).orElse(null); + if (group == null) { + Optional<Object> groupState = planNode.getMutableState(MutableState.KEY_GROUP); + if (groupState.isPresent() && groupsById != null) { + try { + group = groupsById.get(Integer.valueOf(groupState.get().toString())); + } catch (NumberFormatException ignored) { + group = null; + } + } + } + return structInfoOfGroup(group, mode); + } + + private static Optional<GroupStructInfo> structInfoOfGroup(Group group, LiteralMode mode) { + if (group == null) { + return Optional.empty(); + } + GroupStructInfo structInfo = group.getOrComputeHboStructInfo(mode); + return structInfo.isValid() ? Optional.of(structInfo) : Optional.empty(); + } + + /** + * The struct info of the group a plan node belongs to, computed now instead of being taken from + * the per-group cache. The fingerprint does not depend on any data state, so the cached struct + * info is the right source for a lookup; its <b>baseline</b> (the visible version and the row + * counts of its scans) is however a snapshot of the moment it was computed, which may be well + * before the query is planned. Whoever displays that baseline (EXPLAIN prints it as the + * {@code struct=} a user pastes into {@code HBO SET STATISTICS}) or compares it (the drift + * verdict) must therefore ask for it here, so that the whole query reports one data state. + */ + public static Optional<GroupStructInfo> dataStateOfPlanNode(AbstractPlan planNode, + Map<Integer, Group> groupsById, LiteralMode mode) { + Group group = planNode.getGroupExpression().map(GroupExpression::getOwnerGroup).orElse(null); + if (group == null) { + Optional<Object> groupState = planNode.getMutableState(MutableState.KEY_GROUP); + if (groupState.isPresent() && groupsById != null) { + try { + group = groupsById.get(Integer.valueOf(groupState.get().toString())); + } catch (NumberFormatException ignored) { + group = null; + } + } + } + if (group == null) { + return Optional.empty(); + } + GroupStructInfo structInfo = of(group, mode); + return structInfo.isValid() ? Optional.of(structInfo) : Optional.empty(); + } + + /** + * Compute the simplified struct info (and its fingerprint) of a memo group, by traversing the + * group's logical expression and its child groups. + */ + public static GroupStructInfo of(Group group) { + return of(group, LiteralMode.WITH_LITERAL); + } + + /** + * Compute the simplified struct info of a memo group in the given literal mode. + */ + public static GroupStructInfo of(Group group, LiteralMode mode) { + HboStructSummary summary = group.getOrComputeHboStructSummary(); + int maxScansPerGroup = hboMaxScansPerGroup(); + if (maxScansPerGroup > 0 && summary.getScanCount() > maxScansPerGroup) { + // The canonical string of a group describes its whole sub tree, and for a chain of joins + // it is built once per group of that chain, so a cheap structural summary is used as a + // gate: a sub tree with more scan tokens than hbo_max_scans_per_group is not described at + // all (the read side falls back to the optimizer estimation and EXPLAIN reports why). + return new GroupStructInfo(false, "", "", "", INVALID_SCANS, "subtree scans=" + + summary.getScanCount() + " > hbo_max_scans_per_group=" + maxScansPerGroup); + } + Ctx ctx = new Ctx(mode); + try { + Canonical out = new Canonical(); + visit(group, out, ctx); + if (!ctx.valid) { + return INVALID; + } + String canonicalString = out.annotated.toString(); + String shapeString = out.shape.toString(); + String fingerprint = Hashing.sha256() + .hashString(shapeString, StandardCharsets.UTF_8).toString(); + return new GroupStructInfo(true, canonicalString, shapeString, fingerprint, + new ArrayList<>(out.getScans())); + } catch (RuntimeException e) { + // memo content not supported by the simplified struct info: treat as invalid and + // fall back to legacy behavior instead of failing the optimizer on the hot path + LOG.debug("failed to compute hbo struct info for group {}", group.getGroupId(), e); + return ctx.retryable ? TRANSIENT_FAILURE : INVALID; + } + } + + /** + * Visit a group and append its canonical description to {@code sb}. + */ + private static void visit(Group group, Canonical out, Ctx ctx) { + if (!ctx.valid) { + return; + } + if (!ctx.visited.add(group)) { + // shared sub graph (e.g. CTE / repeated child group): cannot be expressed by a single + // canonical tree, mark invalid so that callers fall back to legacy behavior + invalid(ctx); + return; + } + // Use the first logical expression to know the kind of the group head. The canonical forms + // below are insensitive to which expression is picked, so this choice cannot change the + // fingerprint of the group (see the class comment). + GroupExpression ge = group.getFirstLogicalExpression(); + if (ge == null) { + invalid(ctx); + return; + } + appendPlan(ge.getPlan(), ge, out, ctx); + } + + private static void appendPlan(Plan plan, GroupExpression ge, Canonical out, Ctx ctx) { + if (!ctx.valid) { + return; + } + if (plan instanceof LogicalOlapScan) { + appendScan((LogicalOlapScan) plan, out, ctx); + } else if (plan instanceof LogicalFilter) { + LogicalFilter<?> filter = (LogicalFilter<?>) plan; + out.append("F{").append(normalizedSorted(filter.getConjuncts(), ctx.mode)).append("}("); + appendChild(ge, 0, out, ctx); + out.append(")"); + } else if (plan instanceof LogicalProject) { + // project is transparent for structure matching + if (ge.arity() == 1) { + appendChild(ge, 0, out, ctx); + } else { + invalid(ctx); + } + } else if (plan instanceof LogicalJoin) { + appendJoin((LogicalJoin<?, ?>) plan, ge, out, ctx); + } else if (plan instanceof LogicalAggregate) { + appendAggregate((LogicalAggregate<?>) plan, ge, out, ctx); + } else { + // unsupported head operator (sort/topn/limit/window/union/cte/tvf/...) + invalid(ctx); + } + } + + private static void appendJoin(LogicalJoin<?, ?> join, GroupExpression ge, Canonical out, Ctx ctx) { + if (isFlattenableJoinType(join.getJoinType())) { + appendJoinChain(join, ge, out, ctx); + return; + } + // Outer / semi / anti / asof joins: the two sides are semantically different and the join + // cannot be reassociated, so the memo order of the children and the join type are kept. + out.append("J{").append(join.getJoinType().toString()); Review Comment: 认可。mark 状态与 markJoinConjuncts 不在 canonical 里，而 JoinEstimation 对两者的行数处理不同。方案：把 mark 状态编码进 J{...} 头部（如 J{semi-mark,c:[...]}），同属 key 变更，建议与上面两条一起作为一次“key 语义收紧”提交。 ########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/GroupStructInfo.java: ########## @@ -0,0 +1,902 @@ +// 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.memo.Group; +import org.apache.doris.nereids.memo.GroupExpression; +import org.apache.doris.nereids.trees.expressions.And; +import org.apache.doris.nereids.trees.expressions.EqualTo; +import org.apache.doris.nereids.trees.expressions.Expression; +import org.apache.doris.nereids.trees.expressions.Or; +import org.apache.doris.nereids.trees.expressions.SlotReference; +import org.apache.doris.nereids.trees.expressions.literal.Literal; +import org.apache.doris.nereids.trees.plans.AbstractPlan; +import org.apache.doris.nereids.trees.plans.JoinType; +import org.apache.doris.nereids.trees.plans.Plan; +import org.apache.doris.nereids.trees.plans.logical.LogicalAggregate; +import org.apache.doris.nereids.trees.plans.logical.LogicalFilter; +import org.apache.doris.nereids.trees.plans.logical.LogicalJoin; +import org.apache.doris.nereids.trees.plans.logical.LogicalOlapScan; +import org.apache.doris.nereids.trees.plans.logical.LogicalProject; +import org.apache.doris.nereids.util.MutableState; +import org.apache.doris.qe.ConnectContext; + +import com.google.common.hash.Hashing; +import org.apache.logging.log4j.LogManager; +import org.apache.logging.log4j.Logger; + +import java.nio.charset.StandardCharsets; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.TreeSet; +import java.util.stream.Collectors; + +/** + * Simplified struct info of a memo {@link Group}, used by History Based Optimization (HBO). + * + * <p>The struct info is a property of the <b>group</b>, not of one of its group expressions: all + * expressions of a group are logically equivalent, so they describe the same set of relations with + * the same predicates, and the canonical form below is deliberately insensitive to which expression + * is picked. + * <ul> + * <li>join commutativity: children of a join are canonicalized by sorting;</li> + * <li>join associativity: a whole inner / cross join chain is emitted as one node + * ({@code J{inner,c:[...]}(...;...)}) whose children are the chain leaves sorted by their + * canonical form and whose conditions are the sorted union of every condition of the chain, + * so {@code (A join B) join C} and {@code A join (B join C)} produce the same descriptor;</li> + * <li>aggregation: only the group by keys and the child participate, because the output row count + * of an aggregation is the number of groups and cannot be changed by the aggregate functions + * or by the output expressions;</li> + * <li>project is transparent for structure matching.</li> + * </ul> + * This mirrors what the MV oriented {@code rules.exploration.mv.StructInfo} does (it identifies a + * sub tree by its relation set and by level independent - shuttled - predicates), with every MV + * specific field dropped: no hyper graph, no shuttle map, no equivalence class, no lineage. + * + * <p>What the canonical form keeps: + * <ul> + * <li>for each scan: the table qualifier and - as an annotation only - the data state of the scan + * (its visible version, the rows it reads and how many of the table partitions it selects, + * see {@link HboScanDescriptor});</li> + * <li>for filter / join / aggregate: the normalized predicates / join conditions / grouping keys, + * i.e. the structural pattern only (slot and expression ids are stripped by + * {@link #normalizeExpression}).</li> + * </ul> + * The string contains no per-query identifier, so it is reproducible across runs and queries for + * structurally identical sub trees, and its sha256 is used as the HBO cache key (fingerprint). + * + * <p>The sha256 is taken over the canonical string <b>without</b> the scan baselines + * ({@link #stripScanBaseline}): a hbo key identifies a plan pattern and the relation it reads, not a + * data state, so an entry whose table simply keeps growing stays matchable instead of silently never + * matching again. Whether an entry may still be applied is decided on the read side, by comparing + * the baseline of the entry with the data state of the current query (see + * {@link HboStructFreshness}). + * + * <p>The descriptor is derived from the group's logical expression and its child groups (memo level + * traversal, with a visited set to guard shared sub graphs such as CTE). Groups whose content is not + * supported (e.g. contains TVF / CTE consumer, or the head operator is not one of the supported + * kinds) are {@link #isValid() invalid} and callers must fall back to the legacy behavior. + */ +public class GroupStructInfo { + private static final List<HboScanDescriptor> INVALID_SCANS = Collections.emptyList(); + + /** Shared invalid instance: the group content is not supported by the simplified struct info. */ + public static final GroupStructInfo INVALID = new GroupStructInfo(false, "", "", "", INVALID_SCANS); + /** + * Shared instance for a failure which is not a property of the plan: the table state could not be + * read (e.g. the visible version of a cloud table could not be fetched). Unlike + * {@link #INVALID} it is not cached by the memo (see {@code Group#getOrComputeHboStructInfo}), so + * the next lookup of the same group retries instead of disabling hbo struct info for the whole + * query. + */ + public static final GroupStructInfo TRANSIENT_FAILURE = + new GroupStructInfo(false, "", "", "", INVALID_SCANS); + + private static final String SEP = ";"; + private static final Logger LOG = LogManager.getLogger(GroupStructInfo.class); + + /** + * Whether literal values participate in the canonical string / fingerprint. + * <ul> + * <li>{@link #WITH_LITERAL} keeps the literal value ({@code lit(10:int)}): the fingerprint is + * bound to the exact constants, used for filter roots where the constant changes the + * output row count;</li> + * <li>{@link #NO_LITERAL} replaces every literal value with {@code *} ({@code lit(*)}): the + * fingerprint is constant agnostic, used for join / aggregate roots and for the + * constant-free filter shape.</li> + * </ul> + * The literal data type is intentionally not kept: nereids inserts an explicit {@code Cast} + * for mismatching operand types, so two semantically different literal forms already differ by + * the cast node, while equivalent forms (e.g. {@code d > 1} and {@code d > 1.0} on a decimal + * column) are allowed to collapse. + */ + public enum LiteralMode { + WITH_LITERAL, + NO_LITERAL + } + + private final boolean valid; + private final String canonicalString; + /** The canonical string without the scan baselines: the fingerprint input. */ + private final String shapeString; + private final String fingerprint; + /** The scans of the sub tree, in the order their tokens appear in the canonical string. */ + private final List<HboScanDescriptor> scans; + /** Why no struct info was built, when it was refused by a limit instead of being unsupported. */ + private final String skipReason; + + private GroupStructInfo(boolean valid, String canonicalString, String shapeString, String fingerprint, + List<HboScanDescriptor> scans) { + this(valid, canonicalString, shapeString, fingerprint, scans, ""); + } + + private GroupStructInfo(boolean valid, String canonicalString, String shapeString, String fingerprint, + List<HboScanDescriptor> scans, String skipReason) { + this.valid = valid; + this.canonicalString = canonicalString; + this.shapeString = shapeString; + this.fingerprint = fingerprint; + this.scans = scans; + this.skipReason = skipReason; + } + + /** The reason the struct info was refused by a limit, or empty. Only for diagnostics. */ + public String getSkipReason() { + return skipReason; + } + + public boolean isValid() { + return valid; + } + + public String getCanonicalString() { + return canonicalString; + } + + /** + * The fingerprint input: the canonical string with the baseline of every scan token removed + * ({@code S{db.t}}). It is built from the traversal itself and not by parsing the canonical + * string, so no text inside a table name or a literal can be mistaken for a scan token. + */ + public String getShapeString() { + return shapeString; + } + + /** + * The row count and partition selection of every scan of the sub tree, in the order the scan + * tokens appear in the canonical string (i.e. the order a user sees when pasting the struct + * info). Empty when the struct info is invalid. + */ + public List<HboScanDescriptor> getScans() { + return scans; + } + + public String getFingerprint() { + return fingerprint; + } + + /** + * Resolve the fingerprint of the memo group that {@code planNode} belongs to, when the node + * still carries its {@link GroupExpression} back reference (memo inner plans, or plans from + * {@code chooseBestPlan}). Empty when the group content is unsupported (invalid struct info). + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode) { + return fingerprintOfPlanNode(planNode, LiteralMode.WITH_LITERAL); + } + + /** + * Resolve the group fingerprint of a plan node in the given literal mode. + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode, LiteralMode mode) { + return fingerprintOfGroup(planNode.getGroupExpression() + .map(GroupExpression::getOwnerGroup).orElse(null), mode); + } + + /** + * Resolve the fingerprint of the group that {@code planNode} belongs to, with a fallback to + * the {@link MutableState#KEY_GROUP} group-id state that post processors propagate to their + * rewritten copies (see {@code copyStatsAndGroupIdFrom}). {@code groupsById} maps memo group + * id to group, and is looked up only when the back reference is absent. + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode, Map<Integer, Group> groupsById) { + return fingerprintOfPlanNode(planNode, groupsById, LiteralMode.WITH_LITERAL); + } + + /** + * Resolve the group fingerprint of a plan node in the given literal mode, with the + * {@link MutableState#KEY_GROUP} fallback for post-processed copies. + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode, Map<Integer, Group> groupsById, + LiteralMode mode) { + return structInfoOfPlanNode(planNode, groupsById, mode).map(GroupStructInfo::getFingerprint); + } + + private static Optional<String> fingerprintOfGroup(Group group, LiteralMode mode) { + return structInfoOfGroup(group, mode).map(GroupStructInfo::getFingerprint); + } + + /** + * Resolve the {@link GroupStructInfo} (with canonical string and fingerprint) of the group a + * plan node belongs to, using the group-expression back reference or the KEY_GROUP group-id + * state propagated by post processors (see {@link #fingerprintOfPlanNode}). + */ + public static Optional<GroupStructInfo> structInfoOfPlanNode(AbstractPlan planNode, + Map<Integer, Group> groupsById) { + return structInfoOfPlanNode(planNode, groupsById, LiteralMode.WITH_LITERAL); + } + + /** + * Resolve the struct info of the group a plan node belongs to, in the given literal mode. + */ + public static Optional<GroupStructInfo> structInfoOfPlanNode(AbstractPlan planNode, + Map<Integer, Group> groupsById, LiteralMode mode) { + Group group = planNode.getGroupExpression().map(GroupExpression::getOwnerGroup).orElse(null); + if (group == null) { + Optional<Object> groupState = planNode.getMutableState(MutableState.KEY_GROUP); + if (groupState.isPresent() && groupsById != null) { + try { + group = groupsById.get(Integer.valueOf(groupState.get().toString())); + } catch (NumberFormatException ignored) { + group = null; + } + } + } + return structInfoOfGroup(group, mode); + } + + private static Optional<GroupStructInfo> structInfoOfGroup(Group group, LiteralMode mode) { + if (group == null) { + return Optional.empty(); + } + GroupStructInfo structInfo = group.getOrComputeHboStructInfo(mode); + return structInfo.isValid() ? Optional.of(structInfo) : Optional.empty(); + } + + /** + * The struct info of the group a plan node belongs to, computed now instead of being taken from + * the per-group cache. The fingerprint does not depend on any data state, so the cached struct + * info is the right source for a lookup; its <b>baseline</b> (the visible version and the row + * counts of its scans) is however a snapshot of the moment it was computed, which may be well + * before the query is planned. Whoever displays that baseline (EXPLAIN prints it as the + * {@code struct=} a user pastes into {@code HBO SET STATISTICS}) or compares it (the drift + * verdict) must therefore ask for it here, so that the whole query reports one data state. + */ + public static Optional<GroupStructInfo> dataStateOfPlanNode(AbstractPlan planNode, + Map<Integer, Group> groupsById, LiteralMode mode) { + Group group = planNode.getGroupExpression().map(GroupExpression::getOwnerGroup).orElse(null); + if (group == null) { + Optional<Object> groupState = planNode.getMutableState(MutableState.KEY_GROUP); + if (groupState.isPresent() && groupsById != null) { + try { + group = groupsById.get(Integer.valueOf(groupState.get().toString())); + } catch (NumberFormatException ignored) { + group = null; + } + } + } + if (group == null) { + return Optional.empty(); + } + GroupStructInfo structInfo = of(group, mode); + return structInfo.isValid() ? Optional.of(structInfo) : Optional.empty(); + } + + /** + * Compute the simplified struct info (and its fingerprint) of a memo group, by traversing the + * group's logical expression and its child groups. + */ + public static GroupStructInfo of(Group group) { + return of(group, LiteralMode.WITH_LITERAL); + } + + /** + * Compute the simplified struct info of a memo group in the given literal mode. + */ + public static GroupStructInfo of(Group group, LiteralMode mode) { + HboStructSummary summary = group.getOrComputeHboStructSummary(); + int maxScansPerGroup = hboMaxScansPerGroup(); + if (maxScansPerGroup > 0 && summary.getScanCount() > maxScansPerGroup) { + // The canonical string of a group describes its whole sub tree, and for a chain of joins + // it is built once per group of that chain, so a cheap structural summary is used as a + // gate: a sub tree with more scan tokens than hbo_max_scans_per_group is not described at + // all (the read side falls back to the optimizer estimation and EXPLAIN reports why). + return new GroupStructInfo(false, "", "", "", INVALID_SCANS, "subtree scans=" + + summary.getScanCount() + " > hbo_max_scans_per_group=" + maxScansPerGroup); + } + Ctx ctx = new Ctx(mode); + try { + Canonical out = new Canonical(); + visit(group, out, ctx); + if (!ctx.valid) { + return INVALID; + } + String canonicalString = out.annotated.toString(); + String shapeString = out.shape.toString(); + String fingerprint = Hashing.sha256() + .hashString(shapeString, StandardCharsets.UTF_8).toString(); + return new GroupStructInfo(true, canonicalString, shapeString, fingerprint, + new ArrayList<>(out.getScans())); + } catch (RuntimeException e) { + // memo content not supported by the simplified struct info: treat as invalid and + // fall back to legacy behavior instead of failing the optimizer on the hot path + LOG.debug("failed to compute hbo struct info for group {}", group.getGroupId(), e); + return ctx.retryable ? TRANSIENT_FAILURE : INVALID; + } + } + + /** + * Visit a group and append its canonical description to {@code sb}. + */ + private static void visit(Group group, Canonical out, Ctx ctx) { + if (!ctx.valid) { + return; + } + if (!ctx.visited.add(group)) { + // shared sub graph (e.g. CTE / repeated child group): cannot be expressed by a single + // canonical tree, mark invalid so that callers fall back to legacy behavior + invalid(ctx); + return; + } + // Use the first logical expression to know the kind of the group head. The canonical forms + // below are insensitive to which expression is picked, so this choice cannot change the + // fingerprint of the group (see the class comment). + GroupExpression ge = group.getFirstLogicalExpression(); + if (ge == null) { + invalid(ctx); + return; + } + appendPlan(ge.getPlan(), ge, out, ctx); + } + + private static void appendPlan(Plan plan, GroupExpression ge, Canonical out, Ctx ctx) { + if (!ctx.valid) { + return; + } + if (plan instanceof LogicalOlapScan) { + appendScan((LogicalOlapScan) plan, out, ctx); + } else if (plan instanceof LogicalFilter) { + LogicalFilter<?> filter = (LogicalFilter<?>) plan; + out.append("F{").append(normalizedSorted(filter.getConjuncts(), ctx.mode)).append("}("); + appendChild(ge, 0, out, ctx); + out.append(")"); + } else if (plan instanceof LogicalProject) { + // project is transparent for structure matching + if (ge.arity() == 1) { + appendChild(ge, 0, out, ctx); + } else { + invalid(ctx); + } + } else if (plan instanceof LogicalJoin) { + appendJoin((LogicalJoin<?, ?>) plan, ge, out, ctx); + } else if (plan instanceof LogicalAggregate) { + appendAggregate((LogicalAggregate<?>) plan, ge, out, ctx); + } else { + // unsupported head operator (sort/topn/limit/window/union/cte/tvf/...) + invalid(ctx); + } + } + + private static void appendJoin(LogicalJoin<?, ?> join, GroupExpression ge, Canonical out, Ctx ctx) { + if (isFlattenableJoinType(join.getJoinType())) { + appendJoinChain(join, ge, out, ctx); + return; + } + // Outer / semi / anti / asof joins: the two sides are semantically different and the join + // cannot be reassociated, so the memo order of the children and the join type are kept. + out.append("J{").append(join.getJoinType().toString()); + out.append(",c:[").append(normalizedJoinConditions(join, ctx.mode)).append("]}("); + appendChild(ge, 0, out, ctx); + out.append(SEP); + appendChild(ge, 1, out, ctx); + out.append(")"); + } + + /** + * Append the canonical form of a whole inner / cross join chain as a single node. + * + * <p>Inner and cross joins are associative and commutative, so the grouping of the chain is an + * artifact of the explored expression and must not be part of the fingerprint: the chain is + * emitted as {@code J{inner,c:[...]}(leaf;leaf;...)} with the conditions of every join of the + * chain merged into one sorted set and the leaves (scans, filters, aggregations, non + * flattenable joins) sorted by their canonical form. Every expression of a group therefore + * produces the same descriptor. Cross joins are merged with inner joins because a cross join is + * exactly an inner join without condition, and both have the same output row count. + */ + private static void appendJoinChain(LogicalJoin<?, ?> join, GroupExpression ge, Canonical out, Ctx ctx) { + TreeSet<String> conditions = new TreeSet<>(); + List<Leaf> leaves = new ArrayList<>(); + collectJoinConditions(join, conditions, ctx.mode); + for (int i = 0; i < ge.arity(); i++) { + collectJoinChain(ge.child(i), conditions, leaves, ctx); + } + if (!ctx.valid) { + return; + } + // the leaves are ordered by their fingerprint input (their own shape, i.e. without the data + // state of their scans): the order is part of the fingerprint, so it must not depend on a + // data state which the fingerprint deliberately ignores + leaves.sort(Comparator.comparing(Leaf::getShape)); + out.append("J{inner,c:[").append(String.join(SEP, conditions)).append("]}("); + for (int i = 0; i < leaves.size(); i++) { + if (i > 0) { + out.append(SEP); + } + out.append(leaves.get(i).getCanonical()); + } + out.append(")"); + } + + /** + * Collect one member of an inner / cross join chain: either descend into another join of the + * chain (associativity), or append the canonical form of the whole sub tree as one chain leaf. + * The group of {@code ge} is already marked visited by the caller. + */ + private static void collectJoinChain(Group group, TreeSet<String> conditions, List<Leaf> leaves, Ctx ctx) { + if (!ctx.valid) { + return; + } + if (!ctx.visited.add(group)) { + invalid(ctx); + return; + } + GroupExpression ge = group.getFirstLogicalExpression(); + if (ge == null) { + invalid(ctx); + return; + } + Plan plan = ge.getPlan(); + if (plan instanceof LogicalJoin && isFlattenableJoinType(((LogicalJoin<?, ?>) plan).getJoinType())) { + collectJoinConditions((LogicalJoin<?, ?>) plan, conditions, ctx.mode); + for (int i = 0; i < ge.arity(); i++) { + collectJoinChain(ge.child(i), conditions, leaves, ctx); + } + return; + } + if (plan instanceof LogicalProject && ge.arity() == 1) { + // keep descending through projects so that a project between two joins cannot break the + // chain in one expression and not in another + collectJoinChain(ge.child(0), conditions, leaves, ctx); + return; + } + Canonical leaf = new Canonical(); + appendPlan(plan, ge, leaf, ctx); + if (ctx.valid) { + leaves.add(new Leaf(leaf)); + } + } + + /** One leaf of a flattened join chain: both of its canonical forms and its scans. */ + private static class Leaf { + private final Canonical canonical; + + Leaf(Canonical canonical) { + this.canonical = canonical; + } + + Canonical getCanonical() { + return canonical; + } + + String getShape() { + return canonical.shape.toString(); + } + } + + /** Inner and cross joins may be reordered, reassociated and therefore flattened. */ + private static boolean isFlattenableJoinType(JoinType joinType) { + return joinType == JoinType.INNER_JOIN || joinType == JoinType.CROSS_JOIN; + } + + private static void appendAggregate(LogicalAggregate<?> agg, GroupExpression ge, Canonical out, Ctx ctx) { + // Only the grouping keys and the child take part: the output row count of an aggregation is + // the number of groups, which the aggregate functions and the output expressions cannot + // change, so keeping them would only split one plan pattern into several cache entries. + out.append("A{gb:").append(normalizedSorted(agg.getGroupByExpressions(), ctx.mode)); + out.append("}("); + appendChild(ge, 0, out, ctx); + out.append(")"); + } + + private static void invalid(Ctx ctx) { + ctx.valid = false; + } + + /** Mark the struct info invalid because the table state could not be read (retryable). */ + private static void transientFailure(Ctx ctx) { + ctx.valid = false; + ctx.retryable = true; + } + + private static void appendScan(LogicalOlapScan scan, Canonical out, Ctx ctx) { + try { + // the scan token is the table plus the data state of the scan (baseline). Its shape form + // is the table alone and is written by this very call, so the fingerprint input is never + // derived by parsing the canonical string: no table name and no literal value can be + // mistaken for a scan token. + HboScanDescriptor descriptor = HboScanDescriptor.of(scan); Review Comment: 认可，且这条比成本问题严重：TABLESAMPLE 不在 HboScanDescriptor 里，采样扫描与全表扫描同 key 同 baseline。建议最安全的修法：带 TABLESAMPLE 的 scan 直接让 struct info INVALID（不引入新 key 字段），我补提交。 ########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/HboScanDescriptor.java: ########## @@ -0,0 +1,342 @@ +// 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.catalog.Env; +import org.apache.doris.catalog.OlapTable; +import org.apache.doris.nereids.trees.plans.algebra.OlapScan; +import org.apache.doris.rpc.RpcException; +import org.apache.doris.statistics.analysis.TableStatsMeta; + +import java.util.ArrayList; +import java.util.List; + +/** + * The data state of one scan of a hbo struct info: the table it reads, the table visible version, + * the number of rows the scan reads (the sum of the row counts of its selected partitions) and which + * part of the table partitions it selects. + * + * <p>These numbers are the <b>baseline</b> a hbo entry is judged against. The scan token of a + * canonical struct info carries them as an annotation + * ({@code S{db.t,v3,r1000,p1/5}}), so a user copies the state the entry was measured in together + * with the struct info, and the read side compares them with the state of the current query to + * decide whether the injected row count may still be applied (see {@link HboStructFreshness}). + * + * <p>None of these numbers takes part in the fingerprint: + * {@link GroupStructInfo#stripScanBaseline} removes the whole baseline of every scan token before + * the sha256 is taken, so a table which simply keeps growing neither changes the key of an entry nor + * makes it unmatchable; whether the entry may still be applied is a read side decision. + * + * <p>A number which could not be determined is omitted from the token (and parsed back as + * {@link #UNKNOWN}), e.g. the row count of a table whose row count was never reported by any + * backend: such an entry cannot be compared by rows any more and falls back to the version check. + */ +public class HboScanDescriptor { + /** A number which could not be determined; a row count of 0 is a known, meaningful value. */ + public static final long UNKNOWN = -1; + + private final String table; + private final long visibleVersion; + private final long scanRows; + private final RowsKind rowsKind; + private final long selectedPartitions; + private final long totalPartitions; + + HboScanDescriptor(String table, long visibleVersion, long scanRows, RowsKind rowsKind, + long selectedPartitions, long totalPartitions) { + this.table = table; + this.visibleVersion = visibleVersion; + this.scanRows = scanRows; + this.rowsKind = rowsKind; + this.selectedPartitions = selectedPartitions; + this.totalPartitions = totalPartitions; + } + + /** + * How the row count of a scan was obtained. + */ + public enum RowsKind { + /** + * Every selected partition reported its own row count, so the number is the physical size of + * the data the scan reads. + */ + MEASURED, + /** + * The row count of at least one selected partition is not available, so the number is + * derived from the table (its last reported row count, or the statistics of the last + * analysis plus the rows loaded since). Two such numbers are comparable with each other, but + * a number of this kind must never be compared with a {@link #MEASURED} one: the derivation + * can be off by a large factor, e.g. for the partitions of a skewed table. + */ + ESTIMATED, + /** No row count at all (the table was neither analyzed nor reported by a backend). */ + UNKNOWN + } + + /** A row count and how it was obtained. */ + public static class Rows { + private static final Rows UNKNOWN_ROWS = new Rows(UNKNOWN, RowsKind.UNKNOWN); + + private final long rows; + private final RowsKind kind; + + Rows(long rows, RowsKind kind) { + this.rows = rows; + this.kind = kind; + } + + public long getRows() { + return rows; + } + + public RowsKind getKind() { + return kind; + } + + public boolean isKnown() { + return kind != RowsKind.UNKNOWN; + } + } + + /** The state of a scan node: which table it reads, and how much of it. */ + public static HboScanDescriptor of(OlapScan scan) throws RpcException { + OlapTable table = scan.getTable(); + List<Long> selectedPartitionIds = scan.getSelectedPartitionIds(); + Rows rows = rowsOf(table, selectedPartitionIds, scan.getSelectedIndexId()); + return new HboScanDescriptor(table.getNameWithFullQualifiers(), table.getVisibleVersion(), Review Comment: 认可。token 里的 p<选中>/<总数> 只在裁剪时打印，不表达选了哪些分区，所以 PARTITION p1 与 p2 同 key；自连接同 shape 叶子交换后 baseline 也可能错位。方案：把分区选择的稳定摘要放进 shape，并用它给重复叶子配对。属于 key 变更，建议与上面的 key 收紧一起做。 ########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/HboPlanInfoProvider.java: ########## @@ -147,35 +284,62 @@ public void handle(Field field, String confVal) throws Exception { } /** - * Reference the above UpdateConfig comments. + * Reference the above UpdateConfig comments. Every per-query cache of this provider is rebuilt + * (they are all sized and expired by the same two configs), and the entries of a running query + * are carried over so that a runtime change cannot drop the plan info of a query which is still + * in flight. */ public static synchronized void updateConfig() { HboPlanStatisticsManager hboManger = Env.getCurrentEnv().getHboPlanStatisticsManager(); if (hboManger == null) { return; } - HboPlanInfoProvider planInfoProvider = hboManger.getHboPlanInfoProvider(); - if (planInfoProvider == null) { + HboPlanInfoProvider provider = hboManger.getHboPlanInfoProvider(); + if (provider == null) { return; } + int cacheNum = Config.hbo_plan_info_cache_num; + int pinnedCacheNum = Config.hbo_pinned_stats_cache_num; + long expireSeconds = Config.expire_hbo_plan_info_cache_in_fe_second; - Cache<String, Map<Integer, PhysicalPlan>> idToPlanCache = buildHboIdToPlanCache( - Config.hbo_plan_info_cache_num, - Config.expire_hbo_plan_info_cache_in_fe_second - ); - Cache<String, Map<PhysicalPlan, Integer>> planToIdCache = buildHboPlanToIdCache( - Config.hbo_plan_info_cache_num, - Config.expire_hbo_plan_info_cache_in_fe_second - ); - Cache<String, Map<RelationId, Set<Expression>>> scanToFilterCache = buildHboScanToFilterCache( - Config.hbo_plan_info_cache_num, - Config.expire_hbo_plan_info_cache_in_fe_second - ); - idToPlanCache.putAll(planInfoProvider.idToPlanCache.asMap()); - planInfoProvider.idToPlanCache = idToPlanCache; - planToIdCache.putAll(planInfoProvider.planToIdCache.asMap()); - planInfoProvider.planToIdCache = planToIdCache; - scanToFilterCache.putAll(planInfoProvider.scanToFilterCache.asMap()); - planInfoProvider.scanToFilterCache = scanToFilterCache; + Cache<String, Map<Integer, PhysicalPlan>> idToPlanCache = + buildHboIdToPlanCache(cacheNum, expireSeconds); + idToPlanCache.putAll(provider.idToPlanCache.asMap()); + provider.idToPlanCache = idToPlanCache; + + Cache<String, Map<PhysicalPlan, Integer>> planToIdCache = + buildHboPlanToIdCache(cacheNum, expireSeconds); + planToIdCache.putAll(provider.planToIdCache.asMap()); + provider.planToIdCache = planToIdCache; + + Cache<String, Map<RelationId, Set<Expression>>> scanToFilterCache = + buildHboScanToFilterCache(cacheNum, expireSeconds); + scanToFilterCache.putAll(provider.scanToFilterCache.asMap()); + provider.scanToFilterCache = scanToFilterCache; + + Cache<String, Map<Integer, String>> nodeIdToFingerprintCache = + buildHboNodeIdToFingerprintCache(cacheNum, expireSeconds); + nodeIdToFingerprintCache.putAll(provider.nodeIdToFingerprintCache.asMap()); + provider.nodeIdToFingerprintCache = nodeIdToFingerprintCache; Review Comment: 认可，这是既有问题（非本 PR 引入）：updateConfig 复制旧 map 再换 volatile 引用的间隙里，collectHboPlanInfo 可能把新查询写进旧 map。修法：per-query map 放进不可变 holder，或让 swap 与写端共用一把锁。改动不大，我补提交。 -- 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]
