apache / apache/datafusion

[DISCUSSION]: Inconsistent Behavior Between prefer_existing_sort and AggregateExec's required_input_ordering

Open
#14,231 6 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

I noticed an inconsistency in how the optimizer handles ordering in certain scenarios, particularly involving the prefer_existing_sort configuration and the creation behavior of AggregateExec.

### 1. Background on `prefer_existing_sort`

The prefer_existing_sort configuration, part of the enforce_distribution optimizer rule, determines whether the optimizer should use an order-preserving RepartitionExec or a non-order-preserving one. If order needs to be satisfied above the RepartitionExec, a SortExec is added.
https://github.com/apache/datafusion/blob/5edb27678d1b97e74bb83d185166980c901a9b06/datafusion/core/src/physical_optimizer/enforce_distribution.rs#L1279-L1293

### 2. Creation Behavior of `AggregateExec`

AggregateExec sets its required_input_ordering based solely on its group-by expressions without checking any configuration like prefer_existing_sort. This effectively makes the ordering a hard requirement.
https://github.com/apache/datafusion/blob/5edb27678d1b97e74bb83d185166980c901a9b06/datafusion/physical-plan/src/aggregates/mod.rs#L461-L479

### 3. The issue

When these two behaviors interact, if the order is being preserved below a `RepartitionExec` and above the `RepartitionExec` if there's an `AggregateExec`, the optimizer decides to add a `SortExec`, no matter what `prefer_existing_sort` is set (because now it's a hard requirement).
```
AggregateExec: mode=FinalPartitioned, ...
SortExec: ..., preserve_partitioning=[true]
RepartitionExec: ....
CsvExec: ...
```
While `AggregateExec` benefits from receiving ordered input, adding a `SortExec` in this context can incur a significant performance cost, negating any benefits of preserving the order.

### 4. Possible solutions:

A straightforward approach could involve `AggregateExec` respecting the `prefer_existing_sort` configuration before adding ordering requirements. However, this introduces challenges:

The `prefer_existing_sort` setting exists at the optimizer level and injecting it into AggregateExec may lead to poor design. Also evaluating this configuration at runtime feels conceptually incorrect.

Given these challenges, I wanted to open a discussion on alternative solutions or design approaches to address this behavior.

Looking forward to hearing the community's thoughts on this!

Contributor guide

Open the contributing guide

Research direction

Start in datafusion/core/src/physical_optimizer/enforce_distribution.rs around lines 1279-1293 and datafusion/physical-plan/src/aggregates/mod.rs around lines 461-479; trace how prefer_existing_sort and required_input_ordering interact in the shown plan. Reproduce the AggregateExec, SortExec, and RepartitionExec case, then define and validate a design that avoids an unintended hard ordering requirement without coupling AggregateExec to optimizer configuration.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.