apache / apache/datafusion

[Track]: Enable Arrow Row format by default in sort execution

Open
#16,131 1 comment 2 reactions 0 assignees View on GitHub
enhancement
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

### Is your feature request related to a problem or challenge?

Part of https://github.com/apache/datafusion/issues/16065
Note: some steps are not related spilling execution, but they're very related general optimization, so I also mentioned them here.

## Background
In sort queries, when the sort key is multiple columns, a row format can be used to accelerate comparison.

See more about the background in:
https://arrow.apache.org/blog/2022/11/07/multi-column-sorts-in-arrow-rust-part-1/
https://duckdb.org/pdf/ICDE2023-kuiper-muehleisen-sorting.pdf

## Current status
Row format is used in the sort-preserving merge executor to speed up comparison among multiple merge inputs, but not used in the sort executor.

Note: probably its better to help get https://github.com/apache/datafusion/pull/15380 merged first, then start the following steps.

## Purposed next steps
1. Use row format by default in the sort executor. This may temporarily slow down end-to-end benchmarks, but performance can be recovered through future optimizations (see the next point). This change also resolves [issue #14748](https://github.com/apache/datafusion/issues/14748).

2. A sort query executed across multiple partitions currently goes through two stages of SPM: `Local Sort -> SPM1 -> SPM2`. At each stage, the Arrow Row Format array is repeatedly converted without reuse. We should pass the converted rows downstream to enable reuse and reduce overhead.

3. For further optimization in workloads with nearly sorted input, the converted rows can be used to compute each local sort batch’s min/max. This can help concatenate batches without gaps and reduce the degree of merging needed.

4. For further optimization in memory-limited sorts, the converted rows can be written to the spill file and reused when reading back, improving efficiency.

### Describe the solution you'd like

_No response_

### Describe alternatives you've considered

_No response_

### Additional context

_No response_

Contributor guide

Open the contributing guide

Research direction

Start with issue #16065 and PR #15380, then inspect the sort executor and sort-preserving merge executor described in this issue. Determine which of the four proposed optimization steps is in scope and how the current Arrow Row Format conversions flow between stages. Done should be defined against the selected step, beginning with enabling row format by default in sort execution.

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
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.