Repository navigation
bench: add hj queries for partitioned joins on dense and sparse integer keys - #27090
Merged
Merged
Conversation
…er keys No hj query runs a `Partitioned` join on integer keys whose build side is large enough for a hash table or an `ArrayMap` per partition. So the suite does not measure how the build map type changes such a join. This adds two queries over TPC-H `orders`, joined to itself on `o_custkey` in `Partitioned` mode. Q26 builds from the orders of the first 40K customers: dense keys, about 10 rows per key. Q27 builds from customers whose key is a multiple of 37: sparse keys. Both probe 15M rows with about a 2.7% hit rate. The runner now also registers `orders`. Co-Authored-By: Claude Opus 5.5 <[email protected]>
This was referenced Nov 4, 2026
alamb
approved these changes
Nov 4, 2026
Contributor
Author
|
thanks @alamb |
vim89
pushed a commit
to vim89/datafusion
that referenced
this pull request
Nov 11, 2026
…h join filter (apache#27091) ## Which issue does this PR close? - This PR does not close an issue. It follows up on apache#26249, which merged the build partitions of a `Partitioned` hash join into one routed lookup. > [!NOTE] > Stacked on apache#27090, which adds the benchmark queries used below. Review only the last commit, `perf: route probe rows to ArrayMap build partitions in the merged filter`. ## Rationale for this change A `Partitioned` hash join on dense integer keys runs much slower with Parquet filter pushdown on than with it off. On TPC-H SF10 the `hj` Q26 join takes 93.5 ms with `pushdown_filters=true`, against 50.0 ms with it off. A similar join on sparse keys (Q27) does not slow down this way. The cause is the filter the join pushes into its probe-side scan. Each build partition of a dense-key join builds an `ArrayMap`. The routed lookup from apache#26249 accepts only hash tables, so these joins fall back to a `CASE` with one branch per partition. The scan evaluates that `CASE` on every row. ## What changes are included in this PR? The routed lookup now probes an `ArrayMap` partition with the key values of the rows routed to it, because an `ArrayMap` is keyed by value, not by hash. Every non-empty partition can now merge into the routed lookup. The `CASE` fallback remains only for canceled partitions. A follow-up PR removes it. ## What is the testing strategy for this PR? `routed_lookup_fuzz` now builds an `ArrayMap` for about half of its partitions. It compares the routed lookup with one lookup over the whole build side. All `datafusion-physical-plan` tests and all sqllogictests pass. `hj` on TPC-H SF10, 16 partitions, median of 10 iterations: | Query | `pushdown_filters` | `main` + apache#27090 | This PR | |---|---|---|---| | Q26 (dense keys) | `true` | 93.5 ms | 44.7 ms | | Q26 (dense keys) | `false` | 50.0 ms | 48.2 ms | | Q27 (sparse keys) | `true` | 59.2 ms | 57.3 ms | | Q27 (sparse keys) | `false` | 54.5 ms | 55.6 ms | Only Q26 with pushdown on changes. Its probe filter goes from `CASE hash_repartition % 16 WHEN 0 THEN ... hash_lookup ...` to one `hash_lookup`. ## Are there any user-facing changes? No API changes. A `Partitioned` hash join on dense integer keys runs faster when Parquet filter pushdown is on. 🤖 Generated with [Claude Code](https://claude.com/claude-code) --------- Co-authored-by: Claude Opus 5.5 <[email protected]>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Which issue does this PR close?
Partitionedhash join with dense integer keys filters its probe side.Rationale for this change
No
hjquery runs aPartitionedjoin on integer keys whose build partitions are too large for an IN list. Such a join builds anArrayMapper partition when the keys are dense, and a hash table when they are sparse. The suite has no query of either kind, so a change to how these joins filter the probe side has nothing to compare against.What changes are included in this PR?
One commit. It adds two
hjqueries over TPC-Horders, joined to itself ono_custkeyinPartitionedmode:Both probe 15M rows with about a 2.7% hit rate. The runner now also registers
orders. The queries set no Parquet options, so a caller can run them with or without filter pushdown, for example withDATAFUSION_EXECUTION_PARQUET_PUSHDOWN_FILTERS=true.What is the testing strategy for this PR?
The change adds benchmark queries only. I ran both queries on TPC-H SF10 (16 partitions, 10 iterations) and checked their plans: both use
HashJoinExec: mode=Partitioned. With pushdown on, Q26's probe scan gets a per-partition routed filter overArrayMappartitions, and Q27's gets a merged hash lookup.pushdown_filters=falsepushdown_filters=trueAre there any user-facing changes?
No.
🤖 Generated with Claude Code