github-actions[bot] commented on code in PR #67549: URL: https://github.com/apache/doris/pull/67549#discussion_r4320638790
########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/HboJoinConditions.java: ########## @@ -0,0 +1,131 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +package org.apache.doris.nereids.stats; + +import org.apache.doris.nereids.trees.expressions.EqualTo; +import org.apache.doris.nereids.trees.expressions.Expression; +import org.apache.doris.nereids.trees.expressions.NullSafeEqual; +import org.apache.doris.nereids.trees.expressions.Slot; +import org.apache.doris.nereids.trees.expressions.SlotReference; +import org.apache.doris.nereids.trees.plans.JoinType; +import org.apache.doris.nereids.trees.plans.Plan; +import org.apache.doris.nereids.trees.plans.algebra.Join; + +import com.google.common.hash.Hashing; + +import java.nio.charset.StandardCharsets; +import java.util.ArrayList; +import java.util.List; +import java.util.Optional; +import java.util.Set; +import java.util.TreeSet; + +/** + * Canonical description and fingerprint of the equality conditions of a join, used as the key of + * manually injected join expansion entries ({@code HBO SET EXPANSION}). + * + * <p>The join type and the residual (non equality) conditions take part in the key next to the hash + * (equality) conjuncts, because the injected factor replaces the output rows of the whole join: an + * inner join which matches nothing and a left outer join of the same columns produce very different + * row counts, and a selective residual predicate changes the output by orders of magnitude. The + * shape of both sub trees is still excluded, so one injected entry stays reusable by every query + * which joins the same columns with the same join type and the same residual conditions. + * + * <p>The canonical form is {@code JE{<join type>;EqualTo(...);...}} with the pairs and the residual + * conditions sorted; a pair is rendered by {@link GroupStructInfo#normalizeExpression(Expression)} + * which already sorts the two operands of an equality (equality is commutative), so {@code a = b} + * and {@code b = a} collapse. A residual condition is rendered with its literal in both modes, + * because it decides how many partner rows a row finds ({@code b > c + 1} is not {@code b > c + 2}). + */ +public class HboJoinConditions { + private static final String PREFIX = "JE{"; + private static final String SEP = ";"; + + private HboJoinConditions() { + } + + /** True when the injected expansion of this join type is applicable at all. */ + public static boolean isExpansionApplicable(JoinType joinType) { + // semi / anti / mark style joins can never produce more rows than their left input, and + // asof joins match at most one row per left row, so expansion can not happen there + return joinType == JoinType.INNER_JOIN + || joinType == JoinType.LEFT_OUTER_JOIN + || joinType == JoinType.RIGHT_OUTER_JOIN + || joinType == JoinType.FULL_OUTER_JOIN; + } + + /** + * Canonical string of the equality conditions, empty when the join has no equality condition + * (e.g. a cross join). A null safe equality ({@code <=>}) is a hash conjunct as well, so it + * takes part in the canonical like a plain equality. + */ + public static Optional<String> canonicalOf(Join join) { + List<String> pairs = new ArrayList<>(); + for (Expression conjunct : join.getHashJoinConjuncts()) { + if (conjunct instanceof EqualTo || conjunct instanceof NullSafeEqual) { + pairs.add(GroupStructInfo.normalizeExpression(conjunct)); Review Comment: [P2] Bind expansion operands to their underlying relations For the reduced trees `Join(x.a=y.a AND x.b<y.b, Scan(t AS x), Scan(u AS y))` and the same join over `Scan(u AS x), Scan(t AS y)`, these bare slot expressions retain identical x/y qualifiers. With 1000 copies of (a=1,b=1) in t and 1000 copies of (a=1,b=2) in u, the joins return 1000000 versus zero rows, yet both JE keys match. A factor of 1000 pinned for the first therefore gives the second an estimate of 1000000. The OLAP J key's new `#ra` fields do not participate in this separate lookup. Unlike the existing computed-key-producer report, every operand here is a bare scan slot; its missing identity is the table that the SQL alias names. Resolve JE operands to stable relation/column identities before normalizing them. ########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/HboUtils.java: ########## @@ -502,27 +548,77 @@ private static InputTableStatisticsInfo buildHboInputTableStatisticsInfo(Physica * @param planToIdMap planToIdMap * @param scanToFilterMap scanToFilterMap * @param curPlanNodeRuntimeStats curPlanNodeRuntimeStats + * @param nodeFingerprints snapshot of nereids plan node id -> hbo fingerprint taken during + * planning (only populated when the struct-info fingerprint is enabled) * @return plan statistics map */ public static Map<PlanNodeAndHash, PlanStatisticsWithInputInfo> genPlanStatisticsMap( Map<Integer, PhysicalPlan> idToPlanMap, Map<PhysicalPlan, Integer> planToIdMap, Map<RelationId, Set<Expression>> scanToFilterMap, - List<TPlanNodeRuntimeStatsItem> curPlanNodeRuntimeStats) { + List<TPlanNodeRuntimeStatsItem> curPlanNodeRuntimeStats, + Map<Integer, String> nodeFingerprints) { Map<PlanNodeAndHash, PlanStatisticsWithInputInfo> outputPlanStatisticsMap = new HashMap<>(); + // the fingerprint a plan node was published under, so a second node with the same fingerprint + // can be folded into it (the map above is keyed by the plan node identity as well) + Map<String, PlanNodeAndHash> publishedKeyByHash = new HashMap<>(); + int missingFingerprints = 0; + int skippedWithoutSnapshot = 0; for (TPlanNodeRuntimeStatsItem nodeStats : curPlanNodeRuntimeStats) { int nodeId = nodeStats.node_id; PhysicalPlan planNode = idToPlanMap.get(nodeId); - if (planNode != null) { - PlanStatistics curPlanStatistics = PlanStatistics.buildFromStatsItem( - nodeStats, planNode, scanToFilterMap); - InputTableStatisticsInfo inputTableStatisticsInfo = buildHboInputTableStatisticsInfo( - planNode, planToIdMap, scanToFilterMap, curPlanNodeRuntimeStats); - Optional<String> hash = inputTableStatisticsInfo.getHash(); - PlanNodeAndHash planNodeAndHash = new PlanNodeAndHash((AbstractPlan) planNode, hash); - PlanStatisticsWithInputInfo planHashWithInputInfo = new PlanStatisticsWithInputInfo( - nodeId, curPlanStatistics, inputTableStatisticsInfo); - outputPlanStatisticsMap.put(planNodeAndHash, planHashWithInputInfo); + if (planNode == null) { + continue; } + PlanStatistics curPlanStatistics = PlanStatistics.buildFromStatsItem( + nodeStats, planNode, scanToFilterMap); + InputTableStatisticsInfo inputTableStatisticsInfo = buildHboInputTableStatisticsInfo( + planNode, planToIdMap, scanToFilterMap, curPlanNodeRuntimeStats); + Optional<String> hash; + if (nodeFingerprints != null && nodeFingerprints.containsKey(nodeId)) { + String snapshot = nodeFingerprints.get(nodeId); + if (GroupStructInfo.UNSUPPORTED_FINGERPRINT.equals(snapshot)) { + // the node is deliberately excluded from the hbo fingerprint (its group is + // unsupported), so its missing fingerprint is not a diagnostic gap + continue; + } + hash = Optional.ofNullable(snapshot); + } else { + // no planning-time snapshot for this node: skip it + skippedWithoutSnapshot++; + if (nodeFingerprints != null && !nodeFingerprints.isEmpty()) { + missingFingerprints++; + } + continue; + } + if (!hash.isPresent()) { + continue; + } + PlanNodeAndHash planNodeAndHash = new PlanNodeAndHash((AbstractPlan) planNode, hash); + PlanNodeAndHash publishedKey = publishedKeyByHash.get(hash.get()); + if (publishedKey == null) { + publishedKeyByHash.put(hash.get(), planNodeAndHash); + outputPlanStatisticsMap.put(planNodeAndHash, new PlanStatisticsWithInputInfo( + nodeId, curPlanStatistics, inputTableStatisticsInfo)); + continue; + } + // a second runtime node with the same fingerprint (the two scans of a self join, for + // instance): the provider stores one entry per fingerprint, so the input statistics of both + // nodes are folded here - writing both would let the last write discard the other node's + // rows, and the drift comparison of the published entry expects the rows of every scan + PlanStatisticsWithInputInfo published = outputPlanStatisticsMap.get(publishedKey); + outputPlanStatisticsMap.put(publishedKey, new PlanStatisticsWithInputInfo( + published.getId(), published.getPlanStatistics(), + published.getInputTableInfo().merge(inputTableStatisticsInfo))); Review Comment: [P2] Preserve separate input populations for same-key scan runs Consider a qualifying execution with runtime filters OFF of `SELECT count(*) FROM (SELECT a FROM t WHERE b=1) x JOIN (SELECT a FROM t WHERE b=2) y ON x.a=y.a`. The derived aliases wrap Projects, so alias lowering leaves both underlying scan aliases empty and they share the S fingerprint. If both scans read all N mixed rows before filtering, this merge retains one node's output but concatenates both inputs into one run. On the identical next query, historical predicate matching accepts both recorded RelationIds, then scan fallback compares that run's recorded 2N with the single current scan's N and rejects it as STALE at the default tolerance. This is a new consequence of the same-key publication fix, distinct from the existing pruning-counter mismatch: each original scan population is individually comparable. Keep alternative node observations as separate runs under the fingerprint instead of concatenating their inputs. ########## fe/fe-core/src/main/java/org/apache/doris/nereids/stats/GroupStructInfo.java: ########## @@ -0,0 +1,2880 @@ +// 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.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.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.util.MutableState; +import org.apache.doris.qe.ConnectContext; + +import com.google.common.annotations.VisibleForTesting; +import com.google.common.hash.Hashing; +import org.apache.logging.log4j.LogManager; +import org.apache.logging.log4j.Logger; + +import java.nio.charset.StandardCharsets; +import java.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.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 #getShape(LiteralMode)}: the key an hbo entry is registered under. */ + public String getFingerprint(LiteralMode mode) { + boolean noLiteral = mode == LiteralMode.NO_LITERAL; + String materialized = noLiteral ? fingerprintNoLiteral : fingerprintWithLiteral; + if (materialized != null) { + return materialized; + } + materialized = sha256(getShape(mode)); + if (noLiteral) { + fingerprintNoLiteral = materialized; + } else { + fingerprintWithLiteral = materialized; + } + return materialized; + } + + private static String sha256(String value) { + return Hashing.sha256().hashString(value, StandardCharsets.UTF_8).toString(); + } + + /** + * Resolve the fingerprint of the memo group that {@code planNode} belongs to, when the node + * still carries its {@link GroupExpression} back reference (memo inner plans, or plans from + * {@code chooseBestPlan}). Empty when the group content is unsupported (invalid struct info). + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode) { + return fingerprintOfPlanNode(planNode, LiteralMode.WITH_LITERAL); + } + + /** + * Resolve the group fingerprint of a plan node in the given literal mode. + */ + public static Optional<String> fingerprintOfPlanNode(AbstractPlan planNode, LiteralMode mode) { + Group group = planNode.getGroupExpression().map(GroupExpression::getOwnerGroup).orElse(null); + 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. */ + 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 (Child child : node.children) { + definitions.putAll(child.node.columnDefinitions); + } + return Collections.unmodifiableMap(definitions); + } + + /** + * 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), + AGGREGATE("A", false), + // 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: 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(), fileScan.getTableSnapshot().isPresent() + || fileScan.getScanParams().isPresent() || fileScan.getTableSample().isPresent(), ctx); + } + if (plan instanceof PhysicalFileScan) { + PhysicalFileScan fileScan = (PhysicalFileScan) plan; + return fileScanNode(fileScan.getTable(), 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.conditions = joinConditions(join); + node.children = children(ge, ctx, 0); + if (node.children == null) { + return null; + } + for (int i = 1; i < ge.arity(); i++) { + List<Child> more = children(ge, ctx, i); + if (more == null) { + return null; + } + node.children.addAll(more); + } + return node; + } + return joinChainNode(join, ge, ctx); + } + + /** + * A whole inner / cross join chain as one node: inner and cross joins are associative and + * commutative, so the grouping of the chain is an artifact of the explored expression and must not be + * part of the fingerprint. The conditions of every join of the chain are merged (de-duplicated by + * their literal carrying text) and the leaves are sorted by their own identity - an order which is + * part of the fingerprint and must therefore not depend on a data state. + */ + private static Node joinChainNode(Join join, GroupExpression ge, Ctx ctx) { + List<Expression> conditions = joinConditions(join); + List<Leaf> leaves = new ArrayList<>(); + for (int i = 0; i < ge.arity(); i++) { + ChainInfo child = chainInfoOf(ge.child(i)); + if (!child.valid) { + return invalidNode(child.skipReason, ctx); + } + mergeConditions(conditions, child.conditions); + if (!composeChain(child, leaves, ctx)) { + return null; + } + } + if (!ctx.valid) { + return null; + } + leaves.sort(Comparator.comparing(Leaf::sortKey)); + Node node = new Node(Kind.JOIN); + node.flattenable = true; + node.conditions = conditions; + for (Leaf leaf : leaves) { + node.children.add(new Child(leaf.getLeaf().root(), leaf.isRepeated())); + } + return node; + } + + /** + * A set operation: its header carries the kind, the qualifier and the compared columns, and every + * branch writes the mapping of the columns it feeds the outputs with (see {@link #branchMapping}). + * The branches are sorted - the memo may reorder them - together with their mapping, because the + * mapping belongs to one branch and two branches of the same shape can still feed different columns. + */ + private static Node setOperationNode(Plan plan, SetOperation setOperation, GroupExpression ge, Ctx ctx) { + Node node = new Node(Kind.SET_OPERATION); + node.setOperationPlan = plan; + node.setOperation = setOperation; + List<GroupStructInfo> branches = describeBranches(ge, ctx); + if (branches == null) { + return null; + } + List<List<SlotReference>> mappings = setOperation.getRegularChildrenOutputs(); + if (plan instanceof Except) { + // the first branch is the minuend: it keeps its position, the subtrahends are sorted below + node.children.add(branchChild(branches.get(0), mappings, 0)); + List<Integer> subtrahends = new ArrayList<>(); + for (int i = 1; i < branches.size(); i++) { + subtrahends.add(i); + } + subtrahends.sort(Comparator.comparing( + index -> branchSortKey(branches.get(index), mappings, index))); + for (int index : subtrahends) { + node.children.add(branchChild(branches.get(index), mappings, index)); + } + return node; + } + // the branches are sorted because the memo may reorder them + List<Integer> order = new ArrayList<>(); + for (int i = 0; i < branches.size(); i++) { + order.add(i); + } + order.sort(Comparator.comparing(index -> branchSortKey(branches.get(index), mappings, index))); + for (int index : order) { + node.children.add(branchChild(branches.get(index), mappings, index)); + } + return node; + } + + private static Child branchChild(GroupStructInfo branch, List<List<SlotReference>> mappings, int index) { + return new Child(branch.root(), false, branchMapping(mappings, index, branch.root())); + } + + /** The mapping of one branch followed by its shape: the key the branches of a node are sorted by. */ + private static String branchSortKey(GroupStructInfo branch, List<List<SlotReference>> mappings, int index) { + return branchMappingText(branchMapping(mappings, index, branch.root()), LiteralMode.WITH_LITERAL) + + branch.getShape(LiteralMode.WITH_LITERAL); + } + + /** + * The columns one branch of a set operation feeds its outputs with. The branches are children of the + * node, but the projects which select those columns are transparent and the output slots of the + * operation are new ones, so this mapping is the only place where an output column is tied to a + * column of the branch: {@code SELECT a FROM t UNION SELECT a FROM u} and the same query selecting + * {@code u.b} read the same two tables and produce a different number of distinct rows. + */ + private static List<Expression> branchMapping(List<List<SlotReference>> mappings, int index, Node branchNode) { + if (index >= mappings.size() || mappings.get(index).isEmpty()) { + return Collections.emptyList(); + } + Map<ExprId, Expression> definitions = branchNode == null + ? Collections.emptyMap() : branchNode.columnDefinitions; + List<Expression> mapping = new ArrayList<>(mappings.get(index).size()); + for (SlotReference mapped : mappings.get(index)) { + // the mapped slot may be the output of a computed project inside the branch: the value the + // branch feeds the output with is that definition, not the name of the slot + mapping.add(resolveColumnDefinitions(mapped, definitions)); + } + return mapping; + } + + /** The mapping of one branch, rendered in the literal mode of the node above it. */ + private static String branchMappingText(List<Expression> mapping, LiteralMode mode) { + if (mapping.isEmpty()) { + return ""; + } + StringBuilder text = new StringBuilder("["); + for (int i = 0; i < mapping.size(); i++) { + if (i > 0) { + text.append(','); + } + text.append(renderExpression(mapping.get(i), mode)); + } + return text.append(']').toString(); + } + + /** Whether a project only forwards the columns of its child (no output of it is an alias). */ + private static boolean isTransparentProject(Plan plan) { + if (!(plan instanceof Project)) { + return false; + } + for (NamedExpression expression : ((Project) plan).getProjects()) { + if (expression instanceof Alias) { + return false; + } + } + return true; + } + + /** A node which only composes the child at {@code index} (an enforcer, a project, a CTE edge). */ + private static Node passthroughNode(GroupExpression ge, int index, Ctx ctx) { + Node node = new Node(Kind.PASSTHROUGH); + node.children = children(ge, ctx, index); + return node.children == null ? null : node; + } + + /** + * A scan of an internal table: its descriptor carries what the read side needs to compare the data + * state, so a scan whose state cannot be read leaves the whole group undescribed. + */ + private static Node olapScanNode(OlapScan scan, Ctx ctx) { + HboScanDescriptor descriptor = scanDescriptor(scan, ctx); + return descriptor == null ? null : scanRecord(Kind.SCAN, descriptor); + } + + /** + * A scan of an external table. Its identity is the table name only, which is why a scan which reads an + * explicit snapshot or a sampled part of one would share it although it holds different rows: such a + * scan is not described until the selector is part of the identity. + */ + private static Node fileScanNode(TableIf table, boolean explicitlyVersioned, Ctx ctx) { + String name = HboScanDescriptor.qualifiedNameOf(table); + if (name.indexOf(',') >= 0 || name.indexOf('}') >= 0) { + // the token delimiters cannot appear in a table name: the printed struct info could not be + // read back, and a pasted one could resolve to another table + return invalidNode("delimiter in table name " + name, ctx); + } + if (explicitlyVersioned) { + return invalidNode("selected file scan " + name, ctx); + } + return scanRecord(Kind.FILE_SCAN, HboScanDescriptor.ofUnreadableState(table)); Review Comment: [P2] Preserve alias bindings in external scan keys The OLAP `#ra` fix does not cover this FileScan branch. Compare these reduced trees in one external catalog/database: ```text Join(x.a=y.a AND x.b<y.b, FileScan(t AS x), FileScan(u AS y)) Join(x.a=y.a AND x.b<y.b, FileScan(u AS x), FileScan(t AS y)) ``` For NOT NULL BIGINT `(a,b)` data t=(1,1), u=(1,2), they return one versus zero rows. Alias lowering preserves x/y in forwarding Projects, but `ofUnreadableState(table)` drops `tableAlias`; sorting the t/u leaves therefore gives identical exact J keys. The relation prefilter matches, and UNKNOWN external freshness permits the first pin to override the second estimate. This is the separate external-scan instance left after the existing OLAP alias-binding report. Carry the file scan's alias-to-table binding into its descriptor, or resolve predicates to scan occurrences before sorting. -- 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]
