adriangb opened a new issue, #24707:
URL: https://github.com/apache/datafusion/issues/24707
Follow-up from #24526.
That PR added `datafusion/pruning/benches/string_in_list_pruning.rs`,
comparing the compact sorted-domain form against the per-value OR tree. Several
follow-ups from the review need numbers the benchmark can't currently produce,
so it might be worth extending before tackling those.
What it covers today:
- `DOMAIN_SIZES = [20, 21, 256, 1024]`
- `CONTAINERS = 4096`, fixed
- values are `format!("key{index:08}")` — 11 bytes, differing within the
first few
- `Utf8View` column, all values distinct
Axes that might be worth adding:
- **Small N.** Nothing below 20, so we can't currently tell whether the
compact form is also better for small lists. Called out directly in review.
- **Container count.** Fixed at 4096. The compact form is roughly O(C·log N)
against the OR tree's O(C·N), so wherever a crossover in N sits, it probably
moves with C.
- **Value length and shared prefix.** `memcmp` short-circuits at the first
differing byte, so the current keys are close to best case. Domains with long
common prefixes — tenant-prefixed IDs, URLs from one host, UUIDs with a fixed
prefix — would exercise the case where sorting approaches O(N·L log N) and each
probe approaches O(L).
- **Input type.** `Utf8View` only. `Utf8`/`LargeUtf8`/dictionary each pay a
per-batch `cast()` that `Utf8View` doesn't, so today's numbers may be the
cheapest case.
- **Duplicate ratio.** All distinct today; real `IN` lists can be heavily
duplicated.
- **Non-string types**, if that work happens.
Not all of these are necessarily worth it — the first two are the ones other
follow-ups are actually waiting on.
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
