GroupStructInfo.java
// 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.NullSafeEqual;
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.annotations.VisibleForTesting;
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.Collection;
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.concurrent.atomic.AtomicInteger;
/**
* 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;
/**
* Snapshot value which marks a plan node that is deliberately excluded from the hbo
* fingerprint (its group is unsupported, e.g. a sort / topn). It is not a fingerprint and is
* never hashed: the publish path uses it to tell an expected gap from a lost snapshot. A
* concurrent map can not store a null marker, so an empty string is used.
*/
public static final String UNSUPPORTED_FINGERPRINT = "";
private static final List<HboScanDescriptor> INVALID_SCANS = Collections.emptyList();
/**
* Characters which structure the canonical form and therefore can not appear raw inside a
* literal value (see {@link #encodeLiteralValue}).
*/
private static final String RESERVED_LITERAL_CHARS = "\\%(){}[],;:|";
private static final char[] HEX_DIGITS = "0123456789ABCDEF".toCharArray();
/**
* How many groups this query described. A group is described once: the description is memoized on
* the group and composed by its parents, so this number only grows when a new group is reached.
*/
private static final AtomicInteger describedGroups = new AtomicInteger();
/**
* How many descriptions were walked while materializing a string. A description whose string is
* already materialized is copied instead of being walked again, so this number does not grow for
* the sub tree of an already materialized child.
*/
private static final AtomicInteger materializedGroups = new AtomicInteger();
/** Shared invalid instance: the group content is not supported by the simplified struct info. */
public static final GroupStructInfo INVALID =
new GroupStructInfo(false, false, "", Collections.emptyList(), 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, true, "", Collections.emptyList(), 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;
/** Whether the failure was an environment problem which a later lookup may survive. */
private final boolean retryable;
/**
* The rope of this description: the text fragments of its own layer (in both literal modes) and
* references to the descriptions of its child groups. A parent therefore records only its own
* layer and never rebuilds the canonical string of a child; the strings are materialized on the
* first request (see {@link #getCanonical(LiteralMode)}).
*/
private final List<Piece> pieces;
/** 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;
// the forms materialized on first request: the read side only needs a fingerprint, while the
// explain annotation needs the canonical string, so building all of them up front would be wasted
private String canonicalWithLiteral;
private String canonicalNoLiteral;
private String shapeWithLiteral;
private String shapeNoLiteral;
private String fingerprintWithLiteral;
private String fingerprintNoLiteral;
private GroupStructInfo(boolean valid, boolean retryable, String skipReason, List<Piece> pieces,
List<HboScanDescriptor> scans) {
this.valid = valid;
this.retryable = retryable;
this.skipReason = skipReason;
this.pieces = pieces;
this.scans = scans;
}
private static GroupStructInfo ofPieces(List<Piece> pieces, List<HboScanDescriptor> scans) {
return new GroupStructInfo(true, false, "", pieces, Collections.unmodifiableList(scans));
}
private static GroupStructInfo invalidStructInfo(String skipReason) {
return skipReason.isEmpty()
? INVALID
: new GroupStructInfo(false, false, skipReason, Collections.emptyList(), INVALID_SCANS);
}
private static GroupStructInfo transientStructInfo() {
return TRANSIENT_FAILURE;
}
/** 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;
}
/**
* Whether the description failed on the environment (the data state of a table could not be read)
* rather than on the plan: such a failure is not memoized, so that a later lookup retries.
*/
public boolean isRetryable() {
return retryable;
}
/**
* 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;
}
/** The canonical string of one literal mode, with the data state of every scan. */
public String getCanonical(LiteralMode mode) {
boolean noLiteral = mode == LiteralMode.NO_LITERAL;
String materialized = noLiteral ? canonicalNoLiteral : canonicalWithLiteral;
if (materialized != null) {
return materialized;
}
StringBuilder sb = new StringBuilder(256);
appendTo(sb, mode, false);
materialized = sb.toString();
if (noLiteral) {
canonicalNoLiteral = materialized;
} else {
canonicalWithLiteral = materialized;
}
return materialized;
}
/**
* The fingerprint input of one literal mode: the canonical string with the data state of every
* scan removed ({@code S{db.t}}). It is assembled from the rope and never parsed out of the
* canonical string, so no text inside a table name or a literal can be mistaken for a scan token.
*/
public String getShape(LiteralMode mode) {
boolean noLiteral = mode == LiteralMode.NO_LITERAL;
String materialized = noLiteral ? shapeNoLiteral : shapeWithLiteral;
if (materialized != null) {
return materialized;
}
StringBuilder sb = new StringBuilder(256);
appendTo(sb, mode, true);
materialized = sb.toString();
if (noLiteral) {
shapeNoLiteral = materialized;
} else {
shapeWithLiteral = materialized;
}
return materialized;
}
/** The sha256 of {@link #getShape(LiteralMode)}: the key an hbo entry is registered under. */
public String getFingerprint(LiteralMode mode) {
boolean noLiteral = mode == LiteralMode.NO_LITERAL;
String materialized = noLiteral ? fingerprintNoLiteral : fingerprintWithLiteral;
if (materialized != null) {
return materialized;
}
materialized = sha256(getShape(mode));
if (noLiteral) {
fingerprintNoLiteral = materialized;
} else {
fingerprintWithLiteral = materialized;
}
return materialized;
}
/**
* Write one form of this description: the pieces of its own layer and, for a child whose same
* form is already materialized, that materialized string instead of walking the child again.
*/
private void appendTo(StringBuilder out, LiteralMode mode, boolean shape) {
materializedGroups.incrementAndGet();
for (Piece piece : pieces) {
piece.appendTo(out, mode, shape);
}
}
private String materialized(LiteralMode mode, boolean shape) {
if (shape) {
return mode == LiteralMode.NO_LITERAL ? shapeNoLiteral : shapeWithLiteral;
}
return mode == LiteralMode.NO_LITERAL ? canonicalNoLiteral : canonicalWithLiteral;
}
private static String sha256(String value) {
return Hashing.sha256().hashString(value, StandardCharsets.UTF_8).toString();
}
/**
* 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) {
Group group = planNode.getGroupExpression().map(GroupExpression::getOwnerGroup).orElse(null);
return fingerprintOfGroup(group, 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 fingerprintOfGroup(resolveGroup(planNode, groupsById), mode);
}
private static Optional<String> fingerprintOfGroup(Group group, LiteralMode mode) {
GroupStructInfo structInfo = group == null ? INVALID : group.getOrComputeHboStructInfo();
return structInfo.isValid() ? Optional.of(structInfo.getFingerprint(mode)) : Optional.empty();
}
/**
* Resolve the description 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}). Empty when the group content is unsupported.
*/
public static Optional<GroupStructInfo> structInfoOfPlanNode(AbstractPlan planNode,
Map<Integer, Group> groupsById) {
return structInfoOfGroup(resolveGroup(planNode, groupsById));
}
private static Optional<GroupStructInfo> structInfoOfGroup(Group group) {
if (group == null) {
return Optional.empty();
}
GroupStructInfo structInfo = group.getOrComputeHboStructInfo();
return structInfo.isValid() ? Optional.of(structInfo) : Optional.empty();
}
/**
* The description of a group: computed once per query and memoized on the group (see
* {@link Group#getOrComputeHboStructInfo}), so that a parent composes the description of its
* children instead of describing their sub trees again.
*/
public static GroupStructInfo of(Group group) {
if (group.getLogicalExpressions().isEmpty()) {
// physical only group: nothing to describe
return INVALID;
}
return group.getOrComputeHboStructInfo();
}
public static GroupStructInfo describeGroup(Group group) {
return describeGroup(group, new Ctx());
}
private static GroupStructInfo describeGroup(Group group, Ctx ctx) {
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 INVALID;
}
return describeVisited(group, ctx);
}
/**
* The description of a group which the caller already marked visited (the join chain marks the
* groups it descends through itself, so that a group is never added twice within one build).
*/
private static GroupStructInfo describeVisited(Group group, Ctx ctx) {
GroupStructInfo memoized = group.getHboStructInfoOrNull();
if (memoized != null) {
return memoized;
}
GroupStructInfo computed = build(group, ctx);
if (!computed.isRetryable()) {
// a catalog failure is retried by the next lookup instead of being cached
group.setHboStructInfo(computed);
}
return computed;
}
/**
* Describe one group by composing the descriptions of its children (which are memoized, so each
* group of a plan is described exactly once per query), in both literal modes at once.
*/
private static GroupStructInfo build(Group group, Ctx ctx) {
describedGroups.incrementAndGet();
HboStructSummary summary = group.getOrComputeHboStructSummary();
int maxScansPerGroup = hboMaxScansPerGroup();
if (maxScansPerGroup > 0 && summary.getScanCount() > maxScansPerGroup) {
// The canonical string of a group describes its whole sub tree, 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 invalidStructInfo("subtree scans=" + summary.getScanCount()
+ " > hbo_max_scans_per_group=" + maxScansPerGroup);
}
if (group.getLogicalExpressions().isEmpty()) {
// physical only group: there is no expression to describe
return INVALID;
}
GroupExpression ge = group.getFirstLogicalExpression();
Canonical out = new Canonical();
try {
appendPlan(ge.getPlan(), ge, out, ctx);
} 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 ? transientStructInfo() : INVALID;
}
if (!ctx.valid) {
return ctx.retryable ? transientStructInfo() : INVALID;
}
return ofPieces(out.getPieces(), out.getScans());
}
/** The memo group a plan node belongs to: its back reference, or the post processed group id. */
private static Group resolveGroup(AbstractPlan planNode, Map<Integer, Group> groupsById) {
Group group = planNode.getGroupExpression().map(GroupExpression::getOwnerGroup).orElse(null);
if (group != null) {
return group;
}
Optional<Object> groupState = planNode.getMutableState(MutableState.KEY_GROUP);
if (groupState.isPresent() && groupsById != null) {
try {
return groupsById.get(Integer.valueOf(groupState.get().toString()));
} catch (NumberFormatException ignored) {
return null;
}
}
return null;
}
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;
StringBuilder withLiteralHeader = new StringBuilder("F{");
StringBuilder noLiteralHeader = new StringBuilder("F{");
appendNormalizedSorted(filter.getConjuncts(), withLiteralHeader, noLiteralHeader);
out.modes(withLiteralHeader.append("}(").toString(), noLiteralHeader.append("}(").toString());
appendChild(ge, 0, out, ctx);
out.same(")");
} 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 appendChild(GroupExpression ge, int index, Canonical out, Ctx ctx) {
if (!ctx.valid) {
return;
}
// the child is described once per query: its memoized parts are composed here instead of
// walking its sub tree again (the grand children are never visited by this build)
GroupStructInfo child = describeGroup(ge.child(index), ctx);
if (!child.isValid()) {
if (child.isRetryable()) {
transientFailure(ctx);
} else {
invalid(ctx);
}
return;
}
out.append(child);
}
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.same("J{" + join.getJoinType() + ",c:[");
TreeSet<String> conditions = new TreeSet<>();
TreeSet<String> conditionsNoLiteral = new TreeSet<>();
collectJoinConditions(join, conditions, conditionsNoLiteral);
out.modes(String.join(SEP, conditions), String.join(SEP, conditionsNoLiteral));
out.same("]}(");
appendChild(ge, 0, out, ctx);
out.same(SEP);
appendChild(ge, 1, out, ctx);
out.same(")");
}
/**
* 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<>();
TreeSet<String> conditionsNoLiteral = new TreeSet<>();
List<Leaf> leaves = new ArrayList<>();
collectJoinConditions(join, conditions, conditionsNoLiteral);
for (int i = 0; i < ge.arity(); i++) {
collectJoinChain(ge.child(i), conditions, conditionsNoLiteral, 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.same("J{inner,c:[");
out.modes(String.join(SEP, conditions), String.join(SEP, conditionsNoLiteral));
out.same("]}(");
for (int i = 0; i < leaves.size(); i++) {
if (i > 0) {
out.same(SEP);
}
out.append(leaves.get(i).getLeaf());
}
out.same(")");
}
/**
* Collect one member of an inner / cross join chain: either descend into another join of the
* chain (associativity), or take the memoized parts of the whole sub tree as one chain leaf.
* The group of {@code group} is already marked visited by the caller.
*/
private static void collectJoinChain(Group group, TreeSet<String> conditions,
TreeSet<String> conditionsNoLiteral, 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, conditionsNoLiteral);
for (int i = 0; i < ge.arity(); i++) {
collectJoinChain(ge.child(i), conditions, conditionsNoLiteral, 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, conditionsNoLiteral, leaves, ctx);
return;
}
GroupStructInfo leaf = describeVisited(group, ctx);
if (!leaf.isValid()) {
if (leaf.isRetryable()) {
transientFailure(ctx);
} else {
invalid(ctx);
}
return;
}
leaves.add(new Leaf(leaf));
}
/** One leaf of a flattened join chain: the memoized description of that sub tree. */
private static class Leaf {
private final GroupStructInfo leaf;
Leaf(GroupStructInfo leaf) {
this.leaf = leaf;
}
GroupStructInfo getLeaf() {
return leaf;
}
String getShape() {
return leaf.getShape(LiteralMode.WITH_LITERAL);
}
}
/** 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.
StringBuilder withLiteralHeader = new StringBuilder("A{gb:");
StringBuilder noLiteralHeader = new StringBuilder("A{gb:");
appendNormalizedSorted(agg.getGroupByExpressions(), withLiteralHeader, noLiteralHeader);
out.modes(withLiteralHeader.append("}(").toString(), noLiteralHeader.append("}(").toString());
appendChild(ge, 0, out, ctx);
out.same(")");
}
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.scan(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();
}
// -----------------------------------------------------------------------------------
// expression normalization: strip slot/expr ids, keep qualifier + column + literal value
// -----------------------------------------------------------------------------------
/**
* Append the two forms of a set of conjuncts (each form sorted) while normalizing every conjunct
* once.
*/
private static void appendNormalizedSorted(Collection<Expression> conjuncts,
StringBuilder withLiteral, StringBuilder noLiteral) {
List<String> withLiteralParts = new ArrayList<>(conjuncts.size());
List<String> noLiteralParts = new ArrayList<>(conjuncts.size());
for (Expression conjunct : conjuncts) {
StringBuilder partWithLiteral = new StringBuilder();
StringBuilder partNoLiteral = new StringBuilder();
appendNormalizedExpression(conjunct, partWithLiteral, partNoLiteral);
withLiteralParts.add(partWithLiteral.toString());
noLiteralParts.add(partNoLiteral.toString());
}
withLiteralParts.sort(String::compareTo);
noLiteralParts.sort(String::compareTo);
withLiteral.append(String.join(SEP, withLiteralParts));
noLiteral.append(String.join(SEP, noLiteralParts));
}
/**
* Collect both forms of the conditions of one join node (hash and other conjuncts) as sorted, de
* duplicated sets, normalizing every conjunct once: 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 void collectJoinConditions(LogicalJoin<?, ?> join,
Set<String> conditions, Set<String> conditionsNoLiteral) {
for (Expression conjunct : join.getHashJoinConjuncts()) {
addCondition(conjunct, conditions, conditionsNoLiteral);
}
for (Expression conjunct : join.getOtherJoinConjuncts()) {
addCondition(conjunct, conditions, conditionsNoLiteral);
}
}
private static void addCondition(Expression conjunct,
Set<String> conditions, Set<String> conditionsNoLiteral) {
StringBuilder withLiteral = new StringBuilder();
StringBuilder noLiteral = new StringBuilder();
appendNormalizedExpression(conjunct, withLiteral, noLiteral);
conditions.add(withLiteral.toString());
conditionsNoLiteral.add(noLiteral.toString());
}
/**
* Encode a literal value so that it can not be read as the structure of the canonical form. A
* value carrying a parenthesis or a separator (e.g. {@code where s = 'a)b'}) would otherwise
* close its own {@code lit(...)} and could forge a conjunct next to it, which would let two
* different predicates share one fingerprint; an unbalanced parenthesis would also break the
* rendering of the simplified struct info. The reserved characters are percent encoded, so the
* encoding is the identity for the values which carry none of them (numbers, plain strings);
* {@link #decodeLiteralValue} reverses it for display.
*/
public static String encodeLiteralValue(String value) {
StringBuilder sb = null;
for (int i = 0; i < value.length(); i++) {
char c = value.charAt(i);
if (RESERVED_LITERAL_CHARS.indexOf(c) < 0) {
if (sb != null) {
sb.append(c);
}
continue;
}
if (sb == null) {
sb = new StringBuilder(value.length() + 8);
sb.append(value, 0, i);
}
sb.append('%').append(HEX_DIGITS[(c >> 4) & 0xF]).append(HEX_DIGITS[c & 0xF]);
}
return sb == null ? value : sb.toString();
}
/** Reverse of {@link #encodeLiteralValue}: turn an encoded literal value back into its text. */
public static String decodeLiteralValue(String value) {
int start = value.indexOf('%');
if (start < 0) {
return value;
}
StringBuilder sb = new StringBuilder(value.length());
sb.append(value, 0, start);
for (int i = start; i < value.length(); i++) {
char c = value.charAt(i);
if (c == '%' && i + 2 < value.length()
&& Character.digit(value.charAt(i + 1), 16) >= 0
&& Character.digit(value.charAt(i + 2), 16) >= 0) {
sb.append((char) ((Character.digit(value.charAt(i + 1), 16) << 4)
| Character.digit(value.charAt(i + 2), 16)));
i += 2;
} else {
sb.append(c);
}
}
return sb.toString();
}
/**
* 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, 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);
}
/**
* Normalize an expression into its canonical component in the given literal mode: a literal keeps
* its value, or becomes {@code lit(*)} when the constant agnostic form is asked for.
*/
public static String normalizeExpression(Expression expression, LiteralMode mode) {
StringBuilder withLiteral = new StringBuilder();
StringBuilder noLiteral = new StringBuilder();
appendNormalizedExpression(expression, withLiteral, noLiteral);
return mode == LiteralMode.NO_LITERAL ? noLiteral.toString() : withLiteral.toString();
}
/**
* Append both forms of one expression while walking its tree once: the literal carrying form into
* {@code withLiteral} and the constant agnostic one into {@code noLiteral}. The operands of a
* commutative operator are sorted per form, because a literal value may order two operands
* differently than {@code lit(*)} does.
*/
private static void appendNormalizedExpression(Expression expression,
StringBuilder withLiteral, StringBuilder noLiteral) {
if (expression instanceof SlotReference) {
SlotReference slot = (SlotReference) expression;
String text = "col(" + String.join(".", slot.getQualifier()) + "." + slot.getName() + ")";
withLiteral.append(text);
noLiteral.append(text);
} else if (expression instanceof Literal) {
Literal literal = (Literal) expression;
withLiteral.append("lit(").append(encodeLiteralValue(String.valueOf(literal.getValue())))
.append(':').append(literal.getDataType()).append(')');
noLiteral.append("lit(*)");
} else if (expression.children().isEmpty()) {
String name = expression.getClass().getSimpleName();
withLiteral.append(name);
noLiteral.append(name);
} else {
List<String> withLiteralChildren = new ArrayList<>();
List<String> noLiteralChildren = new ArrayList<>();
for (Expression child : expression.children()) {
StringBuilder childWithLiteral = new StringBuilder();
StringBuilder childNoLiteral = new StringBuilder();
appendNormalizedExpression(child, childWithLiteral, childNoLiteral);
withLiteralChildren.add(childWithLiteral.toString());
noLiteralChildren.add(childNoLiteral.toString());
}
if (isOrderInsensitive(expression)) {
// only order-insensitive operators (equal-to / null safe 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)
withLiteralChildren.sort(String::compareTo);
noLiteralChildren.sort(String::compareTo);
}
String name = expression.getClass().getSimpleName();
withLiteral.append(name).append('(').append(String.join(",", withLiteralChildren)).append(')');
noLiteral.append(name).append('(').append(String.join(",", noLiteralChildren)).append(')');
}
}
/**
* Equal-to (including its null safe form) and boolean and/or are commutative; everything else
* keeps its operand order.
*/
private static boolean isOrderInsensitive(Expression expression) {
return expression instanceof EqualTo
|| expression instanceof NullSafeEqual
|| expression instanceof Or
|| expression instanceof And;
}
private static int hboMaxScansPerGroup() {
ConnectContext connectContext = ConnectContext.get();
if (connectContext == null || connectContext.getSessionVariable() == null) {
return DEFAULT_MAX_SCANS_PER_GROUP;
}
return connectContext.getSessionVariable().getHboMaxScansPerGroup();
}
/**
* The structural summary of a memo group: how many scan tokens the struct info of its sub tree
* would contain, and which tables it reads.
*
* <p>It is aggregated bottom up from the children's summaries - no string is rendered and no
* catalog is read - and memoized per group (see {@code Group#getOrComputeHboStructSummary}), so
* it is the cheap gate in front of the canonical string: a group which is too large for
* {@code hbo_max_scans_per_group} never renders one, and a group whose relation key can not
* match any entry does not render one either (see {@code HboPlanStatisticsManager}).
*/
public static final class HboStructSummary {
private final int scanCount;
/** The tables of the sub tree, in traversal order and with duplicates (a self join twice). */
private final List<String> relations;
private final String relationKey;
private HboStructSummary(int scanCount, List<String> relations) {
this.scanCount = scanCount;
this.relations = Collections.unmodifiableList(new ArrayList<>(relations));
List<String> sorted = new ArrayList<>(relations);
Collections.sort(sorted);
this.relationKey = String.join(",", sorted);
}
/** The number of scan tokens in the sub tree (a self join counts the table twice). */
public int getScanCount() {
return scanCount;
}
/**
* The tables of the sub tree as one order independent key (sorted, duplicates kept). A group
* whose struct info could equal another one's necessarily shares this key, so it is a safe
* necessary condition for an entry lookup; a group with no scan at all keys to "".
*/
public String getRelationKey() {
return relationKey;
}
List<String> getRelations() {
return relations;
}
}
/** The summary of a group, computed from the (memoized) summaries of its child groups. */
public static HboStructSummary summaryOf(Group group) {
List<GroupExpression> logicalExpressions = group.getLogicalExpressions();
if (logicalExpressions.isEmpty()) {
// a group which holds only physical expressions (e.g. the storage layer aggregate rule
// inserts one) has nothing to describe, and getFirstLogicalExpression would throw
return new HboStructSummary(0, Collections.emptyList());
}
GroupExpression ge = logicalExpressions.get(0);
Plan plan = ge.getPlan();
List<String> relations = new ArrayList<>();
int scanCount = 0;
if (plan instanceof LogicalOlapScan) {
scanCount = 1;
relations.add(((LogicalOlapScan) plan).getTable().getNameWithFullQualifiers());
}
for (int i = 0; i < ge.arity(); i++) {
Group child = ge.child(i);
if (child == null) {
continue;
}
HboStructSummary childSummary = child.getOrComputeHboStructSummary();
scanCount += childSummary.getScanCount();
relations.addAll(childSummary.getRelations());
}
return new HboStructSummary(scanCount, relations);
}
/**
* Why the struct info of the group of {@code planNode} was refused, if it was refused by a limit.
* Cheap: only the memoized structural summary is read, no canonical string is built.
*/
public static Optional<String> limitSkipReasonOfPlanNode(AbstractPlan planNode,
Map<Integer, Group> groupsById) {
Group group = resolveGroup(planNode, groupsById);
if (group == null) {
return Optional.empty();
}
int maxScansPerGroup = hboMaxScansPerGroup();
int scans = group.getOrComputeHboStructSummary().getScanCount();
if (maxScansPerGroup > 0 && scans > maxScansPerGroup) {
return Optional.of("subtree scans=" + scans
+ " > hbo_max_scans_per_group=" + maxScansPerGroup);
}
return Optional.empty();
}
/** The number of groups described since the last reset. For tests only. */
@VisibleForTesting
public static int getDescribedGroupCount() {
return describedGroups.get();
}
/** Reset the description counter. For tests only. */
@VisibleForTesting
public static void resetDescribedGroupCount() {
describedGroups.set(0);
}
/** The number of descriptions walked since the last reset. For tests only. */
@VisibleForTesting
public static int getMaterializedGroupCount() {
return materializedGroups.get();
}
/** Reset the materialization counter. For tests only. */
@VisibleForTesting
public static void resetMaterializedGroupCount() {
materializedGroups.set(0);
}
/** The relation key of the group of a plan node, or null when that group is not reachable. */
public static String relationKeyOfPlanNode(AbstractPlan planNode, Map<Integer, Group> groupsById) {
Group group = resolveGroup(planNode, groupsById);
return group == null ? null : group.getOrComputeHboStructSummary().getRelationKey();
}
/** The state of one build: it describes the sub tree of the group it was started at. */
private static class Ctx {
private boolean valid = true;
/** whether the failure was an environment problem which a later lookup may survive */
private boolean retryable = false;
private final Set<Group> visited = new HashSet<>();
}
/**
* The rope of one group: a text fragment (its two literal forms) or a reference to the
* description of a child. Materializing a form walks the pieces and copies the strings, it never
* parses them, and it takes the materialized string of a child when that child already has it.
*/
private interface Piece {
void appendTo(StringBuilder out, LiteralMode mode, boolean shape);
}
/** A fragment of text: the same structure in both forms, the literals differ per mode. */
private static final class Text implements Piece {
private final String withLiteral;
private final String noLiteral;
Text(String withLiteral, String noLiteral) {
this.withLiteral = withLiteral;
this.noLiteral = noLiteral;
}
String getWithLiteral() {
return withLiteral;
}
String getNoLiteral() {
return noLiteral;
}
@Override
public void appendTo(StringBuilder out, LiteralMode mode, boolean shape) {
out.append(mode == LiteralMode.NO_LITERAL ? noLiteral : withLiteral);
}
}
/** The scan token of a scan group: the only piece which differs between the two forms. */
private static final class ScanToken implements Piece {
private final HboScanDescriptor descriptor;
ScanToken(HboScanDescriptor descriptor) {
this.descriptor = descriptor;
}
HboScanDescriptor getDescriptor() {
return descriptor;
}
@Override
public void appendTo(StringBuilder out, LiteralMode mode, boolean shape) {
out.append("S{").append(shape ? descriptor.getTable() : descriptor.render()).append('}');
}
}
/** A child sub tree. */
private static final class Child implements Piece {
private final GroupStructInfo child;
Child(GroupStructInfo child) {
this.child = child;
}
GroupStructInfo getChild() {
return child;
}
@Override
public void appendTo(StringBuilder out, LiteralMode mode, boolean shape) {
String materialized = child.materialized(mode, shape);
if (materialized != null) {
// the child is already materialized in this form: copy it instead of walking its own
// pieces again (and therefore without touching its grand children)
out.append(materialized);
return;
}
child.appendTo(out, mode, shape);
}
}
/**
* The rope a build assembles: the pieces of one group, plus the scans of its whole sub tree in
* the order their tokens appear (a caller which compares them with the scans of another struct
* info has to see the same order the printed struct info has, which is not always the build order
* because a join chain prints its leaves sorted).
*/
private static class Canonical {
private final List<Piece> pieces = new ArrayList<>();
private final List<HboScanDescriptor> scans = new ArrayList<>();
/** A fragment which is the same in every form (structure, separator). */
Canonical same(String text) {
return addText(text, text);
}
/** A fragment which differs between the literal modes (a literal carrying expression). */
Canonical modes(String withLiteral, String noLiteral) {
return addText(withLiteral, noLiteral);
}
/** The scan token of a scan group. */
Canonical scan(HboScanDescriptor descriptor) {
pieces.add(new ScanToken(descriptor));
scans.add(descriptor);
return this;
}
/**
* Compose the description of a child (or of a join chain leaf): the rope only records the
* reference, and the scans of the child are inherited in token order.
*/
Canonical append(GroupStructInfo child) {
if (child.isValid()) {
pieces.add(new Child(child));
scans.addAll(child.getScans());
}
return this;
}
private Canonical addText(String withLiteral, String noLiteral) {
if (withLiteral.isEmpty() && noLiteral.isEmpty()) {
return this;
}
Piece last = pieces.isEmpty() ? null : pieces.get(pieces.size() - 1);
if (last instanceof Text) {
// merge neighbouring text, so that a layer of structure does not become a long list
// of one character pieces
Text previous = (Text) last;
pieces.set(pieces.size() - 1, new Text(previous.getWithLiteral() + withLiteral,
previous.getNoLiteral() + noLiteral));
return this;
}
pieces.add(new Text(withLiteral, noLiteral));
return this;
}
List<Piece> getPieces() {
return pieces;
}
List<HboScanDescriptor> getScans() {
return scans;
}
}
}