adriangb opened a new pull request, #10775:
URL: https://github.com/apache/arrow-rs/pull/10775
# Which issue does this PR close?
- Part of #9699.
This revives the direction of #9700 by @mzabaluev (closed as stale), whose
design discussion shaped this API: a configurable fallback *policy* enum with
per-variant parameters (as proposed by @etseidl in the #9700 discussion) rather
than a change to the default heuristics (per @alamb's feedback there). Full
credit to @mzabaluev for the prior art and the `DictionaryFallback` name.
# Rationale for this change
Today the writer abandons dictionary encoding for a column chunk as soon as
the dictionary page exceeds `dictionary_page_size_limit` (1 MiB default),
regardless of whether the dictionary is paying for itself. For columns whose
values are large but highly repetitive — e.g. multi-KiB metadata/payload blobs
where a few thousand distinct values recur throughout the file — a handful of
distinct values overflows the limit, and every subsequent repeat is written out
in full by the fallback encoding. Raising `dictionary_page_size_limit`
file-wide is a blunt instrument: it also grows dictionaries on columns where
the dictionary is *not* profitable, and the limit exists for a reason (readers
must decompress and materialize the entire dictionary page; the format allows
at most one dictionary page per column chunk, so it cannot be split).
This PR adds an opt-in policy that keeps the dictionary past the limit only
while it remains profitable:
```rust
#[non_exhaustive]
pub enum DictionaryFallback {
/// Fall back when the dictionary page exceeds
`dictionary_page_size_limit`.
/// (Current behavior; default.)
OnPageSizeLimit,
/// Keep the dictionary past `dictionary_page_size_limit` (the grace
floor)
/// while it stays profitable — dictionary page smaller than
`worth_ratio` ×
/// the PLAIN-encoded size of the values appended so far — falling back
/// unconditionally at `max_dictionary_page_size` (reader memory guard).
WhenProfitable { worth_ratio: f64, max_dictionary_page_size: usize },
}
```
The PLAIN-encoded size is a cheap, pessimistic upper bound for the fallback
encoding: the spec requires the delta encodings to not exceed PLAIN for the
same values (as noted by @etseidl and @mzabaluev in #9700). The profitability
estimate is documented as an implementation detail so a future PR can replace
it with a measured comparison without changing this API. Suggested opt-in
values: `worth_ratio: 0.1`, `max_dictionary_page_size: 64 * 1024 * 1024`.
**The default is `OnPageSizeLimit` and default output is bit-identical to
today.**
# What changes are included in this PR?
- `DictionaryFallback` enum in `file/properties.rs`, plumbed file-wide
(`set_dictionary_fallback`) and per-column (`set_column_dictionary_fallback`),
following the existing `dictionary_page_size_limit` pattern.
- Both dictionary encoders (the generic `DictEncoder` and the arrow
byte-array `DictEncoder`) accumulate the PLAIN-encoded size of appended values
(one add per value), exposed via a defaulted
`ColumnValueEncoder::estimated_plain_encoded_bytes`.
- `should_dict_fallback` implements the policy: hard cap first, then the
grace floor, then the profitability ratio; encoders with no estimate preserve
the absolute-limit behavior.
- Tests: explicit `OnPageSizeLimit` byte-identical to default properties on
fallback-triggering data; opt-in keeps the dictionary past the limit on a
repetitive column (no fallback-encoded pages, dictionary page present, less
than half the default-policy file size, roundtrip equality); the hard cap
forces fallback even when profitable; a high-cardinality Int64 column produces
byte-identical output to stock under the opt-in policy; property plumbing incl.
`into_builder()` roundtrip and `worth_ratio` validation.
# Benchmarks
Methodology: every file of each dataset is rewritten with `ArrowWriter`,
ZSTD level 1, otherwise default properties, with **only the fallback policy
differing between arms**; numbers are the sum of output file bytes over the
same file set.
## Repetitive large values (seeded reproducer)
A pool of 1000 distinct 16 KiB random blobs over 16384 rows × 4 files (seed
42), values recurring in short runs of 16 — bursty local repeats that recur
file-wide, farther apart than a codec window. Generator (pyarrow):
```python
import numpy as np, pyarrow as pa, pyarrow.parquet as pq, os, string
OUT = "repetitive_large_values_runs"
os.makedirs(OUT, exist_ok=True)
rng = np.random.default_rng(42)
alphabet = np.frombuffer(bytes(string.ascii_letters + string.digits,
"ascii"), dtype=np.uint8)
pool = ["".join(map(chr, rng.choice(alphabet, size=16384))) for _ in
range(1000)]
for f in range(4):
idx = np.repeat(rng.integers(0, 1000, size=1024), 16)
t = pa.table({
"id": pa.array(np.arange(f * 16384, (f + 1) * 16384), pa.int64()),
"key": pa.array(idx, pa.int64()),
"val": pa.array([pool[i] for i in idx], pa.string()),
})
pq.write_table(t, f"{OUT}/part-{f}.parquet", compression="zstd")
```
| Arm | Total bytes | vs stock |
|---|---:|---:|
| Stock (`OnPageSizeLimit`) | 50,874,519 | — |
| `WhenProfitable` (ratio 0.1, cap 64 MiB) | 31,186,188 | **−38.7%** |
| Dictionary disabled | ≈ stock | ≈ 0% |
Disabling dictionary encoding does not help here — every repeat is still
written in full — which addresses the "why not just disable the dictionary"
question from #9700: the win comes from *keeping* the dictionary, not from
avoiding it.
Known limitation (disclosed): with the same data uniformly shuffled, the
policy does not diverge from stock. The decision is made when the dictionary
crosses the grace floor (after ~64 values here), before any repeats are
visible, so the ratio test fails and the writer falls back exactly as stock
does. Fixing this requires deferring the decision until more values have been
sampled — future work below. Stock behaves identically on the shuffled data, so
this is a missed win, not a regression.
## ClickBench (hits_0..hits_29, ~4.1 GB of parquet)
| Arm | Total bytes | vs stock |
|---|---:|---:|
| Stock | 2,655,573,968 | — |
| `WhenProfitable` ratio 0.1 | 2,646,247,827 | −0.35% (no regressions) |
| `WhenProfitable` ratio 0.5 | 2,430,100,561 | −8.5% |
At ratio 0.5 the top movers are `Title` −143.4 MB, `URL` −70.5 MB, `Referer`
−38.9 MB; the regressions are `UserID` +13.2 MB and `FUniqID` +8.3 MB —
sorted/high-cardinality keys where DELTA_BINARY_PACKED beats a nominally
"profitable" dictionary. That regression class is exactly why the conservative
0.1 is the suggested default: PLAIN size is a pessimistic bound for the delta
fallbacks, so a small ratio keeps the policy honest where delta would win.
## Controls
- **TPC-H SF1**: ratio 0.1 is bit-identical to stock (0 diverged column
chunks). Ratio 0.5: +2.1% (`l_orderkey`/`ps_partkey`, the same sorted-key class
as above).
- **TPC-DS SF1**: ±0.04% at both ratios.
- **large_values** (unique 16 KiB values, no repetition): all arms
byte-identical — the policy is a strict no-op when dictionaries don't pay.
# Are there any user-facing changes?
New opt-in API: `DictionaryFallback` (marked `#[non_exhaustive]`),
`WriterPropertiesBuilder::set_dictionary_fallback` /
`set_column_dictionary_fallback`, `WriterProperties::dictionary_fallback` /
`column_dictionary_fallback`, and `DEFAULT_DICTIONARY_FALLBACK`. Default
behavior is unchanged (bit-identical output with default properties).
# Future work
- #9739: on fallback the writer eagerly dumps the oversized dictionary page
instead of re-encoding the already-buffered dictionary-encoded data — a
companion fix that makes falling back cheaper and is independent of this PR.
- #8378: sampling more values before deciding, which together with a
measured (rather than PLAIN-bounded) comparison would let a future
`DictionaryFallback` variant handle the shuffled-data case above without
changing this API.
🤖 Generated with [Claude Code](https://claude.com/claude-code)
--
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]
