You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "geoffreyclaude (via GitHub)" <gi...@apache.org> on 2026/10/15 10:49:51 UTC

[PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

geoffreyclaude opened a new pull request, #26366:
URL: https://github.com/apache/datafusion/pull/26366

   ## Which issue does this PR close?
   
   Follow-up to [#25372](https://github.com/apache/datafusion/pull/25372), related to [#23174](https://github.com/apache/datafusion/issues/23174). This can merge independently of the sort-task concurrency change in [#26242](https://github.com/apache/datafusion/pull/26242).
   
   ## Rationale for this change
   
   Multi-key sorts over many small batches spend quadratic time accounting for retained row buffers, delaying their first merged output.
   
   The merge caches one encoded row buffer per input stream. Each new batch currently scans every cache slot to recalculate the reservation. Reading the first batch from each of N streams therefore requires N full scans. A large merge can spend seconds doing this bookkeeping in a single Tokio poll.
   
   ## What changes are included in this PR?
   
   - Track each stream's reserved bytes and update the total by that stream's change, making each accounting update constant-time.
   - Keep the existing charge while a buffer is reused. Failed buffer growth and stream completion release only that stream's charge.
   - Add a SQL benchmark that sorts two million rows loaded in 32-row batches. Two sort keys exercise the affected row-format merge. Data generation happens before timing.
   
   ## What is the testing strategy for this PR?
   
   A focused regression test fills a bounded memory pool, then rejects growth of a reused row buffer. It checks that the failed stream releases its previous reservation while another stream remains accounted for.
   
   The SQL benchmark runs a single query, with no concurrent workload:
   
   ```bash
   cargo run --release --bin benchmark_runner -- sort_small_batches --iterations 5
   ```
   
   With four Tokio workers and one partition, nine executions per version in interleaved groups gave:
   
   | Single-query wall time | `upstream/main` | This PR |
   |---|---:|---:|
   | Median | 4.82 s | 1.30 s |
   | Range | 4.52–5.64 s | 1.23–1.46 s |
   
   That is about **3.7× faster**. Both optimized builds use the same upstream base and return all two million rows.
   
   ## Are there any user-facing changes?
   
   Large row-format merges perform less bookkeeping while preserving their memory reservations. The SQL benchmark is listed in the benchmark guide, and the internal reservation invariant is documented alongside the per-stream sizes.
   
   Developed with AI assistance.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude commented on code in PR #26366:
URL: https://github.com/apache/datafusion/pull/26366#discussion_r4284201216


##########
datafusion/physical-plan/src/sorts/stream.rs:
##########
@@ -130,22 +133,25 @@ impl ReusableRows {
     /// reservation is free for the same reason. A pool that cannot cover the buffer
     /// fails the query here, as it did before the buffer was cached at all.
     fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
-        self.inner[stream_idx] = Some(Arc::clone(rows));
-        let retained = self.retained_size();
+        let size = rows.size();
+        let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
         debug_assert!(retained >= self.reservation.size());
         if let Err(e) = self.reservation.try_resize(retained) {
-            self.inner[stream_idx] = None;
-            self.reservation.try_resize(self.retained_size())?;
+            self.release(stream_idx);
             return Err(e);
         }
+        self.inner[stream_idx] = Some(Arc::clone(rows));
+        self.reserved_sizes[stream_idx] = size;
         Ok(())
     }
 
     // drop whatever a finished stream was holding
     fn release(&mut self, stream_idx: usize) {
         debug_assert!(self.reservation.size() >= self.retained_size());
-        if let Some(rows) = self.inner[stream_idx].take() {
-            self.reservation.shrink(rows.size());
+        self.inner[stream_idx] = None;
+        let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
+        if reserved != 0 {
+            self.reservation.shrink(reserved);

Review Comment:
   That makes sense! How does the following look to you?
   ```rust
   fn release(&mut self, stream_idx: usize) {
       debug_assert!(self.reservation.size() >= self.retained_size());
       self.inner[stream_idx] = None;
       let released = mem::take(&mut self.reserved_sizes[stream_idx]);
       self.reservation.resize(self.reservation.size() - released);
   }
   ```
   This handles the zero-change case too (I used `resize` rather than `try_resize` since we’re only releasing memory).



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

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

   run benchmark sql
   env:
     BENCH_NAME: sort_small_batches
   baseline:
     ref: 929fc506f948ba9df79189b46087160f1098ce2d


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude commented on code in PR #26366:
URL: https://github.com/apache/datafusion/pull/26366#discussion_r4284201216


##########
datafusion/physical-plan/src/sorts/stream.rs:
##########
@@ -130,22 +133,25 @@ impl ReusableRows {
     /// reservation is free for the same reason. A pool that cannot cover the buffer
     /// fails the query here, as it did before the buffer was cached at all.
     fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
-        self.inner[stream_idx] = Some(Arc::clone(rows));
-        let retained = self.retained_size();
+        let size = rows.size();
+        let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
         debug_assert!(retained >= self.reservation.size());
         if let Err(e) = self.reservation.try_resize(retained) {
-            self.inner[stream_idx] = None;
-            self.reservation.try_resize(self.retained_size())?;
+            self.release(stream_idx);
             return Err(e);
         }
+        self.inner[stream_idx] = Some(Arc::clone(rows));
+        self.reserved_sizes[stream_idx] = size;
         Ok(())
     }
 
     // drop whatever a finished stream was holding
     fn release(&mut self, stream_idx: usize) {
         debug_assert!(self.reservation.size() >= self.retained_size());
-        if let Some(rows) = self.inner[stream_idx].take() {
-            self.reservation.shrink(rows.size());
+        self.inner[stream_idx] = None;
+        let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
+        if reserved != 0 {
+            self.reservation.shrink(reserved);

Review Comment:
   That makes sense! How does the following look to you?
   ```rust
   fn release(&mut self, stream_idx: usize) {
       debug_assert!(self.reservation.size() >= self.retained_size());
       self.inner[stream_idx] = None;
       let released = mem::take(&mut self.reserved_sizes[stream_idx]);
       self.reservation.resize(self.reservation.size() - released);
   }
   ```
   This handles the zero-change case too (I used resize rather than try_resize since we’re only releasing memory).
   
   I think we should keep the total incremental though: summing all stream sizes each time one finishes would make cleanup quadratic 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@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

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

   run benchmark sort
   env:
     BENCH_FILTER: small_batches/two_keys
   baseline:
     ref: 90371f98bc58380fe6cb6540e12f6111c8649946


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

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

   🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/26366#issuecomment-6192383833)
   
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
   
   Comparing codex/incremental-merge-row-accounting (6cfaaa47e53a7558a5f3b38aa88dec977762e78d) to 929fc506f948ba9df79189b46087160f1098ce2d [diff](https://github.com/apache/datafusion/compare/929fc506f948ba9df79189b46087160f1098ce2d..6cfaaa47e53a7558a5f3b38aa88dec977762e78d)
   
   <details><summary>Run configuration</summary>
   
   ```yaml
   run benchmark sql
   env:
     BENCH_NAME: "sort_small_batches"
   baseline:
     ref: "929fc506f948ba9df79189b46087160f1098ce2d"
   ```
   
   </details>
   
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   <details><summary>Details</summary>
   <p>
   
   ```
   group                     HEAD                                   codex_incremental-merge-row-accounting
   -----                     ----                                   --------------------------------------
   sort_small_batches/Q01    3.54       5.4±0.15s        ? ?/sec    1.00  1524.7±31.67ms        ? ?/sec
   ```
   
   </p>
   </details>
   
   <details><summary>Resource Usage</summary>
   
   **sql — base (merge-base)**
   | Metric | Value |
   |--------|-------|
   | Wall time | 835.3s |
   | Peak memory | 456.4 MiB |
   | Avg memory | 31.3 MiB |
   | CPU user | 64.2s |
   | CPU sys | 5.3s |
   | Peak spill | 0 B |
   
   **sql — branch**
   | Metric | Value |
   |--------|-------|
   | Wall time | 600.3s |
   | Peak memory | 465.8 MiB |
   | Avg memory | 14.8 MiB |
   | CPU user | 28.3s |
   | CPU sys | 1.8s |
   | Peak spill | 0 B |
   
   </details>
   
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

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

   🤖 Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/26366#issuecomment-6194487836)
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c6194487836-3457-6dggq 6.12.94+ #1 SMP Fri Aug 21 08:00:16 UTC 2026 aarch64 GNU/Linux`
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   Comparing codex/incremental-merge-row-accounting (24ef31cb9c061dd7ab4fe3e7a5fa60de026ff598) to 90371f98bc58380fe6cb6540e12f6111c8649946 [diff](https://github.com/apache/datafusion/compare/90371f98bc58380fe6cb6540e12f6111c8649946..24ef31cb9c061dd7ab4fe3e7a5fa60de026ff598)
   
   <details><summary>Run configuration</summary>
   
   ```yaml
   run benchmark sort
   env:
     BENCH_FILTER: "small_batches/two_keys"
   baseline:
     ref: "90371f98bc58380fe6cb6540e12f6111c8649946"
   ```
   
   </details>
   
   Results will be posted here when complete
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude commented on code in PR #26366:
URL: https://github.com/apache/datafusion/pull/26366#discussion_r4284201216


##########
datafusion/physical-plan/src/sorts/stream.rs:
##########
@@ -130,22 +133,25 @@ impl ReusableRows {
     /// reservation is free for the same reason. A pool that cannot cover the buffer
     /// fails the query here, as it did before the buffer was cached at all.
     fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
-        self.inner[stream_idx] = Some(Arc::clone(rows));
-        let retained = self.retained_size();
+        let size = rows.size();
+        let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
         debug_assert!(retained >= self.reservation.size());
         if let Err(e) = self.reservation.try_resize(retained) {
-            self.inner[stream_idx] = None;
-            self.reservation.try_resize(self.retained_size())?;
+            self.release(stream_idx);
             return Err(e);
         }
+        self.inner[stream_idx] = Some(Arc::clone(rows));
+        self.reserved_sizes[stream_idx] = size;
         Ok(())
     }
 
     // drop whatever a finished stream was holding
     fn release(&mut self, stream_idx: usize) {
         debug_assert!(self.reservation.size() >= self.retained_size());
-        if let Some(rows) = self.inner[stream_idx].take() {
-            self.reservation.shrink(rows.size());
+        self.inner[stream_idx] = None;
+        let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
+        if reserved != 0 {
+            self.reservation.shrink(reserved);

Review Comment:
   That makes sense! How does the following look to you?
   ```rust
   fn release(&mut self, stream_idx: usize) {
       debug_assert!(self.reservation.size() >= self.retained_size());
       self.inner[stream_idx] = None;
       let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
       self.reservation.resize(self.reservation.size() - reserved);
   }
   ```
   This handles the zero-change case too (I used `resize` rather than `try_resize` since we’re only releasing memory).



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude commented on code in PR #26366:
URL: https://github.com/apache/datafusion/pull/26366#discussion_r4292225619


##########
datafusion/physical-plan/src/sorts/stream.rs:
##########
@@ -130,22 +133,25 @@ impl ReusableRows {
     /// reservation is free for the same reason. A pool that cannot cover the buffer
     /// fails the query here, as it did before the buffer was cached at all.
     fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
-        self.inner[stream_idx] = Some(Arc::clone(rows));
-        let retained = self.retained_size();
+        let size = rows.size();
+        let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
         debug_assert!(retained >= self.reservation.size());
         if let Err(e) = self.reservation.try_resize(retained) {
-            self.inner[stream_idx] = None;
-            self.reservation.try_resize(self.retained_size())?;
+            self.release(stream_idx);
             return Err(e);
         }
+        self.inner[stream_idx] = Some(Arc::clone(rows));
+        self.reserved_sizes[stream_idx] = size;
         Ok(())
     }
 
     // drop whatever a finished stream was holding
     fn release(&mut self, stream_idx: usize) {
         debug_assert!(self.reservation.size() >= self.retained_size());
-        if let Some(rows) = self.inner[stream_idx].take() {
-            self.reservation.shrink(rows.size());
+        self.inner[stream_idx] = None;
+        let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
+        if reserved != 0 {
+            self.reservation.shrink(reserved);

Review Comment:
   I tried using the existing `retained_size()` helper in draft #26389: clear the finished stream and its recorded size, then call `try_resize(self.retained_size())`.
   
   The [benchmark bot results](https://github.com/apache/datafusion/pull/26389#issuecomment-6202596131) show the small-batch sort going from **2.6s to 11.5s**, about **4.4× slower**. Each completed input triggers a scan of all input slots, so this brings back quadratic accounting work during stream completion. The cost is substantial for the workload this PR targets.
   
   Would you be ok with keeping `try_resize()` with the incremental total, but checking it against the sum of the recorded sizes in a debug assertion?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude commented on code in PR #26366:
URL: https://github.com/apache/datafusion/pull/26366#discussion_r4292225619


##########
datafusion/physical-plan/src/sorts/stream.rs:
##########
@@ -130,22 +133,25 @@ impl ReusableRows {
     /// reservation is free for the same reason. A pool that cannot cover the buffer
     /// fails the query here, as it did before the buffer was cached at all.
     fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
-        self.inner[stream_idx] = Some(Arc::clone(rows));
-        let retained = self.retained_size();
+        let size = rows.size();
+        let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
         debug_assert!(retained >= self.reservation.size());
         if let Err(e) = self.reservation.try_resize(retained) {
-            self.inner[stream_idx] = None;
-            self.reservation.try_resize(self.retained_size())?;
+            self.release(stream_idx);
             return Err(e);
         }
+        self.inner[stream_idx] = Some(Arc::clone(rows));
+        self.reserved_sizes[stream_idx] = size;
         Ok(())
     }
 
     // drop whatever a finished stream was holding
     fn release(&mut self, stream_idx: usize) {
         debug_assert!(self.reservation.size() >= self.retained_size());
-        if let Some(rows) = self.inner[stream_idx].take() {
-            self.reservation.shrink(rows.size());
+        self.inner[stream_idx] = None;
+        let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
+        if reserved != 0 {
+            self.reservation.shrink(reserved);

Review Comment:
   I tried using the existing `retained_size()` helper in draft #26389: clear the finished stream and its recorded size, then call `try_resize(self.retained_size())`:
   ```rust
       // drop whatever a finished stream was holding
       fn release(&mut self, stream_idx: usize) -> Result<()> {
           debug_assert!(self.reservation.size() >= self.retained_size());
           self.inner[stream_idx] = None;
           self.reserved_sizes[stream_idx] = 0;
           self.reservation.try_resize(self.retained_size())
       }
   
       fn retained_size(&self) -> usize {
           self.inner.iter().flatten().map(|rows| rows.size()).sum()
       }
   ```
   
   The [benchmark bot results](https://github.com/apache/datafusion/pull/26389#issuecomment-6202596131) show the small-batch sort going from **2.6s to 11.5s**, about **4.4× slower**. Each completed input triggers a scan of all input slots, so this brings back quadratic accounting work during stream completion. The cost is substantial for the workload this PR targets.
   
   Would you be ok with keeping `resize()` with the incremental total, but checking it against the sum of the recorded sizes in a debug assertion? See latest commit.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

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

   🤖 Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/26366#issuecomment-6192383833)
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c6192383833-3439-l648m 6.12.94+ #1 SMP Fri Aug 21 08:00:16 UTC 2026 aarch64 GNU/Linux`
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   Comparing codex/incremental-merge-row-accounting (6cfaaa47e53a7558a5f3b38aa88dec977762e78d) to 929fc506f948ba9df79189b46087160f1098ce2d [diff](https://github.com/apache/datafusion/compare/929fc506f948ba9df79189b46087160f1098ce2d..6cfaaa47e53a7558a5f3b38aa88dec977762e78d)
   
   <details><summary>Run configuration</summary>
   
   ```yaml
   run benchmark sql
   env:
     BENCH_NAME: "sort_small_batches"
   baseline:
     ref: "929fc506f948ba9df79189b46087160f1098ce2d"
   ```
   
   </details>
   
   Results will be posted here when complete
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "EmilyMatt (via GitHub)" <gi...@apache.org>.
EmilyMatt commented on code in PR #26366:
URL: https://github.com/apache/datafusion/pull/26366#discussion_r4283962456


##########
datafusion/physical-plan/src/sorts/stream.rs:
##########
@@ -130,22 +133,25 @@ impl ReusableRows {
     /// reservation is free for the same reason. A pool that cannot cover the buffer
     /// fails the query here, as it did before the buffer was cached at all.
     fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
-        self.inner[stream_idx] = Some(Arc::clone(rows));
-        let retained = self.retained_size();
+        let size = rows.size();
+        let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
         debug_assert!(retained >= self.reservation.size());
         if let Err(e) = self.reservation.try_resize(retained) {
-            self.inner[stream_idx] = None;
-            self.reservation.try_resize(self.retained_size())?;
+            self.release(stream_idx);
             return Err(e);
         }
+        self.inner[stream_idx] = Some(Arc::clone(rows));
+        self.reserved_sizes[stream_idx] = size;
         Ok(())
     }
 
     // drop whatever a finished stream was holding
     fn release(&mut self, stream_idx: usize) {
         debug_assert!(self.reservation.size() >= self.retained_size());
-        if let Some(rows) = self.inner[stream_idx].take() {
-            self.reservation.shrink(rows.size());
+        self.inner[stream_idx] = None;
+        let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
+        if reserved != 0 {
+            self.reservation.shrink(reserved);

Review Comment:
   Personally I always prefer an accumulative sizing, as in, calculate the total size that is held right now(after setting this stream to 0), then do a try_resize, it both avoids bugs and mis-accounting, and also handles the != 0 part on its own



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

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

   🚀 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #26366:
URL: https://github.com/apache/datafusion/pull/26366#issuecomment-6191385045

   ## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/26366?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
   :x: Patch coverage is `72.41379%` with `8 lines` in your changes missing coverage. Please review.
   :white_check_mark: Project coverage is 82.84%. Comparing base ([`91cd7ff`](https://app.codecov.io/gh/apache/datafusion/commit/91cd7ffb927b5a4f9fee1907db50a9610759de5b?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`aca3552`](https://app.codecov.io/gh/apache/datafusion/commit/aca3552e449f675bb9ffb5917516c034edb59b67?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
   :warning: Report is 3 commits behind head on main.
   
   | [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/26366?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
   |---|---|---|
   | [datafusion/physical-plan/src/sorts/stream.rs](https://app.codecov.io/gh/apache/datafusion/pull/26366?src=pr&el=tree&filepath=datafusion%2Fphysical-plan%2Fsrc%2Fsorts%2Fstream.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1wbGFuL3NyYy9zb3J0cy9zdHJlYW0ucnM=) | 72.41% | [2 Missing and 6 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/26366?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
   
   <details><summary>Additional details and impacted files</summary>
   
   
   
   ```diff
   @@            Coverage Diff             @@
   ##             main   #26366      +/-   ##
   ==========================================
   - Coverage   82.84%   82.84%   -0.01%     
   ==========================================
     Files        1151     1151              
     Lines      455510   455528      +18     
     Branches   455510   455528      +18     
   ==========================================
   + Hits       377362   377372      +10     
   - Misses      55236    55240       +4     
   - Partials    22912    22916       +4     
   ```
   </details>
   
   [:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/26366?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).   
   :loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
   <details><summary> :rocket: New features to boost your workflow: </summary>
   
   - :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
   - :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
   </details>


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "EmilyMatt (via GitHub)" <gi...@apache.org>.
EmilyMatt commented on code in PR #26366:
URL: https://github.com/apache/datafusion/pull/26366#discussion_r4285749410


##########
datafusion/physical-plan/src/sorts/stream.rs:
##########
@@ -130,22 +133,25 @@ impl ReusableRows {
     /// reservation is free for the same reason. A pool that cannot cover the buffer
     /// fails the query here, as it did before the buffer was cached at all.
     fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
-        self.inner[stream_idx] = Some(Arc::clone(rows));
-        let retained = self.retained_size();
+        let size = rows.size();
+        let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
         debug_assert!(retained >= self.reservation.size());
         if let Err(e) = self.reservation.try_resize(retained) {
-            self.inner[stream_idx] = None;
-            self.reservation.try_resize(self.retained_size())?;
+            self.release(stream_idx);
             return Err(e);
         }
+        self.inner[stream_idx] = Some(Arc::clone(rows));
+        self.reserved_sizes[stream_idx] = size;
         Ok(())
     }
 
     // drop whatever a finished stream was holding
     fn release(&mut self, stream_idx: usize) {
         debug_assert!(self.reservation.size() >= self.retained_size());
-        if let Some(rows) = self.inner[stream_idx].take() {
-            self.reservation.shrink(rows.size());
+        self.inner[stream_idx] = None;
+        let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
+        if reserved != 0 {
+            self.reservation.shrink(reserved);

Review Comment:
   I think while it's tempting to use the mem::take()'s value, it's more resilient to just set to 0 manually instead and 1. Still use a try_resize(), to not rely on the assumption that memory has only shrunk(logic could change and break that assumption) and 2. Call the functiom that calculates the total size of the stream(the perf impact of this is negligible), as in the future more stuff could be added to that function.
   I.e., never fully "trust" that the current reservation is correct, and always strive to fix 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@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "EmilyMatt (via GitHub)" <gi...@apache.org>.
EmilyMatt commented on code in PR #26366:
URL: https://github.com/apache/datafusion/pull/26366#discussion_r4306510909


##########
datafusion/physical-plan/src/sorts/stream.rs:
##########
@@ -130,22 +133,25 @@ impl ReusableRows {
     /// reservation is free for the same reason. A pool that cannot cover the buffer
     /// fails the query here, as it did before the buffer was cached at all.
     fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
-        self.inner[stream_idx] = Some(Arc::clone(rows));
-        let retained = self.retained_size();
+        let size = rows.size();
+        let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
         debug_assert!(retained >= self.reservation.size());
         if let Err(e) = self.reservation.try_resize(retained) {
-            self.inner[stream_idx] = None;
-            self.reservation.try_resize(self.retained_size())?;
+            self.release(stream_idx);
             return Err(e);
         }
+        self.inner[stream_idx] = Some(Arc::clone(rows));
+        self.reserved_sizes[stream_idx] = size;
         Ok(())
     }
 
     // drop whatever a finished stream was holding
     fn release(&mut self, stream_idx: usize) {
         debug_assert!(self.reservation.size() >= self.retained_size());
-        if let Some(rows) = self.inner[stream_idx].take() {
-            self.reservation.shrink(rows.size());
+        self.inner[stream_idx] = None;
+        let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
+        if reserved != 0 {
+            self.reservation.shrink(reserved);

Review Comment:
   Yeah that sounds like a good compromise :)



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude commented on code in PR #26366:
URL: https://github.com/apache/datafusion/pull/26366#discussion_r4306560878


##########
datafusion/physical-plan/src/sorts/stream.rs:
##########
@@ -130,22 +133,25 @@ impl ReusableRows {
     /// reservation is free for the same reason. A pool that cannot cover the buffer
     /// fails the query here, as it did before the buffer was cached at all.
     fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
-        self.inner[stream_idx] = Some(Arc::clone(rows));
-        let retained = self.retained_size();
+        let size = rows.size();
+        let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
         debug_assert!(retained >= self.reservation.size());
         if let Err(e) = self.reservation.try_resize(retained) {
-            self.inner[stream_idx] = None;
-            self.reservation.try_resize(self.retained_size())?;
+            self.release(stream_idx);
             return Err(e);
         }
+        self.inner[stream_idx] = Some(Arc::clone(rows));
+        self.reserved_sizes[stream_idx] = size;
         Ok(())
     }
 
     // drop whatever a finished stream was holding
     fn release(&mut self, stream_idx: usize) {
         debug_assert!(self.reservation.size() >= self.retained_size());
-        if let Some(rows) = self.inner[stream_idx].take() {
-            self.reservation.shrink(rows.size());
+        self.inner[stream_idx] = None;
+        let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
+        if reserved != 0 {
+            self.reservation.shrink(reserved);

Review Comment:
   awesome! Thanks for the detailed review!



##########
datafusion/physical-plan/src/sorts/stream.rs:
##########
@@ -130,22 +133,25 @@ impl ReusableRows {
     /// reservation is free for the same reason. A pool that cannot cover the buffer
     /// fails the query here, as it did before the buffer was cached at all.
     fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
-        self.inner[stream_idx] = Some(Arc::clone(rows));
-        let retained = self.retained_size();
+        let size = rows.size();
+        let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
         debug_assert!(retained >= self.reservation.size());
         if let Err(e) = self.reservation.try_resize(retained) {
-            self.inner[stream_idx] = None;
-            self.reservation.try_resize(self.retained_size())?;
+            self.release(stream_idx);
             return Err(e);
         }
+        self.inner[stream_idx] = Some(Arc::clone(rows));
+        self.reserved_sizes[stream_idx] = size;
         Ok(())
     }
 
     // drop whatever a finished stream was holding
     fn release(&mut self, stream_idx: usize) {
         debug_assert!(self.reservation.size() >= self.retained_size());
-        if let Some(rows) = self.inner[stream_idx].take() {
-            self.reservation.shrink(rows.size());
+        self.inner[stream_idx] = None;
+        let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
+        if reserved != 0 {
+            self.reservation.shrink(reserved);

Review Comment:
   awesome! Thanks for the detailed review!



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #26366:
URL: https://github.com/apache/datafusion/pull/26366


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

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

   🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/26366#issuecomment-6194487836)
   
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
   
   Comparing codex/incremental-merge-row-accounting (24ef31cb9c061dd7ab4fe3e7a5fa60de026ff598) to 90371f98bc58380fe6cb6540e12f6111c8649946 [diff](https://github.com/apache/datafusion/compare/90371f98bc58380fe6cb6540e12f6111c8649946..24ef31cb9c061dd7ab4fe3e7a5fa60de026ff598)
   
   <details><summary>Run configuration</summary>
   
   ```yaml
   run benchmark sort
   env:
     BENCH_FILTER: "small_batches/two_keys"
   baseline:
     ref: "90371f98bc58380fe6cb6540e12f6111c8649946"
   ```
   
   </details>
   
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   <details><summary>Details</summary>
   <p>
   
   ```
   group                     HEAD                                   codex_incremental-merge-row-accounting
   -----                     ----                                   --------------------------------------
   small_batches/two_keys    4.09      13.9±0.57s        ? ?/sec    1.00       3.4±0.07s        ? ?/sec
   ```
   
   </p>
   </details>
   
   <details><summary>Resource Usage</summary>
   
   **sort — base (merge-base)**
   | Metric | Value |
   |--------|-------|
   | Wall time | 355.1s |
   | Peak memory | 493.7 MiB |
   | Avg memory | 208.7 MiB |
   | CPU user | 162.1s |
   | CPU sys | 6.7s |
   | Peak spill | 0 B |
   
   **sort — branch**
   | Metric | Value |
   |--------|-------|
   | Wall time | 230.1s |
   | Peak memory | 503.8 MiB |
   | Avg memory | 80.5 MiB |
   | CPU user | 42.8s |
   | CPU sys | 3.2s |
   | Peak spill | 0 B |
   
   </details>
   
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude commented on code in PR #26366:
URL: https://github.com/apache/datafusion/pull/26366#discussion_r4284201216


##########
datafusion/physical-plan/src/sorts/stream.rs:
##########
@@ -130,22 +133,25 @@ impl ReusableRows {
     /// reservation is free for the same reason. A pool that cannot cover the buffer
     /// fails the query here, as it did before the buffer was cached at all.
     fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
-        self.inner[stream_idx] = Some(Arc::clone(rows));
-        let retained = self.retained_size();
+        let size = rows.size();
+        let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
         debug_assert!(retained >= self.reservation.size());
         if let Err(e) = self.reservation.try_resize(retained) {
-            self.inner[stream_idx] = None;
-            self.reservation.try_resize(self.retained_size())?;
+            self.release(stream_idx);
             return Err(e);
         }
+        self.inner[stream_idx] = Some(Arc::clone(rows));
+        self.reserved_sizes[stream_idx] = size;
         Ok(())
     }
 
     // drop whatever a finished stream was holding
     fn release(&mut self, stream_idx: usize) {
         debug_assert!(self.reservation.size() >= self.retained_size());
-        if let Some(rows) = self.inner[stream_idx].take() {
-            self.reservation.shrink(rows.size());
+        self.inner[stream_idx] = None;
+        let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
+        if reserved != 0 {
+            self.reservation.shrink(reserved);

Review Comment:
   That makes sense! How does the following look to you?
   ```rust
   fn release(&mut self, stream_idx: usize) {
       debug_assert!(self.reservation.size() >= self.retained_size());
       self.inner[stream_idx] = None;
       let released = mem::take(&mut self.reserved_sizes[stream_idx]);
       self.reservation.resize(self.reservation.size() - released);
   }
   ```
   This handles the zero-change case too (I used `resize` rather than `try_resize` since we’re only releasing memory).
   
   I think we should keep the total incremental though: summing all stream sizes each time one finishes would make cleanup quadratic 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@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude commented on code in PR #26366:
URL: https://github.com/apache/datafusion/pull/26366#discussion_r4292225619


##########
datafusion/physical-plan/src/sorts/stream.rs:
##########
@@ -130,22 +133,25 @@ impl ReusableRows {
     /// reservation is free for the same reason. A pool that cannot cover the buffer
     /// fails the query here, as it did before the buffer was cached at all.
     fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
-        self.inner[stream_idx] = Some(Arc::clone(rows));
-        let retained = self.retained_size();
+        let size = rows.size();
+        let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
         debug_assert!(retained >= self.reservation.size());
         if let Err(e) = self.reservation.try_resize(retained) {
-            self.inner[stream_idx] = None;
-            self.reservation.try_resize(self.retained_size())?;
+            self.release(stream_idx);
             return Err(e);
         }
+        self.inner[stream_idx] = Some(Arc::clone(rows));
+        self.reserved_sizes[stream_idx] = size;
         Ok(())
     }
 
     // drop whatever a finished stream was holding
     fn release(&mut self, stream_idx: usize) {
         debug_assert!(self.reservation.size() >= self.retained_size());
-        if let Some(rows) = self.inner[stream_idx].take() {
-            self.reservation.shrink(rows.size());
+        self.inner[stream_idx] = None;
+        let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
+        if reserved != 0 {
+            self.reservation.shrink(reserved);

Review Comment:
   I tried using the existing `retained_size()` helper in draft #26389: clear the finished stream and its recorded size, then call `try_resize(self.retained_size())`.
   
   The [benchmark bot results](https://github.com/apache/datafusion/pull/26389#issuecomment-6202596131) show the small-batch sort going from **2.6s to 11.5s**, about **4.4× slower**. Each completed input triggers a scan of all input slots, so this brings back quadratic accounting work during stream completion. The cost is substantial for the workload this PR targets.
   
   Could we keep `try_resize()` with the incremental total, and check it against the sum of the recorded sizes in a debug assertion?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude commented on code in PR #26366:
URL: https://github.com/apache/datafusion/pull/26366#discussion_r4292225619


##########
datafusion/physical-plan/src/sorts/stream.rs:
##########
@@ -130,22 +133,25 @@ impl ReusableRows {
     /// reservation is free for the same reason. A pool that cannot cover the buffer
     /// fails the query here, as it did before the buffer was cached at all.
     fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
-        self.inner[stream_idx] = Some(Arc::clone(rows));
-        let retained = self.retained_size();
+        let size = rows.size();
+        let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
         debug_assert!(retained >= self.reservation.size());
         if let Err(e) = self.reservation.try_resize(retained) {
-            self.inner[stream_idx] = None;
-            self.reservation.try_resize(self.retained_size())?;
+            self.release(stream_idx);
             return Err(e);
         }
+        self.inner[stream_idx] = Some(Arc::clone(rows));
+        self.reserved_sizes[stream_idx] = size;
         Ok(())
     }
 
     // drop whatever a finished stream was holding
     fn release(&mut self, stream_idx: usize) {
         debug_assert!(self.reservation.size() >= self.retained_size());
-        if let Some(rows) = self.inner[stream_idx].take() {
-            self.reservation.shrink(rows.size());
+        self.inner[stream_idx] = None;
+        let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
+        if reserved != 0 {
+            self.reservation.shrink(reserved);

Review Comment:
   I tried using the existing `retained_size()` helper in draft #26389: clear the finished stream and its recorded size, then call `try_resize(self.retained_size())`:
   ```rust
       // drop whatever a finished stream was holding
       fn release(&mut self, stream_idx: usize) -> Result<()> {
           debug_assert!(self.reservation.size() >= self.retained_size());
           self.inner[stream_idx] = None;
           self.reserved_sizes[stream_idx] = 0;
           self.reservation.try_resize(self.retained_size())
       }
   
       fn retained_size(&self) -> usize {
           self.inner.iter().flatten().map(|rows| rows.size()).sum()
       }
   ```
   
   The [benchmark bot results](https://github.com/apache/datafusion/pull/26389#issuecomment-6202596131) show the small-batch sort going from **2.6s to 11.5s**, about **4.4× slower**. Each completed input triggers a scan of all input slots, so this brings back quadratic accounting work during stream completion. The cost is substantial for the workload this PR targets.
   
   Would you be ok with keeping `try_resize()` with the incremental total, but checking it against the sum of the recorded sizes in a debug assertion?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: avoid quadratic row-buffer accounting in sort merges [datafusion]

Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude commented on code in PR #26366:
URL: https://github.com/apache/datafusion/pull/26366#discussion_r4292225619


##########
datafusion/physical-plan/src/sorts/stream.rs:
##########
@@ -130,22 +133,25 @@ impl ReusableRows {
     /// reservation is free for the same reason. A pool that cannot cover the buffer
     /// fails the query here, as it did before the buffer was cached at all.
     fn save(&mut self, stream_idx: usize, rows: &Arc<Rows>) -> Result<()> {
-        self.inner[stream_idx] = Some(Arc::clone(rows));
-        let retained = self.retained_size();
+        let size = rows.size();
+        let retained = self.reservation.size() - self.reserved_sizes[stream_idx] + size;
         debug_assert!(retained >= self.reservation.size());
         if let Err(e) = self.reservation.try_resize(retained) {
-            self.inner[stream_idx] = None;
-            self.reservation.try_resize(self.retained_size())?;
+            self.release(stream_idx);
             return Err(e);
         }
+        self.inner[stream_idx] = Some(Arc::clone(rows));
+        self.reserved_sizes[stream_idx] = size;
         Ok(())
     }
 
     // drop whatever a finished stream was holding
     fn release(&mut self, stream_idx: usize) {
         debug_assert!(self.reservation.size() >= self.retained_size());
-        if let Some(rows) = self.inner[stream_idx].take() {
-            self.reservation.shrink(rows.size());
+        self.inner[stream_idx] = None;
+        let reserved = mem::take(&mut self.reserved_sizes[stream_idx]);
+        if reserved != 0 {
+            self.reservation.shrink(reserved);

Review Comment:
   I tried using the existing `retained_size()` helper in draft #26389: clear the finished stream and its recorded size, then call `try_resize(self.retained_size())`:
   ```rust
       // drop whatever a finished stream was holding
       fn release(&mut self, stream_idx: usize) -> Result<()> {
           debug_assert!(self.reservation.size() >= self.retained_size());
           self.inner[stream_idx] = None;
           self.reserved_sizes[stream_idx] = 0;
           self.reservation.try_resize(self.retained_size())
       }
   
       fn retained_size(&self) -> usize {
           self.inner.iter().flatten().map(|rows| rows.size()).sum()
       }
   ```
   
   The [benchmark bot results](https://github.com/apache/datafusion/pull/26389#issuecomment-6202596131) show the small-batch sort going from **2.6s to 11.5s**, about **4.4× slower**. Each completed input triggers a scan of all input slots, so this brings back quadratic accounting work during stream completion. The cost is substantial for the workload this PR targets.
   
   Would you be ok with keeping `resize()` with the incremental total, but checking it against the sum of the recorded sizes in a debug assertion?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org