englefly commented on code in PR #69322: URL: https://github.com/apache/doris/pull/69322#discussion_r4350200709
########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/GroupStructInfo.java: ########## @@ -0,0 +1,3158 @@ +// 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()); + break; + } + case GENERATE: { + StringBuilder header = new StringBuilder(); + appendGenerateHeader(header, node); + out.text(header.toString()); + break; + } + case REPEAT: { + StringBuilder header = new StringBuilder(); + appendRepeatHeader(header, node, mode); + out.text(header.toString()); + 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) { + out.text(renderExpression(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 header fields of a set operation, which decide which rows its branches combine. */ + private static void appendSetOperationKey(ShapeKeyWriter out, Node node) { + SetOperation setOperation = node.setOperation; + out.text(node.setOperationPlan instanceof Union ? "U" + : node.setOperationPlan instanceof Intersect ? "I" : "E"); + out.text(String.valueOf(setOperation.getQualifier()).toLowerCase(Locale.ROOT)); + out.count(setOperation.getOutputs().size()); + for (NamedExpression output : setOperation.getOutputs()) { + out.text(identityText(output)); + } + List<List<NamedExpression>> constantExprsList = setOperation instanceof Union + ? ((Union) setOperation).getConstantExprsList() : Collections.emptyList(); + out.count(constantExprsList.size()); + for (List<NamedExpression> branch : constantExprsList) { + out.count(branch.size()); + for (NamedExpression constant : branch) { + out.text(identityText(constant)); + } + } + } + + /** + * 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); + if (hasNoHboLookupPath(planNode, group)) { + return Optional.empty(); + } + 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) { + Group group = resolveGroup(planNode, groupsById); + if (hasNoHboLookupPath(planNode, group)) { + return Optional.empty(); + } + return fingerprintOfGroup(group, 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) { + Group group = resolveGroup(planNode, groupsById); + if (hasNoHboLookupPath(planNode, group)) { + // the annotation asks for the struct info first: without this guard the node would advertise + // a key which no read path ever looks up (see hasNoHboLookupPath) + return Optional.empty(); + } + return structInfoOfGroup(group); + } + + 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) { + return describeGroup(group); + } + + public static GroupStructInfo describeGroup(Group group) { + return describeGroup(group, new Ctx()); + } + + private static GroupStructInfo describeGroup(Group group, Ctx ctx) { + if (!ctx.visited.add(group)) { + // the same group is reached twice (a CTE which is consumed twice, a scan which feeds two + // consumers, a shared sub tree): a tree cannot express the reuse, so the sub tree is + // described again - the description is the one of a plan which writes that sub tree twice + // (a self join for instance), and the read side of a query builds the same description, so + // an entry recorded from one form applies to the other. The sub tree was read once, so the + // repeated reference composes its canonical form but not its scans again (the drift guard + // compares the scan states of the tables a query actually reads). + GroupStructInfo memoized = group.getHboStructInfoOrNull(); + if (memoized != null) { + return memoized; + } + invalid(ctx, "sharing=group " + group.getGroupId().asInt() + " reached twice"); + 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); + group.setHboStructInfo(computed); + return computed; + } + + /** + * The first logical expression of a group, or null when it holds none: {@link + * Group#getFirstLogicalExpression()} asserts that there is one, so a group which only holds + * physical expressions (an enforcer group, or a group a rule filled with physical plans) cannot be + * asked that way. + */ + private static GroupExpression firstLogicalExpression(Group group) { + List<GroupExpression> logical = group.getLogicalExpressions(); + return logical.isEmpty() ? null : logical.get(0); + } + + /** Why a group has nothing to describe: its chosen id and how many expressions it holds. */ + private static String describeGroupState(Group group) { + return group.getGroupId().asInt() + + " (logical=" + group.getLogicalExpressions().size() + + ", physical=" + group.getPhysicalExpressions().size() + + ", enforcers=" + group.getEnforcers().size() + ")"; + } + + /** + * The expression which is described for a group. The first logical expression is used, and the logical + * form is what the key of a group has to be made of: the read side looks an entry up while the plan is + * still being optimized, i.e. before any expression is chosen, and a physical plan may hold nodes the + * logical plan abstracts away (the two staged aggregation of a {@code count(*)}, for instance), which + * would move the key of every such group and make a pinned entry miss. The expression the plan chooser + * picked is deliberately not consulted for the same reason - a key must not depend on when it is + * computed. The method is package visible so that a test can pin that the recorded choice of the plan + * chooser is not consulted. + */ + static GroupExpression getRepresentativeExpression(Group group) { + GroupExpression logical = firstLogicalExpression(group); + if (logical != null) { + return logical; + } + // Some groups have no logical plan at all, for instance the group of a + // {@link PhysicalStorageLayerAggregate} (an aggregation answered from the storage layer is a + // catalog relation a rule inserts, there is no logical aggregation left to describe) or a group + // which only holds an enforcer. Such a group is described through the physical expression it + // holds: it is the only form it has, so both sides - the read side and the annotation - see the + // same one, and giving the whole struct info up would hide every node above it. + List<GroupExpression> physical = group.getPhysicalExpressions(); + if (!physical.isEmpty()) { + return physical.get(0); + } + // an enforcer group keeps its expression in the enforcer list, not among the physical ones + return group.getEnforcers().isEmpty() ? null : group.getEnforcers().keySet().iterator().next(); + } + + /** + * 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) { + describedGroupCount.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); + } + GroupExpression logical = firstLogicalExpression(group); + if (logical != null) { + return describeExpression(group, logical, ctx); + } + GroupExpression representative = getRepresentativeExpression(group); + if (representative == null) { + // a group without any expression (no logical one, no physical one, no enforcer): there is + // nothing to describe + return invalidStructInfo("no expression in group " + describeGroupState(group)); + } + return describeExpression(group, representative, ctx); + } + + /** Describe one expression of a group: the body of {@link #build} without the choice of it. */ + private static GroupStructInfo describeExpression(Group group, GroupExpression ge, Ctx ctx) { + Node root; + try { + root = buildNode(ge.getPlan(), ge, ctx); + if (root != null) { + applyColumnDefinitions(ge.getPlan(), root); + } + } catch (RuntimeException e) { + // memo content which the simplified struct info cannot describe (an unexpected plan node, a + // cast of a named expression which is not the alias of a window expression): treat the group as + // invalid and fall back to the legacy behavior instead of failing the optimizer on the hot + // path. Rendering cannot throw for a description which was built: it only concatenates. + LOG.debug("failed to compute hbo struct info for group {}", group.getGroupId(), e); + return invalidStructInfo(ctx.reason); + } + if (!ctx.valid || root == null) { + return invalidStructInfo(ctx.reason); + } + return ofNode(root); + } + + /** + * Bind the columns the children of a node compute to the expression which produces them, and + * substitute a reference to such a column in the expressions of this node. + * + * <p>A project is transparent for structure matching and an aggregation keeps only its grouping + * keys in its header, so a column whose value they compute is <em>named</em> by every node above + * them and <em>defined</em> by none: {@code Aggregate(group by x) -> Project(a % 2 AS x) -> + * Scan(t)} and the same plan with {@code % 3} render one {@code A{gb:col(x)}} although their group + * counts differ, and a pinned row count of one is then applied to the other. The definition is + * therefore carried up: the expressions of this node are rewritten so that a column defined by a + * child renders as the expression which computes it, and the map is handed to the nodes above. + */ + private static void applyColumnDefinitions(Plan plan, Node node) { + Map<ExprId, Expression> childDefinitions = childColumnDefinitions(node); + resolveNodeExpressions(node, childDefinitions); + if (plan instanceof Project) { + node.columnDefinitions = projectColumnDefinitions((Project) plan, childDefinitions); + } else if (plan instanceof Aggregate) { + node.columnDefinitions = aggregateColumnDefinitions((Aggregate<?>) plan, childDefinitions); + } else { + node.columnDefinitions = childDefinitions; + } + } + + /** + * The columns an aggregation computes. Its header keeps the grouping keys - the number of groups, + * which is the row count of the node, depends on them alone - so the values its aggregate + * functions produce are defined nowhere: {@code Filter(s = 1) -> Aggregate(group by k, MIN(v) AS + * s)} and the same tree with {@code MAX(v) AS s} render one filter key although one k group whose + * values are 1 and 2 keeps zero and one rows. A definition is the aggregate function under the + * name of the alias which exposes it, resolved against the columns of the child like the header of + * the aggregation itself. + */ + private static Map<ExprId, Expression> aggregateColumnDefinitions(Aggregate<?> aggregate, + Map<ExprId, Expression> childDefinitions) { + Map<ExprId, Expression> definitions = new LinkedHashMap<>(); + for (NamedExpression output : aggregate.getOutputExpressions()) { + if (output instanceof Alias) { + definitions.put(output.getExprId(), + resolveColumnDefinitions(((Alias) output).child(), childDefinitions)); + } + } + return Collections.unmodifiableMap(definitions); + } + + /** + * The definitions the children of a node expose. A join forwards the columns of both sides, but a + * side an outer join null-extends does not forward the value it computed: for the rows the join does + * not match, the whole side is NULL, and a definition which can turn NULL into a non-NULL value + * (a coalesce, an `is null`, a udf, ...) therefore has a different value above the join. Such a + * definition is wrapped with the id of the boundary it crossed (see {@link NullExtended}). + */ + private static Map<ExprId, Expression> childColumnDefinitions(Node node) { + if (node.children.size() == 1) { + return node.children.get(0).node.columnDefinitions; + } + if (node.children.isEmpty()) { + return Collections.emptyMap(); + } + Map<ExprId, Expression> definitions = new LinkedHashMap<>(); + for (int index = 0; index < node.children.size(); index++) { + boolean nullExtended = isNullExtendedSide(node, index); + Map<ExprId, Expression> childDefinitions = node.children.get(index).node.columnDefinitions; + for (Map.Entry<ExprId, Expression> definition : childDefinitions.entrySet()) { + Expression expression = definition.getValue(); + definitions.put(definition.getKey(), nullExtended + && canConvertNullToNonNull(expression) + ? new NullExtended(node.nullExtensionBoundaryId, expression) + : expression); + } + } + return Collections.unmodifiableMap(definitions); + } + + /** Whether a join null-extends the columns of the given child. */ + private static boolean isNullExtendedSide(Node node, int index) { + if (node.kind != Kind.JOIN || node.flattenable || node.nullExtensionBoundaryId < 0) { + return false; + } + switch (node.joinType) { + case LEFT_OUTER_JOIN: + return index == 1; + case RIGHT_OUTER_JOIN: + return index == 0; + case FULL_OUTER_JOIN: + return true; + default: + return false; + } + } + + /** + * Whether an expression can turn a NULL input into a non-NULL value, which is what makes the value it + * computes different above a null-extension boundary (the same classification the outer join push + * down uses, extended over the whole tree: a composite expression is affected when any part of it is, + * and a udf is treated conservatively because its null behaviour is unknown). + */ + private static boolean canConvertNullToNonNull(Expression expression) { + if (expression instanceof NullToNonNullFunction || expression instanceof Udf) { + return true; + } + for (Expression child : expression.children()) { + if (canConvertNullToNonNull(child)) { + return true; + } + } + return false; + } + + /** + * A definition which crossed a null extension: the value it denotes is NULL for the rows the join did + * not match, whatever the wrapped expression computes, so the expression alone would name the same + * value for both plans. The id names the boundary (see Node#nullExtensionBoundaryId). + */ + private static final class NullExtended extends Expression { + private final int boundaryId; + private final Expression child; + + private NullExtended(int boundaryId, Expression child) { + this.boundaryId = boundaryId; + this.child = child; + } + + @Override + public List<Expression> children() { + return Collections.singletonList(child); + } + + @Override + public NullExtended withChildren(List<Expression> children) { + return children.size() == 1 && children.get(0) == child + ? this : new NullExtended(boundaryId, children.get(0)); + } + + @Override + public boolean nullable() { + return true; + } + + @Override + public DataType getDataType() { + return child.getDataType(); + } + + @Override + public <R, C> R accept(ExpressionVisitor<R, C> visitor, C context) { + return visitor.visit(this, context); + } + } + + /** + * The columns a project computes: an alias names the expression it wraps, and that expression is + * the value a node above the project reads. A plain slot of the projection is a forwarded column, + * which keeps the definition it already had below the project (a project of plain slots over a + * project of aliases forwards exactly those definitions). + */ + private static Map<ExprId, Expression> projectColumnDefinitions(Project project, + Map<ExprId, Expression> childDefinitions) { + Map<ExprId, Expression> definitions = new LinkedHashMap<>(); + for (NamedExpression output : project.getProjects()) { + if (output instanceof Alias) { + definitions.put(output.getExprId(), + resolveColumnDefinitions(((Alias) output).child(), childDefinitions)); + } else if (childDefinitions.containsKey(output.getExprId())) { + definitions.put(output.getExprId(), childDefinitions.get(output.getExprId())); + } + } + return Collections.unmodifiableMap(definitions); + } + + /** Substitute every reference to a defined column with the expression which computes it. */ + private static Expression resolveColumnDefinitions(Expression expression, + Map<ExprId, Expression> definitions) { + if (definitions.isEmpty()) { + return expression; + } + return expression.rewriteUp(rewritten -> { + if (!(rewritten instanceof Slot)) { + return rewritten; + } + Expression definition = definitions.get(((Slot) rewritten).getExprId()); + return definition == null ? rewritten : definition; + }); + } + + private static List<Expression> resolveColumnDefinitions(List<Expression> expressions, + Map<ExprId, Expression> definitions) { + if (definitions.isEmpty()) { + return expressions; + } + List<Expression> resolved = new ArrayList<>(expressions.size()); + for (Expression expression : expressions) { + resolved.add(resolveColumnDefinitions(expression, definitions)); + } + return resolved; + } + + /** Rewrite the expressions a node keeps, in place: they are rendered exactly once, later. */ + private static void resolveNodeExpressions(Node node, Map<ExprId, Expression> definitions) { + if (definitions.isEmpty()) { + return; + } + if (node.conditions != null) { + node.conditions = resolveColumnDefinitions(node.conditions, definitions); + } + if (node.orderKeys != null) { + List<OrderKey> orderKeys = new ArrayList<>(node.orderKeys.size()); + for (OrderKey orderKey : node.orderKeys) { + orderKeys.add(orderKey.withExpression( + resolveColumnDefinitions(orderKey.getExpr(), definitions))); + } + node.orderKeys = orderKeys; + } + if (node.windowExpressions != null) { + List<NamedExpression> windowExpressions = new ArrayList<>(node.windowExpressions.size()); + for (NamedExpression windowExpression : node.windowExpressions) { + windowExpressions.add((NamedExpression) + resolveColumnDefinitions(windowExpression, definitions)); + } + node.windowExpressions = windowExpressions; + } + if (node.generators != null) { + node.generators = resolveColumnDefinitions(node.generators, definitions); + } + if (node.generatorConjuncts != null) { + node.generatorConjuncts = resolveColumnDefinitions(node.generatorConjuncts, definitions); + } + if (node.groupingSets != null) { + List<List<Expression>> groupingSets = new ArrayList<>(node.groupingSets.size()); + for (List<Expression> groupingSet : node.groupingSets) { + groupingSets.add(resolveColumnDefinitions(groupingSet, definitions)); + } + node.groupingSets = groupingSets; + } + } + + /** 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; + } + + /** + * Step 1 of a node build: describe one child of this node. The child is described once per query - + * its memoized description is returned - and a child which cannot be described invalidates this + * node with the reason of the child, so that the first reason of the failing sub tree is the one + * which is reported. + */ + private static GroupStructInfo describeChild(GroupExpression ge, int index, Ctx ctx) { + if (!ctx.valid) { + return null; + } + GroupStructInfo child = describeGroup(ge.child(index), ctx); + if (!child.isValid()) { + invalid(ctx, child.getSkipReason()); + return null; + } + return child; + } + + /** + * The conditions and the leaves of a join chain, memoized per group: a chain of n joins used to walk + * its own sub tree once per member (O(n^2) condition renderings for the whole query), while the + * structure of a chain does not depend on the build which reads it - only the bookkeeping of a sub + * tree which is reached more than once does, and that is done while composing the chain. + */ + public static final class ChainInfo { + /** the conditions of the chain, de-duplicated by their literal carrying text */ + private final List<Expression> conditions; + /** the groups the chain is made of, without its leaves: they detect a chain which is reused */ + private final List<Group> members; + /** the groups which are not flattened into the chain, in traversal order */ + private final List<Group> leaves; + private final boolean valid; + private final String skipReason; + + private ChainInfo(List<Expression> conditions, List<Group> members, List<Group> leaves, + boolean valid, String skipReason) { + this.conditions = conditions; + this.members = members; + this.leaves = leaves; + this.valid = valid; + this.skipReason = skipReason; + } + + private static ChainInfo of(List<Expression> conditions, List<Group> members, List<Group> leaves) { + return new ChainInfo(conditions, members, leaves, true, ""); + } + + private static ChainInfo failed(String skipReason) { + return new ChainInfo(new ArrayList<>(), new ArrayList<>(), new ArrayList<>(), false, skipReason); + } + } + + /** The memoized chain info of a group, computed at most once per query. */ + private static ChainInfo chainInfoOf(Group group) { + ChainInfo memoized = group.getHboChainInfoOrNull(); + if (memoized != null) { + return memoized; + } + ChainInfo computed = buildChainInfo(group); + group.setHboChainInfo(computed); + return computed; + } + + /** + * The chain structure of a group: a flattenable join contributes its own conditions and the chains + * of its children, a transparent operator contributes the chain below it, anything else is a leaf. + */ + private static ChainInfo buildChainInfo(Group group) { + GroupExpression ge = getRepresentativeExpression(group); + if (ge == null) { + return ChainInfo.failed("no logical expression in group " + describeGroupState(group)); + } + Plan plan = ge.getPlan(); + if (plan instanceof Join && isFlattenableJoinType(((Join) plan).getJoinType())) { + List<Expression> conditions = joinConditions((Join) plan); + List<Group> members = new ArrayList<>(); + List<Group> leaves = new ArrayList<>(); + members.add(group); + for (int i = 0; i < ge.arity(); i++) { + ChainInfo child = chainInfoOf(ge.child(i)); + if (!child.valid) { + return ChainInfo.failed(child.skipReason); + } + mergeConditions(conditions, child.conditions); + members.addAll(child.members); + leaves.addAll(child.leaves); + } + return ChainInfo.of(conditions, members, leaves); + } + // a top-n must not be flattened into the chain although it is a sort: it keeps a bounded number + // of rows, so it is a boundary of the chain like a limit, and the ordering it keeps them by is + // part of the identity of every node above it. A window is a boundary as well: it keeps every + // row, but the values of the columns it computes depend on its definition, and a node above it + // reads those values. + // a top-n is a sort but must not be flattened (it keeps a bounded number of rows, so it is a + // boundary of the chain), and a window is neither a project nor a sort, so it reaches the leaf + // branch below without a negation which a cleanup could drop + // a project is transparent only while it forwards its columns: one which computes a value is a + // leaf, so that its definitions reach the conditions of the join above it (a flattened project + // would be skipped and its definitions would be lost) + if ((plan instanceof Sort && !(plan instanceof TopN) || isTransparentProject(plan)) && ge.arity() == 1) { + ChainInfo child = chainInfoOf(ge.child(0)); + if (!child.valid) { + return child; + } + List<Group> members = new ArrayList<>(); + members.add(group); + members.addAll(child.members); + return ChainInfo.of(child.conditions, members, child.leaves); + } + List<Group> leaves = new ArrayList<>(); + leaves.add(group); + return ChainInfo.of(new ArrayList<>(), new ArrayList<>(), leaves); + } + + /** + * Add the leaves of a chain to the leaves of the build which is being described: a sub tree which the + * build already reached contributes its canonical form again, but not its scans (its tables are read + * once), and a chain which is reused makes all of its leaves repeated. + */ + private static boolean composeChain(ChainInfo chain, List<Leaf> leaves, Ctx ctx) { + boolean firstUse = true; + for (Group member : chain.members) { + if (!ctx.visited.add(member)) { + firstUse = false; + } + } + for (Group group : chain.leaves) { + boolean repeated = !firstUse || !ctx.visited.add(group); + GroupStructInfo leaf = describeVisited(group, ctx); + if (!leaf.isValid()) { + invalid(ctx, leaf.getSkipReason()); + return false; + } + leaves.add(new Leaf(leaf, repeated)); + } + return true; + } + + /** One leaf of a flattened join chain: the memoized description of that sub tree. */ + private static class Leaf { + private final GroupStructInfo leaf; + /** whether the sub tree of this leaf is referenced by another leaf as well */ + private final boolean repeated; + + Leaf(GroupStructInfo leaf) { + this(leaf, false); + } + + Leaf(GroupStructInfo leaf, boolean repeated) { + this.leaf = leaf; + this.repeated = repeated; + } + + GroupStructInfo getLeaf() { + return leaf; + } + + boolean isRepeated() { + return repeated; + } + + /** The key the leaves of a chain are ordered by: the identity of the sub tree, no data state. */ + String sortKey() { + return leaf.getShape(LiteralMode.WITH_LITERAL); + } + } + + /** + * The conditions of a join as expressions, de-duplicated by their literal carrying text - the key the + * two per-mode string sets used. The rendering happens once per mode in + * {@link #conditions(List, LiteralMode)}, which sorts and de-duplicates each mode on its own, exactly + * like the two {@link TreeSet}s did. + */ + private static List<Expression> joinConditions(Join join) { + List<Expression> conditions = new ArrayList<>(); + addConditions(conditions, join.getHashJoinConjuncts()); + addConditions(conditions, join.getOtherJoinConjuncts()); + // a mark join carries its correlation condition in the mark conjuncts, and the translator turns + // them into the hash condition of the executed null aware join: they decide which rows the node + // keeps, so two mark joins which differ only in that condition must not share a key + addConditions(conditions, join.getMarkJoinConjuncts()); + return conditions; + } + + private static void addConditions(List<Expression> conditions, Collection<Expression> conjuncts) { + mergeConditions(conditions, new ArrayList<>(conjuncts)); + } + + /** Append the conditions which are not in {@code into} yet, keyed by their literal carrying text. */ + private static void mergeConditions(List<Expression> into, List<Expression> from) { + Set<String> seen = new HashSet<>(); + for (Expression condition : into) { + seen.add(identityText(condition)); + } + for (Expression condition : from) { + if (seen.add(identityText(condition))) { + into.add(condition); + } + } + } + + /** 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; + } + + // ------------------------------------------------------------------------------------------ + // the description of one group: a tree of nodes, and the one renderer of the grammar + // ------------------------------------------------------------------------------------------ + + /** What a node of a description is; {@link #appendNode} switches on it. */ + private enum Kind { + SCAN("", false), + FILE_SCAN("", false), + STORAGE_AGGREGATE("A", false), + FILTER("F", false), + // a grouping key can name a definition of the sub tree (the output of a computed project), and the + // literals of that definition decide the number of groups: folding them would let the learned count + // of `GROUP BY a % 2` (two groups) be reused for `GROUP BY a % 1000` (a thousand groups) + AGGREGATE("A", true), + // a join's residual conditions decide which rows the join keeps (a range bound, a function of both + // sides), so their literals are identity: the published and learned keys of a join must not fold + // `t.b > u.b + 1000` and `t.b > u.b + 1` into one entry + JOIN("J", true), + TOPN("T", true), + LIMIT("L", true), + WINDOW("W", true), + GENERATE("G", true), + REPEAT("R", false), + SET_OPERATION("UIE", true), + PASSTHROUGH("", false); + + /** The letters the renderer writes in front of the header of this kind (a set operation has three). */ + private final String headerLetters; + /** + * Whether the literals inside the header of this kind are part of its identity, which means the + * renderer writes them in both literal modes: a generator's delimiter decides how many rows a row + * expands into, a top-n's ordering and a window's definition decide which rows reach the node + * above, a set operation's constant and a limit bound decide the rows of the operation itself. + */ + private final boolean literalsAreIdentity; + + Kind(String headerLetters, boolean literalsAreIdentity) { + this.headerLetters = headerLetters; + this.literalsAreIdentity = literalsAreIdentity; + } + + private String headerLetters() { + return headerLetters; + } + + private boolean literalsAreIdentity() { + return literalsAreIdentity; + } + } + + /** + * One node of a description: the information of the group itself, held as objects (an expression + * list, a bound, an ordering, a scan descriptor, ...), plus the children it composes. Nothing is + * rendered while a node is built: {@link #appendNode} is the only place which knows the grammar, and + * it renders the literals in the mode the caller asks for, which is why a node has no "with literal" + * and "no literal" variant of its own. + */ + private static final class Node { + private final Kind kind; + /** FILTER / AGGREGATE / JOIN: the predicates, the grouping keys or the conjuncts. */ + private List<Expression> conditions; + /** JOIN: a flattened inner / cross join chain is rendered as `inner`, like a cross join. */ + private boolean flattenable; + /** + * JOIN: a mark join preserves every row of its left side and produces a marker column, while the + * same join type without the marker filters the unmatched rows: the two plans keep a different + * number of rows with the same conditions, so the flag is part of the identity. + */ + private boolean markJoin; + /** + * The id of the null extension this node introduces (an outer join which null-extends a side), -1 + * for every other node. The id is assigned in build order inside one description, so the consumer + * of a definition which crossed this node can name it; the description is memoized on the group, + * so the estimation path and the EXPLAIN path see the same ids. + */ + private int nullExtensionBoundaryId = -1; + /** JOIN: the type of a join which is not flattened. */ + private JoinType joinType; + /** TOPN / LIMIT: the bound. */ + private long limit; + private long offset; + /** TOPN: the ordering which decides which rows survive. */ + private List<OrderKey> orderKeys; + /** WINDOW: the named expressions of the window (each child is the window expression). */ + private List<NamedExpression> windowExpressions; + /** GENERATE: the table functions, whose arguments decide how many rows come out. */ + private List<Expression> generators; + /** GENERATE: the aliases of the columns those functions produce, in order. */ + private List<Slot> generatorOutputs; + /** GENERATE: the lateral ON conditions, which decide which produced rows survive. */ + private List<Expression> generatorConjuncts; + /** REPEAT: the grouping sets, in the order they were written. */ + private List<List<Expression>> groupingSets; + /** SET_OPERATION: the plan node and the operation, which know the kind, the qualifier and more. */ + private Plan setOperationPlan; + private SetOperation setOperation; + /** SCAN / FILE_SCAN / STORAGE_AGGREGATE: the token of the relation which is read. */ + private HboScanDescriptor scan; + /** STORAGE_AGGREGATE: the pushed down aggregation. */ + private PhysicalStorageLayerAggregate storageAggregate; + /** + * The columns this node or a node below it computes, keyed by the id of the column which + * exposes the value: an alias of a transparent project and an output of an aggregation are + * the two definitions a node above them cannot see in the canonical form of its children. + */ + private Map<ExprId, Expression> columnDefinitions = Collections.emptyMap(); + /** The children, in the order the canonical string prints them. */ + private List<Child> children = new ArrayList<>(); + /** The rendered forms of this node, filled on the first request of each of them. */ + private String canonicalWithLiteral; + private String canonicalNoLiteral; + private String shapeWithLiteral; + private String shapeNoLiteral; + + private Node(Kind kind) { + this.kind = kind; + } + + private String materialized(LiteralMode mode, boolean shape) { + if (shape) { + return mode == LiteralMode.NO_LITERAL ? shapeNoLiteral : shapeWithLiteral; + } + return mode == LiteralMode.NO_LITERAL ? canonicalNoLiteral : canonicalWithLiteral; + } + + private void setMaterialized(LiteralMode mode, boolean shape, String text) { + if (shape) { + if (mode == LiteralMode.NO_LITERAL) { + shapeNoLiteral = text; + } else { + shapeWithLiteral = text; + } + return; + } + if (mode == LiteralMode.NO_LITERAL) { + canonicalNoLiteral = text; + } else { + canonicalWithLiteral = text; + } + } + } + + /** + * One child of a node: its description, and whether the sub tree is referenced by another child as + * well - such a child writes its canonical form again (a query which reuses a sub tree and a query + * which writes it twice share one entry) while its tables are read once, so its scan tokens are + * inherited by the first reference only. A set operation branch also writes the mapping of its + * columns, which is per parent and can therefore not live in the shared child node. + */ + private static final class Child { + private final Node node; + private final boolean repeated; + /** SET_OPERATION: the expressions the branch feeds its outputs with, empty for every other child. */ + private final List<Expression> mapping; + + private Child(Node node, boolean repeated) { + this(node, repeated, Collections.emptyList()); + } + + private Child(Node node, boolean repeated, List<Expression> mapping) { + this.node = node; + this.repeated = repeated; + this.mapping = mapping; + } + } + + // ---------------------------------------------------------------- build (memo level) + + /** + * Build the description of one node. Every branch follows the same three steps: the node's own + * information is collected as objects, its children are described by {@link #describeChild} (the + * memoized description of a child group, never its sub tree again), and both are put into a + * {@link Node} - the rendering happens later and elsewhere. + */ + private static Node buildNode(Plan plan, GroupExpression ge, Ctx ctx) { + if (!ctx.valid) { + return null; + } + // the order of the checks matters: a top-n is a sort and a window is neither a project nor a + // sort, so the boundaries of a join chain are recognised before the transparent operators + if (plan instanceof OlapScan) { + return olapScanNode((OlapScan) plan, ctx); + } + if (plan instanceof Filter) { + return conditionsNode(Kind.FILTER, ((Filter) plan).getConjuncts(), ge, ctx); + } + if (plan instanceof LogicalCTEConsumer || plan instanceof PhysicalCTEConsumer) { + // both consumers are leaves which reference their producer by id, and neither has a sub tree + // which this description could follow: the producer is reachable only from its anchor, and a + // group is described bottom-up (DeriveStatsJob, collectHboPlanInfo, the explain annotation), + // so the consumer side is visited before the anchor and no producer is known there yet. A plan + // which contains a consumer therefore stays undescribed - the same message for both classes, + // because the reason is the same. + return invalidNode("unsupported=cte consumer without a memo edge", ctx); + } + if (plan instanceof LogicalCTEProducer || plan instanceof PhysicalCTEProducer) { + // a producer materializes the sub tree it was given: transparent + if (ge.arity() != 1) { + return invalidNode(ARITY_REASON_PREFIX + ge.arity() + ARITY_REASON_MIDDLE + + plan.getClass().getSimpleName(), ctx); + } + return passthroughNode(ge, 0, ctx); + } + if (plan instanceof LogicalCTEAnchor || plan instanceof PhysicalCTEAnchor) { + // the value of an anchor is its consumer side: the producer is the first child and the plan + // which consumes it is the second one (LogicalCTEAnchor.computeOutput is right().getOutput()) + if (ge.arity() < 2) { + return invalidNode(ARITY_REASON_PREFIX + ge.arity() + ARITY_REASON_MIDDLE + + plan.getClass().getSimpleName(), ctx); + } + return passthroughNode(ge, 1, ctx); + } + if (plan instanceof LogicalFileScan) { + LogicalFileScan fileScan = (LogicalFileScan) plan; + return fileScanNode(fileScan.getTable(), HboScanDescriptor.relationIdentityOf(fileScan.getTableAlias()), + fileScan.getTableSnapshot().isPresent() || fileScan.getScanParams().isPresent() + || fileScan.getTableSample().isPresent(), ctx); + } + if (plan instanceof PhysicalFileScan) { + PhysicalFileScan fileScan = (PhysicalFileScan) plan; + return fileScanNode(fileScan.getTable(), HboScanDescriptor.relationIdentityOf(fileScan.getTableAlias()), + fileScan.getTableSnapshot().isPresent() || fileScan.getScanParams().isPresent(), ctx); + } + if (plan instanceof PhysicalStorageLayerAggregate) { + // the optimizer answers an aggregation over a scan from the storage layer itself: the node is + // a catalog relation without children, and its identity is the aggregation together with the + // relation it reads. The argument expressions are referenced by expression id there, which is + // not stable across queries, so they are left out: they do not change the number of rows this + // node produces (one row, the query has no grouping). + PhysicalStorageLayerAggregate aggregate = (PhysicalStorageLayerAggregate) plan; + Node node = new Node(Kind.STORAGE_AGGREGATE); + node.storageAggregate = aggregate; + if (aggregate.getRelation() instanceof OlapScan) { + node.scan = scanDescriptor((OlapScan) aggregate.getRelation(), ctx); + if (node.scan == null) { + return null; + } + } + return node; + } + if (plan instanceof TopN) { + if (ge.arity() != 1) { + return invalidNode(ARITY_REASON_PREFIX + ge.arity() + ARITY_REASON_MIDDLE + + plan.getClass().getSimpleName(), ctx); + } + // a top-n keeps its bound and its ordering out of the folding: the bound is written in both + // modes so that the constant agnostic form cannot fold two different bounds into one entry, + // and the ordering is part of the identity because it decides *which* rows survive + TopN topN = (TopN) plan; + Node node = new Node(Kind.TOPN); + node.limit = topN.getLimit(); + node.offset = topN.getOffset(); + node.orderKeys = new ArrayList<>(topN.getOrderKeys()); + node.children = children(ge, ctx, 0); + return node.children == null ? null : node; + } + if (plan instanceof Limit) { + if (ge.arity() != 1) { + return invalidNode(ARITY_REASON_PREFIX + ge.arity() + ARITY_REASON_MIDDLE + + plan.getClass().getSimpleName(), ctx); + } + Limit limit = (Limit) plan; + Node node = new Node(Kind.LIMIT); + node.limit = limit.getLimit(); + node.offset = limit.getOffset(); + node.children = children(ge, ctx, 0); + return node.children == null ? null : node; + } + if (plan instanceof Generate) { + if (ge.arity() != 1) { + return invalidNode(ARITY_REASON_PREFIX + ge.arity() + ARITY_REASON_MIDDLE + + plan.getClass().getSimpleName(), ctx); + } + // a generate expands a row into the rows of its table functions, so its identity is the + // identity of those functions: the function and its arguments decide how many rows come out, + // and the arguments are rendered with their literals (see identityText) + Node node = new Node(Kind.GENERATE); + node.generators = new ArrayList<>(((Generate) plan).getGenerators()); + node.generatorOutputs = generatorOutputsOf(plan); + node.generatorConjuncts = generatorConjunctsOf(plan); + node.children = children(ge, ctx, 0); + return node.children == null ? null : node; + } + if (plan instanceof Repeat) { + if (ge.arity() != 1) { + return invalidNode(ARITY_REASON_PREFIX + ge.arity() + ARITY_REASON_MIDDLE + + plan.getClass().getSimpleName(), ctx); + } + // a repeat produces the rows of several grouping sets, so its identity is the list of those + // sets; the order of the sets is part of the identity (the grouping id values depend on it) + // and is kept as written, while the expressions of one set are sorted (their order does not + // change the groups) + Node node = new Node(Kind.REPEAT); + node.groupingSets = new ArrayList<>(); + for (List<Expression> set : ((Repeat<?>) plan).getGroupingSets()) { + node.groupingSets.add(new ArrayList<>(set)); + } + node.children = children(ge, ctx, 0); + return node.children == null ? null : node; + } + if (plan instanceof Union || plan instanceof Intersect || plan instanceof Except) { + return setOperationNode(plan, (SetOperation) plan, ge, ctx); + } + if (plan instanceof PhysicalDistribute || plan instanceof PhysicalAssertNumRows + || plan instanceof Project || plan instanceof Sort) { + // an enforcer, a project and a sort are transparent for structure matching: none of them + // changes the number of rows, so the nodes above them are described by the shape below and + // they must not make the struct info of those nodes disappear + if (ge.arity() != 1) { + return invalidNode(ARITY_REASON_PREFIX + ge.arity() + ARITY_REASON_MIDDLE + + plan.getClass().getSimpleName(), ctx); + } + return passthroughNode(ge, 0, ctx); + } + if (plan instanceof Window) { + if (ge.arity() != 1) { + return invalidNode(ARITY_REASON_PREFIX + ge.arity() + ARITY_REASON_MIDDLE + + plan.getClass().getSimpleName(), ctx); + } + // a window computes its columns from the rows of its partition, so its definition decides the + // values a node above it reads and is part of the identity; the window itself adds no rows + Node node = new Node(Kind.WINDOW); + node.windowExpressions = new ArrayList<>(((Window) plan).getWindowExpressions()); + node.children = children(ge, ctx, 0); + return node.children == null ? null : node; + } + if (plan instanceof Join) { + return joinNode((Join) plan, ge, ctx); + } + if (plan instanceof Aggregate) { + // only the grouping keys 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 + return conditionsNode(Kind.AGGREGATE, ((Aggregate<?>) plan).getGroupByExpressions(), ge, ctx); + } + return invalidNode(UNSUPPORTED_REASON_PREFIX + plan.getClass().getSimpleName(), ctx); + } + + /** A filter or an aggregation: a header made of its conditions, then its single child. */ + private static Node conditionsNode(Kind kind, Collection<Expression> conditions, GroupExpression ge, + Ctx ctx) { + if (ge.arity() != 1) { + return invalidNode("arity=" + ge.arity() + " of " + ge.getPlan().getClass().getSimpleName(), ctx); + } + Node node = new Node(kind); + node.conditions = new ArrayList<>(conditions); + node.children = children(ge, ctx, 0); + return node.children == null ? null : node; + } + + /** + * A join. An inner or cross join is flattened together with every flattenable join below it into one + * node whose conditions are the merged conditions of the chain and whose children are the leaves of + * the chain (the first sub tree which is not part of it), while an outer / semi / anti / asof join + * keeps its type and the memo order of its two sides, because it cannot be reassociated. + */ + private static Node joinNode(Join join, GroupExpression ge, Ctx ctx) { + if (!isFlattenableJoinType(join.getJoinType())) { + Node node = new Node(Kind.JOIN); + node.joinType = join.getJoinType(); + node.markJoin = join.isMarkJoin(); + if (join.getJoinType().isOuterJoin()) { + node.nullExtensionBoundaryId = ctx.nextBoundaryId++; Review Comment: null-extension 使用 child-index 路径记录 null 生产者. 前面版本用 ctx 的 idGen 会产生不确定的编号 -- 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]
