Jackie-Jiang commented on code in PR #19311: URL: https://github.com/apache/pinot/pull/19311#discussion_r4484353666
########## pinot-query-planner/src/main/java/org/apache/pinot/query/validate/MatchRecognizeValidator.java: ########## @@ -0,0 +1,682 @@ +/** + * 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.pinot.query.validate; + +import java.util.LinkedHashSet; +import java.util.List; +import java.util.Locale; +import java.util.Set; +import java.util.function.UnaryOperator; +import javax.annotation.Nullable; +import org.apache.calcite.sql.SqlAggFunction; +import org.apache.calcite.sql.SqlCall; +import org.apache.calcite.sql.SqlIdentifier; +import org.apache.calcite.sql.SqlKind; +import org.apache.calcite.sql.SqlLiteral; +import org.apache.calcite.sql.SqlMatchRecognize; +import org.apache.calcite.sql.SqlNode; +import org.apache.calcite.sql.SqlNodeList; +import org.apache.calcite.sql.SqlOperator; +import org.apache.calcite.sql.SqlUnresolvedFunction; +import org.apache.calcite.sql.fun.SqlStdOperatorTable; +import org.apache.calcite.sql.parser.SqlParserPos; +import org.apache.calcite.sql.util.SqlBasicVisitor; +import org.apache.pinot.segment.spi.AggregationFunctionType; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + + +/// Pinot specific validation and rewriting of SQL:2016 `MATCH_RECOGNIZE` (row pattern recognition) clauses. +/// +/// This visitor runs on the **raw parsed** [SqlNode] tree, before Calcite's own validation and before +/// [org.apache.calcite.sql2rel.SqlToRelConverter] runs. Running this early is deliberate and load bearing: +/// +/// 1. **The `AFTER MATCH` default must be corrected at the `SqlNode` level.** When the `AFTER MATCH` clause is +/// omitted, the parser leaves [SqlMatchRecognize#getAfter()] as `null`, and `SqlToRelConverter` then silently +/// substitutes [SqlMatchRecognize.AfterOption#SKIP_TO_NEXT_ROW]. SQL:2016 (and Trino, Snowflake and Oracle) all +/// default to `SKIP PAST LAST ROW`. The two differ in whether matches may overlap, so a query ported from +/// another engine would silently return different rows. Conversion erases the omitted-vs-explicit distinction, +/// so the fix has to happen here. See [#applyStandardAfterMatchDefault]. +/// 2. **Unsupported constructs must be rejected before conversion.** Several of them (`ORDER BY` / `PARTITION BY` +/// on arbitrary expressions in particular) blow up inside `SqlToRelConverter` with an `AssertionError` or +/// `ClassCastException` rather than a usable message. +/// 3. **`RUNNING` in `DEFINE` must be normalized before Calcite validation.** SQL:2016 and Trino allow it (and it is +/// the default processing mode for a definition), but Calcite 1.42 rejects both `RUNNING` and `FINAL` there. +/// [#validateDefinitions] removes the redundant `RUNNING` wrapper and rejects `FINAL`, whose future-row +/// semantics cannot be evaluated while a match is being built. +/// 4. **Unquoted pattern variables must be case-insensitive.** Pinot deliberately preserves the spelling of +/// unquoted identifiers in its parser, while Calcite stores pattern variables in exact-case string maps. Without +/// an early rewrite, `PATTERN (A) DEFINE a AS a.price > 0` either creates two symbols or fails to bind. See +/// [#normalizePatternVariableNames]. +/// 5. **Pattern variables and the row source alias need separate internal names.** SQL gives those names separate +/// namespaces inside MATCH_RECOGNIZE, but Calcite reuses the row source alias as the alpha of the universal row +/// pattern variable. [#isolateRowSourceAlias] gives a colliding input an internal alias before Calcite validation, +/// so explicit pattern references and unqualified universal references remain distinguishable. +/// 6. **`PREV` in `DEFINE` must be anchored before Calcite validation.** Calcite rewrites `PREV(x, n)` into the +/// logical `LAST(x, n)` unless `x` is qualified by the variable being defined, which silently changes the rows an +/// unqualified or cross-variable `PREV` reads. See [#anchorAtLastRow]. +/// +/// Everything this class rejects is deferred, not permanently unsupported; each message names the construct so the +/// user can rewrite the query. +/// +/// This class is stateless apart from the tree it is walking and is **not** thread-safe; create a new instance per +/// query, exactly like [RowExpressionValidationVisitor]. +public class MatchRecognizeValidator extends SqlBasicVisitor<Void> { + private static final Logger LOGGER = LoggerFactory.getLogger(MatchRecognizeValidator.class); + + private static final String PERMUTE = "PERMUTE"; + private static final String PERMUTE_NOT_SUPPORTED = + "PERMUTE is not supported yet in the MATCH_RECOGNIZE PATTERN clause. Expand the permutation into an explicit " + + "alternation, e.g. PATTERN ((A B) | (B A))."; + + /// Whether the node currently being visited sits inside a MEASURES or DEFINE list. `RUNNING` wrappers in DEFINE + /// have already been removed and `FINAL` rejected by [#validateDefinitions] before this traversal. + private boolean _inMeasureOrDefine; + private boolean _matchRecognizeFound; + + /// Whether the visited SQL tree contains at least one MATCH_RECOGNIZE clause. + public boolean hasMatchRecognize() { + return _matchRecognizeFound; + } + + @Override + public Void visit(SqlCall call) { + if (call instanceof SqlMatchRecognize) { + visitMatchRecognize((SqlMatchRecognize) call); + return null; + } + SqlKind kind = call.getKind(); + if ((kind == SqlKind.RUNNING || kind == SqlKind.FINAL) && !_inMeasureOrDefine) { + // The RUNNING / FINAL prefix operators are registered for MATCH_RECOGNIZE, but unlike PREV / NEXT / FIRST / + // LAST / CLASSIFIER / MATCH_NUMBER, Calcite does not confine them to a MatchRecognizeScope. Reject them here + // so they cannot leak into an ordinary projection. + String legalClause = kind == SqlKind.FINAL ? "MEASURES" : "MEASURES or DEFINE"; + throw unsupported(kind + " can only be used in the " + legalClause + " clause of a MATCH_RECOGNIZE query: '" + + call + "'."); + } + return super.visit(call); + } + + private void visitMatchRecognize(SqlMatchRecognize match) { + _matchRecognizeFound = true; + validateAndRewrite(match); + // Only MEASURES and DEFINE may contain RUNNING / FINAL. Every other operand has already been checked by + // validateAndRewrite(), so the only one left to descend into is the table reference, which may itself hold a + // nested MATCH_RECOGNIZE. + visitIn(match.getMeasureList(), true); + visitIn(match.getPatternDefList(), true); + visitIn(match.getTableRef(), false); + } + + private void visitIn(SqlNode node, boolean inMeasureOrDefine) { + boolean saved = _inMeasureOrDefine; + _inMeasureOrDefine = inMeasureOrDefine; + try { + node.accept(this); + } finally { + _inMeasureOrDefine = saved; + } + } + + private void validateAndRewrite(SqlMatchRecognize match) { + normalizePatternVariableNames(match); + rejectUnsupportedClauses(match); + validatePartitionBy(match.getPartitionList()); + validateOrderBy(match.getOrderList()); + Set<String> definedVariables = definedVariables(match.getPatternDefList()); + validatePattern(match.getPattern(), definedVariables); + validateDefinitions(match.getPatternDefList()); + // Deliberately last: a query that also uses a deferred construct should be told about that construct first. + validateMeasures(match); + isolateRowSourceAlias(match, definedVariables); + applyStandardAfterMatchDefault(match); + logUndefinedPatternVariables(match, definedVariables); + } + + /// Canonicalizes every unquoted pattern variable to upper case while retaining quoted identifiers verbatim. + /// + /// Pinot configures its parser with `Casing.UNCHANGED`, but Calcite's MATCH_RECOGNIZE implementation keys PATTERN, + /// DEFINE, pattern-field references, and AFTER MATCH targets by exact [String] equality. SQL identifiers do not + /// have those semantics: unquoted names are case-insensitive, while quoted names are case-sensitive. Rewriting the + /// raw tree gives every downstream Calcite map one stable spelling and preserves each component's quoted parser + /// position so `"a"` remains distinct from unquoted `a` (canonical `A`). + private void normalizePatternVariableNames(SqlMatchRecognize match) { + match.setOperand(SqlMatchRecognize.OPERAND_PATTERN, normalizePattern(match.getPattern())); + + SqlNodeList definitions = match.getPatternDefList(); + for (SqlNode definition : definitions) { + SqlNode condition = patternDefinitionCondition(definition); + SqlIdentifier variable = patternDefinitionVariable(definition); + if (condition != null) { + ((SqlCall) definition).setOperand(0, normalizePatternReferences(condition)); + } + if (variable != null && variable.isSimple()) { + ((SqlCall) definition).setOperand(1, normalizeIdentifierComponent(variable, 0)); + } + } + + SqlNodeList measures = match.getMeasureList(); + for (int i = 0; i < measures.size(); i++) { + SqlNode measure = measures.get(i); + SqlNode expression = asOperand(measure, 0); + if (expression != null) { + ((SqlCall) measure).setOperand(0, normalizePatternReferences(expression)); + } else { + measures.set(i, normalizePatternReferences(measure)); + } + } + + SqlNode after = match.getAfter(); + if (after != null) { + match.setOperand(SqlMatchRecognize.OPERAND_AFTER, normalizePattern(after)); + } + } + + /// Rewrites the identifiers in the PATTERN grammar, where every identifier is a pattern variable. + private SqlNode normalizePattern(SqlNode node) { + if (node instanceof SqlIdentifier) { + SqlIdentifier identifier = (SqlIdentifier) node; + return identifier.isSimple() ? normalizeIdentifierComponent(identifier, 0) : identifier; + } + if (!(node instanceof SqlCall)) { + return node; + } + SqlCall call = (SqlCall) node; + List<SqlNode> operands = call.getOperandList(); + for (int i = 0; i < operands.size(); i++) { + SqlNode operand = operands.get(i); + if (operand != null) { + call.setOperand(i, normalizePattern(operand)); + } + } + return call; + } + + /// Rewrites only the alpha of a qualified pattern-field reference. A simple identifier is an input column, not a + /// pattern variable, so changing it here would also change column-name resolution. + private SqlNode normalizePatternReferences(SqlNode node) { + if (node instanceof SqlIdentifier) { + SqlIdentifier identifier = (SqlIdentifier) node; + return identifier.names.size() > 1 ? normalizeIdentifierComponent(identifier, 0) : identifier; + } + if (node instanceof SqlNodeList) { + return rewriteElements((SqlNodeList) node, this::normalizePatternReferences); + } + if (!(node instanceof SqlCall)) { + return node; + } + SqlCall call = (SqlCall) node; + List<SqlNode> operands = call.getOperandList(); + for (int i = 0; i < operands.size(); i++) { + SqlNode operand = operands.get(i); + if (operand != null) { + call.setOperand(i, normalizePatternReferences(operand)); + } + } + return call; + } + + private static SqlIdentifier normalizeIdentifierComponent(SqlIdentifier identifier, int component) { + // Calcite's single-name SqlIdentifier constructor stores quoting only on the node position and leaves + // componentPositions null; compound identifiers retain per-component positions. Consult both representations. + boolean quoted = identifier.isComponentQuoted(component) + || (identifier.isSimple() && identifier.getParserPosition().isQuoted()); + if (quoted) { + return identifier; + } + return identifier.setName(component, canonicalIdentifierComponent(identifier, component)); + } + + private static String canonicalIdentifierComponent(SqlIdentifier identifier, int component) { + boolean quoted = identifier.isComponentQuoted(component) + || (identifier.isSimple() && identifier.getParserPosition().isQuoted()); + String name = identifier.names.get(component); + return quoted ? name : name.toUpperCase(Locale.ROOT); + } + + /// Rewrites an omitted `AFTER MATCH` clause into an explicit `AFTER MATCH SKIP PAST LAST ROW`. + /// + /// Calcite's `SqlToRelConverter` defaults a `null` `AFTER` operand to `SKIP TO NEXT ROW`, which produces + /// overlapping matches. SQL:2016 mandates `SKIP PAST LAST ROW` (non-overlapping matches), and that is what + /// Trino, Snowflake and Oracle do. An explicitly written `AFTER MATCH SKIP TO NEXT ROW` is left untouched: the + /// parser only leaves the operand `null` when the clause is absent from the query text, so the omitted and the + /// explicit case are perfectly distinguishable here. + private void applyStandardAfterMatchDefault(SqlMatchRecognize match) { + if (match.getAfter() != null) { + return; + } + match.setOperand(SqlMatchRecognize.OPERAND_AFTER, + SqlMatchRecognize.AfterOption.SKIP_PAST_LAST_ROW.symbol(match.getParserPosition())); + } + + private void rejectUnsupportedClauses(SqlMatchRecognize match) { + SqlLiteral rowsPerMatch = match.getRowsPerMatch(); + if (rowsPerMatch != null + && rowsPerMatch.getValue() == SqlMatchRecognize.RowsPerMatchOption.ALL_ROWS) { + throw unsupported("ALL ROWS PER MATCH is not supported yet in MATCH_RECOGNIZE. Use ONE ROW PER MATCH (the " + + "default) and expose the per-match values you need through the MEASURES clause."); + } + if (!isEmpty(match.getSubsetList())) { + throw unsupported("SUBSET is not supported yet in MATCH_RECOGNIZE. Remove the SUBSET clause and reference the " + + "individual pattern variables directly."); + } + if (match.getInterval() != null) { + throw unsupported("WITHIN is not supported yet in MATCH_RECOGNIZE. Remove the WITHIN clause and bound the " + + "match with a predicate in the DEFINE clause instead."); + } + } + + /// Rejects the two `MEASURES` shapes whose Calcite row type is not `partition columns ++ measures`, which is what + /// `MatchNode` and `MatchOperator` assume. Both plan without complaint today and only fail on the server, with a + /// message describing an internal invariant rather than the user's mistake. + /// + /// 1. **No `MEASURES` clause at all.** `SqlValidatorImpl.validateMatchRecognize` ends with + /// `if (measureList.size() == 0) ns.setType(<the table reference row type>)`, i.e. the whole *input* row type, + /// which is not the `ONE ROW PER MATCH` shape at all. `MEASURES` is optional in SQL:2016 and in Trino, so this + /// is ordinary valid SQL; we do not own the Calcite code, so rejecting is the only sound option until + /// measures-less `MATCH_RECOGNIZE` is implemented properly. + /// 2. **An alias that collides with a `PARTITION BY` column or with an earlier measure alias.** Calcite adds each + /// measure to the row type only `if (!typeBuilder.nameExists(name))`, so a colliding alias is dropped + /// altogether and the query plans with a column missing. + /// + /// The name comparison is case-sensitive on purpose, because `RelDataTypeFactory.Builder#nameExists` is: + /// `PARTITION BY col1 ... MEASURES LAST(x) AS COL1` really does produce two distinct columns and must keep working. + private void validateMeasures(SqlMatchRecognize match) { + SqlNodeList measureList = match.getMeasureList(); + if (isEmpty(measureList)) { + throw unsupported("MATCH_RECOGNIZE requires a MEASURES clause. ONE ROW PER MATCH emits the PARTITION BY " + + "columns plus the MEASURES, so add at least one measure, e.g. MEASURES MATCH_NUMBER() AS mno."); + } + Set<String> names = new LinkedHashSet<>(); + for (SqlNode partitionKey : match.getPartitionList()) { + // validatePartitionBy() already established that every partition key is a plain identifier. + names.add(lastName((SqlIdentifier) partitionKey)); + } + for (SqlNode measure : measureList) { + SqlNode alias = asOperand(measure, 1); + if (alias instanceof SqlIdentifier && ((SqlIdentifier) alias).isSimple() + && !names.add(((SqlIdentifier) alias).getSimple())) { + throw unsupported("MATCH_RECOGNIZE measure alias '" + ((SqlIdentifier) alias).getSimple() + "' collides with " + + "a PARTITION BY column or an earlier measure alias. Calcite drops the duplicate from the output row " + + "type, which would silently lose a column; rename the measure."); + } + } + } + + /// Gives the row source an internal alias when its SQL name equals a pattern variable. + /// + /// SQL places the input relation and pattern variables in separate namespaces: with input alias `A` and pattern + /// variable `A`, a qualifier in PARTITION BY / ORDER BY names the input, a qualifier in MEASURES / DEFINE names the + /// pattern variable, and an unqualified measure or definition column uses the universal row pattern variable. + /// + /// Calcite does not retain that distinction: it qualifies an unqualified column in MEASURES / DEFINE with the row + /// source alias and later represents both forms as `RexPatternFieldRef(alpha, column)`. Re-aliasing the input before + /// Calcite sees the tree gives universal references an alpha that cannot equal a pattern variable. Qualified input + /// references in PARTITION BY / ORDER BY are rewritten with it; pattern references deliberately are not. + private void isolateRowSourceAlias(SqlMatchRecognize match, Set<String> definedVariables) { + SqlNode tableRef = match.getTableRef(); + SqlIdentifier aliasIdentifier = rowSourceAliasIdentifier(tableRef); + if (aliasIdentifier == null) { + // A join or a sub-query with no explicit alias; Calcite does not qualify anything with a row source alias. + return; Review Comment: [P1] Isolate synthesized aliases for unaliased derived inputs too Calcite does assign an internal source alias to an unaliased subquery, such as `EXPR$0`. That can collide with a quoted pattern variable: ```sql SELECT * FROM (SELECT v, ts, id FROM t) MATCH_RECOGNIZE ( PARTITION BY id ORDER BY ts MEASURES LAST(v) AS lastv PATTERN ("EXPR$0" B) DEFINE "EXPR$0" AS TRUE, B AS TRUE ) AS mr ``` Using this head's validator with Calcite 1.42 and Pinot's identifier-expansion/conformance settings, the measure becomes `FINAL(LAST(EXPR$0.$0, 0))`. `bindPatternFieldRefs()` then binds the unqualified `v` to the `EXPR$0` pattern symbol instead of the universal symbol. For matched values `[10, 20]`, the runtime lookup therefore selects `10` instead of `20`. Please give unaliased derived inputs a fresh explicit internal alias as well, and add a converter/runtime regression for this collision. The conflicting Calcite expression was reproduced in a focused probe; the resulting value follows from the binding and navigation code, rather than a full cluster execution. ########## pinot-query-runtime/src/main/java/org/apache/pinot/query/runtime/operator/MatchOperator.java: ########## @@ -0,0 +1,423 @@ +/** + * 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.pinot.query.runtime.operator; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.List; +import javax.annotation.Nullable; +import org.apache.pinot.common.datatable.StatMap; +import org.apache.pinot.common.utils.DataSchema; +import org.apache.pinot.common.utils.DataSchema.ColumnDataType; +import org.apache.pinot.query.planner.plannode.MatchNode; +import org.apache.pinot.query.planner.plannode.PatternSymbol; +import org.apache.pinot.query.runtime.blocks.MseBlock; +import org.apache.pinot.query.runtime.blocks.RowHeapDataBlock; +import org.apache.pinot.query.runtime.operator.match.MatchExpression; +import org.apache.pinot.query.runtime.operator.match.MatchLimits; +import org.apache.pinot.query.runtime.operator.match.MatchTape; +import org.apache.pinot.query.runtime.operator.match.PartitionMatcher; +import org.apache.pinot.query.runtime.operator.match.PatternNfa; +import org.apache.pinot.query.runtime.operator.match.PatternToNfaCompiler; +import org.apache.pinot.query.runtime.operator.utils.TypeUtils; +import org.apache.pinot.query.runtime.plan.OpChainExecutionContext; +import org.apache.pinot.spi.exception.QueryErrorCode; +import org.apache.pinot.spi.utils.CommonConstants.Broker.Request.QueryOptionKey; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + + +/// Evaluates SQL:2016 `MATCH_RECOGNIZE` (row pattern recognition) with `ONE ROW PER MATCH`. +/// +/// ## What it does per partition +/// +/// For every `PARTITION BY` partition, in `ORDER BY` order, it walks a scan position from the first row to +/// the last. At each position it asks [PartitionMatcher] for the preferred match starting exactly there. On a +/// match it emits one row - the partition key columns followed by the `MEASURES` - and then moves the scan +/// position according to the `AFTER MATCH SKIP` mode. On no match it moves one row forward. +/// +/// ## What it expects from the plan +/// +/// Like [WindowAggregateOperator], this operator does not sort. `PinotMatchExchangeNodeInsertRule` puts a +/// sort exchange underneath that hash distributes on the partition keys and sorts the receiver side on +/// `(partitionKeys..., orderKeys...)`, so rows arrive grouped by partition and ordered within a partition. The +/// operator therefore buffers one partition at a time and releases it at each boundary, and never reads +/// [MatchNode#getCollations()]: the ordering has already been established below it. +/// +/// The grouping half of that assumption is verified rather than trusted. Partition keys are compared directly on the +/// incoming rows and must be monotonically increasing, so a key that reappears after its partition was closed fails +/// without retaining every previously seen key. The ordering half is not re-checked per row, because an exchange that +/// grouped correctly but sorted incorrectly is not a failure mode the exchange can produce - losing the sort loses the +/// grouping too, which the partition-key order check already catches. +/// +/// ## Guardrails throw, they never truncate +/// +/// [QueryOptionKey#MAX_ROWS_IN_MATCH_PARTITION] bounds the rows buffered for a partition and +/// [QueryOptionKey#MAX_STEPS_PER_MATCH_ATTEMPT] bounds the backtracking of one match attempt. Both raise an error, +/// because a truncated pattern result is a wrong result that nothing in the response would flag. +/// +/// ## Not supported yet +/// +/// `ALL ROWS PER MATCH` is rejected here as well as during planning: this operator emits exactly one row per +/// match, so accepting it would silently return the wrong shape of result. +public class MatchOperator extends MultiStageOperator { + private static final Logger LOGGER = LoggerFactory.getLogger(MatchOperator.class); + private static final String EXPLAIN_NAME = "MATCH_RECOGNIZE"; + static final int MAX_OUTPUT_ROWS_PER_BLOCK = 1024; + + private final MultiStageOperator _input; + private final DataSchema _resultSchema; + private final ColumnDataType[] _resultStoredTypes; + private final int[] _partitionKeys; + private final int[] _partitionComparisonKeys; + private final List<PatternSymbol> _patternSymbols; + private final MatchExpression[] _measures; + private final PartitionMatcher _matcher; + private final MatchNode.AfterMatchSkipMode _skipMode; + private final int _skipToSymbolOrdinal; + private final int _maxRowsInMatchPartition; + private final StatMap<StatKey> _statMap = new StatMap<>(StatKey.class); + + private List<Object[]> _partitionRows = new ArrayList<>(); + @Nullable + private List<Object[]> _inputRows; + private int _inputRowIndex; + private boolean _matchingPartition; + private int _scanStart; + private long _matchNumber; + @Nullable + private MseBlock.Eos _inputEos; + private int _numRows; + + public MatchOperator(OpChainExecutionContext context, MultiStageOperator input, DataSchema inputSchema, + MatchNode node) { + super(context); + if (node.getRowsPerMatchMode() != MatchNode.RowsPerMatchMode.ONE_ROW_PER_MATCH) { + throw QueryErrorCode.QUERY_EXECUTION.asException( + "ALL ROWS PER MATCH is not supported yet in MATCH_RECOGNIZE. Use ONE ROW PER MATCH (the default) and " + + "expose the per-match values you need through the MEASURES clause."); + } + _input = input; + _resultSchema = node.getDataSchema(); + _resultStoredTypes = _resultSchema.getStoredColumnDataTypes(); + List<Integer> partitionKeys = node.getPartitionKeys(); + _partitionKeys = new int[partitionKeys.size()]; + for (int i = 0; i < _partitionKeys.length; i++) { + _partitionKeys[i] = partitionKeys.get(i); + ColumnDataType partitionKeyType = inputSchema.getColumnDataType(_partitionKeys[i]); + if (partitionKeyType.isArray()) { + throw QueryErrorCode.QUERY_EXECUTION.asException( + "MATCH_RECOGNIZE PARTITION BY requires single-value columns, but column '" + + inputSchema.getColumnName(_partitionKeys[i]) + "' has type " + partitionKeyType); + } + } + // Calcite exposes the exchange distribution as an ImmutableBitSet, so the rule below this operator sorts + // partition fields by input ordinal. Preserve SQL declaration order in _partitionKeys for the output schema, but + // validate monotonic input against the order the exchange actually produces. + _partitionComparisonKeys = _partitionKeys.clone(); + Arrays.sort(_partitionComparisonKeys); + _patternSymbols = node.getPatternSymbols(); + List<MatchNode.Measure> measures = node.getMeasures(); + _measures = new MatchExpression[measures.size()]; + for (int i = 0; i < _measures.length; i++) { + _measures[i] = MatchExpression.compile(measures.get(i).getExpression(), inputSchema); + } + if (_resultSchema.size() != _partitionKeys.length + _measures.length) { + throw QueryErrorCode.QUERY_EXECUTION.asException( + "MATCH_RECOGNIZE output schema " + _resultSchema + " does not match " + _partitionKeys.length + + " partition key(s) plus " + _measures.length + " measure(s)"); + } + _skipMode = node.getAfterMatchSkipMode(); + _skipToSymbolOrdinal = node.getAfterMatchSkipToSymbolOrdinal(); + + PatternNfa nfa = PatternToNfaCompiler.compile(node.getPattern()); + _maxRowsInMatchPartition = + MatchLimits.getMaxRowsInMatchPartition(context.getOpChainMetadata(), node.getNodeHint()); + long maxStepsPerMatchAttempt = + MatchLimits.getMaxStepsPerMatchAttempt(context.getOpChainMetadata(), node.getNodeHint()); + _matcher = new PartitionMatcher(nfa, _patternSymbols, inputSchema, maxStepsPerMatchAttempt, + this::checkTerminationAndSampleUsage); + } + + @Override + protected Logger logger() { + return LOGGER; + } + + @Override + public List<MultiStageOperator> getChildOperators() { + return List.of(_input); + } + + @Override + public Type getOperatorType() { + return Type.MATCH; + } + + @Override + public String toExplainString() { + return EXPLAIN_NAME; + } + + @Override + public void registerExecution(long time, int numRows, long memoryUsedBytes, long gcTimeMs) { + _statMap.merge(StatKey.EXECUTION_TIME_MS, time); + _statMap.merge(StatKey.EMITTED_ROWS, numRows); + _statMap.merge(StatKey.ALLOCATED_MEMORY_BYTES, memoryUsedBytes); + _statMap.merge(StatKey.GC_TIME_MS, gcTimeMs); + } + + @Override + public StatMap<StatKey> copyStatMaps() { + return new StatMap<>(_statMap); + } + + @Override + protected MseBlock getNextBlock() { + List<Object[]> outputRows = new ArrayList<>(MAX_OUTPUT_ROWS_PER_BLOCK); + while (outputRows.size() < MAX_OUTPUT_ROWS_PER_BLOCK) { + if (_matchingPartition) { + emitMatches(outputRows); + continue; Review Comment: [P2] Honor early termination before resuming buffered matching This operator never checks `_isEarlyTerminated`. Once an outer LIMIT has enough rows, `LimitSortOperator` requests early termination and continues draining to EOS. The signal reaches MATCH directly or through the mailbox exchange, but this loop still runs all remaining match attempts on the buffered input. For example, with `PATTERN (A | B+ C)`, enough initial A matches can satisfy `LIMIT 1`, while a long B-only suffix still triggers repeated unsuccessful searches during draining. That can consume substantial CPU or produce a step-budget error/timeout after the requested result already exists. Please stop matching and release buffered input when early termination is signaled, while preserving/draining the upstream terminal state and stats. A focused test should satisfy the limit before a suffix that would otherwise exhaust the matching budget. ########## pinot-query-runtime/src/main/java/org/apache/pinot/query/runtime/operator/match/MatchTerm.java: ########## @@ -0,0 +1,394 @@ +/** + * 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.pinot.query.runtime.operator.match; + +import java.math.BigDecimal; +import java.math.BigInteger; +import java.math.MathContext; +import java.util.Arrays; +import java.util.List; +import javax.annotation.Nullable; +import org.apache.pinot.common.utils.DataSchema.ColumnDataType; +import org.apache.pinot.query.planner.logical.RexExpression; +import org.apache.pinot.query.runtime.operator.operands.TransformOperand; +import org.apache.pinot.query.runtime.operator.utils.TypeUtils; +import org.apache.pinot.spi.exception.QueryErrorCode; + + +/// A leaf of a MEASURES or DEFINE expression whose value depends on the match rather than on a single row: a row +/// pattern navigation, `CLASSIFIER()`, `MATCH_NUMBER()`, or a single variable aggregate. +/// +/// [MatchExpression] replaces every such leaf with a slot in a synthetic row, so that everything above the +/// leaves - comparisons, boolean connectives, arithmetic, scalar functions - is evaluated by Pinot's ordinary +/// [TransformOperand] machinery instead of a second expression interpreter. +/// +/// Implementations are stateless with respect to the match: all match state is passed in through the +/// [MatchTape], so one instance is reused across every match of every partition. +public interface MatchTerm { + + /// The type this term reports to the enclosing expression. Values returned by [#evaluate] are in the + /// corresponding [stored][ColumnDataType#getStoredType()] representation, exactly like the values of a real + /// input row. + ColumnDataType getResultType(); + + @Nullable + Object evaluate(MatchTape tape); + + /// A row pattern navigation: an optional logical step (`FIRST` / `LAST`) that designates a row of the + /// match, followed by an optional physical step (`PREV` / `NEXT`) that moves a fixed number of rows + /// relative to it, and finally a column read. + /// + /// Both steps are needed because SQL:2016 nests them, e.g. `PREV(LAST(A.price), 2)` designates the last row + /// mapped to `A` and then moves two rows back. The logical step is bounded by the match; the physical step is + /// bounded only by the partition, so it may legally read a row outside the match. Either step falling off its bound + /// yields `null`, as the standard requires. + final class Navigation implements MatchTerm { + private final int _symbolOrdinal; + private final boolean _fromEnd; + private final int _logicalOffset; + private final int _physicalDelta; + private final int _columnIndex; + private final ColumnDataType _resultType; + private final ColumnDataType _storedType; + private final boolean _requiresConversion; + + /// @param symbolOrdinal pattern variable to navigate, or + /// [org.apache.pinot.query.planner.logical.RexExpression.PatternFieldRef#UNIVERSAL_SYMBOL_ORDINAL] + /// for an unqualified column reference, which navigates the rows of the whole match + /// @param fromEnd `true` for `LAST`, `false` for `FIRST` + /// @param logicalOffset how many rows back from the end (or forward from the start) of the designated variable + /// @param physicalDelta rows to move in the partition afterwards; negative for `PREV`, positive for + /// `NEXT`, zero when there is no physical step + /// @param columnIndex column to read, as an index into the input row of the MATCH_RECOGNIZE node + /// @param sourceType type of that input column; values already use its stored representation + public Navigation(int symbolOrdinal, boolean fromEnd, int logicalOffset, int physicalDelta, int columnIndex, + ColumnDataType sourceType, ColumnDataType resultType) { + _symbolOrdinal = symbolOrdinal; + _fromEnd = fromEnd; + _logicalOffset = logicalOffset; + _physicalDelta = physicalDelta; + _columnIndex = columnIndex; + _resultType = resultType; + _storedType = resultType.getStoredType(); + _requiresConversion = sourceType.getStoredType() != _storedType; + } + + @Override + public ColumnDataType getResultType() { + return _resultType; + } + + @Nullable + @Override + public Object evaluate(MatchTape tape) { + int rowIndex = _fromEnd ? tape.lastRow(_symbolOrdinal, _logicalOffset) + : tape.firstRow(_symbolOrdinal, _logicalOffset); + if (rowIndex == MatchTape.NO_ROW) { + return null; + } + long physicalRowIndex = (long) rowIndex + _physicalDelta; + List<Object[]> rows = tape.getPartitionRows(); + if (physicalRowIndex < 0 || physicalRowIndex >= rows.size()) { + return null; + } + Object value = rows.get((int) physicalRowIndex)[_columnIndex]; + // The declared type of the navigation may be wider than the column's (e.g. BIG_DECIMAL for a DOUBLE column), + // and the enclosing operand compares against that declared type. + return value != null && _requiresConversion ? TypeUtils.convert(value, _storedType) : value; + } + } + + /// `CLASSIFIER()`: the name of the pattern variable the designated row is mapped to. A bare call designates the + /// last (current) row; FIRST / LAST may select another match row and PREV / NEXT may move relative to it. + final class Classifier implements MatchTerm { + public static final Classifier INSTANCE = new Classifier(true, 0, 0); + + private final boolean _fromEnd; + private final int _logicalOffset; + private final int _physicalDelta; + + public Classifier(boolean fromEnd, int logicalOffset, int physicalDelta) { + _fromEnd = fromEnd; + _logicalOffset = logicalOffset; + _physicalDelta = physicalDelta; + } + + @Override + public ColumnDataType getResultType() { + return ColumnDataType.STRING; + } + + @Nullable + @Override + public Object evaluate(MatchTape tape) { + int rowIndex = _fromEnd + ? tape.lastRow(RexExpression.PatternFieldRef.UNIVERSAL_SYMBOL_ORDINAL, _logicalOffset) + : tape.firstRow(RexExpression.PatternFieldRef.UNIVERSAL_SYMBOL_ORDINAL, _logicalOffset); + if (rowIndex == MatchTape.NO_ROW) { + return null; + } + long physicalRowIndex = (long) rowIndex + _physicalDelta; + if (physicalRowIndex < 0 || physicalRowIndex >= tape.getPartitionRows().size()) { + return null; + } + return tape.classifierAt((int) physicalRowIndex); + } + } + + /// `MATCH_NUMBER()`: the sequential number of the match within its partition, starting at 1. + final class MatchNumber implements MatchTerm { + public static final MatchNumber INSTANCE = new MatchNumber(); + + private MatchNumber() { + } + + @Override + public ColumnDataType getResultType() { + return ColumnDataType.LONG; + } + + @Override + public Object evaluate(MatchTape tape) { + return tape.getMatchNumber(); + } + } + + /// A single variable aggregate in MEASURES, e.g. `SUM(A.price)` or `COUNT(*)`: the aggregate of an + /// expression evaluated over every row of the match that is mapped to one pattern variable. + /// + /// The argument is evaluated by an ordinary [TransformOperand] against the raw input row, so any scalar + /// expression works, e.g. `SUM(A.price * A.quantity)`. Nulls are skipped, as SQL requires; an aggregate over + /// zero rows is `null` except for `COUNT`, which is `0`. + final class Aggregate implements MatchTerm { + private final Kind _kind; + private final int _symbolOrdinal; + @Nullable + private final TransformOperand _argument; + private final ColumnDataType _resultType; + private final ColumnDataType _storedType; + private final boolean _requiresResultConversion; + + /// @param argument the aggregated expression evaluated against an input row, or `null` for `COUNT(*)`, + /// which counts rows rather than values + public Aggregate(Kind kind, int symbolOrdinal, @Nullable TransformOperand argument, ColumnDataType resultType) { + _kind = kind; + _symbolOrdinal = symbolOrdinal; + _argument = argument; + _resultType = resultType; + _storedType = resultType.getStoredType(); + if (argument != null && argument.getResultType().isArray()) { + throw QueryErrorCode.QUERY_EXECUTION.asException( + "Multi-value operand type '" + argument.getResultType() + "' is not supported for " + kind + + " in a MATCH_RECOGNIZE MEASURES clause. Reduce the array to a scalar before aggregating it."); + } + if ((kind == Kind.SUM || kind == Kind.AVG) && !_storedType.isNumber()) { + throw QueryErrorCode.QUERY_EXECUTION.asException( + "MATCH_RECOGNIZE " + kind + " requires a numeric result type, got: " + resultType + "."); + } + _requiresResultConversion = argument != null && argument.getResultType().getStoredType() != _storedType; + } + + @Override + public ColumnDataType getResultType() { + return _resultType; + } + + @Nullable + @Override + public Object evaluate(MatchTape tape) { + int rowCount = tape.rowCount(_symbolOrdinal); + if (_kind == Kind.COUNT && _argument == null) { + return (long) rowCount; + } + List<Object[]> partitionRows = tape.getPartitionRows(); + switch (_kind) { + case COUNT: + return countNonNull(tape, rowCount, partitionRows); + case MIN: + case MAX: + return evaluateExtremum(tape, rowCount, partitionRows); + case SUM: + case AVG: + return evaluateSumOrAverage(tape, rowCount, partitionRows); + default: + throw new IllegalStateException("Unexpected MATCH_RECOGNIZE aggregate: " + _kind); + } + } + + private long countNonNull(MatchTape tape, int rowCount, List<Object[]> partitionRows) { + long count = 0; + for (int i = 0; i < rowCount; i++) { + Object value = _argument.apply(partitionRows.get(tape.rowAt(_symbolOrdinal, i))); + if (value != null) { + count++; + } + } + return count; + } + + @Nullable + private Object evaluateExtremum(MatchTape tape, int rowCount, List<Object[]> partitionRows) { + Object extremum = null; + for (int i = 0; i < rowCount; i++) { + Object value = _argument.apply(partitionRows.get(tape.rowAt(_symbolOrdinal, i))); + if (value == null) { + continue; + } + if (extremum == null || (_kind == Kind.MIN ? compare(value, extremum) < 0 : compare(value, extremum) > 0)) { + extremum = value; + } + } + if (extremum == null || !_requiresResultConversion) { + return extremum; + } + return TypeUtils.convert(extremum, _storedType); + } + + @Nullable + private Object evaluateSumOrAverage(MatchTape tape, int rowCount, List<Object[]> partitionRows) { + switch (_storedType) { + case INT: + case LONG: + return evaluateIntegralSumOrAverage(tape, rowCount, partitionRows); + case FLOAT: + case DOUBLE: + return evaluateFloatingPointSumOrAverage(tape, rowCount, partitionRows); + case BIG_DECIMAL: + return evaluateDecimalSumOrAverage(tape, rowCount, partitionRows); + default: + throw QueryErrorCode.QUERY_EXECUTION.asException( + "MATCH_RECOGNIZE " + _kind + " requires a numeric result type, got: " + _resultType + "."); + } + } + + @Nullable + private Object evaluateIntegralSumOrAverage(MatchTape tape, int rowCount, List<Object[]> partitionRows) { + long sum = 0; + long count = 0; + for (int i = 0; i < rowCount; i++) { + Object value = _argument.apply(partitionRows.get(tape.rowAt(_symbolOrdinal, i))); + if (value != null) { + sum += numericValue(value).longValue(); + count++; + } + } + if (count == 0) { + return null; + } + long result = _kind == Kind.AVG ? sum / count : sum; + if (_storedType == ColumnDataType.INT) { + return (int) result; + } + return result; + } + + @Nullable + private Object evaluateFloatingPointSumOrAverage(MatchTape tape, int rowCount, List<Object[]> partitionRows) { + double sum = 0; + long count = 0; + for (int i = 0; i < rowCount; i++) { + Object value = _argument.apply(partitionRows.get(tape.rowAt(_symbolOrdinal, i))); + if (value != null) { + sum += numericValue(value).doubleValue(); + count++; + } Review Comment: [P2] Check cancellation and deadlines inside aggregate measure scans This loop, and the COUNT/MIN/MAX/integral/decimal variants, evaluates every matched row without a termination check. These scans happen after the NFA match completes, so the matcher's periodic transition checks do not protect them. An aggregate over a large match with an expensive scalar argument can keep evaluating the remaining rows after cancellation or the deadline. Please pass the operator's termination/resource-sampling callback into measure evaluation and invoke it periodically inside each aggregate loop. A focused regression can trigger cancellation after a known number of argument evaluations and verify that the remaining rows are not all visited. ########## pinot-query-runtime/src/main/java/org/apache/pinot/query/runtime/operator/MatchOperator.java: ########## @@ -0,0 +1,423 @@ +/** + * 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.pinot.query.runtime.operator; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.List; +import javax.annotation.Nullable; +import org.apache.pinot.common.datatable.StatMap; +import org.apache.pinot.common.utils.DataSchema; +import org.apache.pinot.common.utils.DataSchema.ColumnDataType; +import org.apache.pinot.query.planner.plannode.MatchNode; +import org.apache.pinot.query.planner.plannode.PatternSymbol; +import org.apache.pinot.query.runtime.blocks.MseBlock; +import org.apache.pinot.query.runtime.blocks.RowHeapDataBlock; +import org.apache.pinot.query.runtime.operator.match.MatchExpression; +import org.apache.pinot.query.runtime.operator.match.MatchLimits; +import org.apache.pinot.query.runtime.operator.match.MatchTape; +import org.apache.pinot.query.runtime.operator.match.PartitionMatcher; +import org.apache.pinot.query.runtime.operator.match.PatternNfa; +import org.apache.pinot.query.runtime.operator.match.PatternToNfaCompiler; +import org.apache.pinot.query.runtime.operator.utils.TypeUtils; +import org.apache.pinot.query.runtime.plan.OpChainExecutionContext; +import org.apache.pinot.spi.exception.QueryErrorCode; +import org.apache.pinot.spi.utils.CommonConstants.Broker.Request.QueryOptionKey; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + + +/// Evaluates SQL:2016 `MATCH_RECOGNIZE` (row pattern recognition) with `ONE ROW PER MATCH`. +/// +/// ## What it does per partition +/// +/// For every `PARTITION BY` partition, in `ORDER BY` order, it walks a scan position from the first row to +/// the last. At each position it asks [PartitionMatcher] for the preferred match starting exactly there. On a +/// match it emits one row - the partition key columns followed by the `MEASURES` - and then moves the scan +/// position according to the `AFTER MATCH SKIP` mode. On no match it moves one row forward. +/// +/// ## What it expects from the plan +/// +/// Like [WindowAggregateOperator], this operator does not sort. `PinotMatchExchangeNodeInsertRule` puts a +/// sort exchange underneath that hash distributes on the partition keys and sorts the receiver side on +/// `(partitionKeys..., orderKeys...)`, so rows arrive grouped by partition and ordered within a partition. The +/// operator therefore buffers one partition at a time and releases it at each boundary, and never reads +/// [MatchNode#getCollations()]: the ordering has already been established below it. +/// +/// The grouping half of that assumption is verified rather than trusted. Partition keys are compared directly on the +/// incoming rows and must be monotonically increasing, so a key that reappears after its partition was closed fails +/// without retaining every previously seen key. The ordering half is not re-checked per row, because an exchange that +/// grouped correctly but sorted incorrectly is not a failure mode the exchange can produce - losing the sort loses the +/// grouping too, which the partition-key order check already catches. +/// +/// ## Guardrails throw, they never truncate +/// +/// [QueryOptionKey#MAX_ROWS_IN_MATCH_PARTITION] bounds the rows buffered for a partition and +/// [QueryOptionKey#MAX_STEPS_PER_MATCH_ATTEMPT] bounds the backtracking of one match attempt. Both raise an error, +/// because a truncated pattern result is a wrong result that nothing in the response would flag. +/// +/// ## Not supported yet +/// +/// `ALL ROWS PER MATCH` is rejected here as well as during planning: this operator emits exactly one row per +/// match, so accepting it would silently return the wrong shape of result. +public class MatchOperator extends MultiStageOperator { + private static final Logger LOGGER = LoggerFactory.getLogger(MatchOperator.class); + private static final String EXPLAIN_NAME = "MATCH_RECOGNIZE"; + static final int MAX_OUTPUT_ROWS_PER_BLOCK = 1024; + + private final MultiStageOperator _input; + private final DataSchema _resultSchema; + private final ColumnDataType[] _resultStoredTypes; + private final int[] _partitionKeys; + private final int[] _partitionComparisonKeys; + private final List<PatternSymbol> _patternSymbols; + private final MatchExpression[] _measures; + private final PartitionMatcher _matcher; + private final MatchNode.AfterMatchSkipMode _skipMode; + private final int _skipToSymbolOrdinal; + private final int _maxRowsInMatchPartition; + private final StatMap<StatKey> _statMap = new StatMap<>(StatKey.class); + + private List<Object[]> _partitionRows = new ArrayList<>(); + @Nullable + private List<Object[]> _inputRows; + private int _inputRowIndex; + private boolean _matchingPartition; + private int _scanStart; + private long _matchNumber; + @Nullable + private MseBlock.Eos _inputEos; + private int _numRows; + + public MatchOperator(OpChainExecutionContext context, MultiStageOperator input, DataSchema inputSchema, + MatchNode node) { + super(context); + if (node.getRowsPerMatchMode() != MatchNode.RowsPerMatchMode.ONE_ROW_PER_MATCH) { + throw QueryErrorCode.QUERY_EXECUTION.asException( + "ALL ROWS PER MATCH is not supported yet in MATCH_RECOGNIZE. Use ONE ROW PER MATCH (the default) and " + + "expose the per-match values you need through the MEASURES clause."); + } + _input = input; + _resultSchema = node.getDataSchema(); + _resultStoredTypes = _resultSchema.getStoredColumnDataTypes(); + List<Integer> partitionKeys = node.getPartitionKeys(); + _partitionKeys = new int[partitionKeys.size()]; + for (int i = 0; i < _partitionKeys.length; i++) { + _partitionKeys[i] = partitionKeys.get(i); + ColumnDataType partitionKeyType = inputSchema.getColumnDataType(_partitionKeys[i]); + if (partitionKeyType.isArray()) { + throw QueryErrorCode.QUERY_EXECUTION.asException( + "MATCH_RECOGNIZE PARTITION BY requires single-value columns, but column '" + + inputSchema.getColumnName(_partitionKeys[i]) + "' has type " + partitionKeyType); + } + } + // Calcite exposes the exchange distribution as an ImmutableBitSet, so the rule below this operator sorts + // partition fields by input ordinal. Preserve SQL declaration order in _partitionKeys for the output schema, but + // validate monotonic input against the order the exchange actually produces. + _partitionComparisonKeys = _partitionKeys.clone(); + Arrays.sort(_partitionComparisonKeys); + _patternSymbols = node.getPatternSymbols(); + List<MatchNode.Measure> measures = node.getMeasures(); + _measures = new MatchExpression[measures.size()]; + for (int i = 0; i < _measures.length; i++) { + _measures[i] = MatchExpression.compile(measures.get(i).getExpression(), inputSchema); + } + if (_resultSchema.size() != _partitionKeys.length + _measures.length) { + throw QueryErrorCode.QUERY_EXECUTION.asException( + "MATCH_RECOGNIZE output schema " + _resultSchema + " does not match " + _partitionKeys.length + + " partition key(s) plus " + _measures.length + " measure(s)"); + } + _skipMode = node.getAfterMatchSkipMode(); + _skipToSymbolOrdinal = node.getAfterMatchSkipToSymbolOrdinal(); + + PatternNfa nfa = PatternToNfaCompiler.compile(node.getPattern()); + _maxRowsInMatchPartition = + MatchLimits.getMaxRowsInMatchPartition(context.getOpChainMetadata(), node.getNodeHint()); + long maxStepsPerMatchAttempt = + MatchLimits.getMaxStepsPerMatchAttempt(context.getOpChainMetadata(), node.getNodeHint()); + _matcher = new PartitionMatcher(nfa, _patternSymbols, inputSchema, maxStepsPerMatchAttempt, + this::checkTerminationAndSampleUsage); + } + + @Override + protected Logger logger() { + return LOGGER; + } + + @Override + public List<MultiStageOperator> getChildOperators() { + return List.of(_input); + } + + @Override + public Type getOperatorType() { + return Type.MATCH; + } + + @Override + public String toExplainString() { + return EXPLAIN_NAME; + } + + @Override + public void registerExecution(long time, int numRows, long memoryUsedBytes, long gcTimeMs) { + _statMap.merge(StatKey.EXECUTION_TIME_MS, time); + _statMap.merge(StatKey.EMITTED_ROWS, numRows); + _statMap.merge(StatKey.ALLOCATED_MEMORY_BYTES, memoryUsedBytes); + _statMap.merge(StatKey.GC_TIME_MS, gcTimeMs); + } + + @Override + public StatMap<StatKey> copyStatMaps() { + return new StatMap<>(_statMap); + } + + @Override + protected MseBlock getNextBlock() { + List<Object[]> outputRows = new ArrayList<>(MAX_OUTPUT_ROWS_PER_BLOCK); + while (outputRows.size() < MAX_OUTPUT_ROWS_PER_BLOCK) { + if (_matchingPartition) { + emitMatches(outputRows); + continue; + } + + if (_inputRows != null) { + consumeInputRowsUntilPartitionBoundary(); + continue; + } + + if (_inputEos != null) { + if (outputRows.isEmpty()) { + return _inputEos; + } + break; + } + + MseBlock block = _input.nextBlock(); + if (block.isData()) { + _inputRows = ((MseBlock.Data) block).asRowHeap().getRows(); + _inputRowIndex = 0; + continue; + } + + _inputEos = (MseBlock.Eos) block; + if (_inputEos.isError()) { + return _inputEos; + } + if (!_partitionRows.isEmpty()) { + startMatchingPartition(); + } + } + return new RowHeapDataBlock(outputRows, _resultSchema); + } + + /// Consumes rows without allocating extracted keys. A boundary row stays in the input block until the preceding + /// partition has been fully matched and emitted. + private void consumeInputRowsUntilPartitionBoundary() { + assert _inputRows != null; + while (_inputRowIndex < _inputRows.size()) { + Object[] row = _inputRows.get(_inputRowIndex); + if (!_partitionRows.isEmpty()) { + int comparison = comparePartitionKeys(_partitionRows.get(0), row); + if (comparison > 0) { + throw QueryErrorCode.QUERY_EXECUTION.asException( + "MATCH_RECOGNIZE input is not grouped by partition key in ascending order: partition " + + partitionKeyToString(row) + " appeared after " + partitionKeyToString(_partitionRows.get(0))); + } + if (comparison < 0) { + startMatchingPartition(); + return; + } + } + if (_partitionRows.size() >= _maxRowsInMatchPartition) { + throw QueryErrorCode.SERVER_RESOURCE_LIMIT_EXCEEDED.asException( + "MATCH_RECOGNIZE partition exceeds the maximum of " + _maxRowsInMatchPartition + + " rows. Partition on a column with more distinct values, or raise the '" + + QueryOptionKey.MAX_ROWS_IN_MATCH_PARTITION + "' query option."); + } + _partitionRows.add(row); + _inputRowIndex++; + _numRows++; + checkTerminationAndSampleUsagePeriodically(_numRows, EXPLAIN_NAME); + } + _inputRows = null; + } + + @SuppressWarnings({"rawtypes", "unchecked"}) + private int comparePartitionKeys(Object[] leftRow, Object[] rightRow) { + for (int partitionKey : _partitionComparisonKeys) { + Object left = leftRow[partitionKey]; + Object right = rightRow[partitionKey]; + if (left == null) { + if (right == null) { + continue; + } + return 1; + } + if (right == null) { + return -1; + } + if (!(left instanceof Comparable)) { + throw QueryErrorCode.QUERY_EXECUTION.asException( + "MATCH_RECOGNIZE PARTITION BY value is not sortable: " + left.getClass().getName()); + } + int comparison; + try { + comparison = ((Comparable) left).compareTo(right); + } catch (ClassCastException e) { + throw QueryErrorCode.QUERY_EXECUTION.asException( + "MATCH_RECOGNIZE PARTITION BY values have incompatible types: " + left.getClass().getName() + " and " + + right.getClass().getName()); + } + if (comparison != 0) { + return comparison; + } + } + return 0; + } + + private String partitionKeyToString(Object[] row) { + StringBuilder builder = new StringBuilder("["); + for (int i = 0; i < _partitionKeys.length; i++) { + if (i > 0) { + builder.append(", "); + } + builder.append(row[_partitionKeys[i]]); + } + return builder.append(']').toString(); + } + + private void startMatchingPartition() { + _matchingPartition = true; + _scanStart = 0; + _matchNumber = 0; + } + + /// Resumes scanning the buffered partition until it is exhausted or the current output block is full. + private void emitMatches(List<Object[]> outputRows) { + List<Object[]> rows = _partitionRows; + int numPartitionRows = rows.size(); + MatchTape tape = _matcher.getTape(); + while (_scanStart < numPartitionRows && outputRows.size() < MAX_OUTPUT_ROWS_PER_BLOCK) { + checkTerminationAndSampleUsage(); + int endPos = _matcher.match(rows, _scanStart, _matchNumber + 1); + if (endPos == PartitionMatcher.NO_MATCH) { + _scanStart++; + continue; + } + _matchNumber++; + outputRows.add(buildOutputRow(rows, tape)); + _scanStart = nextScanStart(_scanStart, endPos, tape); + } + if (_scanStart >= numPartitionRows) { + _matcher.releasePartition(); + _partitionRows = new ArrayList<>(); + _matchingPartition = false; Review Comment: [P2] Implement the operator buffer-release lifecycle This cleanup only runs after a partition has been scanned successfully. A row-limit failure retains `_partitionRows` and `_inputRows`; a matcher-budget failure, expression failure, or timeout can additionally leave the partition reachable through the matcher tape. The base class now invokes `releaseBuffers()` from both `close()` and `cancel()`, but MATCH does not override that hook or `hasBufferedState()`. With the current sorted receiver, `_inputRows` can retain the entire worker input, not just one partition. Please implement the existing release contract, drop the input/partition/tape references, and release retained matcher arrays on final teardown. Extend the operator buffer-release coverage to include MATCH on partial-output and failure paths. ########## pinot-query-planner/src/main/java/org/apache/pinot/calcite/rel/rules/PinotMatchExchangeNodeInsertRule.java: ########## @@ -0,0 +1,156 @@ +/** + * 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.pinot.calcite.rel.rules; + +import java.util.ArrayList; +import java.util.HashSet; +import java.util.List; +import java.util.Set; +import javax.annotation.Nullable; +import org.apache.calcite.plan.Context; +import org.apache.calcite.plan.RelOptRuleCall; +import org.apache.calcite.plan.RelRule; +import org.apache.calcite.rel.RelCollation; +import org.apache.calcite.rel.RelCollations; +import org.apache.calcite.rel.RelDistributions; +import org.apache.calcite.rel.RelFieldCollation; +import org.apache.calcite.rel.RelNode; +import org.apache.calcite.rel.core.Exchange; +import org.apache.calcite.rel.core.Match; +import org.apache.calcite.tools.RelBuilderFactory; +import org.apache.pinot.calcite.rel.logical.PinotLogicalExchange; +import org.apache.pinot.calcite.rel.logical.PinotLogicalSortExchange; +import org.apache.pinot.query.context.PlannerContext; +import org.apache.pinot.spi.exception.QueryErrorCode; +import org.apache.pinot.spi.exception.QueryException; +import org.apache.pinot.spi.utils.CommonConstants.Broker.Request.QueryOptionKey; +import org.immutables.value.Value; + + +/// Special rule for Pinot, this rule is fixed to always insert an exchange below the MATCH_RECOGNIZE node, mirroring +/// what [PinotWindowExchangeNodeInsertRule] does for `WINDOW`. +/// +/// Row pattern recognition is only correct when every row of a `PARTITION BY` partition is evaluated by the same +/// worker, in `ORDER BY` order. The rule therefore inserts a [PinotLogicalSortExchange] hash-distributed on the +/// `PARTITION BY` keys, sorted on the receiver side. +/// +/// **The receiver-side collation is `(partitionKeys..., orderByKeys...)`, not just the `ORDER BY` keys.** Prepending +/// the partition keys makes rows arrive clustered by partition, so the runtime operator can match and flush one +/// partition at a time and release its buffer at each partition boundary. Sorting on the `ORDER BY` keys alone would +/// interleave partitions and force the operator to buffer a `Map<partitionKey, List<row>>` for the whole input until +/// end-of-stream. An `ORDER BY` key that is also a partition key is dropped from the tail: it is constant inside a +/// partition, so re-sorting on it there is a no-op. +/// +/// Sorting happens on the receiver only. Sender-side sorting is not implemented for exchanges yet (see the same +/// note in [PinotWindowExchangeNodeInsertRule]). +/// +/// A query with no `PARTITION BY` is rejected, because hashing on zero keys sends the entire table to one worker. +/// Set the [QueryOptionKey#ALLOW_MATCH_RECOGNIZE_WITHOUT_PARTITION_BY] query option to opt into that plan. +/// +/// TODO(#19395): Support sender-side sorting so the receiver can k-way merge already sorted streams instead of +/// re-sorting. [email protected] +public class PinotMatchExchangeNodeInsertRule extends RelRule<PinotMatchExchangeNodeInsertRule.Config> { + public static final PinotMatchExchangeNodeInsertRule INSTANCE = + new PinotMatchExchangeNodeInsertRule(PinotRuleUtils.PINOT_REL_FACTORY); + + public PinotMatchExchangeNodeInsertRule(RelBuilderFactory factory) { + this(ImmutablePinotMatchExchangeNodeInsertRule.Config.builder() + .relBuilderFactory(factory) + .operandSupplier(b0 -> b0.operand(Match.class).anyInputs()) + .build()); + } + + private PinotMatchExchangeNodeInsertRule(Config config) { + super(config); + } + + @Override + public boolean matches(RelOptRuleCall call) { + Match match = call.rel(0); + return !PinotRuleUtils.isExchange(match.getInput()); + } + + @Override + public void onMatch(RelOptRuleCall call) { + Match match = call.rel(0); + List<Integer> partitionKeys = match.getPartitionKeys().toList(); + if (partitionKeys.isEmpty() && !isMatchWithoutPartitionByAllowed(call)) { + throw new QueryException(QueryErrorCode.QUERY_PLANNING, + "MATCH_RECOGNIZE without a PARTITION BY clause is not allowed because the whole table has to be routed to " + + "a single worker, which does not scale and can exhaust that worker's memory. Add a PARTITION BY " + + "clause on a column with enough distinct values, or set the query option '" + + QueryOptionKey.ALLOW_MATCH_RECOGNIZE_WITHOUT_PARTITION_BY + "=true' to accept single-worker " + + "execution."); + } + + RelNode input = match.getInput(); + RelCollation collation = clusterByPartitionKeys(partitionKeys, match.getOrderKeys()); + Exchange exchange; + if (collation.getFieldCollations().isEmpty()) { + // Neither PARTITION BY nor ORDER BY: nothing to sort on, so a plain exchange onto a single worker is enough. + exchange = PinotLogicalExchange.create(input, RelDistributions.hash(partitionKeys)); + } else { + exchange = PinotLogicalSortExchange.create(input, RelDistributions.hash(partitionKeys), collation, false, true); Review Comment: Cleanup: use the current explicit Sort path This adds another caller of the deprecated `SortedMailboxReceiveOperator`; the current window exchange rule already uses an explicit Sort above the exchange. The sorted receiver accumulates all worker rows before MATCH can apply its partition limit, does not sample resource usage per received block, and returns the entire input as one block retained by `_inputRows`. Please follow the explicit Sort approach for resource sampling and bounded output blocks, and adjust the memory explanation to acknowledge the full worker-input sort buffer. Switching to FullSort alone still does not bound peak sorting memory; the per-partition MATCH limit is not a limit on this upstream accumulation. ########## pinot-query-runtime/src/main/java/org/apache/pinot/query/runtime/operator/match/MatchTape.java: ########## @@ -0,0 +1,187 @@ +/** + * 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.pinot.query.runtime.operator.match; + +import it.unimi.dsi.fastutil.ints.IntArrayList; +import java.util.List; +import javax.annotation.Nullable; +import org.apache.pinot.query.planner.logical.RexExpression; +import org.apache.pinot.query.planner.plannode.PatternSymbol; + + +/// The classifier tape of the match currently being explored: which pattern variable each row of the candidate match +/// is mapped to, plus everything the MEASURES and DEFINE expressions need in order to navigate it. +/// +/// ## Append only, O(1) backtrack +/// +/// The tape grows by one entry every time the matcher consumes a row ([#push]) and shrinks by one every time it +/// backtracks over that row ([#pop]). Both are O(1): [#pop] only decrements lengths, it never rebuilds an +/// index. The per symbol position lists are maintained the same way, which makes [#lastRow] and +/// [#firstRow] O(1) as well, so logical navigation does not degrade into a scan of the match. +/// +/// ## Rows are addressed by partition index +/// +/// All row indexes handed out by this class are indexes into the partition, not into the match, because physical +/// navigation (`PREV` / `NEXT`) may leave the match while staying inside the partition. The invariant +/// `getEndPos() == getStartPos() + getLength()` always holds: the rows of a match are contiguous. +/// +/// ## Running semantics +/// +/// While the matcher is exploring, the tape holds only the rows matched so far, so a DEFINE predicate evaluated +/// through it automatically sees SQL:2016 *running* semantics. The candidate row is pushed *before* its own +/// predicate is evaluated, which is what makes `PREV(A.col, 0)` inside `DEFINE A` resolve to the current +/// row. Once the match is complete the tape holds all of its rows, so the same lookups give *final* semantics for +/// MEASURES. +/// +/// Not thread safe: one instance belongs to one [PartitionMatcher]. +public class MatchTape { + /// Returned by [#lastRow] and [#firstRow] when no such row exists. + public static final int NO_ROW = -1; + + private final List<PatternSymbol> _patternSymbols; + /// Partition row indexes mapped to each symbol, in ascending order; index is the symbol ordinal. + private final IntArrayList[] _rowsBySymbol; + + private List<Object[]> _partitionRows = List.of(); + private int _startPos; + private int[] _labels = new int[16]; + private int _length; + private long _matchNumber; + + public MatchTape(List<PatternSymbol> patternSymbols) { + _patternSymbols = patternSymbols; + _rowsBySymbol = new IntArrayList[patternSymbols.size()]; + for (int i = 0; i < _rowsBySymbol.length; i++) { + _rowsBySymbol[i] = new IntArrayList(); + } + } + + /// Starts a new match attempt at `startPos` of `partitionRows`. `matchNumber` is the value + /// `MATCH_NUMBER()` reports, which SQL:2016 assigns before the match is known to succeed. + public void reset(List<Object[]> partitionRows, int startPos, long matchNumber) { + _partitionRows = partitionRows; + _startPos = startPos; + _length = 0; + _matchNumber = matchNumber; + for (IntArrayList rows : _rowsBySymbol) { + rows.clear(); + } Review Comment: Cleanup: bound or reclaim cumulative per-symbol tape capacity `IntArrayList.clear()` retains its backing array, including when `releasePartition()` calls this reset. With `PATTERN (A+ | B+ | ... | Z+)` and successive million-row partitions classified entirely as A, then B, and so on, each symbol's list can retain a million positions. That is at least 104 MB across 26 symbols, outside the 64 MiB backtracking-array cap, despite processing one partition at a time. Consider reclaiming oversized per-symbol arrays at partition boundaries or budgeting their combined retained capacity. Final operator teardown should also release this storage. ########## pinot-query-planner/src/main/java/org/apache/pinot/query/planner/logical/RelToPlanNodeConverter.java: ########## @@ -681,6 +703,342 @@ private WindowNode convertLogicalWindow(LogicalWindow node) { aggCalls, windowFrameType, lowerBound, upperBound, fromRexWindowExclusion(windowGroup.exclude), constants); } + /// Converts Calcite's [Match] (SQL:2016 MATCH_RECOGNIZE) into a [MatchNode]. + /// + /// The main job is lowering Calcite's encoding of the `PATTERN` clause - a `RexCall` tree of + /// PATTERN_CONCAT / PATTERN_ALTER / PATTERN_QUANTIFIER over string literals - into the explicit + /// [RowPattern] tree, and binding every pattern variable reference to an ordinal in the symbol table so that + /// the operator never string-matches variable names. + /// + /// [org.apache.pinot.query.validate.MatchRecognizeValidator] runs on the `SqlNode` tree before + /// conversion: it rewrites an omitted `AFTER MATCH` to `SKIP PAST LAST ROW` (the SQL:2016 default, not + /// Calcite's `SKIP TO NEXT ROW`) and rejects the constructs that are not supported yet. No default is + /// re-applied here. The rejections repeated below are a safety net: [MatchNode] cannot represent those + /// constructs, so dropping one silently would return wrong rows. + private MatchNode convertLogicalMatch(Match node) { + if (node.isAllRows()) { + throw new QueryException(QueryErrorCode.QUERY_PLANNING, + "ALL ROWS PER MATCH is not supported yet in MATCH_RECOGNIZE. Use ONE ROW PER MATCH (the default) and " + + "expose the per-match values you need through the MEASURES clause."); + } + if (!node.getSubsets().isEmpty()) { + throw new QueryException(QueryErrorCode.QUERY_PLANNING, + "SUBSET is not supported yet in MATCH_RECOGNIZE. Remove the SUBSET clause and reference the individual " + + "pattern variables directly."); + } + if (node.getInterval() != null) { + throw new QueryException(QueryErrorCode.QUERY_PLANNING, + "WITHIN is not supported yet in MATCH_RECOGNIZE. Remove the WITHIN clause and bound the match with a " + + "predicate in the DEFINE clause instead."); + } + if (node.getMeasures().isEmpty()) { + // Calcite's SqlValidatorImpl.validateMatchRecognize sets the row type of a measures-less MATCH_RECOGNIZE to the + // whole input row type, which is not the ONE ROW PER MATCH shape at all. MatchRecognizeValidator already + // rejects this on the SqlNode tree; this is the safety net, because the output schema below would otherwise be + // silently wrong rather than merely unsupported. + throw new QueryException(QueryErrorCode.QUERY_PLANNING, + "MATCH_RECOGNIZE requires a MEASURES clause. ONE ROW PER MATCH emits the PARTITION BY columns plus the " + + "MEASURES, so add at least one measure, e.g. MEASURES MATCH_NUMBER() AS mno."); + } + + validateMatchPartitionKeyTypes(node); + for (Map.Entry<String, RexNode> measure : node.getMeasures().entrySet()) { + validateMatchAggregateOperandTypes(measure.getValue(), measure.getKey()); + } + + // Order the symbol table by first appearance in PATTERN so the ordinals are deterministic and independent of the + // iteration order of Calcite's pattern definition map. + Map<String, Integer> symbolOrdinals = new LinkedHashMap<>(); + collectPatternSymbols(node.getPattern(), symbolOrdinals); + Map<String, RexNode> patternDefinitions = node.getPatternDefinitions(); + // A DEFINE for a variable that never appears in PATTERN is dead code, but keep it in the table rather than + // dropping it silently. + for (String name : patternDefinitions.keySet()) { + symbolOrdinals.putIfAbsent(name, symbolOrdinals.size()); + } + + List<PatternSymbol> patternSymbols = new ArrayList<>(symbolOrdinals.size()); + for (String name : symbolOrdinals.keySet()) { + RexNode definition = patternDefinitions.get(name); + // Per SQL:2016 a pattern variable with no DEFINE entry matches every row; that is modeled as a null definition. + patternSymbols.add(new PatternSymbol(name, + definition != null ? toBoundRexExpression(definition, symbolOrdinals) : null)); + } + + List<MatchNode.Measure> measures = new ArrayList<>(node.getMeasures().size()); + for (Map.Entry<String, RexNode> measure : node.getMeasures().entrySet()) { + measures.add( + new MatchNode.Measure(measure.getKey(), toBoundRexExpression(measure.getValue(), symbolOrdinals))); + } + + RowPattern pattern = + withAnchors(toRowPattern(node.getPattern(), symbolOrdinals), node.isStrictStart(), node.isStrictEnd()); + + RexNode after = node.getAfter(); + MatchNode.AfterMatchSkipMode afterMatchSkipMode = toAfterMatchSkipMode(after); + // Only SKIP TO FIRST / SKIP TO LAST have a target variable; the other modes keep NO_SKIP_TO_SYMBOL, which must + // stay distinguishable from the legitimate ordinal 0. + boolean hasSkipTarget = afterMatchSkipMode == MatchNode.AfterMatchSkipMode.TO_FIRST + || afterMatchSkipMode == MatchNode.AfterMatchSkipMode.TO_LAST; + int afterMatchSkipToSymbolOrdinal = + hasSkipTarget ? toAfterMatchSkipToSymbolOrdinal((RexCall) after, symbolOrdinals) + : MatchNode.NO_SKIP_TO_SYMBOL; + + return new MatchNode(DEFAULT_STAGE_ID, toDataSchema(node.getRowType()), NodeHint.EMPTY, + convertInputs(node.getInputs()), patternSymbols, pattern, measures, partitionKeysInSourceOrder(node), + node.getOrderKeys().getFieldCollations(), afterMatchSkipMode, afterMatchSkipToSymbolOrdinal, + MatchNode.RowsPerMatchMode.ONE_ROW_PER_MATCH); + } + + private static void validateMatchPartitionKeyTypes(Match node) { + List<RelDataTypeField> inputFields = node.getInput().getRowType().getFieldList(); + for (int partitionKey : node.getPartitionKeys()) { + RelDataTypeField field = inputFields.get(partitionKey); + if (field.getType().getSqlTypeName() == SqlTypeName.ARRAY) { + throw new QueryException(QueryErrorCode.QUERY_PLANNING, + "MATCH_RECOGNIZE does not support multi-value or ARRAY PARTITION BY columns: '" + field.getName() + + "'. Partition by a single-value column instead."); + } + } + } + + private static void validateMatchAggregateOperandTypes(RexNode expression, String measureName) { + if (!(expression instanceof RexCall)) { + return; + } + RexCall call = (RexCall) expression; + if (call.getOperator() instanceof SqlAggFunction) { + for (RexNode operand : call.getOperands()) { + if (operand.getType().getSqlTypeName() == SqlTypeName.ARRAY) { + throw new QueryException(QueryErrorCode.QUERY_PLANNING, + "MATCH_RECOGNIZE measure '" + measureName + "' applies aggregate '" + call.getOperator().getName() + + "' to a multi-value or ARRAY operand, which is not supported. Aggregate a single-value column " + + "instead."); + } + } + } + for (RexNode operand : call.getOperands()) { + validateMatchAggregateOperandTypes(operand, measureName); + } + } + + /// The input column indexes of the `PARTITION BY` keys, in `PARTITION BY` **source** order. + /// + /// `MatchOperator` emits the partition columns positionally in this order, so it has to agree with the output row + /// type. [Match#getPartitionKeys()] is an `ImmutableBitSet` and has lost the order; [PinotLogicalMatch] recovered it + /// right after `SqlToRelConverter`, while the input field names still matched the `PARTITION BY` names. + private static List<Integer> partitionKeysInSourceOrder(Match node) { + if (node instanceof PinotLogicalMatch) { + return ((PinotLogicalMatch) node).getPartitionKeysInSourceOrder(); + } + // Any other Match only knows its keys as a set, which is the source order only for a single partition column. + int numPartitionFields = node.getRowType().getFieldCount() - node.getMeasures().size(); + Preconditions.checkState(numPartitionFields <= 1, + "MATCH_RECOGNIZE with %s PARTITION BY columns must be planned as a PinotLogicalMatch to keep their order, " + + "got: %s", numPartitionFields, node); + return node.getPartitionKeys().asList(); + } + + /// Registers every pattern variable of `pattern` in `symbolOrdinals`, in order of first appearance. + private static void collectPatternSymbols(RexNode pattern, Map<String, Integer> symbolOrdinals) { + if (pattern instanceof RexLiteral) { + symbolOrdinals.putIfAbsent(RexLiteral.stringValue(pattern), symbolOrdinals.size()); + return; + } + if (pattern instanceof RexCall) { + for (RexNode operand : patternChildren((RexCall) pattern)) { + collectPatternSymbols(operand, symbolOrdinals); + } + } + } + + /// The sub-pattern operands of a pattern call. All operands are sub-patterns except for a quantifier, whose last + /// three operands are the bounds and the reluctant flag rather than pattern variables. + private static List<RexNode> patternChildren(RexCall call) { + return call.getKind() == SqlKind.PATTERN_QUANTIFIER ? call.getOperands().subList(0, 1) : call.getOperands(); + } + + private RowPattern toRowPattern(RexNode pattern, Map<String, Integer> symbolOrdinals) { + if (pattern instanceof RexLiteral) { + String name = RexLiteral.stringValue(pattern); + Integer ordinal = symbolOrdinals.get(name); + Preconditions.checkState(ordinal != null, "Unknown MATCH_RECOGNIZE pattern variable: %s", name); + return new RowPattern.Symbol(ordinal); + } + Preconditions.checkState(pattern instanceof RexCall, "Unsupported MATCH_RECOGNIZE PATTERN node: %s", pattern); + RexCall call = (RexCall) pattern; + switch (call.getKind()) { + case PATTERN_CONCAT: + return new RowPattern.Concat(flattenRowPatterns(call, symbolOrdinals)); + case PATTERN_ALTER: + return new RowPattern.Alternate(flattenRowPatterns(call, symbolOrdinals)); + case PATTERN_QUANTIFIER: + return toQuantifier(call, symbolOrdinals); + case PATTERN_PERMUTE: + throw new QueryException(QueryErrorCode.QUERY_PLANNING, + "PERMUTE is not supported yet in the MATCH_RECOGNIZE PATTERN clause. Expand the permutation into an " + + "explicit alternation, e.g. PATTERN ((A B) | (B A))."); + case PATTERN_EXCLUDED: + throw new QueryException(QueryErrorCode.QUERY_PLANNING, + "Pattern exclusions '{- -}' are not supported yet in the MATCH_RECOGNIZE PATTERN clause. Remove the " + + "exclusion; note that exclusions only affect ALL ROWS PER MATCH output, which is also not " + + "supported yet."); + default: + throw new QueryException(QueryErrorCode.QUERY_PLANNING, + "Unsupported MATCH_RECOGNIZE PATTERN construct: '" + call + "'."); + } + } + + /// Flattens the left-deep binary tree Calcite builds for `A B C` and `A | B | C` into the operands of a + /// single n-ary node. Both operators are associative and the operand order is preserved, so the SQL:2016 + /// leftmost-alternative-wins rule is unaffected. + private List<RowPattern> flattenRowPatterns(RexCall call, Map<String, Integer> symbolOrdinals) { + List<RowPattern> children = new ArrayList<>(call.getOperands().size()); + flattenRowPatterns(call, call.getKind(), symbolOrdinals, children); + return children; + } + + private void flattenRowPatterns(RexNode pattern, SqlKind kind, Map<String, Integer> symbolOrdinals, + List<RowPattern> children) { + if (pattern instanceof RexCall && pattern.getKind() == kind) { + for (RexNode operand : ((RexCall) pattern).getOperands()) { + flattenRowPatterns(operand, kind, symbolOrdinals, children); + } + } else { + children.add(toRowPattern(pattern, symbolOrdinals)); + } + } + + private RowPattern toQuantifier(RexCall call, Map<String, Integer> symbolOrdinals) { + List<RexNode> operands = call.getOperands(); + Preconditions.checkState(operands.size() == 4, + "Expecting 4 operands in MATCH_RECOGNIZE pattern quantifier, got: %s", operands.size()); + RowPattern child = toRowPattern(operands.get(0), symbolOrdinals); + // Calcite writes -1 for an unspecified bound: `*`, `+` and `{n,}` leave the maximum open, `{,m}` leaves the + // minimum open. SQL:2016 reads an omitted minimum as 0, while an omitted maximum stays unbounded. + int minRepeat = toQuantifierBound(operands.get(1), call); + int maxRepeat = toQuantifierBound(operands.get(2), call); + if (minRepeat == UNSPECIFIED_QUANTIFIER_BOUND) { + minRepeat = 0; + } + if (maxRepeat != RowPattern.Quantifier.UNBOUNDED && maxRepeat < minRepeat) { + throw new QueryException(QueryErrorCode.QUERY_PLANNING, + "MATCH_RECOGNIZE pattern quantifier '" + call + "' has an upper bound (" + maxRepeat + + ") smaller than its lower bound (" + minRepeat + "), so it can never match."); + } + // The reluctant forms (`*?`, `+?`, `??`, `{n,m}?`) prefer the shortest match. + return new RowPattern.Quantifier(child, minRepeat, maxRepeat, !RexLiteral.booleanValue(operands.get(3))); + } + + private int toQuantifierBound(RexNode bound, RexCall call) { + int value = RexExpressionUtils.getValueAsInt(bound); + if (value < UNSPECIFIED_QUANTIFIER_BOUND) { + throw new QueryException(QueryErrorCode.QUERY_PLANNING, + "MATCH_RECOGNIZE pattern quantifier '" + call + "' has a negative repetition bound: " + value + "."); + } + if (value > MAX_PATTERN_QUANTIFIER_BOUND) { + throw new QueryException(QueryErrorCode.QUERY_PLANNING, + "MATCH_RECOGNIZE pattern quantifier bound " + value + " exceeds the maximum supported bound of " + + MAX_PATTERN_QUANTIFIER_BOUND + ": '" + call + "'. Every repetition expands into pattern matcher " + + "state, so rewrite the pattern with a smaller repetition count, or use an unbounded quantifier " + + "such as '*' or '+' together with a DEFINE predicate that bounds the match."); Review Comment: Cleanup: update the quantifier-limit rationale The message says every repetition expands matcher state, but `PatternToNfaCompiler.compileQuantifier()` now emits a counter-controlled loop rather than unrolling the repetition count. Please update the explanation to describe the actual reason for the 10,000 bound, or reconsider whether that additional bound is still needed alongside the row/step/state limits. -- 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]
