This is an automated email from the ASF dual-hosted git repository.
englefly pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new 9ea1b774a3f [fix](lazy topn) Fix slot-not-found after
PullUpProjectExprUnderTopN with chained expressions (#64486)
9ea1b774a3f is described below
commit 9ea1b774a3f1699a2dffad3f1c29ee682c0455b4
Author: minghong <[email protected]>
AuthorDate: Mon Jun 15 14:34:40 2026 +0800
[fix](lazy topn) Fix slot-not-found after PullUpProjectExprUnderTopN with
chained expressions (#64486)
### What problem does this PR solve?
this pr refactor PullUpProjectExprUnderTopN to avoid slot-not-found error.
in this version, pullup is done in bottom up algorithm. it makes pullup
simpler than previous version
Issue Number: close #xxx
Related PR: #63736
Problem Summary:
### Release note
None
### Check List (For Author)
- Test <!-- At least one of them must be included. -->
- [ ] Regression test
- [ ] Unit Test
- [ ] Manual test (add detailed scripts or steps below)
- [ ] No need to test or manual test. Explain why:
- [ ] This is a refactor/code format and no logic has been changed.
- [ ] Previous test can cover this change.
- [ ] No code files have been changed.
- [ ] Other reason <!-- Add your reason? -->
- Behavior changed:
- [ ] No.
- [ ] Yes. <!-- Explain the behavior change -->
- Does this need documentation?
- [ ] No.
- [ ] Yes. <!-- Add document PR link here. eg:
https://github.com/apache/doris-website/pull/1214 -->
### Check List (For Reviewer who merge this PR)
- [ ] Confirm the release note
- [ ] Confirm test cases
- [ ] Confirm document
- [ ] Add branch pick label <!-- Add branch pick label that this PR
should merge into -->
---
.../rules/rewrite/PullUpProjectExprUnderTopN.java | 473 +++++++--------------
.../rewrite/PullUpProjectExprUnderTopNTest.java | 283 +++++++-----
2 files changed, 316 insertions(+), 440 deletions(-)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PullUpProjectExprUnderTopN.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PullUpProjectExprUnderTopN.java
index 26964be4467..b225bb891e3 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PullUpProjectExprUnderTopN.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PullUpProjectExprUnderTopN.java
@@ -45,13 +45,11 @@ import org.apache.doris.nereids.util.ExpressionUtils;
import org.apache.doris.qe.ConnectContext;
import org.apache.doris.qe.SessionVariable;
-import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
-import java.util.IdentityHashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
@@ -61,18 +59,11 @@ import java.util.Set;
* Pull up non-trivial expressions from Projects below TopN to above TopN,
* exposing their input base columns as lazy materialization candidates.
*
- * <p>Two-pass CustomRewriter:
- * <ol>
- * <li><b>Collector (top-down)</b>: walk the plan tree, find qualifying TopNs,
- * walk into their descendants to find Projects with pull-able expressions.
- * Any operator that references a slot blocks pulling up expressions that
- * output that slot past it. Boundary nodes (Aggregate, Window, Repeat,
- * Relation, CTEProducer) stop the walk.
- * Set operators are treated as blockers for the current TopN but their
- * children are still traversed so nested TopNs inside them are
visited.</li>
- * <li><b>Replacer (bottom-up)</b>: simplify found Projects and add upper
- * Projects above TopN to restore pulled-up expressions.</li>
- * </ol>
+ * <p>The rewriter runs bottom-up. Each LogicalTopN is treated as the current
+ * target TopN after its child has already been rewritten. The target TopN then
+ * collects only Projects in its own child subtree, stops at nested TopNs, and
+ * adds one upper Project to restore the original TopN output. This lets an
+ * upper TopN pull expressions that were just restored above a lower TopN.
*/
public class PullUpProjectExprUnderTopN implements CustomRewriter {
@@ -84,20 +75,7 @@ public class PullUpProjectExprUnderTopN implements
CustomRewriter {
return plan;
}
- // Pass 1: Collect pull-up info
- CollectorContext collectorCtx = new CollectorContext();
- plan.accept(new Collector(), collectorCtx);
-
- if (collectorCtx.topNToPullUpInfo.isEmpty()) {
- return plan;
- }
-
- // Deduplicate: when nested TopNs both try to pull up the same
expression
- // from the same Project, keep it only in the outermost TopN.
- deduplicatePullUps(collectorCtx);
-
- // Pass 2: Replace/restructure
- return plan.accept(new Replacer(), collectorCtx);
+ return plan.accept(new Rewriter(), new RewriteContext());
}
//
=========================================================================
@@ -111,8 +89,7 @@ public class PullUpProjectExprUnderTopN implements
CustomRewriter {
final List<NamedExpression> allPulledUpExprs = new ArrayList<>();
final Map<LogicalProject<? extends Plan>, List<NamedExpression>>
projectToPulledUpExprs
= new LinkedHashMap<>();
- final Map<ExprId, List<Slot>> baseSlotsByExpr = new HashMap<>();
- final Map<ExprId, NamedExpression> passThroughExprByDeduplicatedExpr =
new HashMap<>();
+ final Map<Slot, Expression> pullUpExprReplaceMap = new
LinkedHashMap<>();
PullUpInfo(LogicalTopN topN) {
this.topN = topN;
@@ -122,49 +99,7 @@ public class PullUpProjectExprUnderTopN implements
CustomRewriter {
void addPulledUpExpr(LogicalProject<? extends Plan> project,
NamedExpression expr) {
allPulledUpExprs.add(expr);
projectToPulledUpExprs.computeIfAbsent(project, k -> new
ArrayList<>()).add(expr);
- baseSlotsByExpr.put(expr.getExprId(),
ImmutableList.copyOf(expr.getInputSlots()));
- }
-
- void addPassThroughExprForDeduplicatedExpr(NamedExpression expr) {
- passThroughExprByDeduplicatedExpr.put(expr.getExprId(), expr);
- }
- }
-
- /** Context shared between collector and replacer passes. */
- static class CollectorContext {
- /**
- * Use IdentityHashMap so that two different TopN nodes with the same
- * content (orderKeys, limit, offset) are treated as distinct keys.
- * LogicalTopN.equals() is content-based, which would cause unrelated
- * TopN nodes to collide in a regular HashMap/LinkedHashMap.
- */
- final Map<LogicalTopN, PullUpInfo> topNToPullUpInfo = new
IdentityHashMap<>();
- /**
- * Maintain insertion order for deterministic outer-to-inner iteration
- * in dedup and other passes. The Collector visits the plan top-down,
- * so the order is naturally outer-before-inner.
- */
- final List<LogicalTopN> topNOrder = new ArrayList<>();
- final Map<Slot, Expression> pullUpExprReplaceMap = new
LinkedHashMap<>();
- /**
- * When collectFromNode encounters a nested TopN, it saves the current
- * blockedExprIds (accumulated from outer nodes) so that
visitLogicalTopN
- * for the inner TopN can merge them into its fresh blocked set.
- */
- final Map<LogicalTopN, Set<ExprId>> outerBlockedByTopN = new
IdentityHashMap<>();
- int cteProducerDepth = 0;
-
- boolean hasPullUpInfo(LogicalTopN topN) {
- return topNToPullUpInfo.containsKey(topN);
- }
-
- PullUpInfo getPullUpInfo(LogicalTopN topN) {
- return topNToPullUpInfo.get(topN);
- }
-
- void addPullUpInfo(LogicalTopN topN, PullUpInfo info) {
- topNToPullUpInfo.put(topN, info);
- topNOrder.add(topN);
+ addPullUpExprReplace(expr);
}
void addPullUpExprReplace(NamedExpression expr) {
@@ -174,8 +109,13 @@ public class PullUpProjectExprUnderTopN implements
CustomRewriter {
}
}
+ /** Context for the bottom-up traversal. */
+ static class RewriteContext {
+ int cteProducerDepth = 0;
+ }
+
//
=========================================================================
- // Pass 1: Collector (top-down)
+ // Bottom-up TopN rewriter
//
=========================================================================
private static boolean qualifiesForLazyMatThreshold(LogicalTopN topN) {
@@ -187,11 +127,11 @@ public class PullUpProjectExprUnderTopN implements
CustomRewriter {
return threshold >= limit;
}
- static class Collector extends DefaultPlanRewriter<CollectorContext> {
+ static class Rewriter extends DefaultPlanRewriter<RewriteContext> {
@Override
public Plan visitLogicalCTEProducer(
- LogicalCTEProducer<? extends Plan> cteProducer,
CollectorContext context) {
+ LogicalCTEProducer<? extends Plan> cteProducer, RewriteContext
context) {
context.cteProducerDepth++;
try {
return visit(cteProducer, context);
@@ -201,32 +141,25 @@ public class PullUpProjectExprUnderTopN implements
CustomRewriter {
}
@Override
- public Plan visitLogicalTopN(LogicalTopN topN, CollectorContext
context) {
- if (context.cteProducerDepth > 0
- || !qualifiesForLazyMatThreshold(topN)) {
- return visit(topN, context);
+ public Plan visitLogicalTopN(LogicalTopN topN, RewriteContext context)
{
+ LogicalTopN rewritten = (LogicalTopN) visit(topN, context);
+ if (context.cteProducerDepth > 0 ||
!qualifiesForLazyMatThreshold(rewritten)) {
+ return rewritten;
}
- PullUpInfo info = new PullUpInfo(topN);
+ PullUpInfo info = new PullUpInfo(rewritten);
// Seed blockedExprIds with this TopN's order key ExprIds so that
// expressions used by order keys are not pulled up past this TopN.
- Set<ExprId> blockedExprIds = buildOrderKeyExprIds(topN);
- // If this is a nested TopN, merge in the outer blocked set that
was
- // saved by collectFromNode when it encountered this TopN. This
- // ensures that slots consumed by outer operators (e.g. join
- // conditions above this TopN) also block pull-up from projects
- // under this TopN.
- Set<ExprId> outerBlocked = context.outerBlockedByTopN.remove(topN);
- if (outerBlocked != null) {
- blockedExprIds.addAll(outerBlocked);
+ collectFromNode((Plan) rewritten.child(0), info,
buildOrderKeyExprIds(rewritten));
+ if (info.allPulledUpExprs.isEmpty()) {
+ return rewritten;
}
- collectFromNode((Plan) topN.child(0), info, blockedExprIds,
context);
- if (!info.allPulledUpExprs.isEmpty()) {
- for (NamedExpression expr : info.allPulledUpExprs) {
- context.addPullUpExprReplace(expr);
- }
- context.addPullUpInfo(topN, info);
+
+ Plan simplifiedChild = ((Plan) rewritten.child(0)).accept(new
ProjectSimplifier(), info);
+ if (simplifiedChild == rewritten.child(0)) {
+ return rewritten;
}
- return visit(topN, context);
+ LogicalTopN topNWithSimplifiedChild =
rewritten.withChildren(ImmutableList.of(simplifiedChild));
+ return addUpperProject(topNWithSimplifiedChild, info);
}
}
@@ -237,37 +170,28 @@ public class PullUpProjectExprUnderTopN implements
CustomRewriter {
* along the path from the TopN to the current node. An expression whose
output ExprId
* is in this set cannot be pulled up past the operators that reference it.
*/
- private static void collectFromNode(Plan node, PullUpInfo info,
Set<ExprId> blockedExprIds,
- CollectorContext context) {
+ private static void collectFromNode(Plan node, PullUpInfo info,
Set<ExprId> blockedExprIds) {
if (node instanceof LogicalProject) {
LogicalProject<? extends Plan> project = (LogicalProject<? extends
Plan>) node;
+ Set<ExprId> childBlockedExprIds = new HashSet<>(blockedExprIds);
for (NamedExpression ne : project.getProjects()) {
- if (canPullUp(ne) && !blockedExprIds.contains(ne.getExprId()))
{
+ info.addPullUpExprReplace(ne);
+ boolean canPullUp = canPullUp(ne);
+ if (canPullUp && !blockedExprIds.contains(ne.getExprId())) {
info.addPulledUpExpr(project, ne);
}
+ if (shouldBlockProjectInputs(ne, canPullUp, blockedExprIds)) {
+ childBlockedExprIds.addAll(ne.getInputSlotExprIds());
+ }
}
// Continue into the project's child. Chained projects are all
visited.
- collectFromNode((Plan) project.child(0), info, blockedExprIds,
context);
+ collectFromNode((Plan) project.child(0), info,
childBlockedExprIds);
return;
}
if (node instanceof LogicalTopN) {
- LogicalTopN inner = (LogicalTopN) node;
- // Save the current blockedExprIds (accumulated from outer nodes
- // such as outer TopN + intermediate Joins) so that the inner
- // TopN's own visitLogicalTopN can merge them into its fresh
- // blocked set. Without this, outer join condition slots would
- // not block pull-up from projects under the inner TopN.
- context.outerBlockedByTopN.put(inner, new
HashSet<>(blockedExprIds));
- // Stop traversal here — do NOT collect expressions from under
- // the inner TopN using the outer TopN's PullUpInfo. The inner
- // TopN has its own visitLogicalTopN which will handle its subtree
- // independently. If the outer TopN were to collect expressions
- // from under the inner TopN, dedup would move them to the outer
- // TopN and the inner TopN would only see passThroughExprs. The
- // passThrough mechanism only propagates base slots, which breaks
- // downstream Projects that reference the original expression slot
- // by ExprId (e.g. a "c1 AS c2" rename between the two TopNs).
+ // The bottom-up rewriter has already handled this nested TopN.
+ // The current target TopN only collects Projects above it.
return;
}
@@ -324,7 +248,7 @@ public class PullUpProjectExprUnderTopN implements
CustomRewriter {
}
}
for (Plan child : node.children()) {
- collectFromNode(child, info, newBlocked, context);
+ collectFromNode(child, info, newBlocked);
}
return;
}
@@ -341,7 +265,7 @@ public class PullUpProjectExprUnderTopN implements
CustomRewriter {
}
for (Plan child : node.children()) {
- collectFromNode(child, info, newBlocked, context);
+ collectFromNode(child, info, newBlocked);
}
}
@@ -376,6 +300,26 @@ public class PullUpProjectExprUnderTopN implements
CustomRewriter {
return true;
}
+ private static boolean shouldBlockProjectInputs(
+ NamedExpression ne, boolean canPullUp, Set<ExprId> blockedExprIds)
{
+ if (blockedExprIds.contains(ne.getExprId())) {
+ return true;
+ }
+ if (!(ne instanceof Alias)) {
+ return false;
+ }
+ Expression child = ne.child(0);
+ if (child instanceof Slot || child instanceof Literal) {
+ return false;
+ }
+ // Non-forwarding aliases that cannot be synthesized above TopN must
+ // keep their inputs below TopN. Otherwise, a lower pull-up can remove
+ // the input slot and make this alias look unavailable, causing it to
+ // be reconstructed above TopN through pullUpExprReplaceMap and bypass
+ // canPullUp(), e.g. z = assert_true(x > 0), x = a + 1.
+ return !canPullUp;
+ }
+
private static boolean isBlockingNode(Plan node) {
return node instanceof LogicalAggregate
|| node instanceof LogicalWindow
@@ -394,131 +338,61 @@ public class PullUpProjectExprUnderTopN implements
CustomRewriter {
return orderKeyExprIds;
}
- /**
- * Deduplicate pull-up expressions so that each expression in a Project is
only
- * pulled up to the outermost TopN that collects it.
- *
- * <p>Iteration uses {@link CollectorContext#topNOrder} which preserves the
- * Collector's top-down visit order (outer-to-inner). We keep the first
- * occurrence of each (project-reference, exprId) pair and remove
duplicates
- * from inner TopNs.
- */
- private static void deduplicatePullUps(CollectorContext context) {
- // Use IdentityHashMap because we need to distinguish Project nodes by
object
- // reference, not by content equality.
- Map<LogicalProject<? extends Plan>, Set<ExprId>> handled = new
IdentityHashMap<>();
-
- for (LogicalTopN topN : context.topNOrder) {
- PullUpInfo info = context.topNToPullUpInfo.get(topN);
- List<NamedExpression> toRemove = new ArrayList<>();
- for (Map.Entry<LogicalProject<? extends Plan>,
List<NamedExpression>> entry
- : info.projectToPulledUpExprs.entrySet()) {
- LogicalProject<? extends Plan> project = entry.getKey();
- Set<ExprId> projectHandled = handled.computeIfAbsent(project,
k -> new HashSet<>());
- for (NamedExpression expr : entry.getValue()) {
- if (projectHandled.contains(expr.getExprId())) {
- toRemove.add(expr);
- } else {
- projectHandled.add(expr.getExprId());
- }
- }
- }
- for (NamedExpression expr : toRemove) {
- info.addPassThroughExprForDeduplicatedExpr(expr);
- info.allPulledUpExprs.remove(expr);
- for (List<NamedExpression> list :
info.projectToPulledUpExprs.values()) {
- list.removeIf(e -> e == expr);
- }
- info.baseSlotsByExpr.remove(expr.getExprId());
- }
- info.projectToPulledUpExprs.entrySet().removeIf(e ->
e.getValue().isEmpty());
- }
- }
-
- //
=========================================================================
- // Pass 2: Replacer (bottom-up)
- //
=========================================================================
-
- static class Replacer extends DefaultPlanRewriter<CollectorContext> {
-
+ static class ProjectSimplifier extends DefaultPlanRewriter<PullUpInfo> {
@Override
- public Plan visitLogicalProject(LogicalProject<? extends Plan>
project, CollectorContext context) {
- LogicalProject<? extends Plan> rewritten = (LogicalProject<?
extends Plan>) visit(project, context);
-
- // Collect ALL pulled-up expressions across ALL PullUpInfos for
this
- // project. After dedup, each expression belongs to exactly one
TopN
- // (the outermost one that can pull it up). The project needs to be
- // simplified by removing all of them, exposing their base slots
once.
- List<NamedExpression> allPulledUpExprs =
collectAllPulledUpExprs(context, rewritten);
- if (allPulledUpExprs.isEmpty() && rewritten != project
- && rewritten.getProjects().equals(project.getProjects())) {
- allPulledUpExprs = collectAllPulledUpExprs(context, project);
- }
- return simplifyProject(rewritten, allPulledUpExprs, context);
+ public Plan visitLogicalTopN(LogicalTopN topN, PullUpInfo info) {
+ return topN;
}
@Override
- public Plan visitLogicalTopN(LogicalTopN topN, CollectorContext
context) {
- LogicalTopN rewritten = (LogicalTopN) visit(topN, context);
- // If the subtree was not modified by the replacer, no Projects
- // below were simplified, so the pulled-up expressions' base
- // slots may not be exposed. Skip addUpperProject to avoid
- // computing the expression redundantly above AND below.
- if (rewritten == topN) {
- return rewritten;
- }
- PullUpInfo info = context.getPullUpInfo(topN);
- if (info == null) {
- return rewritten;
- }
- if (info.allPulledUpExprs.isEmpty()
- && info.passThroughExprByDeduplicatedExpr.isEmpty()) {
- return rewritten;
- }
- return addUpperProject(rewritten, info, context);
- }
- }
-
- /**
- * Collect all pulled-up expressions across all PullUpInfos for a project.
- * After dedup each expression belongs to exactly one TopN, but the project
- * must be simplified by removing all of them at once.
- */
- private static List<NamedExpression> collectAllPulledUpExprs(
- CollectorContext context, LogicalProject<?> project) {
- List<NamedExpression> result = new ArrayList<>();
- for (LogicalTopN topN : context.topNOrder) {
- PullUpInfo info = context.topNToPullUpInfo.get(topN);
- List<NamedExpression> exprs =
info.projectToPulledUpExprs.get(project);
+ public Plan visitLogicalProject(LogicalProject<? extends Plan>
project, PullUpInfo info) {
+ LogicalProject<? extends Plan> rewritten = (LogicalProject<?
extends Plan>) visit(project, info);
+ List<NamedExpression> exprs =
info.projectToPulledUpExprs.get(rewritten);
if (exprs != null) {
- result.addAll(exprs);
+ return simplifyProject(rewritten, exprs, info);
}
+ if (rewritten != project &&
rewritten.getProjects().equals(project.getProjects())) {
+ exprs = info.projectToPulledUpExprs.get(project);
+ if (exprs != null) {
+ return simplifyProject(rewritten, exprs, info);
+ }
+ }
+ return simplifyProject(rewritten, ImmutableList.of(), info);
}
- return result;
}
/**
- * Remove pulled-up expressions from this Project and add the input slots
that still need to pass through TopN.
+ * Remove pulled-up expressions from this Project and expose their base
input slots.
*
- * <p>For example, after pulling up {@code x = a + 1}:
+ * <p>For example, pulling up {@code x = a + 1} from cascaded Projects:
*
* <pre>
- * TopN
- * Project(id, x) -- forwards x from its child
- * Project(id, a + 1 as x)
- * Scan(id, a)
- * </pre>
+ * Before:
+ * TopN
+ * Project(id, x) -- forwards x from child
+ * Project(id, a + 1 AS x)
+ * Scan(id, a)
*
- * <p>The lower Project should become {@code Project(id, a)}, because
{@code x} is restored above TopN.
- * The upper Project must also become {@code Project(id, a)} instead of
keeping {@code Project(id, x)},
- * since its child no longer outputs {@code x}.
+ * After simplifyProject (both Projects lose x, gain a):
+ * TopN
+ * Project(id, a) -- x removed because child no longer
outputs it
+ * Project(id, a) -- a+1 removed, base slot a exposed
+ * Scan(id, a)
+ *
+ * {@code addUpperProject} then restores the computation above TopN:
+ * Project(id, a + 1 AS x) -- new upper Project
+ * TopN
+ * Project(id, a)
+ * Project(id, a)
+ * Scan(id, a)
+ * </pre>
*/
private static LogicalProject<? extends Plan> simplifyProject(
LogicalProject<? extends Plan> project,
List<NamedExpression> pulledUpExprs,
- CollectorContext context) {
+ PullUpInfo info) {
Set<ExprId> childOutputExprIds = ((Plan)
project.child(0)).getOutputExprIdSet();
- List<Expression> passThroughExprs =
collectUnavailablePullUpExprs(project, context, childOutputExprIds);
+ List<Expression> passThroughExprs =
collectUnavailablePullUpExprs(project, info, childOutputExprIds);
if (pulledUpExprs.isEmpty() && passThroughExprs.isEmpty()) {
return project;
}
@@ -531,29 +405,26 @@ public class PullUpProjectExprUnderTopN implements
CustomRewriter {
List<NamedExpression> simplified = new ArrayList<>();
Set<ExprId> existingExprIds = new HashSet<>();
for (NamedExpression ne : project.getProjects()) {
- if (!pulledUpExprIds.contains(ne.getExprId())
- && !isUnavailablePullUpSlot(ne, context,
childOutputExprIds)) {
- NamedExpression resolved = resolveNamedExpression(ne, context,
childOutputExprIds);
- simplified.add(resolved);
- existingExprIds.add(resolved.getExprId());
+ if (!pulledUpExprIds.contains(ne.getExprId())) {
+ Expression replaceExpr =
getPullUpReplaceExpression(ne.toSlot(), info);
+ if (replaceExpr == null || !isUnavailableExpression(ne,
childOutputExprIds)) {
+ NamedExpression resolved = resolveAliasChildIfNeeded(ne,
info, childOutputExprIds);
+ simplified.add(resolved);
+ existingExprIds.add(resolved.getExprId());
+ }
}
}
for (NamedExpression pulledUpExpr : pulledUpExprs) {
- for (PullUpInfo info : context.topNToPullUpInfo.values()) {
- if (info.baseSlotsByExpr.get(pulledUpExpr.getExprId()) !=
null) {
- for (Slot baseSlot : resolveInputSlots(pulledUpExpr,
context, childOutputExprIds)) {
- if (!existingExprIds.contains(baseSlot.getExprId())) {
- simplified.add(baseSlot);
- existingExprIds.add(baseSlot.getExprId());
- }
- }
- break; // found, no need to check other PullUpInfos
+ for (Slot baseSlot : resolveInputSlots(pulledUpExpr.child(0),
info, childOutputExprIds)) {
+ if (!existingExprIds.contains(baseSlot.getExprId())) {
+ simplified.add(baseSlot);
+ existingExprIds.add(baseSlot.getExprId());
}
}
}
for (Expression passThroughExpr : passThroughExprs) {
- for (Slot baseSlot : resolveInputSlots(passThroughExpr, context,
childOutputExprIds)) {
+ for (Slot baseSlot : resolveInputSlots(passThroughExpr, info,
childOutputExprIds)) {
if (!existingExprIds.contains(baseSlot.getExprId())) {
simplified.add(baseSlot);
existingExprIds.add(baseSlot.getExprId());
@@ -568,151 +439,103 @@ public class PullUpProjectExprUnderTopN implements
CustomRewriter {
}
private static List<Expression> collectUnavailablePullUpExprs(
- LogicalProject<? extends Plan> project, CollectorContext context,
Set<ExprId> childOutputExprIds) {
+ LogicalProject<? extends Plan> project, PullUpInfo info,
Set<ExprId> childOutputExprIds) {
List<Expression> passThroughExprs = new ArrayList<>();
for (NamedExpression ne : project.getProjects()) {
- if (isUnavailablePullUpSlot(ne, context, childOutputExprIds)) {
- passThroughExprs.add(getPullUpReplaceExpression((Slot) ne,
context));
+ Expression replaceExpr = getPullUpReplaceExpression(ne.toSlot(),
info);
+ if (replaceExpr != null && isUnavailableExpression(ne,
childOutputExprIds)) {
+ passThroughExprs.add(replaceExpr);
}
}
return passThroughExprs;
}
- private static boolean isUnavailablePullUpSlot(
- NamedExpression ne, CollectorContext context, Set<ExprId>
childOutputExprIds) {
- return ne instanceof Slot
- && !childOutputExprIds.contains(ne.getExprId())
- && getPullUpReplaceExpression((Slot) ne, context) != null;
+ /** Check the non-replaceExpr conditions for unavailability.
+ * Caller must have already verified {@code
getPullUpReplaceExpression(ne.toSlot()) != null}. */
+ private static boolean isUnavailableExpression(NamedExpression ne,
Set<ExprId> childOutputExprIds) {
+ if (ne instanceof Slot) {
+ return !childOutputExprIds.contains(ne.getExprId());
+ }
+ return ne instanceof Alias
+ && ne.getInputSlots().stream().anyMatch(slot ->
!childOutputExprIds.contains(slot.getExprId()));
}
- private static Expression getPullUpReplaceExpression(Slot slot,
CollectorContext context) {
- for (Map.Entry<Slot, Expression> entry :
context.pullUpExprReplaceMap.entrySet()) {
- if (entry.getKey().getExprId().equals(slot.getExprId())) {
- return entry.getValue();
+ private static Expression getPullUpReplaceExpression(Slot slot, PullUpInfo
info) {
+ Expression expression = info.pullUpExprReplaceMap.get(slot);
+ while (expression instanceof Slot) {
+ Expression next = info.pullUpExprReplaceMap.get((Slot) expression);
+ if (next == null) {
+ return expression;
}
+ expression = next;
}
- return null;
+ return expression;
}
/** Create a new Project above the TopN that restores pulled-up
expressions. */
- private static LogicalProject<Plan> addUpperProject(LogicalTopN topN,
PullUpInfo info,
- CollectorContext context) {
+ private static LogicalProject<Plan> addUpperProject(LogicalTopN topN,
PullUpInfo info) {
Map<ExprId, NamedExpression> pulledUpBySlotExprId = new HashMap<>();
Set<ExprId> currentOutputExprIds = topN.getOutputExprIdSet();
for (NamedExpression e : info.allPulledUpExprs) {
- pulledUpBySlotExprId.put(e.toSlot().getExprId(),
resolvePulledUpExpr(e, context, currentOutputExprIds));
+ pulledUpBySlotExprId.put(e.toSlot().getExprId(),
resolveAliasChildIfNeeded(e, info, currentOutputExprIds));
}
- // Use the current (possibly rewritten) TopN's output so that slots
- // whose expressions were deduplicated to an outer TopN reference
- // the correct post-simplification ExprIds instead of stale ones.
- List<Slot> currentOutput = topN.getOutput();
- Map<ExprId, Slot> currentOutputByExprId = new HashMap<>();
- for (Slot slot : currentOutput) {
- currentOutputByExprId.put(slot.getExprId(), slot);
- }
List<NamedExpression> upperOutput = new ArrayList<>();
Set<ExprId> upperOutputExprIds = new HashSet<>();
- Set<ExprId> passThroughOutputExprIds = new HashSet<>();
for (int i = 0; i < info.originalTopNOutput.size(); i++) {
Slot origSlot = info.originalTopNOutput.get(i);
NamedExpression pulledUpExpr =
pulledUpBySlotExprId.get(origSlot.getExprId());
if (pulledUpExpr != null) {
upperOutput.add(pulledUpExpr);
upperOutputExprIds.add(pulledUpExpr.getExprId());
+ } else if (currentOutputExprIds.contains(origSlot.getExprId())) {
+ upperOutput.add(origSlot);
+ upperOutputExprIds.add(origSlot.getExprId());
} else {
- Slot currentSlot =
currentOutputByExprId.get(origSlot.getExprId());
- if (currentSlot != null) {
- if
(!passThroughOutputExprIds.contains(currentSlot.getExprId())) {
- upperOutput.add(currentSlot);
- upperOutputExprIds.add(currentSlot.getExprId());
- }
- } else {
- NamedExpression passThroughExpr =
info.passThroughExprByDeduplicatedExpr.get(origSlot.getExprId());
- if (passThroughExpr != null) {
- List<Slot> passThroughSlots =
resolveInputSlots(passThroughExpr, context, currentOutputExprIds);
- addPassThroughSlots(upperOutput, upperOutputExprIds,
passThroughOutputExprIds,
- currentOutputByExprId, passThroughSlots);
- } else {
- // Slot was lost during simplifyProject — pass through
directly.
- // TopN is a pass-through node; the computation for
this slot
- // exists below the TopN even if the intermediate
project lost it.
- if (upperOutputExprIds.add(origSlot.getExprId())) {
- upperOutput.add(origSlot);
- }
- }
- }
+ Expression resolvedExpr = resolveExpression(origSlot, info,
currentOutputExprIds);
+ upperOutput.add(new Alias(origSlot.getExprId(), resolvedExpr,
origSlot.getName()));
+ upperOutputExprIds.add(origSlot.getExprId());
}
}
return new LogicalProject<>(ImmutableList.copyOf(upperOutput), topN);
}
- private static NamedExpression resolveNamedExpression(NamedExpression
expr, CollectorContext context,
+ private static NamedExpression resolveAliasChildIfNeeded(NamedExpression
expr, PullUpInfo info,
Set<ExprId> availableExprIds) {
if (!(expr instanceof Alias)) {
return expr;
}
- Expression resolvedChild = resolveExpression(expr.child(0), context,
availableExprIds);
+ Expression resolvedChild = resolveExpression(expr.child(0), info,
availableExprIds);
if (resolvedChild.equals(expr.child(0))) {
return expr;
}
return new Alias(expr.getExprId(), resolvedChild, expr.getName());
}
- private static NamedExpression resolvePulledUpExpr(NamedExpression expr,
CollectorContext context,
- Set<ExprId> availableExprIds) {
- if (!(expr instanceof Alias)) {
- return expr;
- }
- return new Alias(expr.getExprId(), resolveExpression(expr.child(0),
context, availableExprIds), expr.getName());
- }
-
- private static List<Slot> resolveInputSlots(NamedExpression expr,
CollectorContext context,
+ private static List<Slot> resolveInputSlots(Expression expr, PullUpInfo
info,
Set<ExprId> availableExprIds) {
- return ImmutableList.copyOf(resolveExpression(expr.child(0), context,
availableExprIds).getInputSlots());
+ return ImmutableList.copyOf(resolveExpression(expr, info,
availableExprIds).getInputSlots());
}
- private static List<Slot> resolveInputSlots(Expression expr,
CollectorContext context,
+ private static Expression resolveExpression(Expression expression,
PullUpInfo info,
Set<ExprId> availableExprIds) {
- return ImmutableList.copyOf(resolveExpression(expr, context,
availableExprIds).getInputSlots());
- }
-
- private static Expression resolveExpression(Expression expression,
CollectorContext context,
- Set<ExprId> availableExprIds) {
- Expression resolved = replaceUnavailableSlots(expression, context,
availableExprIds);
+ Expression resolved = replaceUnavailableSlots(expression, info,
availableExprIds);
while (!resolved.equals(expression)) {
expression = resolved;
- resolved = replaceUnavailableSlots(expression, context,
availableExprIds);
+ resolved = replaceUnavailableSlots(expression, info,
availableExprIds);
}
return resolved;
}
- private static Expression replaceUnavailableSlots(Expression expression,
CollectorContext context,
+ private static Expression replaceUnavailableSlots(Expression expression,
PullUpInfo info,
Set<ExprId> availableExprIds) {
Map<Slot, Expression> replaceMap = new LinkedHashMap<>();
- for (Map.Entry<Slot, Expression> entry :
context.pullUpExprReplaceMap.entrySet()) {
+ for (Map.Entry<Slot, Expression> entry :
info.pullUpExprReplaceMap.entrySet()) {
if (!availableExprIds.contains(entry.getKey().getExprId())) {
replaceMap.put(entry.getKey(), entry.getValue());
}
}
return ExpressionUtils.replace(expression, replaceMap);
}
-
- private static void addPassThroughSlots(
- List<NamedExpression> upperOutput,
- Set<ExprId> upperOutputExprIds,
- Set<ExprId> passThroughOutputExprIds,
- Map<ExprId, Slot> currentOutputByExprId,
- List<Slot> passThroughSlots) {
- for (Slot passThroughSlot : passThroughSlots) {
- Slot currentSlot =
currentOutputByExprId.get(passThroughSlot.getExprId());
- Preconditions.checkState(currentSlot != null,
- "Pass-through slot %s should be produced by rewritten
TopN", passThroughSlot);
- if (upperOutputExprIds.add(currentSlot.getExprId())) {
- upperOutput.add(currentSlot);
- }
- passThroughOutputExprIds.add(currentSlot.getExprId());
- }
- }
}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/PullUpProjectExprUnderTopNTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/PullUpProjectExprUnderTopNTest.java
index e0e82aba297..692f978e9f0 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/PullUpProjectExprUnderTopNTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/PullUpProjectExprUnderTopNTest.java
@@ -182,11 +182,11 @@ class PullUpProjectExprUnderTopNTest implements
MemoPatternMatchSupported {
}
@Test
- void testDeduplicatePullUpToOutermostTopN() {
+ void testOuterTopNPullsUnblockedExpressionRestoredByInnerTopN() {
// topn1(order by id) -> filter(x>1) -> topn2(order by id) ->
project(id, x, y) -> scan
- // With the stop-at-inner-TopN change, outer TopN no longer collects
expressions
- // from under the inner TopN. topn2 handles its own subtree: pulls up
both x and y.
- // topn1 has no pullable expressions between itself and topn2 (Filter
is not a Project).
+ // The bottom-up rule lets topn2 pull up x and y first. Then topn1 can
+ // continue pulling y through the Project restored above topn2. x is
+ // still blocked by the Filter between topn1 and topn2.
Slot id = scan1.getOutput().get(0);
Slot a = scan1.getOutput().get(1);
Slot b = scan1.getOutput().get(0);
@@ -204,32 +204,24 @@ class PullUpProjectExprUnderTopNTest implements
MemoPatternMatchSupported {
PlanChecker.from(MemoTestUtils.createConnectContext(), plan)
.applyCustom(new PullUpProjectExprUnderTopN())
- // Root: topn(3) -> filter -> project -> topn(10) -> project
-> scan
- // No addUpperProject for topn(3) — no pullable expressions
between it and topn(10)
.matchesFromRoot(
- logicalTopN(
- logicalFilter(
- logicalProject(
- logicalTopN(
- logicalProject(
-
logicalOlapScan()
- )
- )
- )
- )
- )
- )
- // Inner topn(10) has an upper project with x and y pulled up
- .matches(
logicalProject(
logicalTopN(
- logicalProject(
- logicalOlapScan()
+ logicalFilter(
+ logicalProject(
+ logicalTopN(
+ logicalProject(
+
logicalOlapScan()
+ )
+ )
+ )
)
)
).when(proj -> proj.getProjects().stream()
- .anyMatch(e -> "x".equals(e.getName())))
+ .anyMatch(e -> "y".equals(e.getName())))
)
+ // x remains restored above topn(10), because the Filter above
+ // topn(10) consumes x and blocks it from being pulled to
topn(3).
.matches(
logicalProject(
logicalTopN(
@@ -238,7 +230,7 @@ class PullUpProjectExprUnderTopNTest implements
MemoPatternMatchSupported {
)
)
).when(proj -> proj.getProjects().stream()
- .anyMatch(e -> "y".equals(e.getName())))
+ .anyMatch(e -> "x".equals(e.getName())))
)
.getPlan();
}
@@ -607,12 +599,11 @@ class PullUpProjectExprUnderTopNTest implements
MemoPatternMatchSupported {
}
@Test
- void testDeduplicatedPullUpDoesNotExposePassThroughInputSlots() {
+ void testOuterTopNPullUpDoesNotExposePassThroughInputSlots() {
// topn(3) -> filter(x>1) -> topn(10) -> project(x=a+1, y=b+1, id) ->
scan
- // With stop-at-inner-TopN, topn(10) handles its own subtree:
- // pulls up x and y, restores them above itself.
- // topn(3) has no pullable expressions → no addUpperProject.
- // Root is topn(3), not a Project.
+ // topn(10) pulls up x and y first. Then topn(3) can pull y farther up,
+ // while x remains blocked by the Filter. The root Project must still
+ // expose only the original TopN output, not y's internal input slot b.
LogicalOlapScan scan = new LogicalOlapScan(
PlanConstructor.getNextRelationId(), PlanConstructor.student,
ImmutableList.of("db"));
Slot id = scan.getOutput().get(0);
@@ -633,29 +624,34 @@ class PullUpProjectExprUnderTopNTest implements
MemoPatternMatchSupported {
.applyCustom(new PullUpProjectExprUnderTopN())
.getPlan();
- // Root is topn(3) — no addUpperProject (no pullable expressions)
- LogicalTopN<?> rootTopN = (LogicalTopN<?>) rewritten;
+ LogicalProject<?> rootProject = (LogicalProject<?>) rewritten;
+ Assertions.assertEquals(3, rootProject.getProjects().size());
+ Assertions.assertEquals(x.getExprId(),
rootProject.getProjects().get(0).getExprId());
+ Assertions.assertEquals(y.getExprId(),
rootProject.getProjects().get(1).getExprId());
+ Assertions.assertEquals(id.getExprId(),
rootProject.getProjects().get(2).getExprId());
+
+ LogicalTopN<?> rootTopN = (LogicalTopN<?>) rootProject.child(0);
LogicalFilter<?> midFilter = (LogicalFilter<?>) rootTopN.child(0);
LogicalProject<?> topN10UpperProject = (LogicalProject<?>)
midFilter.child(0);
Assertions.assertEquals(3, topN10UpperProject.getProjects().size());
Assertions.assertEquals(x.getExprId(),
topN10UpperProject.getProjects().get(0).getExprId());
- Assertions.assertEquals(y.getExprId(),
topN10UpperProject.getProjects().get(1).getExprId());
- Assertions.assertEquals(id.getExprId(),
topN10UpperProject.getProjects().get(2).getExprId());
+ Assertions.assertEquals(id.getExprId(),
topN10UpperProject.getProjects().get(1).getExprId());
+ Assertions.assertEquals(b.getExprId(),
topN10UpperProject.getProjects().get(2).getExprId());
LogicalTopN<?> topN10 = (LogicalTopN<?>) topN10UpperProject.child(0);
- // topN(10)'s output is [x, y, id]; base slot b is inside x and y
expressions
+ // b is needed only to restore y above topn(3); it must not leak from
+ // the root Project output.
Assertions.assertTrue(topN10.getOutput().stream()
.anyMatch(slot -> slot.getExprId().equals(b.getExprId())));
+ Assertions.assertFalse(rootProject.getProjects().stream()
+ .anyMatch(expr -> expr.getExprId().equals(b.getExprId())));
}
@Test
- void testDeduplicatedPullUpPassesThroughTransitiveInputSlots() {
+ void testNestedTopNPullUpPassesThroughTransitiveInputSlots() {
// topn(10) -> topn(20) -> project(y, id) -> topn(30) -> project(x,
id) -> scan
- // Each TopN handles its own subtree independently.
- // topn(30): pulls up x from project(x, id), restores above itself
- // topn(20): has project(y=x+1, id) between it and topn(30), y is
pullable,
- // restores y above itself
- // topn(10): no pullable expressions → no addUpperProject
+ // Each TopN handles its own child subtree after lower TopNs have been
+ // rewritten, so y can be pulled all the way above topn(10).
LogicalOlapScan scan = new LogicalOlapScan(
PlanConstructor.getNextRelationId(), PlanConstructor.student,
ImmutableList.of("db"));
Slot id = scan.getOutput().get(0);
@@ -672,60 +668,27 @@ class PullUpProjectExprUnderTopNTest implements
MemoPatternMatchSupported {
.topN(10, 0, ImmutableList.of(1))
.build();
- PlanChecker.from(MemoTestUtils.createConnectContext(), plan)
+ LogicalPlan rewritten = (LogicalPlan)
PlanChecker.from(MemoTestUtils.createConnectContext(), plan)
.applyCustom(new PullUpProjectExprUnderTopN())
- // Root: topn(10) → project(y, id) → topn(20) → project(x, id)
→ project(x) → topn(30) → project → scan
- .matchesFromRoot(
- logicalTopN(
- logicalProject(
- logicalTopN(
- logicalProject(
- logicalProject(
- logicalTopN(
-
logicalProject(
-
logicalOlapScan()
- )
- )
- )
- )
- )
- )
- )
- )
- // topn(20)'s upper project contains y
- .matches(
- logicalProject(
- logicalTopN(
- logicalProject(
- logicalProject(
- logicalTopN(
-
logicalProject(logicalOlapScan())
- )
- )
- )
- )
- ).when(proj -> proj.getProjects().stream()
- .anyMatch(e -> "y".equals(e.getName())))
- )
- // topn(30)'s upper project contains x
- .matches(
- logicalProject(
- logicalTopN(
- logicalProject(logicalOlapScan())
- )
- ).when(proj -> proj.getProjects().stream()
- .anyMatch(e -> "x".equals(e.getName())))
- );
+ .getPlan();
+
+ LogicalProject<?> rootProject = (LogicalProject<?>) rewritten;
+ Assertions.assertTrue(rootProject.getProjects().stream()
+ .anyMatch(e -> "y".equals(e.getName())));
+ LogicalTopN<?> topN10 = (LogicalTopN<?>) rootProject.child(0);
+ Assertions.assertTrue(topN10.getOutput().stream()
+ .anyMatch(slot -> slot.getExprId().equals(a.getExprId())));
+ Assertions.assertTrue(topN10.getOutput().stream()
+ .anyMatch(slot -> slot.getExprId().equals(b.getExprId())));
+ Assertions.assertFalse(topN10.getOutput().stream()
+ .anyMatch(slot -> slot.getExprId().equals(y.getExprId())));
}
@Test
- void testDeduplicatedPullUpKeepsInputSlotRestoredByLowerTopN() {
+ void testNestedTopNPullUpKeepsInputSlotRestoredByLowerTopN() {
// topn(10) -> topn(20) -> project(y, id, x) -> topn(30) -> project(x,
id) -> scan
- // Each TopN handles its own subtree independently.
- // topn(30): pulls up x from project(x, id), restores above itself
- // topn(20): has project(y, id, x) between it and topn(30), but x is a
Slot (no pullup),
- // y=x+1 is pullable, restores above itself
- // topn(10): no pullable expressions → no addUpperProject
+ // topn(20) orders by x, so x remains below topn(20). y is not blocked
+ // by topn(10), so the bottom-up rule can pull y above topn(10).
LogicalOlapScan scan = new LogicalOlapScan(
PlanConstructor.getNextRelationId(), PlanConstructor.student,
ImmutableList.of("db"));
Slot id = scan.getOutput().get(0);
@@ -744,15 +707,9 @@ class PullUpProjectExprUnderTopNTest implements
MemoPatternMatchSupported {
PlanChecker.from(MemoTestUtils.createConnectContext(), plan)
.applyCustom(new PullUpProjectExprUnderTopN())
- // Root: topn(10) — no addUpperProject (no pullable
expressions)
- .matchesFromRoot(logicalTopN().when(t -> t.getLimit() == 10))
- // topn(20)'s upper project contains y
- .matches(
- logicalProject(
- logicalTopN(logicalProject())
- ).when(proj -> proj.getProjects().stream()
- .anyMatch(e -> "y".equals(e.getName())))
- )
+ .matchesFromRoot(logicalProject(logicalTopN().when(t ->
t.getLimit() == 10))
+ .when(proj -> proj.getProjects().stream()
+ .anyMatch(e -> "y".equals(e.getName()))))
// topn(30)'s upper project contains x
.matches(
logicalProject(
@@ -762,6 +719,52 @@ class PullUpProjectExprUnderTopNTest implements
MemoPatternMatchSupported {
);
}
+ @Test
+ void testOuterTopNPullsExpressionRestoredByInnerTopNThroughRename() {
+ // TopN1(order by id)
+ // Project(id, b AS c)
+ // TopN2(order by id)
+ // Project(a + 1 AS b, id)
+ // Scan(id, a)
+ //
+ // The bottom-up rule first pulls b above TopN2. Then TopN1 sees the
+ // restored Project(a + 1 AS b) and can continue pulling the expression
+ // through the rename chain c -> b -> a + 1.
+ Slot id = scan1.getOutput().get(0);
+ Slot a = scan1.getOutput().get(1);
+ Alias b = new Alias(new Add(a, new IntegerLiteral((byte) 1)), "b");
+ Alias c = new Alias(b.toSlot(), "c");
+
+ LogicalProject<LogicalOlapScan> lowerProject = new
LogicalProject<>(ImmutableList.of(b, id), scan1);
+ LogicalTopN<LogicalProject<LogicalOlapScan>> innerTopN = new
LogicalTopN<>(
+ ImmutableList.of(new OrderKey(id, false, false)),
+ 20, 0, lowerProject);
+ LogicalProject<LogicalTopN<LogicalProject<LogicalOlapScan>>>
renameProject
+ = new LogicalProject<>(ImmutableList.of(id, c), innerTopN);
+
LogicalTopN<LogicalProject<LogicalTopN<LogicalProject<LogicalOlapScan>>>>
outerTopN = new LogicalTopN<>(
+ ImmutableList.of(new OrderKey(id, false, false)),
+ 10, 0, renameProject);
+
+ LogicalPlan rewritten = (LogicalPlan)
PlanChecker.from(MemoTestUtils.createConnectContext(), outerTopN)
+ .applyCustom(new PullUpProjectExprUnderTopN())
+ .getPlan();
+
+ LogicalProject<?> outerUpperProject = (LogicalProject<?>) rewritten;
+ Assertions.assertEquals(2, outerUpperProject.getProjects().size());
+ Assertions.assertEquals(id.getExprId(),
outerUpperProject.getProjects().get(0).getExprId());
+ Assertions.assertEquals(c.getExprId(),
outerUpperProject.getProjects().get(1).getExprId());
+
Assertions.assertTrue(outerUpperProject.getProjects().get(1).getInputSlots().stream()
+ .anyMatch(slot -> slot.getExprId().equals(a.getExprId())));
+
+ LogicalTopN<?> rewrittenOuterTopN = (LogicalTopN<?>)
outerUpperProject.child(0);
+ Assertions.assertTrue(rewrittenOuterTopN.getOutput().stream()
+ .anyMatch(slot -> slot.getExprId().equals(a.getExprId())));
+ Assertions.assertFalse(rewrittenOuterTopN.getOutput().stream()
+ .anyMatch(slot -> slot.getExprId().equals(b.getExprId())));
+ Assertions.assertFalse(rewrittenOuterTopN.getOutput().stream()
+ .anyMatch(slot -> slot.getExprId().equals(c.getExprId())));
+ }
+
@Test
void testNotPullUpNoneMovableFunction() {
// topn -> project(assert_true(a+1, "msg") as x) -> scan
@@ -791,6 +794,56 @@ class PullUpProjectExprUnderTopNTest implements
MemoPatternMatchSupported {
);
}
+ @Test
+ void testNoneMovableAliasBlocksDependentPullUp() {
+ // TopN
+ // Project(z = assert_true(x > 0), id)
+ // Project(x = a + 1, id)
+ // Scan
+ //
+ // z cannot be synthesized above TopN. Therefore z must block x, so the
+ // lower Project must keep x instead of pulling x up and making z
+ // unavailable below TopN.
+ Slot id = scan1.getOutput().get(0);
+ Slot a = scan1.getOutput().get(1);
+ Alias x = new Alias(new Add(a, new IntegerLiteral((byte) 1)), "x");
+ Alias z = new Alias(
+ new AssertTrue(
+ new GreaterThan(x.toSlot(), new IntegerLiteral((byte)
0)),
+ new StringLiteral("msg")
+ ),
+ "z"
+ );
+
+ LogicalProject<LogicalOlapScan> lowerProject = new
LogicalProject<>(ImmutableList.of(x, id), scan1);
+ LogicalProject<LogicalProject<LogicalOlapScan>> upperProject = new
LogicalProject<>(
+ ImmutableList.of(z, id), lowerProject);
+ LogicalTopN<LogicalProject<LogicalProject<LogicalOlapScan>>> plan =
new LogicalTopN<>(
+ ImmutableList.of(new OrderKey(id, false, false)), 3, 0,
upperProject);
+
+ LogicalPlan rewritten = (LogicalPlan)
PlanChecker.from(MemoTestUtils.createConnectContext(), plan)
+ .applyCustom(new PullUpProjectExprUnderTopN())
+ .matchesFromRoot(
+ logicalTopN(
+ logicalProject(
+ logicalProject(
+ logicalOlapScan()
+ )
+ )
+ )
+ )
+ .getPlan();
+
+ LogicalTopN<?> topN = (LogicalTopN<?>) rewritten;
+ LogicalProject<?> rewrittenUpperProject = (LogicalProject<?>)
topN.child(0);
+ Assertions.assertTrue(rewrittenUpperProject.getProjects().stream()
+ .anyMatch(expr -> expr.getExprId().equals(z.getExprId())));
+
+ LogicalProject<?> rewrittenLowerProject = (LogicalProject<?>)
rewrittenUpperProject.child(0);
+ Assertions.assertTrue(rewrittenLowerProject.getProjects().stream()
+ .anyMatch(expr -> expr.getExprId().equals(x.getExprId())));
+ }
+
@Test
void testBlockedBySort() {
// topn -> project(id, x, y) -> sort(by x) -> project(id, x, y) -> scan
@@ -1007,11 +1060,10 @@ class PullUpProjectExprUnderTopNTest implements
MemoPatternMatchSupported {
}
@Test
- void testDeduplicatePullUpEffect() {
- // Each TopN independently handles its own subtree — no cross-TopN
dedup.
- // topn(10) pulls up both x and y from the Project below it.
- // topn(3) has no pullable expressions (stops at topn(10) boundary,
- // Filter is not a Project). No addUpperProject for topn(3).
+ void testNestedTopNPullUpWithFilterBlocking() {
+ // Each TopN handles its own child subtree after lower TopNs have been
+ // rewritten. topn(10) restores x and y first; then topn(3) can pull y
+ // farther up, while x remains blocked by the Filter.
//
// Plan: topn(3) -> filter(x>1) -> topn(10) -> project(id, x, y) ->
scan
Slot id = scan1.getOutput().get(0);
@@ -1031,30 +1083,31 @@ class PullUpProjectExprUnderTopNTest implements
MemoPatternMatchSupported {
PlanChecker.from(MemoTestUtils.createConnectContext(), plan)
.applyCustom(new PullUpProjectExprUnderTopN())
- // Root shape: topn(3) -> filter -> project -> topn(10) ->
project -> scan
.matchesFromRoot(
- logicalTopN(
- logicalFilter(
- logicalProject(
- logicalTopN(
- logicalProject(
-
logicalOlapScan()
+ logicalProject(
+ logicalTopN(
+ logicalFilter(
+ logicalProject(
+ logicalTopN(
+ logicalProject(
+
logicalOlapScan()
+ )
)
)
)
)
- )
+ ).when(proj -> proj.getProjects().stream()
+ .anyMatch(e -> "y".equals(e.getName())))
)
- // Inner project (above topn(10)): must contain both x and y
+ // Inner project above topn(10) must still contain x because
the
+ // Filter consumes it.
.matches(
logicalProject(
logicalTopN(
logicalProject(logicalOlapScan())
)
).when(proj -> proj.getProjects().stream()
- .anyMatch(e -> "x".equals(e.getName()))
- && proj.getProjects().stream()
- .anyMatch(e -> "y".equals(e.getName())))
+ .anyMatch(e -> "x".equals(e.getName())))
);
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
