Skip to content

Commit 07bcd31

Browse files
authored
[improvement](fe) Prune partition keys from partition topn sort (apache#63379)
### What problem does this PR solve? Issue Number: close #xxx Related PR: #xxx Problem Summary: PartitionTopN still passed partition key expressions to BE sort info when the same original slot also appeared in window order keys. These keys are constant inside each partition, so keeping them causes redundant comparison work and noisy explain output, especially after slot remapping changes ExprIds. ``` before | 1:VPartitionTopN(42) | | | functions: rank | | | partition by: c_region[#3] | | | order by: c_region[#5] ASC, c_custkey[#6] ASC | | | has global limit: false | | | partition limit: 1 | | | partition topn phase: TWO_PHASE_LOCAL_PTOPN | | | distribute expr lists: c_custkey[#4] ``` after ``` | 1:VPartitionTopN(42) | | | functions: rank | | | partition by: c_region[#3] | | | order by: c_custkey[#6] ASC | | | has global limit: false | | | partition limit: 1 | | | partition topn phase: TWO_PHASE_LOCAL_PTOPN | | | distribute expr lists: c_custkey[#4] | | | ``` This PR also adds a guard for self-join cases where the partition key and order key come from the same original table column, but from different join inputs. Example: ```sql EXPLAIN SELECT * FROM ( SELECT l.c2 AS lc2, r.c2 AS rc2, row_number() OVER ( PARTITION BY l.c2 ORDER BY r.c2 ) AS rn FROM test_global_partition_topn_plan l JOIN test_global_partition_topn_plan r ON l.c1 = r.c1 ) tmp WHERE rn <= 1; ``` Here l.c2 and r.c2 both come from test_global_partition_topn_plan.c2, but they are different slots after the self join. PARTITION BY l.c2 only guarantees that the left-side c2 is constant inside each partition. It does not guarantee that the right-side r.c2 is constant, so ORDER BY r.c2 must not be pruned. The expected EXPLAIN should still keep the order key in VPartitionTopN: ``` 1:VPartitionTopN | functions: row_number | partition by: c2[#0] | order by: c2[#3] ASC | has global limit: false | partition limit: 1 | partition topn phase: TWO_PHASE_LOCAL_PTOPN The different slot ids, c2[#0] and c2[#3], show that the partition key and order key are different join outputs. If the order key were pruned here, the row selected by rn <= 1 could become nondeterministic or incorrect. ```
1 parent 1fa3ca3 commit 07bcd31

15 files changed

Lines changed: 312 additions & 69 deletions

File tree

‎fe/fe-core/src/main/java/org/apache/doris/nereids/properties/ChildOutputPropertyDeriver.java‎

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -421,7 +421,14 @@ public PhysicalProperties visitPhysicalPartitionTopN(PhysicalPartitionTopN<? ext
421421
Preconditions.checkState(childDistSpec instanceof DistributionSpecHash,
422422
"child dist spec is not hash spec");
423423

424-
return new PhysicalProperties(childDistSpec, new OrderSpec(partitionTopN.getOrderKeys()));
424+
// Declare the delivered order via getOutputOrderKeys() (= [partitionKeys, orderKeys]), NOT
425+
// getOrderKeys() (= orderKeys only). getOrderKeys() is the executable sort key list sent to BE, from
426+
// which order keys that duplicate a partition key are pruned (they are constant within each partition,
427+
// so sorting on them is redundant). The two-phase-global output order property, however, must remain
428+
// the full [partitionKeys, orderKeys] -- the same order this node declared before that pruning split.
429+
// Keeping it full stays in lockstep with the parent window's required order (RequestPropertyDeriver),
430+
// so OrderSpec.satisfy passes and no redundant sort enforcer is inserted above this PartitionTopN.
431+
return new PhysicalProperties(childDistSpec, new OrderSpec(partitionTopN.getOutputOrderKeys()));
425432
}
426433
}
427434

‎fe/fe-core/src/main/java/org/apache/doris/nereids/rules/RuleSet.java‎

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -103,7 +103,6 @@
103103
import org.apache.doris.nereids.rules.implementation.SplitAggMultiPhase;
104104
import org.apache.doris.nereids.rules.implementation.SplitAggMultiPhaseWithoutGbyKey;
105105
import org.apache.doris.nereids.rules.implementation.SplitAggWithoutDistinct;
106-
import org.apache.doris.nereids.rules.rewrite.CreatePartitionTopNFromWindow;
107106
import org.apache.doris.nereids.rules.rewrite.EliminateFilter;
108107
import org.apache.doris.nereids.rules.rewrite.EliminateOuterJoin;
109108
import org.apache.doris.nereids.rules.rewrite.MaxMinFilterPushDown;
@@ -163,7 +162,6 @@ public class RuleSet {
163162

164163
public static final List<RuleFactory> PUSH_DOWN_FILTERS = ImmutableList.of(
165164
new MaxMinFilterPushDown(),
166-
new CreatePartitionTopNFromWindow(),
167165
new PushDownFilterThroughProject(),
168166
new PushDownFilterThroughSort(),
169167
new PushDownJoinOtherCondition(),

‎fe/fe-core/src/main/java/org/apache/doris/nereids/rules/implementation/LogicalPartitionTopNToPhysicalPartitionTopN.java‎

Lines changed: 8 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -50,15 +50,14 @@ public Rule build() {
5050

5151
private List<PhysicalPartitionTopN<? extends Plan>> generatePhysicalPartitionTopn(
5252
LogicalPartitionTopN<? extends Plan> logicalPartitionTopN) {
53+
List<OrderKey> orderKeys = !logicalPartitionTopN.getOrderKeys().isEmpty()
54+
? logicalPartitionTopN.getOrderKeys().stream()
55+
.map(OrderExpression::getOrderKey)
56+
.collect(ImmutableList.toImmutableList()) :
57+
ImmutableList.of();
5358
if (logicalPartitionTopN.getPartitionKeys().isEmpty()
5459
|| !checkTwoPhaseGlobalPartitionTopn(logicalPartitionTopN)) {
5560
// if no partition by keys, use local partition topn combined with further full sort
56-
List<OrderKey> orderKeys = !logicalPartitionTopN.getOrderKeys().isEmpty()
57-
? logicalPartitionTopN.getOrderKeys().stream()
58-
.map(OrderExpression::getOrderKey)
59-
.collect(ImmutableList.toImmutableList()) :
60-
ImmutableList.of();
61-
6261
PhysicalPartitionTopN<Plan> onePhaseLocalPartitionTopN = new PhysicalPartitionTopN<>(
6362
logicalPartitionTopN.getFunction(),
6463
logicalPartitionTopN.getPartitionKeys(),
@@ -71,13 +70,10 @@ private List<PhysicalPartitionTopN<? extends Plan>> generatePhysicalPartitionTop
7170

7271
return ImmutableList.of(onePhaseLocalPartitionTopN);
7372
} else {
74-
// if partition by keys exist, the order keys will be set as original partition keys combined with
75-
// orderby keys, to meet upper window operator's order requirement.
76-
ImmutableList<OrderKey> fullOrderKeys = getAllOrderKeys(logicalPartitionTopN);
7773
PhysicalPartitionTopN<Plan> onePhaseGlobalPartitionTopN = new PhysicalPartitionTopN<>(
7874
logicalPartitionTopN.getFunction(),
7975
logicalPartitionTopN.getPartitionKeys(),
80-
fullOrderKeys,
76+
orderKeys,
8177
logicalPartitionTopN.hasGlobalLimit(),
8278
logicalPartitionTopN.getPartitionLimit(),
8379
PartitionTopnPhase.ONE_PHASE_GLOBAL_PTOPN,
@@ -87,7 +83,7 @@ private List<PhysicalPartitionTopN<? extends Plan>> generatePhysicalPartitionTop
8783
PhysicalPartitionTopN<Plan> twoPhaseLocalPartitionTopN = new PhysicalPartitionTopN<>(
8884
logicalPartitionTopN.getFunction(),
8985
logicalPartitionTopN.getPartitionKeys(),
90-
fullOrderKeys,
86+
orderKeys,
9187
logicalPartitionTopN.hasGlobalLimit(),
9288
logicalPartitionTopN.getPartitionLimit(),
9389
PartitionTopnPhase.TWO_PHASE_LOCAL_PTOPN,
@@ -97,7 +93,7 @@ private List<PhysicalPartitionTopN<? extends Plan>> generatePhysicalPartitionTop
9793
PhysicalPartitionTopN<Plan> twoPhaseGlobalPartitionTopN = new PhysicalPartitionTopN<>(
9894
logicalPartitionTopN.getFunction(),
9995
logicalPartitionTopN.getPartitionKeys(),
100-
fullOrderKeys,
96+
orderKeys,
10197
logicalPartitionTopN.hasGlobalLimit(),
10298
logicalPartitionTopN.getPartitionLimit(),
10399
PartitionTopnPhase.TWO_PHASE_GLOBAL_PTOPN,
@@ -166,23 +162,4 @@ private boolean checkPartitionKeys(List<Expression> partitionKeys) {
166162
}
167163
return true;
168164
}
169-
170-
private ImmutableList<OrderKey> getAllOrderKeys(LogicalPartitionTopN<? extends Plan> logicalPartitionTopN) {
171-
ImmutableList.Builder<OrderKey> builder = ImmutableList.builder();
172-
173-
if (!logicalPartitionTopN.getPartitionKeys().isEmpty()) {
174-
builder.addAll(logicalPartitionTopN.getPartitionKeys().stream().map(partitionKey -> {
175-
return new OrderKey(partitionKey, true, false);
176-
}).collect(ImmutableList.toImmutableList()));
177-
}
178-
179-
if (!logicalPartitionTopN.getOrderKeys().isEmpty()) {
180-
builder.addAll(logicalPartitionTopN.getOrderKeys().stream()
181-
.map(OrderExpression::getOrderKey)
182-
.collect(ImmutableList.toImmutableList())
183-
);
184-
}
185-
186-
return builder.build();
187-
}
188165
}

‎fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/EliminateOrderByKey.java‎

Lines changed: 30 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -89,7 +89,17 @@ private static Plan eliminateWindow(LogicalWindow<Plan> window) {
8989
for (OrderExpression orderExpression : orderExpressions) {
9090
orderKeys.add(orderExpression.getOrderKey());
9191
}
92-
List<OrderKey> retainExpression = eliminate(dataTrait, orderKeys);
92+
// an order key that repeats one of the window's own partition keys is constant within each
93+
// partition, so ordering by it is redundant and can be pruned (in addition to the data-trait
94+
// based elimination below).
95+
Set<Expression> partitionKeyConstants = ImmutableSet.copyOf(windowExpression.getPartitionKeys());
96+
List<OrderKey> retainExpression = eliminate(dataTrait, orderKeys, partitionKeyConstants);
97+
// When every order key is redundant the retained list becomes empty, which is fine: an order key
98+
// is only pruned when it is constant within each partition (duplicate / equal to a partition key /
99+
// uniform / functionally constant), so it carried no intra-partition ordering. Dropping it changes
100+
// neither the framed result (for a RANGE frame a constant key keeps the whole partition as one peer
101+
// group, exactly like an empty ORDER BY) nor the partition topn pushdown, and it lets partition topn
102+
// drop the redundant partition key. This matches the existing behavior introduced with this rule.
93103
if (retainExpression.size() == orderKeys.size()) {
94104
newNamedExpressions.add(expr);
95105
continue;
@@ -117,6 +127,19 @@ private static Plan eliminateSort(LogicalSort<Plan> sort) {
117127
}
118128

119129
private static List<OrderKey> eliminate(DataTrait dataTrait, List<OrderKey> inputOrderKeys) {
130+
return eliminate(dataTrait, inputOrderKeys, ImmutableSet.of());
131+
}
132+
133+
/**
134+
* Eliminate redundant order keys.
135+
*
136+
* @param partitionKeyConstants exprs that are constant within the scope of the order keys (e.g. a window's
137+
* partition keys, which are constant inside each partition); an order key equal to one of them is
138+
* redundant. Empty for a plain sort. They are still recorded as dominants so that order keys
139+
* functionally dependent on them are eliminated too.
140+
*/
141+
private static List<OrderKey> eliminate(DataTrait dataTrait, List<OrderKey> inputOrderKeys,
142+
Set<Expression> partitionKeyConstants) {
120143
Set<Slot> validSlots = new HashSet<>();
121144
for (OrderKey inputOrderKey : inputOrderKeys) {
122145
Expression expr = inputOrderKey.getExpr();
@@ -137,6 +160,12 @@ private static List<OrderKey> eliminate(DataTrait dataTrait, List<OrderKey> inpu
137160
if (orderExprWithEqualSet.contains(expr)) {
138161
continue;
139162
}
163+
// eliminate by partition key (constant within each partition for window order keys)
164+
if (partitionKeyConstants.contains(expr)) {
165+
orderExprWithEqualSet.add(expr);
166+
orderExprWithEqualSet.addAll(dataTrait.calEqualSet((Slot) expr));
167+
continue;
168+
}
140169
// eliminate by uniform
141170
if (dataTrait.isUniformAndNotNull((Slot) expr)) {
142171
orderExprWithEqualSet.add(expr);

‎fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/physical/PhysicalPartitionTopN.java‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -104,10 +104,31 @@ public List<Expression> getPartitionKeys() {
104104
return partitionKeys;
105105
}
106106

107+
/**
108+
* Executable sort keys sent to BE (PartitionSortNode.SortInfo): only the within-partition order keys.
109+
* Order keys that duplicate a partition key are already pruned (constant within a partition, so sorting on
110+
* them is redundant). For the order this node declares to its parent, use {@link #getOutputOrderKeys()}.
111+
*/
107112
public List<OrderKey> getOrderKeys() {
108113
return orderKeys;
109114
}
110115

116+
/**
117+
* Output order property declared to the parent (for ChildOutputPropertyDeriver), NOT executed by BE:
118+
* [partitionKeys, orderKeys]. Each partition key is wrapped as an ascending, nulls-last OrderKey and
119+
* prepended to the executable {@link #getOrderKeys()}. This is the full order the (two-phase-global)
120+
* PartitionTopN delivers, kept in lockstep with the parent window's required order so OrderSpec.satisfy
121+
* passes without a redundant sort enforcer, even though BE only sorts by the pruned getOrderKeys().
122+
*/
123+
public List<OrderKey> getOutputOrderKeys() {
124+
return ImmutableList.<OrderKey>builder()
125+
.addAll(partitionKeys.stream()
126+
.map(partitionKey -> new OrderKey(partitionKey, true, false))
127+
.collect(ImmutableList.toImmutableList()))
128+
.addAll(orderKeys)
129+
.build();
130+
}
131+
111132
@Override
112133
public boolean hasGlobalLimit() {
113134
return hasGlobalLimit;

‎fe/fe-core/src/test/java/org/apache/doris/nereids/glue/translator/PhysicalPlanTranslatorTest.java‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@
2020
import org.apache.doris.analysis.Expr;
2121
import org.apache.doris.analysis.GroupingInfo;
2222
import org.apache.doris.analysis.SlotRef;
23+
import org.apache.doris.analysis.SortInfo;
2324
import org.apache.doris.analysis.TupleDescriptor;
2425
import org.apache.doris.analysis.TupleId;
2526
import org.apache.doris.catalog.Column;
@@ -48,6 +49,7 @@
4849
import org.apache.doris.nereids.util.PlanConstructor;
4950
import org.apache.doris.planner.AggregationNode;
5051
import org.apache.doris.planner.OlapScanNode;
52+
import org.apache.doris.planner.PartitionSortNode;
5153
import org.apache.doris.planner.PlanFragment;
5254
import org.apache.doris.planner.PlanNode;
5355
import org.apache.doris.planner.PlanNodeId;
@@ -266,6 +268,37 @@ public void accept(NereidsPlanner planner) {
266268
});
267269
}
268270

271+
@Test
272+
public void testPartitionTopNPrunesPartitionKeyFromSortInfo() throws Exception {
273+
connectContext.getSessionVariable().setEnablePartitionTopN(true);
274+
String sql = "select * from (select a, b, rank() over(partition by a order by a, b) as rk "
275+
+ "from test_db.t) t where rk <= 1";
276+
Planner planner = getSQLPlanner(sql);
277+
Assertions.assertNotNull(planner);
278+
279+
List<PartitionSortNode> partitionSortNodes = new ArrayList<>();
280+
for (PlanFragment fragment : planner.getFragments()) {
281+
PlanNode root = fragment.getPlanRoot();
282+
if (root != null) {
283+
root.collect(PartitionSortNode.class, partitionSortNodes);
284+
}
285+
}
286+
Assertions.assertFalse(partitionSortNodes.isEmpty());
287+
288+
Field sortInfoField = PartitionSortNode.class.getDeclaredField("info");
289+
sortInfoField.setAccessible(true);
290+
SortInfo sortInfo = (SortInfo) sortInfoField.get(partitionSortNodes.get(0));
291+
List<Expr> orderingExprs = sortInfo.getOrderingExprs();
292+
Assertions.assertEquals(1, orderingExprs.size());
293+
// The redundant partition key `a` must be pruned, leaving exactly the slot `b`. Assert the slot
294+
// identity directly: a substring check on the WITH_TABLE-rendered SQL would false-pass because the
295+
// table prefix `test_db` already contains the letter "b".
296+
Expr orderingExpr = orderingExprs.get(0);
297+
Assertions.assertInstanceOf(SlotRef.class, orderingExpr);
298+
Assertions.assertEquals("b", ((SlotRef) orderingExpr).getColumnName());
299+
Assertions.assertNotEquals("a", ((SlotRef) orderingExpr).getColumnName());
300+
}
301+
269302
private OlapScanNode getFirstOlapScanNode(String sql) throws Exception {
270303
Planner planner = getSQLPlanner(sql);
271304
Assertions.assertNotNull(planner);

‎fe/fe-core/src/test/java/org/apache/doris/nereids/rules/implementation/ImplementationTest.java‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,9 +28,11 @@
2828
import org.apache.doris.nereids.trees.expressions.literal.Literal;
2929
import org.apache.doris.nereids.trees.plans.GroupPlan;
3030
import org.apache.doris.nereids.trees.plans.LimitPhase;
31+
import org.apache.doris.nereids.trees.plans.PartitionTopnPhase;
3132
import org.apache.doris.nereids.trees.plans.Plan;
3233
import org.apache.doris.nereids.trees.plans.PlanType;
3334
import org.apache.doris.nereids.trees.plans.RelationId;
35+
import org.apache.doris.nereids.trees.plans.WindowFuncType;
3436
import org.apache.doris.nereids.trees.plans.logical.LogicalFilter;
3537
import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
3638
import org.apache.doris.nereids.trees.plans.logical.LogicalLimit;
@@ -41,6 +43,7 @@
4143
import org.apache.doris.nereids.trees.plans.logical.LogicalSort;
4244
import org.apache.doris.nereids.trees.plans.logical.LogicalTopN;
4345
import org.apache.doris.nereids.trees.plans.physical.PhysicalLimit;
46+
import org.apache.doris.nereids.trees.plans.physical.PhysicalPartitionTopN;
4447
import org.apache.doris.nereids.trees.plans.physical.PhysicalPlan;
4548
import org.apache.doris.nereids.trees.plans.physical.PhysicalProject;
4649
import org.apache.doris.nereids.trees.plans.physical.PhysicalTopN;
@@ -135,4 +138,24 @@ public void toPhysicalLimitTest() {
135138
Assertions.assertEquals(limit, physicalLimit.getLimit());
136139
Assertions.assertEquals(offset, physicalLimit.getOffset());
137140
}
141+
142+
@Test
143+
public void physicalPartitionTopNSeparatesSortKeysFromOutputOrderKeys() {
144+
SlotReference partitionKey = new SlotReference("col1", IntegerType.INSTANCE);
145+
SlotReference orderExpr = new SlotReference("col2", IntegerType.INSTANCE);
146+
OrderKey orderKey = new OrderKey(orderExpr, true, true);
147+
PhysicalPartitionTopN<GroupPlan> partitionTopN = new PhysicalPartitionTopN<>(
148+
WindowFuncType.ROW_NUMBER,
149+
ImmutableList.of(partitionKey),
150+
ImmutableList.of(orderKey),
151+
false,
152+
10,
153+
PartitionTopnPhase.TWO_PHASE_GLOBAL_PTOPN,
154+
groupPlan.getLogicalProperties(),
155+
groupPlan);
156+
157+
Assertions.assertEquals(ImmutableList.of(orderKey), partitionTopN.getOrderKeys());
158+
Assertions.assertEquals(ImmutableList.of(new OrderKey(partitionKey, true, false), orderKey),
159+
partitionTopN.getOutputOrderKeys());
160+
}
138161
}

0 commit comments

Comments
 (0)