github-actions[bot] commented on code in PR #68499: URL: https://github.com/apache/doris/pull/68499#discussion_r4378183269
########## fe/fe-core/src/main/java/org/apache/doris/nereids/spm/placeholder/SPMPlaceholderBuilder.java: ########## @@ -0,0 +1,1147 @@ +// 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.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.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.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 com.google.common.collect.ImmutableList; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Deque; +import java.util.List; + +/** + * 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 { + + /** 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; + + /** + * 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 || !isMapConstructor(expr)) { + return false; + } + List<Expression> pairs = expr.children(); + if (pairs.size() < 2) { + return false; + } + for (int i = 1; i < pairs.size(); i += 2) { + if (!producesNullType(pairs.get(i))) { + return false; + } + } + return true; + } + + /** + * Whether the expression is an all-NULL array (see producesNullType). + * + * An array LITERAL whose every element produces NullType has type ARRAY<NULL_TYPE>, so a + * consumer that reads an ELEMENT (`element_at`) is NullType as well. Both spellings are + * accepted: the parsed {@link ArrayLiteral} and the unbound `array(...)` call, which is only + * a {@link Function} named {@code array} before binding. + * + * An ARRAY_CONCAT WRAPPER is an all-NULL array exactly when every concatenated part is one + * (round-80): the function derives its element type from its inputs, so concatenating only + * all-NULL arrays keeps ARRAY<NULL_TYPE> - and the wrapper was NOT recognized, so + * `k > 0 OR element_at(array_concat(array(NULL), array(NULL)), 1)` kept an ARRAY<NULL_TYPE> + * marker, a Boolean consumer erased the element_at call and its markers, and the + * `array(TRUE), array(TRUE)` variant had nothing left to substitute (the frozen replay then + * returned NULL for a row the caller returns TRUE for). + * + * A TYPE-PRESERVING ARRAY TRANSFORMATION ({@code array_sort} / {@code array_distinct}) wraps + * the same way (round-81): both declare {@code retArgType(0)}, so the result is + * ARRAY<NULL_TYPE> exactly when their INPUT array is - and the unrecognized wrapper left + * the element_at call NullType, which made the Boolean consumer drop it together with its + * markers (`k > 0 OR element_at(array_sort(array(NULL)), 1)` then replayed NULL for k = -1 + * although the {@code array_sort(array(TRUE))} caller returns TRUE). + * + * @param expr the expression to classify + * @return whether it is an all-NULL array value + */ + private static boolean isAllNullArray(Expression expr) { + if (expr == null) { + return false; + } + if (expr.isNullLiteral()) { + // a NULL literal is untyped ARRAY<NULL_TYPE> in an array position + return true; + } + if (isArrayConcatCall(expr)) { + List<Expression> parts = expr.children(); + if (parts.isEmpty()) { + return false; + } + for (Expression part : parts) { + if (!isAllNullArray(part)) { + return false; + } + } + return true; + } + if (isTypePreservingArrayCall(expr)) { + // only the FIRST child is the array whose element type the result inherits: the + // comparator of `array_sort(array, lambda)` contributes no type of its own + List<Expression> parts = expr.children(); + return !parts.isEmpty() && isAllNullArray(parts.get(0)); + } + if (!isArrayConstructor(expr)) { Review Comment: [P1] Preserve markers through MAP_VALUES element extraction Capture `SELECT k>0 OR element_at(map_values(map('x',NULL)),1) AS c FROM t`, then run its `map('x',TRUE)` variant: ```text Project(Or(k>phA, ElementAt(MapValues(Map(phKey,phValue[NullType])),phIndex))) Scan(t) ``` `isAllNullArray` rejects MAP_VALUES here. CreateMap derives MAP<STRING,NULL_TYPE>, MapValues follows the value type into ARRAY<NULL_TYPE>, and ElementAt returns NullType. Without Boolean retyping, `visitOr` erases the entire operand and its marker IDs. Matching still extracts TRUE, but frozen replay returns NULL instead of TRUE for k=-1; the planning probe does not check lost IDs. Track effective producer/consumer types or reject freezes that lose required markers, including containers passed through derived outputs. This is the MAP-value-to-ARRAY signature path, distinct from the repaired ARRAY_SORT/DISTINCT wrappers. ########## fe/fe-core/src/main/java/org/apache/doris/nereids/spm/placeholder/SPMPlaceholderBuilder.java: ########## @@ -0,0 +1,1147 @@ +// 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.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.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.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 com.google.common.collect.ImmutableList; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Deque; +import java.util.List; + +/** + * 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 { + + /** 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; + + /** + * 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 || !isMapConstructor(expr)) { + return false; + } + List<Expression> pairs = expr.children(); + if (pairs.size() < 2) { + return false; + } + for (int i = 1; i < pairs.size(); i += 2) { + if (!producesNullType(pairs.get(i))) { + return false; + } + } + return true; + } + + /** + * Whether the expression is an all-NULL array (see producesNullType). + * + * An array LITERAL whose every element produces NullType has type ARRAY<NULL_TYPE>, so a + * consumer that reads an ELEMENT (`element_at`) is NullType as well. Both spellings are + * accepted: the parsed {@link ArrayLiteral} and the unbound `array(...)` call, which is only + * a {@link Function} named {@code array} before binding. + * + * An ARRAY_CONCAT WRAPPER is an all-NULL array exactly when every concatenated part is one + * (round-80): the function derives its element type from its inputs, so concatenating only + * all-NULL arrays keeps ARRAY<NULL_TYPE> - and the wrapper was NOT recognized, so + * `k > 0 OR element_at(array_concat(array(NULL), array(NULL)), 1)` kept an ARRAY<NULL_TYPE> + * marker, a Boolean consumer erased the element_at call and its markers, and the + * `array(TRUE), array(TRUE)` variant had nothing left to substitute (the frozen replay then + * returned NULL for a row the caller returns TRUE for). + * + * A TYPE-PRESERVING ARRAY TRANSFORMATION ({@code array_sort} / {@code array_distinct}) wraps + * the same way (round-81): both declare {@code retArgType(0)}, so the result is + * ARRAY<NULL_TYPE> exactly when their INPUT array is - and the unrecognized wrapper left + * the element_at call NullType, which made the Boolean consumer drop it together with its + * markers (`k > 0 OR element_at(array_sort(array(NULL)), 1)` then replayed NULL for k = -1 + * although the {@code array_sort(array(TRUE))} caller returns TRUE). + * + * @param expr the expression to classify + * @return whether it is an all-NULL array value + */ + private static boolean isAllNullArray(Expression expr) { + if (expr == null) { + return false; + } + if (expr.isNullLiteral()) { + // a NULL literal is untyped ARRAY<NULL_TYPE> in an array position + return true; + } + if (isArrayConcatCall(expr)) { + List<Expression> parts = expr.children(); + if (parts.isEmpty()) { + return false; + } + for (Expression part : parts) { + if (!isAllNullArray(part)) { + return false; + } + } + return true; + } + if (isTypePreservingArrayCall(expr)) { + // only the FIRST child is the array whose element type the result inherits: the + // comparator of `array_sort(array, lambda)` contributes no type of its own + List<Expression> parts = expr.children(); + return !parts.isEmpty() && isAllNullArray(parts.get(0)); + } + if (!isArrayConstructor(expr)) { + return false; + } + // a bracket array LITERAL is a LEAF: its elements live in getValue(), not in children() + List<? extends Expression> elements = expr instanceof ArrayLiteral + ? ((ArrayLiteral) expr).getValue() : expr.children(); + if (elements.isEmpty()) { + return false; + } + for (Expression element : elements) { + if (!producesNullType(element)) { + return false; + } + } + return true; + } + + /** + * Whether the expression is an {@code array_concat} call (see isAllNullArray). + * + * Matched by NAME through {@link Function}, which covers both the unbound `array_concat(...)` + * call and the bound {@code ArrayConcat} node (its function name is {@code array_concat}). + * + * @param expr the expression to classify + * @return whether it is an array_concat call + */ + private static boolean isArrayConcatCall(Expression expr) { + return expr instanceof Function + && "array_concat".equalsIgnoreCase(((Function) expr).getName()); + } + + /** + * Whether the expression is an {@code array_sort} / {@code array_distinct} call (see + * isAllNullArray). + * + * Both declare {@code retArgType(0)}, i.e. the result's element type is the INPUT array's, so + * an all-NULL input makes the result an all-NULL array. Matched by NAME through + * {@link Function}, which covers the unbound calls and the bound {@code ArraySort} / + * {@code ArrayDistinct} nodes (their function names are {@code array_sort} / + * {@code array_distinct}). + * + * @param expr the expression to classify + * @return whether it is a type-preserving array transformation + */ + private static boolean isTypePreservingArrayCall(Expression expr) { + if (!(expr instanceof Function)) { + return false; + } + String name = ((Function) expr).getName(); + return "array_sort".equalsIgnoreCase(name) + || "array_distinct".equalsIgnoreCase(name); + } + + /** + * Whether the expression builds an ARRAY value (see producesNullType). + * + * Both spellings are accepted: the parsed {@link ArrayLiteral} and the unbound `array(...)` + * call, which is only a {@link Function} named {@code array} before binding. + * + * @param expr the expression to classify + * @return whether it is an array constructor + */ + private static boolean isArrayConstructor(Expression expr) { + if (expr instanceof ArrayLiteral) { + return true; + } + return expr instanceof Function + && "array".equalsIgnoreCase(((Function) expr).getName()); + } + + /** + * Whether the expression is an {@code element_at} call (see producesNullType). + * + * Matched by NAME through {@link Function} for the unbound plan, and by the analyzed + * {@link ElementAt} node for a bound one. + * + * @param expr the expression to classify + * @return whether it is an element_at call + */ + private static boolean isElementAtCall(Expression expr) { + if (expr instanceof ElementAt) { + return true; + } + return expr instanceof Function + && "element_at".equalsIgnoreCase(((Function) expr).getName()); + } + + /** + * Whether the expression is an {@code array_min} / {@code array_max} call (see + * producesNullType). + * + * Both declare {@code ret(FollowToAnyDataType(0))}, i.e. the result IS the input array's + * element type, so an all-NULL input makes the call a NullType producer exactly like + * {@code element_at}. Matched by NAME through {@link Function}, which covers the unbound + * calls and the bound {@code ArrayMin} / {@code ArrayMax} nodes. + * + * @param expr the expression to classify + * @return whether it is an array reducer + */ + private static boolean isArrayReducerCall(Expression expr) { + if (!(expr instanceof Function)) { + return false; + } + String name = ((Function) expr).getName(); + return "array_min".equalsIgnoreCase(name) || "array_max".equalsIgnoreCase(name); + } + + /** + * Whether the expression builds a MAP value (see isAllNullMap). + * + * Matched by NAME through {@link Function}, which covers both the unbound `map(...)` call and + * the bound {@code CreateMap} (its function name is {@code map}). + * + * @param expr the expression to classify + * @return whether it is a map constructor + */ + private static boolean isMapConstructor(Expression expr) { + return expr instanceof Function && "map".equalsIgnoreCase(((Function) expr).getName()); + } + + /** + * Whether the expression is a {@code GREATEST} / {@code LEAST} call (see producesNullType). + * + * {@code GreatestLeast.customSignature} returns the arguments' common type, so an all-NULL + * call is NullType and a Boolean consumer replaces it outright (round-78 #1). LEAST shares the + * class, so both names are accepted. + * + * @param expr the expression to classify + * @return whether it is a GREATEST / LEAST call + */ + private static boolean isGreatestLeastConditional(Expression expr) { + if (!(expr instanceof Function)) { + return false; + } + String name = ((Function) expr).getName(); + return "greatest".equalsIgnoreCase(name) || "least".equalsIgnoreCase(name); + } + + /** + * Whether the expression is an {@code IF} / {@code COALESCE} CALL. Matched by NAME through + * the {@link Function} interface because the parameterized plan is the UNBOUND one, where + * `IF(...)` is still an {@link UnboundFunction} (only the analyzed {@link If} node exists + * after binding). + * + * @param expr the expression to classify + * @return whether it is an IF call + */ + private static boolean isIfConditional(Expression expr) { + return expr instanceof Function && "if".equalsIgnoreCase(((Function) expr).getName()); + } + + /** + * Whether the expression is an {@code IFNULL} / {@code NVL} call (both parse to the same + * {@link Function} named {@code ifnull}; {@code nvl} is accepted as the spelling as well). + * + * It belongs to the all-NULL conditional family even though it has no condition argument: + * {@code ifnull(NULL, NULL)} has NullType, so a Boolean consumer replaces the WHOLE call + * with a typed constant NULL exactly like an all-NULL CASE - `k > 0 OR ifnull(NULL, NULL)` + * lost both markers and the matching `ifnull(NULL, TRUE)` variant had nothing to + * substitute (round-76 #1). + * + * @param expr the expression to classify + * @return whether it is an IFNULL / NVL call + */ + private static boolean isIfNullConditional(Expression expr) { + if (!(expr instanceof Function)) { + return false; + } + String name = ((Function) expr).getName(); + return "ifnull".equalsIgnoreCase(name) || "nvl".equalsIgnoreCase(name); + } + + /** + * Whether the expression is a {@code NULLIF} call. + * + * NULLIF is a THIRD all-NULL producer, on its own signature path: {@code NullIf.customSignature} + * returns the COMMON type of its two arguments, so {@code nullif(NULL, NULL)} has NullType and a + * Boolean consumer ("k > 0 OR nullif(NULL, NULL)") replaces the whole call with a typed constant + * NULL - the markers of both arguments disappear and the matching {@code nullif(TRUE, NULL)} + * variant has no marker left to substitute with TRUE (round-77 #3). It is not covered by the + * IFNULL / NVL branch above: a different function with its own signature rule. + * + * @param expr the expression to classify + * @return whether it is a NULLIF call + */ + private static boolean isNullIfConditional(Expression expr) { + return expr instanceof Function + && "nullif".equalsIgnoreCase(((Function) expr).getName()); + } + + /** + * Whether the expression is a {@code COALESCE} call (see isIfConditional). + * + * @param expr the expression to classify + * @return whether it is a COALESCE call + */ + private static boolean isCoalesceConditional(Expression expr) { + return expr instanceof Function + && "coalesce".equalsIgnoreCase(((Function) expr).getName()); + } + + /** + * Whether the literal at the CURRENT position is a RESULT of its conditional parent (see + * producesNullType) - a CASE's THEN / ELSE, an IF's two value arguments, or any + * COALESCE argument. + * + * Only RESULTS may be typed BOOLEAN: the WHEN / condition operands compare against real + * columns, and a BOOLEAN-typed NULL there (`k = CAST(NULL AS BOOLEAN)`) is a type error in + * the replayed plan. + * + * @param parent the literal's parent expression + * @return whether the literal sits in a result position + */ + private boolean isConditionalResultPosition(Expression parent) { + return isConditionalResultPosition(parent, currentChildIndex()); + } + + /** + * The position-aware form of {@link #isConditionalResultPosition(Expression)}. + * + * @param parent the conditional + * @param childIndex the position of the child inside it + * @return whether that position holds a result + */ + private static boolean isConditionalResultPosition(Expression parent, int childIndex) { + if (parent instanceof WhenClause) { + // a WHEN clause's children are [operand, result]: only the RESULT may be typed + return childIndex == 1; + } + if (parent instanceof CaseWhen) { + // the WHEN clauses are separate WhenClause nodes, so only the ELSE is a direct child + CaseWhen caseWhen = (CaseWhen) parent; + return caseWhen.getDefaultValue().isPresent() + && childIndex == caseWhen.children().size() - 1; + } + if (isIfNullConditional(parent) || isNullIfConditional(parent) + || isGreatestLeastConditional(parent)) { + // every IFNULL / NVL / NULLIF / GREATEST / LEAST argument is a value + return true; + } + if (isIfConditional(parent)) { + return childIndex == 1 || childIndex == 2; + } + if (isArrayConstructor(parent)) { + // an ARRAY's elements are the array's VALUES: under an all-NULL element type the + // consuming call is NullType and gets replaced as a whole, so every element marker + // has to be BOOLEAN already (round-79 #3) + return true; + } + if (isMapConstructor(parent)) { + // a MAP constructor's children alternate KEY, VALUE: only a VALUE feeds the map's + // value type and with it what `element_at` returns, so only the odd positions may be + // typed BOOLEAN - a BOOLEAN key would change the map's key type and be a type error + // for the captured key literal (round-80 #1) + return childIndex % 2 == 1; + } + return isCoalesceConditional(parent); + } + + @Override + public Expression visitLiteral(Literal literal, Expression parent) { + // The ESCAPE operand of LIKE must stay a STRING LITERAL: parameterizing it turned + // the escape into a scalar placeholder call, and the analyzer rejected the whole + // statement ("like escape character must be a string literal" on + // "k like '%a%' escape '!'"). An escape character is part of the LIKE operator's + // syntax, not a search value: keeping it literal makes a user query with a + // DIFFERENT escape character a structural mismatch (the safe direction - the + // query simply runs without the baseline) instead of an unplannable baseline. + // A plain LIKE (no ESCAPE) carries only the left / pattern children; child(2) + // must not be touched then (the pattern literal is visited with the 2-child + // LIKE as its parent, and an unguarded child(2) read threw + // ArrayIndexOutOfBoundsException on every such CREATE). + if (parent instanceof Like && parent.children().size() > 2 + && literal == parent.child(2)) { + return literal; + } + // Deduplicate by value + parent structure + child position: a literal reuses an + // existing id only when the value, the parent expression structure AND the + // position inside that parent all match. The position is required - the two + // operands of "1 + 1" share one parent structure but are different positions, + // and a similar query may carry different values there (one shared id would make + // the two occurrences resolve to the same user value and never match). + int childIndex = currentChildIndex(); + long blockId = currentBlockId; + int projectItem = currentProjectItem(); + long rootOrdinal = currentRootOrdinal; + String occurrencePath = currentOccurrencePath(); + for (PlaceholderExpr record : placeholderExprs) { + if (record.matches(literal, parent, childIndex, blockId, projectItem, rootOrdinal, + occurrencePath)) { + return record.getPlaceholderExpr(); + } + } + long id = nextId++; + SpmConstVar placeholder = SpmConstVar.of(id, + markerPayload(literal, parent, currentProjectItem() >= 0, + booleanConditionalDepth > 0 && isConditionalResultPosition(parent), + booleanConditionalDepth > 0 && isElementAtContainerPosition(parent))); + placeholderExprs.add(new PlaceholderExpr(literal, placeholder, parent, childIndex, + blockId, projectItem, rootOrdinal, occurrencePath)); + return placeholder; + } + + /** + * Whether the literal sits in the CONTAINER position of an `element_at` call (see + * markerPayload). + * + * The container itself is not a value position: its marker has to stay an ARRAY / MAP, so the + * Boolean retyping of a bare NULL cannot apply to it - the container needs its own repair. + * + * @param parent the literal's parent expression + * @return whether the literal is `element_at`'s first argument + */ + private boolean isElementAtContainerPosition(Expression parent) { + return isElementAtCall(parent) && currentChildIndex() == 0; + } + + /** + * The literal the placeholder keeps as its PAYLOAD (readability only - the replay + * substitutes the whole placeholder by id). + * + * A captured NULL is special: a NULL literal's type is NullType, and the analyzer + * COERCES a NullType operand of AND / OR / NOT to a typed BOOLEAN null literal + * (ExpressionAnalyzer.visitOr / visitAnd / visitNot). That rewrite REPLACES the whole + * operand, i.e. it deleted the placeholder: the frozen SQL of + * `k > 0 OR NULL` contained `k > _spm_const_var(1, 0) OR NULL` and the second id was + * gone, so a matching `k > 0 OR TRUE` (same literal-masked digest, id 2 extracted as + * TRUE) had no marker left to substitute and the replay returned NULL instead of TRUE. + * Typing the payload BOOLEAN keeps the marker where the analyzer expects a boolean + * operand: it is not a NullType operand any more, the value substituted at replay + * still lands in the same slot, and matching is unaffected (a placeholder accepts any + * user literal, see SPMAstCheckVisitor). + * + * @param literal the captured literal + * @param parent the literal's parent expression (null at an expression root) + * @param projectionItem whether the literal is a projection item's expression + * @param booleanConditionalResult whether the literal is a RESULT of a conditional that is + * consumed as a Boolean operand + * @param booleanElementContainer whether the literal is the CONTAINER of an `element_at` that + * is consumed as a Boolean operand + * @return the payload the placeholder keeps + */ + private static Literal markerPayload(Literal literal, Expression parent, + boolean projectionItem, boolean booleanConditionalResult, + boolean booleanElementContainer) { + if (booleanElementContainer) { + // A bracket ARRAY literal keeps its elements as LITERALS (ArrayLiteral#getValue), so + // the ELEMENT markers the function spelling gets (see isConditionalResultPosition) + // cannot exist here: the whole literal is ONE marker, its type is the literal's own + // ARRAY<NULL_TYPE> and `element_at` on it is still NullType - the Boolean consumer + // replaced the whole call and the marker with it, so the `element_at([TRUE], 1)` + // variant had no id left to substitute (round-80 #4). Retyping the marker's payload + // to ARRAY<BOOLEAN> removes the NullType from the tree while staying an array value; + // the frozen text carries the id only, so the replay still substitutes the caller's + // own value and keeps its own (correct) type. + Literal containerPayload = booleanContainerPayload(literal); + if (containerPayload != null) { + return containerPayload; + } + } + boolean booleanOperand = parent instanceof And || parent instanceof Or + || parent instanceof Not; + if (literal.isNullLiteral() && (booleanOperand || booleanConditionalResult)) { + return NullLiteral.BOOLEAN_INSTANCE; + } + // A projected NULL (`SELECT NULL AS n` / a bare `SELECT NULL`) exposes a NullType + // SLOT, and a consumer that binds it as a BOOLEAN operand (an enclosing OR / AND / + // WHERE, even in another query block) has the analyzer replace that operand with a + // typed constant NULL - dropping the slot, and with it this marker. A TRUE variant of + // the derived column then has nothing to substitute and the replay keeps NULL. + // Typing the projected NULL BOOLEAN removes the NullType from the tree; a NULL value + // stays NULL through any later coercion, so the only thing that changes is that the + // marker (and the slot that carries it) survives. + if (literal.isNullLiteral() && projectionItem + && (parent == null || parent instanceof org.apache.doris.nereids.trees.expressions.Alias)) { + return NullLiteral.BOOLEAN_INSTANCE; + } + return literal; + } + + /** + * The non-NullType payload of an `element_at` CONTAINER marker (see markerPayload). + * + * Only an all-NULL bracket array literal is repaired - every other container already carries + * a real element type. The array becomes an ARRAY<BOOLEAN> literal of the same shape: its + * elements are all NULL, and a NULL value is NULL whatever its type, so only the marker's TYPE + * changes. A bare NULL container is left alone: `element_at(NULL, k)` is legal for the MAP + * overload too, and typing it as an array would turn a MAP lookup into a type error. + * + * @param literal the captured container literal + * @return the retyped payload, or null when the literal is not an all-NULL array literal + */ + private static Literal booleanContainerPayload(Literal literal) { + if (!(literal instanceof ArrayLiteral)) { Review Comment: [P1] Preserve bare NULL container markers before freezing Capture `SELECT k>0 OR element_at(NULL,1) AS c FROM t`, then execute the `[TRUE]` container variant: ```text Project(Or(k>phA, ElementAt(phB[NullType],phC))) -> Scan(t) ``` This repair excludes the bare NULL container, while the scalar Boolean repair does not apply in the container position. ElementAt's dedicated NullType-input signature therefore returns NullType, and `ExpressionAnalyzer.visitOr` replaces the whole call with Boolean NULL, removing phB/phC. NULL and ArrayLiteral both have the `?` digest, and scalar matching accepts the caller's `[TRUE]`; the frozen projection still replays `k>phA OR NULL`. For k=-1 it returns NULL instead of TRUE. CREATE only replans surviving IDs. Preserve those IDs or decline freezing when binding consumes them. This is the bare-NULL container branch, distinct from the repaired ARRAY/MAP constructor element cases; bracket literals under ARRAY_MIN/MAX also bypass the ElementAt-only container repair. ########## fe/fe-core/src/main/java/org/apache/doris/nereids/spm/builder/SPMPlan2SQLBuilder.java: ########## @@ -0,0 +1,4422 @@ +// 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.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.table.TableValuedFunction; +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_" + ExprId) 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<>(); + + /** 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<>(); + + /** + * 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); + } + } + }); + } + + 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); + // 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. + return relation.toSQL(); Review Comment: [P1] Render the pending root row assertion before freezing On t(k)={1,2}, capture identical SQL `SELECT * FROM ASSERT_ROWS (SELECT k FROM t WHERE k>0) a`. Identity-project elimination leaves: ```text ResultSink(k) AssertNumRows(EQ 1) Filter(k>ph1) Scan(t,k) ``` `visitPhysicalAssertNumRows` only sets the SQLRelation's assertRows flag. The sink's empty-select branch fills its SELECT list and returns the same relation; this root `toSQL()` does not render that flag, which is consumed only by `toRelationSQL()`. Frozen SQL is therefore an ordinary filtered SELECT. CREATE's probe plans it successfully, and identical replay returns both rows where native execution raises the row-count error. Materialize the assertion boundary at the result root (and before moving parent clauses onto it), or decline freezing this shape. Existing ASSERT_ROWS tests cover embedded JOIN inputs, where `toRelationSQL()` runs; the earlier missing-grammar report is repaired. -- 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]
