You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@arrow.apache.org by "cyrankiewicz (via GitHub)" <gi...@apache.org> on 2025/10/16 09:39:57 UTC
[I] Improve Table.sort_by performance [arrow]
cyrankiewicz opened a new issue, #47832:
URL: https://github.com/apache/arrow/issues/47832
### Describe the enhancement requested
It seems Table.sort_by always runs on a single thread, given that tables are stored in-memory I find it surprising.
### Component(s)
Python
--
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: issues-unsubscribe@arrow.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] [Python][Acero] Improve Table.sort_by performance [arrow]
Posted by "cyrankiewicz (via GitHub)" <gi...@apache.org>.
cyrankiewicz commented on issue #47832:
URL: https://github.com/apache/arrow/issues/47832#issuecomment-3410638781
Here is an example:
```python
from typing import Tuple
import numpy as np
import pyarrow as pa
import pyarrow.acero as ac
import contextlib
import resource
import time
def generate_data(N: int):
return pa.Table.from_pydict({'col': np.random.rand(N)})
def parallel_sort(table: pa.Table, sort_keys: list[Tuple[str, str]]) -> pa.Table:
num_producers = pa.cpu_count()
num_rows = table.num_rows
slice_sz = (num_rows + num_producers - 1) // num_producers
if num_producers > 1:
return ac.Declaration.from_sequence(
[
ac.Declaration(
"union",
ac.ExecNodeOptions(),
inputs=[
ac.Declaration.from_sequence(
[
ac.Declaration(
"table_source",
ac.TableSourceNodeOptions(
table.slice(k * slice_sz, slice_sz)
),
),
ac.Declaration(
"order_by",
ac.OrderByNodeOptions(sort_keys=sort_keys),
),
]
)
for k in range(num_producers)
],
),
ac.Declaration("order_by", ac.OrderByNodeOptions(sort_keys=sort_keys)),
]
).to_table()
else:
return table.sort_by(sort_keys=sort_keys)
@contextlib.contextmanager
def timing(title: str):
start_time = time.perf_counter()
start_process_time = time.process_time()
yield
wall_time = time.perf_counter() - start_time
process_time = time.process_time() - start_process_time
print(f"{title}: {wall_time=:.4} {process_time=:.4}")
if __name__ == '__main__':
table = generate_data(10_000_000)
with timing('table.sort_by'):
table.sort_by([('col', 'ascending')])
with timing('hand-written-acero-plan (messy)'):
parallel_sort(table, [('col', 'ascending')])
```
running this on the latest stable `pyarrow: 21.0.0`, I get:
```
$ python benchmark.py
table.sort_by: wall_time=2.174 process_time=2.174
hand-written-acero-plan (messy): wall_time=1.1 process_time=6.261
```
For the regular `table.sort_by` we always get process_time ~ wall_time, this means that even if sorting somehow uses multiple cores it fails to get any speedup from it.
To show that pyarrow is capable of doing "better" I hand-crafted a plan in acero, it's essentialy an paralle mergesort variant (but weaker since I don't think merging using `OrderByNode` is efficient in this case), this is not a proposal, just an example.
You can see that for that code:
* the reported wall time is shorter than for `table.sort_by` on the same data
* the process_time is much higher than the wall time - multiple CPUs were engaged in parallel.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] [Python][Acero] Improve Table.sort_by performance [arrow]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on issue #47832:
URL: https://github.com/apache/arrow/issues/47832#issuecomment-6233271191
This issue has been marked as stale because it has had no activity in the past 365 days. Please remove the stale label or comment below, or this issue will be closed in 14 days. If this improvement is still desired but has no current owner, please add the 'Status: needs champion' label.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Improve Table.sort_by performance [arrow]
Posted by "AlenkaF (via GitHub)" <gi...@apache.org>.
AlenkaF commented on issue #47832:
URL: https://github.com/apache/arrow/issues/47832#issuecomment-3410379140
I do not understand Acero internals to be able to provide feedback, but, I did find this in the documentation: https://arrow.apache.org/docs/cpp/acero/user_guide.html#order-by-sink which states:
> This node [order_by_sink] is a “pipeline breaker” and will fully materialize the dataset in memory. In the future, spillover mechanisms will be added which should alleviate this constraint.
Might materializing the whole dataset limit the degree of parallelism?
That being said, can you provide some more context? It is hard to comment on an enhancement proposal with so little information to start with. What is the size of the dataset when single thread is used? If the dataset is smaller, this still happens?Or is the dataset maybe too small to utilise multi-threading? I am not sure that "Table.sort_by always runs on a single thread" really holds.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] [Python][Acero] Improve Table.sort_by performance [arrow]
Posted by "AlenkaF (via GitHub)" <gi...@apache.org>.
AlenkaF commented on issue #47832:
URL: https://github.com/apache/arrow/issues/47832#issuecomment-6409495240
OK, I see `sort_by` uses the `sort_indices` kernel directly. Though Acero's `order_by` also uses the same `sort_indices` kernel so I think this might be a place to look for parallelism? Again, I am not knowledgeable here, cc @zanmato1984, what do you think?
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] [C++][Acero] Improve Table.sort_by performance [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on issue #47832:
URL: https://github.com/apache/arrow/issues/47832#issuecomment-6452732093
Thanks for the ping, @AlenkaF. I would lean toward keeping `sort_indices` as a synchronous compute primitive and letting Acero handle parallel scheduling and concurrency control, rather than having the compute function manage its own parallelism.
`Table.sort_by` could then delegate to an Acero plan, similar to what `Table.group_by(...).aggregate(...)` already does. This would require adding parallel sorting to Acero's `order_by` first.
Although Acero provides a framework for parallel execution, implementing a parallel sort is non-trivial because sorting is not batch-independent. Locally sorted batches still need to be merged into a globally ordered result. Parallel run generation followed by a merge tree seems like a straightforward starting point, although the final merge could remain a bottleneck.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] [C++][Acero] Improve Table.sort_by performance [arrow]
Posted by "AlenkaF (via GitHub)" <gi...@apache.org>.
AlenkaF commented on issue #47832:
URL: https://github.com/apache/arrow/issues/47832#issuecomment-6461199038
Thanks for such a clear and fast reply @zanmato1984!
I propose to keep this issue open, will update the title to reflect the last comment.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org