Memory limited nest loop join
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Is your feature request related to a problem or challenge?
The common NLJ implementation consumes constant memory. However, DataFusion's implementation is optimized for execution time, which requires it to buffer all input data on one side, making it possible to fail under memory-constrained cases.
The following pseudocode explains the current implementation:
## Normal NLJ
```
for l_batch in nlj.left.get_next_batch():
for r_batch in nlj.right.get_next_batch():
let matched_entries = match(l_batch, r_batch);
output(matched_entries)
nlj.right.reset(); // Let right side of the join restart and scan again
```
## DataFusion's NLJ implementation
```
for l_batch in nlj.left.get_next_batch():
buffered_left_batches.push(l_batch);
for r_batch in nlj.right.get_next_batch():
let matched_entries = match(buffered_left_batches, r_batch);
output(matched_batches);
```
Related code: https://github.com/apache/datafusion/blob/128217081ca922c404fe423c3c1b945662d53c8a/datafusion/physical-plan/src/joins/nested_loop_join.rs#L499
### Describe the solution you'd like
When the memory limit is reached when buffering the left side input, start probing the right side. After it's done, collect the remaining left side entries, and let the right side scan from the beginning and probe again, until finished.
### Describe alternatives you've considered
_No response_
### Additional context
_No response_
Contributor guide
Research direction
Start by reading datafusion/physical-plan/src/joins/nested_loop_join.rs around line 499 and trace how the current nested-loop join buffers and probes input batches. Verify how memory limits and restarting the right input are represented in the execution layer; done means the join can operate within the memory limit while preserving the requested repeated-probing behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- databases
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100