Skip to content

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

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
2010YOUY01 opened this issue May 21, 2025 · 1 comment
Open

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

2010YOUY01 opened this issue May 21, 2025 · 1 comment
Labels
enhancement New feature or request

Comments

@2010YOUY01
Copy link
Contributor

Is your feature request related to a problem or challenge?

Part of #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 #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.

  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

@2010YOUY01 2010YOUY01 added the enhancement New feature or request label May 21, 2025
@2010YOUY01 2010YOUY01 changed the title Track: Enable Arrow Row format by default in sort execution [Track]: Enable Arrow Row format by default in sort execution May 21, 2025
@Dandandan
Copy link
Contributor

The tricky part of this might be not regressing some cases - sorting multiple arrays using lexsort_to_indices is sometimes faster even with multiple arrays, will often use less space and probably can be compressed much better than row format.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants