parthchandra opened a new pull request, #7696:
URL: https://github.com/apache/datafusion-comet/pull/7696
## Which issue does this PR close?
Closes #5686.
## Rationale for this change
A shuffle written by many map tasks into many partitions gives each reduce
task one tiny Arrow batch per shuffle block. On a production job, about 330,000
map tasks write to 16,000 partitions, so each reduce task reads about 330,000
blocks of about 62 rows. When the native sort over that input spills, it is
extremely slow. In one task, `SortExec` took 16,778 s of `elapsed_compute` for
19.7 M rows and 5 spills, about 97% of the task. The shuffle read took 33 s.
The cause is DataFusion 55.2's `ExternalSorter`:
- When it spills, `sort_and_spill_in_mem_batches` calls
`in_mem_sort_stream(false, false)`, which does not combine buffered batches
into runs. Every buffered batch becomes its own merge stream, so a spill of
about 4 M rows merges about 66,000 streams.
- For every output batch, `BatchBuilder` calls arrow `interleave` over every
live input batch, for each column and each struct child. The cost per output
batch grows with the number of streams.
- Without spilling, DataFusion combines runs only for single-key sorts.
Multi-key sorts merge one stream per batch either way.
#5686 found the same problem and measured a large native gain. It was set
aside after an end-to-end run regressed by 11%. In that run each partition held
about 7,800 rows, under the 1 MiB `sort_in_place_threshold_bytes`, so the sort
never merged: it concatenated in place, and the extra `CoalesceBatchesExec` was
pure overhead. The issue also pointed out that the coalescer's buffers were not
charged to a memory pool. This PR follows the analysis in #5686 and addresses
both points.
## What changes are included in this PR?
- **`SortInputCoalesceExec`**
(`native/operators/src/sort_input_coalesce.rs`), a new operator in front of a
native `SortExec`:
- **Gate:** batches pass through unchanged until a task's sort input
reaches the sort's in-place threshold, counted the way the sort counts it.
Small sorts, the case that regressed in #5686, are unaffected.
- **Combining:** after the gate, batches with fewer rows than half of
`spark.comet.batchSize` and fewer than 512 are combined in arrival order. A
combined batch holds at most `spark.comet.batchSize` rows and half the in-place
threshold in bytes, 512 KiB by default, kept between 64 KiB and 4 MiB. The sort
then reserves no more for a combined batch than its own in-place threshold.
Input batches are never split.
- **Memory:** it reserves exactly what it holds, the batches plus the
combined copy, in a consumer that cannot spill. It releases the reservation
before the combined batch reaches the sort, so it holds nothing while the sort
reserves. If the pool refuses, it hands the group and the batch to the sort and
passes the next 64 small batches through before asking again. Errors other than
`ResourcesExhausted` are returned.
- **Never combined:** batches with a different schema start a new group.
Batches with small dictionary keys or small run-end types, at any nesting
depth, pass through, since concatenating them can overflow the key type. A
small slice of a large batch counts as large and passes through.
- **Metrics:** `coalesced_input_batches` and `coalesced_output_batches`
are reported under the sort. The operator's time is part of the sort's time.
- **Planner:** the `Sort` arm adds the coalescer only when
`Sort.coalesce_input` (a new proto field) is set, the sort has no fetch (TopK
never merges), and the input does not already satisfy the ordering (the sort
passes such input through). The semi-join key reduction in `join.rs` looks
through the coalescer and replaces it.
- **Config:** `spark.comet.exec.sort.coalesceInput.enabled`, on by default.
`CometSortExec` sets the proto field from it and declares the two metrics.
- **Docs:**
- The migration guide gets a 1.3.0 note.
- `metrics.md` gets a `CometSort` section.
- `memory_management.md` describes the reservation and the trade-off below.
- **Benchmark:** `native/operators/benches/sort_small_batches.rs`.
**Trade-off to review.** A combined batch is larger than the blocks it
replaces. A sort whose memory share is very close to the least it can run with
can now fail with "Not enough memory to continue external sort" where the tiny
blocks fit. The same is already true of any input that delivers full-size
batches. Halving the cap and holding nothing while the sort reserves made this
much narrower: in tight-pool sweeps, the coalesced sort spilled slightly less
than the plain one and never failed where it fit. It is documented, with the
config as the way out. The complete fix belongs in DataFusion, as a follow-up
below.
**Follow-ups, not in this PR:**
- In DataFusion, combine buffered batches into runs on the spill path,
within the memory budget. Also have `ExternalSorter` split a batch it cannot
reserve after spilling, instead of failing. Either would make this operator
unnecessary or safer.
- Hold the input before the gate without copying it, so the start of each
task's input is combined too.
## How are these changes tested?
- **Rust unit tests in `sort_input_coalesce.rs` (28):**
- **Gate and grouping:** pass-through below the gate without a copy; the
gate's byte counting; the row target, byte cap and 512-row limit; large batches
flushing the group first; empty, zero-row and zero-column batches.
- **Memory:** the reservation covers exactly the held batches and is
released; nothing is held while the sort receives a batch; a refused
reservation flushes the held group first; backoff and resumption; combining
when the pool fits the group but not a full one.
- **Errors and early drop:** an input error reaches the sort and releases
memory; dropping the stream early releases the reservation.
- **Batches never combined:** schema changes; small dictionary keys at the
top level, in a struct and in a list; slices of large batches.
- **Metrics:** a rebuilt node reports through the original's metrics.
- **Types:** a nested map, list and struct mix, decimal(38,10) at its
limits, years 1 and 9999, a time zone, CJK and other non-ASCII strings, and
dictionaries.
- **Spilling sorts:** single-key and multi-key spilling `SortExec`s give
identical output with and without the coalescer.
- **`CometFairMemoryPool` test (`fair_pool.rs`):** a sort whose fair share
is halved by a second spillable consumer spills and finishes with combined
input wherever it does without. It failed with the earlier 1 MiB cap.
- **Planner tests (4):** only a full sort over unordered input is wrapped,
with the session's batch size and threshold; a sort with only a `skip` is
wrapped; the semi-join key reduction replaces the coalescer.
- **`sql-tests/operators/sort_coalesce_input.sql`:** compared with Spark.
Each sort task reads blocks of about 12 rows.
- The data covers nested structs, maps and arrays of structs, decimal
bounds, dates, timestamps and timestamp_ntz from year 1 to 9999, and non-ASCII
strings.
- Sort keys include a single string key, multiple keys with both null
orderings, and a struct field.
- The config matrix covers the in-place threshold (0 and the default), a
normal and a tiny memory pool so the sort spills, and two session time zones.
- **`CometTaskMetricsSuite`:** a sort over 80 map tasks' small blocks spills
and matches Spark. With the config on it combines batches; with it off it does
not. The test checks metrics, which a SQL file cannot.
- **Micro-benchmark** `sort_small_batches`: 200,000 wide rows (fixed-length
string key, 8 longs, a struct, no nulls), one or two sort keys, in memory and
with a memory limit that forces spills, with keys scattered so every batch
spans the whole key range (poorly predicted) and with keys already in order
(the most predictable merge). Times in ms, raw -> combined, on a laptop with
about +/-10% run-to-run noise. Scattered keys:
| Rows per input batch | In memory, 1 key | In memory, 2 keys | Spilling, 1
key | Spilling, 2 keys |
| --- | --- | --- | --- | --- |
| 16 | 86.3 -> 51.9 | 330.2 -> 51.2 | 256.2 -> 79.3 | 258.2 -> 70.7 |
| 64 | 38.8 -> 31.9 | 97.5 -> 32.0 | 102.0 -> 58.6 | 97.7 -> 49.8 |
| 256 | 32.1 -> 29.7 | 45.1 -> 29.0 | 64.2 -> 57.4 | 62.6 -> 50.3 |
| 384 | 31.2 -> 28.3 | 38.7 -> 28.3 | 58.0 -> 57.0 | 55.3 -> 51.2 |
| 1024 (passed through) | 27.0 -> 27.2 | 31.0 -> 31.1 | 40.1 -> 42.7 | 48.3
-> 45.7 |
Keys already in order:
| Rows per input batch | In memory, 1 key | In memory, 2 keys | Spilling, 1
key | Spilling, 2 keys |
| --- | --- | --- | --- | --- |
| 16 | 66.2 -> 38.3 | 310.0 -> 47.1 | 221.0 -> 68.3 | 259.0 -> 73.2 |
| 64 | 29.2 -> 22.1 | 90.7 -> 26.9 | 76.6 -> 47.4 | 99.1 -> 56.2 |
| 256 | 19.7 -> 18.1 | 35.2 -> 23.4 | 44.7 -> 42.5 | 50.1 -> 48.2 |
| 1024 (passed through) | 16.9 -> 17.1 | 21.2 -> 20.9 | 34.5 -> 34.3 | 40.0
-> 47.2 |
When 512-row batches were combined, a spilling single-key sort got slower
(51.4 -> 54.0 ms), so the limit is fewer than 512 rows. Multi-key sorts gain
the most, even in memory, where DataFusion does not combine runs itself.
Cost: batches the coalescer passes through are unchanged, but the extra
operator is not free. With keys in order, spilling and two keys, 1024-row input
is about 7 ms (~18%) slower with the coalescer in place, with the same spill
count. An identity `ProjectionExec` in the same place costs the same (38.6 ->
44.3 ms), so this is the cost of one more operator between an in-memory source
and the sort, not of the coalescer's work. In a Comet plan the sort's input is
already a shuffle reader or scan. Sorts whose input is declared in order are
not wrapped. In the TPC-H runs below, total time did not get worse; q7 is the
one query where it might show.
- **End-to-end:** TPC-H SF100 on one machine (Spark 4.0 standalone, 2
executors x 8 cores), with `spark.comet.exec.sort.coalesceInput.enabled` off
and on, `spark.sql.shuffle.partitions=2000` and AQE partition coalescing off,
at 16g and at 2g off-heap. Three iterations each; times are the average.
| Off-heap | Off (s) | On (s) | Change | Failed tasks, on |
| --- | --- | --- | --- | --- |
| 16g | 1148.3 | 1144.9 | -0.3% | 0 |
| 2g | 1257.7 | 1234.8 | -1.8% | 0 |
- The coalescer combined batches in q3, q4, q9, q10 and q21, including
about 8.4 M small batches in q9 and 5.2 M in q10. Those queries changed by 1%
or less: their sorts did not spill and are not where the time goes. TPC-H does
not reach the spill-heavy sort over tiny blocks that #5686 describes, so this
run shows that the change costs nothing on a standard workload, not the
speed-up.
- No query failed with the coalescer on, and spill counts did not change.
The only failures were in the run with it off: an executor was lost during one
q5 iteration (256.8 s against about 87 s for the others), which is left out of
the 16g "off" total above (1204.9 s with it).
- q11 (about 3 s or 25 s per iteration whatever the setting) and q12 (82
to 112 s) vary too much between iterations to compare. q7 was about 10% slower
with the coalescer on at 16g, though nothing was combined there. That could be
the cost of the extra operator described above, or noise; three iterations do
not separate the two.
--
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]