[Bug](nereids) distributionPrune doesn't slice nereidsPrunedTabletIds per partition

[Larborator]

Search before asking

• I had searched in the issues and found no similar issues.

Version

4.x

What's Wrong?

OlapScanNode.distributionPrune returns the entire nereidsPrunedTabletIds set whenever the query goes through Nereids. The caller OlapScanNode.computeTabletInfo invokes it inside a per-partition loop:

// fe-core/src/main/java/org/apache/doris/planner/OlapScanNode.java
for (Long partitionId : selectedPartitionIds) {
    final MaterializedIndex selectedTable = partition.getIndex(selectedIndexId);
    Collection<Long> prunedTabletIds = distributionPrune(..., true);
    //   ↑ returns the GLOBAL nereidsPrunedTabletIds set, copied into a new ArrayList,
    //     not just tablets belonging to this partition

    if (prunedTabletIds != null) {
        for (Long id : prunedTabletIds) {
            if (selectedTable.getTablet(id) != null) {       // hash lookup
                tablets.add(selectedTable.getTablet(id));    // hash lookup again
                scanTabletIds.add(id);
            }
            // else: id belongs to another partition; result is null and discarded
        }
    }
}

Because nereidsPrunedTabletIds is the union of all selected tablets across all partitions (set in PhysicalPlanTranslator.visitPhysicalOlapScan):

olapScanNode.setNereidsPrunedTabletIds(
    new LinkedHashSet<>(olapScan.getSelectedTabletIds()));

each per-partition iteration walks the entire global set and does a MaterializedIndex.getTablet(id) HashMap lookup on ids that belong to other partitions. The vast majority of these lookups return null and are discarded, but the hash work is already paid.

Complexity

Let P = selectedPartitionIds.size() and M = nereidsPrunedTabletIds.size().

• getTablet calls: O(P × M × 2) instead of O(M × 2)
• HashSet → ArrayList copies inside distributionPrune: O(P × M) elements

The regression is most pronounced on tables whose distribution layout is many partitions × few buckets per partition (e.g. fine-grained hourly partitioning with 2 buckets per partition), because then M ≈ P × bucketsPerPartition, and the total getTablet calls grow as O(P² × bucketsPerPartition).

Concrete example

A range-partitioned table with hourly partitions and 2 buckets per partition, queried with a one-year time range and a bucket-key equality predicate that prunes one of the two buckets per partition:

• P ≈ 24 × 365 ≈ 8760 partitions
• M ≈ 8760 (one tablet per partition selected after bucket pruning)
• Total getTablet lookups: ≈ 76 million
• HashSet copies: ≈ 76M element copies

CPU profiling of the FE plan thread:

OlapScanNode.computeTabletInfo                      83%
  ├─ MaterializedIndex.getTablet -> HashMap.getNode 54%
  ├─ ArrayList.<init> -> HashSet.toArray            17%
  └─ OlapScanNode.addScanRangeLocations              2%

In practice this means a query that planned in ~0.1 s before #53403 now spends ~2.7 s in Nereids Translate Time for the same SQL on the same data.

What You Expected?

distributionPrune under the Nereids path should only return tablets belonging to the partition currently being processed, matching the semantics of the non-Nereids HashDistributionPruner path. Plan time should not depend quadratically on partition count.

How to Reproduce?

1. Create a range-partitioned table with many partitions and few buckets per partition, e.g.:

   CREATE TABLE t (
       event_time DATETIME,
       user_id    BIGINT,
       v          BIGINT
   )
   DUPLICATE KEY(event_time, user_id)
   PARTITION BY RANGE(event_time) (...)              -- hourly, ~8000 partitions
   DISTRIBUTED BY HASH(user_id) BUCKETS 2;

2. Run a query that selects most partitions plus a bucket-key predicate that prunes most of the buckets per partition:

   SET enable_profile = true;
   EXPLAIN SELECT * FROM t
     WHERE event_time >= '2025-01-01' AND event_time < '2026-01-01'
       AND user_id = 12345;

3. SHOW QUERY PROFILE "/<query_id>" and look at Nereids Translate Time. Compare against a build prior to [fix](nereids) fix prune tablets twice #53403, or against an equivalent table whose partition count is small.

4. Optional — attach an async-profiler CPU profile to the FE process during a stress run; the hottest stack will be MaterializedIndex.getTablet -> HashMap.getNode under OlapScanNode.computeTabletInfo.

Anything Else?

No response

Are you willing to submit PR?

• Yes I am willing to submit a PR!

Code of Conduct

• I agree to follow this project's Code of Conduct

[zclllyybb]

Breakwater-GitHub-Analysis-Slot: slot_aa996a8b764f

Initial analysis: this looks like a valid, code-backed FE/Nereids planner performance bug.

What I checked on current master:

• PruneOlapScanTablet builds selectedTabletIds by iterating all selected partitions and appending the per-partition pruned tablets (fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PruneOlapScanTablet.java).
• PhysicalPlanTranslator.computePhysicalOlapScan stores that global list as OlapScanNode.nereidsPrunedTabletIds.
• OlapScanNode.computeTabletInfo() then loops over selectedPartitionIds and calls distributionPrune(..., isNereids && !isPointQuery) for each partition.
• In the Nereids branch, distributionPrune() ignores the current partition's tabletIdsInOrder and returns new ArrayList<>(nereidsPrunedTabletIds). The caller then probes selectedTable.getTablet(id) twice for every id in that global set. MaterializedIndex.getTablet() is a HashMap lookup, so ids from other partitions still pay the lookup cost before being skipped.

Conclusion:

The reported complexity issue is real on current master. It should normally be correctness-neutral because tablets belonging to other partitions are skipped by selectedTable.getTablet(id) != null, but it makes Nereids FE planning cost scale roughly with selected_partitions * globally_pruned_tablets once tablet pruning has populated selectedTabletIds. The many-partitions/few-buckets workload described in the issue is the bad case for this shape.

This also matches the referenced #53403 change: that change avoids re-running hash distribution pruning in computeTabletInfo(), but the replacement global nereidsPrunedTabletIds set is consumed inside a per-partition loop without slicing it back to partition-local tablets.

Suggested fix direction:

• In the Nereids path, make distributionPrune() return only the tablets that belong to the current partition, for example by intersecting the current partition's tabletIdsInOrder with nereidsPrunedTabletIds, or by carrying selected tablets in a partition-keyed structure before translation.
• Avoid the double selectedTable.getTablet(id) lookup by storing the lookup result once before the null check.
• Add a regression test that covers multiple selected partitions with a global Nereids-selected tablet set and verifies that each partition only walks/returns its own tablets. A small performance-oriented FE planner test with many partitions and few buckets would be useful because the current behavior is functionally correct but asymptotically wrong.

Missing information that would still help maintainers:

• Exact affected build/tag for 4.x (master, a specific 4.0/4.1 tag, or a cloud tag) so backport scope can be decided.
• If available, attach the concrete generated DDL and FE profile or async-profiler output. The code path is already enough to confirm the bug, but those artifacts would help quantify the impact and validate the fix.

Recommended next step: treat this as a Nereids planner performance regression introduced by the #53403 fix path, and review a focused patch in OlapScanNode.distributionPrune() plus the regression coverage above.

[Larborator]

Breakwater-GitHub-Analysis-Slot: slot_aa996a8b764f

Initial analysis: this looks like a valid, code-backed FE/Nereids planner performance bug.

What I checked on current master:

• PruneOlapScanTablet builds selectedTabletIds by iterating all selected partitions and appending the per-partition pruned tablets (fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/PruneOlapScanTablet.java).
• PhysicalPlanTranslator.computePhysicalOlapScan stores that global list as OlapScanNode.nereidsPrunedTabletIds.
• OlapScanNode.computeTabletInfo() then loops over selectedPartitionIds and calls distributionPrune(..., isNereids && !isPointQuery) for each partition.
• In the Nereids branch, distributionPrune() ignores the current partition's tabletIdsInOrder and returns new ArrayList<>(nereidsPrunedTabletIds). The caller then probes selectedTable.getTablet(id) twice for every id in that global set. MaterializedIndex.getTablet() is a HashMap lookup, so ids from other partitions still pay the lookup cost before being skipped.

Conclusion:

The reported complexity issue is real on current master. It should normally be correctness-neutral because tablets belonging to other partitions are skipped by selectedTable.getTablet(id) != null, but it makes Nereids FE planning cost scale roughly with selected_partitions * globally_pruned_tablets once tablet pruning has populated selectedTabletIds. The many-partitions/few-buckets workload described in the issue is the bad case for this shape.

This also matches the referenced #53403 change: that change avoids re-running hash distribution pruning in computeTabletInfo(), but the replacement global nereidsPrunedTabletIds set is consumed inside a per-partition loop without slicing it back to partition-local tablets.

Suggested fix direction:

• In the Nereids path, make distributionPrune() return only the tablets that belong to the current partition, for example by intersecting the current partition's tabletIdsInOrder with nereidsPrunedTabletIds, or by carrying selected tablets in a partition-keyed structure before translation.
• Avoid the double selectedTable.getTablet(id) lookup by storing the lookup result once before the null check.
• Add a regression test that covers multiple selected partitions with a global Nereids-selected tablet set and verifies that each partition only walks/returns its own tablets. A small performance-oriented FE planner test with many partitions and few buckets would be useful because the current behavior is functionally correct but asymptotically wrong.

Missing information that would still help maintainers:

• Exact affected build/tag for 4.x (master, a specific 4.0/4.1 tag, or a cloud tag) so backport scope can be decided.
• If available, attach the concrete generated DDL and FE profile or async-profiler output. The code path is already enough to confirm the bug, but those artifacts would help quantify the impact and validate the fix.

Recommended next step: treat this as a Nereids planner performance regression introduced by the #53403 fix path, and review a focused patch in OlapScanNode.distributionPrune() plus the regression coverage above.

Thanks — analysis matches what we saw, and the PR follows your suggested direction.

Done in the latest revision:

• Per-partition slicing in distributionPrune via intersection with the current partition's tabletIdsInOrder (option (a)).
• Cached selectedTable.getTablet(id) to drop the double lookup.