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 0ae01152099 [fix](gready reorder) Fall back from eager join reorder on
non-finite costs (#68435)
0ae01152099 is described below
commit 0ae011520998ce856af001503904f9a6e3079621
Author: feiniaofeiafei <[email protected]>
AuthorDate: Thu Sep 24 14:24:11 2026 +0800
[fix](gready reorder) Fall back from eager join reorder on non-finite costs
(#68435)
### What problem does this PR solve?
Related PR: #67067
Problem Summary:
Greedy join reorder before eager aggregation can fail while planning
valid aggregate queries when derived statistics contain `NaN`. For
example, after a filter estimates zero rows, arithmetic expression
statistics and null-safe equality can propagate a non-finite row count
into a join cluster.
Because comparisons with `NaN` are always false, the enumerator can
leave either the selected group or its best plan unset, causing a null
pointer when accessing `leftGroup.atoms` or `group.bestPlanInfo.plan`.
An atom cost of `Double.MAX_VALUE` can also fail to beat the initial
cost sentinel.
This change rejects non-finite estimated row counts during atom
initialization and join enumeration, propagates failure through both
linear and bushy enumeration, and uses the existing fallback to retain
the original join plan. Finite atom costs are bounded consistently with
join costs. It does not change the underlying statistics estimation
formulas.
The regression reduces the failing queries to small tables and checks
results with reordering both enabled and disabled, covering zero-row
filters, outer joins, empty tables, NULL-safe matches, and nonempty
aggregates. Expected output was generated with the standard regression
runner using reordering disabled. Unit tests cover non-finite
atom/join/bushy costs, the maximum finite atom cost, and retention of
the original plan.
### Release note
Fix planning failures for aggregate joins with non-finite intermediate
statistics during eager join reorder.
---
.../nereids/rules/rewrite/joinorder/JoinOrder.java | 23 ++++--
.../rules/rewrite/joinorder/JoinReorderGreedy.java | 23 ++++--
.../rewrite/joinorder/JoinReorderGreedyTest.java | 56 ++++++++++++++
.../rewrite/joinorder/JoinReorderRuleTest.java | 11 +++
.../eager_agg/join_reorder_non_finite_stats.out | 39 ++++++++++
.../eager_agg/join_reorder_non_finite_stats.groovy | 86 ++++++++++++++++++++++
6 files changed, 224 insertions(+), 14 deletions(-)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinOrder.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinOrder.java
index 715fad5118f..ffdbec6b688 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinOrder.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinOrder.java
@@ -150,7 +150,7 @@ public abstract class JoinOrder {
}
// Different join order algorithms should have different implementations
- protected abstract void enumerate();
+ protected abstract boolean enumerate();
//Get reorder result
public abstract List<Plan> getResult();
@@ -159,8 +159,7 @@ public abstract class JoinOrder {
if (!init(atoms, predicates)) {
return false;
}
- enumerate();
- return true;
+ return enumerate();
}
private boolean init(List<Plan> atoms, List<Expression> predicates) {
@@ -191,7 +190,9 @@ public abstract class JoinOrder {
BitSet atomBit = new BitSet();
atomBit.set(i);
PlanInfo atomPlanInfo = new PlanInfo(atoms.get(i));
- computeCost(atomPlanInfo);
+ if (!computeCost(atomPlanInfo)) {
+ return false;
+ }
GroupInfo groupInfo = new GroupInfo(atomBit);
groupInfo.bestPlanInfo = atomPlanInfo;
@@ -201,9 +202,16 @@ public abstract class JoinOrder {
return true;
}
- protected void computeCost(PlanInfo planInfo) {
- double cost = planInfo.plan.getStats().getRowCount();
- planInfo.rowCount = cost;
+ protected boolean computeCost(PlanInfo planInfo) {
+ double rowCount = planInfo.plan.getStats().getRowCount();
+ // Arithmetic over zero-row inputs can derive NaN statistics. Such
costs cannot
+ // select a best plan, so let the caller retain the original join
cluster.
+ if (!Double.isFinite(rowCount)) {
+ return false;
+ }
+ planInfo.rowCount = rowCount;
+ // Apply the same bound to atoms as to joins, including
Double.MAX_VALUE.
+ double cost = Math.min(rowCount, MAXIMUM_COST);
if (planInfo.leftChild != null) {
cost = cost > (MAXIMUM_COST - planInfo.leftChild.bestPlanInfo.cost)
? MAXIMUM_COST : cost +
planInfo.leftChild.bestPlanInfo.cost;
@@ -219,6 +227,7 @@ public abstract class JoinOrder {
}
}
planInfo.cost = cost;
+ return true;
}
private boolean computeEdgeCover(List<Plan> atoms) {
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinReorderGreedy.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinReorderGreedy.java
index 75dc04269e4..98aa280c873 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinReorderGreedy.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinReorderGreedy.java
@@ -41,11 +41,14 @@ import java.util.stream.Collectors;
/**JoinReorderGreedy*/
public class JoinReorderGreedy extends JoinOrder {
@Override
- protected void enumerate() {
+ protected boolean enumerate() {
for (int curJoinLevel = 2; curJoinLevel <= atomSize; curJoinLevel++) {
- searchJoinOrders(curJoinLevel - 1, 1, false);
- searchBushyJoinOrders(curJoinLevel);
+ if (!searchJoinOrders(curJoinLevel - 1, 1, false)
+ || !searchBushyJoinOrders(curJoinLevel)) {
+ return false;
+ }
}
+ return true;
}
@Override
@@ -59,14 +62,17 @@ public class JoinReorderGreedy extends JoinOrder {
return ImmutableList.of(group.bestPlanInfo.plan);
}
- private void searchBushyJoinOrders(int curJoinLevel) {
+ private boolean searchBushyJoinOrders(int curJoinLevel) {
// Search bushy joins tree fro level x and y, where
// x + y = curJoinLevel and x > 1 and y > 1 and x >= y.
// Note that join trees of level 3 and below are never bushy,
// so this loop only executes at curJoinLevel >= 4
for (int rightLevel = 2; rightLevel <= curJoinLevel / 2; rightLevel++)
{
- searchJoinOrders(curJoinLevel - rightLevel, rightLevel, true);
+ if (!searchJoinOrders(curJoinLevel - rightLevel, rightLevel,
true)) {
+ return false;
+ }
}
+ return true;
}
protected List<GroupInfo> getGroupForLevel(int level) {
@@ -109,7 +115,7 @@ public class JoinReorderGreedy extends JoinOrder {
return bestPlan;
}
- private void searchJoinOrders(int leftLevel, int rightLevel, boolean
isSearchBushyJoin) {
+ private boolean searchJoinOrders(int leftLevel, int rightLevel, boolean
isSearchBushyJoin) {
List<GroupInfo> leftGroupInfos = getGroupForLevel(leftLevel);
List<GroupInfo> rightGroupInfos = getGroupForLevel(rightLevel);
JoinLevel curLevel = joinLevels.get(leftLevel + rightLevel);
@@ -135,10 +141,13 @@ public class JoinReorderGreedy extends JoinOrder {
joinBitSet.or(leftBitset);
joinBitSet.or(rightBitset);
- computeCost(join.get());
+ if (!computeCost(join.get())) {
+ return false;
+ }
getOrCreateGroupInfo(curLevel, joinBitSet, join.get());
}
}
+ return true;
}
protected Optional<PlanInfo> buildJoin(GroupInfo leftGroup, GroupInfo
rightGroup) {
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinReorderGreedyTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinReorderGreedyTest.java
index 812e5dcb12d..7c0a999a0a7 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinReorderGreedyTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinReorderGreedyTest.java
@@ -41,6 +41,7 @@ import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
+import java.util.Optional;
import java.util.function.Function;
import java.util.stream.Collectors;
@@ -146,6 +147,61 @@ class JoinReorderGreedyTest {
Assertions.assertFalse(greedy.reorder(ImmutableList.of(a, b),
ImmutableList.of(predicate)));
}
+ @Test
+ void testRejectNonFiniteAtomRowCount() {
+ for (double rowCount : new double[] {Double.NaN,
Double.POSITIVE_INFINITY}) {
+ LogicalOlapScan a = scan(51, "a", rowCount, 10);
+ LogicalOlapScan b = scan(52, "b", 100, 10);
+ JoinReorderGreedy greedy = new JoinReorderGreedy();
+ Assertions.assertFalse(greedy.reorder(ImmutableList.of(a, b),
ImmutableList.of()));
+ }
+ }
+
+ @Test
+ void testRejectNonFiniteJoinRowCount() {
+ for (double rowCount : new double[] {Double.NaN,
Double.POSITIVE_INFINITY}) {
+ LogicalOlapScan a = scan(61, "a", 100, 10);
+ LogicalOlapScan b = scan(62, "b", 100, 10);
+ JoinReorderGreedy greedy = new JoinReorderGreedy() {
+ @Override
+ protected Optional<PlanInfo> buildJoin(GroupInfo leftGroup,
GroupInfo rightGroup) {
+ Optional<PlanInfo> join = super.buildJoin(leftGroup,
rightGroup);
+ ((LogicalJoin<?, ?>) join.get().plan).setStatistics(
+ new Statistics(rowCount, ImmutableMap.of()));
+ return join;
+ }
+ };
+ Assertions.assertFalse(greedy.reorder(ImmutableList.of(a, b),
ImmutableList.of()));
+ }
+ }
+
+ @Test
+ void testRejectNonFiniteBushyJoinRowCount() {
+ List<Plan> atoms = ImmutableList.of(scan(63, "a", 10, 10), scan(64,
"b", 10, 10),
+ scan(65, "c", 10, 10), scan(66, "d", 10, 10));
+ JoinReorderGreedy greedy = new JoinReorderGreedy() {
+ @Override
+ protected Optional<PlanInfo> buildJoin(GroupInfo leftGroup,
GroupInfo rightGroup) {
+ Optional<PlanInfo> join = super.buildJoin(leftGroup,
rightGroup);
+ if (leftGroup.atoms.cardinality() == 2 &&
rightGroup.atoms.cardinality() == 2) {
+ ((LogicalJoin<?, ?>) join.get().plan).setStatistics(
+ new Statistics(Double.NaN, ImmutableMap.of()));
+ }
+ return join;
+ }
+ };
+ Assertions.assertFalse(greedy.reorder(atoms, ImmutableList.of()));
+ }
+
+ @Test
+ void testMaximumFiniteAtomCost() {
+ LogicalOlapScan a = scan(71, "a", Double.MAX_VALUE, 10);
+ LogicalOlapScan b = scan(72, "b", 1, 1);
+ JoinReorderGreedy greedy = new JoinReorderGreedy();
+ Assertions.assertTrue(greedy.reorder(ImmutableList.of(a, b),
ImmutableList.of()));
+ Assertions.assertEquals(ImmutableList.of("a", "b"),
collectTableNames(greedy.getResult().get(0)));
+ }
+
private static LogicalOlapScan scan(long tableId, String tableName, double
rowCount, double ndv) {
LogicalOlapScan scan = PlanConstructor.newLogicalOlapScan(tableId,
tableName, 0);
ColumnStatistic columnStatistic = new ColumnStatisticBuilder(rowCount)
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinReorderRuleTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinReorderRuleTest.java
index f478e509a83..3b6ca190eee 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinReorderRuleTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/rules/rewrite/joinorder/JoinReorderRuleTest.java
@@ -123,6 +123,17 @@ class JoinReorderRuleTest {
Assertions.assertSame(original, rewritten);
}
+ @Test
+ void testFallbackWhenAtomRowCountIsNonFinite() {
+ for (double rowCount : new double[] {Double.NaN,
Double.POSITIVE_INFINITY}) {
+ LogicalOlapScan a = scan(131, "a", rowCount, 10);
+ LogicalOlapScan b = scan(132, "b", 100, 10);
+ Plan original = innerJoin(a, b, equal(a, b));
+
+ Assertions.assertSame(original,
JoinReorderRule.INSTANCE.rewrite(original, null));
+ }
+ }
+
@Test
void testReorderAtAtomLimit() {
Plan original = chain(JoinReorderRule.MAX_ATOM_NUM_FOR_GREEDY);
diff --git
a/regression-test/data/query_p0/eager_agg/join_reorder_non_finite_stats.out
b/regression-test/data/query_p0/eager_agg/join_reorder_non_finite_stats.out
new file mode 100644
index 00000000000..379d42d5f5a
--- /dev/null
+++ b/regression-test/data/query_p0/eager_agg/join_reorder_non_finite_stats.out
@@ -0,0 +1,39 @@
+-- This file is automatically generated. You should know what you did if you
want to edit this
+-- !empty_filter --
+0
+
+-- !outer_empty_input --
+right
+
+-- !empty_table --
+0
+
+-- !nonempty_join --
+\N 3 90
+1 3 30
+2 3 60
+
+-- !outer_filtered_input --
+\N 1 0 \N
+1 1 0 \N
+2 1 0 \N
+
+-- !empty_filter --
+0
+
+-- !outer_empty_input --
+right
+
+-- !empty_table --
+0
+
+-- !nonempty_join --
+\N 3 90
+1 3 30
+2 3 60
+
+-- !outer_filtered_input --
+\N 1 0 \N
+1 1 0 \N
+2 1 0 \N
+
diff --git
a/regression-test/suites/query_p0/eager_agg/join_reorder_non_finite_stats.groovy
b/regression-test/suites/query_p0/eager_agg/join_reorder_non_finite_stats.groovy
new file mode 100644
index 00000000000..bb640d16c0b
--- /dev/null
+++
b/regression-test/suites/query_p0/eager_agg/join_reorder_non_finite_stats.groovy
@@ -0,0 +1,86 @@
+// 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("join_reorder_non_finite_stats") {
+ sql "DROP TABLE IF EXISTS eager_non_finite_stats"
+ sql "DROP TABLE IF EXISTS eager_non_finite_empty"
+ sql """
+ CREATE TABLE eager_non_finite_stats (k INT, v INT)
+ DUPLICATE KEY(k)
+ DISTRIBUTED BY HASH(k) BUCKETS 1
+ PROPERTIES ("replication_num" = "1")
+ """
+ sql """
+ CREATE TABLE eager_non_finite_empty (k INT, v INT)
+ DUPLICATE KEY(k)
+ DISTRIBUTED BY HASH(k) BUCKETS 1
+ PROPERTIES ("replication_num" = "1")
+ """
+ sql "INSERT INTO eager_non_finite_stats VALUES (1, 10), (2, 20), (NULL,
30)"
+ sql "ANALYZE TABLE eager_non_finite_stats WITH SYNC"
+ sql "ANALYZE TABLE eager_non_finite_empty WITH SYNC"
+
+ // Reduced from RQG aggregate joins. Column statistics are necessary: k < 0
+ // estimates zero rows, and arithmetic/null-safe equality can derive NaN.
+ for (boolean reorder : [false, true]) {
+ sql "set enable_join_reorder_before_eager_agg=${reorder}"
+ order_qt_empty_filter """
+ SELECT COUNT(*)
+ FROM eager_non_finite_stats a JOIN eager_non_finite_stats b
+ ON (a.k % 7) <=> (b.k % 3)
+ WHERE a.k < 0
+ """
+
+ // The null-rejecting RIGHT JOIN makes an inner cluster's input empty.
+ // The preserved side still has rows, so the correct result is 'right'.
+ order_qt_outer_empty_input """
+ SELECT 'right' AS label
+ FROM eager_non_finite_stats a JOIN eager_non_finite_stats b
+ ON (CASE WHEN a.k > 1 THEN b.k ELSE b.v END) <=> (b.v + 1)
+ LEFT JOIN eager_non_finite_empty c ON FALSE
+ RIGHT JOIN eager_non_finite_stats d ON c.k > 0
+ GROUP BY label
+ """
+
+ order_qt_empty_table """
+ SELECT COUNT(*)
+ FROM eager_non_finite_stats a JOIN eager_non_finite_empty b
+ ON (a.k % 7) <=> (b.k % 3)
+ """
+
+ // Retain nonempty results, duplicate matches and NULL-safe matches
too.
+ order_qt_nonempty_join """
+ SELECT a.k, COUNT(*), SUM(b.v)
+ FROM eager_non_finite_stats a JOIN eager_non_finite_stats b
+ ON (a.k % 2) <=> (b.k % 2)
+ CROSS JOIN eager_non_finite_stats c
+ GROUP BY a.k
+ """
+
+ order_qt_outer_filtered_input """
+ SELECT a.k, COUNT(*), COUNT(b.k), SUM(b.v)
+ FROM eager_non_finite_stats a
+ LEFT JOIN (
+ SELECT b.k, b.v
+ FROM eager_non_finite_stats b JOIN eager_non_finite_stats c
+ ON (b.k % 7) <=> (c.k % 3)
+ WHERE b.k < 0
+ ) b ON a.k <=> b.k
+ GROUP BY a.k
+ """
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
