adriangb opened a new pull request, #10882:
URL: https://github.com/apache/arrow-rs/pull/10882
# Which issue does this PR close?
- Closes #10881.
# Rationale for this change
`VariantMetadata::get_entry` resolves a field name to a field id by
searching the
dictionary, decoding and comparing dictionary strings as it goes (linear for
an
unsorted dictionary, logarithmic for a large sorted one).
Several paths copy fields out of a variant object and back into a builder
that
shares that object's metadata dictionary. `shred_variant` writes every field
the
shredding schema does not cover into the leftover `value` column, and
projection
paths do the same. In all of them the field name handed to the builder came
from
`VariantObject::iter`, which produced it by looking up a field id in that
very
dictionary. Searching for it by name is a round trip: the id was already
known,
and the search spends string comparisons recovering it.
`ReadOnlyMetadataBuilder` has a `known_field_names` cache intended to absorb
this
cost, but it cannot help here. `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, never serving a lookup, and each
row
pays to hash names it will never see again.
In a CPU profile of the `shred_variant_unmatched_object_8k_rows` benchmark
added
here, `ReadOnlyMetadataBuilder::try_upsert_field_name` accounted for about
57% of
`shred_variant`. After this change it accounts for about 20%, and
`get_entry` no
longer appears in the hot path.
# What changes are included in this PR?
- `VariantMetadata::borrowed_field_id` (crate-private). A field name that is
a
slice of the dictionary's own value region already encodes its field id: it
belongs to the entry whose offset equals the name's distance from the
start of
that region. This finds the entry with a binary search over the offset
array,
comparing integers instead of decoding dictionary strings, and confirms
the hit
by comparing lengths rather than bytes.
A candidate is accepted only when it starts at the name's address and has
the
name's length, which makes the entry's bytes and the name's bytes the same
bytes. Anything else, including a name that borrows from elsewhere, a
slice of
an entry, or metadata with arbitrary offsets, falls back to the existing
search. Addresses are only ever compared as integers, never dereferenced.
Note that the offset array is monotonic regardless of whether the
dictionary is
sorted, so this binary search is available for unsorted dictionaries too,
where
`get_entry` itself can only search linearly.
- `VariantMetadata::get_entry` tries the above first, so all callers benefit.
Cost for callers this cannot help: `get_entry` is public, and a name that
does
not borrow from the dictionary now runs the address range check before the
existing search. That check short circuits on a failed comparison, so such
a
caller pays a few integer operations and nothing else. The one case that
pays
more is a name pointing into the value region without starting an entry,
for
example a substring of one: that costs a binary search over the offset
array
before falling back. Both are bounded, but I would rather state them than
have
them found in review.
- `ReadOnlyMetadataBuilder::try_upsert_field_name` tries it before consulting
`known_field_names`, so the paths described above do no hashing at all. The
cache still serves field names that do not borrow from the dictionary.
- `shred_variant` reuses one scratch buffer to track which shredded fields a
row
supplied, instead of allocating a `HashSet` per row.
- Two new benchmarks in `parquet-variant-compute/benches/variant_kernels.rs`
covering objects that the shredding schema matches partially and not at
all.
## One behavior note
The spec requires dictionary keys to be unique, and validation enforces that
for
sorted dictionaries. It does not enforce it for unsorted ones, so a
dictionary
that validates can still contain the same key twice. For such a dictionary,
`get_entry` previously returned the first matching id and now returns the id
the
borrowed name actually came from. Both ids name that same string, so a
returned
field id still always names the string the caller asked for, but the
specific id
can differ from before in that spec-violating case. I am happy to reject
duplicates during validation of unsorted dictionaries instead, or to fold
that
into a follow-up, if maintainers prefer.
# Are these changes tested?
Yes. New unit tests cover sorted and unsorted dictionaries, agreement
between the
borrowed lookup, `get_entry`, and lookups by an owned (non-borrowed) copy of
the
same name, names borrowed from a different dictionary that must not be
resolved
against this one, a slice of an entry that shares its start offset without
being
equal to it, and empty field names. The existing `parquet-variant`,
`parquet-variant-compute`, `parquet-variant-json`, proptest fuzz, and
`variant_interop` suites pass unchanged.
The two new benchmarks cover 8192 rows over a 300-entry dictionary with
15-field
objects. I am deliberately not posting timings yet. The machine available to
me is
heavily contended, and a paired interleaved probe there produced a 65% spread
within a single invocation on identical work, so any speedup figure from it
would
be indistinguishable from noise. I will follow up with numbers from a quiet
machine, measured with interleaved arms and with unaffected control
benchmarks
used to certify that the run is valid.
# Are there any user-facing changes?
No public API changes. `get_entry` keeps its signature and its contract that
a
returned field id names the requested string; see the behavior note above
for the
one case where the specific id it picks can differ.
--
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]
