2010YOUY01 opened a new pull request, #16889:
URL: https://github.com/apache/datafusion/pull/16889
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and
enhancements and this helps us generate change logs for our releases. You can
link an issue to this PR using the GitHub syntax. For example `Closes #123`
indicates that this PR will close issue #123.
-->
- Closes #.
## Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in
the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your
changes and offer better suggestions for fixes.
-->
Now the NLJ execution logic is
1. Buffer all left input
2. Read one right batch at a time, and do a Cartesian product
(all-left-batches x right-batch) to fetch the index combination
3. Incrementally do the join on that pre-computed indices
This approach includes one extra step for a very large Cartesian product
calculation, it can be both memory-consuming and in-efficient. A better
approach can be directly perform the join on a small intermediate.
## What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is
sometimes worth providing a summary of the individual changes in this PR.
-->
### Summary
This PR introduces a somewhat unusual change: it rewrites the Nested Loop
Join operator from scratch.
### Motivation
The original implementation performs a Cartesian product of
(all-left-batches x right-batch), materializes that intermediate result for
predicate evaluation, and then materializes the (potentially very large) final
result all at once. This design is inherently inefficient, and although many
patches have attempted to alleviate the problem, the fundamental issue remains.
A key challenge is that the original design and the ideal design (i.e., one
that produces small intermediates during execution) are fundamentally
different. As a result, it's practically impossible to make small incremental
changes that fully address the inefficiency. These patches may also increase
code complexity, making long-term maintenance more difficult.
### Example of Prior Work
Here's a recent example of a small patch intended to improve the situation:
https://github.com/apache/datafusion/pull/16443
Even with careful engineering, I still feel the entropy in the code
increases.
### Why a Rewrite?
Since NLJ is a relatively straightforward operator, a full rewrite seemed
worthwhile. This allows for a clean, simplified design focused on current
goals—performance and memory efficiency—without being constrained by the legacy
implementation.
### Current Status and Outlook
The rewrite is smoother than I expected: The current minimal implementation,
which reuses existing utilities (despite some inefficiencies), is already up to
**2× faster** and is likely significantly more memory-efficient (although
memory usage has not yet been measured)
I also noticed there are several more optimizations opportunities to make it
even faster. Now the implementation got regular tests passed, and there are
several `join_fuzz` tests failing, after fixing them we can iterate on more
optimizations.
### Benchmark Result
The NLJ micro-bench: https://github.com/apache/datafusion/pull/16819
```
┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query ┃ pr-16819 ┃ nlj-rewrite-tmp ┃ Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ QQuery 1 │ 219.41 ms │ 139.04 ms │ +1.58x faster │
│ QQuery 2 │ 265.81 ms │ 210.78 ms │ +1.26x faster │
│ QQuery 3 │ 363.44 ms │ 323.62 ms │ +1.12x faster │
│ QQuery 4 │ 995.84 ms │ 687.71 ms │ +1.45x faster │
│ QQuery 5 │ 640.90 ms │ 359.25 ms │ +1.78x faster │
│ QQuery 6 │ 5677.61 ms │ 2761.88 ms │ +2.06x faster │
│ QQuery 7 │ 666.71 ms │ 356.39 ms │ +1.87x faster │
│ QQuery 8 │ 5632.40 ms │ 2769.81 ms │ +2.03x faster │
│ QQuery 9 │ 673.28 ms │ 425.60 ms │ +1.58x faster │
│ QQuery 10 │ 2185.64 ms │ 1532.81 ms │ +1.43x faster │
└──────────────┴────────────┴─────────────────┴───────────────┘
```
### Implementation
The design/implementation doc can be found in the source.
### Next Steps
Given there are still many opportunities to make it even faster, I plan to
include several major optimizations into the current PR to save some review
bandwidth (It's always a contiguous low hundreds LoC for the core logic, even
if we include more optimizations into it)
- [ ] TODO: doc about the major potential optimizations
- [ ] Fix bug that caused `join_fuzz` tests to fail
- [ ] Memory-limited case (maybe this can be split to a separate PR 🤔 , but
I want to first do some POC to ensure it won't cause big structural change)
Would love to hear your thoughts on this @UBarney @jonathanc-n @ding-young ,
and looking forward to collaborating to make NLJ as fast as possible.
## Are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
5. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are
they covered by existing tests)?
-->
## Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be
updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please add the `api
change` label.
-->
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
