2010YOUY01 opened a new pull request, #25371: URL: https://github.com/apache/datafusion/pull/25371
## 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. --> - part of https://github.com/apache/datafusion/issues/23076 ## Rationale for this change `NestedLoopJoinExec` buffers the build side as multiple `RecordBatch`es and then concatenates them into a single batch. During concatenation, the original batches and the concatenated output coexist, temporarily requiring roughly 2x the memory for the buffered data. See below issue for more details: - https://github.com/apache/datafusion/issues/23076 This PR avoids that memory amplification by keeping the build side in a segmented layout: ``` struct NLJ { // ... build_side: LogicalBatch } // Single contiguous batch abstraction: indexable via global row indices struct LogicalBatch { storage: Vec<RecordBatch> } ``` The segmented batches are wrapped in a reusable `LogicalBatch` abstraction, which presents them as one logically contiguous batch while hiding the underlying physical layout from operators. This has two main benefits: - The abstraction can potentially be reused by other operators, such as hash join and piecewise merge join, that have similar `concat_batches` memory amplification. - Operators do not need to handle segmented batches directly; they can work with `LogicalBatch` as a single logical batch, to simplify their inner logic. This PR supersedes #24820. The main difference is that this PR extracts the segmented batch representation into the reusable `LogicalBatch` abstraction, while #24820 handles the `Vec<RecordBatch>` layout directly inside `NestedLoopJoinExec`. ### Reproducer The query below has approximately 80 MB of raw build-side `Int64` values. Avoiding concatenation eliminates the additional full-size copy created by `concat_batches`. ``` -- /tmp/nlj-rss.sql SET datafusion.optimizer.join_reordering = false; SET datafusion.execution.target_partitions = 1; SELECT count(*), sum(l.value) FROM generate_series(1, 10000000) AS l JOIN generate_series(1, 1) AS r ON (l.value + r.value) % 2 = 0; ``` Measure peak RSS on both the PR branch and `main`: env -u RUSTC_WRAPPER cargo build --locked --profile release-nonlto -p datafusion-cli /usr/bin/time -l target/release-nonlto/datafusion-cli -q -f /tmp/nlj-rss.sql git checkout main env -u RUSTC_WRAPPER cargo build --locked --profile release-nonlto -p datafusion-cli /usr/bin/time -l target/release-nonlto/datafusion-cli -q -f /tmp/nlj-rss.sql Peak RSS: | Branch | Peak RSS | | --- | ---: | | `main` | ~1.6 GB | | This PR | ~800 MB | ## 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. --> - Introduced `LogicalBatch` module, with single contiguous batch abstraction, but internally use segmented physical layout - Use `LogicalBatch` in NLJ ## What is the testing strategy for this PR? <!-- We typically require tests for all PRs in order to: 1. Prevent the code from being accidentally broken by subsequent changes 2. Serve as another way to document the expected behavior of the code Briefly describe how this PR is tested, and point to the specific tests you added. For example: 'This new feature is covered by the `sqllogictest` cases added in `foo.slt`'. If this PR does not add tests, explain why. For example, if the change is already covered by existing tests, please mention it. You should also check the `codecov` bot reply on this PR to confirm the changed code is exercised. --> - For correctness on NLJ, existing tests - Basic and for-documenting API tests on `LogicalBatch` module - Memory validation test for 2X memory issue - the first commit of this PR is this test, it fails without the change. - Manually validated the NLJ execution time is unaffected ``` -- Run bench at feature branch git checkout nlj-segbatch CARGO_COMMAND='cargo run --profile release-nonlto' ./benchmarks/bench.sh run nlj -- Run bench at main branch git checkout main CARGO_COMMAND='cargo run --profile release-nonlto' ./benchmarks/bench.sh run nlj -- Compare PR v.s. main ./benchmarks/bench.sh compare main nlj-segbatch -- Result -------------------- Benchmark nlj.json -------------------- ┏━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━━┳━━━━━━━━━━━┓ ┃ Query ┃ main ┃ nlj-segbatch ┃ Change ┃ ┡━━━━━━━━━━━╇━━━━━━━━━━━━╇━━━━━━━━━━━━━━╇━━━━━━━━━━━┩ │ QQuery 1 │ 86.44 ms │ 83.82 ms │ no change │ │ QQuery 2 │ 102.50 ms │ 103.59 ms │ no change │ │ QQuery 3 │ 153.60 ms │ 151.99 ms │ no change │ │ QQuery 4 │ 327.97 ms │ 324.28 ms │ no change │ │ QQuery 5 │ 228.03 ms │ 231.16 ms │ no change │ │ QQuery 6 │ 1642.58 ms │ 1638.15 ms │ no change │ │ QQuery 7 │ 236.37 ms │ 231.71 ms │ no change │ │ QQuery 8 │ 1633.73 ms │ 1626.62 ms │ no change │ │ QQuery 9 │ 268.37 ms │ 266.83 ms │ no change │ │ QQuery 10 │ 472.76 ms │ 470.76 ms │ no change │ │ QQuery 11 │ 201.69 ms │ 198.44 ms │ no change │ │ QQuery 12 │ 204.23 ms │ 203.82 ms │ no change │ │ QQuery 13 │ 76.10 ms │ 75.14 ms │ no change │ │ QQuery 14 │ 75.40 ms │ 76.92 ms │ no change │ │ QQuery 15 │ 77.00 ms │ 77.05 ms │ no change │ │ QQuery 16 │ 77.80 ms │ 77.23 ms │ no change │ │ QQuery 17 │ 78.90 ms │ 76.17 ms │ no change │ └───────────┴────────────┴──────────────┴───────────┘ ``` ## 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. --> No -- 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]
