Skip to content

Commit a522cd5

Browse files
authored
perf: Reduce peak memory usage of NLJ by 2X using segmented batch layout (#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 #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: - #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 800 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, 100000000) 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
1 parent 6e4d9ba commit a522cd5

5 files changed

Lines changed: 856 additions & 57 deletions

File tree

‎datafusion/core/tests/memory_limit/memory_limit_validation/mod.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@
1818
//! Validates query's actual memory usage is consistent with the specified memory
1919
//! limit.
2020
21+
mod nlj_mem_validation;
2122
mod smj_mem_validation;
2223
mod sort_mem_validation;
2324
mod utils;
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
//! Memory validation for the nested loop join's buffered build side.
19+
20+
use datafusion::prelude::SessionConfig;
21+
22+
use crate::memory_limit::memory_limit_validation::utils;
23+
24+
#[test]
25+
fn nlj_no_mem_limit_runner() {
26+
utils::spawn_test_process("nlj_mem_validation", "nlj_no_mem_limit");
27+
}
28+
29+
// NLJ buffers the entire build side and uses a small, constant amount of memory
30+
// to stream the probe side.
31+
//
32+
// This test verifies that an NLJ without a memory limit follows this estimate.
33+
#[tokio::test]
34+
async fn nlj_no_mem_limit() {
35+
let config = SessionConfig::new()
36+
.with_target_partitions(1)
37+
.with_batch_size(8192)
38+
// Keep the large input on the build side, as written in the query.
39+
.set_bool("datafusion.optimizer.join_reordering", false);
40+
41+
utils::validate_query_with_memory_limits_and_config(
42+
90_000_000, // 80 MB for the build side + 10 MB of extra room.
43+
None,
44+
"SELECT count(*), sum(l.value)
45+
FROM generate_series(1, 10000000) AS l
46+
JOIN generate_series(1, 1) AS r
47+
ON (l.value + r.value) % 2 = 0",
48+
"SELECT count(*), sum(l.value)
49+
FROM generate_series(1, 1000000) AS l
50+
JOIN generate_series(1, 1) AS r
51+
ON (l.value + r.value) % 2 = 0",
52+
config,
53+
Some("NestedLoopJoinExec"),
54+
Some(false),
55+
)
56+
.await;
57+
}

0 commit comments

Comments
 (0)