NestedLoopJoinExec spill path: untracked allocation overshoots memory pool

Describe the bug

NestedLoopJoinExec's memory-limited (spill) path allocates more memory than it reserves through the MemoryPool. The accounting-pool framework added in #22626 surfaces this if HEADROOM_FACTOR in the SLT pool is tightened — see #22721, which lowers it from 8.0 → 5.0 and trips this test.

To Reproduce

In datafusion/sqllogictest/src/accounting_pool.rs, set:

```rust
const HEADROOM_FACTOR: f64 = 5.0;
```

Then run nested_loop_join_spill.slt. First query at line 33:

```sql
SET datafusion.execution.target_partitions = 1;
SET datafusion.runtime.memory_limit = '150K';

SELECT count(*) as cnt, min(v1) as mn, max(v1) as mx
FROM generate_series(1, 100000) AS t1(v1)
INNER JOIN generate_series(1, 1) AS t2(v2)
ON (t1.v1 + t2.v2) > 0;
```

Expected behavior

Query succeeds with allocator usage bounded by the configured memory_limit (×~10% slop for legitimate untracked overhead like Tokio/Rayon thread state).

Actual behavior

```
External error: 1 errors in file datafusion/sqllogictest/test_files/nested_loop_join_spill.slt

query failed: Other Error: allocator overdraft: account balance at panic = -20245 bytes
at nested_loop_join_spill.slt:33
```

Peak allocator usage reaches ~770KB against a declared 150KB pool — 5.13× the budget. The first ~750KB (5×) is absorbed by the headroom factor; the additional 20245 bytes is allocator usage that was never reserved through MemoryPool::try_grow.

Likely root cause

Spill path in NestedLoopJoinExec has at least these untracked allocation sites (need verification with targeted instrumentation):

generate_next_batch buffering — RecordBatches accumulated for the build side before the spill decision
concat_batches at the spill boundary — copies into a coalesced batch before the IPC writer sees it
take_native during the probe phase — gather kernels allocate output buffers
IPC reader path on spill re-read — the StreamReader/FileReader decoder owns buffers that aren't accounted

The first query in the test stays small (100K × i32 = ~400KB build side), so the overshoot is whatever lives off-pool in the spill setup, not the bulk data itself.

Additional context

Surfaced by the allocator-vs-pool tracker added in Track allocator-level memory vs MemoryPool during SLTs to prevent OOMs #22626.
Demonstration PR: Lower SLT HEADROOM_FACTOR 8.0 -> 5.0 to surface nested_loop_join_spill leak #22721 (test-only: lowers HEADROOM_FACTOR; expected to fail until this is fixed).
Fix should reserve memory through MemoryReservation before each of the sites above, not bump the headroom constant — the constant is a leak detector, not a budget.

Component

Physical Plan

@comphead

@comphead @andygrove the first of many issues that will probably be found tightening the ratchet. @alamb do we want an epic?

I think, given the current implementation conventions, this kind of validation is not feasible in this failing SLT.

Issue 1 -- operators don't track in-progress batches

Operators don't account for in-progress batch memory for simplicity. This is typically one batch inside each operator per partition. If the batches are wide or the partition count is high, this can become significant.

SET datafusion.execution.target_partitions = 1;
SET datafusion.runtime.memory_limit = '150K';

SELECT count(*) as cnt, min(v1) as mn, max(v1) as mx
FROM generate_series(1, 100000) AS t1(v1)
INNER JOIN generate_series(1, 1) AS t2(v2)
ON (t1.v1 + t2.v2) > 0;

This query already contains a substantial amount of untracked in-progress memory:

generate_series holds one temporary batch: 8K rows * 8 bytes = 64KB
NLJ holds a batch for evaluating the filter (v1, v2, 0), plus a result batch: roughly 8K rows * 8 bytes * 3

Given the current implementation, this behavior is expected and not specific to NLJ. Addressing it would require updating all operators to account for in-progress batches.

Issue 2 -- memory allocator noise

I'm assuming the 770KB measurement is allocator RSS. This may also include internal fragmentation, or memory that the allocator has not yet returned to the OS. In such cases RSS can appear high, even though the allocator could potentially release the memory immediately if the OS requests it.

Ideas on follow up works

Overall, I don't think issue 1 is easy to solve, and perhaps these very small memory-limited queries should not be used for allocator-vs-pool validation. They are still useful as correctness tests.

This kind of validation is more feasible when memory pool limit >> single batch size. That likely means using memory limits in the hundreds of MB range and adding a separate extended test suite with dedicated test cases.

Issue 2 remains a challenge, and I'm not sure how to make the validation more accurate. It likely requires a deeper investigation into allocator and OS memory accounting behavior.

@2010YOUY01

Thanks @2010YOUY01 , you raise some valid points. I'm working on a full response, but I wanted to just respond now to say I'm not ignoring you :)

@avantgardnerio

Thanks @avantgardnerio and @2010YOUY01
Hope this initiative would bring us closer to broader spilling support. I strongly agree for epic to group current spill tickets into single place
https://github.com/apache/datafusion/issues?q=is%3Aissue%20state%3Aopen%20spill

I would also prob add a spilling support for windows as well

broader spilling support

The tracker I just checked in was specifically aimed at catching memory pool regressions, but since it tracks all allocations one could imagine using a similar thing to better flag when things need to spill.

@2010YOUY01

@2010YOUY01 let me address issue 2 first, since that is a straightforward response. The AccountingAllocator tracks each alloc and free, so RSS / page bloat is not an issue.

I am experimenting with a version of the allocator / OOM guard in Comet in apache/datafusion-comet#4582

@2010YOUY01

@2010YOUY01 , re: issue 1 - PTAL at the actual issue for the DataFusion 51 regression that motivated this whole path. I should have lead with that, and I think it answers a few of your questions. Instead of doing that, I just cranked HEADROOM down to 5 and filed a bug for the first thing it hit (NLJ).

Addressing your points (as I perceive them) not addressed by the above:

This conflates integration tests with memory accounting tests. i.e. the operator is at fault, not a random SLT. I would argue that most of our coverage is through SLTs so adding it here buys regression testing "for free". Normally that might be bad, because when an integration test breaks it's hard to debug, but this tracker usually points to the exact call stack of the bug. I think accounting regressions are real regressions and thus belong in the regression suite.
"small memory-limited queries" - I think the question is twofold: 1. what is "small"? and 2. how does it scale? 700K in a test might be "small", but if that multiplies out in a prod environment to be 7GB, then it's big. A possible solution: we can define both the existing relative HEADROOM and an ABS_HEADROOM and it doesn't fire unless it crosses both. I would lightly push back though because that means we specifically need to run all these with large amounts of data, which means we don't get the benefit of the existing suite.

I think your other concerns (difficulty of tracking, size required to track, etc) are all addressed in the other issue. I hope I was able to give a proper response after I put in proper effort.

@2010YOUY01 , re: issue 1 - PTAL at the actual issue for the DataFusion 51 regression that motivated this whole path. I should have lead with that, and I think it answers a few of your questions. Instead of doing that, I just cranked HEADROOM down to 5 and filed a bug for the first thing it hit (NLJ).

Addressing your points (as I perceive them) not addressed by the above:

This conflates integration tests with memory accounting tests. i.e. the operator is at fault, not a random SLT. I would argue that most of our coverage is through SLTs so adding it here buys regression testing "for free". Normally that might be bad, because when an integration test breaks it's hard to debug, but this tracker usually points to the exact call stack of the bug. I think accounting regressions are real regressions and thus belong in the regression suite.

"small memory-limited queries" - I think the question is twofold: 1. what is "small"? and 2. how does it scale? 700K in a test might be "small", but if that multiplies out in a prod environment to be 7GB, then it's big. A possible solution: we can define both the existing relative HEADROOM and an ABS_HEADROOM and it doesn't fire unless it crosses both. I would lightly push back though because that means we specifically need to run all these with large amounts of data, which means we don't get the benefit of the existing suite.

I think your other concerns (difficulty of tracking, size required to track, etc) are all addressed in the other issue. I hope I was able to give a proper response after I put in proper effort.

Thanks for raising these points. I agree this is an important issue to solve, but I think the proposed approach may be difficult to maintain with the current memory accounting model. Here are a few thoughts on:

why it does not work reliably today
what we might need before it can work well

The current operator-level memory accounting is intentionally incomplete. It mostly tracks buffers that can grow without a fixed bound, such as aggregation hash tables. It generally treats one in-flight batch per operator per partition as constant overhead and leaves it untracked. This can still become large when the operator pipeline is long or when the target partition count is high. Your validation approach would be valid if all of this memory were accounted for, but today's implementation trades completeness for simplicity.
If we do not fix that first, the HEADROOM + ABS_HEADROOM model is wrong. It could produce false positives and make the tests hard to maintain.
- Given this specific bug in the issue, we have to first understand all low level detail in all related operators, then do estimation to figure out if it's false positive or not. Below is the extra investigation to do for bug report triage on this issue, I believe this is very hard to do.

Memory limit is 150K, measured allocation 770K
- generate_series holds one temporary batch: 8K rows * 8 bytes = 64KB
- Current probe side batch: 64KB
- NLJ holds a batch for evaluating the filter (v1, v2, 0), plus a result batch: roughly 8K rows * 8 bytes * 4
- All buffered build side batch: 150KB

--> Corrected memory estimation: 534KB

I agree that catching regressions in SLTs is valuable. But given the assumptions above, the easiest thing we can do for now may be to compare memory usage between commits. That would still let us detect regressions when a PR accidentally increases memory allocation.

TLDR If we decide to continue with #22626, we will need to address all of these issues, i.e. track all allocations in the MemoryPool and update all operators accordingly. The main question is whether we should do that.

I think this is feasible, but it would require paying down a lot of technical debt.
Alternatively, we could accept that memory pool accounting is only accurate when memory_limit >> batch_size * pipeline_length * partition_count, which would allow us to keep the operators simpler.

@avantgardnerio

Maybe this is something we can track / test using a dedicated external tool (like SQL fuzzer) -- for example setup a memory pool as @avantgardnerio suggests in #22739 that compares the allocation reported by the OS and the allocation reported by the memory reservations and then compare them / find areas where they diverge too much

That would avoid the complexity of trying to unit test this type of thing in SLT / etc. but also give us coverage

I filed an epic with a bunch of related memory items to try and coordinate some response

[EPIC] A collection of Memory Accounting Limitations and Improvements #22758

Extreme Programming breaks everything down into:

values: "we have limited resources, so we should manage them wisely"
principles: "so we use X test suite to find untracked memory"
practices: "so we can fix OOM bug GroupValuesRows::emit untracked decode buffer leaks past MemoryReservation #22739 "

IME, people almost always agree on 1 & 3. The principles are usually what takes time to come agreement about, so it's good and natural to be discussing what the optimal way to do this is.

So to avoid getting too abstract, I'll raise a specific grounded question about not doing SLTs:

When our customer runs a query like:

source logs(<team>)
  | filter <priority predicate>
        && \$d.message != null
  | groupby \$d.message agg count(1) as \$d.occurrences
  | orderby \$d.occurrences desc
  | limit 15

If we have memory based SLTs in place, we can translate that into:

statement ok
CREATE TABLE utf8_keys AS
SELECT cast(v AS varchar) || repeat('x', 200) AS k,
       make_array(1) AS _force_rows
FROM generate_series(1, 50000) AS t(v)

statement ok
SET datafusion.runtime.memory_limit = '1M'

query I nosort
SELECT count(*) FROM (
  SELECT k, _force_rows, count(*) AS c
  FROM utf8_keys
  GROUP BY k, _force_rows
)
----
50000

And see an error like:

1. query failed: Other Error: allocator overdraft: account balance at panic = -1384887 bytes
[SQL] SELECT count(*) FROM (
  SELECT k, _force_rows, count(*) AS c
  FROM utf8_keys
  GROUP BY k, _force_rows
)
at /__w/datafusion/datafusion/datafusion/sqllogictest/test_files/group_by_spill_row_decode.slt:49

Then make a PR to fix the error , which stays in the regression suite forever.

So my question is: if we adopt another approach - like SqlFuzz, what would the workflow look like to do the same?

@alamb

@alamb and @2010YOUY01 - what if I introduced a SET runtime.enable_headroom = 5.0 that tests specifically opted into? Would that alleviate the concern? I think that would be better anyway as each test could 1. opt in 2. set it appropriately

So to avoid getting too abstract, I'll raise a specific grounded question about not doing SLTs:

To be clear I don't have anything for/against using SLT as a test harness, I am more concerned about the process and maintainability of the tests over the long term

@alamb and @2010YOUY01 - what if I introduced a SET runtime.enable_headroom = 5.0 that tests specifically opted into? Would that alleviate the concern? I think that would be better anyway as each test could 1. opt in 2. set it appropriately

This sounds like a reasonable approach to me provided:

We clearly document what that setting does, when people should set it, and what they should do if their tests see an error related to it
We have some sort of longer term plan written down (like is the goal to remove all enable_headroom settings

For example, Imagine a new contributor to DataFusion that writes a SLT test for some unrelated feature and it this error

query failed: Other Error: allocator overdraft: account balance at panic = -1384887 bytes

I think it would be very unclear what to do (maybe in the age of LLMs it is easier).

Ideally we could make the error self explanatory and provide the answer of how to solve the issue. Something like this perhaps

query failed: Memory Accounting Mismatch: Plan used 1384887 bytes more actual memory than allowed. Please add a SET runtime.enable_headroom = 5.0 and add this example to ticket https://...

And then have the ticket explain the backstory and have a list of places where memory was over committed

@alamb

make the error self explanatory and provide the answer of how to solve the issue

@alamb I think that's a great solution, and a very reasonable compromise! I'll send a PR with the improvement shortly.

@alamb

@alamb I hope this PR addresses your concerns: #22776

I don't think the error message is the key issue. The problem is that this direction enforces an invariant that does not exist today.

More specifically, the bug reported by this issue — internal accounting showing 150 KB vs. actual allocation of 770 KB — is arguably a feature rather than a bug under the current convention. See:

datafusion/datafusion/execution/src/memory_pool/mod.rs

Lines 60 to 69 in 84bc876

    
           /// # Memory Management Design 
        
           /// 
        
           /// As explained above, DataFusion's design ONLY limits operators that require 
        
           /// "large" amounts of memory (proportional to number of input rows), such as 
        
           /// `GroupByHashExec`. It does NOT track and limit memory used internally by 
        
           /// other operators such as `DataSourceExec` or the `RecordBatch`es that flow 
        
           /// between operators. Furthermore, operators should not reserve memory for the 
        
           /// batches they produce. Instead, if a consumer operator needs to hold batches 
        
           /// from its producers in memory for an extended period, it is the consumer 
        
           /// operator's responsibility to reserve the necessary memory for those batches.

NestedLoopJoinExec spill path: untracked allocation overshoots memory pool #22723 (comment)

I think it is fair to say that this convention may be a bad design, and I am +1 on exploring a direction to fix it. However, I do not think we should write tests that assume this convention has already been invalidated.

In particular, enabling this slt check would effectively assert that MemoryPool accounting must closely track actual allocator usage. That is inconsistent with both the current implementation and the documented convention, where the memory pool intentionally accounts for selected operator-managed memory rather than every byte actually allocated. So the test would not just catch regressions; it would implicitly change the contract by assuming a new accounting convention.

If we can agree on that, I am happy to help provide pointers for exploring an alternative memory-accounting convention, and eventually enabling this slt validation once the new convention is defined.

@2010YOUY01

@2010YOUY01 thanks for the link to the policy, I was unaware. I agree enforcing stricter invariants in the test framework than in the documentation is a bad idea. I'll wait a bit to see if anyone else wants to respond, but otherwise I'll make a revert PR for all of it and close the related issues as "won't fix". Coralogix has a downstream workaround now that alleviates our need for memory tracking.

@2010YOUY01

@2010YOUY01 thanks for the link to the policy, I was unaware. I agree enforcing stricter invariants in the test framework than in the documentation is a bad idea. I'll wait a bit to see if anyone else wants to respond, but otherwise I'll make a revert PR for all of it and close the related issues as "won't fix". Coralogix has a downstream workaround now that alleviates our need for memory tracking.

I agree with @2010YOUY01 here -- trying to make DataFusion's memory model better by enforcing the desired invariants in SLT is probably not a good way to get a clear and coherent design -- we would probably left chasing down memory accounting discrepancies indefinitely

So let's make a revert PR

SOmething I am not quite sure about is if there is a bug in the current code (where the stated policy, however flawed, is not actually followed by the current code)?

Closing in favor of #22834. Revert PR pending.

@alamb

SOmething I am not quite sure about is if there is a bug in the current code (where the stated policy, however flawed, is not actually followed by the current code)?

@alamb Yes, this is possible. The challenge is for slt scale queries they can't be easily caught due to temporary batches noises. If we scale up the queries (GBs of memory), then those temporary batches memory become a small constant, and the accounted memory and actual memory can be validated against each other.
We could definitely set them up in CI, ideally once we get more CI resources to run those slow and memory-consuming queries.

Here is a revert PR: #22860

Revert custom allocator auditing of MemoryPool tracking in SLTs (apac…

Navigation Menu

Repository navigation

NestedLoopJoinExec spill path: untracked allocation overshoots memory pool #22723

Describe the bug

To Reproduce

Expected behavior

Actual behavior

Likely root cause

Additional context

Component

Issue 1 -- operators don't track in-progress batches

Issue 2 -- memory allocator noise

Ideas on follow up works

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	/// # Memory Management Design
	///
	/// As explained above, DataFusion's design ONLY limits operators that require
	/// "large" amounts of memory (proportional to number of input rows), such as
	/// `GroupByHashExec`. It does NOT track and limit memory used internally by
	/// other operators such as `DataSourceExec` or the `RecordBatch`es that flow
	/// between operators. Furthermore, operators should not reserve memory for the
	/// batches they produce. Instead, if a consumer operator needs to hold batches
	/// from its producers in memory for an extended period, it is the consumer
	/// operator's responsibility to reserve the necessary memory for those batches.

NestedLoopJoinExec spill path: untracked allocation overshoots memory pool #22723

Description

Describe the bug

To Reproduce

Expected behavior

Actual behavior

Likely root cause

Additional context

Component

Activity

avantgardnerio commented on Jun 3, 2026

2010YOUY01 commented on Jun 3, 2026

Issue 1 -- operators don't track in-progress batches

Issue 2 -- memory allocator noise

Ideas on follow up works

avantgardnerio commented on Jun 3, 2026

comphead commented on Jun 3, 2026

avantgardnerio commented on Jun 3, 2026

avantgardnerio commented on Jun 3, 2026

andygrove commented on Jun 3, 2026

avantgardnerio commented on Jun 3, 2026

2010YOUY01 commented on Jun 4, 2026

alamb commented on Jun 4, 2026

alamb commented on Jun 4, 2026

avantgardnerio commented on Jun 4, 2026

avantgardnerio commented on Jun 4, 2026

alamb commented on Jun 4, 2026

avantgardnerio commented on Jun 4, 2026

avantgardnerio commented on Jun 5, 2026

2010YOUY01 commented on Jun 5, 2026

avantgardnerio commented on Jun 5, 2026

alamb commented on Jun 8, 2026

avantgardnerio commented on Jun 9, 2026

2010YOUY01 commented on Jun 9, 2026

avantgardnerio commented on Jun 9, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions