Skip to content

Commit be40091

Browse files
airborne12claude
andcommitted
[fix](nereids) Fix deep copy of scans with virtual columns
### What problem does this PR solve? Issue Number: None Related PR: #69292 Problem Summary: A CTE fails to plan when the optimizer inlines it after one of its scans got a virtual column: WITH c AS ( SELECT id, score() AS s FROM t WHERE c1 MATCH 'apple' ORDER BY s DESC LIMIT 2 ) SELECT * FROM c; -- A expression contains slot not from children A score or ANN TopN pushed into a scan, and a MATCH in the select list, add a virtual column to the scan. After rewrite, the optimizer inlines a CTE that has one consumer left (Optimizer.normalizeCtePlan) by deep copying its rewritten body, so the copy includes these scans: - score() and l2_distance_approximate() are nondeterministic, so the rewrite does not inline a CTE that calls them, even with one consumer. Once the TopN pushdown has replaced them with a virtual column of the scan, the optimizer inlines the CTE. - A CTE with MATCH in its select list reaches the optimizer when the rewrite removes all but one of its consumers, e.g. a UNION ALL branch with WHERE 1 = 0. LogicalPlanDeepCopier copied a scan with virtual columns wrongly: - it gave each virtual column two new ids: the slots above the scan were mapped to the first one, and the copied scan output the second one; - the copied scan still output the original virtual column, with its original id, next to the new one; - the score and ANN order keys of the copied scan still used the original slots. So the plan above the copied scan read a slot that the scan does not output. The copier now gives each virtual column one new id, maps the original id to it and maps the score and ANN order keys to the new slots. Relations without virtual columns are copied as before. LogicalOlapScan.withVirtualColumns replaces the virtual columns of the scan, but kept their old slots in the output next to the new ones. It now replaces them there too and keeps the other output slots, which the copier has already mapped. Computing the output of the copy again would not work: it gives VARIANT subpath slots new ids. AdjustNullable, the other caller that replaces existing virtual columns, no longer keeps two slots for a virtual column whose nullability changes. ### Release note Fix "A expression contains slot not from children" for a CTE that orders by score() or by an ANN distance with a LIMIT, or that has MATCH in its select list and is inlined after rewrite. ### Check List (For Author) - Test: Unit Test and Regression test - Unit tests: LogicalPlanDeepCopierTest.testDeepCopyOlapScanWithVirtualColumn and CTEInlineTest.inlineCteWhoseScanHasVirtualColumns (CTEs with a score TopN, an ANN TopN, a MATCH projection, and a VARIANT subpath with a MATCH projection, with one consumer and with a second consumer removed by WHERE 1 = 0). Both fail on master (4 output slots instead of 3; "A expression contains slot not from children") and pass with this change. OrExpansionTest, SplitMultiDistinctTest, DecomposeRepeatWithPreAggregationTest, LogicalOlapScanTest, IvmDeltaRewriteHelperTest and PushDownVirtualColumnsIntoOlapScanTest pass. Checkstyle passes. - Regression test: nereids_rules_p0/cte/test_cte_inline_virtual_column, with its .out generated by the framework, on an FE built from this branch and a BE built from 41a58af plus #69292's SegmentIterator change (this change is FE only). The VARIANT case is only in the unit test, because that BE reads v['x'] as NULL even without a CTE. - Behavior changed: No - Does this need documentation: No Co-Authored-By: Claude Opus 5.5 <[email protected]>
1 parent e02d93d commit be40091

7 files changed

Lines changed: 196 additions & 24 deletions

File tree

‎fe/fe-core/src/main/java/org/apache/doris/nereids/trees/copier/LogicalPlanDeepCopier.java‎

Lines changed: 27 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -113,22 +113,28 @@ public Plan visitLogicalCatalogRelation(LogicalCatalogRelation catalogRelation,
113113
newRelation = ((LogicalOlapScan) newRelation).withPartitionPruned(false);
114114
}
115115
updateReplaceMapWithOutput(catalogRelation, newRelation, context.exprIdReplaceMap);
116-
List<NamedExpression> virtualColumns = catalogRelation.getVirtualColumns().stream()
117-
.map(e -> {
118-
if (e instanceof Alias) {
119-
return new Alias(((Alias) e).child(), e.getName());
120-
}
121-
return e;
122-
})
123-
.collect(ImmutableList.toImmutableList());
124-
for (int i = 0; i < virtualColumns.size(); i++) {
125-
context.exprIdReplaceMap.put(catalogRelation.getVirtualColumns().get(i).getExprId(),
126-
virtualColumns.get(i).getExprId());
116+
if (!catalogRelation.getVirtualColumns().isEmpty()) {
117+
// Each virtual column gets a new id, and its old slot maps to that id.
118+
List<NamedExpression> virtualColumns = catalogRelation.getVirtualColumns().stream()
119+
.map(column -> {
120+
NamedExpression newColumn = column instanceof Alias
121+
? new Alias(ExpressionDeepCopier.INSTANCE.deepCopy(((Alias) column).child(),
122+
context), column.getName())
123+
: (NamedExpression) ExpressionDeepCopier.INSTANCE.deepCopy(column, context);
124+
context.exprIdReplaceMap.put(column.getExprId(), newColumn.getExprId());
125+
return newColumn;
126+
})
127+
.collect(ImmutableList.toImmutableList());
128+
newRelation = newRelation.withVirtualColumns(virtualColumns);
129+
if (newRelation instanceof LogicalOlapScan) {
130+
// The score and ANN order keys sort by virtual columns.
131+
LogicalOlapScan olapScan = (LogicalOlapScan) newRelation;
132+
newRelation = olapScan.appendVirtualColumnsAndTopN(ImmutableList.of(),
133+
copyOrderKeys(olapScan.getAnnOrderKeys(), context), olapScan.getAnnLimit(),
134+
copyOrderKeys(olapScan.getScoreOrderKeys(), context), olapScan.getScoreLimit(),
135+
olapScan.getScoreRangeInfo());
136+
}
127137
}
128-
virtualColumns = virtualColumns.stream()
129-
.map(o -> (NamedExpression) ExpressionDeepCopier.INSTANCE.deepCopy(o, context))
130-
.collect(ImmutableList.toImmutableList());
131-
newRelation = newRelation.withVirtualColumns(virtualColumns);
132138
if (catalogRelation instanceof LogicalSchemaScan
133139
&& ((LogicalSchemaScan) catalogRelation).isFilterPushed()) {
134140
LogicalSchemaScan oldSchemaScan = (LogicalSchemaScan) catalogRelation;
@@ -273,11 +279,15 @@ public Plan visitLogicalSort(LogicalSort<? extends Plan> sort, DeepCopierContext
273279
@Override
274280
public Plan visitLogicalTopN(LogicalTopN<? extends Plan> topN, DeepCopierContext context) {
275281
Plan child = topN.child().accept(this, context);
276-
List<OrderKey> orderKeys = topN.getOrderKeys().stream()
282+
List<OrderKey> orderKeys = copyOrderKeys(topN.getOrderKeys(), context);
283+
return new LogicalTopN<>(orderKeys, topN.getLimit(), topN.getOffset(), child);
284+
}
285+
286+
private static List<OrderKey> copyOrderKeys(List<OrderKey> orderKeys, DeepCopierContext context) {
287+
return orderKeys.stream()
277288
.map(o -> new OrderKey(ExpressionDeepCopier.INSTANCE.deepCopy(o.getExpr(), context),
278289
o.isAsc(), o.isNullFirst()))
279290
.collect(ImmutableList.toImmutableList());
280-
return new LogicalTopN<>(orderKeys, topN.getLimit(), topN.getOffset(), child);
281291
}
282292

283293
@Override

‎fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalOlapScan.java‎

Lines changed: 17 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -687,15 +687,13 @@ public LogicalOlapScan withTableAlias(String tableAlias) {
687687
}
688688

689689
/**
690-
* add virtual column to olap scan.
690+
* replace the virtual columns of olap scan, also in its output.
691691
* @param virtualColumns generated virtual columns
692692
* @return scan with virtual columns
693693
*/
694694
@Override
695695
public LogicalOlapScan withVirtualColumns(List<NamedExpression> virtualColumns) {
696-
LogicalProperties logicalProperties = getLogicalProperties();
697-
List<Slot> output = Lists.newArrayList(logicalProperties.getOutput());
698-
output.addAll(virtualColumns.stream().map(NamedExpression::toSlot).collect(Collectors.toList()));
696+
List<Slot> output = outputWithVirtualColumns(virtualColumns);
699697
LogicalProperties finalLogicalProperties = new LogicalProperties(() -> output, this::computeDataTrait);
700698
return AbstractPlan.copyWithSameId(this, () ->
701699
new LogicalOlapScan(relationId, (Table) table, qualifier,
@@ -707,6 +705,21 @@ public LogicalOlapScan withVirtualColumns(List<NamedExpression> virtualColumns)
707705
scoreRangeInfo, annOrderKeys, annLimit, tableAlias, partitionPrunablePredicates, scanParams));
708706
}
709707

708+
/**
709+
* The output with the slots of the given virtual columns instead of the slots of the current ones. The other
710+
* slots keep their ids, which the slots of the parent plan may already refer to.
711+
*/
712+
protected List<Slot> outputWithVirtualColumns(List<NamedExpression> newVirtualColumns) {
713+
Set<ExprId> oldVirtualColumns = virtualColumns.stream()
714+
.map(NamedExpression::getExprId)
715+
.collect(Collectors.toSet());
716+
List<Slot> output = getLogicalProperties().getOutput().stream()
717+
.filter(slot -> !oldVirtualColumns.contains(slot.getExprId()))
718+
.collect(Collectors.toCollection(ArrayList::new));
719+
newVirtualColumns.forEach(column -> output.add(column.toSlot()));
720+
return output;
721+
}
722+
710723
/**
711724
* Append additional virtual columns to existing ones.
712725
* Unlike {@link #withVirtualColumns} which replaces, this merges existing + new.

‎fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalOlapTableStreamScan.java‎

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -445,9 +445,7 @@ public LogicalOlapTableStreamScan withTableAlias(String tableAlias) {
445445

446446
@Override
447447
public LogicalOlapTableStreamScan withVirtualColumns(List<NamedExpression> virtualColumns) {
448-
LogicalProperties logicalProperties = getLogicalProperties();
449-
List<Slot> output = Lists.newArrayList(logicalProperties.getOutput());
450-
output.addAll(virtualColumns.stream().map(NamedExpression::toSlot).collect(Collectors.toList()));
448+
List<Slot> output = outputWithVirtualColumns(virtualColumns);
451449
LogicalProperties finalLogicalProperties = new LogicalProperties(() -> output, this::computeDataTrait);
452450
return AbstractPlan.copyWithSameId(this, () ->
453451
new LogicalOlapTableStreamScan(relationId, (Table) table, qualifier,

‎fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/CTEInlineTest.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -50,6 +50,24 @@ protected void runBeforeAll() throws Exception {
5050
+ "DUPLICATE KEY(id)\n"
5151
+ "DISTRIBUTED BY HASH(id) BUCKETS 1\n"
5252
+ "PROPERTIES (\"replication_num\" = \"1\")");
53+
createTable("CREATE TABLE cte_inline_text (\n"
54+
+ " id int NULL,\n"
55+
+ " c1 text NULL,\n"
56+
+ " v variant NULL,\n"
57+
+ " INDEX idx_c1 (c1) USING INVERTED PROPERTIES (\"parser\" = \"english\")\n"
58+
+ ") ENGINE=OLAP\n"
59+
+ "DUPLICATE KEY(id)\n"
60+
+ "DISTRIBUTED BY HASH(id) BUCKETS 1\n"
61+
+ "PROPERTIES (\"replication_num\" = \"1\", \"inverted_index_storage_format\" = \"V3\")");
62+
createTable("CREATE TABLE cte_inline_ann (\n"
63+
+ " id int NOT NULL,\n"
64+
+ " embedding array<float> NOT NULL,\n"
65+
+ " INDEX idx_ann (embedding) USING ANN PROPERTIES (\n"
66+
+ " \"index_type\" = \"hnsw\", \"metric_type\" = \"l2_distance\", \"dim\" = \"2\")\n"
67+
+ ") ENGINE=OLAP\n"
68+
+ "DUPLICATE KEY(id)\n"
69+
+ "DISTRIBUTED BY HASH(id) BUCKETS 1\n"
70+
+ "PROPERTIES (\"replication_num\" = \"1\")");
5371
}
5472

5573
@Test
@@ -158,4 +176,28 @@ public void refreshCteConsumersAfterNormalizeEliminatesEmptyBranch() {
158176
connectContext.getSessionVariable().setDisableNereidsRules("");
159177
}
160178
}
179+
180+
@Test
181+
public void inlineCteWhoseScanHasVirtualColumns() {
182+
// The score and ANN TopN and the MATCH projection add virtual columns to the scan of the CTE,
183+
// before the optimizer inlines it.
184+
connectContext.getSessionVariable().setDisableNereidsRules("PRUNE_EMPTY_PARTITION");
185+
try {
186+
for (String body : new String[] {
187+
"select id, score() as s from cte_inline_text where c1 match 'apple' order by s desc limit 2",
188+
"select id from cte_inline_ann order by l2_distance_approximate(embedding, [1.0, 2.0]) limit 2",
189+
"select id, c1 match 'apple' as m from cte_inline_text",
190+
// The copied scan also outputs the VARIANT subpath, whose slot the copy has mapped.
191+
"select id, v['x'] as x, c1 match 'apple' as m from cte_inline_text"}) {
192+
for (String query : new String[] {"with cte as (%s) select * from cte",
193+
"with cte as (%s) select * from cte union all select * from cte where 1 = 0"}) {
194+
String sql = String.format(query, body);
195+
Assertions.assertDoesNotThrow(() -> PlanChecker.from(connectContext).checkPlannerResult(sql),
196+
sql);
197+
}
198+
}
199+
} finally {
200+
connectContext.getSessionVariable().setDisableNereidsRules("");
201+
}
202+
}
161203
}

‎fe/fe-core/src/test/java/org/apache/doris/nereids/trees/copier/LogicalPlanDeepCopierTest.java‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -18,11 +18,14 @@
1818
package org.apache.doris.nereids.trees.copier;
1919

2020
import org.apache.doris.catalog.SchemaTable;
21+
import org.apache.doris.nereids.properties.OrderKey;
22+
import org.apache.doris.nereids.trees.expressions.Alias;
2123
import org.apache.doris.nereids.trees.expressions.EqualTo;
2224
import org.apache.doris.nereids.trees.expressions.Expression;
2325
import org.apache.doris.nereids.trees.expressions.NamedExpression;
2426
import org.apache.doris.nereids.trees.expressions.Slot;
2527
import org.apache.doris.nereids.trees.expressions.SlotReference;
28+
import org.apache.doris.nereids.trees.expressions.functions.scalar.Score;
2629
import org.apache.doris.nereids.trees.expressions.literal.VarcharLiteral;
2730
import org.apache.doris.nereids.trees.plans.Plan;
2831
import org.apache.doris.nereids.trees.plans.algebra.Repeat.RepeatType;
@@ -84,6 +87,30 @@ public void testDeepCopyOlapScanInvalidatesPartitionPruning() {
8487
Assertions.assertTrue(copiedPlan.hasPartitionPredicate());
8588
}
8689

90+
@Test
91+
public void testDeepCopyOlapScanWithVirtualColumn() {
92+
LogicalOlapScan scan = PlanConstructor.newLogicalOlapScan(0, "a", 0);
93+
Alias scoreColumn = new Alias(new Score(), "__score");
94+
scan = scan.appendVirtualColumnsAndTopN(ImmutableList.of(scoreColumn), ImmutableList.of(), Optional.empty(),
95+
ImmutableList.of(new OrderKey(scoreColumn.toSlot(), false, false)), Optional.of(0L),
96+
Optional.empty());
97+
DeepCopierContext context = new DeepCopierContext();
98+
LogicalOlapScan copy = (LogicalOlapScan) scan.accept(LogicalPlanDeepCopier.INSTANCE, context);
99+
100+
// The copy outputs one new score column, which its order key and the slots above it use.
101+
Slot copiedScore = copy.getVirtualColumns().get(0).toSlot();
102+
Assertions.assertNotEquals(scoreColumn.getExprId(), copiedScore.getExprId());
103+
Assertions.assertEquals(scan.getOutput().size(), copy.getOutput().size());
104+
Assertions.assertTrue(copy.getOutput().contains(copiedScore));
105+
Assertions.assertFalse(copy.getOutput().contains(scoreColumn.toSlot()));
106+
Assertions.assertEquals(copiedScore, copy.getScoreOrderKeys().get(0).getExpr());
107+
Assertions.assertEquals(copiedScore.getExprId(), context.exprIdReplaceMap.get(scoreColumn.getExprId()));
108+
for (Slot slot : scan.getOutput()) {
109+
Assertions.assertTrue(copy.getOutputExprIdSet().contains(context.exprIdReplaceMap.get(slot.getExprId())),
110+
slot.toString());
111+
}
112+
}
113+
87114
@Test
88115
public void testDeepCopyOlapScanWithNonFirstOperativeSlot() {
89116
LogicalOlapScan relationPlan = PlanConstructor.newLogicalOlapScan(0, "a", 0);
Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
-- This file is automatically generated. You should know what you did if you want to edit this
2+
-- !score_topn --
3+
1 0.69596696
4+
2 0.49917626
5+
6+
-- !ann_topn --
7+
1
8+
2
9+
10+
-- !match_projection --
11+
1 true
12+
2 true
13+
3 false
14+
Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
// The score and ANN TopN and the MATCH projection add virtual columns to the scan of a CTE,
19+
// which is copied when the optimizer inlines the CTE.
20+
suite("test_cte_inline_virtual_column") {
21+
sql "DROP TABLE IF EXISTS test_cte_inline_virtual_column_text"
22+
sql """
23+
CREATE TABLE test_cte_inline_virtual_column_text (
24+
id INT,
25+
c1 TEXT,
26+
INDEX idx_c1 (c1) USING INVERTED PROPERTIES ("parser" = "english")
27+
) DUPLICATE KEY(id) DISTRIBUTED BY HASH(id) BUCKETS 1
28+
PROPERTIES ("replication_num" = "1", "inverted_index_storage_format" = "V3")
29+
"""
30+
sql """
31+
INSERT INTO test_cte_inline_virtual_column_text VALUES
32+
(1, 'apple apple apple'), (2, 'apple banana'), (3, 'banana cherry')
33+
"""
34+
35+
sql "DROP TABLE IF EXISTS test_cte_inline_virtual_column_ann"
36+
sql """
37+
CREATE TABLE test_cte_inline_virtual_column_ann (
38+
id INT NOT NULL,
39+
embedding ARRAY<FLOAT> NOT NULL,
40+
INDEX idx_ann (embedding) USING ANN PROPERTIES (
41+
"index_type" = "hnsw", "metric_type" = "l2_distance", "dim" = "2")
42+
) DUPLICATE KEY(id) DISTRIBUTED BY HASH(id) BUCKETS 1
43+
PROPERTIES ("replication_num" = "1")
44+
"""
45+
sql """
46+
INSERT INTO test_cte_inline_virtual_column_ann VALUES
47+
(1, [1.0, 2.0]), (2, [2.0, 3.0]), (3, [10.0, 10.0])
48+
"""
49+
50+
order_qt_score_topn """
51+
WITH c AS (
52+
SELECT id, score() AS s FROM test_cte_inline_virtual_column_text
53+
WHERE c1 MATCH 'apple' ORDER BY s DESC LIMIT 2
54+
)
55+
SELECT * FROM c
56+
"""
57+
order_qt_ann_topn """
58+
WITH c AS (
59+
SELECT id FROM test_cte_inline_virtual_column_ann
60+
ORDER BY l2_distance_approximate(embedding, [1.0, 2.0]) LIMIT 2
61+
)
62+
SELECT * FROM c
63+
"""
64+
order_qt_match_projection """
65+
WITH c AS (SELECT id, c1 MATCH 'apple' AS m FROM test_cte_inline_virtual_column_text)
66+
SELECT * FROM c UNION ALL SELECT * FROM c WHERE 1 = 0
67+
"""
68+
}

0 commit comments

Comments
 (0)