apache / apache/datafusion

External sort spill GC inflates deduplicated string views

Open
#23,564 0 comments 0 reactions 0 assignees View on GitHub
bug
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

### 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](https://docs.rs/arrow-array/latest/arrow_array/array/struct.GenericByteViewArray.html#method.gc):

> Note: this function does not attempt to canonicalize / deduplicate values. For this feature see [GenericByteViewBuilder::with_deduplicate_strings](https://docs.rs/arrow-array/latest/arrow_array/builder/struct.GenericByteViewBuilder.html#method.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:

```sql
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:

```bash
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:

```rust
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_

Contributor guide

Open the contributing guide

Research direction

Reproduce the issue with datafusion-cli using the provided COPY and low-memory EXPLAIN ANALYZE commands, then trace the external sort spill path where string views are processed with gc(). Compare the spill size with and without deduplicating through GenericByteViewBuilder, and verify that the explain output shows substantially lower spilled bytes without regressions.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering, performance
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
68/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.