adriangb opened a new issue, #10881:
URL: https://github.com/apache/arrow-rs/issues/10881
### Is your feature request related to a problem or challenge?
Several `parquet-variant` and `parquet-variant-compute` paths copy fields
out of a
variant object and into a builder that shares that object's metadata
dictionary.
`shred_variant` does this for every field the shredding schema does not
cover,
writing it into the leftover `value` column, and projection paths do the
same.
In all of these, the field name being inserted came from
`VariantObject::iter`,
which produced it by looking up a field id in that dictionary. Handing that
name
to the builder makes it search the dictionary again, by string, to recover
the id
it already had. `VariantMetadata::get_entry` decodes and compares dictionary
entries as it searches, linearly for an unsorted dictionary and
logarithmically
for a large sorted one.
`ReadOnlyMetadataBuilder` carries a `known_field_names` cache meant to absorb
this, but it does not help in the array-building case.
`VariantValueArrayBuilder::builder_ext` constructs a fresh
`ReadOnlyMetadataBuilder` per value, so in a per-row builder the cache is
populated and dropped again on every row without ever serving a lookup, and
each
row additionally pays to hash names it will never see again.
The cost is significant for wide objects over a large dictionary. In a CPU
profile of a shredding benchmark over 8192 rows with 15-field objects and a
300-entry dictionary, `ReadOnlyMetadataBuilder::try_upsert_field_name`
accounted
for roughly 57% of time spent in `shred_variant`.
### Describe the solution you'd like
Recognize the case where the field name is a slice of the dictionary's own
value
region. Such a name already encodes its field id: it belongs to the entry
whose
offset equals the name's distance from the start of that region. That id can
be
recovered with a binary search over the offset array, comparing integers,
with no
string decoding or comparison at all.
The offset array is monotonic whether or not the dictionary is sorted, so
this
also gives unsorted dictionaries a logarithmic path where `get_entry` can
only
search linearly today.
The candidate has to be verified so this can never disagree about which
string a
field id names. Checking that the entry starts at the name's address and has
the
name's length is sufficient, and makes any other input, including a name
borrowed
from elsewhere or a slice of an entry, fall back to the existing search.
### Describe alternatives you've considered
- Making the `known_field_names` cache outlive a single row. This requires an
`unsafe` lifetime recast of the `HashMap`, since its keys borrow from the
metadata, and still needs correct invalidation when the metadata changes.
- Keying a cache on the metadata's pointer identity. This has an ABA hazard:
a
freed dictionary's address can be reused by a different one.
Both are more invasive and harder to justify than removing the need for the
lookup on this path.
### Additional context
I have a change implementing this and will open a PR referencing this issue.
One related question for maintainers: validation enforces dictionary key
uniqueness only on the `is_sorted` branch, so an unsorted dictionary
containing
the same key twice currently passes full validation even though the spec
requires
keys to be unique. Any change here interacts with that, since two entries can
name the same string. Happy to tighten unsorted validation separately if
that is
wanted.
--
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]
