github-actions[bot] commented on code in PR #68499: URL: https://github.com/apache/doris/pull/68499#discussion_r4431570880
########## fe/fe-core/src/main/java/org/apache/doris/nereids/spm/placeholder/SPMPlaceholderBuilder.java: ########## @@ -0,0 +1,1500 @@ +// 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.spm.placeholder; + +import org.apache.doris.catalog.FunctionSignature; +import org.apache.doris.nereids.spm.SPMPlanTreeSupport; +import org.apache.doris.nereids.trees.expressions.And; +import org.apache.doris.nereids.trees.expressions.CaseWhen; +import org.apache.doris.nereids.trees.expressions.Expression; +import org.apache.doris.nereids.trees.expressions.InPredicate; +import org.apache.doris.nereids.trees.expressions.InSubquery; +import org.apache.doris.nereids.trees.expressions.Like; +import org.apache.doris.nereids.trees.expressions.Not; +import org.apache.doris.nereids.trees.expressions.Or; +import org.apache.doris.nereids.trees.expressions.SubqueryExpr; +import org.apache.doris.nereids.trees.expressions.WhenClause; +import org.apache.doris.nereids.trees.expressions.functions.BoundFunction; +import org.apache.doris.nereids.trees.expressions.functions.Function; +import org.apache.doris.nereids.trees.expressions.functions.scalar.ElementAt; +import org.apache.doris.nereids.trees.expressions.literal.ArrayLiteral; +import org.apache.doris.nereids.trees.expressions.literal.Literal; +import org.apache.doris.nereids.trees.expressions.literal.MapLiteral; +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.logical.LogicalPlan; +import org.apache.doris.nereids.types.ArrayType; +import org.apache.doris.nereids.types.BooleanType; +import org.apache.doris.nereids.types.DataType; +import org.apache.doris.nereids.types.MapType; +import org.apache.doris.nereids.types.coercion.FollowToArgumentType; + +import com.google.common.collect.ImmutableList; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Deque; +import java.util.List; +import java.util.Locale; +import java.util.Map; +import java.util.Set; + +/** + * SPMPlaceholderBuilder + * + * Replaces the literal constants in a query with + * SPM placeholder functions so that one baseline can match structurally identical + * queries. Core replacement rules: + * + * - Literal -> SpmConstVar (scalar placeholder with an auto-increment id) + * - "IN (constant list)" -> InPredicate(expr, [SpmConstList(id, ...)]) (list placeholder) + * + * The auto-increment id guarantees that placeholders in the same position of bindSql and + * planSql share the same id (in path A auto-capture both come from the same already + * parameterized tree, so the ids naturally match). + * + * Placeholder deduplication follows: a literal + * reuses an existing placeholder id only when the literal value (Step 1), its parent + * expression structure (Step 2, PlaceholderExpr.matches) AND its position inside that + * parent (child index) are equal. This is important for matching correctness: with + * value-only dedup, "a = 1 AND b = 1" would assign one id to both literals and a user + * query "a = 5 AND b = 7" could never match; without the child index, the two operands + * of "1 + 1" would share one id and a similar query "2 + 1" could never match either. + */ +public class SPMPlaceholderBuilder extends ExpressionVisitor<Expression, Expression> + implements SPMPlanTreeSupport.ExprTransform { + + /** + * The ARRAY scalar functions that declare {@code retArgType(0)}: each one's result IS its + * first argument's array type, so an all-NULL input makes the whole result an all-NULL array. + * + * <p>They are exactly the wrappers a projected all-NULL container can sit UNDER while the + * enclosing call is still consumed as a Boolean operand, e.g. + * {@code k > 0 OR element_at(array_reverse_sort(array(NULL)), 1)}: the wrapper hands + * {@code array(NULL)}'s NullType element type to {@code element_at}, so the marker has to be + * repaired at the WRAPPER's argument position. Matching only {@code array_sort} / + * {@code array_distinct} left every other member of the family unrecognized (round-87 + * review). + * + * <p>Matched by NAME because the capture runs on the PARSE tree, where the call is still an + * unbound {@link Function} and no signature is resolved yet; a BOUND node is classified from + * its {@code retArgType(0)} signature instead (see followsFirstArgument), so a function added + * to the family is recognized without touching this list. {@code array_concat} is NOT here: + * it derives its element type from EVERY part and is handled separately + * (isArrayConcatCall). + */ + private static final Set<String> TYPE_PRESERVING_ARRAY_CALLS = Set.of( + "array_apply", "array_compact", "array_difference", "array_distinct", + "array_except", "array_except_all", "array_filter", "array_first", + "array_intersect", "array_last", "array_popback", "array_popfront", + "array_pushback", "array_pushfront", "array_remove", "array_reverse_sort", + "array_shuffle", "array_slice", "array_sort", "array_sortby", "array_union", + "reverse", "trim_array"); + + /** The MAP counterpart of {@link #TYPE_PRESERVING_ARRAY_CALLS} (same {@code retArgType(0)} + * declaration: {@code map_filter} returns its first argument's map type). */ + private static final Set<String> TYPE_PRESERVING_MAP_CALLS = Set.of("map_filter"); + + /** Auto-increment placeholder id counter (starts at 1). */ + private long nextId = 1; + + /** Placeholder record list. */ + private final List<PlaceholderExpr> placeholderExprs = new ArrayList<>(); + + /** + * Optional GROUP BY mirror lookup, installed by SPMPlanTreeSupport.TreeTransformer for + * one clause window (see setGroupByMirrorLookup): maps an expression's + * pre-parameterization text to the ALREADY-transformed GROUP BY expression that must + * be reused - also for NESTED subexpressions (e.g. the substr(...) inside + * "HAVING substr(...) = 'x'"), because the analyzer resolves such a clause + * expression-wise and demands literal expression equality with the GROUP BY under + * ONLY_FULL_GROUP_BY. Null outside the window. + */ + private java.util.function.Function<String, Expression> groupByMirrorLookup; + + /** + * DFS stack of child positions: the top is the index of the expression currently + * being visited inside its direct parent (empty = parent-less root). Two literals + * under the same parent (e.g. the operands of "1 + 1") are different positions and + * must never reuse one placeholder id. + */ + private final Deque<Integer> childIndexStack = new ArrayDeque<>(); + + /** + * Query-block identity: incremented when entering a nested query block (the plan of + * a subquery expression). Two literals in DIFFERENT blocks never share a placeholder + * id even when value / parent / position coincide: in + * SELECT * FROM t WHERE a=1 AND EXISTS (SELECT 1 FROM u WHERE a=1) the two a=1 + * literals used to reuse one id, and a user query with outer a=2 / inner a=3 was + * rejected (one id must resolve to ONE value), so the baseline could never hit. + * The counter restarts per tree (see startNewTree): bind and plan trees traverse the + * same structure in the same order, so corresponding blocks keep corresponding + * numbers and the cross-tree id alignment is preserved. + */ + private long nextBlockId = 1; + private long currentBlockId = 0; + + /** + * Enclosing query-block ids (see enterQueryBlock()): a nested block's id is + * restored on exit, so SIBLING derived tables / CTE bodies get distinct ids while the + * enclosing block numbering resumes - the same discipline the subquery-expression + * blocks already followed. + */ + private final Deque<Long> blockIdStack = new ArrayDeque<>(); + + /** + * Projection ITEM positions of the SELECT-list slots currently being visited (see + * enterProjectionItem(int)): SELECT 1 AS x, 1 AS y must give its two + * literals different placeholder ids although value, parent structure and child + * position coincide (see PlaceholderExpr#matches). + */ + private final Deque<Integer> projectItemStack = new ArrayDeque<>(); + + /** + * Ordinal of the expression ROOT currently being transformed, counted per query block in + * walk order (see beginExpressionRoot): two equal literals in DIFFERENT roots of one + * block (the ON clauses of two joins, two conjuncts of one filter, ...) used to share one + * placeholder id although they are independent slots - a query that varies them + * separately (1/1 -> 2/3) was then rejected by recordPlaceholderValue and the saved + * baseline could never be used (the reviewer's round-58 finding). The counting restarts + * per tree run AND per block, so the bind and plan trees of one baseline traverse the + * same structure in the same order and corresponding roots keep corresponding ordinals. + */ + private long nextRootOrdinal = 0; + private long currentRootOrdinal = -1; + + /** + * Depth of an all-NULL CONDITIONAL (CASE / IF / COALESCE) currently visited in a Boolean + * context (see markerPayload): such a node has NullType and the analyzer replaces the whole + * operand with a typed constant, so its branch NULLs are parameterized BOOLEAN. + */ + private int booleanConditionalDepth; + + /** + * Depth of a CONTAINER CONSTRUCTOR (`array(...)`) whose ELEMENTS are the markers that carry + * the container's element type (see markerPayload): an all-NULL element list is what makes + * the constructor NullType, so its NULL elements are parameterized BOOLEAN while the + * constructor itself sits in a container position of a NullType-producing chain. + */ + private int containerElementDepth; + + /** + * Whether a bare integer GROUP BY ordinal references a SELECT item that carries a + * placeholder (see SPMPlanTreeSupport#visitLogicalAggregate). The ordinal itself stays + * CONCRETE, but the analyzer resolves it to that item's (parameterized) expression, and + * the frozen rendering of a placeholder group key is NOT faithful: the capture optimizer + * rewrote `GROUP BY <placeholder>` into a child column, so a frozen replay of + * `SELECT 1 AS c, count(*) ... GROUP BY 1` grouped by `k` while the user's own query + * grouped by the constant. The CREATE keeps the user planSql then and replays the + * parameterized tree, whose analysis resolves the ordinal in the caller's own query. + */ + private boolean parameterizedGroupByOrdinalTarget; + + /** The enclosing block's root-ordinal counter, restored by exitQueryBlock(). */ + private final Deque<Long> rootOrdinalStack = new ArrayDeque<>(); + + /** The enclosing root's ordinal, restored by exitQueryBlock() (see enterQueryBlock). */ + private final Deque<Long> currentRootOrdinalStack = new ArrayDeque<>(); + + /** Installs / clears the GROUP BY mirror lookup window (null = disabled). */ + public void setGroupByMirrorLookup(java.util.function.Function<String, Expression> lookup) { + this.groupByMirrorLookup = lookup; + } + + /** See parameterizedGroupByOrdinalTarget. */ + public boolean hasParameterizedGroupByOrdinalTarget() { + return parameterizedGroupByOrdinalTarget; + } + + /** Marks one bare integer GROUP BY ordinal whose SELECT item carries placeholders. */ + public void noteParameterizedGroupByOrdinalTarget() { + this.parameterizedGroupByOrdinalTarget = true; + } + + /** + * Parameterizes a list of expressions with this single shared builder (entry point). + * + * Every expression is parameterized in order with the same builder, so placeholder + * ids stay globally unique and position-aligned across all query blocks (the topmost + * block's literals get the lowest ids, then derived tables / CTE bodies / nested + * blocks, in DFS order). This is what keeps the bind expressions of a multi-block + * baseline matched against the user query block by block. + * + * @param exprs the raw expressions to parameterize (one per query block) + * @return the parameterized expressions (containing SpmConstVar / SpmConstList) + */ + public List<Expression> parameterizeExpressions(List<Expression> exprs) { + List<Expression> parameterized = new ArrayList<>(exprs.size()); + for (Expression expr : exprs) { + // each element is one query block of the same tree: its own block scope + startNewTree(); + beginExpressionRoot(); + parameterized.add(expr.accept(this, null)); + } + return parameterized; + } + + /** Starts one expression ROOT of the current block (see nextRootOrdinal). */ + private void beginExpressionRoot() { + currentRootOrdinal = nextRootOrdinal++; + } + + /** Restarts the per-tree query-block numbering (a tree's root block is 0). */ + public void startNewTree() { + nextBlockId = 1; + currentBlockId = 0; + blockIdStack.clear(); + projectItemStack.clear(); + // one tree = one root-ordinal run: corresponding roots of the bind tree and the + // (separately parsed) plan tree keep corresponding ordinals + nextRootOrdinal = 0; + currentRootOrdinal = -1; + rootOrdinalStack.clear(); + currentRootOrdinalStack.clear(); + } + + /** + * The whole-tree parameterization transform: the builder IS an + * SPMPlanTreeSupport.ExprTransform, so the plan walk can hand it the query + * BLOCK and projection ITEM scopes of the expressions it visits (see + * SPMPlanTreeSupport.ExprTransform#enterQueryBlock()). Passing a bare lambda + * instead would lose those scopes and merge independent literals into one placeholder + * id. + */ + @Override + public Expression apply(Expression expr) { + beginExpressionRoot(); + return expr.accept(this, null); + } + + /** + * Transform of a SUBQUERY expression's own plan tree: every expression the walk hands + * over is a block ROOT (the child-position sentinel -1), and the query-block / + * projection-item scope hooks are forwarded to the enclosing builder so nested + * derived tables keep their own block ids. + */ + private final class SubqueryBlockTransform implements SPMPlanTreeSupport.ExprTransform { + @Override + public Expression apply(Expression expr) { + beginExpressionRoot(); + childIndexStack.push(-1); + try { + return expr.accept(SPMPlaceholderBuilder.this, null); + } finally { + childIndexStack.pop(); + } + } + + @Override + public void enterQueryBlock() { + SPMPlaceholderBuilder.this.enterQueryBlock(); + } + + @Override + public void exitQueryBlock() { + SPMPlaceholderBuilder.this.exitQueryBlock(); + } + + @Override + public void enterProjectionItem(int index) { + SPMPlaceholderBuilder.this.enterProjectionItem(index); + } + + @Override + public void exitProjectionItem() { + SPMPlaceholderBuilder.this.exitProjectionItem(); + } + } + + /** + * Enters a nested query block (see + * org.apache.doris.nereids.spm.SPMPlanTreeSupport.ExprTransform#enterQueryBlock()): + * the block gets its own monotonic id, the enclosing one is restored by + * exitQueryBlock(). + */ + @Override + public void enterQueryBlock() { + blockIdStack.push(currentBlockId); + currentBlockId = nextBlockId++; + // the root-ordinal counting is per BLOCK as well: a nested block's roots must not + // shift the enclosing block's ordinals (and vice versa), and the enclosing counters + // resume on exit + rootOrdinalStack.push(nextRootOrdinal); + nextRootOrdinal = 0; + currentRootOrdinalStack.push(currentRootOrdinal); + currentRootOrdinal = -1; + } + + /** Leaves the current nested query block and restores the enclosing block id. */ + @Override + public void exitQueryBlock() { + if (!blockIdStack.isEmpty()) { + currentBlockId = blockIdStack.pop(); + } + if (!rootOrdinalStack.isEmpty()) { + nextRootOrdinal = rootOrdinalStack.pop(); + } + if (!currentRootOrdinalStack.isEmpty()) { + currentRootOrdinal = currentRootOrdinalStack.pop(); + } + } + + /** + * Enters one projection item of a projection-like list: every literal of its subtree + * carries this position, so two equally shaped literals in different items (or in a + * projection and in a filter) never share one placeholder id. + */ + @Override + public void enterProjectionItem(int index) { + projectItemStack.push(index); + } + + /** Leaves the current projection item. */ + @Override + public void exitProjectionItem() { + if (!projectItemStack.isEmpty()) { + projectItemStack.pop(); + } + } + + /** Position of the projection item currently being visited; -1 outside a SELECT list. */ + private int currentProjectItem() { + Integer top = projectItemStack.peek(); + return top == null ? -1 : top; + } + + public List<PlaceholderExpr> getPlaceholderExprs() { + return placeholderExprs; + } + + /** Position of the expression currently being visited inside its direct parent; -1 at a root. */ + private int currentChildIndex() { + Integer top = childIndexStack.peek(); + return top == null ? -1 : top; + } + + /** + * The occurrence path of the literal currently being visited: the child positions from the + * transformed EXPRESSION ROOT down to the literal, rendered as "0/1/..." (empty for a + * root literal). Two equal literals can sit under structurally EQUAL parents at + * different places of one root ("a = 1 AND a = 1": the parents are the two And + * children), and only the path tells those independent slots apart - see + * PlaceholderExpr#occurrencePath. + */ + private String currentOccurrencePath() { + if (childIndexStack.isEmpty()) { + return ""; + } + Object[] positions = childIndexStack.toArray(); + StringBuilder sb = new StringBuilder(); + for (int i = positions.length - 1; i >= 0; i--) { + if (sb.length() > 0) { + sb.append('/'); + } + sb.append(positions[i]); + } + return sb.toString(); + } + + // ==================== literal -> scalar placeholder ==================== + + /** + * Whether the expression's TYPE is NullType. + * + * The type is derived structurally because this builder walks the UNBOUND plan, where + * {@code getDataType()} throws. A node produces NullType when EVERY value it can yield is + * NULL - a NULL literal, a CASE whose every result does, an IF whose two value arguments do, + * a COALESCE / IFNULL / NVL / NULLIF / GREATEST / LEAST all of whose arguments do. Collected as + * a Boolean operand (directly, or through a projected slot) such an expression is REPLACED by + * the analyzer with a typed constant NULL, which deletes the placeholders inside it. + * + * The test is RECURSIVE on purpose (round-78 #5): a conditional nested in the RESULT of + * another conditional (`k > 0 OR (CASE WHEN k = 0 THEN ifnull(NULL, NULL) ELSE NULL END)`) + * yields NullType although its result is not a NULL LITERAL, so a literal-only test left its + * inner markers NullType and the consumer erased them - a TRUE variant then replayed as NULL. + * The same recursion covers the custom-signature producers: {@code GreatestLeast#customSignature} + * returns the arguments' common type, i.e. NullType for {@code greatest(NULL, NULL)} (round-78 + * #1, LEAST shares the path). + * + * @param expr the expression to classify + * @return whether every value the expression can yield is NULL + */ + private static boolean producesNullType(Expression expr) { + if (expr == null) { + return false; + } + if (expr.isNullLiteral()) { + return true; + } + List<Expression> children = expr.children(); + if (expr instanceof CaseWhen) { + CaseWhen caseWhen = (CaseWhen) expr; + for (WhenClause clause : caseWhen.getWhenClauses()) { + if (!producesNullType(clause.getResult())) { + return false; + } + } + return !caseWhen.getDefaultValue().isPresent() + || producesNullType(caseWhen.getDefaultValue().get()); + } + if (isIfConditional(expr)) { + return children.size() == 3 && producesNullType(children.get(1)) + && producesNullType(children.get(2)); + } + if (isIfNullConditional(expr) || isNullIfConditional(expr) + || isGreatestLeastConditional(expr) || isCoalesceConditional(expr)) { + // every argument contributes a value the result may equal: all-NULL arguments make + // the whole call NullType (IFNULL / NVL / NULLIF / GREATEST / LEAST / COALESCE) + if (children.isEmpty()) { + return false; + } + for (Expression child : children) { + if (!producesNullType(child)) { + return false; + } + } + return true; + } + if (isElementAtCall(expr)) { + // `element_at(array(NULL), 1)` takes its type from the ARRAY's element type and + // `element_at(map('x', NULL), 'x')` from the MAP's VALUE type (CreateMap derives + // MAP<STRING, NULL_TYPE>), so an all-NULL container makes the WHOLE call NullType: a + // Boolean consumer replaced the two markers of + // `k > 0 OR element_at(array(NULL), 1)` with a typed constant and the + // `element_at(array(TRUE), 1)` variant had nothing to substitute (round-79 #3), and + // the MAP spelling lost the value marker the same way (round-80 #1). + return !children.isEmpty() && isAllNullContainer(children.get(0)); + } + if (isArrayReducerCall(expr)) { + // The SAME producer classification, for the array REDUCERS (round-81 P1): + // ARRAY_MIN / ARRAY_MAX return `FollowToAnyDataType(0)`, i.e. the INPUT array's + // element type, so an all-NULL input makes the whole call NullType - binding then + // replaced `k > 0 OR array_min(array(NULL))` with `k > ph OR NULL` and the + // `array_min(array(TRUE))` caller got NULL instead of TRUE. Keeping the family in + // ONE classifier is what lets the marker be retyped before the Boolean consumer + // drops it - the same defect the bare element_at trigger had, so it is carried here + // instead of in a per-function inline. + return !children.isEmpty() && isAllNullArray(children.get(0)); + } + return false; + } + + /** + * Whether the expression is a container whose ELEMENT type is NullType (see producesNullType): + * an all-NULL array or an all-NULL-valued map. Both overloads of `element_at` return the + * container's element / value type, so either one makes the call a NullType producer. + * + * @param expr the expression to classify + * @return whether it is an all-NULL array or map value + */ + private static boolean isAllNullContainer(Expression expr) { + return isAllNullArray(expr) || isAllNullMap(expr); + } + + /** + * Whether the expression builds a MAP whose every VALUE produces NullType (see + * producesNullType). + * + * The children of a map constructor alternate KEY, VALUE, so only the odd positions feed the + * map's value type - and with it what `element_at` returns. Both spellings are accepted: the + * parsed `map(...)` call and the bound {@code CreateMap}, which is a {@link Function} named + * {@code map}. A MAP LITERAL ({@code MapLiteral}) is a leaf without children and is therefore + * not covered - its entries are never parameterized either. + * + * @param expr the expression to classify + * @return whether it is an all-NULL-valued map value + */ + private static boolean isAllNullMap(Expression expr) { + if (expr == null) { + return false; + } + if (expr instanceof MapLiteral) { + // A map LITERAL is a LEAF: its entries live in getValue(), not in children() + // (round-84 #1). visitLiteral parameterizes the whole literal as ONE marker, and + // without this branch `element_at({'x': NULL}, 'x')` stayed a NullType producer + // candidate, the Boolean consumer replaced the whole call and the marker with it, + // and the `{'x': TRUE}` variant had no id left to substitute. + Map<Literal, Literal> entries = ((MapLiteral) expr).getValue(); + if (entries.isEmpty()) { + // the same argument as for the empty ARRAY literal: without an entry there is no + // value type to inherit, so the empty map is NullType-valued as well (round-85) + return true; + } + for (Literal value : entries.values()) { + if (!producesNullType(value)) { + return false; + } + } + return true; + } + if (!isMapConstructor(expr)) { Review Comment: [P1] Follow MAP wrappers when repairing Boolean NULL markers Capture identical bind/plan SQL `SELECT k>0 OR element_at(map_filter(map('x',NULL),array(TRUE)),'x') AS c FROM t` on `t(k)={-1}`, then execute the variant changing the map value to TRUE. The reduced capture tree is: ```text Project(Or(k>ph1, ElementAt(MapFilter(Map(phKey,phNull),Array(phTrue)),phKey2))) Scan(t) ``` `isAllNullMap(MapFilter(...))` returns false here, although `map_filter` preserves its input MAP value type. Boolean repair therefore leaves `MAP<STRING,NULL_TYPE>` intact; `ExpressionAnalyzer.visitOr` replaces the entire ElementAt operand with Boolean NULL and erases its markers. Frozen replay becomes `k>ph1 OR NULL`: the TRUE variant still matches, but returns NULL rather than TRUE. The capture probe checks only surviving physical-plan markers and accepts this SQL. This is the MAP-wrapper path, separate from the repaired ARRAY-wrapper and bare MAP-literal cases. Recurse through type-preserving MAP calls and repair their underlying values, or reject capture when required markers disappear. ########## fe/fe-core/src/main/java/org/apache/doris/nereids/spm/builder/SPMPlan2SQLBuilder.java: ########## @@ -0,0 +1,4743 @@ +// 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.spm.builder; + +import org.apache.doris.analysis.TableScanParams; +import org.apache.doris.analysis.TableSnapshot; +import org.apache.doris.catalog.Column; +import org.apache.doris.catalog.OlapTable; +import org.apache.doris.catalog.Partition; +import org.apache.doris.common.Pair; +import org.apache.doris.nereids.parser.NereidsParser; +import org.apache.doris.nereids.properties.DistributionSpec; +import org.apache.doris.nereids.properties.DistributionSpecReplicated; +import org.apache.doris.nereids.trees.TableSample; +import org.apache.doris.nereids.trees.expressions.AggregateExpression; +import org.apache.doris.nereids.trees.expressions.Alias; +import org.apache.doris.nereids.trees.expressions.CTEId; +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.IsNull; +import org.apache.doris.nereids.trees.expressions.MarkJoinSlotReference; +import org.apache.doris.nereids.trees.expressions.NamedExpression; +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.NoneMovableFunction; +import org.apache.doris.nereids.trees.expressions.functions.agg.AggregateFunction; +import org.apache.doris.nereids.trees.expressions.functions.agg.GroupConcat; +import org.apache.doris.nereids.trees.expressions.functions.agg.MultiDistinctGroupConcat; +import org.apache.doris.nereids.trees.expressions.functions.generator.Unnest; +import org.apache.doris.nereids.trees.expressions.functions.scalar.GroupingId; +import org.apache.doris.nereids.trees.expressions.functions.scalar.GroupingScalarFunction; +import org.apache.doris.nereids.trees.expressions.functions.scalar.If; +import org.apache.doris.nereids.trees.expressions.functions.table.TableValuedFunction; +import org.apache.doris.nereids.trees.expressions.literal.Literal; +import org.apache.doris.nereids.trees.plans.AggPhase; +import org.apache.doris.nereids.trees.plans.JoinType; +import org.apache.doris.nereids.trees.plans.LimitPhase; +import org.apache.doris.nereids.trees.plans.Plan; +import org.apache.doris.nereids.trees.plans.algebra.SetOperation.Qualifier; +import org.apache.doris.nereids.trees.plans.physical.AbstractPhysicalJoin; +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.PhysicalCatalogRelation; +import org.apache.doris.nereids.trees.plans.physical.PhysicalDistribute; +import org.apache.doris.nereids.trees.plans.physical.PhysicalEmptyRelation; +import org.apache.doris.nereids.trees.plans.physical.PhysicalExcept; +import org.apache.doris.nereids.trees.plans.physical.PhysicalFileScan; +import org.apache.doris.nereids.trees.plans.physical.PhysicalFilter; +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.PhysicalHashJoin; +import org.apache.doris.nereids.trees.plans.physical.PhysicalIntersect; +import org.apache.doris.nereids.trees.plans.physical.PhysicalLazyMaterialize; +import org.apache.doris.nereids.trees.plans.physical.PhysicalLazyMaterializeFileScan; +import org.apache.doris.nereids.trees.plans.physical.PhysicalLazyMaterializeOlapScan; +import org.apache.doris.nereids.trees.plans.physical.PhysicalLazyMaterializeTVFScan; +import org.apache.doris.nereids.trees.plans.physical.PhysicalLimit; +import org.apache.doris.nereids.trees.plans.physical.PhysicalNestedLoopJoin; +import org.apache.doris.nereids.trees.plans.physical.PhysicalOlapScan; +import org.apache.doris.nereids.trees.plans.physical.PhysicalOneRowRelation; +import org.apache.doris.nereids.trees.plans.physical.PhysicalPartitionTopN; +import org.apache.doris.nereids.trees.plans.physical.PhysicalProject; +import org.apache.doris.nereids.trees.plans.physical.PhysicalQuickSort; +import org.apache.doris.nereids.trees.plans.physical.PhysicalRecursiveUnion; +import org.apache.doris.nereids.trees.plans.physical.PhysicalRecursiveUnionAnchor; +import org.apache.doris.nereids.trees.plans.physical.PhysicalRecursiveUnionProducer; +import org.apache.doris.nereids.trees.plans.physical.PhysicalRelation; +import org.apache.doris.nereids.trees.plans.physical.PhysicalRepeat; +import org.apache.doris.nereids.trees.plans.physical.PhysicalResultSink; +import org.apache.doris.nereids.trees.plans.physical.PhysicalSetOperation; +import org.apache.doris.nereids.trees.plans.physical.PhysicalSink; +import org.apache.doris.nereids.trees.plans.physical.PhysicalStorageLayerAggregate; +import org.apache.doris.nereids.trees.plans.physical.PhysicalTVFRelation; +import org.apache.doris.nereids.trees.plans.physical.PhysicalTopN; +import org.apache.doris.nereids.trees.plans.physical.PhysicalUnion; +import org.apache.doris.nereids.trees.plans.physical.PhysicalWindow; +import org.apache.doris.nereids.trees.plans.physical.PhysicalWorkTableReference; +import org.apache.doris.nereids.trees.plans.visitor.PlanVisitor; + +import com.google.common.collect.Lists; +import org.apache.commons.lang3.StringUtils; +import org.apache.logging.log4j.LogManager; +import org.apache.logging.log4j.Logger; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Locale; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.TreeMap; +import java.util.TreeSet; +import java.util.regex.Matcher; +import java.util.regex.Pattern; +import java.util.stream.Collectors; + +/** + * Physical-plan decompiler (M1). + * + * Decompiles the optimal physical plan tree output by the optimizer into one + * semantically equivalent standard SQL (planSql). planSql freezes the optimizer's key + * decisions (JOIN order, aggregate structure, sort semantics) through SQL structure and + * HINTs, so the plan can be replayed during query rewrite. This is the core engine of + * the SPM "plan-to-SQL" approach. + * + * Design (design doc 6.2): + * + * - Pass-through: physical infrastructure nodes such as PhysicalDistribute and + * PhysicalResultSink have no SQL equivalent and return the child result directly. + * - Merge: a local aggregate (LOCAL) registers the aggregate function names onto the + * child relation without adding nesting. + * - Wrap: Filter / Join / global aggregate / TopN / Project / Window create a new + * SQLRelation and set an alias; parent operators reference it as a subquery through + * toRelationSQL(). + * + * Known M1 simplifications: + * + * - Scan uses the real column names (no c_N normalization; column-name collision + * scenarios are handled in a later milestone). + */ +public class SPMPlan2SQLBuilder extends PlanVisitor<SQLRelation, Void> { + + private static final Logger LOG = LogManager.getLogger(SPMPlan2SQLBuilder.class); + + /** Generated output names ("c_" + position) produced by re-export labels and dedupe renames. */ + private static final Pattern GENERATED_NAME_PATTERN = Pattern.compile("\\bc_\\d+\\b"); + + /** JOIN distribution HINT prefix constants. */ + private static final String HINT_JOIN_BROADCAST = "BROADCAST"; + private static final String HINT_JOIN_SHUFFLE = "SHUFFLE"; + + /** + * Re-export labels a hoist step created one level below ("X AS c_N" items): maps the + * generated label back to the ExprId of the item it re-exports, so a later hoist step + * can re-export the SAME label through one more projection level (tpcds q78: the + * ORDER BY hoisted out of the 16-item projection references c_14/c_15/c_16, and the + * 11-item projection above it must therefore re-export them). + */ + private final Map<String, ExprId> reExportedLabels = new HashMap<>(); + + /** Expression printer (carries the columnNames mapping of SQLRelation). */ + private final SPMExprSqlBuilder exprSqlBuilder = new SPMExprSqlBuilder(); + + /** Per-decompile alias sequence for LATERAL VIEW clauses whose output slot has no + * user qualifier (reset in toSQL). */ + private int lateralViewSeq = 0; + + /** CTE body relations keyed by CTEId (registered by visitPhysicalCTEProducer). The + * consumer references the CTE by its alias instead of inlining the body, so the + * decompiled planSql keeps the WITH structure - one definition shared by every + * consumer - like StarRocks does. */ + private final Map<CTEId, SQLRelation> cteBodies = new HashMap<>(); + + /** CTEId -> the generated alias (t_N) that references the WITH definition. */ + private final Map<CTEId, String> cteAliases = new HashMap<>(); + + /** + * The WITH entries (alias AS (body)) in producer visit order - the definition + * order of the emitted WITH clause. They are attached to the ROOT relation in + * toSQL(): every consumer lies inside the statement, so the definitions are + * visible everywhere regardless of how deeply the CTE anchors are nested in the + * physical tree (attaching at each anchor instead would place a definition inside + * one join branch while a consumer sits in another branch). Producers are visited + * in dependency order - a consumer requires its producer to be registered already - + * so the list is a valid SQL definition order (a CTE used by another CTE is + * defined before it). + */ + private final List<String> cteDefinitions = new ArrayList<>(); + + /** Recursive CTE output column names keyed by CTE name. Registered from the anchor + * branch of a PhysicalRecursiveUnion; used to name the recursive work-table self + * reference and the outer reference so the decompiled WITH RECURSIVE stays + * re-parseable. */ + private final Map<String, List<String>> recursiveCteColumns = new HashMap<>(); + + /** Local (partial) aggregate output column -> the aggregate input expression it + * aggregates, e.g. local partial_sum(x)#N registers N -> x. A global + * aggregate references such a column as sum(partial_sum(x)#N); the global + * decompile rewrites it back to sum(x) so the decompiled SQL stays a single + * logical aggregate (no partial_ intermediate functions). */ + private final Map<ExprId, Expression> localAggParams = new HashMap<>(); + + /** + * Buffer columns produced by the distinct-dedup branch: their defining partial + * aggregate consumed a DATA column (e.g. DISTINCT_LOCAL's partial_count(key)), + * not another partial buffer. In a DISTINCT_GLOBAL merge stage a count(...) over + * such a buffer is the user's count(DISTINCT key). + * + * A plan may mix plain aggregates with a distinct one (TPCDS q28: + * avg(x), count(x), count(DISTINCT x)): the plain count rides along the same + * DISTINCT_GLOBAL stage, but its buffer is a merge chain (its defining partial + * aggregated another partial buffer, e.g. partial_count(partial_count(x))), so it + * must NOT be rendered with DISTINCT. Both chains otherwise resolve to the same + * data column, which is why the provenance has to be recorded while the + * intermediate stages are eliminated. + */ + private final Set<ExprId> distinctMergeBuffers = new HashSet<>(); + + /** + * Table id to (partition id to the name the CAPTURE resolved), snapshotted while the + * planning locks were held (see SPMOptimizer.OptimizeResult#getPartitionNames). Empty when + * the caller has none (a direct / test-side decompile). + */ + private final Map<Long, Map<Long, String>> capturedPartitionNames; + + /** The OUTERMOST projection of the decompiled tree (by identity). It alone prunes its + * output to the final user-visible columns; every intermediate projection outputs the + * full child column set plus its own expressions, so an upper layer (filter / join / + * aggregate / projection) can always resolve the columns it references. */ + private final Set<Plan> outputProjects = + Collections.newSetFromMap(new java.util.IdentityHashMap<>()); + + /** + * Identity map: physical plan node -> the ExprIds of its output columns that upper + * layers actually consume (the final result columns plus every column referenced by + * a decompiled expression above). An entry ABSENT, or mapped to null, means "no + * pruning for this node and everything below it" (the pre-pruning behaviour). + * + * The decompiled planSql inflates when every intermediate projection re-emits the + * whole child column set (a deep TPCDS join stack re-lists hundreds of c_N columns + * per level). This map drives live-column pruning: each SELECT list is filtered to + * the live columns only, so a column that is never referenced above and is not part + * of the final result disappears from every intermediate projection. Equivalence is + * preserved because only dead columns are dropped. + */ + private final Map<Plan, Set<ExprId>> neededOutputs = + new java.util.IdentityHashMap<>(); + + /** + * CTEId -> the CTE body output columns referenced by every inlined consumer (the + * consumer output slots mapped back to their producer slots). Filled while the main + * query is propagated top-down; the CTE producer subtree is propagated afterwards + * with exactly this column set, so a big CTE body (a deep TPCDS join stack) only + * keeps the columns its consumers actually read. + */ + private final Map<CTEId, Set<ExprId>> cteConsumerNeeds = new HashMap<>(); + /** + * CTE ids with at least one consumer that must keep every body column (see + * propagateNeed): a consumer under a NON-prunable node (e.g. a UNION branch) receives + * need = null, and without this obligation the producer was pruned to the OTHER + * consumer's columns alone while the union branch still emitted its y reference - + * an invalid frozen text that the creation probe accepted whenever an IN-list marker + * skipped validation. + */ + private final Set<CTEId> cteKeepAllConsumers = new HashSet<>(); + + /** + * Per-decompile generated-column-name state: when a decompiled output column has no + * clean user alias it is exported under a generated c_N name (c_1, c_2, ...), + * assigned in decompile order and memoized by the output ExprId so every reference + * to the same column prints the same alias. A fresh per-decompile sequence (instead + * of embedding the analyzer's ExprId) keeps the generated names small, readable and + * independent of how many internal ExprIds the optimizer allocated. + */ + private final Map<ExprId, String> generatedColumnNames = new HashMap<>(); + private int generatedColumnSeq = 0; + + /** + * Normalized names already visible in the CURRENT decompile: user aliases and the + * preserved source columns of the relations a generated name gets exported next to. + * A generated c_N must avoid them - the counter alone only keeps the + * GENERATED names apart, so a source column literally named c_1 (or a group-by + * item / user alias of that name) could end up next to sum(v) AS c_1 or + * MARK_SLOT c_1: two ExprIds registered under one visible name make the + * enclosing projection / result sink read an AMBIGUOUS column from the derived + * relation after reload. Project / window outputs repair duplicates afterwards + * (dedupeSelectOutputNames); the join (MARK_SLOT / explicit projection) and aggregate + * exports do not, so they reserve here instead. + */ + private final Set<String> reservedOutputNames = new HashSet<>(); + + /** + * Builds a renderer WITHOUT an under-lock partition-name snapshot (direct / test-side + * decompile): a pinned partition is then named from the live catalog. + */ + public SPMPlan2SQLBuilder() { + this(java.util.Map.of()); + } + + /** + * Builds a renderer carrying the partition names the CAPTURE resolved while the planning locks + * were held (see SPMOptimizer.OptimizeResult#getPartitionNames). + * + * @param partitionNames table id to (partition id to the ADMITTED name), or null + */ + public SPMPlan2SQLBuilder(Map<Long, Map<Long, String>> partitionNames) { + this.capturedPartitionNames = partitionNames == null + ? java.util.Map.of() : partitionNames; + } + + /** + * Rejects freezing when any expression of the plan carries a + * SessionVarGuardExpr (see containsSessionVarGuard): the guard holds the + * alias-UDF DEFINITION's saved session variables and has no SQL rendering. Every + * expansion of a definition with saved variables retains the guard (see + * AliasUdfBuilder), including creators whose variables already matched - the frozen + * text would otherwise re-analyze the arithmetic under the CALLER's settings. + * + * @param plan the physical plan about to be decompiled + */ + public static void rejectSessionVarGuardedExpressions(Plan plan) { + org.apache.doris.nereids.spm.SPMPlanTreeSupport.<RuntimeException>walkPlans(plan, node -> { + for (org.apache.doris.nereids.trees.expressions.Expression expr + : node.getExpressions()) { + if (containsSessionVarGuard(expr)) { + throw new UnsupportedOperationException("SPM cannot freeze an expression" + + " carrying a session-variable guard: " + expr); + } + } + }); + } + + /** + * Rejects freezing when any expression of the plan still carries a SUBQUERY. + * + * <p>This builder renders expressions with {@link SPMExprSqlBuilder}, which has no SQL + * rendering for a subquery: it emits the structural PSEUDO text + * {@code INSUBQUERY(compareExpr)[...]} / {@code EXISTS[...]} / {@code SCALARSUBQUERY[...]} + * (see SPMExprSqlBuilder#visitSubqueryExpr) - the digest form, not a query. Stored as frozen + * SQL that text is not the user's {@code IN (SELECT ...)}: it is an ordinary, unreserved + * function call, so a user alias UDF (or catalog function) of that name with compatible + * arguments made capture-time validation SUCCEED, the baseline was stored with + * {@code planFrozen = true}, and every replay evaluated the user's UDF / array access instead + * of the original subquery - returning different rows than the query it claims to replay + * (round-89 review). Rejecting here keeps the baseline on the parameterized-plan-tree path, + * which handles subqueries natively; the same refusal covers a plan whose subquery survives in + * a projection (scalar subquery) or a filter (IN / EXISTS). + * + * @param plan the physical plan about to be decompiled + */ + public static void rejectSubqueryExpressions(Plan plan) { + org.apache.doris.nereids.spm.SPMPlanTreeSupport.<RuntimeException>walkPlans(plan, node -> { + for (org.apache.doris.nereids.trees.expressions.Expression expr + : node.getExpressions()) { + if (containsSubqueryExpression(expr)) { + throw new UnsupportedOperationException("SPM cannot freeze an expression" + + " carrying a subquery (its SQL has no subquery rendering): " + expr); + } + } + }); + } + + /** + * Rejects freezing when the plan references a USER function under one of SPM's INTERNAL + * pseudo names (see {@link SPMExprSqlBuilder#INTERNAL_PSEUDO_FUNCTION_NAMES}). + * + * <p>Those names are reserved by SPM: they name the structural markers of the digest text, and + * a frozen SQL must never be readable as - or shadowed by - a user function of the same name. + * A user (or catalog) function that happens to carry one of them keeps the baseline on the + * parameterized-plan-tree path instead of producing text that means two different things. + * + * @param plan the physical plan about to be decompiled + */ + public static void rejectReservedInternalFunctionNames(Plan plan) { + org.apache.doris.nereids.spm.SPMPlanTreeSupport.<RuntimeException>walkPlans(plan, node -> { + for (org.apache.doris.nereids.trees.expressions.Expression expr + : node.getExpressions()) { + if (containsReservedInternalFunction(expr)) { + throw new UnsupportedOperationException("SPM cannot freeze an expression" + + " that calls the reserved internal name of a subquery marker: " + + expr); + } + } + }); + } + + private static boolean containsSubqueryExpression( + org.apache.doris.nereids.trees.expressions.Expression expr) { + if (expr instanceof org.apache.doris.nereids.trees.expressions.SubqueryExpr) { + return true; + } + for (org.apache.doris.nereids.trees.expressions.Expression child : expr.children()) { + if (containsSubqueryExpression(child)) { + return true; + } + } + return false; + } + + private static boolean containsReservedInternalFunction( + org.apache.doris.nereids.trees.expressions.Expression expr) { + if (expr instanceof Function) { + // the NAME alone reserves it: an internal marker must never be shadowed by (or + // confused with) a user function in ANY namespace + Function function = (Function) expr; + if (SPMExprSqlBuilder.INTERNAL_PSEUDO_FUNCTION_NAMES.contains( + function.getName().toLowerCase(java.util.Locale.ROOT))) { + return true; + } + } + for (org.apache.doris.nereids.trees.expressions.Expression child : expr.children()) { + if (containsReservedInternalFunction(child)) { + return true; + } + } + return false; + } + + private static boolean containsSessionVarGuard( + org.apache.doris.nereids.trees.expressions.Expression expr) { + if (expr instanceof org.apache.doris.nereids.trees.expressions.SessionVarGuardExpr) { + return true; + } + for (org.apache.doris.nereids.trees.expressions.Expression child : expr.children()) { + if (containsSessionVarGuard(child)) { + return true; + } + } + return false; + } + + /** + * Marks the OUTERMOST projection of the decompiled tree: the first PhysicalProject + * reached from the root along single-child pass-through nodes (ResultSink / Sort / + * Distribute / ...). Walking stops at an aggregate - an aggregate that feeds the + * result carries the final SELECT list itself, so there is no outermost projection + * and every projection below it is an intermediate one (full child output). + */ + private void markOutputProject(Plan plan) { + Plan current = plan; + while (current != null) { + if (current instanceof PhysicalProject) { + outputProjects.add(current); + return; + } + if (current instanceof PhysicalHashAggregate || current.arity() != 1) { + return; + } + current = current.child(0); + } + } + + // ==================== live-column analysis (dead-column pruning) ==================== + + /** Whether this subtree may be pruned by the live-column analysis. Non-linear + * decompile shapes (CTE bodies, set operations, recursive unions, grouping sets) + * are left untouched: their select lists are kept whole. */ + private static boolean isPrunableNode(Plan node) { + return node instanceof PhysicalProject + || node instanceof PhysicalWindow + || node instanceof PhysicalHashJoin + || node instanceof PhysicalNestedLoopJoin + || node instanceof PhysicalHashAggregate + || node instanceof PhysicalFilter + || node instanceof PhysicalTopN + || node instanceof PhysicalQuickSort + || node instanceof PhysicalLimit + || node instanceof PhysicalDistribute + || node instanceof PhysicalLazyMaterialize + || node instanceof PhysicalLazyMaterializeOlapScan + || node instanceof PhysicalPartitionTopN + || node instanceof PhysicalAssertNumRows + || node instanceof PhysicalResultSink + || node instanceof PhysicalCTEAnchor; + } + + /** Pre-analysis entry: fills neededOutputs top-down from the root. */ + private void computeNeeded(Plan root) { + neededOutputs.clear(); + cteConsumerNeeds.clear(); + cteKeepAllConsumers.clear(); + Set<ExprId> rootNeed = new HashSet<>(); + for (Slot slot : root.getOutput()) { + rootNeed.add(slot.getExprId()); + } + propagateNeed(root, rootNeed); + } + + /** + * Top-down live-column propagation. need is the set of output ExprIds of + * node that upper layers consume; null means "keep everything" (never prune + * below). Every parent hands each child the child's output columns that must stay + * alive: the columns the parent passes through and the columns the parent's own + * decompiled expressions reference. + */ + private void propagateNeed(Plan node, Set<ExprId> need) { + if (node == null) { + return; + } + if (node instanceof PhysicalCTEConsumer) { + // a CTE consumer has no children; record which body columns its live output + // columns map back to, so the producer subtree can be pruned to exactly them. + // need = null means "keep everything": the consumer sits under a non-prunable + // node (a UNION branch, a recursive union), so it must record a KEEP-ALL + // obligation - otherwise the producer was pruned to the OTHER consumers' + // columns while this consumer still referenced its own (see + // cteKeepAllConsumers). + PhysicalCTEConsumer consumer = (PhysicalCTEConsumer) node; + if (need == null) { + cteKeepAllConsumers.add(consumer.getCteId()); + return; + } + Set<ExprId> bodyNeeds = cteConsumerNeeds.computeIfAbsent( + consumer.getCteId(), k -> new HashSet<>()); + for (Slot slot : consumer.getOutput()) { + if (need.contains(slot.getExprId())) { + bodyNeeds.add(consumer.getProducerSlot(slot).getExprId()); + } + } + return; + } + if (need == null || !isPrunableNode(node)) { + // keep everything on this node and below (no pruning boundary) + for (Plan child : node.children()) { + propagateNeed(child, null); + } + return; + } + Set<ExprId> nodeNeed = new HashSet<>(need); + neededOutputs.put(node, nodeNeed); + + if (node instanceof PhysicalCTEAnchor) { + // child(0) is the CTE producer whose body every consumer inlines. The main + // query (child(1)) is propagated FIRST so every consumer records which body + // columns it reads; the body subtree is then pruned to exactly those columns. + // A body with no consumer (or one whose consumers never resolve) keeps every + // column. + PhysicalCTEAnchor<? extends Plan, ? extends Plan> anchor = + (PhysicalCTEAnchor<? extends Plan, ? extends Plan>) node; + if (anchor.child(1) != null) { + propagateNeed(anchor.child(1), nodeNeed); + } + Plan producer = anchor.child(0); + if (producer == null) { + return; + } + if (producer instanceof PhysicalCTEProducer) { + PhysicalCTEProducer<? extends Plan> cteProducer = + (PhysicalCTEProducer<? extends Plan>) producer; + Set<ExprId> bodyNeed = cteConsumerNeeds.get(cteProducer.getCteId()); + if (cteKeepAllConsumers.contains(cteProducer.getCteId())) { + // at least one consumer keeps every column: the body must NOT be + // pruned (a UNION branch's y reference would otherwise dangle) + propagateNeed(cteProducer.child(0), null); + } else if (bodyNeed != null && !bodyNeed.isEmpty()) { + propagateNeed(cteProducer.child(0), bodyNeed); + } else { + propagateNeed(cteProducer.child(0), null); + } + } else { + propagateNeed(producer, null); + } + return; + } + if (node instanceof PhysicalProject) { + propagateProjectNeed((PhysicalProject<? extends Plan>) node, nodeNeed); + } else if (node instanceof PhysicalHashJoin || node instanceof PhysicalNestedLoopJoin) { + propagateJoinNeed((AbstractPhysicalJoin<? extends Plan, ? extends Plan>) node, nodeNeed); + } else if (node instanceof PhysicalHashAggregate) { + propagateAggregateNeed((PhysicalHashAggregate<? extends Plan>) node, nodeNeed); + } else if (node instanceof PhysicalWindow) { + propagateWindowNeed((PhysicalWindow<? extends Plan>) node, nodeNeed); + } else if (node instanceof PhysicalFilter) { + PhysicalFilter<? extends Plan> filter = (PhysicalFilter<? extends Plan>) node; + Set<ExprId> childNeed = new HashSet<>(nodeNeed); + addExprSlots(filter.getPredicate(), childNeed); + propagateNeed(filter.child(0), childNeed); + } else if (node instanceof PhysicalTopN) { + PhysicalTopN<? extends Plan> topN = (PhysicalTopN<? extends Plan>) node; + Set<ExprId> childNeed = new HashSet<>(nodeNeed); + for (org.apache.doris.nereids.properties.OrderKey key : topN.getOrderKeys()) { + addExprSlots(key.getExpr(), childNeed); + } + propagateNeed(topN.child(0), childNeed); + } else if (node instanceof PhysicalQuickSort) { + PhysicalQuickSort<? extends Plan> sort = (PhysicalQuickSort<? extends Plan>) node; + Set<ExprId> childNeed = new HashSet<>(nodeNeed); + for (org.apache.doris.nereids.properties.OrderKey key : sort.getOrderKeys()) { + addExprSlots(key.getExpr(), childNeed); + } + propagateNeed(sort.child(0), childNeed); + } else { + // pure pass-through nodes (limit / distribute / lazy materialize / ...): + // their output slots are the child slots, so the same need flows down + for (Plan child : node.children()) { + propagateNeed(child, nodeNeed); + } + } + } + + /** PhysicalProject: live pass-through columns plus the columns referenced by the + * project's own expressions whose output is itself live. */ + private void propagateProjectNeed(PhysicalProject<? extends Plan> project, Set<ExprId> need) { + Plan child = project.child(0); + if (child == null) { + return; + } + Set<ExprId> childNeed = new HashSet<>(); + boolean finalProject = outputProjects.contains(project); + if (finalProject) { + // the outermost projection emits its full projection list: every referenced + // child column must stay alive + for (NamedExpression projectExpr : project.getProjects()) { + addExprSlots(projectExpr, childNeed); + } + } else { + // pass-through: the child columns that are still live above this projection + Set<ExprId> childOut = outputIdSet(child); + for (ExprId id : need) { + if (childOut.contains(id)) { + childNeed.add(id); + } + } + // plus the columns referenced by this projection's own live expressions + for (NamedExpression projectExpr : project.getProjects()) { + if (need.contains(projectExpr.getExprId())) { + addExprSlots(projectExpr, childNeed); + } + } + } + propagateNeed(child, childNeed); + } + + /** Join: the preserved output columns flow to the side that produces them; the + * hash / other / mark conjuncts are always decompiled, so every column they + * reference stays alive on its own side. */ + private void propagateJoinNeed(AbstractPhysicalJoin<? extends Plan, ? extends Plan> join, + Set<ExprId> need) { + Plan left = join.left(); + Plan right = join.right(); + if (left == null || right == null) { + return; + } + Set<ExprId> leftOut = outputIdSet(left); + Set<ExprId> rightOut = outputIdSet(right); + Set<ExprId> conjRefs = new HashSet<>(); + for (Expression conjunct : join.getHashJoinConjuncts()) { + addExprSlots(conjunct, conjRefs); + } + for (Expression conjunct : join.getOtherJoinConjuncts()) { + addExprSlots(conjunct, conjRefs); + } + for (Expression conjunct : join.getMarkJoinConjuncts()) { + addExprSlots(conjunct, conjRefs); + } + Set<ExprId> leftNeed = new HashSet<>(); + Set<ExprId> rightNeed = new HashSet<>(); + for (ExprId id : need) { + if (leftOut.contains(id)) { + leftNeed.add(id); + } + if (rightOut.contains(id)) { + rightNeed.add(id); + } + } + for (ExprId id : conjRefs) { + if (leftOut.contains(id)) { + leftNeed.add(id); + } + if (rightOut.contains(id)) { + rightNeed.add(id); + } + } + propagateNeed(left, leftNeed); + propagateNeed(right, rightNeed); + } + + /** Aggregate: the global stage keeps its whole output list (GROUP BY keys and + * aggregate functions), but the input columns its expressions reference must stay + * alive below. Local / intermediate execution stages are pass-through nodes. */ + private void propagateAggregateNeed(PhysicalHashAggregate<? extends Plan> agg, Set<ExprId> need) { + AggPhase phase = agg.getAggPhase(); + if (phase.isLocal() || isIntermediateAggStage(agg)) { + for (Plan child : agg.children()) { + propagateNeed(child, need); + } + return; + } + Plan child = agg.child(0); + if (child == null) { + return; + } + Set<ExprId> childNeed = new HashSet<>(); + for (Expression groupBy : agg.getGroupByExpressions()) { + addExprSlots(groupBy, childNeed); + } + for (NamedExpression output : agg.getOutputExpressions()) { + addAggregateOutputRefs(output, childNeed); + } + propagateNeed(child, childNeed); + } + + /** Window: live pass-through columns plus the input columns of the live window + * expressions. */ + private void propagateWindowNeed(PhysicalWindow<? extends Plan> window, Set<ExprId> need) { + Plan child = window.child(0); + if (child == null) { + return; + } + Set<ExprId> childNeed = new HashSet<>(); + Set<ExprId> childOut = outputIdSet(child); + for (ExprId id : need) { + if (childOut.contains(id)) { + childNeed.add(id); + } + } + for (NamedExpression windowExpr : window.getWindowExpressions()) { + if (need.contains(windowExpr.getExprId())) { + addExprSlots(windowExpr, childNeed); + } + } + propagateNeed(child, childNeed); + } + + /** The columns referenced by one global-aggregate output expression, with every + * local partial-buffer reference resolved down to its data columns (mirrors + * appendAggSelect / resolveBufferSlots so the pruned SELECT lists keep exactly the + * columns the decompiled aggregate prints). */ + private void addAggregateOutputRefs(NamedExpression output, Set<ExprId> out) { + Expression inner = output instanceof Alias ? ((Alias) output).child() : output; + if (inner instanceof SlotReference) { + // group-by key pass-through + out.add(((SlotReference) inner).getExprId()); + return; + } + if (inner instanceof AggregateExpression) { + AggregateExpression aggExpr = (AggregateExpression) inner; + List<Expression> args = aggExpr.getFunction().children().isEmpty() + ? new ArrayList<>(aggExpr.children()) : aggExpr.getFunction().children(); + for (Expression arg : args) { + addResolvedExprSlots(arg, out); + } + return; + } + addExprSlots(inner, out); + } + + /** Collects every slot of expr, resolving partial-buffer slots through + * localAggParams down to their data columns (mirrors resolveBufferSlots). */ + private void addResolvedExprSlots(Expression expr, Set<ExprId> out) { + if (expr instanceof SlotReference) { + Expression param = localAggParams.get(((SlotReference) expr).getExprId()); + if (param != null) { + addResolvedExprSlots(param, out); + return; + } + out.add(((SlotReference) expr).getExprId()); + return; + } + for (Expression childExpr : expr.children()) { + addResolvedExprSlots(childExpr, out); + } + } + + /** Output ExprId set of a plan node. */ + private static Set<ExprId> outputIdSet(Plan node) { + Set<ExprId> ids = new HashSet<>(); + for (Slot slot : node.getOutput()) { + ids.add(slot.getExprId()); + } + return ids; + } + + /** Adds every slot ExprId used by an expression. */ + private static void addExprSlots(Expression expr, Set<ExprId> out) { + if (expr == null) { + return; + } + collectAllSlotIds(expr, out); + } + + /** Pre-walk that fills localAggParams bottom-up so the live-column analysis + * (which runs before the decompile walk) can resolve partial-buffer references. The + * decompile walk re-fills the same map while it descends (harmless duplicate). */ + private void collectLocalAggParams(Plan node) { + for (Plan child : node.children()) { + collectLocalAggParams(child); + } + if (node instanceof PhysicalHashAggregate) { + PhysicalHashAggregate<? extends Plan> agg = (PhysicalHashAggregate<? extends Plan>) node; + if (agg.getAggPhase().isLocal() || isIntermediateAggStage(agg)) { + recordLocalAggStage(agg); + } + } + } + + /** Registers one local (partial) aggregate stage's buffer outputs (see the field + * comment of localAggParams). */ + private void recordLocalAggStage(PhysicalHashAggregate<? extends Plan> agg) { + for (NamedExpression output : agg.getOutputExpressions()) { + Expression inner = output instanceof Alias ? ((Alias) output).child() : output; + if (inner instanceof AggregateExpression && isPartialAggregate((AggregateExpression) inner)) { + Expression rawParam = extractPartialParam((AggregateExpression) inner); + if (agg.getGroupByExpressions().isEmpty() + && isDistinctMergeContribution(((AggregateExpression) inner).children())) { + distinctMergeBuffers.add(output.getExprId()); + } + Expression param = rawParam; + if (param == null) { + // count(*) has no data argument (extractPartialParam -> null). Map the + // buffer to the partial expression itself so the enclosing + // merge-finalize count(*) resolves its argument back to the star, which + // appendAggSelect collapses into count(*) (isNestedNoArgCount) - without + // this the raw buffer slot (named e.g. "partial_count(*)") would leak + // into the decompiled SQL as the invalid count(partial_count(*)). + param = inner; + } + while (param instanceof SlotReference) { + Expression resolved = localAggParams.get(((SlotReference) param).getExprId()); + if (resolved == null) { + break; + } + param = resolved; + } + localAggParams.put(output.getExprId(), param); + } + } + } + + /** + * Whether an output of an eliminated DISTINCT_LOCAL stage is the distinct-dedup + * contribution (see distinctMergeBuffers). + * + * The distinction has to be read from the aggregate expression's own children - + * the physical input of the buffer - because the merge function's argument is + * normalized to the data column for EVERY buffer: + * + * - merge-chain buffer (plain aggregate riding along): its input is another + * partial buffer, already recorded in localAggParams, or a count-star function + * with no argument at all; + * - distinct-dedup buffer: its input is the dedup KEY data column, either as the + * bare slot (partial_count(key)) or wrapped as the partial function's argument + * (count(key)). + */ + private boolean isDistinctMergeContribution(List<Expression> exprChildren) { + if (exprChildren.isEmpty()) { + return false; + } + Expression bufferArg = exprChildren.get(0); + if (bufferArg instanceof SlotReference) { + return !localAggParams.containsKey(((SlotReference) bufferArg).getExprId()); + } + List<Expression> argChildren = bufferArg.children(); + if (argChildren.isEmpty()) { + // e.g. the count(*) star buffer: raw-row counting, never the distinct merge + return false; + } + for (Expression child : argChildren) { + if (!(child instanceof SlotReference) + || localAggParams.containsKey(((SlotReference) child).getExprId())) { + return false; + } + } + return true; + } + + /** The live column filter for one explicit SELECT list: the list a node emits is + * pruned to the node's needed output columns (no entry in the map, or a null need, + * keeps the whole list - e.g. mock plan trees and unpruned subtrees). */ + private void filterLiveSelects(Plan node, List<Pair<ExprId, String>> selects) { + Set<ExprId> need = neededOutputs.get(node); + if (need == null) { + return; + } + selects.removeIf(p -> !need.contains(p.key())); + } + + /** + * Decompile entry: physical plan -> planSql. + * + * @param plan the optimal physical plan + * @return planSql (standard SQL text) + */ + public String toSQL(Plan plan) { + // An alias-UDF expansion computed under the DEFINITION's stored session + // variables (decimalOverflowScale / enable_decimal256 / ...) carries a + // SessionVarGuardExpr; the SQL text has no way to express that guard, so + // printing only its child would replan the arithmetic under the LATER caller's + // variables and could change its type, scale or value while the same bind SQL + // still matches. Reject freezing instead (CREATE keeps the user planSql / + // falls back to the parameterized-plan-tree path). + rejectSessionVarGuardedExpressions(plan); + // A residual SUBQUERY has no SQL rendering here (SPMExprSqlBuilder emits the digest + // pseudo form, which a user function of the same name could legally satisfy), and SPM's + // pseudo names are reserved - both are refusals, so the baseline stays on the + // parameterized-plan-tree path (see rejectSubqueryExpressions). + rejectSubqueryExpressions(plan); + rejectReservedInternalFunctionNames(plan); + // reset the per-decompile alias / generated-name sequences: t_N and c_N only + // need to be unique WITHIN the one produced SQL, so numbering restarts here and + // the decompiled text stays compact across calls + SQLRelation.resetAliasCounter(); + cteBodies.clear(); + cteAliases.clear(); + cteDefinitions.clear(); + generatedColumnNames.clear(); + generatedColumnSeq = 0; + reservedOutputNames.clear(); + lateralViewSeq = 0; + outputProjects.clear(); + localAggParams.clear(); + distinctMergeBuffers.clear(); + markOutputProject(plan); + collectLocalAggParams(plan); + computeNeeded(plan); + SQLRelation relation = plan.accept(this, null); + // attach the collected CTE definitions (WITH) to the outermost relation: they + // are collected in producer dependency order and are visible to the whole + // statement, which is exactly the scope a CTE anchor binds + if (!cteDefinitions.isEmpty()) { + List<String> merged = relation.getCte() == null + ? new ArrayList<>() : new ArrayList<>(relation.getCte()); + merged.addAll(cteDefinitions); + relation.setCte(merged); + } + // PhysicalAssertNumRows carries no node of its own in the frozen text: it renders + // as the ASSERT_ROWS relation prefix wherever its parent references the input + // relation (visitPhysicalAssertNumRows), and the parser rebuilds the assertion. + // + // At the ROOT there is no parent to consume that prefix (round-83 #4): toSQL() of the + // relation never renders assertRows, so `SELECT * FROM ASSERT_ROWS (SELECT ...) a` + // froze as an ordinary filtered SELECT - CREATE's probe planned it happily and an + // identical replay returned BOTH rows where native execution raises the row-count + // error. The boundary is therefore materialized HERE, in the only statement form the + // grammar has for it: the ASSERT_ROWS relation under a plain SELECT *. + if (relation.isAssertRows()) { + return "SELECT * FROM " + relation.toRelationSQL(); + } + return relation.toSQL(); + } + + /** + * Handles a child node. + * + * @param plan child physical plan + * @return SQLRelation of the child plan + */ + private SQLRelation process(Plan plan) { + return plan.accept(this, null); + } + + // ==================== default: unsupported operators ==================== + + @Override + public SQLRelation visit(Plan plan, Void context) { + throw new UnsupportedOperationException( + "SPMPlan2SQLBuilder does not support plan: " + plan.getClass().getSimpleName()); + } + + // ==================== pass-through mode ==================== + /** + * PhysicalStorageLayerAggregate: a scan-shaped shortcut that returns COUNT / MIN / MAX + * for the wrapped scan from table or footer metadata instead of reading the data. + * AggregateStrategies keeps the enclosing aggregate (or the constant-only project) on + * TOP of the shortcut and keeps every expression in terms of the wrapped relation's + * slots, so decompiling the wrapped relation publishes exactly those slots and the + * enclosing operators render the same SQL aggregate (count(*) / min(x) / ...) over the + * same table. Replaying that SQL re-derives an equivalent plan; there is no clause that + * describes the shortcut itself and none is needed, because the shortcut is an + * execution strategy of the aggregate rather than a different result. + */ + @Override + public SQLRelation visitPhysicalStorageLayerAggregate( + PhysicalStorageLayerAggregate storageLayerAggregate, Void context) { + return visitPhysicalRelation(storageLayerAggregate.getRelation(), context); + } + + /** + * PhysicalDistribute: a data exchange node with no SQL equivalent; returns the child. + */ + @Override + public SQLRelation visitPhysicalDistribute(PhysicalDistribute<? extends Plan> distribute, Void context) { + return process(distribute.child(0)); + } + + /** + * PhysicalLazyMaterialize: an optimizer lazy-column-materialization wrapper with no + * SQL equivalent; returns the child. + */ + @Override + public SQLRelation visitPhysicalLazyMaterialize( + PhysicalLazyMaterialize<? extends Plan> lazy, Void context) { + return process(lazy.child(0)); + } + + /** + * PhysicalLazyMaterializeOlapScan: an OlapScan wrapped with lazy column + * materialization; decompiled as a normal scan. + */ + @Override + public SQLRelation visitPhysicalLazyMaterializeOlapScan( + PhysicalLazyMaterializeOlapScan scan, Void context) { + return visitPhysicalRelation(scan, context); + } + + /** + * PhysicalLazyMaterializeFileScan: a file scan wrapped with lazy column + * materialization; decompiled as a normal scan (including its scan modifiers - + * the wrapper subclasses PhysicalFileScan, so the TABLESAMPLE / snapshot / scan + * parameter rendering applies unchanged). + */ + @Override + public SQLRelation visitPhysicalLazyMaterializeFileScan( + PhysicalLazyMaterializeFileScan scan, Void context) { + return visitPhysicalRelation(scan, context); + } + + /** + * PhysicalResultSink (and sinks in general): result collection nodes with no SQL + * equivalent; passed through. For the RESULT sink the final output column ORDER is + * forced to the sink's output list (the user SELECT order) - the physical aggregate + * / projection below may emit columns in a different order (e.g. group-by keys + * before aggregates), which would reorder the user-visible result columns. + */ + @Override + public SQLRelation visitPhysicalSink(PhysicalSink<? extends Plan> sink, Void context) { + if (sink instanceof PhysicalResultSink) { + SQLRelation child = process(sink.child(0)); + List<Slot> outputs = sink.getOutput(); + if (outputs.isEmpty()) { + return child; + } + // Final output columns in the USER SELECT order. Each output column is + // emitted as its in-scope reference (child.getColumnNames()), and - when the + // reference is a decompile-internal alias (c_N) that hides the original + // column label - re-labelled with the ResultSink output slot's name + // (output.getName()): that label is exactly what a normal execution of the + // original query shows in the result header (a plain alias such as + // "d_week_seq1", a table column name, or the expression text of an + // un-aliased expression column), so the frozen planSql keeps the SAME output + // column names as the original SQL (SR model: the final SELECT list is + // driven by the logical query's output columns, not by the internal c_N + // aliases the decompiler had to mint for unambiguous references). + List<Pair<ExprId, String>> ordered = new ArrayList<>(); + boolean anyRenamed = false; + for (Slot output : outputs) { + String ref = child.getColumnNames().get(output.getExprId()); + if (ref == null) { + ref = output.getName(); + } + String display = output.getName(); + if (display == null || display.isEmpty() || display.equals(ref)) { + ordered.add(Pair.of(output.getExprId(), ref)); + continue; + } + // Re-expose the column under its original label: "c_3 AS d_week_seq1" + // (or "AS `round(...)`" for an un-aliased expression column, whose header + // text is the expression itself). The quoted name never participates in + // name resolution of the frozen SQL body, so quoting is always safe. + ordered.add(Pair.of(output.getExprId(), ref + " AS " + quoteIdentifier(display))); + anyRenamed = true; + } + if (child.getRelationName() == null) { + // inline relation (plain table scan): SELECT * renders in the table + // schema order and the ResultSink output follows the scan order; + // nothing to reorder. + return child; + } + if (child.getSelects().isEmpty()) { + // SELECT * over a wrapped subquery (TopN/Sort wrapper whose FROM is a + // subquery): the columns are referenceable, so rewrite the outer SELECT + // list to the user column order in place (preserving ORDER BY / LIMIT) - + // UNLESS a re-labelled alias would SHADOW a name the ORDER BY references + // "c_3 AS b" next to "ORDER BY b" rebinds the sort to the + // alias although the clause was rendered against the base column b. Then + // the relabel moves to the wrapper below, where the clause keeps its own + // query block and the aliases cannot capture it. + String inPlaceOrderBy = child.getOrderBy(); + if (inPlaceOrderBy.isEmpty() + || !orderByShadowedByRelabel(child, inPlaceOrderBy, ordered)) { + child.setSelects(ordered); + return child; + } + } + // Explicit projection already emitted (e.g. a bare aggregate + // "sum(...) AS revenue" or a pass-through projection). Overwriting it in + // place would replace the expression with a bare name that is not resolvable + // in the FROM scope, so: + // - if the emitted columns already carry the original labels in the user + // SELECT order, keep the projection untouched; + // - otherwise wrap the child in a subquery and select the ordered + // (re-labelled) columns from it. + if (!anyRenamed && sameExprIdOrder(child.getSelects(), ordered)) { + return child; + } + SQLRelation outer = new SQLRelation(); + String alias = outer.newAlias(); + // A TOP-LEVEL ORDER BY / LIMIT pair is a semantic user clause: matching + // deliberately ignores its LIMIT value, and mergeLimits adopts the user's value + // by position - but a limit left INSIDE the derived table can never be reached + // by that positional merge (the frozen root would have no Limit node next to + // the user's Limit), so a matched LIMIT 200 query kept the captured 100-row + // cap. This wrapper is a PURE output relabelling (it neither filters nor + // aggregates), so hoisting the pair onto it is semantically identical and + // makes the frozen root a Limit node again. + // The ORDER BY moves WITH the LIMIT: a derived-table ORDER BY WITHOUT its + // LIMIT is only a hint the optimizer is free to drop, and the outer SELECT + // would then return an arbitrary LIMIT slice (a q02-style query replayed as + // unordered rows). Clear both BEFORE rendering the child text - toSQL() + // captures them into the string. + String sinkOrderBy = child.getOrderBy(); + String sinkLimit = child.getLimit(); + if (!sinkOrderBy.isEmpty() || !sinkLimit.isEmpty()) { + // Independently of the LIMIT: "SELECT a FROM t ORDER BY b + 1" + // (no LIMIT at all) arrives here as a Sort under the final relabel wrapper, + // and leaving the ORDER BY inside the derived table was NOT safe - the + // frozen text is re-planned at replay, and a sort that the user asked for + // but that sits one level down came back as unordered rows (Nereids drops + // an inner sort it considers redundant). The wrapper is a pure output + // relabelling, so the user clause belongs on it. Hidden sort keys the + // child's SELECT list does not export are added to it first (see + // hoistableOrderBy); a key that cannot be exported, or that a relabelled + // wrapper alias would capture, keeps the clause inside the child - its own + // query block still resolves it. ORDER BY and LIMIT + // always move TOGETHER: a limit without its order picks arbitrary rows. + String hoisted = sinkOrderBy.isEmpty() ? "" + : hoistableOrderBy(child, sinkOrderBy, ordered, true); + if (hoisted != null) { + outer.setOrderBy(hoisted); + outer.setLimit(sinkLimit); + child.setOrderBy(""); + child.setLimit(""); + } + } + // A relabelled ASSERT_ROWS child keeps its assertion (round-85): toSQL() of the + // relation never renders the relation PREFIX (only toRelationSQL does), so the + // wrapper used to drop the single-row assertion of + // `SELECT * FROM ASSERT_ROWS (SELECT k+1 FROM t WHERE k>0) a` - CREATE's probe planned + // the plain SELECT happily and an identical replay returned BOTH rows where native + // execution raises the row-count error. The relation prefix is the only statement + // form the grammar has for it, so it is rendered HERE with this wrapper's alias. + outer.setFrom((child.isAssertRows() + ? "ASSERT_ROWS (" + child.toSQL() + ") " + : "(" + child.toSQL() + ") ") + alias); + outer.setSelects(ordered); + return outer; + } + return visit((Plan) sink, context); + } + + /** Whether the projection ExprIds appear in the same order as ordered. */ + private static boolean sameExprIdOrder(List<Pair<ExprId, String>> projection, + List<Pair<ExprId, String>> ordered) { + if (projection.size() != ordered.size()) { + return false; + } + for (int i = 0; i < projection.size(); i++) { + if (projection.get(i).key() != ordered.get(i).key()) { + return false; + } + } + return true; + } + + /** + * Quotes an identifier for use as executable SQL text whenever it is not a plain + * unquotable identifier: a column named a-b must be emitted as `a-b`, + * otherwise the frozen projection re-parses as the subtraction a - b. A name that + * looks plain can still be a RESERVED keyword (a legal quoted column named + * from must not be emitted bare - the parser tokenizes that as the FROM + * keyword rather than an identifier), so the keyword check decides as well. + * Embedded backticks are doubled. Unquotable names stay verbatim, so ordinary + * schemas keep byte-identical frozen SQL. Also used for result-column labels (the + * expression text of an un-aliased output column such as + * round((sun_sales1 / sun_sales2), 2) is wrapped so the frozen planSql can + * carry the original column header verbatim). + */ + public static String quoteIdentifier(String name) { + if (name == null) { + return null; + } + if (name.matches("[A-Za-z_][A-Za-z0-9_]*") && NereidsParser.isValidUnquotedIdentifier(name)) { + return name; + } + return "`" + name.replace("`", "``") + "`"; + } + + /** + * Quotes every dot-separated component of a (possibly) qualified metadata name + * (catalog.db.table), so a table whose name is not a plain identifier (`my-table`) + * is still emitted as an identifier reference rather than as an expression. + */ + static String quoteQualifiedName(String name) { + if (name == null || name.isEmpty()) { + return name; + } + String[] parts = name.split("\\.", -1); + StringBuilder sb = new StringBuilder(name.length() + 4); + for (int i = 0; i < parts.length; i++) { + if (i > 0) { + sb.append('.'); + } + sb.append(quoteIdentifier(parts[i])); + } + return sb.toString(); + } + + /** + * Fully-qualified name of a table with every COMPONENT quoted separately + * (catalog.db.table). getNameWithFullQualifiers() FLATTENS a legal quoted + * component such as `t.a` into "internal.db.t.a", and splitting that on every dot + * would emit FOUR identifiers instead of the intended three-part name with `t.a` + * quoted as ONE component - a manually created frozen baseline carrying that broken + * text then fails re-analysis after a reload, and no raw fallback tree exists for a + * frozen row. The metadata components are taken structurally, never re-split. + */ + static String quoteQualifiedTableName(org.apache.doris.catalog.TableIf table) { + StringBuilder sb = new StringBuilder(); + for (String component : table.getFullQualifiers()) { + if (sb.length() > 0) { + sb.append('.'); + } + sb.append(quoteIdentifier(component)); + } + return sb.toString(); + } + + // ==================== Scan (wrapped as subquery or inline) ==================== + + /** + * PhysicalRelation (PhysicalOlapScan / PhysicalFileScan, etc.): table scan. + * + * M1 simplification: the scan output columns are registered to columnNames by their + * real column names and from is inlined as the table name (not wrapped). The + * predicate is handled by the parent PhysicalFilter. + */ + @Override + public SQLRelation visitPhysicalRelation(PhysicalRelation relation, Void context) { + if (!(relation instanceof PhysicalCatalogRelation)) { + throw new UnsupportedOperationException( + "SPMPlan2SQLBuilder does not support relation: " + relation.getClass().getSimpleName()); + } + PhysicalCatalogRelation catalogRelation = (PhysicalCatalogRelation) relation; + // A TEMPORARY table's catalog object carries the CREATOR session's internal name + // (<sessionId>_#TEMP#_<name>), not the text the user typed. Emitting it into the + // frozen planSql would persist a session-scoped identifier: another session + // running the same "FROM t" text matches the same bind key (catalog.db.t), and + // Database.getTableNullable accepts the already-marked internal name unchanged, + // so the replay would read the CREATOR's (possibly still live) temporary table + // instead of its own t. Never render it - the GLOBAL create / capture path + // rejects temporary relations before freezing (SPMPlanner), and a SESSION-scope + // freeze (where the session's own temp table is the intended target) falls back + // to the raw user text instead. + if (catalogRelation.getTable().isTemporary()) { + throw new UnsupportedOperationException( + "SPMPlan2SQLBuilder does not support temporary tables: the physical relation" + + " carries the creator session's internal name"); + } + SQLRelation sqlRelation = new SQLRelation(); + // Emit the fully qualified name (catalog.db.table) so the frozen planSql resolves + // the same table when it is replayed from a session whose current database (or + // catalog) differs from the one used at CREATE time (cross-db queries, + // information_schema, ...). Tables without a database (e.g. FunctionGenTable) + // keep the bare name. Every COMPONENT is backtick-quoted separately when it is + // not a plain identifier, so a metadata name containing operators is re-parsed + // as an identifier instead of an expression, and a legal quoted component such + // as `t.a` keeps its boundary (see quoteQualifiedTableName). Scan modifiers + // (partition selection, TABLESAMPLE, snapshot, scan parameters) follow the name + // in grammar order. + String table = catalogRelation.getTable().getDatabase() == null + ? quoteIdentifier(catalogRelation.getTable().getName()) + : quoteQualifiedTableName(catalogRelation.getTable()); + sqlRelation.setFrom(table + renderScanModifiers(relation)); + // Remember WHICH table this scan reads: two occurrences of one table are a self + // join even when their FROM texts differ (each occurrence may carry its own + // PARTITION / TABLESAMPLE pin), and the join must wrap both sides then. + sqlRelation.setRelationIdentity(table); + // Register output columns: ExprId -> real column name. Internal system columns + // (e.g. rowid columns a join may request from the scan) are execution details + // and are never registered so they cannot leak into projections / ON clauses. + for (Slot slot : relation.getOutput()) { + if (isSystemColumnName(slot.getName())) { + continue; + } + // registered as executable SQL text: a special-character column (`a-b`) + // must be backtick-quoted, otherwise a frozen projection SELECT a-b + // re-parses as the subtraction a - b and returns a different value + sqlRelation.registerRef(slot.getExprId(), quoteIdentifier(slot.getName())); + } + return sqlRelation; + } + + // ==================== table-valued functions ==================== + + /** + * PhysicalTVFRelation: a table-valued function in FROM (e.g. + * numbers('number' = '5')). The function's own SQL text is used because a TVF + * argument list is a property list, not a normal expression list; the output + * columns keep their names. + */ + @Override + public SQLRelation visitPhysicalTVFRelation(PhysicalTVFRelation tvfRelation, Void context) { + SQLRelation relation = new SQLRelation(); + relation.setFrom(renderTableValuedFunction(tvfRelation.getFunction())); + for (Slot slot : tvfRelation.getOutput()) { + relation.registerRef(slot.getExprId(), quoteIdentifier(slot.getName())); + } + return relation; + } + + /** + * Renders one TVF call safely. TableValuedFunction.computeToSql() concatenates each + * concrete key/value between apostrophes WITHOUT escaping, so a valid property such + * as an S3 object key containing an apostrophe or backslash would freeze malformed + * SQL: with a placeholder-bearing predicate the row is classified as frozen, no + * fallback tree is rebuilt, and after refresh/restart the baseline silently stops + * applying. The property map is serialized in a deterministic key order with the + * same default-mode-safe quoting as every other SPM-emitted string literal (the + * stored text is always re-parsed under MODE_DEFAULT). + */ + private static String renderTableValuedFunction(TableValuedFunction function) { + String args = new TreeMap<>(function.getTVFProperties().getMap()).entrySet().stream() + .map(kv -> quoteSqlString(kv.getKey()) + " = " + quoteSqlString(kv.getValue())) + .collect(Collectors.joining(", ")); + return quoteIdentifier(function.getName()) + "(" + args + ")"; + } + + /** PhysicalLazyMaterializeTVFScan: a TVF scan wrapped by lazy materialization. */ + @Override + public SQLRelation visitPhysicalLazyMaterializeTVFScan( + PhysicalLazyMaterializeTVFScan scan, Void context) { + return visitPhysicalTVFRelation(scan, context); + } + + /** + * Renders the scan modifiers that the frozen SQL must carry, in the order the grammar + * accepts them after the table name + * (optScanParams, materializedViewName, tableSnapshot, specifiedPartition, sample): + * + * olap scans: @paramType(...) parameters (binlog reads), the partition list + * when the scan reads a strict non-empty subset of the table partitions, and + * TABLESAMPLE; + * file scans: @paramType(...) parameters, FOR VERSION/TIME AS OF + * snapshots and TABLESAMPLE. + * + * Dropping any of them would silently change what the frozen planSql reads: a + * "FROM t PARTITION(p1)" baseline would replay over every partition, a snapshot read + * would run against the moving head of the table, and a sampled scan would return the + * full table. + * + * The partition list is emitted only when the user pinned it (a pruned scan re-derives + * its selection by replay); a frozen text without the pin simply does not match the + * pinned user query (a safe miss, never a replay over the wrong partitions). + * + * Two scan states are deliberately NOT emitted. The selected index is an optimizer + * choice (a rollup is a consistent copy, so the choice carries no semantics) that + * cannot be told apart from a user-written INDEX clause; freezing it would pin the + * optimization and stop the plain user query from matching. A user-written INDEX + * pin only survives in the user tree, so such queries never match a frozen text that + * dropped the pin. + * + * A user-written INDEX pin is NOT lost to this asymmetry (round-54 #2): the pin is a + * SEMANTIC choice (on an aggregate-key table the forced rollup returns one aggregated + * row per rollup key while the base table returns one per record), the matching key + * carries it (UnboundRelation#toDigest renders "INDEX <name>", so only callers + * with the same pin match), and this method cannot reproduce it. The CREATE therefore + * declines the FREEZE for a statement that pins an index at all + * (SPMPlanTreeSupport#pinsExplicitIndex): the user planSql is kept, plan_frozen stays + * false, and the rewrite replays the parameterized tree, whose own analysis re-applies + * the pin - so the frozen-text path below is never asked to render one. + */ + private String renderScanModifiers(PhysicalRelation relation) { + StringBuilder modifiers = new StringBuilder(); + if (relation instanceof PhysicalOlapScan) { + PhysicalOlapScan scan = (PhysicalOlapScan) relation; + modifiers.append(renderScanParams(scan.getScanParams())); + modifiers.append(renderPartitionSelection(scan)); + modifiers.append(renderTabletSelection(scan)); + modifiers.append(renderTableSample(scan.getTableSample())); + } else if (relation instanceof PhysicalFileScan) { + PhysicalFileScan scan = (PhysicalFileScan) relation; + modifiers.append(renderScanParams(scan.getScanParams())); + modifiers.append(renderTableSnapshot(scan.getTableSnapshot())); + modifiers.append(renderTableSample(scan.getTableSample())); + } + return modifiers.toString(); + } + + /** + * OLAP partition selection: the ids of a user-written PARTITION(...) / + * TEMPORARY PARTITION(...) list are frozen as that very clause - including + * when the pin happens to cover every partition that exists right now (a cardinality + * test would drop the clause and a later ADD PARTITION would let the pinned query + * silently read the new partition) and including the temporary namespace (a temp pin + * replayed as a formal PARTITION(name) binds the wrong partition or fails to bind). + * Partition pruning also shrinks selectedPartitionIds without any user pin, + * so only the manual provenance is ever rendered; a pruned scan re-derives its + * selection by replay. Ids are sorted so the frozen text is deterministic (the + * matcher compares the selection as a set). + */ + private String renderPartitionSelection(PhysicalOlapScan scan) { + List<Long> pinnedIds = scan.getManuallySpecifiedPartitions(); + if (pinnedIds.isEmpty()) { + return ""; + } + OlapTable table = scan.getTable(); + List<Long> sortedIds = new ArrayList<>(pinnedIds); + Collections.sort(sortedIds); + boolean temporary = table.isTemporaryPartition(sortedIds.get(0)); + StringBuilder partition = new StringBuilder(temporary ? " TEMPORARY PARTITION(" : " PARTITION("); + for (int i = 0; i < sortedIds.size(); i++) { + if (i > 0) { + partition.append(", "); + } + if (table.isTemporaryPartition(sortedIds.get(i)) != temporary) { + throw new UnsupportedOperationException( + "SPM decompile: a partition pin mixing temporary and formal partitions" + + " has no single-clause rendering"); + } + long partitionId = sortedIds.get(i); + Partition partitionMeta = table.getPartition(partitionId); + Map<Long, String> capturedNames = capturedPartitionNames.get(table.getId()); + String capturedName = capturedNames == null ? null : capturedNames.get(partitionId); + if (capturedName != null) { + // The ADMITTED name wins (round-86): the applied pin is a SET OF IDS, while the + // stored bind text (and every later caller matching it) names the partition it + // wrote. Reading the LIVE name here would freeze a `RENAME PARTITION` that landed + // between the capture and this render, so an identical caller pinning the OLD + // name - now a different, newly added partition - would be answered from the + // renamed one. A partition whose live name already moved makes the CREATE decline + // the freeze instead of freezing a text the bind cannot describe. + if (partitionMeta == null || !capturedName.equals(partitionMeta.getName())) { + throw new UnsupportedOperationException( + "SPM decompile: the pinned partition " + partitionId + " of table " + + table.getName() + " was renamed / dropped after the capture" + + " ('" + capturedName + "' is the admitted name); keeping" + + " the user planSql so the replay re-resolves the pin"); + } + partition.append(quoteIdentifier(capturedName)); + continue; + } + if (partitionMeta == null) { + throw new UnsupportedOperationException( + "SPM decompile: the pinned partition " + partitionId + " of table " + + table.getName() + " no longer exists and the capture did not" + + " snapshot its name"); + } + partition.append(quoteIdentifier(partitionMeta.getName())); + } + return partition.append(')').toString(); + } + + /** + * OLAP tablet pin: TABLET(id, ...) is frozen when the user wrote it. Bucket + * pruning also fills selectedTabletIds, so only the manual provenance is + * rendered; without the clause a replayed scan would read every tablet of the + * selected partitions and could return rows the captured query excluded. Ids are + * sorted (the matcher compares the tablet list as a set). + */ + private static String renderTabletSelection(PhysicalOlapScan scan) { + List<Long> pinnedIds = scan.getManuallySpecifiedTabletIds(); + if (pinnedIds.isEmpty()) { + return ""; + } + List<Long> sortedIds = new ArrayList<>(pinnedIds); + Collections.sort(sortedIds); + StringBuilder tablet = new StringBuilder(" TABLET("); + for (int i = 0; i < sortedIds.size(); i++) { + if (i > 0) { + tablet.append(", "); + } + tablet.append(sortedIds.get(i)); + } + return tablet.append(')').toString(); + } + + /** + * TABLESAMPLE(n PERCENT | n ROWS) [REPEATABLE seed]: both olap and file scans keep the + * user's sample. Dropping it would replay over the full table and return rows the + * captured plan never sampled in. + */ + private static String renderTableSample(Optional<TableSample> tableSample) { + if (!tableSample.isPresent()) { + return ""; + } + TableSample sample = tableSample.get(); + StringBuilder modifiers = new StringBuilder(" TABLESAMPLE(") + .append(sample.sampleValue) + .append(sample.isPercent ? " PERCENT)" : " ROWS)"); + if (sample.seek >= 0) { + modifiers.append(" REPEATABLE ").append(sample.seek); + } + return modifiers.toString(); + } + + /** + * FOR VERSION AS OF / FOR TIME AS OF: a time-travel read must stay pinned to the + * captured version, otherwise the replay reads the current table contents. A numeric + * version is emitted as a literal, every other value (and all times) as a string. + */ + private static String renderTableSnapshot(Optional<TableSnapshot> tableSnapshot) { + if (!tableSnapshot.isPresent()) { + return ""; + } + TableSnapshot snapshot = tableSnapshot.get(); + if (snapshot.getType() == TableSnapshot.VersionType.TIME) { + return " FOR TIME AS OF " + quoteSqlString(snapshot.getValue()); + } + String value = snapshot.getValue(); + if (value.matches("[0-9]+")) { + return " FOR VERSION AS OF " + value; + } + return " FOR VERSION AS OF " + quoteSqlString(value); + } + + /** + * The @paramType(...) read parameters (incremental / branch / tag / options / + * snapshot / reset): the map form when the parameters carry key/value pairs, otherwise + * the bare identifier list form. Dropping them would replay a different (e.g. + * non-incremental) read than the captured one. + */ + private static String renderScanParams(Optional<TableScanParams> scanParams) { + if (!scanParams.isPresent()) { + return ""; + } + TableScanParams params = scanParams.get(); + StringBuilder modifiers = new StringBuilder(" @").append(params.getParamType()).append('('); + Map<String, String> mapParams = params.getMapParams(); + if (!mapParams.isEmpty()) { + boolean first = true; + for (Map.Entry<String, String> param : mapParams.entrySet()) { + if (!first) { + modifiers.append(", "); + } + first = false; + modifiers.append(quoteIdentifier(param.getKey())) + .append(" = ") + .append(quoteSqlString(param.getValue())); + } + } else { + List<String> listParams = params.getListParams(); + for (int i = 0; i < listParams.size(); i++) { + if (i > 0) { + modifiers.append(", "); + } + modifiers.append(quoteIdentifier(listParams.get(i))); + } + } + return modifiers.append(')').toString(); + } + + /** + * A single-quoted SQL string literal: embedded single quotes are doubled AND + * backslashes are doubled, so the value cannot terminate the literal, change the frozen + * SQL structure, or decode to a DIFFERENT value. The DEFAULT sql_mode treats a backslash + * as an escape introducer (a semantic value such as release\next would otherwise + * reparse as release + newline + ext under that mode and select another external ref), + * so the literal doubles it; the SPM re-parses pin the DEFAULT mode (see + * SPMPlanner.parseStoredSelect), which makes the round trip exact under default AND + * NO_BACKSLASH_ESCAPES sessions alike. + */ + static String quoteSqlString(String value) { + return "'" + value.replace("\\", "\\\\").replace("'", "''") + "'"; + } + + // ==================== Generate (LATERAL VIEW) ==================== + + /** + * PhysicalGenerate: LATERAL VIEW clauses over the child relation - one clause per + * generator. The parser wraps every user-written LATERAL VIEW ... into its + * own single-generator node, while MergeGenerates (for two independent + * views) folds stacked nodes into one node carrying several generators; the + * executor rolls several functions over each child row, i.e. a cartesian expansion, + * which is exactly what stacked LATERAL VIEWs express (MergeGenerates only merges + * when the upper view does not reference the lower view's output). LATERAL VIEW + * clauses attach to the child's COMPLETE query block: the child's WHERE / GROUP BY / + * HAVING / ORDER BY / LIMIT clauses must stay inside the lateral-view input (a + * derived table with LIMIT 10 limits the input, not the exploded rows). The + * generator output columns are registered on the same relation so parent operators + * can reference them; the alias is taken from the output slot's qualifier when it + * survived analysis, otherwise a per-decompile lv_N alias is used. Generate + * conjuncts (if any) are appended to the relation's WHERE. + */ + @Override + public SQLRelation visitPhysicalGenerate(PhysicalGenerate<? extends Plan> generate, Void context) { + SQLRelation childRelation = process(generate.child(0)); + List<Function> generators = generate.getGenerators(); + List<Slot> outputs = generate.getGeneratorOutput(); + if (generators.isEmpty() || generators.size() != outputs.size()) { + // post-binding plans keep exactly one output slot per generator (multi-column + // generators carry their columns in the expand alias project above) + throw new UnsupportedOperationException("SPM decompile generate: generator/output arity mismatch " + + generators.size() + "/" + outputs.size()); + } + // The LATERAL VIEW must attach to the child's COMPLETE query block. Attaching it + // to the bare FROM fragment (getFrom()) would keep the child's WHERE / GROUP BY / + // HAVING / ORDER BY / LIMIT clauses on the OUTER relation, where they apply AFTER + // the explode: a derived table with LIMIT 10 would limit the exploded rows + // instead of the lateral-view input, a GROUP BY would regroup the generator + // output, and frozen replay could return rows the captured plan filtered out. + // A FROM-less child (e.g. LATERAL VIEW over "SELECT 1 AS x") needs the wrapper + // for the same reason. + SQLRelation relation; + String baseSql; + if (childRelation.getFrom().isEmpty() || childRelation.hasOwnBlock()) { + if (childRelation.getRelationName() == null) { + childRelation.newAlias(); + } + baseSql = childRelation.toRelationSQL(); + // the wrapper carries the child's column mapping only; the child's clauses + // stay inside baseSql (moving them onto this relation would re-apply them + // after the lateral view) + relation = new SQLRelation(); + relation.getColumnNames().putAll(childRelation.getColumnNames()); + } else { + relation = childRelation; + baseSql = relation.getFrom(); + } + List<String> aliases = new ArrayList<>(outputs.size()); + // The analyzer may name a generator output with an internal column name + // ("$c$N"); such a name cannot be referenced in SQL, so give it a generated + // visible name and register the slot under that name for the parent operators. + // A generator output may also COLLIDE with a name the child already exports + // (SELECT t.x, lv.x FROM t LATERAL VIEW explode(t.arr) lv AS x is valid: the two + // slots carry different qualifiers, but the frozen SQL references a derived + // relation's columns by name) - registering both as bare x made the parent emit + // SELECT x, x ..., which fails binding as ambiguous after reload. Rename the + // generator output to a unique visible name and register THAT for the slot. + // A generator output may also COLLIDE with a name the child already exports + // (SELECT t.x, lv.x FROM t LATERAL VIEW explode(t.arr) lv AS x is valid: the two + // slots carry different qualifiers, but the frozen SQL references a derived + // relation's columns by name) - registering both as bare x made the parent emit + // SELECT x, x ..., which fails binding as ambiguous after reload. Rename the + // generator output to a unique visible name and register THAT for the slot. + // + // The comparison follows the ANALYZER's identifier-case rules: Doris resolves + // column names case-insensitively, so a case-SENSITIVE set missed the collision + // of a source column X and a generator output x (the frozen projection emitted + // X AS a, x AS b, exactly the ambiguous pair the rename exists to avoid, and + // the create-time probe skipped this text because of its IN-list marker). + Set<String> takenNames = new TreeSet<>(String.CASE_INSENSITIVE_ORDER); + for (String existing : childRelation.getColumnNames().values()) { + if (existing != null) { + takenNames.add(existing.replace("`", "")); + } + } + List<String> columnNames = new ArrayList<>(outputs.size()); + for (Slot slot : outputs) { + String alias = slot.getQualifier().isEmpty() + ? "" : slot.getQualifier().get(slot.getQualifier().size() - 1); + aliases.add(alias.isEmpty() ? "lv_" + (lateralViewSeq++) : alias); + String name = slot.getName(); + String visible = name == null || name.startsWith("$c$") + ? "lv_col_" + (lateralViewSeq++) : name; + while (takenNames.contains(visible)) { + visible = visible + "_"; + } + takenNames.add(visible); + columnNames.add(visible); + } + StringBuilder from = new StringBuilder(baseSql); + for (int i = 0; i < generators.size(); i++) { + from.append(" LATERAL VIEW ") + .append(exprSqlBuilder.print(generators.get(i), relation)) + .append(' ') + .append(quoteIdentifier(aliases.get(i))) + .append(" AS ") + .append(quoteIdentifier(columnNames.get(i))); + } + relation.setFrom(from.toString()); + for (int i = 0; i < outputs.size(); i++) { + relation.registerRef(outputs.get(i).getExprId(), quoteIdentifier(columnNames.get(i))); + } + // When this relation is wrapped as a subquery by its parent, its SELECT list is + // the subquery output: the generator columns must be part of it, otherwise the + // parent's reference to a generated column fails to resolve ("Unknown column + // ... in table list"). An empty SELECT list means "*" and already covers them. + if (!relation.getSelects().isEmpty()) { + List<Pair<ExprId, String>> selects = new ArrayList<>(relation.getSelects()); + for (int i = 0; i < outputs.size(); i++) { + selects.add(Pair.of(outputs.get(i).getExprId(), quoteIdentifier(columnNames.get(i)))); + } + relation.setSelects(selects); + } + if (!generate.getConjuncts().isEmpty()) { + // The conjuncts are the generate's original join ON predicates (they reach + // the TableFunctionNode as expandConjuncts). On an OUTER generator the BE + // keeps ONE NULL-extended left row when every generated value fails them + // (LEFT JOIN UNNEST(arr) AS u(x) ON u.x > 0 over arr = [-1] keeps the left + // row), while the LATERAL VIEW + WHERE rendering below would filter that row + // away. The frozen text has no rendering for that ON semantics, so decline + // and let the rewrite replay the parameterized tree. + for (Function generator : generators) { + if (isOuterGenerator(generator)) { + throw new UnsupportedOperationException("SPM decompile generate: the join ON" + + " conjuncts of the outer generator " + generator + " rely on" + + " expandConjuncts keeping the NULL-extended row when every generated" + + " value fails them; replay the parameterized tree instead"); + } + } + String conjuncts = generate.getConjuncts().stream() + .map(expr -> exprSqlBuilder.print(expr, relation)) + .collect(Collectors.joining(" AND ")); + relation.setWhere(relation.getWhere().isEmpty() + ? conjuncts + : relation.getWhere() + " AND " + conjuncts); + } + return relation; + } + + /** + * Whether one generator renders its OUTER form - the "xxx_outer" function family + * (explode_outer / posexplode_outer / ...; the catalog derives the same name for + * outer lookup) or an Unnest still carrying the outer flag before convertUnnest. + * Only the outer form keeps the NULL-extended row when the expandConjuncts fail + * (see visitPhysicalGenerate). + */ + private static boolean isOuterGenerator(Function generator) { + if (generator instanceof Unnest) { + return ((Unnest) generator).isOuter(); + } + return generator.getName().endsWith("_outer"); + } + + // ==================== CTE (anchor / producer / consumer) ==================== + + /** + * PhysicalCTEAnchor: two children - child(0) is the PhysicalCTEProducer (the CTE + * body, processed first: it registers the WITH definition and the alias consumers + * reference) and child(1) is the main query. The WITH entry itself is attached to + * the root relation in toSQL(), not here (see cteDefinitions). + */ + @Override + public SQLRelation visitPhysicalCTEAnchor( + PhysicalCTEAnchor<? extends Plan, ? extends Plan> anchor, Void context) { + process(anchor.child(0)); + return process(anchor.child(1)); + } + + /** + * PhysicalCTEProducer: processes the CTE body and registers it (plus a fresh alias + * and the WITH entry) under the CTEId, so every PhysicalCTEConsumer references the + * single shared definition instead of inlining a body copy. The body subtree is + * already pruned to the union of all consumer needs by the live-column analysis. + */ + @Override + public SQLRelation visitPhysicalCTEProducer(PhysicalCTEProducer<? extends Plan> producer, Void context) { + SQLRelation body = process(producer.child(0)); + String alias = SQLRelation.newTableAlias(); + cteBodies.put(producer.getCteId(), body); + cteAliases.put(producer.getCteId(), alias); + cteDefinitions.add(alias + " AS (" + body.toSQL() + ")"); Review Comment: [P1] Render pending row assertions inside CTE definitions On `t(k)={1,2}`, capture identical SQL `WITH c AS (SELECT k FROM ASSERT_ROWS (SELECT k FROM t WHERE k>0) a) SELECT k FROM c`. Capture forces CTE materialization; after identity-project elimination the relevant tree is: ```text CTEAnchor CTEProducer(c) -> AssertNumRows(EQ 1) -> Filter(k>ph1) -> Scan(t) CTEConsumer(c) ``` `visitPhysicalAssertNumRows` only sets `body.assertRows`, but this `body.toSQL()` does not consume that flag; only `toRelationSQL()` does. The WITH definition consequently becomes a plain filtered SELECT. The consumer has no assertion flag, so the repaired result-root/sink paths cannot recover it. The planning probe accepts it, and identical replay returns both rows instead of the required row-count error. This is a separate CTE statement boundary from [the repaired result-root report](https://github.com/apache/doris/pull/68499#discussion_r4378183282). Render the assertion through a shared statement serializer before registering the WITH body, and cover CTE capture/replay error preservation. ########## fe/fe-core/src/main/java/org/apache/doris/nereids/spm/SPMPlanner.java: ########## @@ -0,0 +1,1775 @@ +// 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.spm; + +import org.apache.doris.common.AnalysisException; +import org.apache.doris.common.Pair; +import org.apache.doris.common.UserException; +import org.apache.doris.nereids.StatementContext; +import org.apache.doris.nereids.parser.NereidsParser; +import org.apache.doris.nereids.spm.builder.SPMPlan2SQLBuilder; +import org.apache.doris.nereids.spm.manager.BaselineManager; +import org.apache.doris.nereids.spm.manager.SessionBaselineStore; +import org.apache.doris.nereids.spm.matcher.SPMFrozenTreeReplacer; +import org.apache.doris.nereids.spm.matcher.SPMPlaceholderReplacer; +import org.apache.doris.nereids.spm.placeholder.SPMPlaceholderBuilder; +import org.apache.doris.nereids.spm.placeholder.SpmConstList; +import org.apache.doris.nereids.spm.placeholder.SpmConstVar; +import org.apache.doris.nereids.trees.expressions.Expression; +import org.apache.doris.nereids.trees.expressions.SubqueryExpr; +import org.apache.doris.nereids.trees.plans.Plan; +import org.apache.doris.nereids.trees.plans.commands.Command; +import org.apache.doris.nereids.trees.plans.commands.ExplainCommand; +import org.apache.doris.nereids.trees.plans.logical.LogicalPlan; +import org.apache.doris.nereids.trees.plans.physical.PhysicalCatalogRelation; +import org.apache.doris.qe.ConnectContext; +import org.apache.doris.qe.SqlModeHelper; + +import org.apache.logging.log4j.LogManager; +import org.apache.logging.log4j.Logger; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +/** + * SPMPlanner - the controller of the whole-query SPM bind and rewrite. + * + * SPM works on the WHOLE parsed (still unbound) SELECT plan tree + * + * 1. Build (CREATE BASELINE PLAN / auto capture): parse bindSql, replace EVERY literal + * of the whole tree (filters, having, projections, aggregate group-by/output and + * every subquery inside an expression, recursively) with a placeholder through one + * shared SPMPlaceholderBuilder, and do the same for planSql so both trees share the + * same placeholder ids. The baseline keeps the parameterized bind tree (used for the + * Level 3 structural match) and the parameterized plan tree (used to produce the + * rewritten query). + * 2. Rewrite (user query, called from StmtExecutor / EXPLAIN): compute the value-free + * full-query digest / hash, find candidate baselines (Level 1 hash + Level 2 digest), + * structurally compare the candidate's parameterized bind tree with the user's tree + * over the whole tree (Level 3, extracting the user values for every placeholder id), + * and on a match replay the baseline's FROZEN planSql (M3): the frozen text - the + * decompiled optimal plan carrying placeholder ids, join distribution hints and the + * pushed-down structure - is re-parsed and the extracted values are substituted by + * placeholder id, so the rewrite reproduces the frozen optimal structure. + * Baselines without a frozen placeholder text fall back to substituting the candidate's + * parameterized plan tree. The substituted tree (still unbound, no placeholders left) + * is returned and planned normally by the caller. + * + * A query without any query-block WHERE - e.g. one whose SELECT-list scalar subquery + * carries its own WHERE - is handled naturally: the subquery's literals are part of the + * whole tree and take part in parameterization, matching, value extraction and rewrite, + * so no special case or rejection is needed. + * + * A failed rewrite, a timeout or a no-match returns null (the caller executes the + * original query normally; SPM degrades transparently). + */ +public class SPMPlanner { + + private static final Logger LOG = LogManager.getLogger(SPMPlanner.class); + + /** Id of the baseline used by the last successful rewrite (-1 when none). */ + private long usedBaselineId = -1; + + /** + * The matched baseline OBJECT (see verifyReplayMetadata): the post-plan + * validation must keep the fingerprint of the SAME incarnation the match used, so a + * concurrent DROP / refresh cannot make it silently skip the check. + */ + private BaselinePlan usedBaseline; + + /** + * Returns the id of the baseline used by the last successful rewrite. + * + * @return the baseline id, or -1 when the last rewrite did not hit a baseline + */ + public long getUsedBaselineId() { + return usedBaselineId; + } + + /** The matched baseline object (see verifyReplayMetadata). */ + public BaselinePlan getUsedBaseline() { + return usedBaseline; + } + + // ==================== query rewrite (called from StmtExecutor / EXPLAIN) ==================== + + /** + * Rewrites a user query (parsed, still unbound) via SPM. + * + * Runs the three-level match against every candidate baseline and, on a hit, + * substitutes the user's actual literal values into the candidate's parameterized + * plan tree and returns the resulting (unbound) plan. The caller (StmtExecutor) + * plans the returned tree normally, so the rewritten query goes through the regular + * analyze / optimize pipeline. + * + * @param userPlan the parsed (unbound) plan of the user query + * @param deadline rewrite deadline (epoch millis) for the spm_rewrite_timeout_ms budget + * @return the rewritten unbound plan, or null when no baseline matched / timed out / + * the substituted plan is unusable + */ + public LogicalPlan tryRewritePlan(LogicalPlan userPlan, long deadline) { + if (System.currentTimeMillis() > deadline) { + LOG.info("SPM tryRewritePlan: timeout before matching, degrade to the original plan"); + return null; + } + // SELECT ... INTO OUTFILE writes to a destination that lives OUTSIDE the plan + // expressions: the generic match cannot see a different path / format and the + // rewritten tree keeps the CAPTURED sink fields, so a replay would export to the + // baseline's destination. SPM refuses to rewrite such statements (the original + // query runs normally, which is always correct). + if (SPMPlanTreeSupport.containsFileSink(userPlan)) { + LOG.info("SPM tryRewritePlan: the statement writes to a file sink (OUTFILE); keeping" + + " the original plan"); + return null; + } + ConnectContext ctx = ConnectContext.get(); + SessionBaselineStore sessionStore = ctx == null ? null : ctx.getSessionBaselineStore(); + // Fast path: with no baseline anywhere (global or session) there is nothing to + // match, so skip the whole-tree digest rendering below - it walks every literal + // of the whole query and is the most expensive part of a rewrite attempt. + if (!BaselineManager.getInstance().hasBaselines() + && (sessionStore == null || sessionStore.isEmpty())) { + return null; + } + // A caller SET_VAR hint is applied by EliminateLogicalSelectHint while the + // statement is planned; the SPM replay replaces the whole tree BEFORE that pass + // and the frozen text carries no hint, so the replay would run under the + // session's ORIGINAL settings - a SET_VAR(time_zone='+08:00') caller matching an + // identical baseline evaluated from_unixtime(epoch_col) in its own zone and + // changed result values. The caller's SET_VAR hints are re-attached to the + // replayed tree at the return sites (see SPMPlanTreeSupport#carrySetVarHints); + // the hint writes a STATEMENT-scoped session variable, so its block does not + // matter. + // Level 1/2 use the FULL-QUERY value-free digest (Plan.toSpmDigest() renders every + // literal as "?", so the digest is value-independent). The digest is computed on a + // namespace-qualified COPY: "FROM t" is keyed as the CURRENT catalog/db's t, so a + // baseline captured under db1 can never match the same text executed under db2 + // (the frozen planSql is fully qualified and would silently keep running against + // db1.t). Explicitly qualified references stay verbatim on both sides, and so do + // references to a CTE alias: those bind inside the query's own WITH clause and are + // therefore namespace-independent. + LogicalPlan matchPlan = SPMPlanTreeSupport.namespaceQualified(userPlan, + captureCatalogName(ctx), captureDatabaseName(ctx)); + String queryDigest = SPMPlanTreeSupport.canonicalSpmDigest(matchPlan.toSpmDigest()); + long queryHash = SPMUtils.hashOf(queryDigest); + // SESSION-scope baselines of the current connection are consulted BEFORE the + // global ones, so a session baseline can override a global baseline for this + // session only; each candidate list is already priority-ordered. + List<BaselinePlan> candidates = new ArrayList<>(); + if (sessionStore != null) { + candidates.addAll(sessionStore.findCandidateBaselines(queryDigest, queryHash)); + } + candidates.addAll( + BaselineManager.getInstance().findCandidateBaselines(queryDigest, queryHash)); + if (candidates.isEmpty()) { + return null; + } + // View guard (computed lazily on the first structural match, so the per-query + // hot path pays nothing): the replay of a matched baseline is planned before the + // normal authorization pass and resolves a view to its base tables, so + // authorization would check the base tables instead of the view - a view-only + // user is denied on the base tables, while a base-table user passes the same + // view query without any view check. View queries keep the original plan. + boolean viewChecked = false; + boolean viewReferenced = false; + // Schema-identity guard state (computed lazily, once per query, only after the + // first structural match): see the check inside the loop. + boolean schemaChecked = false; + String currentSchemaFingerprint = null; + for (BaselinePlan candidate : candidates) { + if (System.currentTimeMillis() > deadline) { + LOG.info("SPM tryRewritePlan: timeout before matching baseline {}, " + + "degrade to the original plan", candidate.getId()); + return null; + } + LogicalPlan bindTree = candidate.getParameterizedBindPlan(); + if (bindTree == null) { + continue; + } + // Level 3: whole-tree structural match + value extraction + Map<Long, Expression> placeholderValues = new HashMap<>(); + if (!SPMPlanTreeSupport.check(bindTree, matchPlan, placeholderValues)) { + continue; + } + LOG.info("SPM tryRewritePlan: baseline {} matched, extracted {} placeholder values", + candidate.getId(), placeholderValues.size()); + if (!viewChecked) { + viewChecked = true; + viewReferenced = SPMPlanTreeSupport.referencesView(ctx, userPlan); + } + if (viewReferenced) { + LOG.info("SPM tryRewritePlan: the query references a view; keeping the original" + + " plan so view authorization is preserved"); + return null; + } + // Schema-identity guard (see BaselinePlan#schemaFingerprint): the bind key is + // built from the STILL-UNBOUND query, so `SELECT * FROM t WHERE k = 1` keeps + // the same digest and Level-3 tree after `ALTER TABLE t ADD COLUMN extra` + // (or a DROP + CREATE of t), while the frozen plan still emits the + // creator-time output columns - the matched replay would silently return the + // old column set. A baseline whose referenced-table fingerprint no longer + // matches fails closed (the user query keeps its own plan); pre-column rows + // without a fingerprint skip the check. The current fingerprint is computed + // once per query, and only after a structural match (hot path pays nothing). + // The stored fingerprint is the BIND-SIDE tables UNION the PLAN-side tables + // of the frozen plan; here - BEFORE the query is planned - only the bind side + // can be recomputed, so the guard checks that every current bind-side entry is + // still present (a DROP + CREATE / ALTER REPLACES its entry, so drift is still + // caught). The full comparison, plan side included, runs after planning + // (see verifyReplayMetadata). + String bindFingerprint = candidate.getSchemaFingerprint(); + if (bindFingerprint != null && !bindFingerprint.isEmpty()) { + if (!schemaChecked) { + schemaChecked = true; + currentSchemaFingerprint = + SPMPlanTreeSupport.schemaFingerprint(ctx, userPlan); + } + if (!SPMPlanTreeSupport.schemaFingerprintBindSideContained( + bindFingerprint, currentSchemaFingerprint)) { + LOG.info("SPM tryRewritePlan: baseline {} skipped: the referenced table" + + " schema changed since the baseline was created", candidate.getId()); + continue; + } + } + // The expensive part (value-free digest, candidate lookup, whole-tree check) is + // already done and a baseline has matched: finish the (cheap) value substitution + // even when the budget has been consumed. Previously this path re-checked the + // deadline here and returned null on expiry, silently throwing the completed + // match away (rewrite degraded to the original plan). + // M3: replay the FROZEN optimal plan. A baseline whose frozen planSql carries + // placeholder calls (decompiled from the SPM-optimized physical plan, structure + // + join distribution hints preserved) is re-parsed and the user values are + // substituted by placeholder id - the rewrite reproduces the frozen optimal + // structure exactly (SR-aligned). Baselines without a frozen placeholder text + // (in-memory engine, decompile-fallback planSql, legacy "?" frozen text) fall + // back to substituting the parameterized plan tree. + LogicalPlan rewritten = rewriteFromFrozenTree(candidate, placeholderValues); + if (rewritten != null) { + // non-expression literals (LIMIT / OFFSET) are long fields, not + // placeholders; adopt the user's values so a structurally identical query + // with a different limit is rewritten with the USER limit + // the frozen sink pinned the CAPTURED output labels: expose the caller's + // own ones (a value variant must not report the captured header). A shape + // whose labels CANNOT be aligned skips this baseline instead of exposing + // the captured header (see UnalignableOutputLabelsException). + LogicalPlan alignedReplay; + try { + alignedReplay = SPMPlanTreeSupport.alignRootOutputLabels(rewritten, + matchPlan); + } catch (SPMPlanTreeSupport.UnalignableOutputLabelsException unalignable) { + LOG.info("SPM tryRewritePlan: baseline {} skipped: {}", + candidate.getId(), unalignable.getMessage()); + continue; + } + LogicalPlan replay = SPMPlanTreeSupport.mergeLimits(alignedReplay, matchPlan); + // The cap contract keys every row cap by the OCCURRENCE of the relation it + // truncates, and the occurrence is the relation's ordinal in the tree's walk + // order. That ordinal is only stable when the caller's tree and the FROZEN plan + // render the occurrences in the same relative order - which the optimizer need + // not do: it may place a derived table on the OTHER side of a JOIN than the user + // wrote it (a derived-table TopN joined with the same table), and the very same + // cap then keys as t#0 on one side and t#1 on the other. For a caller that runs + // the statement the frozen plan was BUILT FROM (its canonical plan digest equals + // the baseline's planSqlDigest) the cap contract cannot prove anything the text + // identity does not already prove, so the replay is kept; any other caller - a + // value variant, whose digest matches but whose placement could genuinely differ - + // still has to satisfy it (see SPMRound40SafetyTest). + boolean sameFrozenStatement = candidate.getPlanSqlDigest() != null + && candidate.getPlanSqlDigest().equals(queryDigest); Review Comment: [P1] Do not bypass retained-cap checks with a value-free digest Capture identical bind/plan `SELECT a.k,b.v FROM t a CROSS JOIN u b LIMIT 1`. Enabled `PushDownLimit` rules can produce: ```text Limit(1) CrossJoin Limit(1) -> Scan(t) Limit(1) -> Scan(u) ``` The decompiler preserves both input caps as derived-table LIMITs. A caller changing only the outer LIMIT to 3 still makes this comparison true: both `planSqlDigest` and `queryDigest` mask literal LIMIT values. `mergeLimits` can update the outer cap, but the raw caller has no counterparts for these optimizer-generated input caps, so they remain 1. This branch then skips `limitContractPreserved` and accepts replay. With two rows in each table, replay returns one pair where the caller returns three; ordering/schema checks and the planning probe do not reject it. This occurs with identical capture SQL, separate from earlier manual limit-relocation cases. Use value-preserving identity for this exception or validate/rebind every retained cap for value variants. -- 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]
