Internal error in ExternalSorter when running with memory limit

[DerGut]

Describe the bug

When running a sort with a low memory limit, DataFusion can run into an internal error. I noticed this with the SHOW ALL; command, which is converted to SELECT name, value FROM information_schema.df_settings ORDER BY name and hence runs a sort.

To Reproduce

cargo run --bin=datafusion-cli -- -m=10m -c="show all"

Will error with

Error: Internal error: Should be called after `spill_append`.
This was likely caused by a bug in DataFusion's code and we would welcome that you file an bug report in our issue tracker

Note, that -m=20m will succeed again.

Expected behavior

I'd instead expect the sort to either work (if necessary with spilling) or to return a non-internal error that's actionable to the user.

Additional context

Tested this on main.

I'd be happy to dig a little bit deeper into this over the weekend :)

[DerGut]

I just noticed that for even lower settings of --memory-limit, I get a different error e.g.

Error: Resources exhausted: Failed to allocate additional 10485760 bytes for ExternalSorterMerge[0] with 0 bytes already allocated for this reservation - 9437184 bytes remain available for the total pool

with -m=9m.

My current suspicion is that the hard-coded

datafusion/datafusion/common/src/config.rs

Line 341 in 5ab5a03

pub sort_spill_reservation_bytes: usize, default = 10 * 1024 * 1024

clashes with memory limits configured to the same value in some way which then breaks assumptions in the sort code.

---

EDIT: confirmed that I get the same behavior with other memory limits, for as long as the memory limit matches sort_spill_reservation_bytes, e.g.:

DATAFUSION_EXECUTION_SORT_SPILL_RESERVATION_BYTES=20971520 cargo run --bin datafusion-cli -- --memory-limit=20m --command="SHOW all;"

[DerGut]

What I've found so far:

1. The amount of sort_spill_reservation_bytes is used to reserve memory for the merge
2. The followup sort reservation for the next batch fails because no memory is available (according to the configured limit)
3. The ExternalSorter tries to free up memory by sorting any in-memory records and spilling them to disk, but there aren't any (most of ExternalSorter::sort_and_spill_in_mem_batches becomes a noop)
4. The code errors when finishing the spill because it expects that something was spilled to disk...

What's happening on the happy path instead?

I'm only looking at scenarios that spill to disk, as this seems to be where the ExternalSorter is tripping up.

sort_spill_reservation_bytes > memory limit

The ExternalSorter already tries to reserve more memory for the merge than is available. It fails with

Error: Resources exhausted: Failed to allocate additional 10485760 bytes for ExternalSorterMerge[0] with 0 bytes already allocated for this reservation - 9437184 bytes remain available for the total pool

(not exactly a happy path but we get an error that makes sense to the user)

Other cases

Playing around with this more, I've also found the internal error popping up in some combinations of sort_spill_reservation_bytes < memory limit. I will need to look into this more tomorrow.

[2010YOUY01]

This analysis makes sense, IMO the condition to trigger this specific InternalError should be sort_spill_reservation_bytes + first batch's memory size < memory limit, the reproducing steps are:

1. Sort execution start, sort_spill_reservation_bytes is pre-reserved for later merge step
2. Reading first batch, there is not enough memory budget to hold the first batch
3. Spilling is triggered, but nothing has been written into the spill file -> InternalError

I think the fix (for a more user-friendly error message) would be

1. When sort_spill_reservation_byte reservation failed, the error message should include considering set the memory limit larger than this reservation memory size
2. For the code path triggered this internal error, return an ExecutionError instead with a similar error message

[DerGut]

You are right!

With v46.0.1, the ExternalSorter estimates 35840 bytes for the first record batch. Running with sort_spill_reservation_bytes + record batch size == memory limit:

DATAFUSION_EXECUTION_SORT_SPILL_RESERVATION_BYTES=512 cargo run --bin datafusion-cli -- --memory-limit=35840  --command="SHOW all;"

the command succeeds while running with --memory-limit=35839 (sort_spill_reservation_bytes + record batch size > memory limit) fails.

---

Including more actionable context in the error message makes a lot of sense to me. I'll put up a PR to change this behavior. Thanks a lot for looking into it 🙇