External sort spill GC inflates deduplicated string views #23564

Describe the bug

A recent PR adjusted the way the spill sort works by running gc() on string views: http://github.com/apache/datafusion/pull/21633

While this did reduce the file size considerably in some cases, in other cases this has caused a regression in spill file sizes. Namely, a highly deduplicated string view, will inflate considerably as gc() by its contract does not deduplicate:

Note: this function does not attempt to canonicalize / deduplicate values. For this feature see GenericByteViewBuilder::with_deduplicate_strings.

I.e, in a production workload I saw, trying to sort ~1gb of compressed parquet data blew out to 73gb of spilled bytes....

This is especially bad because we are spilling because we are already under memory pressure already, and reading back those inflated spilled files increases memory usage at the worse possible time.

To Reproduce

Create a deduped parquet file using datafusion-cli:

COPY (
  SELECT value AS id,
         'container-id-' || lpad(CAST(value % 1000 AS VARCHAR), 50, '0') AS label
  FROM generate_series(1, 1000000)
) TO 'repro.parquet' STORED AS PARQUET;

This creates a ~1.3mb parquet file.

Sort it with a low memory limit and look at the explain output:

datafusion-cli -m 64M -c "EXPLAIN ANALYZE SELECT * FROM 'repro.parquet' ORDER BY id;"

You will see that the spilled bytes is significantly higher than the parquet file:

DataSourceExec: ... bytes_scanned=1.37 M, output_bytes=31.0 MB
SortExec: expr=[id@0 ASC NULLS LAST], preserve_partitioning=[false],
  output_rows=1.00 M, output_bytes=108.8 MB,
  spill_count=2, spilled_bytes=83.2 MB, spilled_rows=1.00 M

So in other words, a 1.3 MB parquet file spills to 83.2 MB

Expected behavior

Spilling does not allocate that much disk to spill a string view column.

We should really be using something like:

  let mut builder = GenericByteViewBuilder::with_capacity(array.len())
      .with_deduplicate_strings();
  for v in array.iter() { builder.append_option(v); }
  builder.finish()

With that in place, the spill bytes is much lower

Additional context

No response