github-actions[bot] commented on code in PR #69322:
URL: https://github.com/apache/doris/pull/69322#discussion_r4356183525
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/JoinEstimation.java:
##########
@@ -278,6 +279,13 @@ private static Statistics estimateInnerJoin(Statistics
leftStats, Statistics rig
innerJoinStats = estimateInnerJoinWithEqualPredicate(leftStats,
rightStats, join);
}
+ if (expansion != 1.0) {
+ // the factor is the fan out of the equality conditions: scale
their estimate before the
+ // residual conditions (which keep their own selectivity) are
applied
+ innerJoinStats = new StatisticsBuilder(innerJoinStats)
Review Comment:
[P2] Preserve residual selectivity when expanding equality rows
For the reduced plan `INNER(hash=a.k=b.k, other=(a.v IS NULL OR b.v IS
NULL), Scan(a), Scan(b))`, let each analyzed input have 1000 rows, k
NDV=1000/no NULLs and v NDV=500/NULLs=500. The cross-input OR remains a join
residual. A factor of 100 changes the equality estimate from 1000 to 100000
here, but `StatisticsBuilder` retains each v's absolute null count and
base-column identity. `FilterEstimation.visitIsNull` therefore still estimates
500 for each disjunct, and `visitOr` returns at most 1000, effectively
discarding the registered expansion. Later normalization cannot restore the
lost factor. Scale the dependent populations consistently before applying
residuals, or preserve the unexpanded residual selectivity. This reaches the
multiplier with known column statistics and is separate from the existing
unknown-statistics early-return issue.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/GroupStructInfo.java:
##########
@@ -0,0 +1,3235 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.stats;
+
+import org.apache.doris.catalog.TableIf;
+import org.apache.doris.nereids.memo.Group;
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.OrderKey;
+import org.apache.doris.nereids.trees.expressions.Alias;
+import org.apache.doris.nereids.trees.expressions.And;
+import org.apache.doris.nereids.trees.expressions.ArrayItemReference;
+import org.apache.doris.nereids.trees.expressions.EqualTo;
+import org.apache.doris.nereids.trees.expressions.ExprId;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.Match;
+import org.apache.doris.nereids.trees.expressions.NamedExpression;
+import org.apache.doris.nereids.trees.expressions.NullSafeEqual;
+import org.apache.doris.nereids.trees.expressions.NullToNonNullFunction;
+import org.apache.doris.nereids.trees.expressions.Or;
+import org.apache.doris.nereids.trees.expressions.OrderExpression;
+import org.apache.doris.nereids.trees.expressions.SearchExpression;
+import org.apache.doris.nereids.trees.expressions.Slot;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
+import org.apache.doris.nereids.trees.expressions.WindowExpression;
+import org.apache.doris.nereids.trees.expressions.functions.Function;
+import org.apache.doris.nereids.trees.expressions.functions.Udf;
+import
org.apache.doris.nereids.trees.expressions.functions.agg.AggregateFunction;
+import org.apache.doris.nereids.trees.expressions.functions.scalar.Lambda;
+import org.apache.doris.nereids.trees.expressions.literal.ArrayLiteral;
+import org.apache.doris.nereids.trees.expressions.literal.DateLiteral;
+import org.apache.doris.nereids.trees.expressions.literal.Literal;
+import org.apache.doris.nereids.trees.expressions.literal.NullLiteral;
+import org.apache.doris.nereids.trees.expressions.visitor.ExpressionVisitor;
+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.algebra.Aggregate;
+import org.apache.doris.nereids.trees.plans.algebra.Except;
+import org.apache.doris.nereids.trees.plans.algebra.Filter;
+import org.apache.doris.nereids.trees.plans.algebra.Generate;
+import org.apache.doris.nereids.trees.plans.algebra.Intersect;
+import org.apache.doris.nereids.trees.plans.algebra.Join;
+import org.apache.doris.nereids.trees.plans.algebra.Limit;
+import org.apache.doris.nereids.trees.plans.algebra.OlapScan;
+import org.apache.doris.nereids.trees.plans.algebra.Project;
+import org.apache.doris.nereids.trees.plans.algebra.Repeat;
+import org.apache.doris.nereids.trees.plans.algebra.SetOperation;
+import org.apache.doris.nereids.trees.plans.algebra.Sort;
+import org.apache.doris.nereids.trees.plans.algebra.TopN;
+import org.apache.doris.nereids.trees.plans.algebra.Union;
+import org.apache.doris.nereids.trees.plans.algebra.Window;
+import org.apache.doris.nereids.trees.plans.logical.LogicalCTEAnchor;
+import org.apache.doris.nereids.trees.plans.logical.LogicalCTEConsumer;
+import org.apache.doris.nereids.trees.plans.logical.LogicalCTEProducer;
+import org.apache.doris.nereids.trees.plans.logical.LogicalFileScan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalGenerate;
+import org.apache.doris.nereids.trees.plans.logical.LogicalOlapScan;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalAssertNumRows;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalCTEAnchor;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalCTEConsumer;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalCTEProducer;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalDistribute;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalFileScan;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalGenerate;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalHashAggregate;
+import
org.apache.doris.nereids.trees.plans.physical.PhysicalStorageLayerAggregate;
+import org.apache.doris.nereids.types.DataType;
+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.time.ZoneId;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Locale;
+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.
+ *
+ * <p>This description is always built by the FE from the plan it is looking
at, and every string it can
+ * produce is one of its renderings: {@link #getCanonical(LiteralMode)} is the
text EXPLAIN prints and a
+ * user may paste into {@code HBO SET STATISTICS ... STRUCT='...'}, {@link
#getShape(LiteralMode)} is the
+ * same text without the data state of the scans, and {@link
#getFingerprint(LiteralMode)} is the sha256
+ * of that shape. Nothing is ever parsed to produce a fingerprint - in
particular the text a user pasted
+ * is only compared with the fingerprint next to it, never taken as its source.
+ */
+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 = "";
+
+ /**
+ * The prefix of the reason a node whose kind the description does not
support is reported with, and
+ * the two halves of the reason a node with an unsupported number of
children is reported with. They
+ * are constants so that the corpus can bind the frozen skip texts to the
formula which produces them
+ * instead of restating the prefix.
+ */
+ static final String UNSUPPORTED_REASON_PREFIX = "unsupported=";
+ static final String ARITY_REASON_PREFIX = "arity=";
+ static final String ARITY_REASON_MIDDLE = " of ";
+
+ 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 = "\u0000\\%(){}[],;:|";
+
+ 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 describedGroupCount = 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 materializedGroupCount = new
AtomicInteger();
+
+ /** Shared invalid instance: the group content is not supported by the
simplified struct info. */
+ public static final GroupStructInfo INVALID = new GroupStructInfo(false,
"", null, INVALID_SCANS);
+
+ private static final String SEP = ";";
+
+ /**
+ * The header letters whose arguments are part of the identity of their
node (see
+ * {@link Kind#literalsAreIdentity()}): the fold of a pasted struct info
copies those headers verbatim,
+ * because folding one of their literals would make the sha256 of the text
differ from the fingerprint
+ * EXPLAIN printed. The set is derived from the kinds which render the
text, so a kind whose literals
+ * stop being identity cannot be forgotten here.
+ */
+ private static final String PROTECTED_HEADERS = protectedHeaders();
+
+ /**
+ * The markers of the headers whose condition collection is sorted per
literal mode, i.e. the ones the
+ * fold of a pasted struct info has to re-sort after it folded their
literals (see
+ * {@code recanonicalizeFoldedConditions}): a filter, an aggregation, a
join (which also de-duplicates)
+ * and the grouping sets of a repeat.
+ */
+ private static final String[] CONDITION_HEADER_MARKERS = {"F{", "A{gb:",
"J{", "R{gs:["};
+
+ /**
+ * The functions whose value depends on the session time zone although
neither their arguments nor
+ * their result are a date: an epoch value is read in that zone ({@code
hour_from_unixtime(t.ts) = 0}
+ * keeps 1000 rows in one session and 1 row in another although its
argument is the same integer).
+ * A function whose argument or result is a date or a datetime is covered
by its type instead (see
+ * {@link #usesSessionTimeZone}).
+ */
+ private static final List<String> EPOCH_TIME_ZONE_FUNCTIONS =
Arrays.asList(
+ "hour_from_unixtime", "minute_from_unixtime",
"second_from_unixtime",
+ "microsecond_from_unixtime", "unix_timestamp");
+
+ private static final String NO_LOOKUP_PATH_REASON =
+ "storage layer aggregate: the read side applies the row count of
the aggregation above it";
+
+ private static final String PARTIAL_STAGE_REASON =
+ "local (partial) aggregation stage: the read side applies the row
count of the final"
+ + " aggregation above it";
+
+ 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. It is the primary key of a
scan, of a constant-free
+ * filter shape and of the key the publish path generates for a join
/ aggregate root; every
+ * root which is annotated also carries a literal carrying form.</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
+ }
+
+ /**
+ * Whether the description could be built. It is invalid - and the memo
caches that answer, so every
+ * node above the sub tree gets no fingerprint for the whole query - when
one of the following holds
+ * for the sub tree it covers:
+ * <ul>
+ * <li>it contains an operator the canonical form does not describe,
which the annotation prints as
+ * {@code unsupported=<Operator>}: a table valued function relation
({@code numbers},
+ * {@code s3}), an apply, a recursive union, a partition top-n,
...;</li>
+ * <li>it reads more scans than {@code hbo_max_scans_per_group}:
+ * {@code subtree scans=N > hbo_max_scans_per_group=M};</li>
+ * <li>a table name carries a struct info delimiter ({@code ,} or {@code
}}), so the printed token
+ * could not be read back: {@code delimiter in table name
<table>};</li>
+ * <li>the memo does not look like a canonical form can express it: a
unary operator whose group
+ * expression has another arity, a CTE consumer which has no memo
edge to its producer, a
+ * reused sub tree whose description is not available;</li>
+ * <li>the data state of a scan cannot be read (an external table whose
metadata is not available,
+ * a cloud rpc failure): {@code no data state for <table>
(<cause>)}.</li>
+ * </ul>
+ * A node whose group cannot be resolved at all is not described either,
which the annotation reports
+ * as {@code no group for <Operator>}.
+ */
+ private final boolean valid;
+ /**
+ * The tree of this description: the information of its own group and the
descriptions of the groups
+ * below it, all as objects. Nothing is rendered while it is built -
{@link #render} is the one place
+ * which knows the grammar - and every node remembers the forms it has
rendered, so a parent which is
+ * rendered later composes the text of a child instead of walking its sub
tree again.
+ */
+ private final Node root;
+ /** 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, String skipReason, Node root,
+ List<HboScanDescriptor> scans) {
+ this.valid = valid;
+ this.skipReason = skipReason;
+ this.root = root;
+ this.scans = scans;
+ }
+
+ private static GroupStructInfo ofNode(Node root) {
+ List<HboScanDescriptor> scans = new ArrayList<>();
+ collectScans(root, scans);
+ return new GroupStructInfo(true, "", root,
Collections.unmodifiableList(scans));
+ }
+
+ private static GroupStructInfo invalidStructInfo(String skipReason) {
+ return skipReason.isEmpty()
+ ? INVALID
+ : new GroupStructInfo(false, skipReason, null, INVALID_SCANS);
+ }
+
+ private static String protectedHeaders() {
+ StringBuilder letters = new StringBuilder();
+ for (Kind kind : Kind.values()) {
+ if (kind.literalsAreIdentity()) {
+ letters.append(kind.headerLetters());
+ }
+ }
+ return letters.toString();
+ }
+
+ /** 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;
+ }
+
+ /** The node this description is made of; null when the description is
invalid. */
+ private Node root() {
+ return root;
+ }
+
+ /**
+ * 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). A sub
+ * tree which the canonical string writes twice - a child which is
referenced more than once - keeps
+ * its token in the text twice while its tables are read once, so its
descriptors appear here once;
+ * a caller which compares this list with the tokens of a text has to
expect that difference (the
+ * learned freshness comparison folds the tokens of a text per table for
the same reason). 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;
+ }
+ materialized = root == null ? "" : render(root, mode, false);
+ 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 rendered from the same tree as the
canonical string, with the scan
+ * tokens reduced to their identity, and never parsed out of the text, 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;
+ }
+ materialized = root == null ? "" : render(root, mode, true);
+ if (noLiteral) {
+ shapeNoLiteral = materialized;
+ } else {
+ shapeWithLiteral = materialized;
+ }
+ return materialized;
+ }
+
+ /**
+ * The sha256 of {@link #shapeKey(LiteralMode)}: the key an hbo entry is
registered under.
+ *
+ * <p>The preimage is the structural form of this description, not the
canonical string: every field
+ * is written with its length, so a table name, an alias or a literal
which contains a character of
+ * the printed grammar cannot change which field it belongs to. The
canonical string is the readable
+ * projection of the same tree ({@link #getCanonical}), and a pasted
struct info is never hashed.
+ */
+ public String getFingerprint(LiteralMode mode) {
+ boolean noLiteral = mode == LiteralMode.NO_LITERAL;
+ String materialized = noLiteral ? fingerprintNoLiteral :
fingerprintWithLiteral;
+ if (materialized != null) {
+ return materialized;
+ }
+ materialized = sha256(shapeKey(mode));
+ if (noLiteral) {
+ fingerprintNoLiteral = materialized;
+ } else {
+ fingerprintWithLiteral = materialized;
+ }
+ return materialized;
+ }
+
+ private static String sha256(byte[] value) {
+ return Hashing.sha256().hashBytes(value).toString();
+ }
+
+ /** The structural identity of this description in one literal mode (see
{@link #getFingerprint}). */
+ private byte[] shapeKey(LiteralMode mode) {
+ ShapeKeyWriter out = new ShapeKeyWriter();
+ if (root == null) {
+ // an invalid description has no tree: its key is a marker of its
own
+ out.tag(-1);
+ return out.toByteArray();
+ }
+ out.tag(0);
+ appendShapeKey(out, root, mode);
+ return out.toByteArray();
+ }
+
+ /**
+ * Write one node of the structural identity: the kind, the fields the
canonical string prints for it
+ * (each as one length prefixed text) and the children. A field is never
split by the text of another
+ * one, which the printed grammar cannot promise for a value which carries
its characters.
+ */
+ private static void appendShapeKey(ShapeKeyWriter out, Node node,
LiteralMode mode) {
+ if (node.kind == Kind.PASSTHROUGH && node.children.size() == 1) {
+ // a node which only composes its child renders no text of its
own, so a plan which keeps such
+ // a node and the same plan with it inlined are one description:
the identity must not name
+ // the node, otherwise the two forms of one plan would be keyed
apart
+ appendShapeKey(out, node.children.get(0).node, mode);
+ return;
+ }
+ out.tag(node.kind.ordinal());
+ switch (node.kind) {
+ case SCAN:
+ case FILE_SCAN:
+ appendScanKey(out, node.scan);
+ return;
+ case STORAGE_AGGREGATE:
+ out.text(String.valueOf(node.storageAggregate.getAggOp()));
+ out.flag(node.scan != null);
+ if (node.scan != null) {
+ appendScanKey(out, node.scan);
+ }
+ return;
+ case FILTER:
+ out.text(sortedConditions(node.conditions, mode));
+ break;
+ case AGGREGATE:
+ out.text(sortedIdentityConditions(node.conditions));
+ break;
+ case JOIN:
+ out.text(node.flattenable ? "inner" :
String.valueOf(node.joinType));
+ out.flag(node.markJoin);
+ out.text(distinctIdentityConditions(node.conditions));
+ break;
+ case TOPN: {
+ StringBuilder header = new StringBuilder();
+ appendTopNHeader(header, node, mode);
+ out.text(header.toString());
+ break;
+ }
+ case LIMIT:
+ out.text(bound("L", node.limit, node.offset));
+ break;
+ case WINDOW: {
+ StringBuilder header = new StringBuilder();
+ appendWindowHeader(header, node);
+ out.text(header.toString());
+ // the header is the display form; the expressions it names
are written structurally as
+ // well, so a value inside them (an array literal, for
instance) keeps its own boundaries
+ out.count(node.windowExpressions.size());
+ for (NamedExpression namedExpression : node.windowExpressions)
{
+ appendExpressionKey(out, namedExpression,
LiteralMode.WITH_LITERAL);
+ }
+ break;
+ }
+ case GENERATE: {
+ StringBuilder header = new StringBuilder();
+ appendGenerateHeader(header, node);
+ out.text(header.toString());
+ out.count(node.generators.size());
+ for (Expression generator : node.generators) {
+ appendExpressionKey(out, generator,
LiteralMode.WITH_LITERAL);
+ }
+ out.count(node.generatorConjuncts.size());
+ for (Expression conjunct : node.generatorConjuncts) {
+ appendExpressionKey(out, conjunct,
LiteralMode.WITH_LITERAL);
+ }
+ break;
+ }
+ case REPEAT: {
+ StringBuilder header = new StringBuilder();
+ appendRepeatHeader(header, node, mode);
+ out.text(header.toString());
+ out.count(node.groupingSets.size());
+ for (List<Expression> set : node.groupingSets) {
+ out.count(set.size());
+ for (Expression key : set) {
+ appendExpressionKey(out, key,
LiteralMode.WITH_LITERAL);
+ }
+ }
+ break;
+ }
+ case SET_OPERATION:
+ appendSetOperationKey(out, node);
+ break;
+ case PASSTHROUGH:
+ break;
+ default:
+ throw new IllegalStateException("unknown node kind " +
node.kind);
+ }
+ out.count(node.children.size());
+ for (Child child : node.children) {
+ // a child which is referenced more than once renders the text of
the first reference, so the
+ // identity names the sub tree only, not how often the plan
references it
+ out.count(child.mapping.size());
+ for (Expression mapped : child.mapping) {
+ appendExpressionKey(out, mapped, mode);
+ }
+ appendShapeKey(out, child.node, mode);
+ }
+ }
+
+ /**
+ * The identity of a scan, one field at a time: a table name which carries
the characters of the
+ * printed token ({@code #ti:}, a comma) cannot stand for another field
because each field has its own
+ * length here.
+ */
+ private static void appendScanKey(ShapeKeyWriter out, HboScanDescriptor
descriptor) {
+ out.text(descriptor.getTable());
+ out.number(descriptor.getTableId());
+ out.text(descriptor.getRelationIdentity());
+ out.text(descriptor.getPartitionIdentity());
+ out.text(descriptor.getTabletIdentity());
+ out.text(descriptor.getIndexIdentity());
+ }
+
+ /**
+ * The key of one expression: its kind, the fields which define its value
(a literal's type and
+ * value, a slot's qualifier) and its children, every one of them length
prefixed. The display form
+ * of an expression is not used here: a value which carries the characters
of that form cannot stand
+ * for a field of the identity.
+ */
+ private static void appendExpressionKey(ShapeKeyWriter out, Expression
expression, LiteralMode mode) {
+ String name = expression.getClass().getSimpleName();
+ out.text(name.isEmpty() ? expression.getClass().getName() : name);
+ List<Expression> children = expression.children();
Review Comment:
[P2] Preserve DISTINCT in set-operation mapping keys
With `agg_phase=3`, compare `SELECT COUNT(v) AS x FROM t GROUP BY k UNION
SELECT x FROM u` with `COUNT(DISTINCT v)` in its first branch (`u.x` is
BIGINT). `BuildAggForUnion` produces the reduced tree:
```text
Aggregate(gb=x)
UnionAll
Aggregate(gb=k, Count(v) AS x) -> Scan(t)
Scan(u), mapping u.x
```
The DISTINCT variant keeps this logical shape, but this encoder writes only
`Count` and its child, omitting `isDistinct()`. The child aggregate key
contains only k, so both actual fingerprints collide in both modes. For
t={(1,1),(1,1)} and u.x={1}, the UNION has two versus one rows; identical scan
baselines accept the other query's pinned count. Encode the semantic fields
already handled by `expressionName` in this binary path and cover mapped
DISTINCT aggregates. Unlike the existing cast/order text-normalization and
aggregate-producer threads, the canonical text already distinguishes this pair;
the separate mapping hash loses that distinction.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/HboStatisticsStore.java:
##########
@@ -0,0 +1,295 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.stats;
+
+import org.apache.doris.catalog.Database;
+import org.apache.doris.catalog.Env;
+import org.apache.doris.catalog.TableIf;
+import org.apache.doris.common.Config;
+import org.apache.doris.common.FeConstants;
+import org.apache.doris.datasource.InternalCatalog;
+import org.apache.doris.statistics.repository.ResultRow;
+import org.apache.doris.statistics.util.StatisticsUtil;
+
+import com.google.common.collect.ImmutableList;
+import org.apache.logging.log4j.LogManager;
+import org.apache.logging.log4j.Logger;
+
+import java.nio.charset.StandardCharsets;
+import java.time.Instant;
+import java.time.LocalDateTime;
+import java.time.ZoneId;
+import java.time.format.DateTimeFormatter;
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Persistence of manually injected (pinned) hbo statistics into the internal
database
+ * ({@code __internal_schema.hbo_statistics}), controlled by
+ * {@code Config.hbo_persist_pinned_to_internal_db}.
+ *
+ * <p>The in-memory {@link HboPlanStatisticsManager} stays authoritative on
the read path;
+ * SET/DELETE are written through synchronously (best effort, failures only
logged) and a FE
+ * loads the whole table into memory lazily on first use, so pinned entries
survive a FE
+ * restart. All FEs share the table through the backend storage.
+ */
+public class HboStatisticsStore {
+ private static final Logger LOG =
LogManager.getLogger(HboStatisticsStore.class);
+
+ private static final String INTERNAL_DB = FeConstants.INTERNAL_DB_NAME;
+ private static final String TABLE = "hbo_statistics";
+ private static final String FULL_QUALIFIED =
+ InternalCatalog.INTERNAL_CATALOG_NAME + "." + INTERNAL_DB + "." +
TABLE;
+ /** max length (bytes) of the struct_info varchar column */
+ private static final int STRUCT_MAX_BYTES = 65533;
+
+ /** creation time of an entry, as a datetime(3) column like the other
internal tables */
+ private static final String CREATE_TIME_COLUMN = "create_time";
+ /** fan-out factor of a PinnedType.JOIN_EXPANSION entry, NULL for a row
count entry */
+ private static final String EXPANSION_COLUMN = "expansion";
+ /** which struct info the entry is keyed by (with_literal / no_literal) */
+ private static final String LITERAL_MODE_COLUMN = "literal_mode";
+ /** the columns this version writes and reads, checked once per FE (see
verifySchema) */
+ private static final List<String> COLUMNS =
ImmutableList.of("fingerprint", "row_count", "stats_type",
+ LITERAL_MODE_COLUMN, "struct_info", EXPANSION_COLUMN,
CREATE_TIME_COLUMN);
+ // the DDL and the schema check are done once per FE: the table can only
change by a FE upgrade,
+ // and both cost a round trip to the internal table (a forwarded DDL on a
follower FE)
+ private static volatile boolean tableCreated = false;
+ private static volatile boolean schemaVerified = false;
+
+ private HboStatisticsStore() {
+ }
+
+ /**
+ * Whether a canonical struct info fits the {@code struct_info} column
without truncation.
+ * A truncated struct info would keep its fingerprint but lose its scan
tokens (the baseline is
+ * printed after the conditions), which silently disables both the
freshness verdict and the
+ * relation pre filter for that entry, so such an entry must not be
accepted at all.
+ */
+ public static boolean fitsStructColumn(String structCanonical) {
+ return structCanonical == null
+ ||
structCanonical.getBytes(java.nio.charset.StandardCharsets.UTF_8).length <=
STRUCT_MAX_BYTES;
+ }
+
+ /** Create the table if it does not exist, and check that its schema is
the current one. */
+ public static void ensureTable() throws Exception {
+ if (!tableCreated) {
+ StatisticsUtil.execUpdate(createDdl());
+ tableCreated = true;
+ }
+ if (!schemaVerified) {
+ verifySchema();
+ }
+ }
+
+ /**
+ * Check that the table has every column this version reads and writes, by
looking at its metadata
+ * in the FE catalog. A query would be cheaper to write but wrong to
interpret: it fails both when
+ * the table has an old schema and when the internal schema is simply not
ready yet, and the two
+ * need opposite reactions (drop the table vs wait).
+ *
+ * <p>A table created by an older FE version (e.g. with a {@code
create_time_ms} column) cannot be
+ * written by this version, and because it is created with {@code CREATE
TABLE IF NOT EXISTS} it
+ * stays broken; the check therefore logs the fix and forgets that the
table was "created", so
+ * that the DDL runs again - and recreates the table - after the operator
dropped it. Without
+ * that, persistence would stay dead until the FE restarts.
+ */
+ private static void verifySchema() throws Exception {
+ Database db =
Env.getCurrentEnv().getInternalCatalog().getDbNullable(INTERNAL_DB);
+ TableIf table = db == null ? null : db.getTableNullable(TABLE);
+ if (table == null) {
+ // the DDL succeeded but the table is not visible yet (a follower
waiting for the journal,
+ // or an internal schema which is not ready): retry later, do not
blame the table
+ throw new IllegalStateException("the internal table " +
FULL_QUALIFIED + " is not visible yet");
+ }
+ List<String> missing = new ArrayList<>();
+ for (String column : COLUMNS) {
+ if (table.getColumn(column) == null) {
+ missing.add(column);
+ }
+ }
+ if (!missing.isEmpty()) {
+ tableCreated = false;
+ LOG.warn("the internal table {} has no {} column: it was created
by an older FE version and"
+ + " has to be dropped so that it is recreated (DROP TABLE
{})",
+ FULL_QUALIFIED, missing, FULL_QUALIFIED);
+ throw new IllegalStateException("the internal table " +
FULL_QUALIFIED + " has an old schema");
+ }
+ schemaVerified = true;
+ }
+
+ /**
+ * Upsert one pinned entry (UNIQUE KEY fingerprint replaces on conflict).
+ */
+ public static boolean persist(String fingerprint, long rows,
+ HboPlanStatisticsManager.PinnedType type, String structCanonical,
double expansion,
+ HboPlanStatisticsManager.LiteralMode literalMode, long
createTimeMs) {
+ try {
+ ensureTable();
+ HboPlanStatisticsManager.PinnedType statsType = type == null
+ ? HboPlanStatisticsManager.PinnedType.EXACT : type;
+ // an empty struct_info records no data state: the freshness
comparison reports unknown for such
+ // an entry and the pinned lookup index has no relation key for
it, which is why the pinned scope
+ // of HBO SET requires the canonical string (see
HboStatisticsCommand)
+ String struct = truncateUtf8(structCanonical == null ? "" :
structCanonical, STRUCT_MAX_BYTES);
+ // the fingerprint kind is only known after the entry was applied
once, so the stored
+ // value stays UNKNOWN (it is reported by HBO SHOW from the
in-memory entry)
+ String sql = "INSERT INTO " + FULL_QUALIFIED
+ + " (`fingerprint`, `row_count`, `stats_type`, `" +
LITERAL_MODE_COLUMN + "`, `struct_info`,"
+ + " `" + EXPANSION_COLUMN + "`, `" + CREATE_TIME_COLUMN +
"`) VALUES ('"
+ + StatisticsUtil.escapeSQL(fingerprint) + "', " + rows +
", '"
+ +
StatisticsUtil.escapeSQL(statsType.name().toLowerCase(java.util.Locale.ROOT)) +
"', '"
+ + StatisticsUtil.escapeSQL((literalMode == null
+ ? HboPlanStatisticsManager.LiteralMode.NO_LITERAL
: literalMode)
+ .name().toLowerCase(java.util.Locale.ROOT))
+ + "', '" + StatisticsUtil.escapeSQL(struct) + "', "
+ + (expansion > 0 ? String.valueOf(expansion) : "NULL")
+ + ", '" + createTimeLiteral(createTimeMs) + "')";
+ StatisticsUtil.execUpdate(sql);
+ return true;
+ } catch (Exception t) {
+ LOG.warn("failed to persist hbo pinned statistics for fingerprint
{}", fingerprint, t);
+ return false;
+ }
+ }
+
+ /**
+ * Remove the pinned entry of a fingerprint.
+ *
+ * @return true when the row was removed (or the table had no such row),
false when the removal
+ * failed (e.g. the internal schema is not ready yet); the caller
reports the failure
+ */
+ public static boolean delete(String fingerprint) {
+ try {
+ ensureTable();
+ // the entry of this fingerprint is removed: the caller only drops
its in-memory copy after
+ // this returns true, and reports the failure to the user otherwise
+ String sql = "DELETE FROM " + FULL_QUALIFIED + " WHERE
`fingerprint` = '"
+ + StatisticsUtil.escapeSQL(fingerprint) + "'";
+ StatisticsUtil.execUpdate(sql);
Review Comment:
[P2] Wait for deletion visibility before completing the pending load
`execUpdate` also succeeds when DELETE returns SQL OK with `COMMITTED` after
its publish timeout (`DeleteJob.commit`; the MOW insert path does too by
default). If this FE's one-time load is still pending after startup/retry,
DELETE then invalidates the cache and acknowledges success, but the subsequent
`loadAll` can still read the old visible row. `ensurePinnedLoaded` reinstalls
it and marks the load complete, so the deleted override stays active even after
publication removes the stored row. Wait for VISIBLE or preserve deletion state
across that pending load; the FE-local lock alone does not establish SQL
visibility. This needs neither another FE/replacement nor a caught SQL error,
unlike the existing persistence threads.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/HboPlanStatisticsManager.java:
##########
@@ -38,4 +177,431 @@ public HboPlanStatisticsProvider
getHboPlanStatisticsProvider() {
public HboPlanInfoProvider getHboPlanInfoProvider() {
return hboPlanInfoProvider;
}
+
+ /**
+ * Inject (or overwrite) a pinned statistics entry applied unconditionally.
+ * @param fingerprint hbo fingerprint (simplified group struct info sha256)
+ * @param rows output row count that overrides the optimizer estimation
+ * @param structCanonical optional human-readable simplified struct info
canonical string
+ */
+ public void putPinnedPlanStatistics(String fingerprint, long rows, String
structCanonical) {
+ putPinnedPlanStatistics(fingerprint, rows, PinnedType.EXACT,
structCanonical, LiteralMode.NO_LITERAL);
+ }
+
+ /**
+ * Inject (or overwrite) a pinned statistics entry.
+ * @param type how the injected row count is applied (unconditional vs
filter-small guard)
+ * @param structCanonical optional human-readable simplified struct info
canonical string
+ */
+ public void putPinnedPlanStatistics(String fingerprint, long rows,
PinnedType type, String structCanonical,
+ LiteralMode literalMode) {
+ putPinnedStatistics(fingerprint, rows, type, structCanonical, 0,
literalMode);
+ }
+
+ /**
+ * Inject (or overwrite) a pinned statistics entry.
+ *
+ * @param expansion fan-out factor, only for {@link
PinnedType#JOIN_EXPANSION} entries
+ */
+ private void putPinnedStatistics(String fingerprint, long rows, PinnedType
type, String structCanonical,
+ double expansion, LiteralMode literalMode) {
+ // LRU bounded by Config.hbo_pinned_stats_cache_num; pinned entries
are otherwise never
+ // expired automatically and are only removed by HBO DELETE STATISTICS
or eviction
+ long createTimeMs = System.currentTimeMillis();
+ synchronized (pinnedLoadLock) {
+ // the stored row is written first: when the write fails the
statement fails and the entry
+ // is not pinned, so an entry which only lives in memory (and
disappears on a restart)
+ // cannot be reported as set
+ if (persistenceEnabled() &&
!HboStatisticsStore.persist(fingerprint, rows, type, structCanonical,
+ expansion, literalMode, createTimeMs)) {
+ throw new IllegalStateException("failed to persist the hbo
statistics entry " + fingerprint
+ + " into the internal table, see the FE log; the entry
was not set");
+ }
+ pinnedPlanStatistics.put(fingerprint,
+ new PinnedHboStatistics(fingerprint, rows, type,
structCanonical, expansion, literalMode,
+ createTimeMs));
+ if (type != PinnedType.JOIN_EXPANSION) {
+ // only row count entries are looked up by relation key: a
join expansion entry is
+ // keyed by the join conditions, is rejected by
getPinnedPlanStatistics, and its
+ // scanless canonical would turn the pre filter into a no-op
for every group
+ registerRelationKey(structCanonical);
+ }
+ }
+ }
+
+ /**
+ * The pinned row-count entry of a sub tree. Entries of another kind (a
join expansion factor
+ * keyed by the join conditions) are never returned here, so the two read
paths can not pick up
+ * each other's entry.
+ *
+ * <p>This is the planning hot path, so it only reads the in-memory cache:
the persisted entries
+ * of this FE are loaded by {@link HboPinnedStatisticsLoader} in the
background. Doing it here
+ * would run a DDL and a full table scan on a user query's planning
thread, and the internal
+ * statement it runs would re-enter this manager (see the class javadoc).
+ */
+ public Optional<PinnedHboStatistics> getPinnedPlanStatistics(String
fingerprint) {
+ return
Optional.ofNullable(pinnedPlanStatistics.getIfPresent(fingerprint))
+ .filter(pinned -> !pinned.isExpansion());
+ }
+
+ /**
+ * Whether this FE holds any pinned entry at all (of any kind). The
planning path looks an entry
+ * up by the hbo fingerprint of a plan node, and that fingerprint is
expensive to build (a whole
+ * memo subtree traversal); an empty cache means every such lookup is a
guaranteed miss, so the
+ * caller can skip building the fingerprint. Like {@link
#getPinnedPlanStatistics(String)} this
+ * only reads the in-memory cache and never triggers the background loader.
+ */
+ public boolean hasAnyPinnedStatistics() {
+ return !pinnedPlanStatistics.asMap().isEmpty();
+ }
+
+ /**
+ * Whether a pinned entry could possibly apply to a sub tree which reads
exactly {@code
+ * relationKey} (see {@link
GroupStructInfo.HboStructSummary#getRelationKey()}).
+ *
+ * <p>An entry is keyed by the fingerprint of its struct info, and two
equal struct infos
+ * necessarily read the same tables, so an entry whose relation key
differs can not match: the
+ * caller can skip building the (expensive) fingerprint. The index is an
over approximation -
+ * keys are only ever added, so a removed or evicted entry may keep its
key - which can only make
+ * a lookup happen, never suppress one.
+ */
+ public boolean mayHavePinnedEntryForRelations(String relationKey) {
+ return pinnedEntriesWithoutRelationKey.get() > 0 ||
pinnedRelationKeys.contains(relationKey);
+ }
+
+ /** Register the relation key of an entry's struct info in the lookup
index. */
+ private void registerRelationKey(String structCanonical) {
+ List<HboScanDescriptor> scans =
HboScanDescriptor.parseAll(structCanonical);
+ if (scans.isEmpty()) {
+ // an entry which records no scan at all can not be filtered by a
relation key
+ pinnedEntriesWithoutRelationKey.incrementAndGet();
+ return;
+ }
+ List<String> tables = new ArrayList<>(scans.size());
+ for (HboScanDescriptor scan : scans) {
+ tables.add(scan.getTable());
+ }
+ Collections.sort(tables);
+ pinnedRelationKeys.add(String.join(",", tables));
Review Comment:
[P3] Retire relation keys when pinned entries leave the cache
The pinned cache is bounded by `hbo_pinned_stats_cache_num` (5000 by
default), but this set only grows: successful DELETE, stale cleanup and
Caffeine eviction never remove relation keys. Repeated SET/DELETE for distinct
table combinations therefore retains one full table-list string per historical
combination for the lifetime of the FE, even when the pinned cache is empty.
Load likewise registers rows beyond the cache's eventual admission bound.
Bound/rebuild this index or track references from live entries so the
configured cache bound also bounds its retained metadata. This is separate from
the existing learned relation-table cache's hot-configuration issue.
--
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]
