apache / apache/datafusion

Memory limited nest loop join

Open
#15,760 4 comments 0 reactions 0 assignees View on GitHub
enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.