You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "Dandandan (via GitHub)" <gi...@apache.org> on 2024/12/04 09:12:12 UTC
[I] Optimize SortPreservingMergeStream for single-column merge [datafusion]
Dandandan opened a new issue, #13642:
URL: https://github.com/apache/datafusion/issues/13642
### Is your feature request related to a problem or challenge?
Currently `SortPreservingMergeStream` converts column to row-format even when sorting a single column.
We can optimize `SortPreservingMergeStream` to not do this when the sort expression is a single column, which avoids the conversion and makes comparisons faster.
### Describe the solution you'd like
Optimize the `SortPreservingMergeStream` for single column sorts, only converting to row-format when dealing with multi-column sorts.
### Describe alternatives you've considered
_No response_
### Additional context
This should be beneficial for many queries, e.g. https://github.com/apache/datafusion/issues/13586
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Optimize SortPreservingMergeStream for single-column merge [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on issue #13642:
URL: https://github.com/apache/datafusion/issues/13642#issuecomment-2524851266
It seems single column case is optimized here
https://github.com/apache/datafusion/blob/8404cd05891f1884226ce512eee8b9a89ea99c5b/datafusion/physical-plan/src/sorts/streaming_merge.rs#L168-L180
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Optimize SortPreservingMergeStream for single-column merge [datafusion]
Posted by "alan910127 (via GitHub)" <gi...@apache.org>.
alan910127 commented on issue #13642:
URL: https://github.com/apache/datafusion/issues/13642#issuecomment-2524647175
As shown in my [flamegraph profile](https://github.com/apache/datafusion/issues/13586#issuecomment-2514416848), there are code paths that invoke `arrow::Row::cmp`.
From what I understand, `RowValues` (which implements `CursorValues` and whose `cmp` method is called in `is_gt`) might come from `RowCursorStream::convert_batch`.
However, I’m not entirely sure if this is accurate or if it can explain for the lack of usage of `RowConverter` or `SortFields`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Optimize SortPreservingMergeStream for single-column merge [datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on issue #13642:
URL: https://github.com/apache/datafusion/issues/13642#issuecomment-2524709601
Thanks for the flamegraph, indeed looks like it happens when dealing with working with `PartitionedStream`. namely in
```
let cursor = self.convert_batch(&batch)?;
```
and `type CursorStream<C> = Box<dyn PartitionedStream<Output = Result<(C, RecordBatch)>>>;` so it explains
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Optimize SortPreservingMergeStream for single-column merge [datafusion]
Posted by "alan910127 (via GitHub)" <gi...@apache.org>.
alan910127 commented on issue #13642:
URL: https://github.com/apache/datafusion/issues/13642#issuecomment-2517494786
take
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Optimize SortPreservingMergeStream for single-column merge [datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on issue #13642:
URL: https://github.com/apache/datafusion/issues/13642#issuecomment-2524610225
Hi @Dandandan does the `SortPreservingMergeStream` work with row format? I checked quickly https://github.com/apache/datafusion/blob/main/datafusion/physical-plan/src/sorts/merge.rs#L44 I dont see `RowConverter` or SortFields in there. Am I missing something?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Optimize SortPreservingMergeStream for single-column merge [datafusion]
Posted by "alan910127 (via GitHub)" <gi...@apache.org>.
alan910127 commented on issue #13642:
URL: https://github.com/apache/datafusion/issues/13642#issuecomment-2632903421
I've found that the sort isn't actually planned as a single-column sort. The `expressions` in this case contains multiple columns:
```rust
// SQL: row_number() over (partition by id6 order by v3 desc)
LexOrdering {
inner: [
PhysicalSortExpr {
expr: Column { name: "id6", index: 0 },
options: SortOptions { descending: false, nulls_first: false }
},
PhysicalSortExpr {
expr: Column { name: "v3", index: 1 },
options: SortOptions { descending: true, nulls_first: true }
}
]
}
```
I'm not sure whether this behavior is expected or if the plan should have used a single-column sort optimization in this case.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Optimize SortPreservingMergeExec for single-column merge [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #13642:
URL: https://github.com/apache/datafusion/issues/13642#issuecomment-2633132708
Hm I see the query has two
I am not totally sure where I found the single row still in `SortPreservingMergeStream`.
I do think however there is opportunity for `sort_batch` in `ExternalSorter` (https://github.com/apache/datafusion/blob/ea788c72dddf24acd8dc8068cede939e11dfab84/datafusion/physical-plan/src/sorts/sort.rs#L628 ) I'll open a new ticket about that one.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Optimize SortPreservingMergeExec for single-column merge [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan closed issue #13642: Optimize SortPreservingMergeExec for single-column merge
URL: https://github.com/apache/datafusion/issues/13642
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org