This is an automated email from the ASF dual-hosted git repository.
morrySnow 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 3347ea64fc7 [fix](dphyp) Fix DPHyp join reorder producing wrong
results for aliases on nullable side of outer join (#65682)
3347ea64fc7 is described below
commit 3347ea64fc7f114ebaf34cf94bacd544f57d8b46
Author: starocean999 <[email protected]>
AuthorDate: Tue Aug 4 10:47:54 2026 +0800
[fix](dphyp) Fix DPHyp join reorder producing wrong results for aliases on
nullable side of outer join (#65682)
Related PR: #61146
#### Problem Summary:
When enable_dphyp_optimizer=true, DPHyp join reorder can produce wrong
results for queries where the nullable side of an outer join contains
Alias/Project expressions with functions like COALESCE, IFNULL, or
CAST(COALESCE(...)).
#### Root Cause:
HyperGraph.Builder.addAlias() unconditionally adds all aliases to
aliasReplaceMap, including those defined on the nullable side of outer
joins. This causes their defining expressions to be "unwrapped" and
later reconstructed by PlanReceiver.proposeProject() ABOVE the outer
join via finalProjects. The expression then operates on null-extended
values, changing semantics — e.g., COALESCE(NULL, 0) = 0 instead of the
correct NULL for non-matching outer join rows.
#### Fix:
Added an isNullableSide context flag that propagates through
buildForDPhyper() and addAlias() during graph construction. When
processing an outer join:
LEFT OUTER JOIN → right child flagged as nullable
RIGHT OUTER JOIN → left child flagged as nullable
FULL OUTER JOIN → both children flagged as nullable
The flag propagates through nested projects and inner joins
Aliases on the nullable side are not added to aliasReplaceMap,
preserving the original Project boundary below the outer join so that
expressions execute before null-extension.
---
.../java/org/apache/doris/nereids/jobs/Job.java | 3 +-
.../doris/nereids/jobs/cascades/ApplyRuleJob.java | 3 +-
.../joinorder/hypergraphv2/GraphSimplifier.java | 2 +-
.../jobs/joinorder/hypergraphv2/HyperGraph.java | 305 ++++++++++++--
.../joinorder/hypergraphv2/SubgraphEnumerator.java | 14 +
.../hypergraphv2/receiver/AbstractReceiver.java | 53 +++
.../joinorder/hypergraphv2/receiver/Counter.java | 36 +-
.../hypergraphv2/receiver/PlanReceiver.java | 106 +++--
.../java/org/apache/doris/nereids/memo/Memo.java | 20 +-
.../GraphSimplifierFeasibleRootTest.java | 156 ++++++++
.../joinorder/hypergraphv2/NullableAliasTest.java | 437 +++++++++++++++++++++
.../jobs/joinorder/hypergraphv2/OtherJoinTest.java | 1 +
.../hypergraphv2/SubgraphEnumeratorTest.java | 8 +-
.../test_dphyp_outer_join_alias_nullable.out | 31 ++
.../test_dphyp_outer_join_alias_nullable.groovy | 239 +++++++++++
15 files changed, 1352 insertions(+), 62 deletions(-)
diff --git a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/Job.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/Job.java
index 41e5e1b8d7e..c1e7dbefc1e 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/Job.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/Job.java
@@ -107,7 +107,8 @@ public abstract class Job implements TracerSupplier {
CopyInResult result = context.getCascadesContext()
.getMemo()
- .copyIn(after, targetGroup, rule.isRewrite());
+ .copyIn(after, targetGroup, rule.isRewrite(),
+
context.getCascadesContext().getStatementContext().isDpHyp());
if (result.generateNewExpression ||
result.correspondingExpression.getOwnerGroup() != targetGroup) {
getEventTracer().log(TransformEvent.of(targetGroup.getLogicalExpression(),
before, afters,
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/cascades/ApplyRuleJob.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/cascades/ApplyRuleJob.java
index a12080796a3..6e6ec9bcaee 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/cascades/ApplyRuleJob.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/cascades/ApplyRuleJob.java
@@ -86,7 +86,8 @@ public class ApplyRuleJob extends Job {
}
CopyInResult result = context.getCascadesContext()
.getMemo()
- .copyIn(newPlan, groupExpression.getOwnerGroup(),
false);
+ .copyIn(newPlan, groupExpression.getOwnerGroup(),
false,
+
context.getCascadesContext().getStatementContext().isDpHyp());
if (!result.generateNewExpression) {
continue;
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/GraphSimplifier.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/GraphSimplifier.java
index 8b3ec9fe2b3..a39d488dc58 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/GraphSimplifier.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/GraphSimplifier.java
@@ -245,7 +245,7 @@ public class GraphSimplifier {
int upperBound = 1;
// Try to probe the largest number of steps to satisfy the limit
- Counter counter = new Counter(limit);
+ Counter counter = new Counter(graph, limit);
SubgraphEnumerator enumerator = new SubgraphEnumerator(counter, graph);
while (true) {
boolean hitUpperLimit = false;
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/HyperGraph.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/HyperGraph.java
index a1287bca073..7ce60557a1b 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/HyperGraph.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/HyperGraph.java
@@ -28,9 +28,11 @@ import org.apache.doris.nereids.memo.Group;
import org.apache.doris.nereids.memo.GroupExpression;
import org.apache.doris.nereids.rules.expression.ExpressionRewriteContext;
import org.apache.doris.nereids.trees.expressions.Alias;
+import org.apache.doris.nereids.trees.expressions.ExprId;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.NamedExpression;
import org.apache.doris.nereids.trees.expressions.Slot;
+import
org.apache.doris.nereids.trees.expressions.functions.NoneMovableFunction;
import org.apache.doris.nereids.trees.plans.DistributeType;
import org.apache.doris.nereids.trees.plans.JoinType;
import org.apache.doris.nereids.trees.plans.Plan;
@@ -46,6 +48,7 @@ import com.google.common.collect.Sets;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
+import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
@@ -62,27 +65,34 @@ public class HyperGraph {
private final List<Edge> joinEdges;
private final List<AbstractNode> nodes;
private final List<NamedExpression> finalProjects;
- private final Map<Long, List<NamedExpression>> nodeToLiteralAlias;
+ // Each value is a flattened list of projected aliases for a given bitmap.
+ // Cross-layer references (e.g., z = x + 1 referencing x = COALESCE(v, 0))
+ // are resolved at flush time so that only a single layer is stored.
+ private final Map<Long, List<NamedExpression>> nodeToProjectedAliases;
private final CascadesContext ctx;
HyperGraph(List<NamedExpression> finalProjects, List<Edge> joinEdges,
List<AbstractNode> nodes,
- Map<Long, List<NamedExpression>> nodeToLiteralAlias,
CascadesContext ctx) {
+ Map<Long, List<NamedExpression>> nodeToProjectedAliases,
CascadesContext ctx) {
this.finalProjects = ImmutableList.copyOf(finalProjects);
this.joinEdges = ImmutableList.copyOf(joinEdges);
this.nodes = ImmutableList.copyOf(nodes);
- this.nodeToLiteralAlias = nodeToLiteralAlias;
+ this.nodeToProjectedAliases = nodeToProjectedAliases;
this.ctx = ctx;
}
/**
- * the project with alias and slot
+ * the project with alias and slot, without volatile or non-movable
expressions.
+ * Projects containing volatile (e.g. uuid()) or non-movable (e.g.
assert_true())
+ * expressions are treated as join-cluster boundaries (like aggregate
nodes).
*/
public static boolean isValidProject(Plan plan) {
if (!(plan instanceof LogicalProject)) {
return false;
}
return ((LogicalProject<? extends Plan>) plan).getProjects().stream()
- .allMatch(e -> e instanceof Slot || e instanceof Alias);
+ .allMatch(e -> (e instanceof Slot || e instanceof Alias)
+ && !e.containsVolatileExpression()
+ && !e.containsType(NoneMovableFunction.class));
}
/**
@@ -125,23 +135,23 @@ public class HyperGraph {
return joinEdges.get(index);
}
- public boolean hasLiteralAlias() {
- return !nodeToLiteralAlias.isEmpty();
+ public boolean hasProjectedAliases() {
+ return !nodeToProjectedAliases.isEmpty();
}
/**
* find all literal alias should be projected after left join right
*/
- public List<NamedExpression> getLiteralAlias(long left, long right) {
+ public List<NamedExpression> getProjectedAliases(long left, long right) {
ImmutableList.Builder<NamedExpression> aliasList =
ImmutableList.builder();
if (left == right) {
- List<NamedExpression> namedExpressions =
nodeToLiteralAlias.get(left);
+ List<NamedExpression> namedExpressions =
nodeToProjectedAliases.get(left);
if (namedExpressions != null) {
aliasList.addAll(namedExpressions);
}
} else {
long nodes = LongBitmap.newBitmapUnion(left, right);
- for (Map.Entry<Long, List<NamedExpression>> entry :
nodeToLiteralAlias.entrySet()) {
+ for (Map.Entry<Long, List<NamedExpression>> entry :
nodeToProjectedAliases.entrySet()) {
if (!LongBitmap.isSubset(entry.getKey(), left) &&
!LongBitmap.isSubset(entry.getKey(), right)
&& LongBitmap.isSubset(entry.getKey(), nodes)) {
aliasList.addAll(entry.getValue());
@@ -151,6 +161,156 @@ public class HyperGraph {
return aliasList.build();
}
+ /**
+ * Returns true if the cross-bitmap alias layers that would be emitted at
+ * this join step have a dependency that cannot be resolved. Specifically,
+ * if a later layer references an alias from an earlier layer whose bitmap
+ * key is also split across both children (not yet emitted), then emitting
+ * both in one flat Project causes CheckAfterRewrite to reject the plan.
+ * Rejecting the join order forces DPHyp to find an alternative where the
+ * producer layer's source is fully contained in one child.
+ */
+ public boolean hasUnresolvableAliasDependency(long left, long right) {
+ List<Map.Entry<Long, List<NamedExpression>>> entries =
getProjectedAliasEntries(
+ left, right);
+ if (entries.size() < 2) {
+ return false;
+ }
+ Set<ExprId> producedExprIds = new HashSet<>();
+ for (Map.Entry<Long, List<NamedExpression>> entry : entries) {
+ long key = entry.getKey();
+ // If this layer's key spans both children, the layer is being
+ // emitted NOW (not pre-existing in a child).
+ boolean keySpansBoth = !LongBitmap.isSubset(key, left)
+ && !LongBitmap.isSubset(key, right);
+ if (keySpansBoth) {
+ for (NamedExpression alias : entry.getValue()) {
+ for (Slot inputSlot : alias.getInputSlots()) {
+ if (producedExprIds.contains(inputSlot.getExprId())) {
+ return true;
+ }
+ }
+ }
+ }
+ for (NamedExpression alias : entry.getValue()) {
+ producedExprIds.add(alias.getExprId());
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Returns the projected alias entries in insertion order that should be
+ * emitted when joining {@code left} and {@code right}. Each entry is a
+ * separate layer keyed by its source bitmap. Unlike
+ * {@link #getProjectedAliases} which flattens all layers, this preserves
+ * layer boundaries so that cross-bitmap dependent aliases (e.g., y = x +
C.v
+ * on key {A,B,C} where x is on key {A,B}) can be emitted as nested
+ * Project nodes in dependency order.
+ */
+ public List<Map.Entry<Long, List<NamedExpression>>>
getProjectedAliasEntries(
+ long left, long right) {
+ List<Map.Entry<Long, List<NamedExpression>>> result = new
ArrayList<>();
+ if (left == right) {
+ List<NamedExpression> layer = nodeToProjectedAliases.get(left);
+ if (layer != null) {
+ result.add(Map.entry(left, layer));
+ }
+ } else {
+ long nodes = LongBitmap.newBitmapUnion(left, right);
+ for (Map.Entry<Long, List<NamedExpression>> entry :
nodeToProjectedAliases.entrySet()) {
+ long key = entry.getKey();
+ if (!LongBitmap.isSubset(key, left) &&
!LongBitmap.isSubset(key, right)
+ && LongBitmap.isSubset(key, nodes)) {
+ result.add(entry);
+ }
+ }
+ }
+ return result;
+ }
+
+ /**
+ * Returns the union of input slots of all projected aliases whose bitmap
+ * is a superset of the given nodes. Used by PlanReceiver to preserve
+ * columns in intermediate join outputs that are needed by pending aliases
+ * (both those emitted now and those deferred to a later join).
+ * Without this, calculateRequiredSlots prunes base columns like A.v/B.v
+ * that a pending alias s=A.v+B.v depends on, and CheckAfterRewrite fails.
+ * Uses isOverlap (not isSubset) because DPHyp can build mixed subplans
+ * like {A,C} that only partially overlap with an alias's source {A,B};
+ * inputs from the overlapping part (A.v) must still be preserved.
+ */
+ public Set<Slot> getAllAliasInputSlotsForNodes(long nodes) {
+ Set<Slot> result = new HashSet<>();
+ for (Map.Entry<Long, List<NamedExpression>> entry :
nodeToProjectedAliases.entrySet()) {
+ if (LongBitmap.isOverlap(nodes, entry.getKey())) {
+ for (NamedExpression alias : entry.getValue()) {
+ result.addAll(alias.getInputSlots());
+ }
+ }
+ }
+ return result;
+ }
+
+ /**
+ * Returns the input slots of aliases whose source bitmap is NOT fully
+ * contained in {@code nodes}. Such aliases reference tables outside
+ * {@code nodes}, so they are deferred to a later join step and their raw
+ * input columns (from the tables within {@code nodes}) must be preserved
+ * through the current step. Unlike the split-dependent
+ * {@code left/right} subset checks, this condition depends only on the
+ * union {@code nodes}, so it is join-order-independent — every
+ * decomposition of the same bitmap keeps the same slots.
+ */
+ public Set<Slot> getDeferredAliasInputSlotsForNodes(long nodes) {
+ Set<Slot> result = new HashSet<>();
+ for (Map.Entry<Long, List<NamedExpression>> entry :
nodeToProjectedAliases.entrySet()) {
+ long key = entry.getKey();
+ if (!LongBitmap.isSubset(key, nodes) &&
LongBitmap.isOverlap(nodes, key)) {
+ for (NamedExpression alias : entry.getValue()) {
+ result.addAll(alias.getInputSlots());
+ }
+ }
+ }
+ return result;
+ }
+
+ /**
+ * Returns true if the edge can be safely used as a join predicate between
+ * left and right. An edge is unsafe when it references a projected alias
+ * whose source bitmap spans both children — the alias layer is emitted by
+ * proposeProject (after proposeJoin), so the join predicate cannot see it.
+ * Such edges must wait for a later join step where the alias source is
+ * fully contained in one child.
+ *
+ * <p>This guards against missed-edge fallback consuming a projected alias
+ * across a split source endpoint:
+ * <pre>
+ * Edge {A,B}--{C} with predicate s=C.t, where s has source {A,B}.
+ * When left={A,C}, right={B}: s spans both children, so unsafe.
+ * When left={A,B}, right={C}: {A,B} subset of left, so safe.
+ * </pre>
+ */
+ public boolean isEdgeSafeForJoin(Edge edge, long left, long right) {
+ if (!hasProjectedAliases()) {
+ return true;
+ }
+ List<NamedExpression> splitAliases = getProjectedAliases(left, right);
+ if (splitAliases.isEmpty()) {
+ return true;
+ }
+ Set<ExprId> splitAliasExprIds = new HashSet<>();
+ for (NamedExpression alias : splitAliases) {
+ splitAliasExprIds.add(alias.getExprId());
+ }
+ for (Slot slot : edge.getInputSlots()) {
+ if (splitAliasExprIds.contains(slot.getExprId())) {
+ return false;
+ }
+ }
+ return true;
+ }
+
// find edges to connect left and right node
public BitSet findConnectionEdges(long left, long right) {
BitSet operatorEdgesMap = new BitSet();
@@ -279,7 +439,12 @@ public class HyperGraph {
// addAlias method add slots from both simple node and joined nodes,
depending on the alias's input slots
private final HashMap<Slot, Long> slotToHyperNodeMap = new
LinkedHashMap<>();
- private final Map<Long, List<NamedExpression>> nodeToLiteralAlias =
new LinkedHashMap<>();
+ private final Map<Long, List<NamedExpression>> nodeToProjectedAliases
= new LinkedHashMap<>();
+
+ // Accumulates aliases for the current Project layer. Reset for each
new Project
+ // in buildForDPhyper so that each source Project forms a separate
layer,
+ // preserving materialization boundaries for volatile expressions.
+ private List<NamedExpression> currentProjectedAliasLayer = null;
private Set<Slot> finalOutputs;
@@ -314,7 +479,7 @@ public class HyperGraph {
}
public HyperGraph build() {
- return new HyperGraph(finalProjects, joinEdges, nodes,
nodeToLiteralAlias, ctx);
+ return new HyperGraph(finalProjects, joinEdges, nodes,
nodeToProjectedAliases, ctx);
}
public void updateNode(int idx, Group group) {
@@ -330,23 +495,75 @@ public class HyperGraph {
* latest join edges index
*/
private Pair<BitSet, Long> buildForDPhyper(GroupExpression
groupExpression) {
+ return buildForDPhyper(groupExpression, false);
+ }
+
+ private Pair<BitSet, Long> buildForDPhyper(GroupExpression
groupExpression, boolean isNullableSide) {
// process Project
if (isValidProject(groupExpression.getPlan())) {
LogicalProject<?> project = (LogicalProject<?>)
groupExpression.getPlan();
- Pair<BitSet, Long> res =
buildForDPhyper(groupExpression.child(0).getLogicalExpressions().get(0));
+ Pair<BitSet, Long> res = buildForDPhyper(
+
groupExpression.child(0).getLogicalExpressions().get(0), isNullableSide);
+ // Start a new layer for this Project. Each source Project
becomes one
+ // LogicalProject layer, preserving materialization boundaries
for
+ // volatile expressions (e.g., uuid()) that
PlanUtils.canMergeWithProjections
+ // would otherwise reject.
+ List<NamedExpression> savedLayer =
this.currentProjectedAliasLayer;
+ this.currentProjectedAliasLayer = new ArrayList<>();
for (NamedExpression expr : project.getProjects()) {
if (expr instanceof Alias) {
- this.addAlias((Alias) expr, res.second);
+ this.addAlias((Alias) expr, res.second,
isNullableSide);
}
}
+ // Flush the layer if non-empty. If aliases for this key
already
+ // exist, resolve cross-layer references (e.g., z = x + 1 where
+ // x was defined by an earlier Project on the same subtree) and
+ // merge into the existing single layer. Cross-layer resolution
+ // is safe because volatile/non-movable expressions are already
+ // excluded by isValidProject.
+ if (!this.currentProjectedAliasLayer.isEmpty()) {
+ long key = res.second;
+ List<NamedExpression> existing =
nodeToProjectedAliases.get(key);
+ if (existing != null) {
+ Map<Slot, Expression> replaceMap = new
LinkedHashMap<>();
+ for (NamedExpression a : existing) {
+ if (a instanceof Alias) {
+ replaceMap.put(a.toSlot(), ((Alias)
a).child());
+ }
+ }
+ for (NamedExpression expr :
currentProjectedAliasLayer) {
+ existing.add((NamedExpression)
ExpressionUtils.replace(expr, replaceMap));
+ }
+ } else {
+ nodeToProjectedAliases.put(key,
+ new ArrayList<>(currentProjectedAliasLayer));
+ }
+ }
+ this.currentProjectedAliasLayer = savedLayer;
return res;
}
// process Join
if (isValidJoin(groupExpression.getPlan())) {
LogicalJoin<?, ?> join = (LogicalJoin<?, ?>)
groupExpression.getPlan();
- Pair<BitSet, Long> left =
buildForDPhyper(groupExpression.child(0).getLogicalExpressions().get(0));
- Pair<BitSet, Long> right =
buildForDPhyper(groupExpression.child(1).getLogicalExpressions().get(0));
+ JoinType joinType = join.getJoinType();
+ // Determine if children are on the nullable side:
+ // - For LEFT OUTER JOIN, the right child is nullable
+ // - For RIGHT OUTER JOIN, the left child is nullable
+ // - For FULL OUTER JOIN, both children are nullable
+ // - If we're already inside a nullable context, propagate down
+ boolean leftNullable = isNullableSide
+ || joinType.isRightOuterJoin()
+ || joinType.isAsofRightOuterJoin()
+ || joinType.isFullOuterJoin();
+ boolean rightNullable = isNullableSide
+ || joinType.isLeftOuterJoin()
+ || joinType.isAsofLeftOuterJoin()
+ || joinType.isFullOuterJoin();
+ Pair<BitSet, Long> left = buildForDPhyper(
+
groupExpression.child(0).getLogicalExpressions().get(0), leftNullable);
+ Pair<BitSet, Long> right = buildForDPhyper(
+
groupExpression.child(1).getLogicalExpressions().get(0), rightNullable);
return Pair.of(this.addJoin(join, left, right),
LongBitmap.or(left.second, right.second));
}
@@ -366,7 +583,7 @@ public class HyperGraph {
*
* @param alias The alias Expression in project Operator
*/
- public boolean addAlias(Alias alias, long subTreeNodes) {
+ public boolean addAlias(Alias alias, long subTreeNodes, boolean
isNullableSide) {
Slot aliasSlot = alias.toSlot();
if (slotToHyperNodeMap.containsKey(aliasSlot)) {
return true;
@@ -385,15 +602,57 @@ public class HyperGraph {
if (bitmap == 0) {
bitmap = subTreeNodes;
addToReplaceMap = false;
- List<NamedExpression> aliasList =
nodeToLiteralAlias.get(bitmap);
- if (aliasList == null) {
- aliasList = new ArrayList<>(1);
- nodeToLiteralAlias.put(bitmap, aliasList);
+ // Constant aliases go into the current Project layer (set up
by
+ // buildForDPhyper) and will be flushed to
nodeToProjectedAliases
+ // keyed by the layer's subtree bitmap after the Project is
processed.
+ if (currentProjectedAliasLayer != null) {
+ currentProjectedAliasLayer.add(alias);
}
- aliasList.add(alias);
}
Preconditions.checkArgument(bitmap > 0, "slot must belong to some
table");
- slotToHyperNodeMap.put(aliasSlot, bitmap);
+ boolean mustStayInCurrentAliasLayer = isNullableSide &&
!(alias.child() instanceof Slot);
+ // Map nullable-side alias slots to subTreeNodes instead of the
minimal
+ // referenced bitmap. Otherwise a later join predicate like s=C.k
sees s as
+ // {B} (its input slot) and creates a {B}--{C} edge, allowing
DPHyp to join
+ // B and C before A — but s can only be emitted when {A,B} is
complete.
+ // Using subTreeNodes (e.g. {A,B}) forces the predicate edge to
require the
+ // full source subtree, matching the emission key in
nodeToProjectedAliases.
+ // Note: always use subTreeNodes for nullable-side aliases. A
Slot-forwarding
+ // alias (e.g. s=A.k) that shares a Project with expression
aliases cannot
+ // safely use the minimal bitmap — its layer only emits at {A,B},
so exposing
+ // it as {A} would let DPHyp form predicate edges before the alias
exists.
+ slotToHyperNodeMap.put(aliasSlot, mustStayInCurrentAliasLayer ?
subTreeNodes : bitmap);
+ // Do not add aliases on the nullable side of outer joins to
aliasReplaceMap.
+ // Aliases on the nullable side (e.g., COALESCE(v, 0) AS dv on the
right side of
+ // a LEFT JOIN) must execute BEFORE the outer join's
null-extension.
+ // If added to aliasReplaceMap, they would be unwrapped and
reconstructed above
+ // the outer join by PlanReceiver.proposeProject(), changing
execution order
+ // and producing wrong results.
+ // Instead, add them to the current Project layer. buildForDPhyper
flushes each
+ // layer to nodeToProjectedAliases keyed by subTreeNodes so the
alias is only
+ // projected when the full original subtree is available,
preserving the
+ // execution boundary and volatile materialization order.
+ // No replaceNameExpression here: nullable-side aliases are stored
as
+ // independent layers that reference child-output slots, so
expansion is
+ // unnecessary and could trigger expression-limit failures for
large chains
+ // (the same reason PlanUtils.tryMergeProjections keeps layers).
+ if (addToReplaceMap && mustStayInCurrentAliasLayer) {
+ if (currentProjectedAliasLayer != null) {
+ // Resolve forwarding aliases (e.g., x → A.v) through
+ // aliasReplaceMap before storing the layer body. A
+ // join-separated chain may first resolve a lower Slot
+ // alias into aliasReplaceMap and then build a later
+ // expression alias that references it. Without this
+ // substitution the stored layer references a slot (x)
+ // that no child outputs, and CheckAfterRewrite fails.
+ // replaceNameExpression is safe here — it only replaces
+ // Alias slots whose source is already fully built in
+ // the same nullable subtree.
+ Alias resolved = (Alias)
ExpressionUtils.replaceNameExpression(alias, aliasReplaceMap);
+ currentProjectedAliasLayer.add(resolved);
+ }
+ return true;
+ }
alias = (Alias) ExpressionUtils.replaceNameExpression(alias,
aliasReplaceMap);
if (addToReplaceMap) {
aliasReplaceMap.put(aliasSlot, alias.child());
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/SubgraphEnumerator.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/SubgraphEnumerator.java
index 93cd07f8b44..cfbfc0ddb1b 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/SubgraphEnumerator.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/SubgraphEnumerator.java
@@ -145,6 +145,20 @@ public class SubgraphEnumerator {
return false;
}
}
+ // A successful enumeration must actually build the full join (the root
+ // bitmap). DPHyp can walk every CSG/CMP without any receiver returning
+ // FAIL while never inserting the root — e.g. when the only full split
+ // is rejected by the alias-dependency rule (a producer alias whose
+ // source spans both children, as in a producer-after-consumer alias
+ // chain: x on {A,B} consumed by y on {A,B,C} at split {A,C}--{B}).
+ // Accepting such a rootless probe makes GraphSimplifier stop
+ // simplifying and makes the final PlanReceiver pass return a null best
+ // plan for the root. Requiring the root bitmap forces the simplifier
+ // to keep applying steps, or the caller to fall back to the original
+ // group, instead of returning a null plan.
+ if (!receiver.contain(hyperGraph.getNodesMap())) {
+ return false;
+ }
if (enableTrace) {
LOG.info(traceBuilder.toString());
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/receiver/AbstractReceiver.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/receiver/AbstractReceiver.java
index b1def9945f2..9d71adcd3f1 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/receiver/AbstractReceiver.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/receiver/AbstractReceiver.java
@@ -18,10 +18,13 @@
package org.apache.doris.nereids.jobs.joinorder.hypergraphv2.receiver;
import org.apache.doris.common.Pair;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.HyperGraph;
import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.bitmap.LongBitmap;
import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.edge.Edge;
import org.apache.doris.nereids.memo.Group;
+import java.util.BitSet;
+import java.util.HashMap;
import java.util.List;
/**
@@ -39,6 +42,56 @@ public abstract class AbstractReceiver {
public abstract Group getBestPlan(long bitSet);
+ /**
+ * Find all edges that are missed by the current connection edges but whose
+ * reference nodes are a subset of the joined nodes. These missed edges
+ * must be added to the emitted join (they become additional join
+ * conditions). If any missed edge is enforced-order, or references a
+ * projected alias whose source spans both children, the csg-cmp pair is
+ * rejected (returns false).
+ *
+ * <p>This logic is shared by {@link PlanReceiver} (which actually emits
+ * the plan) and {@link Counter} (which counts csg-cmp pairs during graph
+ * simplification). Keeping them consistent is essential: GraphSimplifier
+ * relies on Counter to decide how many simplification steps are needed to
+ * satisfy {@code dphyperLimit}, and an over-count would over-constrain the
+ * graph and change the enumeration output.
+ */
+ protected boolean processMissedEdges(HyperGraph hyperGraph, HashMap<Long,
BitSet> usdEdges,
+ long left, long right, List<Edge> edges, List<Edge> missingEdges) {
+ // find all used edges
+ BitSet usedEdgesBitmap = new BitSet();
+ usedEdgesBitmap.or(usdEdges.get(left));
+ usedEdgesBitmap.or(usdEdges.get(right));
+ edges.forEach(edge -> usedEdgesBitmap.set(edge.getIndex()));
+
+ // find all referenced nodes
+ long allReferenceNodes = LongBitmap.or(left, right);
+
+ // find the edge which is not in usedEdgesBitmap and its referenced
nodes is subset of allReferenceNodes
+ for (Edge edge : hyperGraph.getJoinEdges()) {
+ if (LongBitmap.isSubset(edge.getReferenceNodes(),
allReferenceNodes)
+ && !usedEdgesBitmap.get(edge.getIndex())) {
+ if (edge.isEnforcedOrder()) {
+ return false;
+ } else {
+ // Reject missed edges that reference a projected alias
whose
+ // source bitmap spans both children. The alias layer is
emitted
+ // by proposeProject (after proposeJoin), so the join
predicate
+ // would reference a slot that does not exist in either
child's
+ // output. Wait for a later join step where the alias
source is
+ // fully contained in one child.
+ if (!hyperGraph.isEdgeSafeForJoin(edge, left, right)) {
+ return false;
+ }
+ // add the missed edge to edges
+ missingEdges.add(edge);
+ }
+ }
+ }
+ return true;
+ }
+
/**
* checkConflictRule for CD-C
*/
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/receiver/Counter.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/receiver/Counter.java
index eb94f6bb095..2a19820eb4c 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/receiver/Counter.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/receiver/Counter.java
@@ -17,12 +17,15 @@
package org.apache.doris.nereids.jobs.joinorder.hypergraphv2.receiver;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.HyperGraph;
import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.bitmap.LongBitmap;
import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.edge.Edge;
import org.apache.doris.nereids.memo.Group;
import com.google.common.base.Preconditions;
+import java.util.ArrayList;
+import java.util.BitSet;
import java.util.HashMap;
import java.util.List;
@@ -32,14 +35,18 @@ import java.util.List;
public class Counter extends AbstractReceiver {
// limit define the max number of csg-cmp pair in this Receiver
private final int limit;
+ private final HyperGraph hyperGraph;
private final HashMap<Long, Integer> counter = new HashMap<>();
+ private final HashMap<Long, BitSet> usdEdges = new HashMap<>();
private int emitCount = 0;
- public Counter() {
+ public Counter(HyperGraph hyperGraph) {
+ this.hyperGraph = hyperGraph;
this.limit = Integer.MAX_VALUE;
}
- public Counter(int limit) {
+ public Counter(HyperGraph hyperGraph, int limit) {
+ this.hyperGraph = hyperGraph;
this.limit = limit;
}
@@ -54,13 +61,34 @@ public class Counter extends AbstractReceiver {
public EmitState emitCsgCmp(long left, long right, List<Edge> edges) {
Preconditions.checkArgument(counter.containsKey(left));
Preconditions.checkArgument(counter.containsKey(right));
- if (!checkConflictRule(left, right, edges)) {
+ // Mirror PlanReceiver.emitCsgCmp: find missed edges first, reject the
+ // pair when an enforced-order / unsafe alias edge is found, then count
+ // the pair before the conflict-rule and alias-dependency checks (same
+ // ordering as PlanReceiver, so GraphSimplifier's limit decision
matches
+ // what PlanReceiver actually emits).
+ List<Edge> missingEdges = new ArrayList<>();
+ if (!processMissedEdges(hyperGraph, usdEdges, left, right, edges,
missingEdges)) {
return EmitState.CONTINUE;
}
emitCount += 1;
if (emitCount > limit) {
return EmitState.FAIL;
}
+ edges.addAll(missingEdges);
+ if (!checkConflictRule(left, right, edges)) {
+ return EmitState.CONTINUE;
+ }
+ // Reject cross-bitmap alias layer dependencies, same as PlanReceiver.
+ if (hyperGraph.hasUnresolvableAliasDependency(left, right)) {
+ return EmitState.CONTINUE;
+ }
+ // track used edges for the joined bitmap, same as PlanReceiver
+ BitSet usedEdgesBitmap = new BitSet();
+ usedEdgesBitmap.or(usdEdges.get(left));
+ usedEdgesBitmap.or(usdEdges.get(right));
+ edges.forEach(edge -> usedEdgesBitmap.set(edge.getIndex()));
+ usdEdges.put(LongBitmap.newBitmapUnion(left, right), usedEdgesBitmap);
+
long bitmap = LongBitmap.newBitmapUnion(left, right);
if (!counter.containsKey(bitmap)) {
counter.put(bitmap, counter.get(left) * counter.get(right));
@@ -72,6 +100,7 @@ public class Counter extends AbstractReceiver {
public void addGroup(long bitmap, Group group) {
counter.put(bitmap, 1);
+ usdEdges.put(bitmap, new BitSet());
}
public boolean contain(long bitmap) {
@@ -80,6 +109,7 @@ public class Counter extends AbstractReceiver {
public void reset() {
this.counter.clear();
+ this.usdEdges.clear();
emitCount = 0;
}
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/receiver/PlanReceiver.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/receiver/PlanReceiver.java
index 40f0f426948..a0d967aa454 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/receiver/PlanReceiver.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/receiver/PlanReceiver.java
@@ -160,6 +160,18 @@ public class PlanReceiver extends AbstractReceiver {
LogicalPlan logicalJoin = proposeJoin(joinType, leftPlan, rightPlan,
hashConjuncts,
otherConjuncts);
+ // Reject join orders where cross-bitmap alias layers have an
+ // unresolvable dependency — a later layer references an alias from
+ // an earlier layer whose source spans both children. The producer
+ // layer must be fully contained in one child before the consumer
+ // can be emitted, otherwise CheckAfterRewrite rejects the plan.
+ if (hyperGraph.hasUnresolvableAliasDependency(left, right)) {
+ if (fullKeyEmitted) {
+ missingEdgeFail = true;
+ }
+ return EmitState.CONTINUE;
+ }
+
LogicalPlan logicalPlan = proposeProject(logicalJoin, edges, left,
right);
// Second, we copy all physical plan to Group and generate properties
and calculate cost
@@ -211,29 +223,10 @@ public class PlanReceiver extends AbstractReceiver {
// The root cause is hyper predicate should be encoded as one or more
hyper edges in different scenarios.
// But we are not able to do so in all cases (complex expression and outer
joins).
// So we use processMissedEdges to find all valid edges when join 0, 1, 2
as fallback plan.
+ // The logic is shared with Counter (see
AbstractReceiver.processMissedEdges) so that
+ // GraphSimplifier's pair count matches what PlanReceiver actually emits.
private boolean processMissedEdges(long left, long right, List<Edge>
edges, List<Edge> missingEdges) {
- // find all used edges
- BitSet usedEdgesBitmap = new BitSet();
- usedEdgesBitmap.or(usdEdges.get(left));
- usedEdgesBitmap.or(usdEdges.get(right));
- edges.forEach(edge -> usedEdgesBitmap.set(edge.getIndex()));
-
- // find all referenced nodes
- long allReferenceNodes = LongBitmap.or(left, right);
-
- // find the edge which is not in usedEdgesBitmap and its referenced
nodes is subset of allReferenceNodes
- for (Edge edge : hyperGraph.getJoinEdges()) {
- if (LongBitmap.isSubset(edge.getReferenceNodes(),
allReferenceNodes)
- && !usedEdgesBitmap.get(edge.getIndex())) {
- if (edge.isEnforcedOrder()) {
- return false;
- } else {
- // add the missed edge to edges
- missingEdges.add(edge);
- }
- }
- }
- return true;
+ return super.processMissedEdges(hyperGraph, usdEdges, left, right,
edges, missingEdges);
}
private void proposeAllDistributedPlans(GroupExpression groupExpression) {
@@ -291,29 +284,86 @@ public class PlanReceiver extends AbstractReceiver {
private LogicalPlan proposeProject(LogicalPlan join, List<Edge> edges,
long left, long right) {
Set<Slot> outputSet = join.getOutputSet();
- // calculate required columns by all parents
- Set<Slot> requireSlots = calculateRequiredSlots(left, right, edges);
+ // calculate required columns by all parents (final outputs + unused
edges)
+ Set<Slot> parentRequireSlots = calculateRequiredSlots(left, right,
edges);
+ // Pending projected aliases may reference input slots (e.g., A.v, B.v
for
+ // s=A.v+B.v) that are not in finalRequiredSlots or unused edges.
Preserve
+ // them so the join output still contains the base columns needed to
evaluate
+ // the alias expressions, both for aliases emitted at this stage and
those
+ // deferred to a later join whose bitmap is a superset.
+ Set<Slot> aliasInputSlots = hyperGraph.getAllAliasInputSlotsForNodes(
+ LongBitmap.newBitmapUnion(left, right));
+ Set<Slot> requireSlots = new HashSet<>(parentRequireSlots);
+ requireSlots.addAll(aliasInputSlots);
List<NamedExpression> allProjects = new ArrayList<>(outputSet.size());
for (Slot slot : outputSet) {
if (requireSlots.contains(slot)) {
allProjects.add(slot);
}
}
- if (hyperGraph.hasLiteralAlias()) {
- allProjects.addAll(hyperGraph.getLiteralAlias(left, right));
- }
if (allProjects.isEmpty()) {
allProjects.add(new Alias(new ExprId(-1), new
TinyIntLiteral((byte) 1)));
}
- // propose logical project
+ // propose logical project for the slot pass-through
LogicalPlan logicalPlan;
if (outputSet.equals(new HashSet<>(allProjects))) {
logicalPlan = join;
} else {
logicalPlan = new LogicalProject<>(allProjects, join);
}
+
+ // Emit projected aliases as a single LogicalProject node.
+ // Cross-layer references (e.g., z = x + 1 referencing x = COALESCE(v,
0))
+ // were already resolved at graph-build time, so only one Project is
needed.
+ // Carry forward child slots still required by parents (e.g., join
keys)
+ // or by deferred alias layers (e.g., B.w for a later y=B.w+1).
+ // Use the full requireSlots so that deferred-layer inputs survive
+ // through intermediate layers.
+ if (hyperGraph.hasProjectedAliases()) {
+ List<NamedExpression> aliases =
hyperGraph.getProjectedAliases(left, right);
+ if (!aliases.isEmpty()) {
+ Set<ExprId> aliasExprIds = new HashSet<>();
+ for (NamedExpression a : aliases) {
+ aliasExprIds.add(a.getExprId());
+ }
+ List<NamedExpression> mergedLayer = new ArrayList<>(aliases);
+ // Decide which raw base columns can be dropped from this alias
+ // layer's carry-forward. A base column is an alias raw input
+ // that is consumed once every alias reading it has been
+ // materialized within this union. It must be KEPT when:
+ // - it is still required by the final output, or
+ // - a deferred alias (source NOT inside this union) reads it
+ // (that alias is materialized at a later join step and
+ // reads the raw base column from the join output), or
+ // - some join edge references it (e.g. a pushed-down hash
+ // expression such as `col + 1 = key` reads the raw base
+ // column from the join output).
+ // Every exclusion above is computed from the graph + union
+ // only, never from the left/right split, so all decompositions
+ // of the same bitmap produce the same plan output set (memo
+ // output-set consistency). A split-dependent drop would let
+ // one ordering drop a column that another ordering still
needs,
+ // producing "Input slot(s) not in child's output" failures.
+ Set<Slot> exclusivelyEmittedSlots = new
HashSet<>(aliasInputSlots);
+ exclusivelyEmittedSlots.removeAll(finalRequiredSlots);
+
exclusivelyEmittedSlots.removeAll(hyperGraph.getDeferredAliasInputSlotsForNodes(
+ LongBitmap.newBitmapUnion(left, right)));
+ for (Edge edge : hyperGraph.getJoinEdges()) {
+ exclusivelyEmittedSlots.removeAll(edge.getInputSlots());
+ }
+ for (Slot childSlot : logicalPlan.getOutputSet()) {
+ if (requireSlots.contains(childSlot)
+ && !aliasExprIds.contains(childSlot.getExprId())
+ && !exclusivelyEmittedSlots.contains(childSlot)) {
+ mergedLayer.add(childSlot);
+ }
+ }
+ logicalPlan = new LogicalProject<>(mergedLayer, logicalPlan);
+ }
+ }
+
if (LongBitmap.newBitmapUnion(left, right) == allNodeBitmap
&& !logicalPlan.getOutputSet().equals(new
HashSet<>(finalProjects))) {
logicalPlan = new LogicalProject<>(finalProjects, logicalPlan);
diff --git a/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java
index 6573f34febc..0d6862a3f4a 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java
@@ -292,11 +292,29 @@ public class Memo {
* is the corresponding group expression of the plan
*/
public CopyInResult copyIn(Plan plan, @Nullable Group target, boolean
rewrite) {
+ return copyIn(plan, target, rewrite, false);
+ }
+
+ /**
+ * Add plan to Memo.
+ *
+ * @param plan {@link Plan} or {@link Expression} to be added
+ * @param target target group to add node. null to generate new Group
+ * @param rewrite whether to rewrite the node to the target group
+ * @param isInDpHyper whether this copy happens during DPHyp enumeration.
During DPHyp
+ * the output of a group is only guaranteed to be
consistent by its
+ * output slot set (nullability may legitimately differ
across join
+ * orders of outer joins), so the relaxed set-only
comparison is used.
+ * @return CopyInResult, in which the generateNewExpression is true if a
newly generated
+ * groupExpression added into memo, and the
correspondingExpression
+ * is the corresponding group expression of the plan
+ */
+ public CopyInResult copyIn(Plan plan, @Nullable Group target, boolean
rewrite, boolean isInDpHyper) {
CopyInResult result;
if (rewrite) {
result = doRewrite(plan, target);
} else {
- result = doCopyIn(plan, target, null, false);
+ result = doCopyIn(plan, target, null, isInDpHyper);
}
maybeAddStateId(result);
return result;
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/GraphSimplifierFeasibleRootTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/GraphSimplifierFeasibleRootTest.java
new file mode 100644
index 00000000000..ae230dc3fc2
--- /dev/null
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/GraphSimplifierFeasibleRootTest.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.doris.nereids.jobs.joinorder.hypergraphv2;
+
+import org.apache.doris.nereids.CascadesContext;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.bitmap.LongBitmap;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.edge.Edge;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.AbstractNode;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.DPhyperNode;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.receiver.Counter;
+import org.apache.doris.nereids.memo.Group;
+import org.apache.doris.nereids.sqltest.SqlTestBase;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalOlapScan;
+import org.apache.doris.nereids.util.PlanChecker;
+
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Regression tests for the DPHyp feasible-root guarantee.
+ *
+ * <p>A successful enumeration must have actually built the full join (the root
+ * bitmap). Without this, DPHyp can walk every CSG/CMP without any receiver
+ * returning FAIL while never inserting the root — e.g. when the only full
split
+ * is rejected by the alias-dependency rule (a producer alias whose source
spans
+ * both children, as in a producer-after-consumer alias chain). The
+ * GraphSimplifier would then accept a rootless probe and the final
+ * PlanReceiver pass would return a null best plan for the root.
+ */
+public class GraphSimplifierFeasibleRootTest extends SqlTestBase {
+
+ // Alias chain on the nullable side of an outer join:
+ // x = T2.score + T3.score key {T2, T3} (A, B)
+ // dv = x + T1.score key {T2, T3, T1} (A, B, C)
+ // outer: T4 left join (...) (preserved table, nullable side)
+ // Inner join cluster {T2, T3, T1} has edges {T2}--{T3} and {T2}--{T1}.
+ private static final String ALIAS_CHAIN_SQL =
+ "select T4.id, Sub.dv "
+ + "from T4 left join ("
+ + " select Sub2.id, Sub2.x + T1.score as dv "
+ + " from ("
+ + " select T2.id, T2.score + T3.score as x "
+ + " from T2 inner join T3 on T2.id = T3.id"
+ + " ) Sub2 inner join T1 on Sub2.id = T1.id"
+ + ") Sub on T4.id = Sub.id";
+
+ /**
+ * Builds the DPHyp hypergraph for the join cluster of the analyzed plan.
+ */
+ private static HyperGraph buildHyperGraph(CascadesContext c1) {
+ Group joinGroup = c1.getMemo().getRoot();
+ while
(!HyperGraph.isValidJoin(joinGroup.getLogicalExpression().getPlan())
+ && joinGroup.getLogicalExpression().arity() > 0) {
+ joinGroup = joinGroup.getLogicalExpression().child(0);
+ }
+ HyperGraph.Builder builder = HyperGraph.builderForDPhyper(joinGroup,
c1);
+ for (AbstractNode node : builder.getNodes()) {
+ DPhyperNode dPhyperNode = (DPhyperNode) node;
+ builder.updateNode(node.getIndex(), dPhyperNode.getGroup());
+ }
+ return builder.build();
+ }
+
+ /**
+ * Forces the producer-after-consumer order and checks that the rootless
+ * enumeration is reported as failure.
+ *
+ * <p>The GraphSimplifier cost-orders A-C before A-B;
concretizeSimplificationStep
+ * then extends the A-B edge ({T2}--{T3}) to {A,C}--{B} ({T2,T1}--{T3}).
+ * After that {A,B} is no longer a connected subgraph, so the only full
+ * split of {A,B,C} is {A,C}--{B} — which is rejected by
+ * hasUnresolvableAliasDependency (dv references x whose source {A,B} spans
+ * both children). The root bitmap is never inserted, and a rootless
+ * enumeration must be reported as failure instead of silently succeeding.
+ */
+ @Test
+ void testProducerAfterConsumerOrderRejectsRootlessEnumeration() {
+ CascadesContext c1 = createCascadesContext(ALIAS_CHAIN_SQL,
connectContext);
+ PlanChecker.from(c1).analyze().rewrite();
+ HyperGraph hyperGraph = buildHyperGraph(c1);
+
+ // Baseline: without simplification the full plan is reachable.
+ Counter counter = new Counter(hyperGraph);
+ SubgraphEnumerator enumerator = new SubgraphEnumerator(counter,
hyperGraph);
+ Assertions.assertTrue(enumerator.enumerate());
+ Assertions.assertTrue(counter.contain(hyperGraph.getNodesMap()));
+
+ // Identify the producer edge A-B ({T2}--{T3}) and force the order.
+ int a = nodeIndexOfTable(hyperGraph, "T2");
+ int b = nodeIndexOfTable(hyperGraph, "T3");
+ int c = nodeIndexOfTable(hyperGraph, "T1");
+ long aMap = LongBitmap.newBitmap(a);
+ long bMap = LongBitmap.newBitmap(b);
+ long cMap = LongBitmap.newBitmap(c);
+ Edge abEdge = null;
+ for (Edge edge : hyperGraph.getJoinEdges()) {
+ long ref = edge.getLeftExtendedNodes() |
edge.getRightExtendedNodes();
+ if (ref == (aMap | bMap)) {
+ abEdge = edge;
+ break;
+ }
+ }
+ Assertions.assertNotNull(abEdge, "producer edge A-B should exist");
+ hyperGraph.modifyEdge(abEdge.getIndex(), aMap | cMap, bMap);
+
+ // The fix: rootless enumeration must be reported as failure so the
+ // caller falls back instead of returning a null best plan.
+ Counter counter2 = new Counter(hyperGraph);
+ SubgraphEnumerator enumerator2 = new SubgraphEnumerator(counter2,
hyperGraph);
+ Assertions.assertFalse(enumerator2.enumerate());
+ Assertions.assertFalse(counter2.contain(hyperGraph.getNodesMap()));
+ }
+
+ /**
+ * With a low dphyperLimit the GraphSimplifier is forced to simplify. If it
+ * produces a producer-after-consumer order whose only full split is
+ * rejected, enumeration must not return a null plan — the caller falls
back
+ * to the original group instead.
+ */
+ @Test
+ void testAliasChainDpHypWithLowLimitProducesValidPlan() {
+ connectContext.getSessionVariable().dphyperLimit = 1;
+ CascadesContext c1 = createCascadesContext(ALIAS_CHAIN_SQL,
connectContext);
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ private static int nodeIndexOfTable(HyperGraph hyperGraph, String table) {
+ for (AbstractNode node : hyperGraph.getNodes()) {
+ DPhyperNode dn = (DPhyperNode) node;
+ Plan p = dn.getGroup().getLogicalExpression().getPlan();
+ if (p instanceof LogicalOlapScan) {
+ if (table.equals(((LogicalOlapScan) p).getTable().getName())) {
+ return node.getIndex();
+ }
+ }
+ }
+ throw new IllegalStateException("table not found: " + table);
+ }
+}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/NullableAliasTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/NullableAliasTest.java
new file mode 100644
index 00000000000..20a698fdcf4
--- /dev/null
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/NullableAliasTest.java
@@ -0,0 +1,437 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.jobs.joinorder.hypergraphv2;
+
+import org.apache.doris.nereids.CascadesContext;
+import org.apache.doris.nereids.sqltest.SqlTestBase;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.util.PlanChecker;
+
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+public class NullableAliasTest extends SqlTestBase {
+ @Test
+ void testCoalesceOnNullableSide() {
+ // COALESCE on the nullable (right) side of a LEFT JOIN.
+ // DPHyp must keep the COALESCE below the outer join.
+ CascadesContext c1 = createCascadesContext(
+ "select T1.id, sum(T2.score + ifnull(T3.age, 0)) "
+ + "from T1 left join T2 on T1.id = T2.id "
+ + "left join (select id, coalesce(score, 0) as age
from T3) T3 "
+ + "on T2.id = T3.id group by T1.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testIfnullOnNullableSide() {
+ // IFNULL on the nullable side of LEFT JOIN.
+ CascadesContext c1 = createCascadesContext(
+ "select T1.id, sum(ifnull(T2.score, 0)) "
+ + "from T1 left join T2 on T1.id = T2.id "
+ + "left join (select id, ifnull(score, 0) as score
from T3) T3 "
+ + "on T2.id = T3.id group by T1.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testChainedAliasOnNullableSide() {
+ // Chained aliases on nullable side: y = x + 1, x = coalesce(v, 0).
+ // Verifies layered storage preserves the x->y dependency.
+ CascadesContext c1 = createCascadesContext(
+ "select T1.id, sum(T2.score + T3.dv) "
+ + "from T1 left join T2 on T1.id = T2.id "
+ + "left join ("
+ + " select id, (x + 1) as dv from ("
+ + " select id, coalesce(score, 0) as x from T3"
+ + " ) sub1"
+ + ") T3 on T2.id = T3.id group by T1.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testJoinPredicateOnNullableAlias() {
+ // Nullable alias used in a higher join predicate.
+ // Verifies slotToHyperNodeMap maps the alias to its full subtree.
+ CascadesContext c1 = createCascadesContext(
+ "select T1.id, sum(T2.score + T3.s) "
+ + "from T1 inner join T2 on T1.id = T2.id "
+ + "left join ("
+ + " select T1.id, coalesce(T2.score, 0) as s "
+ + " from T1 inner join T2 on T1.id = T2.id"
+ + ") T3 on T1.id = T3.id and T3.s = T2.score "
+ + "group by T1.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testNestedOuterJoinAlias() {
+ // COALESCE on nullable side where the Project's subtree itself
+ // contains a LEFT JOIN (inner nullable join).
+ CascadesContext c1 = createCascadesContext(
+ "select T1.id, sum(coalesce(Sub.dv, 0)) "
+ + "from T1 inner join T2 on T1.id = T2.id "
+ + "left join ("
+ + " select L.id, coalesce(R.score, 0) as dv "
+ + " from T1 L left join T2 R on L.id = R.id"
+ + ") Sub on T2.id = Sub.id group by T1.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testPassThroughJoinKeyInLayer() {
+ // Aliased Project on a single table that also outputs the join key.
+ // Verifies that the layer carries forward D.k so parent join C.k =
D.k works.
+ CascadesContext c1 = createCascadesContext(
+ "select T1.id, sum(T2.score + T3.dv) "
+ + "from T1 left join T2 on T1.id = T2.id "
+ + "left join (select id, coalesce(score, 0) as dv from
T3) T3 "
+ + "on T2.id = T3.id group by T1.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testMixedSubplanPreservesAliasInputs() {
+ // Alias s = InnerT2.score + InnerT3.score on the nullable side,
+ // source bitmap {InnerT2, InnerT3, InnerT1} (mapped to subTreeNodes).
+ // The inner join cluster has three relations: InnerT2, InnerT3,
InnerT1.
+ //
+ // DPHyp can build {InnerT2, InnerT1} first (via InnerT2.id =
InnerT1.id),
+ // a mixed subplan that partially overlaps the alias source {InnerT2,
InnerT3}
+ // at InnerT2. Without getAllAliasInputSlotsForNodes,
calculateRequiredSlots
+ // sees only the join key InnerT2.id as required for the next edge
+ // {InnerT2}--{InnerT3}, and prunes InnerT2.score. The alias s cannot
be
+ // rebuilt later because its input column is gone.
+ //
+ // With the fix: getAllAliasInputSlotsForNodes uses isOverlap (not
isSubset)
+ // to detect that the alias source overlaps the current node set at
InnerT2,
+ // and preserves InnerT2.score + InnerT3.score in requireSlots.
+ //
+ // s is consumed in the outer SELECT so it is not pruned before DPHyp.
+ CascadesContext c1 = createCascadesContext(
+ "select OuterT1.id, Sub.s "
+ + "from T1 OuterT1 left join ("
+ + " select InnerT2.id, (InnerT2.score +
InnerT3.score) as s "
+ + " from T2 InnerT2"
+ + " inner join T3 InnerT3 on InnerT2.id = InnerT3.id"
+ + " inner join T1 InnerT1 on InnerT2.id = InnerT1.id"
+ + ") Sub on OuterT1.id = Sub.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testDropAliasRawInputsAfterMaterialization() {
+ // Alias dv = length(score) on nullable side over {T1,T2}.
+ // After dv materializes, raw T2.score should not leak into ancestor
+ // join outputs — verifies parentRequireSlots excludes alias inputs
+ // from the mergedLayer carry-forward.
+ CascadesContext c1 = createCascadesContext(
+ "select T1.id, sum(T2.score + coalesce(Sub.dv, 0)) "
+ + "from T1 inner join T2 on T1.id = T2.id "
+ + "left join ("
+ + " select T1.id, char_length(cast(T2.score as
string)) as dv "
+ + " from T1 inner join T2 on T1.id = T2.id"
+ + ") Sub on T1.id = Sub.id "
+ + "group by T1.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testSlotForwardingAliasOnMinimalBitmap() {
+ // Slot-forwarding alias s = T1.id over {T1,T2} on nullable side.
+ // Since all nullable-side aliases now map to subTreeNodes for safety,
+ // s = T3.id forms a {T1,T2}--{T3} edge. Verifies DPHyp still
+ // produces a valid plan.
+ CascadesContext c1 = createCascadesContext(
+ "select T2.id, sum(T2.score + T3.score) "
+ + "from T2 inner join T3 on T2.id = T3.id "
+ + "left join ("
+ + " select T1.id as s "
+ + " from T1 inner join T2 on T1.id = T2.id"
+ + ") Sub on Sub.s = T3.id "
+ + "group by T2.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testVolatileProjectAsClusterBoundary() {
+ // uuid() on the nullable side: the Project is treated as a cluster
+ // boundary (isValidProject returns false because uuid() is volatile),
+ // falling through to addDPHyperNode like an aggregate node.
+ CascadesContext c1 = createCascadesContext(
+ "select T1.id, sum(T2.score + T3.s) "
+ + "from T1 left join T2 on T1.id = T2.id "
+ + "left join ("
+ + " select T1.id, (coalesce(T2.score, 0) +
uuid_numeric()) as s "
+ + " from T1 inner join T2 on T1.id = T2.id"
+ + ") T3 on T1.id = T3.id "
+ + "group by T1.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testVolatileAliasOnNullableSide() {
+ // uuid() alias on nullable side of LEFT JOIN.
+ // The Project containing uuid() is a cluster boundary, so DPHyp
+ // treats it as a leaf node and does not reorder across it.
+ CascadesContext c1 = createCascadesContext(
+ "select T1.id, sum(ifnull(T2.score, 0) + T3.dv) "
+ + "from T1 left join T2 on T1.id = T2.id "
+ + "left join ("
+ + " select T1.id, uuid_numeric() as dv "
+ + " from T1 inner join T2 on T1.id = T2.id"
+ + ") T3 on T1.id = T3.id "
+ + "group by T1.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testSplitSourceAliasMissedEdge() {
+ // Problem: a projected alias on the nullable side whose source bitmap
+ // spans two base tables is consumed by a join predicate via the
+ // missed-edge fallback while its source is split across both children.
+ //
+ // Plan structure (bottom-up):
+ // S2 = InnerT2 INNER JOIN InnerT3 ON InnerT2.id = InnerT3.id
+ // Project(InnerT2.id, coalesce(InnerT3.score, 0) AS s)
+ // -> alias s has source {InnerT2, InnerT3}
+ // Sub = S2 INNER JOIN C ON S2.id = C.id AND S2.s = C.score
+ // -> edges: {InnerT2}--{C}, {InnerT2,InnerT3}--{C}
+ // Outer: PreservedT1 LEFT JOIN Sub ON PreservedT1.id = Sub.id
+ //
+ // Inner join cluster: {InnerT2, InnerT3, C}
+ // Edge {InnerT2}--{InnerT3}: InnerT2.id = InnerT3.id
+ // Edge {InnerT2}--{C}: S2.id = C.id
+ // Edge {InnerT2,InnerT3}--{C}: S2.s = C.score
+ //
+ // DPHyp can reorder the inner join cluster:
+ // 1. Build {InnerT2, C} via edge {InnerT2}--{C}
+ // 2. Combine with {InnerT3} via edge {InnerT2}--{InnerT3}
+ // At step 2, processMissedEdges finds the unused edge
+ // {InnerT2,InnerT3}--{C} (predicate S2.s = C.score).
+ // All reference nodes {InnerT2,InnerT3,C} are in the union,
+ // so it would normally be added as a connection edge.
+ //
+ // Without the fix: proposeJoin would evaluate S2.s = C.score
+ // while neither child outputs S2.s — the alias layer is only
+ // emitted later by proposeProject (after the full {InnerT2,InnerT3,C}
+ // is assembled). This violates CheckAfterRewrite.
+ //
+ // With the fix (isEdgeSafeForJoin): getProjectedAliasLayers detects
+ // that the alias layer for {InnerT2,InnerT3} spans both children
+ // ({InnerT2,C} and {InnerT3}), and rejects the unsafe missed edge.
+ CascadesContext c1 = createCascadesContext(
+ "select PreservedT1.id, Sub.s "
+ + "from T1 PreservedT1 left join ("
+ + " select S2.id, S2.s "
+ + " from ("
+ + " select InnerT2.id, coalesce(InnerT3.score, 0)
as s "
+ + " from T2 InnerT2 inner join T3 InnerT3 on
InnerT2.id = InnerT3.id"
+ + " ) S2 "
+ + " inner join T1 C on S2.id = C.id and S2.s =
C.score"
+ + ") Sub on PreservedT1.id = Sub.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testJoinSeparatedChainForwardingAlias() {
+ // A join-separated chain on the nullable side:
+ // Lower: Project(T2.id, T2.score AS x) on leaf T2
+ // x = T2.score, child is Slot → enters aliasReplaceMap
(x→T2.score)
+ // No layer emitted — x is a simple forwarding alias.
+ // Upper: Project(InnerA.id, InnerA.x + 1 AS y) on (T2 ⋈ T3)
+ // y = x + 1, child is expression →
mustStayInCurrentAliasLayer
+ // Without the fix: y stored as "y = x + 1" without resolving
x.
+ // Child join outputs T2.id, T2.score, T3.id, T3.score, but
NOT x.
+ // PlanReceiver asks for x → CheckAfterRewrite fails.
+ // With the fix: replaceNameExpression resolves x → T2.score
+ // before storing, so y = T2.score + 1 references a real
column.
+ CascadesContext c1 = createCascadesContext(
+ "select OuterT1.id, Sub.y "
+ + "from T1 OuterT1 left join ("
+ + " select InnerA.id, (InnerA.x + 1) as y "
+ + " from ("
+ + " select T2.id, T2.score as x "
+ + " from T2"
+ + " ) InnerA inner join T3 on InnerA.id = T3.id"
+ + ") Sub on OuterT1.id = Sub.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testDropAliasRawInputsSingleTableLeaf() {
+ // Alias dv = char_length(cast(score as string)) on nullable side over
{T2}.
+ // After dv materializes, raw T2.score should not leak into ancestor
+ // join outputs — verifies getAllAliasInputSlotsForNodes skips aliases
+ // whose source bitmap is already fully contained in a completed child.
+ // Without the fix, T2.score survives through the join step as an
+ // aliasInputSlot, widening the join output and distorting cost.
+ CascadesContext c1 = createCascadesContext(
+ "select T1.id, Sub.dv "
+ + "from T1 left join ("
+ + " select T2.id, char_length(cast(T2.score as
string)) as dv "
+ + " from T2"
+ + ") Sub on T1.id = Sub.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testAliasConsumesJoinKey() {
+ // Alias dv = T2.id + 1 on nullable side over {T2}. Unlike the
+ // drop-raw-input test, here the alias consumes the join key itself.
+ // T2.id is therefore both an emitted-alias input AND required by
+ // the parent outer-join edge. Without the exclusively-emitted
+ // check the join key would be dropped from the rebuilt child,
+ // and the later LeftOuterJoin(T1.id = Sub.id) would reference
+ // a slot that no longer exists → CheckAfterRewrite failure.
+ // The fix preserves T2.id because it is still in parentRequireSlots.
+ CascadesContext c1 = createCascadesContext(
+ "select T1.id, Sub.dv "
+ + "from T1 left join ("
+ + " select T2.id, T2.id + 1 as dv "
+ + " from T2"
+ + ") Sub on T1.id = Sub.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testCrossBitmapAliasLayers() {
+ // Two alias layers with different bitmap keys on the nullable side.
+ // x = A.score + B.score key {A,B} (inner Project)
+ // dv = x#X + C.score key {A,B,C} (outer Project)
+ // DPHyp can build {A,C}+{B}, at which point both alias layers would
+ // be emitted. The later layer dv references x#X from the earlier
+ // layer x, but x's source spans both children — x#X does not exist
+ // in the join child. Without the fix, CheckAfterRewrite rejects
+ // the plan. With the fix (hasUnresolvableAliasDependency), the
+ // {A,C}+{B} join order is rejected and DPHyp falls back to a valid
+ // order like {A,B}+{C}.
+ CascadesContext c1 = createCascadesContext(
+ "select T1.id, Sub.dv "
+ + "from T1 left join ("
+ + " select Sub2.id, Sub2.x, Sub2.x + C.score as dv "
+ + " from ("
+ + " select A.id, A.score + B.score as x "
+ + " from T2 A inner join T3 B on A.id = B.id"
+ + " ) Sub2 inner join T1 C on Sub2.id = C.id"
+ + ") Sub on T1.id = Sub.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ }
+
+ @Test
+ void testNullableAliasOnRightJoinSide() {
+ // RIGHT OUTER JOIN: the left side is nullable. A complex alias
+ // dv = T2.score + T3.score is defined inside an inner-join cluster
+ // on the left (nullable) side. DPHyp must keep the alias below the
+ // right-join null-extension — the same pattern as the LEFT JOIN
+ // tests but with the nullable flag on the left child instead.
+ // The plan tree is printed so that a developer inspecting test
+ // output can verify the outer join is present and the nullable
+ // slots carry the correct nullability flags.
+ CascadesContext c1 = createCascadesContext(
+ "select Sub.dv "
+ + "from ("
+ + " select T2.id, T2.score + T3.score as dv "
+ + " from T2 inner join T3 on T2.id = T3.id"
+ + ") Sub right join T1 on Sub.id = T1.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ String tree = plan.treeString();
+ Assertions.assertTrue(tree.contains("RIGHT") || tree.contains("LEFT"),
+ "Plan should contain an outer join (RIGHT or LEFT-converted)."
+ + "\nPlan tree:\n" + tree);
+ }
+
+ @Test
+ void testNullableAliasOnFullJoinBothSides() {
+ // FULL OUTER JOIN: both sides are nullable. Each side carries a
+ // complex alias on the nullable side:
+ // Left (Sub1): dv1 = T2.score + T3.score (inner-join cluster)
+ // Right (Sub2): dv2 = char_length(cast(T1.score as string))
+ // Both aliases must execute below the full-outer null-extension.
+ // The plan tree is printed so that a developer inspecting test
+ // output can verify both aliases are below the null-extension.
+ CascadesContext c1 = createCascadesContext(
+ "select Sub1.dv1, Sub2.dv2 "
+ + "from ("
+ + " select T2.id, T2.score + T3.score as dv1 "
+ + " from T2 inner join T3 on T2.id = T3.id"
+ + ") Sub1 full outer join ("
+ + " select T1.id, char_length(cast(T1.score as
string)) as dv2 "
+ + " from T1"
+ + ") Sub2 on Sub1.id = Sub2.id",
+ connectContext
+ );
+ Plan plan =
PlanChecker.from(c1).analyze().rewrite().dpHypOptimize().getBestPlanTree();
+ Assertions.assertNotNull(plan);
+ String tree = plan.treeString();
+ Assertions.assertTrue(tree.contains("FULL"),
+ "Plan should contain a FULL OUTER JOIN."
+ + "\nPlan tree:\n" + tree);
+ }
+}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/OtherJoinTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/OtherJoinTest.java
index 9229b8b76f7..2b727b76bd1 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/OtherJoinTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/OtherJoinTest.java
@@ -53,6 +53,7 @@ public class OtherJoinTest extends TPCHTestBase {
CascadesContext cascadesContext =
MemoTestUtils.createCascadesContext(connectContext.getStatementContext(),
plan);
hyperGraphBuilder.initStats("tpch", cascadesContext);
+ connectContext.getSessionVariable().dphyperLimit = 100000;
try {
Plan optimizedPlan = PlanChecker.from(cascadesContext)
.dpHypOptimize()
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/SubgraphEnumeratorTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/SubgraphEnumeratorTest.java
index a59379aa3b9..4593ec88750 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/SubgraphEnumeratorTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/SubgraphEnumeratorTest.java
@@ -45,7 +45,7 @@ public class SubgraphEnumeratorTest {
.addEdge(JoinType.INNER_JOIN, 0, 3)
.addEdge(JoinType.INNER_JOIN, 0, 4)
.build();
- Counter counter = new Counter();
+ Counter counter = new Counter(hyperGraph);
SubgraphEnumerator subgraphEnumerator = new
SubgraphEnumerator(counter, hyperGraph);
subgraphEnumerator.enumerate();
long fullSet = LongBitmap.newBitmapBetween(0, 5);
@@ -69,7 +69,7 @@ public class SubgraphEnumeratorTest {
.addEdge(JoinType.INNER_JOIN, 2, 3)
.build();
long fullSet = LongBitmap.newBitmapBetween(0, 4);
- Counter counter = new Counter();
+ Counter counter = new Counter(hyperGraph);
SubgraphEnumerator subgraphEnumerator = new
SubgraphEnumerator(counter, hyperGraph);
subgraphEnumerator.enumerate();
HashMap<Long, Integer> cache = new HashMap<>();
@@ -83,7 +83,7 @@ public class SubgraphEnumeratorTest {
long fullSet = LongBitmap.newBitmapBetween(0, tableNum);
for (int i = 0; i < 10; i++) {
HyperGraph hyperGraph = new
HyperGraphBuilder().randomBuildWith(tableNum, edgeNum);
- Counter counter = new Counter();
+ Counter counter = new Counter(hyperGraph);
SubgraphEnumerator subgraphEnumerator = new
SubgraphEnumerator(counter, hyperGraph);
subgraphEnumerator.enumerate();
HashMap<Long, Integer> cache = new HashMap<>();
@@ -97,7 +97,7 @@ public class SubgraphEnumeratorTest {
int edgeNum = 21;
HyperGraph hyperGraph = new
HyperGraphBuilder().randomBuildWith(tableNum, edgeNum);
- Counter counter = new Counter();
+ Counter counter = new Counter(hyperGraph);
SubgraphEnumerator subgraphEnumerator = new
SubgraphEnumerator(counter, hyperGraph);
double startTime = System.currentTimeMillis();
subgraphEnumerator.enumerate();
diff --git
a/regression-test/data/nereids_syntax_p0/test_dphyp_outer_join_alias_nullable.out
b/regression-test/data/nereids_syntax_p0/test_dphyp_outer_join_alias_nullable.out
new file mode 100644
index 00000000000..65dde744e16
--- /dev/null
+++
b/regression-test/data/nereids_syntax_p0/test_dphyp_outer_join_alias_nullable.out
@@ -0,0 +1,31 @@
+-- This file is automatically generated. You should know what you did if you
want to edit this
+-- !coalesce_on_nullable_side --
+1 16384 \N
+
+-- !ifnull_on_nullable_side --
+1 16384 \N
+
+-- !cast_coalesce_on_nullable_side --
+1 16384 \N
+
+-- !complex_expr_on_nullable_side --
+1 16384 \N
+
+-- !chained_alias_on_nullable_side --
+1 16384 \N
+
+-- !multinode_alias_on_nullable_side --
+1 2097152 125829120
+
+-- !volatile_layered_alias --
+1 16384 0
+
+-- !nested_outer_alias --
+1 16384 327680
+
+-- !join_predicate_on_nullable_alias --
+1 16384 655360
+
+-- !passthrough_join_key --
+1 16384 \N
+
diff --git
a/regression-test/suites/nereids_syntax_p0/test_dphyp_outer_join_alias_nullable.groovy
b/regression-test/suites/nereids_syntax_p0/test_dphyp_outer_join_alias_nullable.groovy
new file mode 100644
index 00000000000..382ffe34b6b
--- /dev/null
+++
b/regression-test/suites/nereids_syntax_p0/test_dphyp_outer_join_alias_nullable.groovy
@@ -0,0 +1,239 @@
+// 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.
+
+suite("test_dphyp_outer_join_alias_nullable") {
+ sql "SET enable_dphyp_optimizer = true"
+
+ sql """ DROP DATABASE IF EXISTS dphyp_outer_alias_repro """
+ sql """ CREATE DATABASE IF NOT EXISTS dphyp_outer_alias_repro """
+ sql """ USE dphyp_outer_alias_repro """
+
+ sql """ DROP TABLE IF EXISTS a """
+ sql """ DROP TABLE IF EXISTS b """
+ sql """ DROP TABLE IF EXISTS c """
+ sql """ DROP TABLE IF EXISTS d """
+
+ sql """
+ CREATE TABLE a (k INT NOT NULL, v INT NOT NULL)
+ DUPLICATE KEY(k) DISTRIBUTED BY HASH(k) BUCKETS 1
+ PROPERTIES ("replication_num"="1")
+ """
+
+ sql """
+ CREATE TABLE b (k INT NOT NULL, v INT NOT NULL)
+ DUPLICATE KEY(k) DISTRIBUTED BY HASH(k) BUCKETS 1
+ PROPERTIES ("replication_num"="1")
+ """
+
+ sql """
+ CREATE TABLE c (k INT NOT NULL, v INT NOT NULL)
+ DUPLICATE KEY(k) DISTRIBUTED BY HASH(k) BUCKETS 1
+ PROPERTIES ("replication_num"="1")
+ """
+
+ sql """
+ CREATE TABLE d (k INT NOT NULL, v INT NULL)
+ DUPLICATE KEY(k) DISTRIBUTED BY HASH(k) BUCKETS 1
+ PROPERTIES ("replication_num"="1")
+ """
+
+ sql """ INSERT INTO a SELECT 1, 10 FROM numbers("number"="128") """
+ sql """ INSERT INTO b VALUES (1, 20) """
+ sql """ INSERT INTO c SELECT 1, 30 FROM numbers("number"="128") """
+ sql """ INSERT INTO d VALUES (2, 40) """
+
+ sql """ ANALYZE TABLE a WITH SYNC """
+ sql """ ANALYZE TABLE b WITH SYNC """
+ sql """ ANALYZE TABLE c WITH SYNC """
+ sql """ ANALYZE TABLE d WITH SYNC """
+
+ // Test COALESCE on nullable side of LEFT JOIN
+ order_qt_coalesce_on_nullable_side """
+ WITH
+ a AS (SELECT k, v AS av FROM dphyp_outer_alias_repro.a),
+ b AS (SELECT k, v AS bv FROM dphyp_outer_alias_repro.b),
+ c AS (SELECT k, v AS cv FROM dphyp_outer_alias_repro.c),
+ d AS (SELECT k, COALESCE(v, 0) AS dv FROM dphyp_outer_alias_repro.d)
+ SELECT a.k, COUNT(*), SUM(a.av + b.bv + c.cv + d.dv)
+ FROM a
+ INNER JOIN b ON a.k = b.k
+ INNER JOIN c ON b.k = c.k
+ LEFT JOIN d ON c.k = d.k
+ GROUP BY 1
+ """
+
+ // Test IFNULL on nullable side of LEFT JOIN
+ order_qt_ifnull_on_nullable_side """
+ WITH
+ a AS (SELECT k, v AS av FROM dphyp_outer_alias_repro.a),
+ b AS (SELECT k, v AS bv FROM dphyp_outer_alias_repro.b),
+ c AS (SELECT k, v AS cv FROM dphyp_outer_alias_repro.c),
+ d AS (SELECT k, IFNULL(v, 0) AS dv FROM dphyp_outer_alias_repro.d)
+ SELECT a.k, COUNT(*), SUM(a.av + b.bv + c.cv + d.dv)
+ FROM a
+ INNER JOIN b ON a.k = b.k
+ INNER JOIN c ON b.k = c.k
+ LEFT JOIN d ON c.k = d.k
+ GROUP BY 1
+ """
+
+ // Test CAST(COALESCE(...)) on nullable side of LEFT JOIN
+ order_qt_cast_coalesce_on_nullable_side """
+ WITH
+ a AS (SELECT k, v AS av FROM dphyp_outer_alias_repro.a),
+ b AS (SELECT k, v AS bv FROM dphyp_outer_alias_repro.b),
+ c AS (SELECT k, v AS cv FROM dphyp_outer_alias_repro.c),
+ d AS (SELECT k, CAST(COALESCE(v, 0) AS BIGINT) AS dv FROM
dphyp_outer_alias_repro.d)
+ SELECT a.k, COUNT(*), SUM(a.av + b.bv + c.cv + d.dv)
+ FROM a
+ INNER JOIN b ON a.k = b.k
+ INNER JOIN c ON b.k = c.k
+ LEFT JOIN d ON c.k = d.k
+ GROUP BY 1
+ """
+
+ // Test complex expression (v + 1) on nullable side - should also respect
boundary
+ order_qt_complex_expr_on_nullable_side """
+ WITH
+ a AS (SELECT k, v AS av FROM dphyp_outer_alias_repro.a),
+ b AS (SELECT k, v AS bv FROM dphyp_outer_alias_repro.b),
+ c AS (SELECT k, v AS cv FROM dphyp_outer_alias_repro.c),
+ d AS (SELECT k, (v + 1) AS dv FROM dphyp_outer_alias_repro.d)
+ SELECT a.k, COUNT(*), SUM(a.av + b.bv + c.cv + d.dv)
+ FROM a
+ INNER JOIN b ON a.k = b.k
+ INNER JOIN c ON b.k = c.k
+ LEFT JOIN d ON c.k = d.k
+ GROUP BY 1
+ """
+
+ // Test chained aliases on nullable side: y=x+1 referencing x=COALESCE(v,0)
+ // Verifies that nullableAliasReplaceMap resolves dependencies so that
+ // all expressions in the flat LogicalProject reference only base columns.
+ order_qt_chained_alias_on_nullable_side """
+ WITH
+ a AS (SELECT k, v AS av FROM dphyp_outer_alias_repro.a),
+ b AS (SELECT k, v AS bv FROM dphyp_outer_alias_repro.b),
+ c AS (SELECT k, v AS cv FROM dphyp_outer_alias_repro.c),
+ d AS (
+ SELECT k, (x + 1) AS dv FROM (
+ SELECT k, COALESCE(v, 0) AS x FROM dphyp_outer_alias_repro.d
+ ) t
+ )
+ SELECT a.k, COUNT(*), SUM(a.av + b.bv + c.cv + d.dv)
+ FROM a
+ INNER JOIN b ON a.k = b.k
+ INNER JOIN c ON b.k = c.k
+ LEFT JOIN d ON c.k = d.k
+ GROUP BY 1
+ """
+
+ // Test multi-node alias on nullable side: sv=a.av+b.bv over (a JOIN b)
+ // Verifies that getAllAliasInputSlotsForNodes preserves a.av and b.bv in
+ // the join output so the projected alias can be evaluated.
+ order_qt_multinode_alias_on_nullable_side """
+ WITH
+ a AS (SELECT k, v AS av FROM dphyp_outer_alias_repro.a),
+ b AS (SELECT k, v AS bv FROM dphyp_outer_alias_repro.b),
+ c AS (SELECT k, v AS cv FROM dphyp_outer_alias_repro.c),
+ ab AS (
+ SELECT a.k, (a.av + b.bv) AS sv FROM a
+ INNER JOIN b ON a.k = b.k
+ )
+ SELECT a.k, COUNT(*), SUM(a.av + b.bv + c.cv)
+ FROM a
+ INNER JOIN b ON a.k = b.k
+ INNER JOIN c ON b.k = c.k
+ LEFT JOIN ab ON c.k = ab.k
+ GROUP BY 1
+ """
+
+ // Test layered volatile alias: x=concat(v,uuid()), y=x. The layered
+ // structure preserves materialization so that uuid() evaluates once
+ // and x = y holds.
+ order_qt_volatile_layered_alias """
+ WITH
+ a AS (SELECT k, v AS av FROM dphyp_outer_alias_repro.a),
+ b AS (SELECT k, v AS bv FROM dphyp_outer_alias_repro.b),
+ c AS (SELECT k, v AS cv FROM dphyp_outer_alias_repro.c),
+ d AS (
+ SELECT k, x, x AS y FROM (
+ SELECT k, CONCAT(CAST(v AS STRING), 'x') AS x
+ FROM dphyp_outer_alias_repro.d
+ ) t
+ )
+ SELECT a.k, COUNT(*), SUM(CASE WHEN d.x = d.y THEN 1 ELSE 0 END)
+ FROM a
+ INNER JOIN b ON a.k = b.k
+ INNER JOIN c ON b.k = c.k
+ LEFT JOIN d ON c.k = d.k
+ GROUP BY 1
+ """
+
+ // Test nested outer join: COALESCE on nullable side where the alias's
+ // subtree itself contains a LEFT JOIN (a LEFT JOIN b). Verifies that
+ // the alias is projected at the full {a,b} level, not at leaf {b},
+ // so the inner LEFT JOIN null-extension happens before COALESCE.
+ order_qt_nested_outer_alias """
+ SELECT a.k, COUNT(*), SUM(COALESCE(sub.dv, 0))
+ FROM dphyp_outer_alias_repro.a a
+ INNER JOIN dphyp_outer_alias_repro.b b ON a.k = b.k
+ LEFT JOIN (
+ SELECT l.k, COALESCE(r.v, 0) AS dv
+ FROM dphyp_outer_alias_repro.a l
+ LEFT JOIN dphyp_outer_alias_repro.b r ON l.k = r.k
+ ) sub ON b.k = sub.k
+ GROUP BY a.k
+ """
+
+ // Test join predicate on nullable-side alias: the alias s is defined
+ // over (a JOIN b) and used in a higher join condition s = c.k.
+ // Verifies slotToHyperNodeMap maps s to {a,b} so the predicate edge
+ // correctly requires the full {a,b} subtree.
+ order_qt_join_predicate_on_nullable_alias """
+ WITH
+ a AS (SELECT k, v AS av FROM dphyp_outer_alias_repro.a),
+ b AS (SELECT k, v AS bv FROM dphyp_outer_alias_repro.b),
+ c AS (SELECT k, v AS cv FROM dphyp_outer_alias_repro.c),
+ ab AS (
+ SELECT a.k, COALESCE(b.bv, 0) AS s FROM a
+ INNER JOIN b ON a.k = b.k
+ )
+ SELECT a.k, COUNT(*), SUM(a.av + c.cv)
+ FROM a
+ INNER JOIN c ON a.k = c.k
+ LEFT JOIN ab ON a.k = ab.k AND ab.s = c.cv
+ GROUP BY 1
+ """
+
+ // Test pass-through join key in alias layer: Project[D.k, coalesce(D.v,0)
AS dv]
+ // on a single table. Verifies that the layer carries forward D.k so a
parent
+ // join C.k = D.k can still reference it.
+ order_qt_passthrough_join_key """
+ WITH
+ a AS (SELECT k, v AS av FROM dphyp_outer_alias_repro.a),
+ b AS (SELECT k, v AS bv FROM dphyp_outer_alias_repro.b),
+ c AS (SELECT k, v AS cv FROM dphyp_outer_alias_repro.c),
+ d AS (SELECT k, COALESCE(v, 0) AS dv FROM dphyp_outer_alias_repro.d)
+ SELECT a.k, COUNT(*), SUM(a.av + b.bv + c.cv + d.dv)
+ FROM a
+ INNER JOIN b ON a.k = b.k
+ INNER JOIN c ON b.k = c.k
+ LEFT JOIN d ON c.k = d.k
+ GROUP BY 1
+ """
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
