Skip to content

Commit 9e45962

Browse files
authored
[opt](dphyper)optimize dphyper's statistics calculation (apache#64559)
Problem Summary: After DPHyp join enumeration copies projected join alternatives into the memo, the memo statistics are stale — DPHyp uses a lightweight heuristic cost model that does not produce accurate row counts or column distributions. Without a full statistics refresh, the subsequent cascades optimization phase (OptimizeGroupJob) sees incorrect costs and can produce suboptimal plans. This PR introduces MemoStatsAndCostRecomputer, a bottom-up statistics and cost recomputation pass that runs after DPHyp and before cascades optimization. It re-estimates logical row counts for every memo group, aggregates them according to a configurable policy, and rebuilds physical costs from the refreshed statistics. Key changes: 1. MemoStatsAndCostRecomputer (new) - Bottom-up logical row-count re-estimation for every memo group. - Trust-join-count aggregation policy: scores each candidate expression by counting joins whose equal-join predicates have high-confidence (ndv/rowCount > 0.9) column statistics, keeping only the candidates with the most trusted joins. - Per-group isStatsReliable tracking that stays consistent with the selected/aggregated statistics instead of leaking from the last candidate estimated in the loop. - Project-group stats divergence protection: when two LogicalProject alternatives diverge by >1000x in row count, the stats from the currently-best PhysicalProject are preserved to avoid a misleading aggregate (average/median). - Two-pass logical re-estimation for CTE queries so consumers can settle on refreshed producer stats. - Physical-cost recomputation: clears and rebuilds per-group lowest-cost-plan tables from the refreshed statistics. 2. countTrustJoins / getGroupTrustJoinCount - Deterministic trust-join scoring: replaced child.getFirstLogical- Expression() (memo-insertion-order dependent) with a per-group max across all alternatives, memoized via groupTrustJoinCountCache. - Cache is cleared before each logical re-estimation pass so CTE producer stat changes are reflected. 3. hasTrustableEqualCondition (JoinEstimation) - Rejects unknown column stats (ColumnStatistic.UNKNOWN) before the NDV-ratio check. Unknown stats carry ndv=1, which could falsely pass the >0.9 threshold on one-row tables. 4. GraphSimplifier cache isolation - deriveStats and calCost now snapshot and restore their caches between alternative join-order evaluations, preventing the second alternative from reading column statistics derived for the first alternative's join order. 5. DPHyp shape-check regression tests - TPC-DS SF1000: 99 queries - TPC-H SF1000: 22 queries
1 parent 3818343 commit 9e45962

264 files changed

Lines changed: 21948 additions & 115 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎fe/fe-core/src/main/java/org/apache/doris/nereids/cost/CostModel.java‎

Lines changed: 10 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -552,22 +552,23 @@ public Cost visitPhysicalNestedLoopJoin(
552552
Statistics leftStatistics = context.getChildStatistics(0);
553553
Statistics rightStatistics = context.getChildStatistics(1);
554554
/*
555-
* nljPenalty:
556-
* The row count estimation for nested loop join (NLJ) results often has significant errors.
557-
* When the estimated row count is higher than the actual value, the cost benefits of subsequent
558-
* operators (e.g., aggregation) may be overestimated. This can lead the optimizer to choose a
559-
* plan where a small table joins a large table, severely impacting the overall SQL execution efficiency.
555+
* nljPenalty multiplies the CPU cost (and memory cost) of a nested loop join
556+
* to penalise plans where NLJ is selected for non-trivial input sizes.
560557
*
561-
* For example, if the subsequent operator is an aggregation (AGG) and the GROUP BY key aligns with
562-
* the distribution key of the small table, the optimizer might prioritize avoiding shuffling the NLJ
563-
* results by choosing to join the small table to the large table, even if this is suboptimal.
558+
* NLJ runs in O(leftRows * rightRows) time, but its estimated output row count
559+
* can be inaccurate — when overestimated, downstream operators (e.g. AGG) appear
560+
* to have large cost benefits, tricking the optimizer into preferring a small-left-
561+
* large-right NLJ plan. Applying a penalty proportional to the smaller side's row
562+
* count makes the CPU cost reflect the true join effort, helping the cost model
563+
* favour hash join or reorder the join tree.
564564
*/
565565
double nljPenalty = 1.0;
566566
if (leftStatistics.getRowCount() < 10 * rightStatistics.getRowCount()) {
567567
nljPenalty = Math.min(leftStatistics.getRowCount(), rightStatistics.getRowCount());
568568
}
569+
nljPenalty = Math.max(nljPenalty, 1.0);
569570
return Cost.of(context.getSessionVariable(),
570-
leftStatistics.getRowCount() * rightStatistics.getRowCount(),
571+
leftStatistics.getRowCount() * rightStatistics.getRowCount() * nljPenalty,
571572
rightStatistics.getRowCount() * nljPenalty,
572573
0);
573574
}

‎fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/cascades/OptimizeGroupExpressionJob.java‎

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -93,9 +93,7 @@ private List<Rule> getExplorationRules(CascadesContext cascadesContext) {
9393
private List<Rule> getJoinRules() {
9494
boolean isDisableJoinReorder = context.getCascadesContext().getConnectContext().getSessionVariable()
9595
.isDisableJoinReorder()
96-
|| context.getCascadesContext().isLeadingDisableJoinReorder()
97-
|| context.getCascadesContext().getMemo().getGroupExpressionsSize() > context.getCascadesContext()
98-
.getConnectContext().getSessionVariable().memoMaxGroupExpressionSize;
96+
|| context.getCascadesContext().isLeadingDisableJoinReorder();
9997
boolean isDpHyp = context.getCascadesContext().getStatementContext().isDpHyp();
10098
boolean isAfterDpHyper = context.getCascadesContext().getStatementContext().isAfterDpHyper();
10199
boolean isEnableBushyTree = context.getCascadesContext().getConnectContext().getSessionVariable()

‎fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/executor/Optimizer.java‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,7 @@
3636
import org.apache.doris.nereids.rules.rewrite.EliminateUnnecessaryProject;
3737
import org.apache.doris.nereids.rules.rewrite.MergeProjectable;
3838
import org.apache.doris.nereids.rules.rewrite.PushDownExpressionsInHashCondition;
39+
import org.apache.doris.nereids.stats.MemoStatsAndCostRecomputer;
3940
import org.apache.doris.nereids.trees.plans.Plan;
4041
import org.apache.doris.nereids.trees.plans.logical.LogicalCTEAnchor;
4142
import org.apache.doris.nereids.trees.plans.logical.LogicalCTEConsumer;
@@ -135,6 +136,19 @@ private void dpHypOptimize() {
135136
// Due to EnsureProjectOnTopJoin, root group can't be Join Group, so DPHyp doesn't change the root group
136137
cascadesContext.pushJob(new JoinOrderJob(root, cascadesContext.getCurrentJobContext()));
137138
cascadesContext.getJobScheduler().executeJobPool(cascadesContext);
139+
/*
140+
* Re-estimate logical row counts and rebuild physical costs for the entire memo,
141+
* then reconstruct the lowest-cost plan table for every group.
142+
*
143+
* This is called after DPHyp join enumeration which copies projected join
144+
* alternatives into the memo. DPHyp's own cost model is a lightweight
145+
* heuristic; once all alternatives are in place the memo needs a full
146+
* bottom-up statistics refresh so that the subsequent cascades optimization
147+
* phase (OptimizeGroupJob) sees accurate row counts and costs.
148+
*/
149+
MemoStatsAndCostRecomputer.recompute(root, PhysicalProperties.ANY, cascadesContext,
150+
MemoStatsAndCostRecomputer.LogicalExpressionRowCountSyncPolicy
151+
.KEEP_INDIVIDUAL_EXPRESSION_ROW_COUNT);
138152

139153
// 1) copy out logical plan from memo
140154
Plan plan = cascadesContext.getMemo().copyOutBestLogicalPlan();

‎fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Group.java‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -308,6 +308,10 @@ public void setBestPlan(GroupExpression expression, Cost cost, PhysicalPropertie
308308
}
309309
}
310310

311+
public void putBestPlan(GroupExpression expression, Cost cost, PhysicalProperties properties) {
312+
setBestPlan(expression, cost, properties);
313+
}
314+
311315
/**
312316
* replace best plan with new properties
313317
*/

‎fe/fe-core/src/main/java/org/apache/doris/nereids/memo/GroupExpression.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -344,6 +344,21 @@ public void setEstOutputRowCount(double estOutputRowCount) {
344344
this.estOutputRowCount = estOutputRowCount;
345345
}
346346

347+
public double getEstOutputRowCount() {
348+
return estOutputRowCount;
349+
}
350+
351+
/**
352+
* Clear cost-related state (cost, lowestCostTable, requestPropertiesMap).
353+
* Does NOT reset estOutputRowCount — that is stats state, set during the
354+
* stats computation phase which runs before cost recomputation.
355+
*/
356+
public void clearCostState() {
357+
cost = null;
358+
lowestCostTable.clear();
359+
requestPropertiesMap.clear();
360+
}
361+
347362
public Map<PhysicalProperties, PhysicalProperties> getRequestPropertiesMap() {
348363
return ImmutableMap.copyOf(requestPropertiesMap);
349364
}

‎fe/fe-core/src/main/java/org/apache/doris/nereids/stats/JoinEstimation.java‎

Lines changed: 63 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,7 @@
2727
import org.apache.doris.nereids.trees.plans.JoinType;
2828
import org.apache.doris.nereids.trees.plans.algebra.Join;
2929
import org.apache.doris.nereids.util.ExpressionUtils;
30+
import org.apache.doris.qe.ConnectContext;
3031
import org.apache.doris.statistics.ColumnStatistic;
3132
import org.apache.doris.statistics.ColumnStatisticBuilder;
3233
import org.apache.doris.statistics.Statistics;
@@ -53,6 +54,16 @@ public class JoinEstimation {
5354
private static double TRUSTABLE_UNIQ_THRESHOLD = 0.9;
5455
private static double OUTER_JOIN_NULL_SUPPLELMENT_RATIO = 0.1;
5556

57+
private static boolean shouldDecayRemainingUntrustConditions() {
58+
ConnectContext connectContext = ConnectContext.get();
59+
return connectContext == null || connectContext.getSessionVariable() == null
60+
|| connectContext.getSessionVariable().isEnableLowConfidenceEqJoinRemainingConditionDecay();
61+
}
62+
63+
private static void normalizeColumnStatistics(Statistics outputStats, Statistics inputStats) {
64+
outputStats.normalizeColumnStatistics(inputStats.getRowCount(), false);
65+
}
66+
5667
private static EqualPredicate normalizeEqualPredJoinCondition(EqualPredicate equal, Statistics rightStats) {
5768
boolean changeOrder = equal.left().getInputSlots().stream()
5869
.anyMatch(slot -> rightStats.findColumnStatistics(slot) != null);
@@ -63,6 +74,45 @@ private static EqualPredicate normalizeEqualPredJoinCondition(EqualPredicate equ
6374
}
6475
}
6576

77+
/**
78+
* Check whether any equal-join predicate has high-confidence column statistics
79+
* on at least one side, i.e. {@code ndv / rowCount > TRUSTABLE_UNIQ_THRESHOLD (0.9)}.
80+
*
81+
* A "trustable" equality means one side of the join key is nearly unique, so the
82+
* join selectivity estimation is reliable. This is used by
83+
* {@code MemoStatsAndCostRecomputer.isTrustJoin()} to score join candidates for
84+
* the {@code trust_join_count} row-count aggregation policy, and by
85+
* {@code estimateInnerJoinWithEqualPredicate()} to separate high-confidence
86+
* equalities from low-confidence ones.
87+
*
88+
* Unknown column stats ({@code ColumnStatistic.UNKNOWN}) are rejected before the
89+
* NDV check because they carry {@code ndv=1} which could falsely pass the ratio
90+
* test on small tables.
91+
*/
92+
static boolean hasTrustableEqualCondition(Statistics leftStats, Statistics rightStats, Join join) {
93+
if (join.getEqualPredicates().isEmpty()) {
94+
return false;
95+
}
96+
double rightStatsRowCount = StatsMathUtil.nonZeroDivisor(rightStats.getRowCount());
97+
double leftStatsRowCount = StatsMathUtil.nonZeroDivisor(leftStats.getRowCount());
98+
return join.getEqualPredicates().stream()
99+
.map(expression -> normalizeEqualPredJoinCondition((EqualPredicate) expression, rightStats))
100+
.anyMatch(equal -> {
101+
ColumnStatistic eqLeftColStats = ExpressionEstimation.estimate(equal.left(), leftStats);
102+
ColumnStatistic eqRightColStats = ExpressionEstimation.estimate(equal.right(), rightStats);
103+
// Reject unknown column stats: ExpressionEstimation.visitSlotReference()
104+
// returns ColumnStatistic.UNKNOWN (ndv=1, isUnKnown=true) when a slot
105+
// has no stats. An unknown column with ndv=1 could satisfy the NDV-ratio
106+
// check for small row counts, but the equality should not be treated as
107+
// trustable.
108+
if (eqLeftColStats.isUnKnown || eqRightColStats.isUnKnown) {
109+
return false;
110+
}
111+
return eqRightColStats.ndv / rightStatsRowCount > TRUSTABLE_UNIQ_THRESHOLD
112+
|| eqLeftColStats.ndv / leftStatsRowCount > TRUSTABLE_UNIQ_THRESHOLD;
113+
});
114+
}
115+
66116
private static boolean joinConditionContainsUnknownColumnStats(Statistics leftStats,
67117
Statistics rightStats, Join join) {
68118
for (Expression expr : join.getEqualPredicates()) {
@@ -150,6 +200,11 @@ private static Statistics estimateInnerJoinWithEqualPredicate(Statistics leftSta
150200
Optional<Double> ratio = unTrustEqualRatio.stream().min(Double::compareTo);
151201
if (ratio.isPresent()) {
152202
outputRowCount = Math.max(1, outputRowCount * ratio.get());
203+
if (shouldDecayRemainingUntrustConditions()) {
204+
outputRowCount = Math.max(1, outputRowCount * Math.pow(
205+
UNTRUSTABLE_CONDITION_SELECTIVITY_LINEAR_FACTOR,
206+
Math.max(0, unTrustableCondition.size() - 1)));
207+
}
153208
}
154209
}
155210
innerJoinStats = crossJoinStats.withRowCountAndEnforceValid(outputRowCount);
@@ -296,7 +351,8 @@ private static Statistics estimateSemiOrAnti(Statistics leftStats, Statistics ri
296351
.putColumnStatistics(rightStats.columnStatistics())
297352
.build();
298353
}
299-
result.normalizeColumnStatistics();
354+
normalizeColumnStatistics(result,
355+
join.getJoinType().isLeftSemiOrAntiJoin() ? leftStats : rightStats);
300356
return result;
301357
}
302358
double rowCount = Double.POSITIVE_INFINITY;
@@ -354,7 +410,8 @@ private static Statistics estimateSemiOrAnti(Statistics leftStats, Statistics ri
354410
builder.setRowCount(rowCount);
355411
}
356412
Statistics outputStats = builder.build();
357-
outputStats.normalizeColumnStatistics();
413+
normalizeColumnStatistics(outputStats,
414+
join.getJoinType().isLeftSemiOrAntiJoin() ? leftStats : rightStats);
358415
return outputStats;
359416
}
360417
}
@@ -376,7 +433,8 @@ private static Statistics estimateAsofInnerJoin(Statistics leftStats, Statistics
376433
.putColumnStatistics(rightStats.columnStatistics())
377434
.build();
378435
}
379-
result.normalizeColumnStatistics();
436+
normalizeColumnStatistics(result,
437+
join.getJoinType().isAsofLeftInnerJoin() ? leftStats : rightStats);
380438
return result;
381439
}
382440
double rowCount = Double.POSITIVE_INFINITY;
@@ -403,7 +461,8 @@ private static Statistics estimateAsofInnerJoin(Statistics leftStats, Statistics
403461
}
404462
builder.setRowCount(rowCount);
405463
Statistics outputStats = builder.build();
406-
outputStats.normalizeColumnStatistics();
464+
normalizeColumnStatistics(outputStats,
465+
join.getJoinType().isAsofLeftInnerJoin() ? leftStats : rightStats);
407466
return outputStats;
408467
}
409468
}

0 commit comments

Comments
 (0)