Skip to content

Commit 663f8c7

Browse files
authored
fix(merge_insert): stop indexed merges failing or hanging under a bounded pool (#10581)
Closes #10580 An indexed `merge_insert` under a bounded pool can fail with `Failed to allocate`, and on main it can hang. With rows outside the index, the target reaches its sort through `RepartitionExec`, which takes a third share of the fair pool and, until DataFusion 56, can deadlock with two spilling inputs (apache/datafusion#24883). Separately, a spilled source sort keeps a growing merge reservation while the target sort runs, so the target sort can fail even on a fully indexed table. This change replaces `RepartitionExec` with `CoalescePartitionsExec` and finishes the source sort before the target sort starts, using the `materialize_stream` barrier from #9129 with the same `pool/8` in-memory limit as `update_join`. Each sort then has the pool to itself. Up to `pool/8` of the sorted source stays in memory outside the pool's accounting. The barrier has a price when the source exceeds `pool/8`: it is written to temporary storage once more, which took 1.07-1.28x the time of main in my runs and up to twice the peak temporary disk. With the default 100 GiB limit, a merge where few rows match reaches it at a source of about 33 GiB instead of 50 GiB. Smaller sources stay within 1.09x of main, and merges with many rows outside the index get 1.7-2x faster. Batches in the `CoalescePartitionsExec` channel are not accounted either, which raised peak RSS by 9% with 64 KiB rows and by at most 1% with narrower ones. Capping the size of those scan batches is left to #10077.
1 parent e85c959 commit 663f8c7

3 files changed

Lines changed: 185 additions & 16 deletions

File tree

‎rust/lance/src/dataset/write/merge_insert/job.rs‎

Lines changed: 26 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -48,10 +48,10 @@ use datafusion::{
4848
execution::context::{SessionConfig, SessionContext},
4949
logical_expr::{self, Expr, Extension, JoinType, LogicalPlan},
5050
physical_plan::{
51-
ExecutionPlan, PhysicalExpr, SendableRecordBatchStream, display::DisplayableExecutionPlan,
52-
joins::SortMergeJoinExec, projection::ProjectionExec, repartition::RepartitionExec,
53-
sorts::sort::SortExec, stream::RecordBatchStreamAdapter, streaming::PartitionStream,
54-
union::UnionExec,
51+
ExecutionPlan, PhysicalExpr, SendableRecordBatchStream,
52+
coalesce_partitions::CoalescePartitionsExec, display::DisplayableExecutionPlan,
53+
joins::SortMergeJoinExec, projection::ProjectionExec, sorts::sort::SortExec,
54+
stream::RecordBatchStreamAdapter, streaming::PartitionStream, union::UnionExec,
5555
},
5656
physical_planner::{DefaultPhysicalPlanner, PhysicalPlanner},
5757
prelude::DataFrame,
@@ -70,10 +70,10 @@ use lance_core::{
7070
};
7171
use lance_datafusion::{
7272
exec::{
73-
HardCapBatchSizeExec, LanceExecutionOptions, analyze_plan,
73+
HardCapBatchSizeExec, LanceExecutionOptions, OneShotExec, analyze_plan,
7474
execute_plan_with_session_context, new_session_context, provider_to_stream,
7575
},
76-
spill::spilling_table_provider_with_job_disk_manager,
76+
spill::{materialize_stream, spilling_table_provider_with_job_disk_manager},
7777
utils::StreamingWriteSource,
7878
};
7979
use lance_index::IndexCriteria;
@@ -434,11 +434,10 @@ impl MergeInsertJob {
434434
.create_plan()
435435
.await?;
436436
let unioned = UnionExec::try_new(vec![target, fallback_data])?;
437-
// Enforce only 1 partition.
438-
target = Arc::new(RepartitionExec::try_new(
439-
unioned,
440-
datafusion::physical_plan::Partitioning::RoundRobinBatch(1),
441-
)?);
437+
// Enforce only 1 partition. RepartitionExec would take a share of the fair pool
438+
// from the target sort, and until DataFusion 56 spilling from two inputs can
439+
// deadlock it (apache/datafusion#24883).
440+
target = Arc::new(CoalescePartitionsExec::new(unioned));
442441
}
443442

444443
// We need to prefix the fields in the target with target_ so that we don't have any duplicate
@@ -507,7 +506,22 @@ impl MergeInsertJob {
507506
}
508507
let source_input = Arc::new(HardCapBatchSizeExec::new(source_input, max_batch_bytes));
509508
let target = Arc::new(HardCapBatchSizeExec::new(target, max_batch_bytes));
510-
let source_input = Arc::new(SortExec::new(source_ordering, source_input));
509+
// A sort spilled to several runs keeps a merge reservation until its output is read,
510+
// and that reservation grows with the number of runs, up to the whole pool. Finish
511+
// the source sort first, so that each sort has the pool to itself.
512+
let sorted_source = execute_plan_with_session_context(
513+
Arc::new(SortExec::new(source_ordering, source_input)),
514+
execution_options.clone(),
515+
session_ctx,
516+
)?;
517+
let (sorted_source, _) = materialize_stream(
518+
sorted_source,
519+
session_ctx.runtime_env(),
520+
execution_options.mem_pool_size() as usize / 8,
521+
"materializing sorted merge insert source",
522+
)
523+
.await?;
524+
let source_input = Arc::new(OneShotExec::new(sorted_source));
511525
let target = Arc::new(SortExec::new(target_ordering, target));
512526
let joined: Arc<dyn ExecutionPlan> = Arc::new(SortMergeJoinExec::try_new(
513527
source_input,

‎rust/lance/src/dataset/write/merge_insert/update_fragments.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -154,9 +154,9 @@ impl MergeInsertJob {
154154
) -> Result<PatchedFragments> {
155155
let (current_version, write_version) = versions;
156156
// Fully stage the joined updates before starting the fragment sort. An
157-
// indexed join can keep merge streams for both sorted inputs live while
157+
// indexed join can keep the merge stream of its target sort live while
158158
// its output is pulled; draining a disk-backed replay first releases
159-
// those upstream reservations before the downstream sort allocates. The
159+
// that upstream reservation before the downstream sort allocates. The
160160
// zero memory limit is deliberate: the staging buffer holds plain
161161
// RecordBatches outside DataFusion's memory-pool accounting, so any
162162
// in-memory allowance would weaken the operation's bounded-memory

‎rust/lance/tests/merge_insert_spill.rs‎

Lines changed: 157 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -8,14 +8,19 @@
88
//! This file must stay a single-test integration binary because the indexed
99
//! merge path reads its pool size from the process-global `LANCE_MEM_POOL_SIZE`.
1010
11+
use std::collections::BTreeMap;
1112
use std::sync::Arc;
1213

13-
use arrow_array::{cast::AsArray, types::UInt64Type};
14+
use arrow_array::{
15+
RecordBatch, RecordBatchIterator, RecordBatchReader,
16+
cast::AsArray,
17+
types::{Float32Type, UInt32Type, UInt64Type},
18+
};
1419
use lance::Dataset;
1520
use lance::dataset::write::merge_insert::{WhenMatched, WhenNotMatched};
1621
use lance::dataset::{MergeInsertBuilder, WriteParams};
1722
use lance::index::DatasetIndexExt;
18-
use lance_datagen::{BatchCount, ByteCount, RowCount, Seed, array, gen_batch};
23+
use lance_datagen::{BatchCount, ByteCount, Dimension, RowCount, Seed, array, gen_batch};
1924
use lance_index::IndexType;
2025
use lance_index::scalar::ScalarIndexParams;
2126

@@ -27,6 +32,112 @@ const PARTIAL_ROWS_PER_BATCH: u64 = 50_000;
2732
const PARTIAL_BATCHES: u32 = 4;
2833
const WIDE_KEY_BYTES: u64 = 2048;
2934
const NUM_ROWS: u64 = 8192;
35+
const SPILLED_SOURCE_MEM_POOL_SIZE: u64 = 8 * 1024 * 1024;
36+
const SPILLED_SOURCE_ROWS: u64 = 1024;
37+
// Vector dimensions of the rows below. A fixed width decodes to what the file holds, so the
38+
// batches have the sizes these comments rely on.
39+
//
40+
// 8192 rows of this width are about 2.7 MiB, above the 2 MiB byte cap of a sort input in a
41+
// 16 MiB pool, so the sort reserves 4 MiB for a capped slice.
42+
const TAIL_DIM: u32 = 80;
43+
const SPILLED_SOURCE_DIM: u32 = 1536;
44+
// A sort reserves twice a batch. Twice this 3 MiB row is more than a third of a 16 MiB pool
45+
// and less than two thirds.
46+
const WIDE_ROW_DIM: u32 = 768 * 1024;
47+
48+
fn rows(first_id: u64, num_rows: u64, dim: u32, updated: u32) -> RecordBatch {
49+
gen_batch()
50+
.with_seed(Seed::from(first_id))
51+
.col("id", array::step_custom::<UInt64Type>(first_id, 1))
52+
.col(
53+
"payload",
54+
array::rand_vec::<Float32Type>(Dimension::from(dim)),
55+
)
56+
.col("updated", array::fill::<UInt32Type>(updated))
57+
.into_batch_rows(RowCount::from(num_rows))
58+
.unwrap()
59+
}
60+
61+
fn reader(batches: Vec<RecordBatch>) -> Box<dyn RecordBatchReader + Send> {
62+
let schema = batches[0].schema();
63+
Box::new(RecordBatchIterator::new(
64+
batches.into_iter().map(Ok),
65+
schema,
66+
))
67+
}
68+
69+
fn ids(batch: &RecordBatch) -> &[u64] {
70+
batch["id"].as_primitive::<UInt64Type>().values()
71+
}
72+
73+
/// Upserts `source` by `id` under `pool_bytes` and checks every row. The dataset has `indexed`
74+
/// under an index on `id`, and `unindexed` in a fragment appended after the index build.
75+
async fn upsert(
76+
pool_bytes: u64,
77+
indexed: RecordBatch,
78+
unindexed: Option<RecordBatch>,
79+
source: Vec<RecordBatch>,
80+
) {
81+
let mut expected = ids(&indexed)
82+
.iter()
83+
.chain(unindexed.iter().flat_map(ids))
84+
.map(|id| (*id, 0))
85+
.collect::<BTreeMap<u64, u32>>();
86+
let (mut expected_updates, mut expected_inserts) = (0, 0);
87+
for id in source.iter().flat_map(ids) {
88+
match expected.insert(*id, 1) {
89+
Some(_) => expected_updates += 1,
90+
None => expected_inserts += 1,
91+
}
92+
}
93+
94+
let mut dataset = Dataset::write(reader(vec![indexed]), "memory://", None)
95+
.await
96+
.unwrap();
97+
dataset
98+
.create_index(
99+
&["id"],
100+
IndexType::Scalar,
101+
None,
102+
&ScalarIndexParams::default(),
103+
false,
104+
)
105+
.await
106+
.unwrap();
107+
if let Some(unindexed) = unindexed {
108+
dataset.append(reader(vec![unindexed]), None).await.unwrap();
109+
}
110+
111+
unsafe { std::env::set_var("LANCE_MEM_POOL_SIZE", pool_bytes.to_string()) };
112+
let (dataset, stats) = MergeInsertBuilder::try_new(Arc::new(dataset), vec!["id".to_string()])
113+
.unwrap()
114+
.when_matched(WhenMatched::UpdateAll)
115+
.when_not_matched(WhenNotMatched::InsertAll)
116+
.try_build()
117+
.unwrap()
118+
.execute_reader(reader(source))
119+
.await
120+
.unwrap();
121+
122+
assert_eq!(stats.num_updated_rows, expected_updates);
123+
assert_eq!(stats.num_inserted_rows, expected_inserts);
124+
let mut scan = dataset.scan();
125+
scan.project(&["id", "updated"]).unwrap();
126+
let merged = scan.try_into_batch().await.unwrap();
127+
let mut actual = ids(&merged)
128+
.iter()
129+
.copied()
130+
.zip(
131+
merged["updated"]
132+
.as_primitive::<UInt32Type>()
133+
.values()
134+
.iter()
135+
.copied(),
136+
)
137+
.collect::<Vec<_>>();
138+
actual.sort_unstable();
139+
assert_eq!(actual, expected.into_iter().collect::<Vec<_>>());
140+
}
30141

31142
#[tokio::test]
32143
async fn test_indexed_merge_insert_spills_wide_source() {
@@ -235,4 +346,48 @@ async fn test_indexed_merge_insert_spills_wide_source() {
235346
.unwrap(),
236347
partial_total_rows as usize
237348
);
349+
350+
// Rows appended after the index build reach the target sort through a scan, whose batches
351+
// hit the byte cap of the sort input. A capped batch fits the sort's share of the pool next
352+
// to one other spillable consumer, but not next to two.
353+
upsert(
354+
MEM_POOL_SIZE,
355+
rows(0, 1024, TAIL_DIM, 0),
356+
Some(rows(1024, NUM_ROWS, TAIL_DIM, 0)),
357+
vec![
358+
rows(512, 1024, TAIL_DIM, 1),
359+
rows(1024 + NUM_ROWS, 512, TAIL_DIM, 1),
360+
],
361+
)
362+
.await;
363+
364+
// A source spilled to several runs keeps a merge reservation for each run of its last merge
365+
// pass for as long as its stream is open. The target sort must not have to fit next to it.
366+
// The keys arrive out of order, so the join is right only if the source reaches it sorted.
367+
upsert(
368+
SPILLED_SOURCE_MEM_POOL_SIZE,
369+
rows(0, SPILLED_SOURCE_ROWS, SPILLED_SOURCE_DIM, 0),
370+
None,
371+
vec![
372+
rows(
373+
SPILLED_SOURCE_ROWS,
374+
SPILLED_SOURCE_ROWS,
375+
SPILLED_SOURCE_DIM,
376+
1,
377+
),
378+
rows(0, SPILLED_SOURCE_ROWS, SPILLED_SOURCE_DIM, 1),
379+
],
380+
)
381+
.await;
382+
383+
// The byte cap cannot split a row, so a row of up to a quarter of the pool must fit on either
384+
// side of the join and in either arm of the target: a sort reserves twice the row, and
385+
// merging two runs of it takes twice that.
386+
upsert(
387+
MEM_POOL_SIZE,
388+
rows(0, 1, WIDE_ROW_DIM, 0),
389+
Some(rows(1, 1, WIDE_ROW_DIM, 0)),
390+
vec![rows(0, 2, WIDE_ROW_DIM, 1), rows(2, 1, WIDE_ROW_DIM, 1)],
391+
)
392+
.await;
238393
}

0 commit comments

Comments
 (0)