seawinde commented on code in PR #63899:
URL: https://github.com/apache/doris/pull/63899#discussion_r3612846875
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/PartitionIncrementMaintainer.java:
##########
@@ -259,29 +261,41 @@ public Void visitLogicalJoin(LogicalJoin<? extends Plan,
? extends Plan> join,
// check join type and partition column side
Set<Slot> leftColumnSet = join.child(0).getOutputSet();
Set<NamedExpression> namedExpressions = new
HashSet<>(context.getPartitionAndRefExpressionMap().keySet());
+ boolean needVisitJoinChildren = false;
+ boolean needCollectInvalidRight = false;
+ boolean needCollectInvalidLeft = false;
for (NamedExpression partitionSlotToCheck : namedExpressions) {
if (!(partitionSlotToCheck instanceof SlotReference)) {
continue;
}
boolean useLeft = leftColumnSet.contains(partitionSlotToCheck);
JoinType joinType = join.getJoinType();
if (joinType.isInnerJoin() || joinType.isCrossJoin()) {
- visit(join, context);
+ needVisitJoinChildren = true;
} else if ((joinType.isLeftJoin()
|| joinType.isLeftSemiJoin()
|| joinType.isLeftAntiJoin()) && useLeft) {
- context.collectInvalidTableSet(join.right());
- visit(join, context);
+ needCollectInvalidRight = true;
+ needVisitJoinChildren = true;
} else if ((joinType.isRightJoin()
|| joinType.isRightAntiJoin()
|| joinType.isRightSemiJoin()) && !useLeft) {
- context.collectInvalidTableSet(join.left());
- visit(join, context);
+ needCollectInvalidLeft = true;
+ needVisitJoinChildren = true;
} else {
context.addFailReason(String.format("partition column is
in un supported join null generate side, "
+ "current join type is %s, partitionSlot is %s",
joinType, partitionSlotToCheck));
}
}
+ if (needCollectInvalidRight) {
+ context.collectInvalidTableSet(join.right());
+ }
+ if (needCollectInvalidLeft) {
+ context.collectInvalidTableSet(join.left());
+ }
+ if (needVisitJoinChildren) {
+ visit(join, context);
+ }
Review Comment:
复杂度变化是：
旧：K × 遍历 Join 子树
新：1 × 遍历 Join 子树
这里的 K 不是“MV 有几个分区列”，而是当前 Join 上 partitionAndRefExpressionMap 中需要追踪的等价 Slot
数量。一个分区列经过等值 Join 后，可以扩展成多个 Slot。
例如：
SELECT f.dt, SUM(f.value)
FROM fact f
JOIN header h ON f.dt = h.dt
GROUP BY f.dt;
MV 按 f.dt 分区。
进入 Join 前，context 里大致是：
partitionAndRefExpressionMap = {
f.dt
}
在 visitLogicalJoin()
前半段，fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/PartitionIncrementMaintainer.java:898
会根据：
f.dt = h.dt
得到等价 Slot：
f.dt -> {h.dt}
然后在
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/PartitionIncrementMaintainer.java:252
把 h.dt 加进 context：
partitionAndRefExpressionMap = {
f.dt,
h.dt
}
于是后面的循环实际执行两次：
for (partitionSlotToCheck : [f.dt, h.dt]) {
if (innerJoin) {
visit(join, context);
}
}
旧代码相当于：
f.dt -> 遍历 fact JOIN header 整棵子树
h.dt -> 再遍历 fact JOIN header 整棵子树
所以这里 K = 2。新代码只是设置两次 needVisitJoinChildren = true，最后仅遍历一次。
再看三表 Join：
FROM fact f
JOIN header h ON f.dt = h.dt
JOIN detail d ON f.dt = d.dt
等价集合可能变成：
{f.dt, h.dt, d.dt}
此时当前 Join 的 K = 3。旧代码会遍历 Join 子树三次。
更糟的是 Join 树通常是：
Join(f.dt = d.dt)
/ \
Join(f.dt = h.dt) detail
/ \
fact header
外层 Join 遍历三次时，每次进入内层 Join，内层又可能按多个 Slot 重复遍历。因此嵌套 Join
中开销可能接近乘法放大，而不只是简单多走两次。
所以，即使 MV 只有一个分区列，只要它通过等值 Join 对应到多张表，K 就会大于 1。
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
