Repository navigation
Commit adffd19
authored
fix: leave memory for others when a spilled sort merges its runs (apache#26264)
## Which issue does this PR close?
- Part of apache#25804 (finding 9: "The final spill merge grows its
reservation until the pool refuses").
## Rationale for this change
A sort that has spilled finishes with a merge of its spilled runs. That
merge
seats as many runs as the memory pool will admit (the fan-in is
unlimited by
default), and it holds those buffers until its output is fully consumed.
In a query with several partitions, partitions that finish their input
early
start this final merge while other partitions are still buffering input,
and
while the operator above the sort is still running. Each early merge
takes
whatever the pool admits, and the pool can be exhausted. The partition
that is
still sorting then fails to grow its reservation and the query fails
with
`ResourcesExhausted`, even though only memory for read-ahead buffers was
taken.
A standalone reproduction (below): 6.67M rows,
`SUM(p) OVER (PARTITION BY g ORDER BY k ROWS UNBOUNDED PRECEDING)`
followed by
`MAX`, 10 target partitions, a `FairSpillPool` of 62.5 MB, 40 runs per
setting:
| `sort_spill_reservation_bytes` | main (2c568b4) | this PR |
|---|---|---|
| 1 MB | 25 / 40 succeed | 40 / 40 |
| 1.6 MB | 34 / 40 | 40 / 40 |
| 3 MB | 7 / 40 | 35 / 40 |
The failures are the partitions that are still sorting:
`Failed to allocate additional 3.0 MB for ExternalSorterMerge[6] with
0.0 B
already allocated`, `... 598.8 KB for ExternalSorter[8] with 0.0 B ...`,
or
`... 144.1 KB for ExternalSorterMerge[7]` in `BatchBuilder::push_batch`
while
merging in-memory batches to spill. With a pool instrumented to record
each
consumer's reservation, five partitions in their final merge held 12-29
MB
each when the refusal happened. Capping `max_spill_merge_fan_in` at 4
made
the same runs succeed, which confirms that the merge fan-in causes the
failures.
## What changes are included in this PR?
apache#25383 lets aggregate spill replay leave memory for the aggregate: the
merge
asks the pool to admit its buffers plus as much again, then returns the
extra.
The sort uses a narrower form of that policy:
- The minimum merge of two runs is admitted as before, against the pool
alone. A sort under tight memory keeps its current behavior: it does not
re-spill runs smaller or emit shorter batches only to leave headroom.
- Each run beyond the minimum is seated only if the pool can admit what
the
merge takes beyond the workspace it already holds
(`sort_spill_reservation_bytes`, retained since apache#24740), plus as much
again. The extra is returned before the merge starts. Seating runs
within
the merge's own workspace needs no headroom, because it takes nothing
from others.
When the pool refuses, the merge seats fewer runs and merges in more
passes,
as it already does under memory pressure.
The policy is a new `with_fan_in_headroom` option on
`StreamingMergeBuilder`
and `MultiLevelMergeBuilder`, enabled by `ExternalSorter`. The
aggregate's
replay headroom is unchanged.
Headroom is kept only while someone may need it: while another partition
of
the same `SortExec` is still reading its input, or while another
consumer
holds memory in the pool. Partitions that have already started their own
final merge are covered by the second check. A partition leaves the
count
when it has read all its input, or when it is dropped before that (its
stream
dropped early, or its input failed). A sort with the pool to itself
seats every run that fits, as before, and so does the last partition to
finish reading: keeping headroom there cost an extra merge pass (up to
1.8x
the spilled rows) whether or not anyone needed the memory. With all 2M
rows
in one of 4 partitions, most pools between 16 and 64 MB spilled 1.5-1.8x
the
rows with headroom on; with the count of partitions still reading, every
pool
from 16 to 128 MB spills the same rows as without headroom.
On balanced multi-partition sorts (2M rows, greedy pool, 20 runs each,
same
build with headroom off and on; measured by @jayzhan211 before headroom
followed the count of partitions still reading, which moved these
configs
from 54 to 49 of 60 successes, against 32 without headroom):
| partitions / pool / reservation | success, off → on | spilled rows,
off → on |
|---|---|---|
| 4 / 96 MB / 1 MB | 8 → 17 of 20 | 2.76M → 3.35M |
| 8 / 192 MB / 10 MB | 12 → 17 of 20 | 2.00M → 2.16M |
| 2 / 64 MB / 1 MB | 12 → 20 of 20 | 3.00M → 3.82M |
Where another consumer holds memory, headroom is kept and the merge
seats
fewer runs, so it rewrites rows in more passes. That is the price of the
fix:
with a skewed 4-partition sort under `SortPreservingMergeExec`, or two
one-partition sorts sharing a pool, @jayzhan211 measured up to 1.9x the
spilled rows at 24297ff. `sort_tpch` SF1 Q3/Q4/Q11 showed no
wall-clock
change above noise.
<details>
<summary>Measured cost at 24297ff, same build with headroom off and on
(by @jayzhan211)</summary>
| Plan | Pool | Success, off → on | Spilled rows, off → on |
|---|---|---|---|
| 4 partitions, 97/1/1/1 of 2M rows, under `SortPreservingMergeExec` |
24 MB | 9/9 → 9/9 | 7.66M → 11.01M |
| same | 32 MB | 9/9 → 9/9 | 4.99M → 9.38M |
| same | 48 MB | 1/9 → 9/9 | 2.99M → 4.40M |
| same | 64 MB | 9/9 → 9/9 | 1.94M → 3.12M |
| Two one-partition `SortExec`s, 1.5M rows each | 32 MB | 20/20 → 20/20
| 7.83M → 14.28M |
| same | 48 MB | 17/20 → 19/20 | 6.10M → 8.24M |
Greedy pool, 1 MB `sort_spill_reservation_bytes`.
</details>
### What this does not fix
Each merge leaves as much free as it takes, but merges that start one
after
another still compound: in the remaining 3 MB failures, nine partitions
held
3-18 MB each (17.9, 11.5, 7.7, 5.1, ... MB), and the last partition to
start
could not reserve its own 3 MB `sort_spill_reservation_bytes`. With 10
partitions, the workspaces alone are half of this pool. A guarantee
would
need each merge to know how many partitions share the pool, for example
a
per-partition share of the limit. I left that out of this PR, because it
is
a larger policy change and I would like to hear whether it is wanted.
A single-partition sort, or the last partition to finish reading, still
leaves nothing for the operator above it: that operator reserves nothing
before its first batch, so the merge cannot see it. A `SortExec` whose
partitions are not all executed (for example under a `LIMIT` that stops
early)
counts the partitions never started as still reading, so it keeps
headroom.
## What is the testing strategy for this PR?
- `test_final_spilled_merge_leaves_headroom` (sort/spill_tests.rs)
spills a
sort and leaves the pool room for the final merge to seat every run, but
not to seat every run and still leave as much free. It checks that
whatever
the merge takes beyond its workspace, it leaves as much free, and that
the
output is correct and every reservation is released. It fails on main
("the final merge takes 168128 bytes beyond its workspace and leaves
109728
free").
- `test_sort_exec_keeps_headroom_only_while_siblings_read_input` runs a
`SortExec` partition with no sibling, an idle sibling, a sibling that
has
finished reading, and a sibling whose stream was dropped unpolled; it
fails
if the condition is replaced by `true` or `false`, or if a dropped
partition
stays counted.
- `test_sort_exec_rerun_without_reset_state_keeps_no_headroom` executes
a lone
partition three times without `reset_state`; it fails if the count
wraps.
- Existing tests pass unchanged: `datafusion-physical-plan` (2970),
`datafusion-execution`, the `memory_limit` tests in `core_integration`,
and
the sort, merge, spilling and aggregate fuzz tests (`extended_tests`).
In particular, the batch-size test under a tight limit
(`..._when_having_to_spill`) and the workspace retention tests from
apache#24740
are unaffected.
<details>
<summary>Reproduction</summary>
`Cargo.toml`:
```toml
[package]
name = "sortrepro"
version = "0.1.0"
edition = "2024"
[dependencies]
datafusion = { git = "https://github.com/apache/datafusion", default-features = false }
tokio = { version = "1", features = ["rt-multi-thread"] }
futures = "0.3"
```
`src/main.rs`, run as `sortrepro <sort_spill_reservation_bytes> <runs>`:
```rust
//! A window over a spilling sort, 10 partitions, one FairSpillPool.
//! Usage: sortrepro <sort_spill_reservation_bytes> <runs>
use std::sync::Arc;
use datafusion::arrow::array::{Decimal256Array, Int32Array, RecordBatch};
use datafusion::arrow::datatypes::{DataType, Field, Schema, SchemaRef, i256};
use datafusion::catalog::streaming::StreamingTable;
use datafusion::common::ScalarValue;
use datafusion::functions_aggregate::expr_fn::max;
use datafusion::functions_aggregate::sum::sum_udaf;
use datafusion::logical_expr::expr::WindowFunction;
use datafusion::logical_expr::{
Expr, ExprFunctionExt, WindowFrame, WindowFrameBound, WindowFrameUnits,
WindowFunctionDefinition, col,
};
use datafusion::execution::memory_pool::FairSpillPool;
use datafusion::execution::runtime_env::RuntimeEnvBuilder;
use datafusion::execution::{SendableRecordBatchStream, TaskContext};
use datafusion::physical_plan::stream::RecordBatchStreamAdapter;
use datafusion::physical_plan::streaming::PartitionStream;
use datafusion::prelude::{SessionConfig, SessionContext};
const ROWS: i32 = 6_666_815;
const BATCH: i32 = 8192;
const POOL: usize = 65_484_800; // 62.5 MB
/// (g, k, p): 1000 groups of increasing k, with a decimal to sum.
#[derive(Debug)]
struct Gen(SchemaRef);
impl PartitionStream for Gen {
fn schema(&self) -> &SchemaRef {
&self.0
}
fn execute(&self, _: Arc<TaskContext>) -> SendableRecordBatchStream {
let schema = Arc::clone(&self.0);
let s = Arc::clone(&schema);
let batches = (0..(ROWS + BATCH - 1) / BATCH).map(move |b| {
let (lo, hi) = (b * BATCH, ((b + 1) * BATCH).min(ROWS));
let k: Vec<i32> = (lo..hi).map(|i| i * 3).collect();
let g: Vec<i32> = k.iter().map(|k| k % 1000).collect();
let p: Vec<i256> = k
.iter()
.map(|k| i256::from_i128((*k as i128 * 7919) % 10_000_000))
.collect();
let p = Decimal256Array::from(p).with_precision_and_scale(76, 2)?;
Ok(RecordBatch::try_new(
Arc::clone(&s),
vec![
Arc::new(Int32Array::from(g)),
Arc::new(Int32Array::from(k)),
Arc::new(p),
],
)?)
});
Box::pin(RecordBatchStreamAdapter::new(
schema,
futures::stream::iter(batches),
))
}
}
async fn run(sort_spill_reservation_bytes: usize) -> datafusion::error::Result<()> {
let mut config = SessionConfig::new()
.with_target_partitions(10)
.with_batch_size(BATCH as usize);
config.options_mut().execution.sort_spill_reservation_bytes =
sort_spill_reservation_bytes;
let runtime = RuntimeEnvBuilder::new()
.with_memory_pool(Arc::new(FairSpillPool::new(POOL)))
.build_arc()?;
let ctx = SessionContext::new_with_config_rt(config, runtime);
let schema = Arc::new(Schema::new(vec![
Field::new("g", DataType::Int32, false),
Field::new("k", DataType::Int32, false),
Field::new("p", DataType::Decimal256(76, 2), false),
]));
let table = StreamingTable::try_new(
Arc::clone(&schema),
vec![Arc::new(Gen(schema))],
)?;
// SELECT max(s) FROM (SELECT sum(p) OVER (PARTITION BY g ORDER BY k
// ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS s FROM t)
let s = Expr::from(WindowFunction::new(
WindowFunctionDefinition::AggregateUDF(sum_udaf()),
vec![col("p")],
))
.partition_by(vec![col("g")])
.order_by(vec![col("k").sort(true, false)])
.window_frame(WindowFrame::new_bounds(
WindowFrameUnits::Rows,
WindowFrameBound::Preceding(ScalarValue::UInt64(None)),
WindowFrameBound::CurrentRow,
))
.build()?
.alias("s");
ctx.read_table(Arc::new(table))?
.window(vec![s])?
.aggregate(vec![], vec![max(col("s"))])?
.collect()
.await?;
Ok(())
}
fn main() {
let args: Vec<String> = std::env::args().collect();
let reservation: usize = args[1].parse().unwrap();
let runs: usize = args[2].parse().unwrap();
let rt = tokio::runtime::Builder::new_multi_thread()
.worker_threads(10)
.enable_all()
.build()
.unwrap();
let mut ok = 0;
for _ in 0..runs {
match rt.block_on(run(reservation)) {
Ok(()) => ok += 1,
Err(e) => println!("{e}"),
}
}
println!("sort_spill_reservation_bytes={reservation}: {ok} / {runs} succeeded");
}
```
</details>
## Are there any user-facing changes?
No API changes. A sort that spills to many runs may merge in more passes
when
the pool is shared, instead of failing other consumers of the pool.1 parent 6c42917 commit adffd19
4 files changed
Lines changed: 557 additions & 9 deletions
File tree
- datafusion/physical-plan/src/sorts
- sort
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
15 | 15 | | |
16 | 16 | | |
17 | 17 | | |
18 | | - | |
| 18 | + | |
19 | 19 | | |
20 | 20 | | |
21 | 21 | | |
| |||
28 | 28 | | |
29 | 29 | | |
30 | 30 | | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
31 | 49 | | |
32 | 50 | | |
33 | 51 | | |
| |||
148 | 166 | | |
149 | 167 | | |
150 | 168 | | |
| 169 | + | |
| 170 | + | |
| 171 | + | |
| 172 | + | |
| 173 | + | |
151 | 174 | | |
152 | 175 | | |
153 | 176 | | |
| |||
191 | 214 | | |
192 | 215 | | |
193 | 216 | | |
| 217 | + | |
194 | 218 | | |
195 | 219 | | |
196 | 220 | | |
| |||
216 | 240 | | |
217 | 241 | | |
218 | 242 | | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
| 247 | + | |
| 248 | + | |
| 249 | + | |
| 250 | + | |
| 251 | + | |
| 252 | + | |
| 253 | + | |
219 | 254 | | |
220 | 255 | | |
221 | 256 | | |
| |||
584 | 619 | | |
585 | 620 | | |
586 | 621 | | |
| 622 | + | |
| 623 | + | |
| 624 | + | |
| 625 | + | |
| 626 | + | |
| 627 | + | |
| 628 | + | |
| 629 | + | |
| 630 | + | |
| 631 | + | |
| 632 | + | |
| 633 | + | |
| 634 | + | |
| 635 | + | |
587 | 636 | | |
588 | 637 | | |
589 | 638 | | |
| |||
609 | 658 | | |
610 | 659 | | |
611 | 660 | | |
612 | | - | |
| 661 | + | |
| 662 | + | |
| 663 | + | |
| 664 | + | |
| 665 | + | |
| 666 | + | |
| 667 | + | |
| 668 | + | |
| 669 | + | |
| 670 | + | |
| 671 | + | |
| 672 | + | |
| 673 | + | |
| 674 | + | |
613 | 675 | | |
614 | 676 | | |
615 | 677 | | |
| |||
677 | 739 | | |
678 | 740 | | |
679 | 741 | | |
680 | | - | |
| 742 | + | |
681 | 743 | | |
682 | 744 | | |
683 | 745 | | |
| |||
977 | 1039 | | |
978 | 1040 | | |
979 | 1041 | | |
980 | | - | |
| 1042 | + | |
981 | 1043 | | |
982 | 1044 | | |
983 | 1045 | | |
| |||
1474 | 1536 | | |
1475 | 1537 | | |
1476 | 1538 | | |
| 1539 | + | |
| 1540 | + | |
| 1541 | + | |
| 1542 | + | |
| 1543 | + | |
| 1544 | + | |
| 1545 | + | |
| 1546 | + | |
| 1547 | + | |
| 1548 | + | |
| 1549 | + | |
| 1550 | + | |
| 1551 | + | |
| 1552 | + | |
| 1553 | + | |
| 1554 | + | |
| 1555 | + | |
| 1556 | + | |
| 1557 | + | |
| 1558 | + | |
| 1559 | + | |
| 1560 | + | |
| 1561 | + | |
| 1562 | + | |
| 1563 | + | |
| 1564 | + | |
| 1565 | + | |
| 1566 | + | |
| 1567 | + | |
| 1568 | + | |
| 1569 | + | |
| 1570 | + | |
| 1571 | + | |
| 1572 | + | |
| 1573 | + | |
| 1574 | + | |
| 1575 | + | |
| 1576 | + | |
| 1577 | + | |
| 1578 | + | |
| 1579 | + | |
| 1580 | + | |
| 1581 | + | |
| 1582 | + | |
| 1583 | + | |
| 1584 | + | |
| 1585 | + | |
| 1586 | + | |
| 1587 | + | |
| 1588 | + | |
| 1589 | + | |
| 1590 | + | |
| 1591 | + | |
| 1592 | + | |
| 1593 | + | |
| 1594 | + | |
| 1595 | + | |
| 1596 | + | |
| 1597 | + | |
| 1598 | + | |
| 1599 | + | |
| 1600 | + | |
| 1601 | + | |
| 1602 | + | |
| 1603 | + | |
| 1604 | + | |
| 1605 | + | |
| 1606 | + | |
| 1607 | + | |
| 1608 | + | |
| 1609 | + | |
| 1610 | + | |
| 1611 | + | |
| 1612 | + | |
| 1613 | + | |
| 1614 | + | |
| 1615 | + | |
| 1616 | + | |
| 1617 | + | |
| 1618 | + | |
| 1619 | + | |
| 1620 | + | |
| 1621 | + | |
| 1622 | + | |
| 1623 | + | |
| 1624 | + | |
| 1625 | + | |
| 1626 | + | |
| 1627 | + | |
| 1628 | + | |
| 1629 | + | |
| 1630 | + | |
| 1631 | + | |
| 1632 | + | |
| 1633 | + | |
| 1634 | + | |
| 1635 | + | |
| 1636 | + | |
| 1637 | + | |
| 1638 | + | |
| 1639 | + | |
| 1640 | + | |
| 1641 | + | |
| 1642 | + | |
| 1643 | + | |
| 1644 | + | |
| 1645 | + | |
| 1646 | + | |
| 1647 | + | |
| 1648 | + | |
| 1649 | + | |
| 1650 | + | |
| 1651 | + | |
| 1652 | + | |
| 1653 | + | |
| 1654 | + | |
| 1655 | + | |
| 1656 | + | |
| 1657 | + | |
| 1658 | + | |
| 1659 | + | |
| 1660 | + | |
| 1661 | + | |
| 1662 | + | |
| 1663 | + | |
| 1664 | + | |
| 1665 | + | |
| 1666 | + | |
| 1667 | + | |
| 1668 | + | |
| 1669 | + | |
| 1670 | + | |
| 1671 | + | |
| 1672 | + | |
| 1673 | + | |
| 1674 | + | |
| 1675 | + | |
| 1676 | + | |
| 1677 | + | |
| 1678 | + | |
| 1679 | + | |
| 1680 | + | |
| 1681 | + | |
| 1682 | + | |
| 1683 | + | |
| 1684 | + | |
| 1685 | + | |
| 1686 | + | |
| 1687 | + | |
| 1688 | + | |
| 1689 | + | |
| 1690 | + | |
| 1691 | + | |
| 1692 | + | |
| 1693 | + | |
| 1694 | + | |
| 1695 | + | |
| 1696 | + | |
| 1697 | + | |
| 1698 | + | |
| 1699 | + | |
| 1700 | + | |
| 1701 | + | |
| 1702 | + | |
| 1703 | + | |
| 1704 | + | |
| 1705 | + | |
| 1706 | + | |
| 1707 | + | |
| 1708 | + | |
| 1709 | + | |
| 1710 | + | |
| 1711 | + | |
| 1712 | + | |
| 1713 | + | |
| 1714 | + | |
| 1715 | + | |
| 1716 | + | |
| 1717 | + | |
1477 | 1718 | | |
1478 | 1719 | | |
1479 | 1720 | | |
| |||
0 commit comments