dtenedor opened a new pull request, #12282:
URL: https://github.com/apache/arrow-rs/pull/12282
# Which issue does this PR close?
None.
# Rationale for this change
When the `ArrowWriter` writes an Arrow dictionary array of strings or
binary, it updates the page
statistics by comparing every row's value with the running min and max: two
`memcmp` calls per
row. With the dictionary cache from #11982, interning is already one lookup
per row, so these
comparisons are now most of the cost. In
`string_dictionary_low_cardinality_20`, a dictionary of 20
values, `update_statistics` is 22-24% and `memcmp` 24-27% of the write.
A batch of rows can only reference values from the dictionary, so its min
and max are the min and
max of the values it references, however many rows reference each one.
# What changes are included in this PR?
`update_dictionary_statistics` marks the keys the batch's rows use, then
compares each referenced
dictionary value once. It is used when the dictionary has no more values
than the batch has rows:
then some rows must repeat a value, and the pass over the dictionary's flags
is no longer than the
batch.
The per-row computation is kept for:
- larger dictionaries, where the rows of a batch are mostly distinct anyway
- decimals: values that are numerically equal can have different bytes, and
which one becomes the
statistic depends on row order
- geospatial statistics
- a key outside the dictionary, which reads as an empty value
The statistics, and so the file, are unchanged.
# Are these changes tested?
A new test writes dictionary arrays of 1 to 100,000 values, with null keys
and null values, and
checks that each writes the same file bytes as its values cast to `Utf8`. It
passes before and after
this change. Output was also checked to be byte-identical to main's for 288
more dictionary array
files:
- `Int8`, `Int16` and `Int32` keys
- `Utf8` and `Binary` values, with duplicate and empty values
- 1 to 20,000 dictionary values
- small batch and page sizes, and dictionary encoding turned off
`arrow_writer` bench, Intel Xeon Platinum 8559C, default x86-64 target,
median of 5 alternating
rounds:
| `arrow_writer` bench | main | PR | Speedup |
| :--- | ---: | ---: | ---: |
| `string_dictionary_low_cardinality_20/default` | 8.254 ms | 3.296 ms |
2.50x |
| `string_dictionary_low_cardinality_100/default` | 8.245 ms | 3.725 ms |
2.21x |
| `string_dictionary_low_cardinality_400/default` | 8.465 ms | 5.188 ms |
1.63x |
| the three above with `parquet_2` | | | 2.50x / 2.20x / 1.65x |
| `string_dictionary_1pct_cardinality` (10K values, per-row path) | | |
1.05-1.06x |
| `string_dictionary` (per-row path) | | | 0.98-1.01x |
| `string`, `string_non_null`, `short_string_non_null` (not dictionary
arrays) | | | 0.98-1.01x |
An earlier version used the shortcut for dictionaries up to 16 times the
batch. It made
`string_dictionary_1pct_cardinality` 0.61x, because its batches reference
nearly 1,024 distinct
values out of 10,000, and every batch scanned all 10,000 flags. Collecting
keys as they are first
seen instead brought that case to 0.87x, but lowered the low-cardinality
gains, to 2.13x for 20
values.
Limiting the shortcut to dictionaries no larger than the batch avoids both.
None of the measured inputs got slower. The 0.98x results are on paths this
change doesn't affect.
Not measured on aarch64.
# Are there any significant user-facing changes?
No.
# AI usage disclosure
An AI coding agent (Claude Code) generated the code, the test and this
description, and ran the
benchmarks and the output checks. This PR is a draft until the submitter has
reviewed it.
This pull request and its description were written by Isaac.
--
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]