englefly commented on code in PR #67549:
URL: https://github.com/apache/doris/pull/67549#discussion_r4244252580
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/NereidsPlanner.java:
##########
@@ -635,10 +671,124 @@ private void collectHboPlanInfo(String queryId,
PhysicalPlan root, PlanTranslato
.getHboPlanInfoProvider().putPlanToIdMap(queryId,
planToIdMap);
}
planToIdMap.put(root, planId.asInt());
+ // snapshot the hbo fingerprint (simplified group struct info)
per plan node id;
+ // consumed by the profile publish path after the memo has
been released
+ // publish keys are constant agnostic: join / aggregation
fingerprints never
+ // carry literals, and scan tokens contain none by construction
+ Optional<String> fingerprint =
GroupStructInfo.fingerprintOfPlanNode(
+ (AbstractPlan) root, groupsById,
GroupStructInfo.LiteralMode.NO_LITERAL);
+ HboPlanInfoProvider planInfoProvider = Env.getCurrentEnv()
+
.getHboPlanStatisticsManager().getHboPlanInfoProvider();
+ Map<Integer, String> nodeFingerprints = planInfoProvider
+ .getNodeIdToFingerprintMap(queryId);
+ if (nodeFingerprints.isEmpty()) {
+ planInfoProvider.putNodeIdToFingerprintMap(queryId,
nodeFingerprints);
+ }
+ // keyed by the real PlanNodeId (the same id used by the
profile publish
+ // path via runtime stats item.node_id), not by the nereids
plan id. A null value
+ // marks a node which is deliberately excluded from the hbo
fingerprint (an
+ // unsupported group such as sort / topn), so that the publish
path does not warn
+ // about a fingerprint which was never meant to exist
+ nodeFingerprints.put(planId.asInt(), fingerprint.orElse(null));
Review Comment:
认可，已修复（0cbdc52d362）：ConcurrentHashMap 不接受 null，改为使用哨兵
GroupStructInfo.UNSUPPORTED_FINGERPRINT（空串，不可能是 sha256）；HboUtils 遇到哨兵直接跳过、不计入
missingFingerprints，因此被有意排除的节点不会告警，真正丢失的快照仍会告警。
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/GroupStructInfo.java:
##########
@@ -0,0 +1,910 @@
+// 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 {
+ /**
+ * The default of {@code hbo_max_scans_per_group}, used when no session is
available. 20 keeps
+ * every TPC-DS shape observed in this repository (the largest single sub
tree is query64's
+ * 19 scan join group) while refusing trees which are pathologically wide.
+ */
+ public static final int DEFAULT_MAX_SCANS_PER_GROUP = 20;
+ 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) {
+ if (group.getLogicalExpressions().isEmpty()) {
+ // physical only group: nothing to describe (see summaryOf)
+ return INVALID;
+ }
+ 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) {
+ // a failure which came from reading the catalog (e.g. a cloud
rpc error) may survive
+ // a later attempt: INVALID would be cached by the memo group
and disable hbo for the
+ // whole query, TRANSIENT_FAILURE is retried instead
+ return ctx.retryable ? TRANSIENT_FAILURE : 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() +
")";
Review Comment:
认可，已修复（0cbdc52d362）：字面量值不再原样写入 canonical，改为对会构成结构的字符（\\ % ( ) { } [ ] , ; :
|）做百分号编码，编码对不含这些字符的值是恒等变换。这样 lit(...) 内部不可能闭合自身或伪造后续 conjunct，两个不同谓词不会再共享
fingerprint；EXPLAIN/SHOW 展示时由 decodeLiteralValue 还原原值。
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/SimpleStructInfo.java:
##########
@@ -0,0 +1,339 @@
+// 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 com.google.common.collect.ImmutableMap;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Human readable (simplified) rendering of a hbo struct info canonical string.
+ *
+ * <p>The canonical string is the fingerprint input and stays the
authoritative description; the
+ * simplified string is only meant to help a user locate an entry, so it drops
everything that
+ * cannot be told apart at a glance and keeps the shape:
+ * <ul>
+ * <li>scan: {@code S{internal.hbo_test.t,v2,r1000}} becomes {@code
S{hbo_test.t}} - the catalog
+ * is dropped (except for non internal catalogs, which are kept because
they identify the
+ * table), the data state of the scan is dropped (the visible version
and the scanned rows,
+ * which only annotate the entry and never take part in its
fingerprint), the pruned partition
+ * count is kept ({@code ,p1/2}) and a {@code #k} suffix is added only
when the same table
+ * appears more than once in the struct;</li>
+ * <li>filter: predicates are written with operator symbols ({@code
col(internal.hbo_test.x.b) =
+ * lit(1:INT)} becomes {@code x.b = 1}), {@code ;} means AND, {@code |}
means OR, literals are
+ * written as their value (or as {@code *} for the constant agnostic
granularity), and a
+ * column keeps its qualifier only when it is needed to tell two
occurrences apart;</li>
+ * <li>join: only the list of the chain leaves is kept, join type and join
conditions are dropped
+ * ({@code J{S{hbo_test.t1}, S{hbo_test.t2}, S{hbo_test.t3}}}), because
the chain is already
+ * flattened and the remaining differences are visible in the canonical
form;</li>
+ * <li>aggregation: only the grouping keys and the child are kept, the
aggregate functions and the
+ * output expressions are dropped (they cannot change the output row
count).</li>
+ * </ul>
+ * Two entries may therefore share one simplified string while having
different canonical strings;
+ * {@code HBO SHOW STATISTICS FULL} prints the canonical form to tell them
apart.
+ *
+ * <p>Because the simplified form is a pure function of the canonical string,
it never needs to be
+ * persisted: it is derived on demand, so it can never go stale.
+ */
+public final class SimpleStructInfo {
+ private static final Map<String, String> BINARY_OPERATORS =
ImmutableMap.<String, String>builder()
+ .put("EqualTo", "=")
+ .put("NotEqualTo", "!=")
+ .put("LessThan", "<")
+ .put("LessThanEqual", "<=")
+ .put("GreaterThan", ">")
+ .put("GreaterThanEqual", ">=")
+ .put("NullSafeEqual", "<=>")
+ .build();
+ private static final String CATALOG_NAME = "internal";
+ private static final char AND = ';';
+ private static final String OR = "|";
+
+ private final String canonical;
+ private final Set<String> tableNames = new HashSet<>();
+ private final Map<String, Integer> scanTokenCount = new LinkedHashMap<>();
+ private final Map<String, Integer> scanTokenSeen = new HashMap<>();
+ private int pos;
+
+ private SimpleStructInfo(String canonical) {
+ this.canonical = canonical;
+ }
+
+ /**
+ * Render the simplified form of a canonical struct info string. Text
which is not a canonical
+ * struct info (a row of the internal table written by an older version,
or a hand written
+ * literal) is returned unchanged instead of printing something misleading.
+ */
+ public static String render(String canonical) {
+ if (canonical == null || canonical.isEmpty()) {
+ return "";
+ }
+ SimpleStructInfo renderer = new SimpleStructInfo(canonical);
+ renderer.collectScans();
+ try {
+ String simple = renderer.renderNode(null);
+ return renderer.pos == canonical.length() ? simple : canonical;
+ } catch (RuntimeException e) {
+ return canonical;
+ }
+ }
+
+ private void collectScans() {
+ int index = 0;
+ while ((index = HboScanDescriptor.nextScanTokenStart(canonical,
index)) >= 0) {
+ int end = canonical.indexOf('}', index);
+ if (end < 0) {
+ return;
+ }
+ String header = canonical.substring(index + 2, end);
+ String token = scanToken(header);
+ scanTokenCount.merge(token, 1, Integer::sum);
+ tableNames.add(tableName(header));
+ index = end;
+ }
+ }
+
+ //
------------------------------------------------------------------------------------------
+ // node rendering
+ //
------------------------------------------------------------------------------------------
+
+ /**
+ * Render one node, starting at {@link #pos}.
+ *
+ * @param parent the logical operator of the enclosing node ({@code null}
when top level), used
+ * to decide whether a nested AND / OR needs parentheses
+ */
+ private String renderNode(String parent) {
+ char kind = canonical.charAt(pos++);
+ String header = readBraced();
+ if (kind == 'S') {
+ return renderScan(header);
+ }
+ expect('(');
+ if (kind == 'J') {
+ List<String> children = new ArrayList<>();
+ children.add(renderNode(parent));
+ while (canonical.charAt(pos) == AND) {
+ pos++;
+ children.add(renderNode(parent));
+ }
+ expect(')');
+ // join type and join conditions are dropped: the leaves and the
canonical form carry
+ // the differences a user has to tell apart
+ return "J{" + String.join(", ", children) + "}";
+ }
+ String child = renderNode(parent);
+ expect(')');
+ if (kind == 'F') {
+ return "F{" + renderPredicates(header, parent) + "}(" + child +
")";
+ }
+ if (kind == 'A') {
+ // gb:<group by keys>
+ int colon = header.indexOf(':');
+ String groupBy = colon < 0 ? header : header.substring(colon + 1);
+ return "A{" + renderPredicates(groupBy, parent) + "}(" + child +
")";
+ }
+ throw new IllegalStateException("unknown hbo struct info node: " +
kind);
+ }
+
+ private String renderScan(String header) {
+ String token = scanToken(header);
+ String[] parts = header.split(",");
+ StringBuilder sb = new
StringBuilder("S{").append(simplifiedTableName(parts[0]));
+ Integer count = scanTokenCount.get(token);
+ if (count != null && count > 1) {
+ sb.append('#').append(scanTokenSeen.merge(token, 1, Integer::sum)
- 1);
+ }
+ for (int i = 1; i < parts.length; i++) {
+ // keep the pruned partition count, drop the visible version
+ if (parts[i].startsWith("p")) {
+ sb.append(',').append(parts[i]);
+ }
+ }
+ return sb.append('}').toString();
+ }
+
+ //
------------------------------------------------------------------------------------------
+ // expression rendering
+ //
------------------------------------------------------------------------------------------
+
+ private String renderPredicates(String expressions, String parent) {
+ List<String> rendered = new ArrayList<>();
+ for (String conjunct : splitTopLevel(expressions, AND)) {
+ if (!conjunct.trim().isEmpty()) {
+ rendered.add(renderExpression(conjunct, parent));
+ }
+ }
+ return String.join("; ", rendered);
+ }
+
+ /**
+ * Render one canonical expression ({@code ClassName(children)}, {@code
col(qualifier.name)} or
+ * {@code lit(value:type)}) with operator symbols.
+ */
+ private String renderExpression(String expression, String parent) {
+ String text = expression.trim();
+ if (text.startsWith("col(") && text.endsWith(")")) {
+ return renderColumn(text.substring(4, text.length() - 1));
+ }
+ if (text.startsWith("lit(") && text.endsWith(")")) {
+ return renderLiteral(text.substring(4, text.length() - 1));
+ }
+ int open = text.indexOf('(');
+ if (open < 0) {
+ return text;
+ }
+ String name = text.substring(0, open);
+ // only nested AND / OR groups need parentheses, comparisons never do;
the operands of any
+ // other expression are rendered without a logical context
+ String childParent = "And".equals(name) ? "and" : "Or".equals(name) ?
"or" : null;
+ List<String> arguments = new ArrayList<>();
+ for (String argument : splitTopLevel(text.substring(open + 1,
text.length() - 1), ',')) {
+ arguments.add(renderExpression(argument, childParent));
+ }
+ String operator = BINARY_OPERATORS.get(name);
+ if (operator != null && arguments.size() == 2) {
+ return arguments.get(0) + " " + operator + " " + arguments.get(1);
+ }
+ if ("And".equals(name)) {
+ String joined = String.join("; ", arguments);
+ return "or".equals(parent) ? "(" + joined + ")" : joined;
+ }
+ if ("Or".equals(name)) {
+ String joined = String.join(" " + OR + " ", arguments);
+ return "and".equals(parent) ? "(" + joined + ")" : joined;
+ }
+ if ("Not".equals(name) && arguments.size() == 1) {
+ return "!(" + arguments.get(0) + ")";
+ }
+ return name + "(" + String.join(", ", arguments) + ")";
+ }
+
+ /**
+ * A column keeps its qualifier unless the struct describes a single table
and the qualifier is
+ * that table: a single table struct is already identified by its scan
token, while an alias (or
+ * a second table) is needed to tell two occurrences apart.
+ */
+ private String renderColumn(String qualifiedName) {
+ int lastDot = qualifiedName.lastIndexOf('.');
+ if (lastDot < 0) {
+ return qualifiedName;
+ }
+ String qualifier = qualifiedName.substring(0, lastDot);
+ String column = qualifiedName.substring(lastDot + 1);
+ int qualifierDot = qualifier.lastIndexOf('.');
+ String owner = qualifierDot < 0 ? qualifier :
qualifier.substring(qualifierDot + 1);
+ if (tableNames.size() == 1 && tableNames.contains(owner)) {
+ return column;
+ }
+ return owner + "." + column;
+ }
+
+ private String renderLiteral(String literal) {
+ // lit(*) for the constant agnostic granularity, lit(value:type)
otherwise: the type is
+ // dropped, the value is kept
+ int lastColon = literal.lastIndexOf(':');
+ return lastColon < 0 ? literal : literal.substring(0, lastColon);
+ }
+
+ //
------------------------------------------------------------------------------------------
+ // string helpers
+ //
------------------------------------------------------------------------------------------
+
+ /** Read the content of the bracketed group which starts at {@link #pos},
advancing past it. */
+ private String readBraced() {
+ char open = canonical.charAt(pos);
+ char close = open == '{' ? '}' : ')';
+ expect(open);
+ // the opening bracket is already consumed but it is still open
+ int depth = 1;
+ int start = pos;
+ while (pos < canonical.length()) {
+ char c = canonical.charAt(pos);
+ if (c == open || c == '(' || c == '[') {
+ depth++;
+ } else if (c == close || c == ')' || c == ']') {
Review Comment:
认可，已修复（0cbdc52d362）：与上一条同源。字面量编码后 readBraced 的括号计数不会再被值里的 ) 提前闭合，render
也不再退化成完整 canonical；renderLiteral 展示前会解码。
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/GroupStructInfo.java:
##########
@@ -0,0 +1,910 @@
+// 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 {
+ /**
+ * The default of {@code hbo_max_scans_per_group}, used when no session is
available. 20 keeps
+ * every TPC-DS shape observed in this repository (the largest single sub
tree is query64's
+ * 19 scan join group) while refusing trees which are pathologically wide.
+ */
+ public static final int DEFAULT_MAX_SCANS_PER_GROUP = 20;
+ 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) {
+ if (group.getLogicalExpressions().isEmpty()) {
+ // physical only group: nothing to describe (see summaryOf)
+ return INVALID;
+ }
+ 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) {
+ // a failure which came from reading the catalog (e.g. a cloud
rpc error) may survive
+ // a later attempt: INVALID would be cached by the memo group
and disable hbo for the
+ // whole query, TRANSIENT_FAILURE is retried instead
+ return ctx.retryable ? TRANSIENT_FAILURE : 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 +
")";
+ }
+ }
+
+ /** Equal-to, boolean and/or are commutative; everything else keeps its
operand order. */
+ private static boolean isOrderInsensitive(Expression expression) {
+ return expression instanceof EqualTo
Review Comment:
认可，已修复（0cbdc52d362）：isOrderInsensitive 现在包含 NullSafeEqual，作用于
EqualTo/Or/And，因此 t.a <=> u.a 与 u.a <=> t.a 折叠为同一 canonical，左右交换 join 侧不再产生不同
fingerprint。
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/HboJoinConditions.java:
##########
@@ -0,0 +1,87 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.stats;
+
+import org.apache.doris.nereids.trees.expressions.EqualTo;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.NullSafeEqual;
+import org.apache.doris.nereids.trees.plans.JoinType;
+import org.apache.doris.nereids.trees.plans.algebra.Join;
+
+import com.google.common.hash.Hashing;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Optional;
+
+/**
+ * Canonical description and fingerprint of the equality conditions of a join,
used as the key of
+ * manually injected join expansion entries ({@code HBO SET EXPANSION}).
+ *
+ * <p>Only the hash (equality) conjuncts participate: the expansion behaviour
of a join is a
+ * property of the joined column pairs, so the key deliberately excludes the
join type, the shape
+ * of both sub trees and every non equality condition. That makes one injected
entry reusable by
+ * every query joining the same columns.
+ *
+ * <p>The canonical form is {@code JE{EqualTo(...);EqualTo(...)}} with the
pairs sorted; a pair is
+ * rendered by {@link GroupStructInfo#normalizeExpression(Expression)} which
already sorts the two
+ * operands of an equality (equality is commutative), so {@code a = b} and
{@code b = a} collapse.
+ */
+public class HboJoinConditions {
+ private static final String PREFIX = "JE{";
+ private static final String SEP = ";";
+
+ private HboJoinConditions() {
+ }
+
+ /** True when the injected expansion of this join type is applicable at
all. */
+ public static boolean isExpansionApplicable(JoinType joinType) {
+ // semi / anti / mark style joins can never produce more rows than
their left input, and
+ // asof joins match at most one row per left row, so expansion can not
happen there
+ return joinType == JoinType.INNER_JOIN
+ || joinType == JoinType.LEFT_OUTER_JOIN
+ || joinType == JoinType.RIGHT_OUTER_JOIN
+ || joinType == JoinType.FULL_OUTER_JOIN;
+ }
+
+ /**
+ * Canonical string of the equality conditions, empty when the join has no
equality condition
+ * (e.g. a cross join). A null safe equality ({@code <=>}) is a hash
conjunct as well, so it
+ * takes part in the canonical like a plain equality.
+ */
+ public static Optional<String> canonicalOf(Join join) {
+ List<String> pairs = new ArrayList<>();
+ for (Expression conjunct : join.getHashJoinConjuncts()) {
Review Comment:
认可，已修复（0cbdc52d362）：JE key 现在为 JE{<join type>;hash conditions...;residual
conditions...}，残留（非等值）条件以常量无关形式参与并按序排序，因此 INNER 无匹配与 LEFT OUTER 不再共用同一因子；两个子树的
shape 仍然排除，同一 join type + 同一条件的查询依旧共享条目。相应更新了 hbo_join_expansion_inject_test /
hbo_persist_internal_db_test 及其期望输出。
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/parser/LogicalPlanBuilder.java:
##########
@@ -7182,6 +7185,147 @@ public LogicalPlan
visitAdminSetFrontendConfig(DorisParser.AdminSetFrontendConfi
applyToAll);
}
+ @Override
+ public LogicalPlan
visitHboSetStatistics(DorisParser.HboSetStatisticsContext ctx) {
+ checkHboStatementWords(ctx.hbo, ctx.statistics);
+ Double value = null;
+ String typeName = null;
+ String fingerprint = null;
+ String structCanonical = null;
+ String literalModeName = null;
+ for (DorisParser.HboSetParamContext param : ctx.hboSetParam()) {
+ if (param instanceof DorisParser.HboSetValueContext) {
+ if (value != null) {
+ throw new ParseException("VALUE is given twice in hbo set
statistics statement");
+ }
+ try {
+ value =
Double.parseDouble(((DorisParser.HboSetValueContext) param).value.getText());
+ } catch (NumberFormatException e) {
+ throw new ParseException("hbo statistics VALUE out of
range: "
+ + ((DorisParser.HboSetValueContext)
param).value.getText());
+ }
+ } else if (param instanceof DorisParser.HboSetTypeContext) {
+ if (typeName != null) {
+ throw new ParseException("TYPE is given twice in hbo set
statistics statement");
+ }
+ typeName = ((DorisParser.HboSetTypeContext)
param).typeName.getText();
+ } else if (param instanceof DorisParser.HboSetStructContext) {
+ if (structCanonical != null) {
+ throw new ParseException("STRUCT is given twice in hbo set
statistics statement");
+ }
+ structCanonical = SqlLiteralUtils.parseStringLiteral(
+ ((DorisParser.HboSetStructContext)
param).structCanonical.getText());
+ } else if (param instanceof DorisParser.HboSetFingerprintContext) {
+ DorisParser.HboSetFingerprintContext fingerprintParam =
+ (DorisParser.HboSetFingerprintContext) param;
+ if (!isHboWord(fingerprintParam.fingerprintWord,
"FINGERPRINT")) {
+ throw
unknownHboParameter(fingerprintParam.fingerprintWord);
+ }
+ if (fingerprint != null) {
+ throw new ParseException("FINGERPRINT is given twice in
hbo set statistics statement");
+ }
+ fingerprint =
stripQuotes(fingerprintParam.fingerprint.getText());
+ } else if (param instanceof DorisParser.HboSetWordContext) {
+ DorisParser.HboSetWordContext wordParam =
(DorisParser.HboSetWordContext) param;
+ if (isHboWord(wordParam.valueWord, "FINGERPRINT")) {
+ // a bare FINGERPRINT value can not be lexed reliably (a
hex fingerprint may start
+ // with a digit), so it has to be quoted
+ throw new ParseException("the FINGERPRINT value must be
quoted: FINGERPRINT='<64 hex>'");
+ }
+ if (!isHboWord(wordParam.valueWord, "LITERAL_MODE")) {
+ // this alternative is also matched by an unknown
parameter whose value happens to
+ // be an identifier (LITERAL_MODE=NO_LITERAL is the only
one that takes one), so
+ // report the parameter name instead of claiming
LITERAL_MODE was expected
+ throw unknownHboParameter(wordParam.valueWord);
+ }
+ if (literalModeName != null) {
+ throw new ParseException("LITERAL_MODE is given twice in
hbo set statistics statement");
+ }
+ literalModeName = wordParam.valueName.getText();
+ } else if (param instanceof DorisParser.HboSetUnknownContext) {
+ throw unknownHboParameter(((DorisParser.HboSetUnknownContext)
param).unknownWord);
+ }
+ }
+ if (value == null) {
+ throw new ParseException("expect 'VALUE=<number>' in hbo set
statistics statement");
+ }
+ if (fingerprint == null) {
+ throw new ParseException("expect \"FINGERPRINT='<fingerprint>'\"
in hbo set statistics statement");
+ }
+ return new HboStatisticsCommand(HboStatisticsCommand.Op.SET,
+ ctx.scope == null ? null : ctx.scope.getText(),
+ fingerprint,
+ value,
+ typeName,
+ structCanonical == null ? "" : structCanonical,
+ literalModeName);
+ }
+
+ @Override
+ public LogicalPlan
visitHboDeleteStaleStatistics(DorisParser.HboDeleteStaleStatisticsContext ctx) {
+ checkHboStatementWords(ctx.hbo, ctx.statistics);
+ checkHboWord(ctx.staleWord, "STALE");
+ Long olderThanSeconds = null;
+ if (ctx.olderWord != null && ctx.olderThan != null) {
+ checkHboWord(ctx.olderWord, "OLDER_THAN");
+ try {
+ olderThanSeconds = Long.parseLong(ctx.olderThan.getText());
+ } catch (NumberFormatException e) {
+ throw new ParseException(
+ "hbo delete stale statistics OLDER_THAN out of range:
" + ctx.olderThan.getText());
+ }
+ }
+ return new HboDeleteStaleStatisticsCommand(olderThanSeconds);
+ }
+
+ @Override
+ public LogicalPlan
visitHboDeleteStatistics(DorisParser.HboDeleteStatisticsContext ctx) {
+ checkHboStatementWords(ctx.hbo, ctx.statistics);
+ checkHboWord(ctx.fingerprintWord, "FINGERPRINT");
+ return new HboStatisticsCommand(HboStatisticsCommand.Op.DELETE,
+ ctx.scope == null ? null : ctx.scope.getText(),
+ stripQuotes(ctx.fingerprint.getText()), 0, null, "", null);
+ }
+
+ @Override
+ public LogicalPlan
visitHboShowStatistics(DorisParser.HboShowStatisticsContext ctx) {
+ checkHboStatementWords(ctx.hbo, ctx.statistics);
+ String scope = ctx.scope == null ? null : ctx.scope.getText();
+ String likePattern = ctx.likePattern == null ? null :
stripQuotes(ctx.likePattern.getText());
Review Comment:
认可，已修复（0cbdc52d362）：SHOW ... LIKE 的 pattern 改走
SqlLiteralUtils.parseStringLiteral，'' 折半与反斜杠转义都与普通字符串字面量一致，'%O''Brien%' 可以正确匹配。
--
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]
