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]

Reply via email to