You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "gruuya (via GitHub)" <gi...@apache.org> on 2023/08/02 12:43:59 UTC

[GitHub] [arrow-datafusion] gruuya opened a new pull request, #7180: Eager external sorting

gruuya opened a new pull request, #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180

   # Which issue does this PR close?
   
   Partially addresses #7149 
   
   # Rationale for this change
   
   Try to take advantage of the `fetch` count known to the `SortExec` to reduce the size of the sorted batches that are later merged.
   
   # What changes are included in this PR?
   
   Instead of accumulating the full batches prior to sorting/spilling them in preparation for the merge-sort, try to do the sorting ahead of time on each incoming batch inside of the `ExternalSorter`.
   
   # Are these changes tested?
   
   The existing sort-spill tests pass. As for the timing and memory implications, using the setup:
   - `jemallocator::Jemalloc` for the global allocator in order to record the memory profiles using bytehound
   - `https://seafowl-public.s3.eu-west-1.amazonaws.com/tutorial/trase-supply-chains.parquet` as target for the external table `CREATE EXTERNAL TABLE supply_chains STORED AS PARQUET LOCATION '/home/ubuntu/supply-chains.parquet';`
   - run `SELECT * FROM supply_chains ORDER BY flow_id DESC LIMIT K` for K=1, 10, 100, 1000
   
   
    I've recorded the following:
   
   
   1. current main
   <img width="1395" alt="slika" src="https://github.com/apache/arrow-datafusion/assets/45558892/b0fa3351-f8a2-48b8-af85-1aed4e47186d">
   2. this PR
   <img width="1380" alt="slika" src="https://github.com/apache/arrow-datafusion/assets/45558892/a648e88b-c444-49a2-9a5e-6d50f516fae1">
   
   
   # Are there any user-facing changes?
   
   Only runtime/memory profiles.


-- 
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


[GitHub] [arrow-datafusion] alamb commented on pull request #7180: Top-K eager batch sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1671311059

   I have been thinking about this PR and implementing `LIMIT` in general
   
   It is my opinion that we could keep DataFusion simpler *and* make this query faster and use less memory by implementing a real `TopKExec` rather than trying to optimize `SortExec` more
   
   The basic idea would be to keep a heap of the top K items (using Row Format / specialization for single columns) and I think we could even prototype the idea using the same `SortExec` but using a different stream when there was a fetch.
   
   Given how important Sort / Limit is I would like to help.
   
   What do you think @gruuya and @Dandandan and @ozankabak ?


-- 
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


[GitHub] [arrow-datafusion] alamb commented on pull request #7180: Top-K eager batch sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1671809853

   Sounds like a good plan @gruuya -- I believe I have some time this afternoon I can devote to trying to get a prototype for TopK up and running. I'll report back here with any progress 
   


-- 
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


[GitHub] [arrow-datafusion] Dandandan commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1288366071


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +261,23 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self
+            .fetch
+            .map_or(false, |f| f <= input.num_rows() && f <= 100)
+        {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter.
+            // Currently only applied for fetch of 100 rows or less.
+            input = sort_batch(&input, &self.expr, self.fetch)?;

Review Comment:
   Yes, definitely.



-- 
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


[GitHub] [arrow-datafusion] alamb commented on pull request #7180: Top-K eager external sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1666117428

   > TLDR: unstable sort and changed batch sizes result in different order of items with the same value in the sort column between main and this PR.
   
   very nice πŸ•΅οΈ work
   
   
   > Perhaps it's ok to change the test output to match the one being obtained now?
   
   ```sql
   SELECT
     MAX(c12) OVER window1,
     MIN(c12) OVER window2 as max1
     FROM aggregate_test_100
     WINDOW window1 AS (ORDER BY C12),
     window2 AS (PARTITION BY C11),
     window3 AS (ORDER BY C1)
     ORDER BY C3
     LIMIT 5
   ```
   
   If you are saying there are more than 5 values with the same value of c5 then I think technically the query produces non specified answers and thus I think we should change the test to be deterministic -- perhaps we can increase the `LIMIT` to include all the first values of `c3`
   
   


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager external sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1283154043


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -133,11 +131,28 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter; first perform a memory reservation
+            // for the sorting procedure.
+            let mut reservation =
+                MemoryConsumer::new(format!("insert_batch{}", self.partition_id))
+                    .register(&self.runtime.memory_pool);
+
+            // TODO: This should probably be try_grow (#5885)
+            reservation.resize(input.get_array_memory_size());
+            // Maybe we should perform sorting in a parallel task to unblock the caller

Review Comment:
   Ah yeah, I think that makes sense; will remove the 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


[GitHub] [arrow-datafusion] alamb commented on a diff in pull request #7180: Top-K eager external sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1283098372


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -133,11 +131,28 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter; first perform a memory reservation
+            // for the sorting procedure.
+            let mut reservation =
+                MemoryConsumer::new(format!("insert_batch{}", self.partition_id))
+                    .register(&self.runtime.memory_pool);
+
+            // TODO: This should probably be try_grow (#5885)
+            reservation.resize(input.get_array_memory_size());
+            // Maybe we should perform sorting in a parallel task to unblock the caller

Review Comment:
   if the parallelization is working correctly all the other cores should be busy doing something useful here -- and thus sorting in another task may not be warranted but I am not sure



-- 
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


[GitHub] [arrow-datafusion] alamb commented on pull request #7180: Top-K eager batch sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1673629789

   FWIW I made a very simplistic POC for a special TopK operator and for my test (K=10) it goes almost 2x faster and uses 1/3 the peak memory. There is also plenty of room for both algorithmic and engineering optimizations. I'll be hacking on the idea in https://github.com/apache/arrow-datafusion/pull/7250 and will make a broader announcement when ready


-- 
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


[GitHub] [arrow-datafusion] alamb commented on pull request #7180: Top-K eager batch sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1668018956

   > Strangely I see slowdown even for base cases when eager sorting does not apply. I'll need to think about it a bit.
   
   I wonder if it could be related to the benchmark itself somehow -- perhaps you could run the benchmark again main twice and see if you got consistent results?
   
   I believe I was seeing some non consistent results when I was running last week myself


-- 
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


[GitHub] [arrow-datafusion] alamb commented on pull request #7180: Top-K eager batch sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1669657173

   I will not merge this until we get consensus on the approach


-- 
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


[GitHub] [arrow-datafusion] gruuya closed pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya closed pull request #7180: Top-K eager batch sorting 
URL: https://github.com/apache/arrow-datafusion/pull/7180


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1288155319


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +261,23 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self
+            .fetch
+            .map_or(false, |f| f <= input.num_rows() && f <= 100)
+        {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter.
+            // Currently only applied for fetch of 100 rows or less.
+            input = sort_batch(&input, &self.expr, self.fetch)?;

Review Comment:
   Yeah, that's worth trying to benchmark as well. It could also be something like every `n` unsorted rows or every `size` unsorted bytes to accommodate for variability in batch row count.



-- 
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


[GitHub] [arrow-datafusion] yjshen commented on pull request #7180: Top-K eager batch sorting

Posted by "yjshen (via GitHub)" <gi...@apache.org>.
yjshen commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1667250149

   How about K slightly smaller than the batch size? Say K=8000 when batch size=8192.


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1286583473


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +256,19 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {

Review Comment:
   I was also thinking something similar but along the lines of `f < input.num_rows() && f <= 100`, so that we effectively have a hard cur-off for eager sorting after 100 rows.



-- 
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


[GitHub] [arrow-datafusion] Dandandan commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1287692850


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +261,23 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self
+            .fetch
+            .map_or(false, |f| f <= input.num_rows() && f <= 100)
+        {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter.
+            // Currently only applied for fetch of 100 rows or less.
+            input = sort_batch(&input, &self.expr, self.fetch)?;

Review Comment:
   I wonder whether you could recover part of the perf difference by concar + sorting only once every `n` (say every 10) batches. The selectivity of the limit and total work to be performed is much bigger for sorting 81920 vs 8192 rows, also the merging to be performed will be over fewer batches.



##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +261,23 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self
+            .fetch
+            .map_or(false, |f| f <= input.num_rows() && f <= 100)
+        {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter.
+            // Currently only applied for fetch of 100 rows or less.
+            input = sort_batch(&input, &self.expr, self.fetch)?;

Review Comment:
   I wonder whether you could recover part of the perf difference by concat + sorting only once every `n` (say every 10) batches. The selectivity of the limit and total work to be performed is much bigger for sorting 81920 vs 8192 rows, also the merging to be performed will be over fewer batches.



-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager external sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1285004993


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +251,27 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter; first perform a memory reservation
+            // for the sorting procedure.
+            let mut reservation =

Review Comment:
   I think the reasoning for the new consumer was that we only want to reserve a bit of memory briefly to account for the overhead of keeping both the sorted and original batch at the same time. Given that in this case we drop the old batch asap (due to `input` re-assignment) in favor of a smaller/truncated one I'd agree that a new consumer is not needed in that case. (Same could be said about the consumer/reservation in `sort_batch_stream`,  though in that case since it isn't given that there is a `LIMIT` we'd end up holding 2 same-sized batches at one point in time.)
   
   That said, `reservation.try_grow(input.get_array_memory_size())` does then get called immediately below to check whether the new batch can be kept in memory without breaking the configured limit, so I don't think there's a need for another `try_grow` prior to that.



-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager external sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1285109657


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +251,27 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter; first perform a memory reservation
+            // for the sorting procedure.
+            let mut reservation =

Review Comment:
   So I went ahead to add this, but then it seemed to me that the logic of `split` (and `take` by extension) is backwards? In particular, the `size` of the reservation is not _free_ memory, but instead _used_ memory, right? And with `split` we'd effectively deduct some piece of memory in our accounting that was previously allocated (without actually freeing that memory). 
   
   Atm I went with skipping reservation updates at all in this case; the reason being that we're already holding the input batch in memory and we're are about to (try to) allocate memory for it right after sorting it anyway. Hence, the sole purpose of that reservation seems to be to account for that extra piece of memory due to non-in-place sorting (i.e. having the old and the new bath present at the same time briefly), and that piece of memory is guaranteed to be less than the batch size. Let me know if you'd like me to do something else.
   
   I also changed that tests output. Now all tests should be passing, so it's probably time for the regular benchmarks.



-- 
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


[GitHub] [arrow-datafusion] alamb commented on pull request #7180: Top-K eager external sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1663886146

   I also was thinking we can probably write a test for this behavior in https://github.com/apache/arrow-datafusion/blob/main/datafusion/core/tests/memory_limit.rs
   
   I have something similar in https://github.com/apache/arrow-datafusion/pull/7130#pullrequestreview-1559634018
   
   I can potentially help writing that test if you agree it would be helpful


-- 
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


[GitHub] [arrow-datafusion] alamb commented on a diff in pull request #7180: Top-K eager external sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1285023739


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +251,27 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter; first perform a memory reservation
+            // for the sorting procedure.
+            let mut reservation =

Review Comment:
   Ah that makes sense
   
   I think I think you could use (they very newly added) `Reservation::split()` to track the short allocation and free it on drop without needing an entirely new consumer:
   
   https://github.com/apache/arrow-datafusion/blob/23547587c2773ddddb9b16cba1eb8ebf2eebd85a/datafusion/execution/src/memory_pool/mod.rs#L225-L231
   
   perhaps like 
   ```rust
   let batch_reservation = self.reservation.split(input.get_arra_memory_size());
   input = sort_batch(&input, &self.expr, self.fetch)?;
   // free allocation for previous input
   // (it would also be freed on drop so the free isn't necessary but may be clearer)
   batch_reservation.free();
   ```
   
   
   



-- 
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


[GitHub] [arrow-datafusion] alamb commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1285990301


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +251,27 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter; first perform a memory reservation
+            // for the sorting procedure.
+            let mut reservation =

Review Comment:
   > Atm I went with skipping reservation updates at all in this case; 
   
   I think this make sense -- especially since the extra memory for batches is likely small given k is very often small.



-- 
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


[GitHub] [arrow-datafusion] yjshen commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "yjshen (via GitHub)" <gi...@apache.org>.
yjshen commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1286412463


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +256,19 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {

Review Comment:
   I'm thinking can we make the heuristic `f < input.num_rows() / 10` or something magic numbers to only do eager sort for small `K's?



##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -639,15 +614,47 @@ fn write_sorted(
     Ok(())
 }
 
-fn read_spill(sender: Sender<Result<RecordBatch>>, path: &Path) -> Result<()> {
+/// Stream batches from spill files.
+///
+/// Each spill file has one or more batches. Intra-batch order is guaranteed (each one is sorted),
+/// but the inter-batch ordering is not guaranteed, hence why we need to convert each batch from the
+/// spill to a separate input stream for the merge-sort procedure.

Review Comment:
   Will this produce unnecessary comparison when the inter-batch ordering is guaranteed for the normal case without `K`?
   



-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1286389087


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -465,16 +484,23 @@ impl ExternalSorter {
         // This is a very rough heuristic and likely could be refined further
         if self.reservation.size() < 1048576 {
             // Concatenate memory batches together and sort
-            let batch = concat_batches(&self.schema, &self.in_mem_batches)?;
+            let (_, batches): (Vec<bool>, Vec<RecordBatch>) =
+                std::mem::take(&mut self.in_mem_batches).into_iter().unzip();
+            let batch = concat_batches(&self.schema, &batches)?;
             self.in_mem_batches.clear();
-            return self.sort_batch_stream(batch, metrics);
+            // Even if all individual batches were themselves sorted the resulting concatenated one
+            // isn't guaranteed to be sorted, so we must perform sorting on the stream.
+            return self.sort_batch_stream(batch, false, metrics);

Review Comment:
   Good point; will try to benchmark that change too.



-- 
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


[GitHub] [arrow-datafusion] gruuya commented on pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1668573152

   Ok, I went back and re-visited [a change](https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1664209600) I made previously, and it looks like it was definitely contributing to consistent systemic regression I initially observed.
   
   I also think I found a better way to solve that issue (basically convert all the batches from a single spill into individual streams) that I pushed now. This still results in the optimized memory profiles depicted in the PR description.
   
   Here are the new sorting benchmarks (10 iterations, for fetch in `None, Some(1), Some(10), Some(100), Some(1000), Some(8000), Some(10000)`):
    <details><summary>sorting benchmarks</summary>
     
     ```text
   ┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
   ┃ Query        ┃       main ┃ top-k-eager-sorting ┃        Change ┃
   ┑━━━━━━━━━━━━━━╇━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
   β”‚ Qsort utf8   β”‚ 37157.19ms β”‚          37730.09ms β”‚     no change β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚ 48290.35ms β”‚          49269.24ms β”‚     no change β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚ 38306.38ms β”‚          38645.93ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚ 53457.21ms β”‚          54205.26ms β”‚     no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ None         β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚ 38104.45ms β”‚          38006.01ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ None         β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚ 43931.69ms β”‚          43924.41ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ None         β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1869.92ms β”‚           1899.74ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  2011.87ms β”‚           1821.10ms β”‚ +1.10x faster β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1851.76ms β”‚           1760.68ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1914.27ms β”‚           1953.97ms β”‚     no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  2138.20ms β”‚           2417.24ms β”‚  1.13x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  1999.94ms β”‚           2128.49ms β”‚  1.06x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1904.48ms β”‚           1906.43ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  2025.38ms β”‚           1833.70ms β”‚ +1.10x faster β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1837.30ms β”‚           1787.43ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1905.57ms β”‚           1962.79ms β”‚     no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  2125.98ms β”‚           2436.01ms β”‚  1.15x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  2010.12ms β”‚           2144.80ms β”‚  1.07x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1910.96ms β”‚           1961.26ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  2033.24ms β”‚           1869.98ms β”‚ +1.09x faster β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1845.95ms β”‚           1782.47ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1962.15ms β”‚           1986.78ms β”‚     no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  2157.68ms β”‚           2467.28ms β”‚  1.14x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  2046.18ms β”‚           2199.65ms β”‚  1.08x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1983.56ms β”‚           2035.27ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  2151.34ms β”‚           1995.38ms β”‚ +1.08x faster β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1899.04ms β”‚           1855.03ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  2103.93ms β”‚           2243.71ms β”‚  1.07x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  2274.01ms β”‚           2662.95ms β”‚  1.17x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  2224.79ms β”‚           2587.77ms β”‚  1.16x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  2176.51ms β”‚           2745.07ms β”‚  1.26x slower β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(8000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  2300.06ms β”‚           2695.76ms β”‚  1.17x slower β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(8000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1990.73ms β”‚           2343.61ms β”‚  1.18x slower β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(8000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  2758.47ms β”‚           4018.36ms β”‚  1.46x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(8000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  2903.87ms β”‚           4070.53ms β”‚  1.40x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(8000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  3540.07ms β”‚           5640.86ms β”‚  1.59x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(8000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  2255.55ms β”‚           2181.42ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10000)  β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  2380.78ms β”‚           2367.10ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10000)  β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  2108.30ms β”‚           2022.66ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10000)  β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  2817.34ms β”‚           2758.43ms β”‚     no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10000)  β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  2625.46ms β”‚           2564.71ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10000)  β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  3457.03ms β”‚           3418.22ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10000)  β”‚            β”‚                     β”‚               β”‚
   β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜
   ```
   </details>
   
   Note that the base cases now show no changes compared to main, which is what I expect. There are a couple of speedups, but still the overall direction is regression-y. This is especially pronounced for K = 8000 (good idea for including that value @yjshen).
   
   It could be that there are some further micro-optimizations waiting that would push the runtimes for this branch to merge-acceptable territory while keeping the memory usage as is, though I doubt it. I'll give it some more thought and report back if I come up with 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@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager external sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1285004993


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +251,27 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter; first perform a memory reservation
+            // for the sorting procedure.
+            let mut reservation =

Review Comment:
   I think the reasoning for the new consumer was that we only want to reserve a bit of memory briefly to account for the overhead of keeping both the sorted and original batch at the same time. Given that in this case we drop the old batch asap (due to `input` re-assignment) in favor of a smaller/truncated one I'd agree that a new consumer is not needed in that case. (Same could be said about the consumer/reservation in `sort_batch_stream`,  though in that case since it isn't given that there is a `LIMIT` we'd end up holding 2 same-ish batches at one point in time.)
   
   That said, `reservation.try_grow(input.get_array_memory_size())` does then get called immediately below to check whether the new batch can be kept in memory without breaking the configured limit, so I don't think there's a need for another `try_grow` prior to that.



-- 
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


[GitHub] [arrow-datafusion] gruuya commented on pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1668606350

   Thanks @alamb for the reviews and timely feedback.
   
   > in my opinion this code is now good enough to be merged.
   
   I'd like to emphasize that there are still regressions with this approach. In fact in case of larger files (> 1GB) with K in 1000-8000 range, the runtime seems to be hit the most, with probably negligible memory improvements (if any). Anecdotally, the original file I've been testing does now show considerable speedup though, but that is perhaps not a typical file size (146M). So it's a mixed bag really, and I'm not sure it's best for this to be merged as is.


-- 
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


[GitHub] [arrow-datafusion] alamb commented on pull request #7180: Eager external sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1662144889

   FYI https://github.com/apache/arrow-datafusion/pull/7179 may also be interesting


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1289724142


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +261,23 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self
+            .fetch
+            .map_or(false, |f| f <= input.num_rows() && f <= 100)
+        {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter.
+            // Currently only applied for fetch of 100 rows or less.
+            input = sort_batch(&input, &self.expr, self.fetch)?;

Review Comment:
   Fwiw, I did try out a variety of approaches along these lines, but still failed to eliminate the perf difference. There's probably a combination of parameters that is just right and could yield better results, but with the native Top-K operator in the works that likely won't be necessary.



-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1285109657


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +251,27 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter; first perform a memory reservation
+            // for the sorting procedure.
+            let mut reservation =

Review Comment:
   Hmm, so I went ahead to add this, but then it seemed to me that the logic of `split` is backwards (for this case at least)? In particular, the `size` of the reservation is not _free_ memory, but instead _used_ memory, right? And with `split` + `free` we'd effectively deduct some piece of memory in our accounting that was previously allocated elsewhere (without actually freeing that memory). 
   
   Atm I went with skipping reservation updates at all in this case; the reason being that we're already holding the input batch in memory and we're are about to (try to) allocate memory for it right after sorting it anyway. Hence, the sole purpose of that reservation seems to be to account for that extra piece of memory due to non-in-place sorting (i.e. having the old and the new bath present at the same time briefly), and that piece of memory is guaranteed to be less than the batch size. Let me know if you'd like me to do something else.
   
   I also changed that tests output. Now all tests should be passing, so it's probably time for the regular benchmarks.



-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager external sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1285004993


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +251,27 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter; first perform a memory reservation
+            // for the sorting procedure.
+            let mut reservation =

Review Comment:
   I think the reasoning for the new consumer was that we only want to reserve a bit of memory briefly to account for the overhead of keeping both the sorted and original batch at the same time. Given that in this case we drop the old batch asap (due to `input` re-assignment) in favor of a smaller/truncated one I'd agree that a new consumer is not needed in that case. (Same could be said about the consumer/reservation in `sort_batch_stream`,  though in that case since it isn't given that there is a `LIMIT` we could end up holding 2 same-sized batches at one point in time.)
   
   That said, `reservation.try_grow(input.get_array_memory_size())` does then get called immediately below to check whether the new (sorted/truncated) batch can be kept in memory without breaking the configured limit, so I don't think there's a need for another `try_grow` prior to that.



-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager external sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1285004993


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +251,27 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter; first perform a memory reservation
+            // for the sorting procedure.
+            let mut reservation =

Review Comment:
   I think the reasoning for the new consumer was that we only want to reserve a bit of memory briefly to account for the overhead of keeping both the sorted and original batch at the same time. Given that in this case we drop the old batch asap (due to `input` re-assignment) in favor of a smaller/truncated one I'd agree that a new consumer is not needed in that case. (Same could be said about the consumer/reservation in `sort_batch_stream`,  though in that case since it isn't given that there is a `LIMIT` we could end up holding 2 same-sized batches at one point in time.)
   
   That said, `reservation.try_grow(input.get_array_memory_size())` does then get called immediately below to check whether the new batch can be kept in memory without breaking the configured limit, so I don't think there's a need for another `try_grow` prior to that.



-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1286582862


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -639,15 +614,47 @@ fn write_sorted(
     Ok(())
 }
 
-fn read_spill(sender: Sender<Result<RecordBatch>>, path: &Path) -> Result<()> {
+/// Stream batches from spill files.
+///
+/// Each spill file has one or more batches. Intra-batch order is guaranteed (each one is sorted),
+/// but the inter-batch ordering is not guaranteed, hence why we need to convert each batch from the
+/// spill to a separate input stream for the merge-sort procedure.

Review Comment:
   I think not, because than it should be single record batch per spill. I can add a sort counter to double-check though.



-- 
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


[GitHub] [arrow-datafusion] ozankabak commented on pull request #7180: Top-K eager batch sorting

Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1669647841

   > I'd like to emphasize that there are still regressions with this approach. In fact in case of larger files (> 1GB) with K in 1000-8000 range, the runtime seems to be hit the most, with probably negligible memory improvements (if any). Anecdotally, the original file I've been testing does now show considerable speedup though, but that is perhaps not a typical file size (146M). So it's a mixed bag really, and I'm not sure it's best for this to be merged as is.
   
   I agree. A lot of us are thinking about solving the "top K" problem these days, I feel we should be able to find a solution that will achieve desirable results without the regressions.


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1286754073


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -639,15 +614,47 @@ fn write_sorted(
     Ok(())
 }
 
-fn read_spill(sender: Sender<Result<RecordBatch>>, path: &Path) -> Result<()> {
+/// Stream batches from spill files.
+///
+/// Each spill file has one or more batches. Intra-batch order is guaranteed (each one is sorted),
+/// but the inter-batch ordering is not guaranteed, hence why we need to convert each batch from the
+/// spill to a separate input stream for the merge-sort procedure.

Review Comment:
   Ah, good point; for some reason I thought that only 1 batch gets collected from `in_mem_sort_stream` in case of no fetch, even though that is not a given.



-- 
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


[GitHub] [arrow-datafusion] ozankabak commented on pull request #7180: Top-K eager batch sorting

Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1671330447

   I think trying out the `TopK` operator idea is definitely worthwhile. I think we will need to be very careful with the implementation (e.g. the heap part) to get it to perform, but I have a feeling that we should be able to get decent performance if we get the implementation right.
   
   Even if it turns out we can't, I think that effort will result in some interesting learnings we should be able to leverage to optimize the LIMIT case via other approaches.


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1667235351

   > Would it be possible to compare the sorting performance of this pull request with the main branch by modifying the test sets in the description of [#6163](https://github.com/apache/arrow-datafusion/pull/6163) with different values of `K`?
   
   Certainly; I started up a slightly modified sorting benchmark with an additional [outer loop](https://github.com/apache/arrow-datafusion/blob/main/benchmarks/src/bin/parquet.rs#L202-L214) `for fetch in &[None, Some(1), Some(10), Some(100), Some(1000), Some(10000)]`. The idea is that the first and last case should not hit the eager sorting code heuristic (because of the missing fetch, and fetch being larger than batch sizes respectively), so they should be same as on main. Will report back today hopefully.


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1671652152

   Agreed, real `TopKExec` would be fantastic (actually I was convinced that this was already implemented in 28.0.0 after a cursory code/PR glance, hence my original issue #7149).
   
   That said, that may take some time, and this PR feels to be on the verge of breaking even when it comes to performance and thus serve as a bandaid/base case until the real thing is implemented. So I'm compelled to continue experimenting with a couple of related approaches (i.e. things along the line of @Dandandan's batched eager sorting) for a short while if you don't mind (and share if I find something promising).


-- 
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


[GitHub] [arrow-datafusion] alamb commented on pull request #7180: Top-K eager batch sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1672164001

   I have made some progress on a native TopK operator -- I need to run some performance tests and polish it up and then I'll share it. 
   
   I am sure it will need some additional work but I think it is looking promising


-- 
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


[GitHub] [arrow-datafusion] yjshen commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "yjshen (via GitHub)" <gi...@apache.org>.
yjshen commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1286603014


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -639,15 +614,47 @@ fn write_sorted(
     Ok(())
 }
 
-fn read_spill(sender: Sender<Result<RecordBatch>>, path: &Path) -> Result<()> {
+/// Stream batches from spill files.
+///
+/// Each spill file has one or more batches. Intra-batch order is guaranteed (each one is sorted),
+/// but the inter-batch ordering is not guaranteed, hence why we need to convert each batch from the
+/// spill to a separate input stream for the merge-sort procedure.

Review Comment:
   A spill file is generated by `in_mem_sort()` and then spill. And `spill_sorted_batches` takes `batches: Vec<RecordBatch>` as one of the arguments.



-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1286970765


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -465,16 +484,23 @@ impl ExternalSorter {
         // This is a very rough heuristic and likely could be refined further
         if self.reservation.size() < 1048576 {
             // Concatenate memory batches together and sort
-            let batch = concat_batches(&self.schema, &self.in_mem_batches)?;
+            let (_, batches): (Vec<bool>, Vec<RecordBatch>) =
+                std::mem::take(&mut self.in_mem_batches).into_iter().unzip();
+            let batch = concat_batches(&self.schema, &batches)?;
             self.in_mem_batches.clear();
-            return self.sort_batch_stream(batch, metrics);
+            // Even if all individual batches were themselves sorted the resulting concatenated one
+            // isn't guaranteed to be sorted, so we must perform sorting on the stream.
+            return self.sort_batch_stream(batch, false, metrics);

Review Comment:
   So I did try to test this approach as well, and then saw some improvements that seemed too good to be true. I went and re-ran the benchmarks again and the improvements held, until they didn't at some point πŸ€·πŸ»β€β™‚οΈ  (fwiw I'm running the benchmarks on a cloud VM, not dedicated hardware).
   
   In hindsight, the sorting benchmarks actually do not use a memory limit and so there were no spills and this code path wasn't exercised. I did try running the benchmarks with memory limits on, but then I hit `Dictionary replacement detected when writing IPC file format.` arrow error during spilling. It seems like this is a general problem as it happens on the main branch too, though I haven't investigated further.
   
   Either way, I'll add this check now even without doing benchmarking on it because it seems it can only help.



##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -465,16 +484,23 @@ impl ExternalSorter {
         // This is a very rough heuristic and likely could be refined further
         if self.reservation.size() < 1048576 {
             // Concatenate memory batches together and sort
-            let batch = concat_batches(&self.schema, &self.in_mem_batches)?;
+            let (_, batches): (Vec<bool>, Vec<RecordBatch>) =
+                std::mem::take(&mut self.in_mem_batches).into_iter().unzip();
+            let batch = concat_batches(&self.schema, &batches)?;
             self.in_mem_batches.clear();
-            return self.sort_batch_stream(batch, metrics);
+            // Even if all individual batches were themselves sorted the resulting concatenated one
+            // isn't guaranteed to be sorted, so we must perform sorting on the stream.
+            return self.sort_batch_stream(batch, false, metrics);

Review Comment:
   So I did try to test this approach as well, and then saw some improvements that seemed too good to be true. I went and re-ran the benchmarks again and the improvements held, until they didn't at some point πŸ€·πŸ»β€β™‚οΈ  (fwiw I'm running the benchmarks on a cloud VM, not dedicated hardware).
   
   In hindsight, the sorting benchmarks actually do not use a memory limit and so there were no spills and this code path wasn't exercised. I did try running the benchmarks with memory limits on, but then I hit `Dictionary replacement detected when writing IPC file format.` arrow error during spilling. It seems like this is a general problem as it happens on the main branch too, though I haven't investigated further.
   
   Either way, I'll add this check now even without doing benchmarking on it because it seems it can only help.



-- 
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


[GitHub] [arrow-datafusion] alamb commented on pull request #7180: Top-K eager external sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1666474912

   > Oh actually I meant that there are only 2 identical values for the sorting column (C3) which end up in the top-5 according to the test query, but their order is unstable when using a LIMIT as opposed to without it:
   
   Yeah, I agree this test is not well designed as it is "non deterministic" (there is no one single right answer)
   
   I think either updating the output or updating the test are both appropriate in this case
   
   We could also add `rowsort` to the query, but that might obscure real ordering bugs given the query has an ORDER BY.


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1286391361


##########
datafusion/core/tests/memory_limit.rs:
##########
@@ -45,17 +47,38 @@ fn init() {
     let _ = env_logger::try_init();
 }
 
+#[rstest]
+#[case::cant_grow_reservation(vec!["Resources exhausted: Failed to allocate additional", "ExternalSorter"], 100_000)]
+#[case::cant_spill_to_disk(vec!["Resources exhausted: Memory Exhausted while Sorting (DiskManager is disabled)"], 200_000)]
+#[case::no_oom(vec![], 600_000)]
 #[tokio::test]
-async fn oom_sort() {
+async fn sort(#[case] expected_errors: Vec<&str>, #[case] memory_limit: usize) {
     TestCase::new(
         "select * from t order by host DESC",
-        vec![
-            "Resources exhausted: Memory Exhausted while Sorting (DiskManager is disabled)",
-        ],
-        200_000,
+        expected_errors,
+        memory_limit,
+    )
+    .run()
+    .await
+}
+
+// We expect to see lower memory thresholds in general when applying a `LIMIT` clause due to eager sorting
+#[rstest]
+#[case::cant_grow_reservation(vec!["Resources exhausted: Failed to allocate additional", "ExternalSorter"], 20_000)]
+#[case::cant_spill_to_disk(vec!["Memory Exhausted while Sorting (DiskManager is disabled)"], 40_000)]
+//#[case::no_oom(vec![], 80_000)]

Review Comment:
   I don't quite understand why atm, but this test case now fails. In fact, the no-oom threshold is like 10 times that value which is even weirder. I did double-check with bytehound and the memory profiles are still looking good outside of this test. Will need to think about it.



-- 
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


[GitHub] [arrow-datafusion] yjshen commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "yjshen (via GitHub)" <gi...@apache.org>.
yjshen commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1286420913


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -639,15 +614,47 @@ fn write_sorted(
     Ok(())
 }
 
-fn read_spill(sender: Sender<Result<RecordBatch>>, path: &Path) -> Result<()> {
+/// Stream batches from spill files.
+///
+/// Each spill file has one or more batches. Intra-batch order is guaranteed (each one is sorted),
+/// but the inter-batch ordering is not guaranteed, hence why we need to convert each batch from the
+/// spill to a separate input stream for the merge-sort procedure.

Review Comment:
   Will this produce unnecessary comparison when the inter-batch ordering in spillfiles are guaranteed for the normal case without `K`?
   



-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager external sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1285109657


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +251,27 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter; first perform a memory reservation
+            // for the sorting procedure.
+            let mut reservation =

Review Comment:
   So I went ahead to add this, but then it seemed to me that the logic of `split` (and `take` by extension) is backwards (for this case at least)? In particular, the `size` of the reservation is not _free_ memory, but instead _used_ memory, right? And with `split` we'd effectively deduct some piece of memory in our accounting that was previously allocated (without actually freeing that memory). 
   
   Atm I went with skipping reservation updates at all in this case; the reason being that we're already holding the input batch in memory and we're are about to (try to) allocate memory for it right after sorting it anyway. Hence, the sole purpose of that reservation seems to be to account for that extra piece of memory due to non-in-place sorting (i.e. having the old and the new bath present at the same time briefly), and that piece of memory is guaranteed to be less than the batch size. Let me know if you'd like me to do something else.
   
   I also changed that tests output. Now all tests should be passing, so it's probably time for the regular benchmarks.



-- 
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


[GitHub] [arrow-datafusion] yjshen commented on pull request #7180: Top-K eager batch sorting

Posted by "yjshen (via GitHub)" <gi...@apache.org>.
yjshen commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1667044811

   Would it be possible to compare the sorting performance of this pull request with the main branch by modifying the test sets in the description of [#6163](https://github.com/apache/arrow-datafusion/pull/6163) with different values of `K`? 
   
   I am interested in these tests because we are reintroducing per-batch sorting (for TopK), which was noted as a source of inefficiency in https://github.com/apache/arrow-datafusion/pull/6163#issuecomment-1529002495:
   > The cost of sorting and copying all the values an additional time far outweighs any cache locality effects.
   
   By analyzing the results of the suggested tests, we can determine whether we need to implement simple heuristics to determine when to use eager sorting (if `K` is similar to `batch_size`) or if the performance improvement in #6163 is mainly due to the adaptive sorting algorithm over index-based sorting, and thus eager sorting will not cause performance regression.
   
   


-- 
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


[GitHub] [arrow-datafusion] alamb commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1286384488


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -465,16 +484,23 @@ impl ExternalSorter {
         // This is a very rough heuristic and likely could be refined further
         if self.reservation.size() < 1048576 {
             // Concatenate memory batches together and sort
-            let batch = concat_batches(&self.schema, &self.in_mem_batches)?;
+            let (_, batches): (Vec<bool>, Vec<RecordBatch>) =
+                std::mem::take(&mut self.in_mem_batches).into_iter().unzip();
+            let batch = concat_batches(&self.schema, &batches)?;
             self.in_mem_batches.clear();
-            return self.sort_batch_stream(batch, metrics);
+            // Even if all individual batches were themselves sorted the resulting concatenated one
+            // isn't guaranteed to be sorted, so we must perform sorting on the stream.
+            return self.sort_batch_stream(batch, false, metrics);

Review Comment:
   Another approach might be be to not use the `concat` in place heuristic if there are any previously sorted batches -- now the code only checks for the overall size less than 1MB -- it could also check if there was any true in `in_mem_batches` and if there are use the merge path below



-- 
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


[GitHub] [arrow-datafusion] gruuya commented on pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1670296640

   Alright, @alamb @yjshen, this is probably the final, best-effort, attempt so far, with the simplest implementation. 
   
   I've set a hard cut-off for eager sorting at 100 rows so that the pronounced regressions for bigger fetches are avoided (at least for the 1.0 scale factor in the benchmarks). It also happens that most of the memory savings occur for K <= 100, in addition to probably 80% of usages in practice falling into that range.
    <details><summary>sorting benchmarks</summary>
     
     ```text
   ┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
   ┃ Query        ┃       main ┃ top-k-eager-sorting ┃        Change ┃
   ┑━━━━━━━━━━━━━━╇━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
   β”‚ Qsort utf8   β”‚ 28233.61ms β”‚          29131.55ms β”‚     no change β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚ 36739.73ms β”‚          37069.77ms β”‚     no change β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚ 29974.54ms β”‚          30505.64ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚ 40214.81ms β”‚          40837.69ms β”‚     no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ None         β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚ 29429.65ms β”‚          29552.35ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ None         β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚ 34435.12ms β”‚          34964.91ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ None         β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1709.85ms β”‚           1813.60ms β”‚  1.06x slower β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1842.45ms β”‚           1734.15ms β”‚ +1.06x faster β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1680.46ms β”‚           1669.21ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1745.56ms β”‚           1869.70ms β”‚  1.07x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1965.73ms β”‚           2339.40ms β”‚  1.19x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  1813.14ms β”‚           2046.39ms β”‚  1.13x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1712.66ms β”‚           1823.54ms β”‚  1.06x slower β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1832.73ms β”‚           1738.45ms β”‚ +1.05x faster β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1699.42ms β”‚           1662.90ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1762.86ms β”‚           1855.61ms β”‚  1.05x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1974.07ms β”‚           2323.84ms β”‚  1.18x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  1854.64ms β”‚           2025.10ms β”‚  1.09x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1733.28ms β”‚           1834.81ms β”‚  1.06x slower β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1845.74ms β”‚           1751.06ms β”‚ +1.05x faster β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1685.38ms β”‚           1680.20ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1799.54ms β”‚           1911.41ms β”‚  1.06x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  2008.06ms β”‚           2368.46ms β”‚  1.18x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  1855.62ms β”‚           2085.46ms β”‚  1.12x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1728.54ms β”‚           1728.53ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1867.64ms β”‚           1865.83ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1691.19ms β”‚           1693.69ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1784.79ms β”‚           1801.06ms β”‚     no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1999.16ms β”‚           2000.34ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  1869.82ms β”‚           1877.08ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1774.79ms β”‚           1786.39ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1959.51ms β”‚           1933.94ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1714.06ms β”‚           1715.05ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1940.85ms β”‚           1943.97ms β”‚     no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  2103.61ms β”‚           2108.73ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  2032.56ms β”‚           2060.30ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜
   ```
   </details>
   
   Still not sure whether this is merge-worthy, but seems like the best trade-off between run-times and memory profiles so far.


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1667281048

   > How about K slightly smaller than the batch size? Say K=8000 when batch size=8192.
   
   Sorry didn't see this comment in time, maybe I could add that case later on.
   
   Anyway I've got some preliminary results and they're not very promising (if there's a change it's non-insignificant slowdown)
   ```text
   ┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━┓
   ┃ Query        ┃       main ┃ top-k-eager-sorting ┃       Change ┃
   ┑━━━━━━━━━━━━━━╇━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━┩
   β”‚ Qsort utf8   β”‚ 35484.89ms β”‚          37195.91ms β”‚    no change β”‚
   β”‚ with fetch   β”‚            β”‚                     β”‚              β”‚
   β”‚ None         β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort int    β”‚ 46779.63ms β”‚          46817.47ms β”‚    no change β”‚
   β”‚ with fetch   β”‚            β”‚                     β”‚              β”‚
   β”‚ None         β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort        β”‚ 36037.43ms β”‚          36471.88ms β”‚    no change β”‚
   β”‚ decimal with β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort        β”‚ 51767.49ms β”‚          52308.29ms β”‚    no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚              β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort utf8   β”‚ 35248.66ms β”‚          35866.21ms β”‚    no change β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort mixed  β”‚ 41124.15ms β”‚          42406.47ms β”‚    no change β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort utf8   β”‚  1894.58ms β”‚           2081.23ms β”‚ 1.10x slower β”‚
   β”‚ with fetch   β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort int    β”‚  1995.16ms β”‚           1992.60ms β”‚    no change β”‚
   β”‚ with fetch   β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort        β”‚  1811.48ms β”‚           1924.61ms β”‚ 1.06x slower β”‚
   β”‚ decimal with β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort        β”‚  1873.19ms β”‚           2138.09ms β”‚ 1.14x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚              β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort utf8   β”‚  2106.81ms β”‚           2584.92ms β”‚ 1.23x slower β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort mixed  β”‚  1948.55ms β”‚           2304.72ms β”‚ 1.18x slower β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort utf8   β”‚  1841.42ms β”‚           2084.12ms β”‚ 1.13x slower β”‚
   β”‚ with fetch   β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort int    β”‚  1967.58ms β”‚           1994.95ms β”‚    no change β”‚
   β”‚ with fetch   β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort        β”‚  1811.81ms β”‚           1906.41ms β”‚ 1.05x slower β”‚
   β”‚ decimal with β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort        β”‚  1902.72ms β”‚           2107.02ms β”‚ 1.11x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚              β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort utf8   β”‚  2096.74ms β”‚           2567.12ms β”‚ 1.22x slower β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort mixed  β”‚  1983.58ms β”‚           2285.19ms β”‚ 1.15x slower β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort utf8   β”‚  1860.15ms β”‚           2098.58ms β”‚ 1.13x slower β”‚
   β”‚ with fetch   β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort int    β”‚  2017.14ms β”‚           2018.33ms β”‚    no change β”‚
   β”‚ with fetch   β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort        β”‚  1831.45ms β”‚           1980.09ms β”‚ 1.08x slower β”‚
   β”‚ decimal with β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort        β”‚  1933.97ms β”‚           2171.31ms β”‚ 1.12x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚              β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort utf8   β”‚  2155.04ms β”‚           2657.61ms β”‚ 1.23x slower β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort mixed  β”‚  2028.39ms β”‚           2365.85ms β”‚ 1.17x slower β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort utf8   β”‚  1970.11ms β”‚           2160.91ms β”‚ 1.10x slower β”‚
   β”‚ with fetch   β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort int    β”‚  2142.49ms β”‚           2123.38ms β”‚    no change β”‚
   β”‚ with fetch   β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort        β”‚  1891.53ms β”‚           2007.44ms β”‚ 1.06x slower β”‚
   β”‚ decimal with β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort        β”‚  2089.55ms β”‚           2424.50ms β”‚ 1.16x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚              β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort utf8   β”‚  2251.87ms β”‚           2860.59ms β”‚ 1.27x slower β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort mixed  β”‚  2215.35ms β”‚           2739.82ms β”‚ 1.24x slower β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort utf8   β”‚  2273.12ms β”‚           2440.54ms β”‚ 1.07x slower β”‚
   β”‚ with fetch   β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(10000)  β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort int    β”‚  2352.27ms β”‚           2540.47ms β”‚ 1.08x slower β”‚
   β”‚ with fetch   β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(10000)  β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort        β”‚  2062.62ms β”‚           2255.48ms β”‚ 1.09x slower β”‚
   β”‚ decimal with β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(10000)  β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort        β”‚  2741.88ms β”‚           2937.61ms β”‚ 1.07x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚              β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(10000)  β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort utf8   β”‚  2554.86ms β”‚           2733.78ms β”‚ 1.07x slower β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(10000)  β”‚            β”‚                     β”‚              β”‚
   β”‚ Qsort mixed  β”‚  3408.55ms β”‚           3589.02ms β”‚ 1.05x slower β”‚
   β”‚ tuple with   β”‚            β”‚                     β”‚              β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚              β”‚
   β”‚ Some(10000)  β”‚            β”‚                     β”‚              β”‚
   β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜
   ```
   
   Strangely I see slowdown even for base cases when eager sorting does not apply. I'll need to think about it a bit.


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1672741025

   Glad to hear that @alamb! 
   
   I think we can close this PR now as it seems it's obsolete (as well as too verbose at this point), and continue discussion in a dedicated issue/PR for a native Top-K operator.


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on pull request #7180: Top-K eager external sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1664209600

   I consolidated/extended the fuzz tests; I've ran into one more edge case while doing that: https://github.com/apache/arrow-datafusion/pull/7180/commits/ca0786f181c67b53bd55934d7bf0ba8ecfd54976#diff-c0e76bbcb3ed7bfbba2f99fedfdab7ebb9200746a835db51619a6b10e3e2adcfR255-R262
   
   This might have some runtime implications on it's own, so it will be worthwhile to double check the benchmarks afterwards (i.e. once I resolve the other failing test). It could also be that there is a more elegant way of solving that.
   
   


-- 
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


[GitHub] [arrow-datafusion] alamb commented on a diff in pull request #7180: Top-K eager external sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1284769893


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +251,27 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter; first perform a memory reservation
+            // for the sorting procedure.
+            let mut reservation =

Review Comment:
   I don't think we need a new consumer here for each batch insertion -- we could just update the main reservation on `self.reservation`
   
   So something like do the sort and then update the size on limit
   ```
               input = sort_batch(&input, &self.expr, self.fetch)?;
               reservation.try_grow(input.get_array_memory_size());
   ```
   
   
   Note the accounting is reworked in https://github.com/apache/arrow-datafusion/pull/7130 



##########
datafusion/core/tests/fuzz_cases/order_spill_fuzz.rs:
##########
@@ -30,76 +30,85 @@ use datafusion::physical_plan::sorts::sort::SortExec;
 use datafusion::physical_plan::{collect, ExecutionPlan};
 use datafusion::prelude::{SessionConfig, SessionContext};
 use rand::Rng;
+use rstest::rstest;
 use std::sync::Arc;
 use test_utils::{batches_to_vec, partitions_to_sorted_vec};
 
-#[tokio::test]
-#[cfg_attr(tarpaulin, ignore)]
-async fn test_sort_1k_mem() {
-    run_sort(10240, vec![(5, false), (20000, true), (1000000, true)]).await
-}
-
-#[tokio::test]
-#[cfg_attr(tarpaulin, ignore)]
-async fn test_sort_100k_mem() {
-    run_sort(102400, vec![(5, false), (20000, false), (1000000, true)]).await
-}
-
-#[tokio::test]
-async fn test_sort_unlimited_mem() {
-    run_sort(
-        usize::MAX,
-        vec![(5, false), (2000, false), (1000000, false)],
-    )
-    .await
-}
-
 /// Sort the input using SortExec and ensure the results are correct according to `Vec::sort`
-async fn run_sort(pool_size: usize, size_spill: Vec<(usize, bool)>) {
-    for (size, spill) in size_spill {
-        let input = vec![make_staggered_batches(size)];
-        let first_batch = input
-            .iter()
-            .flat_map(|p| p.iter())
-            .next()
-            .expect("at least one batch");
-        let schema = first_batch.schema();
-
-        let sort = vec![PhysicalSortExpr {
-            expr: col("x", &schema).unwrap(),
-            options: SortOptions {
-                descending: false,
-                nulls_first: true,
-            },
-        }];
-
-        let exec = MemoryExec::try_new(&input, schema, None).unwrap();
-        let sort = Arc::new(SortExec::new(sort, Arc::new(exec)));
-
-        let runtime_config = RuntimeConfig::new()
-            .with_memory_pool(Arc::new(GreedyMemoryPool::new(pool_size)));
-        let runtime = Arc::new(RuntimeEnv::new(runtime_config).unwrap());
-        let session_ctx = SessionContext::with_config_rt(SessionConfig::new(), runtime);
-
-        let task_ctx = session_ctx.task_ctx();
-        let collected = collect(sort.clone(), task_ctx).await.unwrap();
-
-        let expected = partitions_to_sorted_vec(&input);
-        let actual = batches_to_vec(&collected);
-
-        if spill {
-            assert_ne!(sort.metrics().unwrap().spill_count().unwrap(), 0);
-        } else {
-            assert_eq!(sort.metrics().unwrap().spill_count().unwrap(), 0);
-        }
+#[rstest]

Review Comment:
   ❀️ 



##########
datafusion/core/tests/memory_limit.rs:
##########
@@ -45,17 +47,38 @@ fn init() {
     let _ = env_logger::try_init();
 }
 
+#[rstest]
+#[case::cant_grow_reservation(vec!["Resources exhausted: Failed to allocate additional", "ExternalSorter"], 100_000)]
+#[case::cant_spill_to_disk(vec!["Resources exhausted: Memory Exhausted while Sorting (DiskManager is disabled)"], 200_000)]
+#[case::no_oom(vec![], 600_000)]
 #[tokio::test]
-async fn oom_sort() {
+async fn sort(#[case] expected_errors: Vec<&str>, #[case] memory_limit: usize) {
     TestCase::new(
         "select * from t order by host DESC",
-        vec![
-            "Resources exhausted: Memory Exhausted while Sorting (DiskManager is disabled)",
-        ],
-        200_000,
+        expected_errors,
+        memory_limit,
+    )
+    .run()
+    .await
+}
+
+// We expect to see lower memory thresholds in general when applying a `LIMIT` clause due to eager sorting

Review Comment:
   this is nice



##########
datafusion/core/tests/fuzz_cases/order_spill_fuzz.rs:
##########
@@ -30,76 +30,85 @@ use datafusion::physical_plan::sorts::sort::SortExec;
 use datafusion::physical_plan::{collect, ExecutionPlan};
 use datafusion::prelude::{SessionConfig, SessionContext};
 use rand::Rng;
+use rstest::rstest;
 use std::sync::Arc;
 use test_utils::{batches_to_vec, partitions_to_sorted_vec};
 
-#[tokio::test]
-#[cfg_attr(tarpaulin, ignore)]
-async fn test_sort_1k_mem() {
-    run_sort(10240, vec![(5, false), (20000, true), (1000000, true)]).await
-}
-
-#[tokio::test]
-#[cfg_attr(tarpaulin, ignore)]
-async fn test_sort_100k_mem() {
-    run_sort(102400, vec![(5, false), (20000, false), (1000000, true)]).await
-}
-
-#[tokio::test]
-async fn test_sort_unlimited_mem() {
-    run_sort(
-        usize::MAX,
-        vec![(5, false), (2000, false), (1000000, false)],
-    )
-    .await
-}
-
 /// Sort the input using SortExec and ensure the results are correct according to `Vec::sort`
-async fn run_sort(pool_size: usize, size_spill: Vec<(usize, bool)>) {
-    for (size, spill) in size_spill {
-        let input = vec![make_staggered_batches(size)];
-        let first_batch = input
-            .iter()
-            .flat_map(|p| p.iter())
-            .next()
-            .expect("at least one batch");
-        let schema = first_batch.schema();
-
-        let sort = vec![PhysicalSortExpr {
-            expr: col("x", &schema).unwrap(),
-            options: SortOptions {
-                descending: false,
-                nulls_first: true,
-            },
-        }];
-
-        let exec = MemoryExec::try_new(&input, schema, None).unwrap();
-        let sort = Arc::new(SortExec::new(sort, Arc::new(exec)));
-
-        let runtime_config = RuntimeConfig::new()
-            .with_memory_pool(Arc::new(GreedyMemoryPool::new(pool_size)));
-        let runtime = Arc::new(RuntimeEnv::new(runtime_config).unwrap());
-        let session_ctx = SessionContext::with_config_rt(SessionConfig::new(), runtime);
-
-        let task_ctx = session_ctx.task_ctx();
-        let collected = collect(sort.clone(), task_ctx).await.unwrap();
-
-        let expected = partitions_to_sorted_vec(&input);
-        let actual = batches_to_vec(&collected);
-
-        if spill {
-            assert_ne!(sort.metrics().unwrap().spill_count().unwrap(), 0);
-        } else {
-            assert_eq!(sort.metrics().unwrap().spill_count().unwrap(), 0);
-        }
+#[rstest]

Review 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


[GitHub] [arrow-datafusion] gruuya commented on pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1675215624

   > @gruuya perhaps you could test your example query with #7250 and see if it helps your usecase too?
   
   Oh, I'd love to! I'll report back to that PR when I get some numbers.


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1285109657


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +251,27 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter; first perform a memory reservation
+            // for the sorting procedure.
+            let mut reservation =

Review Comment:
   Hmm, so I went ahead to add this, but then it seemed to me that the logic of `split` (and `take` by extension) is backwards (for this case at least)? In particular, the `size` of the reservation is not _free_ memory, but instead _used_ memory, right? And with `split` we'd effectively deduct some piece of memory in our accounting that was previously allocated (without actually freeing that memory). 
   
   Atm I went with skipping reservation updates at all in this case; the reason being that we're already holding the input batch in memory and we're are about to (try to) allocate memory for it right after sorting it anyway. Hence, the sole purpose of that reservation seems to be to account for that extra piece of memory due to non-in-place sorting (i.e. having the old and the new bath present at the same time briefly), and that piece of memory is guaranteed to be less than the batch size. Let me know if you'd like me to do something else.
   
   I also changed that tests output. Now all tests should be passing, so it's probably time for the regular benchmarks.



##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -253,11 +251,27 @@ impl ExternalSorter {
     /// Appends an unsorted [`RecordBatch`] to `in_mem_batches`
     ///
     /// Updates memory usage metrics, and possibly triggers spilling to disk
-    async fn insert_batch(&mut self, input: RecordBatch) -> Result<()> {
+    async fn insert_batch(&mut self, mut input: RecordBatch) -> Result<()> {
         if input.num_rows() == 0 {
             return Ok(());
         }
 
+        let mut batch_sorted = false;
+        if self.fetch.map_or(false, |f| f < input.num_rows()) {
+            // Eagerly sort the batch to potentially reduce the number of rows
+            // after applying the fetch parameter; first perform a memory reservation
+            // for the sorting procedure.
+            let mut reservation =

Review Comment:
   Hmm, so I went ahead to add this, but then it seemed to me that the logic of `split` is backwards (for this case at least)? In particular, the `size` of the reservation is not _free_ memory, but instead _used_ memory, right? And with `split` we'd effectively deduct some piece of memory in our accounting that was previously allocated (without actually freeing that memory). 
   
   Atm I went with skipping reservation updates at all in this case; the reason being that we're already holding the input batch in memory and we're are about to (try to) allocate memory for it right after sorting it anyway. Hence, the sole purpose of that reservation seems to be to account for that extra piece of memory due to non-in-place sorting (i.e. having the old and the new bath present at the same time briefly), and that piece of memory is guaranteed to be less than the batch size. Let me know if you'd like me to do something else.
   
   I also changed that tests output. Now all tests should be passing, so it's probably time for the regular benchmarks.



-- 
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


[GitHub] [arrow-datafusion] gruuya commented on pull request #7180: Top-K eager external sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1666163172

   > If you are saying there are more than 5 values with the same value of c5 then I think technically the query produces non specified answers and thus I think we should change the test to be deterministic -- perhaps we can increase the LIMIT to include all the first values of c3
   
   Oh actually I meant that there are only 2 identical values for the sorting column (C3) which end up in the top-5 according to the test query, but their order is unstable when using a `LIMIT` as opposed to without it:
   ```sql
   ❯ SELECT
     MAX(c12) OVER window1,
     MIN(c12) OVER window2 as max1,
     C3
     FROM aggregate_test_100
     WINDOW window1 AS (ORDER BY C12),
     window2 AS (PARTITION BY C11),
     window3 AS (ORDER BY C1)
     ORDER BY C3;
   +--------------------------------------------------------------------------------------------------------------------------------+----------------------+------+
   | MAX(aggregate_test_100.c12) ORDER BY [aggregate_test_100.c12 ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW | max1                 | c3   |
   +--------------------------------------------------------------------------------------------------------------------------------+----------------------+------+
   | 0.9706712283358269                                                                                                             | 0.9706712283358269   | -117 |
   | 0.8506721053047003                                                                                                             | 0.8506721053047003   | -117 |
   | 0.152498292971736                                                                                                              | 0.152498292971736    | -111 |
   | 0.36936304600612724                                                                                                            | 0.36936304600612724  | -107 |
   | 0.565352842229935                                                                                                              | 0.565352842229935    | -106 |
   ...
   | 0.7631239070049998                                                                                                             | 0.7631239070049998   | 125  |
   +--------------------------------------------------------------------------------------------------------------------------------+----------------------+------+
   100 rows in set. Query took 0.154 seconds.
   
   ❯ SELECT
     MAX(c12) OVER window1,
     MIN(c12) OVER window2 as max1,
     C3
     FROM aggregate_test_100
     WINDOW window1 AS (ORDER BY C12),
     window2 AS (PARTITION BY C11),
     window3 AS (ORDER BY C1)
     ORDER BY C3
     LIMIT 5;
   +--------------------------------------------------------------------------------------------------------------------------------+---------------------+------+
   | MAX(aggregate_test_100.c12) ORDER BY [aggregate_test_100.c12 ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW | max1                | c3   |
   +--------------------------------------------------------------------------------------------------------------------------------+---------------------+------+
   | 0.8506721053047003                                                                                                             | 0.8506721053047003  | -117 |
   | 0.9706712283358269                                                                                                             | 0.9706712283358269  | -117 |
   | 0.152498292971736                                                                                                              | 0.152498292971736   | -111 |
   | 0.36936304600612724                                                                                                            | 0.36936304600612724 | -107 |
   | 0.565352842229935                                                                                                              | 0.565352842229935   | -106 |
   +--------------------------------------------------------------------------------------------------------------------------------+---------------------+------+
   5 rows in set. Query took 0.042 seconds.
   ```
   
   (Note that I've included the C3 column for clarity.)


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on pull request #7180: Top-K eager external sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1663961615

   > I also was thinking we can probably write a test for this behavior in https://github.com/apache/arrow-datafusion/blob/main/datafusion/core/tests/memory_limit.rs
   > 
   > I have something similar in [#7130 (review)](https://github.com/apache/arrow-datafusion/pull/7130#pullrequestreview-1559634018)
   > 
   > I can potentially help writing that test if you agree it would be helpful
   
   Thanks, I certainly planned on adding tests, just wanted to concentrate on the benchmarks first. I'm thinking of starting with `order_spill_fuzz.rs` file for starters, extend the cases for some limit numbers, then if it's needed I can extend https://github.com/apache/arrow-datafusion/blob/main/datafusion/core/tests/memory_limit.rs as well.
   
   Incidentally, there's a [failing test](https://github.com/apache/arrow-datafusion/actions/runs/5749956405/job/15586047326?pr=7180#step:6:2884) now, which I've been looking at and it's a bit curiousβ€”the difference comes down to the fact that previously processed batch size was a bit different (due to the fetch) and the intermediate sort call was stable (i.e. preserved order), while currently it's unstable (didn't preserve order).
   
   To be more specific, in this particular [test](https://github.com/apache/arrow-datafusion/blob/main/datafusion/core/tests/sqllogictests/test_files/window.slt#L3198-L3215) there are always 2 input batches (I've added the column C3 for more clarity).
   One with 99 rows
   ```rust
   [
       "+--------------------------------------------------------------------------------------------------------------------------------+----------------------+------+",
       "| MAX(aggregate_test_100.c12) ORDER BY [aggregate_test_100.c12 ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW | max1                 | c3   |",
       "+--------------------------------------------------------------------------------------------------------------------------------+----------------------+------+",
       "| 0.01479305307777301                                                                                                            | 0.01479305307777301  | -86  |",
       "| 0.02182578039211991                                                                                                            | 0.02182578039211991  | -38  |",
       "| 0.03968347085780355                                                                                                            | 0.03968347085780355  | 30   |",
       "| 0.04429073092078406                                                                                                            | 0.04429073092078406  | 36   |",
       "| 0.047343434291126085                                                                                                           | 0.047343434291126085 | -95  |",
       ...
       "| 0.980809631269599                                                                                                              | 0.980809631269599    | 52   |",
       "| 0.991517828651004                                                                                                              | 0.991517828651004    | 29   |",
       "+--------------------------------------------------------------------------------------------------------------------------------+----------------------+------+",
   ]
   ```
   and one with 1 row:
   ```rust
   [
       "+--------------------------------------------------------------------------------------------------------------------------------+--------------------+-----+",
       "| MAX(aggregate_test_100.c12) ORDER BY [aggregate_test_100.c12 ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW | max1               | c3  |",
       "+--------------------------------------------------------------------------------------------------------------------------------+--------------------+-----+",
       "| 0.9965400387585364                                                                                                             | 0.9965400387585364 | 120 |",
       "+--------------------------------------------------------------------------------------------------------------------------------+--------------------+-----+",
   ]
   ```
   In the case of this PR the first batch is sorted to:
   ```rust
   [
       "+--------------------------------------------------------------------------------------------------------------------------------+---------------------+------+",
       "| MAX(aggregate_test_100.c12) ORDER BY [aggregate_test_100.c12 ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW | max1                | c3   |",
       "+--------------------------------------------------------------------------------------------------------------------------------+---------------------+------+",
       "| 0.8506721053047003                                                                                                             | 0.8506721053047003  | -117 |",
       "| 0.9706712283358269                                                                                                             | 0.9706712283358269  | -117 |",
       "| 0.152498292971736                                                                                                              | 0.152498292971736   | -111 |",
       "| 0.36936304600612724                                                                                                            | 0.36936304600612724 | -107 |",
       "| 0.565352842229935                                                                                                              | 0.565352842229935   | -106 |",
       "+--------------------------------------------------------------------------------------------------------------------------------+---------------------+------+",
   ]
   ```
   I.e. without preserving the order for the same C3
   On main this isn't manifested since the two batches get concatenated into a batch with 100 rows and the sorting of that batch turns out to be stable for some reason:
   ```rust
   [
       "+--------------------------------------------------------------------------------------------------------------------------------+---------------------+------+",
       "| MAX(aggregate_test_100.c12) ORDER BY [aggregate_test_100.c12 ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW | max1                | c3   |",
       "+--------------------------------------------------------------------------------------------------------------------------------+---------------------+------+",
       "| 0.9706712283358269                                                                                                             | 0.9706712283358269  | -117 |",
       "| 0.8506721053047003                                                                                                             | 0.8506721053047003  | -117 |",
       "| 0.152498292971736                                                                                                              | 0.152498292971736   | -111 |",
       "| 0.36936304600612724                                                                                                            | 0.36936304600612724 | -107 |",
       "| 0.565352842229935                                                                                                              | 0.565352842229935   | -106 |",
       "+--------------------------------------------------------------------------------------------------------------------------------+---------------------+------+",
   ]
   ```
   
   Still need to look into this a bit more.


-- 
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


[GitHub] [arrow-datafusion] alamb commented on pull request #7180: Top-K eager batch sorting

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1675055983

   BTW I think  https://github.com/apache/arrow-datafusion/pull/7250 is ready for some feedback -- it seems to work quite well, both with memory consumed as well as performance wise.
   
   @gruuya  perhaps you could test your example query with https://github.com/apache/arrow-datafusion/pull/7250 and see if it helps your usecase too?


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on pull request #7180: Top-K eager external sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1665730913

   Fwiw, I was able to narrow down the reason why that [last test is failing](https://github.com/apache/arrow-datafusion/actions/runs/5762302725/job/15622067686?pr=7180#step:6:2911); TLDR: unstable sort and changed batch sizes result in different order of items with the same value in the sort column between main and this PR.
   
   ## Details
   
   The repro involves an array 1 with 100 elements (this is basically column C3 from the [test file](https://github.com/apache/arrow-testing/blob/e81d0c6de35948b3be7984af8e00413b314cde6e/data/csv/aggregate_test_100.csv)) and array 2 with all elements from array 1 except one (which doesn't affect the output, namely 120)
   ```rust
   use arrow::compute::SortOptions;
   use arrow::compute::{lexsort_to_indices, SortColumn};
   use arrow_array::{ArrayRef, Int32Array};
   let options = SortOptions {
       descending: false,
       nulls_first: false,
   };
   let get_indices = |sort_column: SortColumn, fetch: Option<usize>| -> Vec<u32> {
       lexsort_to_indices(&vec![sort_column], fetch)
           .unwrap()
           .into_iter()
           .map(|maybe_index| maybe_index.unwrap_or_else(|| panic!("No index!")))
           .collect::<Vec<u32>>()
   };
   let array_1: ArrayRef = Arc::new(Int32Array::from(vec![
       1, -40, 29, -85, -82, -111, 104, 13, 38, -38, 57, -54, 112, 113, 54, 103, 49,
       -98, 77, 97, -56, -99, 36, -53, -29, -25, 123, -31, 45, 17, 97, -60, 36, -5,
       13, 41, 93, 73, -2, 22, 63, 102, -8, 17, 52, 68, 31, -24, 65, 125, 17, -106,
       -59, 55, -60, -76, 73, -117, -101, 62, -79, 68, 70, -61, 74, 122, 71, -94,
       -72, 71, 96, -48, -56, 52, -5, 12, 64, -90, -86, -117, 14, 29, -59, 83, -12,
       3, -72, -107, 118, 97, -101, -43, -101, -44, 5, 120, -95, 123, 47, 30,
   ]));
   let sort_column_1 = SortColumn {
       values: array_1,
       options: Some(options.clone()),
   };
   let indices_1_no_fetch = get_indices(sort_column_1.clone(), None);
   let indices_1_fetch_5 = get_indices(sort_column_1, Some(5));
   println!("Indices for sorting array 1");
   println!("{:#?}", indices_1_no_fetch[0..5].to_vec());
   println!("{:#?}", indices_1_fetch_5);
   
   let array_2: ArrayRef = Arc::new(Int32Array::from(vec![
       1, -40, 29, -85, -82, -111, 104, 13, 38, -38, 57, -54, 112, 113, 54, 103, 49,
       -98, 77, 97, -56, -99, 36, -53, -29, -25, 123, -31, 45, 17, 97, -60, 36, -5,
       13, 41, 93, 73, -2, 22, 63, 102, -8, 17, 52, 68, 31, -24, 65, 125, 17, -106,
       -59, 55, -60, -76, 73, -117, -101, 62, -79, 68, 70, -61, 74, 122, 71, -94,
       -72, 71, 96, -48, -56, 52, -5, 12, 64, -90, -86, -117, 14, 29, -59, 83, -12,
       3, -72, -107, 118, 97, -101, -43, -101, -44, 5, -95, 123, 47, 30,
   ]));
   let sort_column_2 = SortColumn {
       values: array_2,
       options: Some(options),
   };
   let indices_2_no_fetch = get_indices(sort_column_2.clone(), None);
   let indices_2_fetch_5 = get_indices(sort_column_2, Some(5));
   println!("Indices for sorting array 2");
   println!("{:#?}", indices_2_no_fetch[0..5].to_vec());
   println!("{:#?}", indices_2_fetch_5);
   ```
   
   This prints out:
   ```text
   Indices for sorting array 1
   [
       57,
       79,
       5,
       87,
       51,
   ]
   [
       57,
       79,
       5,
       87,
       51,
   ]
   Indices for sorting array 2
   [
       57,
       79,
       5,
       87,
       51,
   ]
   [
       79,
       57,
       5,
       87,
       51,
   ]
   ```
   Note that in the case of the second array the first two indices are swapped when setting some fetch size, as then the [unstable sort](https://github.com/apache/arrow-rs/blob/master/arrow-ord/src/sort.rs#L711) gets used, and the two smallest array values are the same (-117).
   
   ##
   
   Perhaps it's ok to change the test output to match the one being obtained now?


-- 
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


[GitHub] [arrow-datafusion] gruuya commented on a diff in pull request #7180: Top-K eager batch sorting

Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on code in PR #7180:
URL: https://github.com/apache/arrow-datafusion/pull/7180#discussion_r1287280089


##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -639,15 +614,47 @@ fn write_sorted(
     Ok(())
 }
 
-fn read_spill(sender: Sender<Result<RecordBatch>>, path: &Path) -> Result<()> {
+/// Stream batches from spill files.
+///
+/// Each spill file has one or more batches. Intra-batch order is guaranteed (each one is sorted),
+/// but the inter-batch ordering is not guaranteed, hence why we need to convert each batch from the
+/// spill to a separate input stream for the merge-sort procedure.

Review Comment:
   Fwiw, I did revise the approach to stream the entire spill in one stream when inter-batch order is guaranteed (which involved keeping track of this as well). I also added the hard cut-off for eager batching to 100 rows.
   
    <details><summary>sorting benchmarks</summary>
     
     ```text
   ┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
   ┃ Query        ┃       main ┃ top-k-eager-sorting ┃        Change ┃
   ┑━━━━━━━━━━━━━━╇━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
   β”‚ Qsort utf8   β”‚ 28233.61ms β”‚          29251.16ms β”‚     no change β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚ 36739.73ms β”‚          36870.39ms β”‚     no change β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚ 29974.54ms β”‚          30480.98ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚ 40214.81ms β”‚          40804.29ms β”‚     no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ None         β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚ 29429.65ms β”‚          29875.64ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ None         β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚ 34435.12ms β”‚          34415.10ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ None         β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1709.85ms β”‚           1829.22ms β”‚  1.07x slower β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1842.45ms β”‚           1749.96ms β”‚ +1.05x faster β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1680.46ms β”‚           1677.47ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1745.56ms β”‚           1871.46ms β”‚  1.07x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1965.73ms β”‚           2331.78ms β”‚  1.19x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  1813.14ms β”‚           2061.60ms β”‚  1.14x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1712.66ms β”‚           1829.49ms β”‚  1.07x slower β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1832.73ms β”‚           1759.00ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1699.42ms β”‚           1686.28ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1762.86ms β”‚           1877.71ms β”‚  1.07x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1974.07ms β”‚           2337.96ms β”‚  1.18x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  1854.64ms β”‚           2078.75ms β”‚  1.12x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1733.28ms β”‚           1853.74ms β”‚  1.07x slower β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1845.74ms β”‚           1797.14ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1685.38ms β”‚           1712.97ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1799.54ms β”‚           1907.62ms β”‚  1.06x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  2008.06ms β”‚           2371.06ms β”‚  1.18x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  1855.62ms β”‚           2110.55ms β”‚  1.14x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1728.54ms β”‚           1760.71ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1867.64ms β”‚           1902.02ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1691.19ms β”‚           1708.74ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1784.79ms β”‚           1830.82ms β”‚     no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1999.16ms β”‚           2034.22ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  1869.82ms β”‚           1914.20ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1774.79ms β”‚           1814.19ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1959.51ms β”‚           1999.51ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1714.06ms β”‚           1730.36ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1940.85ms β”‚           1969.82ms β”‚     no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  2103.61ms β”‚           2132.59ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  2032.56ms β”‚           2087.27ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜
   ```
   </details>
   
   Overall the times are not that impressive, and the implementation is quite convoluted at this point, so I wouldn't merge this either.



##########
datafusion/core/src/physical_plan/sorts/sort.rs:
##########
@@ -639,15 +614,47 @@ fn write_sorted(
     Ok(())
 }
 
-fn read_spill(sender: Sender<Result<RecordBatch>>, path: &Path) -> Result<()> {
+/// Stream batches from spill files.
+///
+/// Each spill file has one or more batches. Intra-batch order is guaranteed (each one is sorted),
+/// but the inter-batch ordering is not guaranteed, hence why we need to convert each batch from the
+/// spill to a separate input stream for the merge-sort procedure.

Review Comment:
   Fwiw, I did revise the approach to stream the entire spill in one stream when inter-batch order is guaranteed (which involved keeping track of this as well). I also added the hard cut-off for eager batching to 100 rows.
   
    <details><summary>sorting benchmarks</summary>
     
     ```text
   ┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
   ┃ Query        ┃       main ┃ top-k-eager-sorting ┃        Change ┃
   ┑━━━━━━━━━━━━━━╇━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
   β”‚ Qsort utf8   β”‚ 28233.61ms β”‚          29251.16ms β”‚     no change β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚ 36739.73ms β”‚          36870.39ms β”‚     no change β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚ 29974.54ms β”‚          30480.98ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch None   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚ 40214.81ms β”‚          40804.29ms β”‚     no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ None         β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚ 29429.65ms β”‚          29875.64ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ None         β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚ 34435.12ms β”‚          34415.10ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ None         β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1709.85ms β”‚           1829.22ms β”‚  1.07x slower β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1842.45ms β”‚           1749.96ms β”‚ +1.05x faster β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1680.46ms β”‚           1677.47ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1745.56ms β”‚           1871.46ms β”‚  1.07x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1965.73ms β”‚           2331.78ms β”‚  1.19x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  1813.14ms β”‚           2061.60ms β”‚  1.14x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1)      β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1712.66ms β”‚           1829.49ms β”‚  1.07x slower β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1832.73ms β”‚           1759.00ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1699.42ms β”‚           1686.28ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1762.86ms β”‚           1877.71ms β”‚  1.07x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1974.07ms β”‚           2337.96ms β”‚  1.18x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  1854.64ms β”‚           2078.75ms β”‚  1.12x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(10)     β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1733.28ms β”‚           1853.74ms β”‚  1.07x slower β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1845.74ms β”‚           1797.14ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1685.38ms β”‚           1712.97ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1799.54ms β”‚           1907.62ms β”‚  1.06x slower β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  2008.06ms β”‚           2371.06ms β”‚  1.18x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  1855.62ms β”‚           2110.55ms β”‚  1.14x slower β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(100)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1728.54ms β”‚           1760.71ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1867.64ms β”‚           1902.02ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1691.19ms β”‚           1708.74ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1784.79ms β”‚           1830.82ms β”‚     no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1999.16ms β”‚           2034.22ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  1869.82ms β”‚           1914.20ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(101)    β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  1774.79ms β”‚           1814.19ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort int    β”‚  1959.51ms β”‚           1999.51ms β”‚     no change β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1714.06ms β”‚           1730.36ms β”‚     no change β”‚
   β”‚ decimal      β”‚            β”‚                     β”‚               β”‚
   β”‚ fetch        β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort        β”‚  1940.85ms β”‚           1969.82ms β”‚     no change β”‚
   β”‚ integer      β”‚            β”‚                     β”‚               β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort utf8   β”‚  2103.61ms β”‚           2132.59ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β”‚ Qsort mixed  β”‚  2032.56ms β”‚           2087.27ms β”‚     no change β”‚
   β”‚ tuple fetch  β”‚            β”‚                     β”‚               β”‚
   β”‚ Some(1000)   β”‚            β”‚                     β”‚               β”‚
   β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜
   ```
   </details>
   
   Overall the times are not that impressive, and the implementation is quite convoluted at this point, so I wouldn't merge this either.



-- 
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