You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "andygrove (via GitHub)" <gi...@apache.org> on 2026/10/17 15:30:30 UTC
[PR] perf: store the build rows of repeated hash join keys together [datafusion]
andygrove opened a new pull request, #26447:
URL: https://github.com/apache/datafusion/pull/26447
## Which issue does this PR close?
- Part of #17494.
## Rationale for this change
When a build-side key repeats, `HashJoinExec` keeps the build rows of each key in a chain: the map holds the first
row and `next[row]` the one after it. A probe row follows the chain with one load for every match, and each load
depends on the one before, so nothing overlaps them. Once the build side no longer fits in the cache, most of those
loads are misses. That is what makes joins with many build rows per key, such as the join of `catalog_sales` and
`inventory` in TPC-DS q72, several times slower than a sort-merge join: in the reproduction posted on #17494,
85% of the hash join's samples are in `ArrayMap::get_matched_indices_with_limit_offset`, with `traverse_chain`
inlined into it.
## What changes are included in this PR?
The build rows of each repeated key are stored next to each other, so that a probe row reads its matches in order:
- `ArrayMap` groups the rows by key with a counting sort when some key repeats: the rows of the key in `slot` are
`rows[starts[slot]..starts[slot + 1]]`. It uses the same memory as the chain, one slot array and one index per
build row.
- `JoinHashMapU32` and `JoinHashMapU64` group the rows after the last build batch is inserted, when the hash values
have at least two rows each on average. The map then holds the position of each hash value's group, which starts
with its number of rows, and the chain is freed. The groups take one more index per distinct hash value than the
chain. The build reserves that memory first, and keeps the chain if it cannot.
- Grouping follows 16 chains at once, so that their loads overlap. Following one chain at a time cost about 75 ns a
build row. It holds up to 4096 rows of each chain until the chain ends, and measures longer chains to place them
in a second pass, so that it holds at most 16 x 4096 indices besides the groups.
- The probe copies a probe row's matches with one slice copy (`emit_grouped_rows`). `ProbeOffset::MidChain::next`
is then the position in the groups to resume from.
Matches come out in the same order as before, so the join's output does not change.
## Benchmarks
`datafusion-cli` (`release-nonlto`) on an AMD 7950X3D (16 cores), two runs each.
The reproduction from #17494: 64M build rows over 640K keys, about 100 rows per key, 96M probe rows and a residual
filter that keeps 6% of the 9.6B candidate pairs, with 16 partitions:
| Keys | main | this PR | Sort-merge join, for reference |
| ------------------------------ | -------------- | -------------- | ------------------------------ |
| Dense (`ArrayMap`) | 59.1 s, 60.0 s | 17.4 s, 17.6 s | 10.4 s to 11.8 s |
| Sparse (`JoinHashMap`) | 76.4 s, 75.5 s | 33.5 s, 33.2 s | 9.4 s to 13.4 s |
| Unique, dense, 64M build rows | 1.79 s, 1.61 s | 1.77 s, 1.63 s | |
| Unique, sparse, 64M build rows | 1.82 s, 1.62 s | 1.78 s, 1.68 s | |
What grouping costs when there is little to probe: the same 64M build rows, and 16K probe rows:
| Keys | main | this PR |
| ---------------------- | --------------------- | --------------------- |
| Dense (`ArrayMap`) | 0.489, 0.373, 0.379 s | 0.574, 0.421, 0.478 s |
| Sparse (`JoinHashMap`) | 0.686, 0.458, 0.485 s | 0.737, 0.571, 0.566 s |
`dfbench hj` on TPC-H SF10, the median of 12 iterations over three runs that alternate between main and this PR.
The benchmark turns off join reordering, so Q4 to Q15 build on `lineitem`, about 600 rows per key, and probe
`supplier`. Where every probe row matches (Q5, Q7, Q9, Q11 and Q13) they are 15% to 34% faster, and the high fan-out
queries Q22 to Q25 are 11% to 22% faster. Where 10% of the probe rows match (Q4 to Q14, even), the probe returns too
few matches to pay for grouping 60M build rows, and they are 1% to 10% slower. The other queries are within 6%.
<details>
<summary>All 25 queries</summary>
| Query | Scenario | main ms | this PR ms | Change |
| ----- | ------------------------------------------------------------------- | ------- | ---------- | ------ |
| Q1 | density=1 prob hit=1 25*1.5M | 3.0 | 3.1 | +2% |
| Q2 | density=0.026 prob hit=1 25*1.5M | 6.7 | 6.9 | +2% |
| Q3 | density=1 prob hit=1 100K*60M | 53.4 | 52.2 | -2% |
| Q4 | density=1 prob hit=0.1 100K*60M | 208.3 | 215.5 | +3% |
| Q5 | density=0.75 prob hit=1 100K*60M | 407.8 | 267.1 | -34% |
| Q6 | density=0.75 prob hit=0.1 100K*60M | 254.2 | 256.7 | +1% |
| Q7 | density=0.5 prob hit=1 100K*60M | 398.8 | 261.5 | -34% |
| Q8 | density=0.5 prob hit=0.1 100K*60M | 248.9 | 254.5 | +2% |
| Q9 | density=0.2 prob hit=1 100K*60M | 398.6 | 266.6 | -33% |
| Q10 | density=0.2 prob hit=0.1 100K*60M | 251.3 | 259.2 | +3% |
| Q11 | density=0.1 prob hit=1 100K*60M | 402.1 | 277.3 | -31% |
| Q12 | density=0.1 prob hit=0.1 100K*60M | 252.2 | 262.9 | +4% |
| Q13 | density=0.01 prob hit=1 100K*60M | 479.7 | 407.4 | -15% |
| Q14 | density=0.01 prob hit=0.1 100K*60M | 279.5 | 308.4 | +10% |
| Q15 | density=0.2 prob hit=0.1 100K (20% dups)*60M | 221.0 | 215.8 | -2% |
| Q16 | density=1 prob hit=1 25*1.5M RightSemi | 3.7 | 3.6 | -2% |
| Q17 | density=1 prob hit=1 100K*60M RightSemi | 56.4 | 55.4 | -2% |
| Q18 | density=1 prob hit=0.1 100K*60M RightSemi | 57.7 | 54.4 | -6% |
| Q19 | density=1 prob hit=1 25*1.5M RightAnti | 3.0 | 3.0 | +2% |
| Q20 | density=1 prob hit=1 100K*60M RightAnti | 43.1 | 43.9 | +2% |
| Q21 | density=1 prob hit=0.1 100K*60M RightAnti | 67.5 | 64.9 | -4% |
| Q22 | density=1 prob hit=0.01 100K (fanout 100)*60M RightSemi | 47.6 | 42.5 | -11% |
| Q23 | density=1 prob hit=1 32K (fanout~78)*2.3M long keys count | 114.8 | 92.9 | -19% |
| Q24 | density=1 prob hit=1 3K (single hot bucket)*20K long keys count | 308.7 | 241.2 | -22% |
| Q25 | density=1 prob hit=1 20K (fanout~78 multi key)*240K multi key count | 176.0 | 152.7 | -13% |
</details>
The `hash_join_probe` criterion benchmark, whose build keys are unique, is within 2% of main for 11 of its 13
cases, as close as two runs of main are to each other. `right_semi_clustered_10pct` was 5% slower and
`right_semi_sparse_100k_all_hit` 6% to 8% slower, in a single run.
## What is the testing strategy for this PR?
- New unit tests compare grouped maps with the chain or with a brute-force result: `JoinHashMapU32` and
`JoinHashMapU64` with rows inserted in batches from the last to the first and one row left out, as for a NULL key,
probed with limits from 1 to 8192 and with NULL probe keys, and `ArrayMap` with repeated, NULL and out of range
keys. Others cover chains long enough for the second pass of grouping, the size of the groups, the memory freed,
and that short chains are not grouped.
- The existing hash join tests, the join fuzz tests (`--features extended_tests`), the join and memory limit tests
of `core_integration`, and all sqllogictests pass, with grouping on wherever keys repeat.
## Are there any user-facing changes?
No. `JoinHashMapType`, which is public for internal use only, gains `grouped_rows_size` and `group_rows`, both with
default implementations.
## Notes for reviewers
- Most of what is left of the gap to the sort-merge join in the reproduction is gathering build columns at the
matched rows, which are scattered across the build batch. Ordering the build batch by key would make that
sequential too, but it changes the order of build-side output for outer, semi and anti joins, so it is not part
of this PR.
- Grouping is decided at build time. Deciding it from how much the probe has followed chains would avoid the cost
when the probe side is small, but the map is shared across probe streams in `CollectLeft` mode, and would need
interior mutability and memory accounting during the probe.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6251247997
run benchmarks
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "comphead (via GitHub) via github" <gi...@datafusion.apache.org>.
comphead commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6532278515
run benchmark tpch10 hj
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "andygrove (via GitHub) via github" <gi...@datafusion.apache.org>.
andygrove commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6952082686
Thanks for the suggestion, Adrian. I split this into #27528 (benchmark) β #27530 (hash maps) β this PR (`ArrayMap`). Review threads from here still apply.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "comphead (via GitHub) via github" <gi...@datafusion.apache.org>.
comphead commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6532277110
> Looks like we might need a rebase or something to get benches running?
Updated, not sure why benches failed, there was no error π€
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6530446483
Looks like we might need a rebase or something to get benches running?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6251330865
π€ Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/26447#issuecomment-6251247997)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
Comparing perf-hash-join-flat-chains (80c53008bb28094009845fce18a214f256e83ef3) to 484183d (merge-base) [diff](https://github.com/apache/datafusion/compare/484183dc34ea565190d9cd4a66db6d24789f95d0..80c53008bb28094009845fce18a214f256e83ef3)
<details><summary>Run configuration</summary>
```yaml
run benchmark tpch
```
</details>
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
Comparing HEAD and perf-hash-join-flat-chains
--------------------
Benchmark tpch_sf1.json
--------------------
βββββββββββββ³βββββββββββ³βββββββββββββββββββββββββββββ³ββββββββββββ
β Query β HEAD β perf-hash-join-flat-chains β Change β
β‘ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β QQuery 1 β 41.74 ms β 42.53 ms β no change β
β QQuery 2 β 19.12 ms β 19.07 ms β no change β
β QQuery 3 β 29.37 ms β 30.34 ms β no change β
β QQuery 4 β 17.95 ms β 18.09 ms β no change β
β QQuery 5 β 36.99 ms β 37.94 ms β no change β
β QQuery 6 β 14.32 ms β 14.82 ms β no change β
β QQuery 7 β 44.25 ms β 46.20 ms β no change β
β QQuery 8 β 43.45 ms β 43.19 ms β no change β
β QQuery 9 β 54.05 ms β 53.88 ms β no change β
β QQuery 10 β 43.46 ms β 42.96 ms β no change β
β QQuery 11 β 14.54 ms β 14.82 ms β no change β
β QQuery 12 β 19.10 ms β 19.51 ms β no change β
β QQuery 13 β 45.56 ms β 46.14 ms β no change β
β QQuery 14 β 25.71 ms β 26.60 ms β no change β
β QQuery 15 β 33.41 ms β 32.82 ms β no change β
β QQuery 16 β 14.57 ms β 14.72 ms β no change β
β QQuery 17 β 87.51 ms β 83.57 ms β no change β
β QQuery 18 β 48.80 ms β 48.76 ms β no change β
β QQuery 19 β 33.20 ms β 33.90 ms β no change β
β QQuery 20 β 33.98 ms β 35.12 ms β no change β
β QQuery 21 β 62.55 ms β 60.40 ms β no change β
β QQuery 22 β 15.20 ms β 15.05 ms β no change β
βββββββββββββ΄βββββββββββ΄βββββββββββββββββββββββββββββ΄ββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββ³βββββββββββ
β Benchmark Summary β β
β‘βββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β Total Time (HEAD) β 778.84ms β
β Total Time (perf-hash-join-flat-chains) β 780.42ms β
β Average Time (HEAD) β 35.40ms β
β Average Time (perf-hash-join-flat-chains) β 35.47ms β
β Queries Faster β 0 β
β Queries Slower β 0 β
β Queries with No Change β 22 β
β Queries with Failure β 0 β
βββββββββββββββββββββββββββββββββββββββββββββ΄βββββββββββ
Distribution per query (min / mean Β±stddev / max):
Comparing HEAD and perf-hash-join-flat-chains
--------------------
Benchmark tpch_sf1.json
--------------------
βββββββββββββ³βββββββββββββββββββββββββββββββββ³βββββββββββββββββββββββββββββββββ³βββββββββββββββ
β Query β HEAD β perf-hash-join-flat-chains β Change β
β‘βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β QQuery 1 β 41.74 / 42.56 Β±1.09 / 44.64 ms β 42.53 / 43.67 Β±0.62 / 44.27 ms β no change β
β QQuery 2 β 19.12 / 19.42 Β±0.20 / 19.70 ms β 19.07 / 19.69 Β±0.73 / 21.07 ms β no change β
β QQuery 3 β 29.37 / 29.93 Β±0.37 / 30.36 ms β 30.34 / 30.74 Β±0.29 / 31.23 ms β no change β
β QQuery 4 β 17.95 / 18.15 Β±0.17 / 18.42 ms β 18.09 / 18.78 Β±0.72 / 20.13 ms β no change β
β QQuery 5 β 36.99 / 37.60 Β±0.47 / 38.17 ms β 37.94 / 39.36 Β±1.58 / 42.43 ms β no change β
β QQuery 6 β 14.32 / 14.50 Β±0.15 / 14.72 ms β 14.82 / 15.57 Β±0.76 / 16.79 ms β 1.07x slower β
β QQuery 7 β 44.25 / 49.07 Β±3.83 / 53.84 ms β 46.20 / 48.83 Β±1.98 / 52.00 ms β no change β
β QQuery 8 β 43.45 / 44.71 Β±1.34 / 47.24 ms β 43.19 / 43.79 Β±0.57 / 44.87 ms β no change β
β QQuery 9 β 54.05 / 55.93 Β±1.04 / 56.89 ms β 53.88 / 54.60 Β±0.49 / 55.36 ms β no change β
β QQuery 10 β 43.46 / 44.44 Β±0.74 / 45.48 ms β 42.96 / 43.66 Β±0.78 / 45.16 ms β no change β
β QQuery 11 β 14.54 / 14.96 Β±0.46 / 15.84 ms β 14.82 / 15.12 Β±0.55 / 16.22 ms β no change β
β QQuery 12 β 19.10 / 19.57 Β±0.29 / 20.03 ms β 19.51 / 19.84 Β±0.33 / 20.35 ms β no change β
β QQuery 13 β 45.56 / 47.04 Β±1.24 / 49.21 ms β 46.14 / 47.59 Β±1.52 / 50.49 ms β no change β
β QQuery 14 β 25.71 / 26.08 Β±0.21 / 26.33 ms β 26.60 / 26.78 Β±0.21 / 27.18 ms β no change β
β QQuery 15 β 33.41 / 34.28 Β±0.68 / 35.10 ms β 32.82 / 34.17 Β±1.89 / 37.91 ms β no change β
β QQuery 16 β 14.57 / 14.90 Β±0.20 / 15.20 ms β 14.72 / 14.99 Β±0.25 / 15.46 ms β no change β
β QQuery 17 β 87.51 / 89.14 Β±1.37 / 91.37 ms β 83.57 / 87.10 Β±2.24 / 90.19 ms β no change β
β QQuery 18 β 48.80 / 50.00 Β±0.91 / 51.15 ms β 48.76 / 49.49 Β±0.47 / 49.99 ms β no change β
β QQuery 19 β 33.20 / 33.98 Β±0.77 / 35.42 ms β 33.90 / 34.53 Β±0.66 / 35.80 ms β no change β
β QQuery 20 β 33.98 / 34.83 Β±0.47 / 35.35 ms β 35.12 / 35.58 Β±0.45 / 36.30 ms β no change β
β QQuery 21 β 62.55 / 63.73 Β±1.38 / 66.36 ms β 60.40 / 62.03 Β±1.16 / 63.95 ms β no change β
β QQuery 22 β 15.20 / 16.48 Β±1.77 / 19.98 ms β 15.05 / 16.31 Β±2.16 / 20.63 ms β no change β
βββββββββββββ΄βββββββββββββββββββββββββββββββββ΄βββββββββββββββββββββββββββββββββ΄βββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββ³βββββββββββ
β Benchmark Summary β β
β‘βββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β Total Time (HEAD) β 801.33ms β
β Total Time (perf-hash-join-flat-chains) β 802.22ms β
β Average Time (HEAD) β 36.42ms β
β Average Time (perf-hash-join-flat-chains) β 36.46ms β
β Queries Faster β 0 β
β Queries Slower β 1 β
β Queries with No Change β 21 β
β Queries with Failure β 0 β
βββββββββββββββββββββββββββββββββββββββββββββ΄βββββββββββ
```
</p>
</details>
<details><summary>Resource Usage</summary>
**tpch β base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 5.0s |
| Peak memory | 1.1 GiB |
| Avg memory | 638.7 MiB |
| CPU user | 22.4s |
| CPU sys | 2.1s |
| Peak spill | 0 B |
**tpch β branch**
| Metric | Value |
|--------|-------|
| Wall time | 5.0s |
| Peak memory | 1.1 GiB |
| Avg memory | 641.1 MiB |
| CPU user | 22.5s |
| CPU sys | 2.0s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6251274519
π€ Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/26447#issuecomment-6251247997)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c6251247997-3574-sbs95 6.12.94+ #1 SMP Fri Aug 21 08:00:16 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing perf-hash-join-flat-chains (80c53008bb28094009845fce18a214f256e83ef3) to 484183d (merge-base) [diff](https://github.com/apache/datafusion/compare/484183dc34ea565190d9cd4a66db6d24789f95d0..80c53008bb28094009845fce18a214f256e83ef3)
<details><summary>Run configuration</summary>
```yaml
run benchmark tpch
```
</details>
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangb (via GitHub) via github" <gi...@datafusion.apache.org>.
adriangb commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6570480410
@andygrove maybe an easy first step would be to split the benchmarks into their own pr and then stack a pr on top that re-organizes the commits in some logical way that we can review refactors and tests on their own, etc.?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "andygrove (via GitHub) via github" <gi...@datafusion.apache.org>.
andygrove commented on code in PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#discussion_r4432072272
##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
@@ -3398,6 +3398,18 @@ async fn collect_left_input(
offset += batch.num_rows();
}
+ // Store the rows of each repeated key next to each other, so that a
+ // probe reads its matches in order. Keep the chain if the memory for
+ // the groups is not available.
+ if let Some(size) = hashmap.grouped_rows_size()
Review Comment:
Done. Grouping now runs after every reservation the build needs, just before the map is shared, and keeps the chain if the pool has no room for the groups. `grouping_needs_no_more_memory_than_the_build` checks that a build that fits without its groups still succeeds; with the old order it fails with `ResourcesExhausted`. `group_rows(&reservation, &mem_used)` now makes the size check, grows the reservation and gives back the chain's memory, and both maps call one generic function for it.
##########
datafusion/physical-plan/src/joins/join_hash_map.rs:
##########
@@ -337,11 +415,175 @@ impl JoinHashMapType for JoinHashMapU64 {
fn len(&self) -> usize {
self.map.len()
}
+
+ fn grouped_rows_size(&self) -> Option<usize> {
+ grouped_rows_size(&self.map, &self.next, self.chained)
+ }
+
+ fn group_rows(&mut self) -> usize {
+ if self.grouped_rows_size().is_none() {
+ return 0;
+ }
+ let freed = self.next.capacity() * size_of::<u64>();
+ self.groups = group_rows(&mut self.map, &self.next);
+ self.next = vec![];
+ freed
+ }
}
-use crate::joins::chain::traverse_chain;
+use crate::joins::chain::{emit_grouped_rows, traverse_chain};
use crate::joins::join_hash_map::ProbeOffset::{AtRow, MidChain};
+/// Returns the number of bytes that [`group_rows`] allocates for `map` and
+/// `next`, or `None` if the hash values have fewer than two rows each on
+/// average, or if a position in the groups would not fit in `T`.
+fn grouped_rows_size<T>(
+ map: &HashTable<(u64, T)>,
+ next: &[T],
+ chained: bool,
+) -> Option<usize>
+where
+ T: ArrowNativeType,
+{
+ // Following a chain costs a cache miss for each row after the first, which
+ // only adds up when the average chain is long enough. `next.len()` counts
+ // the rows left out of the map, such as NULL keys, too.
+ if !chained || next.len() < map.len().saturating_mul(2) {
Review Comment:
The NULL keys: the threshold and the size of the groups now count the rows inserted into the map, from the nonzero entries of `next`, so the rows left out of it count towards neither. `test_which_build_rows_are_grouped` covers both.
The skew: in `Partitioned` mode the hot key ends up in one partition, whose hash values have many rows each, so its rows are grouped. A single map with fewer than two rows per hash value on average, as in `CollectLeft` mode, isn't grouped. With your shape at 15M build rows, 5M of them on one key at scattered positions, and 100 probe rows on that key, the join takes 1.56 s on main and 0.97 s with this PR when `Partitioned`, and 1.6 s with both in `CollectLeft` mode.
I added a skewed case to `hj`: Q26 has 6M build rows, 1.5M of them on one key, and 100 probe rows on it. Like Q23 to Q25 it runs `Partitioned`, and it takes 0.53 to 0.60 s on main and 0.36 s with this PR. Catching the skew in a single map would take more than the average, such as sampling the chain lengths, which I'd leave for a follow-up.
##########
datafusion/physical-plan/src/joins/join_hash_map.rs:
##########
@@ -396,6 +641,33 @@ where
let zero = T::try_from(0).unwrap();
let one = T::try_from(1).unwrap();
+ if !groups.is_empty() {
Review Comment:
Done: both public functions are as on main, and grouped rows go through `grouped_matched_indices` instead, which takes `limit` by value and which `ArrayMap` now shares. The `stream_join_utils.rs` hunk and those test lines are gone. With the enum from your next comment, `get_matched_indices` on grouped rows is `unreachable!`.
##########
datafusion/physical-plan/src/joins/join_hash_map.rs:
##########
@@ -165,29 +179,56 @@ pub trait JoinHashMapType: Send + Sync {
/// Returns the number of entries in the join hash map.
fn len(&self) -> usize;
+
+ /// Returns the number of bytes that [`Self::group_rows`] would allocate,
+ /// or `None` if it would not group the rows: when the hash values have
+ /// fewer than two build rows each on average, the chains are too short for
+ /// grouping to pay for itself.
+ fn grouped_rows_size(&self) -> Option<usize> {
+ None
+ }
+
+ /// Stores the build rows of each hash value next to each other, in chain
+ /// order, and drops the chain. A probe row then reads its matches from one
+ /// place, instead of following the chain with a dependent load for every
+ /// match, which misses the cache when the build side is large. Call this
+ /// once every build row has been inserted. Returns the number of bytes
+ /// freed.
+ fn group_rows(&mut self) -> usize {
+ 0
+ }
}
pub struct JoinHashMapU32 {
- // Stores hash value to last row index
+ // Stores hash value to last row index, or to its group in `groups`
map: HashTable<(u64, u32)>,
// Stores indices in chained list data structure
next: Vec<u32>,
// Whether any hash value maps to more than one row
chained: bool,
+ // The build rows of each hash value once `group_rows` has grouped them,
+ // after which `next` is empty
+ groups: Vec<u32>,
Review Comment:
Done: the rows are `KeyRows::Chain { next, chained }` or `KeyRows::Grouped { groups }`, which replaces the `groups.is_empty()` checks, and inserting rows once they are grouped is `unreachable!`.
##########
datafusion/physical-plan/src/joins/chain.rs:
##########
@@ -75,3 +75,43 @@ where
match_row_idx = next - one;
}
}
+
+/// Emits the build rows `rows[pos..end]` of probe row `prob_idx`, at most
+/// `remaining` of them, for maps that store the build rows of each key next to
+/// each other instead of in a chain. Returns `Some(offset)` if the limit was
+/// reached and there are more results to process, as [`traverse_chain`] does.
+/// A [`MidChain`] offset then holds the position in `rows` to resume from,
+/// which is never `0` because at least one row was emitted.
+#[expect(clippy::too_many_arguments)]
+#[inline(always)]
+pub(crate) fn emit_grouped_rows<T>(
Review Comment:
Done, thanks.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangbot (via GitHub) via github" <gi...@datafusion.apache.org>.
adriangbot commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6532330413
π€ Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/26447#issuecomment-6532278515)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c6532278515-4175-9rqwh 6.12.105+ #1 SMP Sat Sep 19 07:55:25 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing perf-hash-join-flat-chains (71afb43ea7ef43b49f4129d005b17a6325080f9c) to 5f5418e (merge-base) [diff](https://github.com/apache/datafusion/compare/5f5418e2f3abee1020796d673904e8a69c977ca6..71afb43ea7ef43b49f4129d005b17a6325080f9c)
<details><summary>Run configuration</summary>
```yaml
run benchmark hj
```
</details>
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6526082347
Benchmark for [this request](https://github.com/apache/datafusion/pull/26447#issuecomment-6526017495) failed before finishing (Kubernetes reason: `BackoffLimitExceeded`).
Benchmarks requested: `tpch10`
<details><summary>Runner log (last 40 lines)</summary>
```
2026-10-30T15:08:52.025015Z INFO runner starting benchmark runner bench_type=Datafusion, pr_url=https://github.com/apache/datafusion/pull/26447, benchmarks=tpch10
2026-10-30T15:08:52.088531Z INFO benchmark_controller::runner::bench_datafusion === Cloning PR branch ===
2026-10-30T15:08:52.088558Z INFO benchmark_controller::runner::shell running command cmd=git, args=["clone", "--depth=200", "https://github.com/apache/datafusion.git", "/workspace/datafusion-branch"], cwd="/"
2026-10-30T15:09:02.099145Z INFO benchmark_controller::runner::shell running command cmd=git, args=["fetch", "origin", "refs/pull/26447/head:perf-hash-join-flat-chains", "main"], cwd="/workspace/datafusion-branch"
2026-10-30T15:09:22.104732Z INFO benchmark_controller::runner::shell running command cmd=git, args=["checkout", "perf-hash-join-flat-chains"], cwd="/workspace/datafusion-branch"
2026-10-30T15:09:27.106309Z INFO benchmark_controller::runner::shell running command cmd=git, args=["merge-base", "HEAD", "origin/main"], cwd="/workspace/datafusion-branch"
2026-10-30T15:09:32.108166Z ERROR runner benchmark failed error=git merge-base: git merge-base HEAD origin/main exited with code 1
stdout:
stderr:
```
</details>
<details><summary>Kubernetes message</summary>
```
Job has reached the specified backoff limit
```
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on code in PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#discussion_r4425166866
##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
@@ -3398,6 +3398,18 @@ async fn collect_left_input(
offset += batch.num_rows();
}
+ // Store the rows of each repeated key next to each other, so that a
+ // probe reads its matches in order. Keep the chain if the memory for
+ // the groups is not available.
+ if let Some(size) = hashmap.grouped_rows_size()
Review Comment:
Grouping is optional, but it runs before mandatory reservations. `concat_build_batches`, the key arrays and the bitmaps all call `try_grow(..)?` afterwards. Grouping keeps one extra index per distinct hash value reserved, so a build that fits on main can now fail there with `ResourcesExhausted` instead of falling back to the chain. Running it after those reservations would let the fallback cover them.
The caller also has to call `grouped_rows_size`, `try_grow`, `group_rows` and `shrink` in that order, and `group_rows` repeats the size check. One method that takes the reservation would keep that protocol in one place. The `JoinHashMapU32` and `JoinHashMapU64` impls of `group_rows` are identical apart from `size_of`, so their body could move into the free `group_rows`.
##########
datafusion/physical-plan/src/joins/join_hash_map.rs:
##########
@@ -396,6 +641,33 @@ where
let zero = T::try_from(0).unwrap();
let one = T::try_from(1).unwrap();
+ if !groups.is_empty() {
Review Comment:
Only the symmetric hash join calls `get_matched_indices`, and its `PruningJoinHashMap` always passes `&[]`. So this branch, including its `deleted_offset` handling, only runs in `test_grouped_rows_match_the_chain`.
Dispatching to `get_grouped_matched_indices` inside the `JoinHashMapU32` and `JoinHashMapU64` impls would leave both public free functions unchanged. That drops this branch, the `stream_join_utils.rs` hunk and those test lines. A `debug_assert!(self.groups.is_empty())` in `get_matched_indices` would guard the contract. `get_grouped_matched_indices` could then take `limit` by value, since nothing reads `remaining_output` after it returns.
##########
datafusion/physical-plan/src/joins/join_hash_map.rs:
##########
@@ -165,29 +179,56 @@ pub trait JoinHashMapType: Send + Sync {
/// Returns the number of entries in the join hash map.
fn len(&self) -> usize;
+
+ /// Returns the number of bytes that [`Self::group_rows`] would allocate,
+ /// or `None` if it would not group the rows: when the hash values have
+ /// fewer than two build rows each on average, the chains are too short for
+ /// grouping to pay for itself.
+ fn grouped_rows_size(&self) -> Option<usize> {
+ None
+ }
+
+ /// Stores the build rows of each hash value next to each other, in chain
+ /// order, and drops the chain. A probe row then reads its matches from one
+ /// place, instead of following the chain with a dependent load for every
+ /// match, which misses the cache when the build side is large. Call this
+ /// once every build row has been inserted. Returns the number of bytes
+ /// freed.
+ fn group_rows(&mut self) -> usize {
+ 0
+ }
}
pub struct JoinHashMapU32 {
- // Stores hash value to last row index
+ // Stores hash value to last row index, or to its group in `groups`
map: HashTable<(u64, u32)>,
// Stores indices in chained list data structure
next: Vec<u32>,
// Whether any hash value maps to more than one row
chained: bool,
+ // The build rows of each hash value once `group_rows` has grouped them,
+ // after which `next` is empty
+ groups: Vec<u32>,
Review Comment:
After `group_rows`, a map value is a group position, but `update_from_iter` doesn't know that. An insert on an existing hash would index the empty `next` and panic, and a new hash would store a `row + 1` among the group positions. No caller does this today. An enum like `KeyRows` in `ArrayMap`, for example `Chain { next, chained }` and `Grouped { groups }`, would make the state explicit and replace the `groups.is_empty()` checks. At least a `debug_assert!` in `update_from_iter` would catch misuse.
##########
datafusion/physical-plan/src/joins/chain.rs:
##########
@@ -75,3 +75,43 @@ where
match_row_idx = next - one;
}
}
+
+/// Emits the build rows `rows[pos..end]` of probe row `prob_idx`, at most
+/// `remaining` of them, for maps that store the build rows of each key next to
+/// each other instead of in a chain. Returns `Some(offset)` if the limit was
+/// reached and there are more results to process, as [`traverse_chain`] does.
+/// A [`MidChain`] offset then holds the position in `rows` to resume from,
+/// which is never `0` because at least one row was emitted.
+#[expect(clippy::too_many_arguments)]
+#[inline(always)]
+pub(crate) fn emit_grouped_rows<T>(
Review Comment:
`end` is only used as the end of `rows`. Passing `&rows[..end]` drops a parameter, which brings it to 7, so the `#[expect(clippy::too_many_arguments)]` can go.
##########
datafusion/physical-plan/src/joins/join_hash_map.rs:
##########
@@ -337,11 +415,175 @@ impl JoinHashMapType for JoinHashMapU64 {
fn len(&self) -> usize {
self.map.len()
}
+
+ fn grouped_rows_size(&self) -> Option<usize> {
+ grouped_rows_size(&self.map, &self.next, self.chained)
+ }
+
+ fn group_rows(&mut self) -> usize {
+ if self.grouped_rows_size().is_none() {
+ return 0;
+ }
+ let freed = self.next.capacity() * size_of::<u64>();
+ self.groups = group_rows(&mut self.map, &self.next);
+ self.next = vec![];
+ freed
+ }
}
-use crate::joins::chain::traverse_chain;
+use crate::joins::chain::{emit_grouped_rows, traverse_chain};
use crate::joins::join_hash_map::ProbeOffset::{AtRow, MidChain};
+/// Returns the number of bytes that [`group_rows`] allocates for `map` and
+/// `next`, or `None` if the hash values have fewer than two rows each on
+/// average, or if a position in the groups would not fit in `T`.
+fn grouped_rows_size<T>(
+ map: &HashTable<(u64, T)>,
+ next: &[T],
+ chained: bool,
+) -> Option<usize>
+where
+ T: ArrowNativeType,
+{
+ // Following a chain costs a cache miss for each row after the first, which
+ // only adds up when the average chain is long enough. `next.len()` counts
+ // the rows left out of the map, such as NULL keys, too.
+ if !chained || next.len() < map.len().saturating_mul(2) {
Review Comment:
Two cases where the average misleads:
- Skew. One key with 500K rows plus 1M unique keys gives `next.len()` of 1.5M, below `2 * map.len()`, so nothing is grouped. Every probe row that hits the hot key still walks a 500K-long chain, which is the q72 shape. Could the benchmarks include a skewed case like this?
- NULL keys. `next.len()` counts every build row, but `update_hash` leaves NULL keys out of the map. A build with 60% NULL keys and nearly unique non-NULL keys passes this check and pays for grouping. `groups` also gets capacity for the NULL rows, which stays reserved and unused for the whole join.
Counting the rows `update_from_iter` inserts would make both the threshold and the capacity exact.
##########
datafusion/physical-plan/src/joins/join_hash_map.rs:
##########
@@ -692,6 +1057,177 @@ mod tests {
assert_eq!(match_indices, vec![1, 0]);
}
+ /// Collects every match of `hash_values`, `limit` at a time.
+ fn all_matches(
+ hash_map: &dyn JoinHashMapType,
+ hash_values: &[u64],
+ valid_keys: Option<&NullBuffer>,
+ limit: usize,
+ ) -> Vec<(u32, u64)> {
+ let mut matches = vec![];
+ let mut input_indices = vec![];
+ let mut match_indices = vec![];
+ let mut offset = AtRow { row: 0 };
+ loop {
+ let next_offset = hash_map.get_matched_indices_with_limit_offset(
+ hash_values,
+ valid_keys,
+ limit,
+ offset,
+ &mut input_indices,
+ &mut match_indices,
+ );
+ assert!(input_indices.len() <= limit);
+ assert_eq!(input_indices.len(), match_indices.len());
+ matches.extend(
+ input_indices
+ .iter()
+ .copied()
+ .zip(match_indices.iter().copied()),
+ );
+ match next_offset {
+ Some(next) => offset = next,
+ None => return matches,
+ }
+ }
+ }
+
+ /// Builds two maps from the same rows, inserted batch by batch and last
+ /// to first as `update_hash` does, with row 7 left out as a NULL key would
+ /// be, and groups the rows of the second.
+ fn chained_and_grouped<M: JoinHashMapType>(
+ new_map: impl Fn(usize) -> M,
+ build_hashes: &[u64],
+ ) -> (M, M) {
+ let insert = |hash_map: &mut M| {
+ for (batch_idx, hashes) in build_hashes.chunks(64).enumerate().rev() {
+ let offset = batch_idx * 64;
+ hash_map.update_from_iter(
+ Box::new(
+ hashes
+ .iter()
+ .enumerate()
+ .map(move |(i, hash)| (offset + i, hash))
+ .filter(|(row, _)| *row != 7)
+ .rev(),
+ ),
+ 0,
+ );
+ }
+ };
+ let mut chained = new_map(build_hashes.len());
+ insert(&mut chained);
+ let mut grouped = new_map(build_hashes.len());
+ insert(&mut grouped);
+ assert!(grouped.grouped_rows_size().is_some());
+ assert!(grouped.group_rows() > 0);
+ (chained, grouped)
+ }
+
+ #[test]
+ fn test_grouped_rows_match_the_chain() {
+ // 13 hash values over 300 build rows, and probe rows that repeat,
+ // miss (13 to 16) or have a NULL key.
+ let build_hashes: Vec<u64> = (0..300u64).map(|i| (i * 7919) % 13).collect();
+ let probe_hashes: Vec<u64> = (0..50u64).map(|i| (i * 31) % 17).collect();
+ let valid_keys =
+ NullBuffer::from((0..50).map(|i| i % 9 != 4).collect::<Vec<_>>());
+
+ let (chained, grouped) =
+ chained_and_grouped(JoinHashMapU32::with_capacity, &build_hashes);
+ let (chained_u64, grouped_u64) =
+ chained_and_grouped(JoinHashMapU64::with_capacity, &build_hashes);
+ for limit in [1, 2, 3, 5, 23, 64, 8192] {
+ for valid in [None, Some(&valid_keys)] {
+ let expected = all_matches(&chained, &probe_hashes, valid, limit);
+ assert!(!expected.is_empty());
+ assert_eq!(all_matches(&grouped, &probe_hashes, valid, limit), expected);
+ assert_eq!(
+ all_matches(&chained_u64, &probe_hashes, valid, limit),
+ expected
+ );
+ assert_eq!(
+ all_matches(&grouped_u64, &probe_hashes, valid, limit),
+ expected
+ );
+ }
+ }
+
+ let iter = || Box::new(probe_hashes.iter().enumerate());
+ let expected = chained.get_matched_indices(iter(), None);
+ assert_eq!(grouped.get_matched_indices(iter(), None), expected);
+ assert_eq!(grouped_u64.get_matched_indices(iter(), None), expected);
+ assert_eq!(
+ grouped.contain_hashes(&probe_hashes),
+ chained.contain_hashes(&probe_hashes)
+ );
+ }
+
+ #[test]
+ fn test_grouped_rows_match_the_chain_for_long_chains() {
+ // Hash values 0 and 1 have chains too long for grouping to hold their
+ // rows until their end, among 2,000 short chains.
+ let build_hashes: Vec<u64> = (0..30_000u64)
+ .map(|i| if i % 3 == 0 { i % 2 } else { 2 + i % 2_000 })
+ .collect();
+ let probe_hashes: Vec<u64> = vec![0, 5, 1, 7, 2_001, 3_000, 0];
+
+ let (chained, grouped) =
+ chained_and_grouped(JoinHashMapU32::with_capacity, &build_hashes);
+ for limit in [1, 7, 4_096, 5_000, 8_192, 100_000] {
+ let expected = all_matches(&chained, &probe_hashes, None, limit);
+ assert_eq!(expected.len(), 2 * 5_000 + 5_000 + 3 * 10);
+ assert_eq!(all_matches(&grouped, &probe_hashes, None, limit), expected);
+ }
+ }
+
+ #[test]
+ fn test_unique_hash_values_are_not_grouped() {
Review Comment:
This test and `test_short_chains_are_not_grouped` make the same assertions on two inputs, and their `all_matches` checks re-test the chain and unique paths that `test_get_matched_indices_skips_invalid_keys*` and `test_unique_fast_path_with_uninserted_row` already cover. One table-driven test over `(hashes, expected grouped_rows_size)` could cover both, together with the size check in `test_group_rows_replaces_the_chain`. In `test_grouped_rows_match_the_chain`, `chained_u64` re-tests the existing chain path, so only `grouped_u64` adds coverage.
##########
datafusion/physical-plan/src/joins/array_map.rs:
##########
@@ -180,60 +197,88 @@ impl ArrayMap {
}
let size = (range + 1) as usize;
- let mut data: Vec<u32> = vec![0; size];
- let mut next: Vec<u32> = vec![];
- let mut num_of_distinct_key = 0;
-
downcast_supported_integer!(
array.data_type() => (
- fill_data,
+ build,
array,
min_val,
- &mut data,
- &mut next,
- &mut num_of_distinct_key
+ size
)
- )?;
-
- Ok(Self {
- data,
- offset: min_val,
- next,
- num_of_distinct_key,
- })
+ )
}
- fn fill_data<T: ArrowNumericType>(
+ fn build<T: ArrowNumericType>(
array: &ArrayRef,
- offset_val: u64,
- data: &mut [u32],
- next: &mut Vec<u32>,
- num_of_distinct_key: &mut usize,
- ) -> Result<()>
+ offset: u64,
+ size: usize,
+ ) -> Result<Self>
where
T::Native: AsPrimitive<u64>,
{
let arr = array.as_primitive::<T>();
- // Iterate in reverse to maintain FIFO order when there are duplicate keys.
- for (i, val) in arr.iter().enumerate().rev() {
- if let Some(val) = val {
- let key: u64 = val.as_();
- let Some(idx) = Self::key_to_index(key, offset_val, data.len()) else {
- return internal_err!("failed build Array idx >= data.len()");
- };
+ let mut data: Vec<u32> = vec![0; size];
+ let mut num_of_distinct_key = 0;
+ let mut unique = true;
+ for (i, val) in arr.iter().enumerate() {
+ let Some(val) = val else { continue };
+ let Some(idx) = Self::key_to_index(val.as_(), offset, size) else {
+ return internal_err!("failed build Array idx >= data.len()");
+ };
+ if data[idx] != 0 {
+ unique = false;
+ break;
+ }
+ data[idx] = i as u32 + 1;
+ num_of_distinct_key += 1;
+ }
+ if unique {
+ return Ok(Self {
+ rows: KeyRows::Unique { data },
+ offset,
+ num_of_distinct_key,
+ });
+ }
- if data[idx] != 0 {
- if next.is_empty() {
- *next = vec![0; array.len()]
- }
- next[i] = data[idx]
- } else {
- *num_of_distinct_key += 1;
- }
- data[idx] = (i) as u32 + 1;
+ // Some key repeats, so group the build rows by key with a counting
+ // sort, reusing the allocation. First count each key's rows...
+ let mut starts = data;
+ starts.fill(0);
+ // One more slot, for the end of the last key's rows
+ starts.reserve_exact(1);
+ starts.push(0);
Review Comment:
`data` was allocated with exactly `size` capacity, so `reserve_exact(1)` reallocates and may copy the whole slot array, right after `fill(0)` has swept it. Dropping `data` and allocating `vec![0; size + 1]` here skips both the sweep and the copy, and zeroed allocations can come straight from the OS. The slot array scales with the key range, so this grows with it.
##########
datafusion/physical-plan/src/joins/array_map.rs:
##########
@@ -274,14 +324,27 @@ impl ArrayMap {
)
}
- /// Looks up `key` (a raw probe value cast to `u64`) in the build side,
- /// returning the 1-based build-side slot if the key maps to a non-empty
- /// bucket, or `None` otherwise.
+ /// Returns the slot of `key` (a raw probe value cast to `u64`), or `None`
+ /// if it is outside the build side's key range.
+ #[inline]
+ fn slot(&self, key: u64) -> Option<usize> {
Review Comment:
`slot` and `contains` match on `self.rows` for every row of `contain_keys`, which backs the dynamic filter on every scanned probe row. Matching once outside `collect_bool`, with one closure per variant, removes the per-row branch and both helpers. The lookup paths already call `key_to_index` directly.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangb (via GitHub) via github" <gi...@datafusion.apache.org>.
adriangb commented on code in PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#discussion_r4428231300
##########
datafusion/physical-plan/src/joins/array_map.rs:
##########
@@ -261,14 +324,27 @@ impl ArrayMap {
)
}
- /// Looks up `key` (a raw probe value cast to `u64`) in the build side,
- /// returning the 1-based build-side slot if the key maps to a non-empty
- /// bucket, or `None` otherwise.
+ /// Returns the slot of `key` (a raw probe value cast to `u64`), or `None`
+ /// if it is outside the build side's key range.
+ #[inline]
+ fn slot(&self, key: u64) -> Option<usize> {
+ let slots = match &self.rows {
+ KeyRows::Unique { data } => data.len(),
+ KeyRows::Grouped { starts, .. } => starts.len() - 1,
Review Comment:
Test gap: mutating `starts.len() - 1` β `starts.len() / 1` survives both unit tests and a fuzz test. `slot()` is only reached via `contain_keys`, and nothing probes the key `max + 1` there. That key would index `starts[size + 1]`. A one-row case in `test_array_map_grouped_rows_keep_build_order` would cover it.
##########
datafusion/physical-plan/src/joins/array_map.rs:
##########
@@ -167,60 +197,88 @@ impl ArrayMap {
}
let size = (range + 1) as usize;
- let mut data: Vec<u32> = vec![0; size];
- let mut next: Vec<u32> = vec![];
- let mut num_of_distinct_key = 0;
-
downcast_supported_integer!(
array.data_type() => (
- fill_data,
+ build,
array,
min_val,
- &mut data,
- &mut next,
- &mut num_of_distinct_key
+ size
)
- )?;
-
- Ok(Self {
- data,
- offset: min_val,
- next,
- num_of_distinct_key,
- })
+ )
}
- fn fill_data<T: ArrowNumericType>(
+ fn build<T: ArrowNumericType>(
array: &ArrayRef,
- offset_val: u64,
- data: &mut [u32],
- next: &mut Vec<u32>,
- num_of_distinct_key: &mut usize,
- ) -> Result<()>
+ offset: u64,
+ size: usize,
+ ) -> Result<Self>
where
T::Native: AsPrimitive<u64>,
{
let arr = array.as_primitive::<T>();
- // Iterate in reverse to maintain FIFO order when there are duplicate keys.
- for (i, val) in arr.iter().enumerate().rev() {
- if let Some(val) = val {
- let key: u64 = val.as_();
- let Some(idx) = Self::key_to_index(key, offset_val, data.len()) else {
- return internal_err!("failed build Array idx >= data.len()");
- };
+ let mut data: Vec<u32> = vec![0; size];
+ let mut num_of_distinct_key = 0;
+ let mut unique = true;
+ for (i, val) in arr.iter().enumerate() {
+ let Some(val) = val else { continue };
+ let Some(idx) = Self::key_to_index(val.as_(), offset, size) else {
+ return internal_err!("failed build Array idx >= data.len()");
+ };
+ if data[idx] != 0 {
+ unique = false;
+ break;
+ }
+ data[idx] = i as u32 + 1;
+ num_of_distinct_key += 1;
+ }
+ if unique {
+ return Ok(Self {
+ rows: KeyRows::Unique { data },
+ offset,
+ num_of_distinct_key,
+ });
+ }
- if data[idx] != 0 {
- if next.is_empty() {
- *next = vec![0; array.len()]
- }
- next[i] = data[idx]
- } else {
- *num_of_distinct_key += 1;
- }
- data[idx] = (i) as u32 + 1;
+ // Some key repeats, so group the build rows by key with a counting
+ // sort, reusing the allocation. First count each key's rows...
+ let mut starts = data;
Review Comment:
This is where `hj` Q14 (`density=0.01`, 100K build rows β ~10M slots) loses ~20%. Grouping makes 3 passes over all `size` slots (`fill`, prefix sum, placement), on top of the aborted unique pass. `try_new` goes from 6.7% to 22.5% of samples.
I tried allocating a fresh `vec![0; size + 1]` here instead of `fill` + `reserve_exact` + `push`: no difference, so the cost is the O(range) passes, not the realloc.
Worth a density gate? E.g. keep the chain when `num_rows` is small relative to `size`, similar to the avg-β₯2-rows-per-hash heuristic in `grouped_rows_size`.
##########
datafusion/physical-plan/src/joins/join_hash_map.rs:
##########
@@ -383,6 +641,33 @@ where
let zero = T::try_from(0).unwrap();
let one = T::try_from(1).unwrap();
+ if !groups.is_empty() {
+ for (row_idx, hash_value) in iter {
+ if let Some((_, pos)) =
+ map.find(*hash_value, |(hash, _)| *hash_value == *hash)
+ {
+ let pos: u64 = (*pos).into();
+ let pos = pos as usize;
+ let len: u64 = groups[pos].into();
+ for &row in &groups[pos + 1..=pos + len as usize] {
+ let match_row_idx = if let Some(offset) = deleted_offset {
+ let offset = T::try_from(offset).unwrap();
+ if row < offset {
Review Comment:
Test gap: `row < offset` β `==` / `>` / `<=` all survive, and so does `PruningJoinHashMap::get_matched_indices_with_limit_offset β None` in `stream_join_utils.rs`. The grouped + `deleted_offset` (pruning) path doesn't seem to be covered by any test. Is a SHJ test with pruning plus repeated keys worth adding?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "andygrove (via GitHub) via github" <gi...@datafusion.apache.org>.
andygrove commented on code in PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#discussion_r4432072877
##########
datafusion/physical-plan/src/joins/array_map.rs:
##########
@@ -180,60 +197,88 @@ impl ArrayMap {
}
let size = (range + 1) as usize;
- let mut data: Vec<u32> = vec![0; size];
- let mut next: Vec<u32> = vec![];
- let mut num_of_distinct_key = 0;
-
downcast_supported_integer!(
array.data_type() => (
- fill_data,
+ build,
array,
min_val,
- &mut data,
- &mut next,
- &mut num_of_distinct_key
+ size
)
- )?;
-
- Ok(Self {
- data,
- offset: min_val,
- next,
- num_of_distinct_key,
- })
+ )
}
- fn fill_data<T: ArrowNumericType>(
+ fn build<T: ArrowNumericType>(
array: &ArrayRef,
- offset_val: u64,
- data: &mut [u32],
- next: &mut Vec<u32>,
- num_of_distinct_key: &mut usize,
- ) -> Result<()>
+ offset: u64,
+ size: usize,
+ ) -> Result<Self>
where
T::Native: AsPrimitive<u64>,
{
let arr = array.as_primitive::<T>();
- // Iterate in reverse to maintain FIFO order when there are duplicate keys.
- for (i, val) in arr.iter().enumerate().rev() {
- if let Some(val) = val {
- let key: u64 = val.as_();
- let Some(idx) = Self::key_to_index(key, offset_val, data.len()) else {
- return internal_err!("failed build Array idx >= data.len()");
- };
+ let mut data: Vec<u32> = vec![0; size];
+ let mut num_of_distinct_key = 0;
+ let mut unique = true;
+ for (i, val) in arr.iter().enumerate() {
+ let Some(val) = val else { continue };
+ let Some(idx) = Self::key_to_index(val.as_(), offset, size) else {
+ return internal_err!("failed build Array idx >= data.len()");
+ };
+ if data[idx] != 0 {
+ unique = false;
+ break;
+ }
+ data[idx] = i as u32 + 1;
+ num_of_distinct_key += 1;
+ }
+ if unique {
+ return Ok(Self {
+ rows: KeyRows::Unique { data },
+ offset,
+ num_of_distinct_key,
+ });
+ }
- if data[idx] != 0 {
- if next.is_empty() {
- *next = vec![0; array.len()]
- }
- next[i] = data[idx]
- } else {
- *num_of_distinct_key += 1;
- }
- data[idx] = (i) as u32 + 1;
+ // Some key repeats, so group the build rows by key with a counting
+ // sort, reusing the allocation. First count each key's rows...
+ let mut starts = data;
+ starts.fill(0);
+ // One more slot, for the end of the last key's rows
+ starts.reserve_exact(1);
+ starts.push(0);
Review Comment:
Done: sorted rows get a new zeroed `starts`. Since @adriangb's review, an `ArrayMap` only sorts its rows that way when it has at least two rows for each slot, without building a chain first. Any other keeps main's chain and has its rows grouped later, without a pass over the slots.
##########
datafusion/physical-plan/src/joins/array_map.rs:
##########
@@ -274,14 +324,27 @@ impl ArrayMap {
)
}
- /// Looks up `key` (a raw probe value cast to `u64`) in the build side,
- /// returning the 1-based build-side slot if the key maps to a non-empty
- /// bucket, or `None` otherwise.
+ /// Returns the slot of `key` (a raw probe value cast to `u64`), or `None`
+ /// if it is outside the build side's key range.
+ #[inline]
+ fn slot(&self, key: u64) -> Option<usize> {
Review Comment:
Done: `contain_keys` matches on the layout once, with a loop for each, and `slot` and `contains` are gone.
##########
datafusion/physical-plan/src/joins/join_hash_map.rs:
##########
@@ -692,6 +1057,177 @@ mod tests {
assert_eq!(match_indices, vec![1, 0]);
}
+ /// Collects every match of `hash_values`, `limit` at a time.
+ fn all_matches(
+ hash_map: &dyn JoinHashMapType,
+ hash_values: &[u64],
+ valid_keys: Option<&NullBuffer>,
+ limit: usize,
+ ) -> Vec<(u32, u64)> {
+ let mut matches = vec![];
+ let mut input_indices = vec![];
+ let mut match_indices = vec![];
+ let mut offset = AtRow { row: 0 };
+ loop {
+ let next_offset = hash_map.get_matched_indices_with_limit_offset(
+ hash_values,
+ valid_keys,
+ limit,
+ offset,
+ &mut input_indices,
+ &mut match_indices,
+ );
+ assert!(input_indices.len() <= limit);
+ assert_eq!(input_indices.len(), match_indices.len());
+ matches.extend(
+ input_indices
+ .iter()
+ .copied()
+ .zip(match_indices.iter().copied()),
+ );
+ match next_offset {
+ Some(next) => offset = next,
+ None => return matches,
+ }
+ }
+ }
+
+ /// Builds two maps from the same rows, inserted batch by batch and last
+ /// to first as `update_hash` does, with row 7 left out as a NULL key would
+ /// be, and groups the rows of the second.
+ fn chained_and_grouped<M: JoinHashMapType>(
+ new_map: impl Fn(usize) -> M,
+ build_hashes: &[u64],
+ ) -> (M, M) {
+ let insert = |hash_map: &mut M| {
+ for (batch_idx, hashes) in build_hashes.chunks(64).enumerate().rev() {
+ let offset = batch_idx * 64;
+ hash_map.update_from_iter(
+ Box::new(
+ hashes
+ .iter()
+ .enumerate()
+ .map(move |(i, hash)| (offset + i, hash))
+ .filter(|(row, _)| *row != 7)
+ .rev(),
+ ),
+ 0,
+ );
+ }
+ };
+ let mut chained = new_map(build_hashes.len());
+ insert(&mut chained);
+ let mut grouped = new_map(build_hashes.len());
+ insert(&mut grouped);
+ assert!(grouped.grouped_rows_size().is_some());
+ assert!(grouped.group_rows() > 0);
+ (chained, grouped)
+ }
+
+ #[test]
+ fn test_grouped_rows_match_the_chain() {
+ // 13 hash values over 300 build rows, and probe rows that repeat,
+ // miss (13 to 16) or have a NULL key.
+ let build_hashes: Vec<u64> = (0..300u64).map(|i| (i * 7919) % 13).collect();
+ let probe_hashes: Vec<u64> = (0..50u64).map(|i| (i * 31) % 17).collect();
+ let valid_keys =
+ NullBuffer::from((0..50).map(|i| i % 9 != 4).collect::<Vec<_>>());
+
+ let (chained, grouped) =
+ chained_and_grouped(JoinHashMapU32::with_capacity, &build_hashes);
+ let (chained_u64, grouped_u64) =
+ chained_and_grouped(JoinHashMapU64::with_capacity, &build_hashes);
+ for limit in [1, 2, 3, 5, 23, 64, 8192] {
+ for valid in [None, Some(&valid_keys)] {
+ let expected = all_matches(&chained, &probe_hashes, valid, limit);
+ assert!(!expected.is_empty());
+ assert_eq!(all_matches(&grouped, &probe_hashes, valid, limit), expected);
+ assert_eq!(
+ all_matches(&chained_u64, &probe_hashes, valid, limit),
+ expected
+ );
+ assert_eq!(
+ all_matches(&grouped_u64, &probe_hashes, valid, limit),
+ expected
+ );
+ }
+ }
+
+ let iter = || Box::new(probe_hashes.iter().enumerate());
+ let expected = chained.get_matched_indices(iter(), None);
+ assert_eq!(grouped.get_matched_indices(iter(), None), expected);
+ assert_eq!(grouped_u64.get_matched_indices(iter(), None), expected);
+ assert_eq!(
+ grouped.contain_hashes(&probe_hashes),
+ chained.contain_hashes(&probe_hashes)
+ );
+ }
+
+ #[test]
+ fn test_grouped_rows_match_the_chain_for_long_chains() {
+ // Hash values 0 and 1 have chains too long for grouping to hold their
+ // rows until their end, among 2,000 short chains.
+ let build_hashes: Vec<u64> = (0..30_000u64)
+ .map(|i| if i % 3 == 0 { i % 2 } else { 2 + i % 2_000 })
+ .collect();
+ let probe_hashes: Vec<u64> = vec![0, 5, 1, 7, 2_001, 3_000, 0];
+
+ let (chained, grouped) =
+ chained_and_grouped(JoinHashMapU32::with_capacity, &build_hashes);
+ for limit in [1, 7, 4_096, 5_000, 8_192, 100_000] {
+ let expected = all_matches(&chained, &probe_hashes, None, limit);
+ assert_eq!(expected.len(), 2 * 5_000 + 5_000 + 3 * 10);
+ assert_eq!(all_matches(&grouped, &probe_hashes, None, limit), expected);
+ }
+ }
+
+ #[test]
+ fn test_unique_hash_values_are_not_grouped() {
Review Comment:
Done: `test_which_build_rows_are_grouped` is a table of build hashes and the length of their groups, which covers both tests and the size check, and it also checks the reservation and the matches. `test_grouped_rows_match_the_chain` now compares only the grouped maps with the chain.
##########
datafusion/physical-plan/src/joins/array_map.rs:
##########
@@ -167,60 +197,88 @@ impl ArrayMap {
}
let size = (range + 1) as usize;
- let mut data: Vec<u32> = vec![0; size];
- let mut next: Vec<u32> = vec![];
- let mut num_of_distinct_key = 0;
-
downcast_supported_integer!(
array.data_type() => (
- fill_data,
+ build,
array,
min_val,
- &mut data,
- &mut next,
- &mut num_of_distinct_key
+ size
)
- )?;
-
- Ok(Self {
- data,
- offset: min_val,
- next,
- num_of_distinct_key,
- })
+ )
}
- fn fill_data<T: ArrowNumericType>(
+ fn build<T: ArrowNumericType>(
array: &ArrayRef,
- offset_val: u64,
- data: &mut [u32],
- next: &mut Vec<u32>,
- num_of_distinct_key: &mut usize,
- ) -> Result<()>
+ offset: u64,
+ size: usize,
+ ) -> Result<Self>
where
T::Native: AsPrimitive<u64>,
{
let arr = array.as_primitive::<T>();
- // Iterate in reverse to maintain FIFO order when there are duplicate keys.
- for (i, val) in arr.iter().enumerate().rev() {
- if let Some(val) = val {
- let key: u64 = val.as_();
- let Some(idx) = Self::key_to_index(key, offset_val, data.len()) else {
- return internal_err!("failed build Array idx >= data.len()");
- };
+ let mut data: Vec<u32> = vec![0; size];
+ let mut num_of_distinct_key = 0;
+ let mut unique = true;
+ for (i, val) in arr.iter().enumerate() {
+ let Some(val) = val else { continue };
+ let Some(idx) = Self::key_to_index(val.as_(), offset, size) else {
+ return internal_err!("failed build Array idx >= data.len()");
+ };
+ if data[idx] != 0 {
+ unique = false;
+ break;
+ }
+ data[idx] = i as u32 + 1;
+ num_of_distinct_key += 1;
+ }
+ if unique {
+ return Ok(Self {
+ rows: KeyRows::Unique { data },
+ offset,
+ num_of_distinct_key,
+ });
+ }
- if data[idx] != 0 {
- if next.is_empty() {
- *next = vec![0; array.len()]
- }
- next[i] = data[idx]
- } else {
- *num_of_distinct_key += 1;
- }
- data[idx] = (i) as u32 + 1;
+ // Some key repeats, so group the build rows by key with a counting
+ // sort, reusing the allocation. First count each key's rows...
+ let mut starts = data;
Review Comment:
Thanks for tracking this down. A sparse `ArrayMap` now makes no pass over all its slots: it keeps main's chain when it is built, and `group_rows` groups its rows later, as for a hash map, counting and placing them in two passes over the keys that touch only the slots of the keys that occur. Only maps with at least two rows for each slot still sort their rows as they are built. A density gate would have cost Q13 its speedup, since it has the same build side as Q14. The numbers are in my comment on the PR.
##########
datafusion/physical-plan/src/joins/array_map.rs:
##########
@@ -261,14 +324,27 @@ impl ArrayMap {
)
}
- /// Looks up `key` (a raw probe value cast to `u64`) in the build side,
- /// returning the 1-based build-side slot if the key maps to a non-empty
- /// bucket, or `None` otherwise.
+ /// Returns the slot of `key` (a raw probe value cast to `u64`), or `None`
+ /// if it is outside the build side's key range.
+ #[inline]
+ fn slot(&self, key: u64) -> Option<usize> {
+ let slots = match &self.rows {
+ KeyRows::Unique { data } => data.len(),
+ KeyRows::Grouped { starts, .. } => starts.len() - 1,
Review Comment:
`slot` is gone: after @comphead's review, `contain_keys` matches on the layout once, with a loop for each. `test_array_map_layouts` probes the keys just outside the range through `contain_keys` for each layout, and fails with your mutation's equivalent there, `starts.len() / 1`.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6236196309
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/26447?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `95.63107%` with `27 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 82.91%. Comparing base ([`484183d`](https://app.codecov.io/gh/apache/datafusion/commit/484183dc34ea565190d9cd4a66db6d24789f95d0?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`80c5300`](https://app.codecov.io/gh/apache/datafusion/commit/80c53008bb28094009845fce18a214f256e83ef3?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
| [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/26447?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [...atafusion/physical-plan/src/joins/join\_hash\_map.rs](https://app.codecov.io/gh/apache/datafusion/pull/26447?src=pr&el=tree&filepath=datafusion%2Fphysical-plan%2Fsrc%2Fjoins%2Fjoin_hash_map.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1wbGFuL3NyYy9qb2lucy9qb2luX2hhc2hfbWFwLnJz) | 95.97% | [13 Missing and 2 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/26447?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [datafusion/physical-plan/src/joins/array\_map.rs](https://app.codecov.io/gh/apache/datafusion/pull/26447?src=pr&el=tree&filepath=datafusion%2Fphysical-plan%2Fsrc%2Fjoins%2Farray_map.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1wbGFuL3NyYy9qb2lucy9hcnJheV9tYXAucnM=) | 94.68% | [6 Missing and 5 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/26447?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...usion/physical-plan/src/joins/stream\_join\_utils.rs](https://app.codecov.io/gh/apache/datafusion/pull/26447?src=pr&el=tree&filepath=datafusion%2Fphysical-plan%2Fsrc%2Fjoins%2Fstream_join_utils.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1wbGFuL3NyYy9qb2lucy9zdHJlYW1fam9pbl91dGlscy5ycw==) | 50.00% | [1 Missing :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/26447?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #26447 +/- ##
==========================================
+ Coverage 82.89% 82.91% +0.01%
==========================================
Files 1154 1154
Lines 457630 458147 +517
Branches 457630 458147 +517
==========================================
+ Hits 379370 379868 +498
- Misses 55256 55263 +7
- Partials 23004 23016 +12
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/26447?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangbot (via GitHub) via github" <gi...@datafusion.apache.org>.
adriangbot commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6532344672
π€ Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/26447#issuecomment-6532278515)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c6532278515-4174-tbgjb 6.12.105+ #1 SMP Sat Sep 19 07:55:25 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing perf-hash-join-flat-chains (71afb43ea7ef43b49f4129d005b17a6325080f9c) to 5f5418e (merge-base) [diff](https://github.com/apache/datafusion/compare/5f5418e2f3abee1020796d673904e8a69c977ca6..71afb43ea7ef43b49f4129d005b17a6325080f9c)
<details><summary>Run configuration</summary>
```yaml
run benchmark tpch10
```
</details>
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6524763996
Thanks @adriangb for running the benchmarks.
TPC-DS q72, the query this PR targets, is 1.87x faster: 1,821 ms to 973 ms. TPC-H and ClickBench don't change. Adding up the fastest run of each query:
| Suite | main | this PR | Change |
| --- | --- | --- | --- |
| [TPC-DS SF1](https://github.com/apache/datafusion/pull/26447#issuecomment-6251343888) | 9,557 ms | 8,720 ms | -8.8% |
| [TPC-H SF1](https://github.com/apache/datafusion/pull/26447#issuecomment-6251330865) | 779 ms | 780 ms | +0.2% |
| [ClickBench, partitioned](https://github.com/apache/datafusion/pull/26447#issuecomment-6251368710) | 19,280 ms | 19,199 ms | -0.4% |
q72 accounts for all of the TPC-DS change: the other 98 queries add up to 11 ms more than on main.
Apart from q72 and q15, each query the bot marks as faster or slower is marked on only one of its two measures, the fastest run or the mean. These include TPC-H q6 and the ClickBench queries marked up to 1.61x slower on the mean. None of them has a join, so this PR doesn't change how they run.
Two results are worth a closer look:
- TPC-DS q15 is about 6% slower on both measures: 59.1 ms to 62.9 ms in the fastest run, and 61.3 ms to 64.9 ms on average. Its fastest run on this PR is about as slow as the slowest on main, 63.2 ms.
- The peak memory of the TPC-DS run went from 1.9 GiB to 2.2 GiB, while TPC-H stayed at 1.1 GiB and ClickBench went from 18.3 GiB to 18.5 GiB. The runner measures it over the whole run, so it doesn't show which query it comes from.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "andygrove (via GitHub) via github" <gi...@datafusion.apache.org>.
andygrove commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6544865682
Thanks @adriangb for the thorough review, and for the differential fuzzing.
**`hj` Q14.** The cost you found came from passes over every slot of a sparse `ArrayMap`: Q14's build side spreads about 200 rows per key over 21M slots in each partition. A density gate would have given up Q13's speedup, since Q13 has the same build side, so instead:
- An `ArrayMap` with at least two rows for every slot still sorts its rows by key as it is built, where the passes over the slots are short.
- Any other `ArrayMap` builds main's chain, and `group_rows` groups it afterwards as for a hash map: if its keys have at least two rows each on average, after the build's other reservations, and only if the pool has room. It counts and places the rows in two passes over the keys, which touch only the slots of the keys that occur.
`dfbench hj` on an M3 Max, `release-nonlto`, median of 3 rounds of 5 iterations:
| Query | main | this PR |
| --- | --- | --- |
| Q13 | 607 ms | 202 ms |
| Q14 | 245 ms | 213 ms |
Q14 hadn't regressed on this machine with the commit you reviewed either (1.00 of main), so I couldn't reproduce the 1.2 times; could you rerun Q14 on your VM?
**The test gaps.** `slot()` is gone, and `test_array_map_layouts` now probes the keys just outside the range through `contain_keys` for each layout; it fails if the number of slots of the sorted layout is off by one. The grouped `deleted_offset` path is gone too, see inline.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6251343888
π€ Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/26447#issuecomment-6251247997)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
Comparing perf-hash-join-flat-chains (80c53008bb28094009845fce18a214f256e83ef3) to 484183d (merge-base) [diff](https://github.com/apache/datafusion/compare/484183dc34ea565190d9cd4a66db6d24789f95d0..80c53008bb28094009845fce18a214f256e83ef3)
<details><summary>Run configuration</summary>
```yaml
run benchmark tpcds
```
</details>
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
Comparing HEAD and perf-hash-join-flat-chains
--------------------
Benchmark tpcds_sf1.json
--------------------
βββββββββββββ³βββββββββββββ³βββββββββββββββββββββββββββββ³ββββββββββββββββ
β Query β HEAD β perf-hash-join-flat-chains β Change β
β‘ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β QQuery 1 β 5.81 ms β 5.72 ms β no change β
β QQuery 2 β 82.88 ms β 83.12 ms β no change β
β QQuery 3 β 29.47 ms β 29.43 ms β no change β
β QQuery 4 β 500.81 ms β 521.00 ms β no change β
β QQuery 5 β 52.31 ms β 52.21 ms β no change β
β QQuery 6 β 37.07 ms β 37.38 ms β no change β
β QQuery 7 β 73.25 ms β 73.20 ms β no change β
β QQuery 8 β 36.92 ms β 37.43 ms β no change β
β QQuery 9 β 53.89 ms β 53.73 ms β no change β
β QQuery 10 β 61.69 ms β 61.51 ms β no change β
β QQuery 11 β 328.06 ms β 317.98 ms β no change β
β QQuery 12 β 31.55 ms β 30.11 ms β no change β
β QQuery 13 β 119.52 ms β 117.01 ms β no change β
β QQuery 14 β 397.48 ms β 389.86 ms β no change β
β QQuery 15 β 59.10 ms β 62.91 ms β 1.06x slower β
β QQuery 16 β 6.59 ms β 6.72 ms β no change β
β QQuery 17 β 82.53 ms β 81.23 ms β no change β
β QQuery 18 β 112.22 ms β 114.00 ms β no change β
β QQuery 19 β 43.74 ms β 42.43 ms β no change β
β QQuery 20 β 38.71 ms β 37.55 ms β no change β
β QQuery 21 β 18.00 ms β 17.58 ms β no change β
β QQuery 22 β 70.91 ms β 70.75 ms β no change β
β QQuery 23 β 334.37 ms β 333.19 ms β no change β
β QQuery 24 β 207.99 ms β 209.78 ms β no change β
β QQuery 25 β 111.85 ms β 111.93 ms β no change β
β QQuery 26 β 47.66 ms β 47.25 ms β no change β
β QQuery 27 β 6.40 ms β 6.34 ms β no change β
β QQuery 28 β 59.59 ms β 61.76 ms β no change β
β QQuery 29 β 98.49 ms β 98.39 ms β no change β
β QQuery 30 β 34.43 ms β 34.13 ms β no change β
β QQuery 31 β 111.85 ms β 112.84 ms β no change β
β QQuery 32 β 21.43 ms β 22.07 ms β no change β
β QQuery 33 β 37.60 ms β 37.44 ms β no change β
β QQuery 34 β 11.36 ms β 10.71 ms β +1.06x faster β
β QQuery 35 β 78.66 ms β 79.16 ms β no change β
β QQuery 36 β 6.52 ms β 6.33 ms β no change β
β QQuery 37 β 7.46 ms β 7.32 ms β no change β
β QQuery 38 β 66.33 ms β 66.40 ms β no change β
β QQuery 39 β 76.86 ms β 77.22 ms β no change β
β QQuery 40 β 25.26 ms β 26.30 ms β no change β
β QQuery 41 β 13.03 ms β 13.21 ms β no change β
β QQuery 42 β 25.20 ms β 24.82 ms β no change β
β QQuery 43 β 5.34 ms β 5.23 ms β no change β
β QQuery 44 β 9.32 ms β 9.24 ms β no change β
β QQuery 45 β 47.59 ms β 44.77 ms β +1.06x faster β
β QQuery 46 β 12.54 ms β 12.05 ms β no change β
β QQuery 47 β 271.03 ms β 263.77 ms β no change β
β QQuery 48 β 94.28 ms β 93.25 ms β no change β
β QQuery 49 β 73.09 ms β 72.57 ms β no change β
β QQuery 50 β 60.88 ms β 60.03 ms β no change β
β QQuery 51 β 96.02 ms β 95.97 ms β no change β
β QQuery 52 β 25.35 ms β 25.13 ms β no change β
β QQuery 53 β 30.15 ms β 30.22 ms β no change β
β QQuery 54 β 55.21 ms β 55.24 ms β no change β
β QQuery 55 β 24.40 ms β 24.24 ms β no change β
β QQuery 56 β 39.20 ms β 39.22 ms β no change β
β QQuery 57 β 177.93 ms β 172.43 ms β no change β
β QQuery 58 β 110.95 ms β 109.12 ms β no change β
β QQuery 59 β 120.29 ms β 119.92 ms β no change β
β QQuery 60 β 39.43 ms β 38.47 ms β no change β
β QQuery 61 β 11.43 ms β 10.74 ms β +1.06x faster β
β QQuery 62 β 45.86 ms β 44.76 ms β no change β
β QQuery 63 β 30.20 ms β 30.26 ms β no change β
β QQuery 64 β 384.65 ms β 384.80 ms β no change β
β QQuery 65 β 138.00 ms β 132.52 ms β no change β
β QQuery 66 β 80.11 ms β 80.74 ms β no change β
β QQuery 67 β 275.20 ms β 280.51 ms β no change β
β QQuery 68 β 13.19 ms β 12.64 ms β no change β
β QQuery 69 β 58.22 ms β 58.05 ms β no change β
β QQuery 70 β 108.36 ms β 109.94 ms β no change β
β QQuery 71 β 36.09 ms β 35.97 ms β no change β
β QQuery 72 β 1821.28 ms β 973.37 ms β +1.87x faster β
β QQuery 73 β 11.13 ms β 11.24 ms β no change β
β QQuery 74 β 183.71 ms β 194.09 ms β 1.06x slower β
β QQuery 75 β 144.64 ms β 146.98 ms β no change β
β QQuery 76 β 35.39 ms β 35.56 ms β no change β
β QQuery 77 β 62.50 ms β 63.62 ms β no change β
β QQuery 78 β 173.31 ms β 182.83 ms β 1.05x slower β
β QQuery 79 β 70.21 ms β 69.96 ms β no change β
β QQuery 80 β 101.12 ms β 102.86 ms β no change β
β QQuery 81 β 27.20 ms β 27.81 ms β no change β
β QQuery 82 β 17.25 ms β 18.06 ms β no change β
β QQuery 83 β 33.80 ms β 34.29 ms β no change β
β QQuery 84 β 30.30 ms β 30.46 ms β no change β
β QQuery 85 β 102.86 ms β 101.24 ms β no change β
β QQuery 86 β 26.99 ms β 26.79 ms β no change β
β QQuery 87 β 64.34 ms β 66.51 ms β no change β
β QQuery 88 β 59.65 ms β 60.78 ms β no change β
β QQuery 89 β 36.12 ms β 37.33 ms β no change β
β QQuery 90 β 16.96 ms β 17.17 ms β no change β
β QQuery 91 β 42.09 ms β 42.20 ms β no change β
β QQuery 92 β 30.52 ms β 31.48 ms β no change β
β QQuery 93 β 51.29 ms β 51.88 ms β no change β
β QQuery 94 β 40.26 ms β 40.09 ms β no change β
β QQuery 95 β 84.16 ms β 81.68 ms β no change β
β QQuery 96 β 24.53 ms β 24.22 ms β no change β
β QQuery 97 β 53.77 ms β 52.79 ms β no change β
β QQuery 98 β 45.41 ms β 45.95 ms β no change β
β QQuery 99 β 67.04 ms β 67.63 ms β no change β
βββββββββββββ΄βββββββββββββ΄βββββββββββββββββββββββββββββ΄ββββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββ³ββββββββββββ
β Benchmark Summary β β
β‘ββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β Total Time (HEAD) β 9556.98ms β
β Total Time (perf-hash-join-flat-chains) β 8720.15ms β
β Average Time (HEAD) β 96.54ms β
β Average Time (perf-hash-join-flat-chains) β 88.08ms β
β Queries Faster β 4 β
β Queries Slower β 3 β
β Queries with No Change β 92 β
β Queries with Failure β 0 β
βββββββββββββββββββββββββββββββββββββββββββββ΄ββββββββββββ
Distribution per query (min / mean Β±stddev / max):
Comparing HEAD and perf-hash-join-flat-chains
--------------------
Benchmark tpcds_sf1.json
--------------------
βββββββββββββ³ββββββββββββββββββββββββββββββββββββββββ³βββββββββββββββββββββββββββββββββββββββ³ββββββββββββββββ
β Query β HEAD β perf-hash-join-flat-chains β Change β
β‘βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β QQuery 1 β 5.81 / 6.38 Β±1.00 / 8.38 ms β 5.72 / 6.34 Β±0.90 / 8.12 ms β no change β
β QQuery 2 β 82.88 / 83.47 Β±0.53 / 84.46 ms β 83.12 / 83.53 Β±0.35 / 84.15 ms β no change β
β QQuery 3 β 29.47 / 29.71 Β±0.22 / 30.02 ms β 29.43 / 29.99 Β±0.35 / 30.51 ms β no change β
β QQuery 4 β 500.81 / 509.42 Β±7.87 / 520.87 ms β 521.00 / 525.13 Β±2.13 / 526.97 ms β no change β
β QQuery 5 β 52.31 / 52.75 Β±0.29 / 53.08 ms β 52.21 / 52.60 Β±0.48 / 53.45 ms β no change β
β QQuery 6 β 37.07 / 37.77 Β±0.48 / 38.22 ms β 37.38 / 38.03 Β±0.37 / 38.50 ms β no change β
β QQuery 7 β 73.25 / 73.76 Β±0.45 / 74.37 ms β 73.20 / 73.96 Β±0.55 / 74.74 ms β no change β
β QQuery 8 β 36.92 / 39.01 Β±2.66 / 44.21 ms β 37.43 / 37.66 Β±0.21 / 37.93 ms β no change β
β QQuery 9 β 53.89 / 55.40 Β±1.03 / 56.95 ms β 53.73 / 54.66 Β±1.13 / 56.82 ms β no change β
β QQuery 10 β 61.69 / 62.08 Β±0.38 / 62.70 ms β 61.51 / 61.99 Β±0.28 / 62.37 ms β no change β
β QQuery 11 β 328.06 / 334.10 Β±5.02 / 342.32 ms β 317.98 / 324.75 Β±3.79 / 328.86 ms β no change β
β QQuery 12 β 31.55 / 31.92 Β±0.38 / 32.64 ms β 30.11 / 30.64 Β±0.48 / 31.46 ms β no change β
β QQuery 13 β 119.52 / 120.81 Β±1.24 / 123.10 ms β 117.01 / 118.68 Β±0.98 / 119.63 ms β no change β
β QQuery 14 β 397.48 / 402.94 Β±3.75 / 407.92 ms β 389.86 / 394.43 Β±5.72 / 405.55 ms β no change β
β QQuery 15 β 59.10 / 61.34 Β±1.48 / 63.15 ms β 62.91 / 64.85 Β±1.23 / 66.78 ms β 1.06x slower β
β QQuery 16 β 6.59 / 6.78 Β±0.19 / 7.12 ms β 6.72 / 6.86 Β±0.12 / 7.02 ms β no change β
β QQuery 17 β 82.53 / 84.26 Β±2.40 / 88.98 ms β 81.23 / 83.04 Β±2.21 / 87.20 ms β no change β
β QQuery 18 β 112.22 / 114.37 Β±1.47 / 116.45 ms β 114.00 / 115.63 Β±1.39 / 117.45 ms β no change β
β QQuery 19 β 43.74 / 44.20 Β±0.41 / 44.91 ms β 42.43 / 43.11 Β±0.70 / 44.30 ms β no change β
β QQuery 20 β 38.71 / 39.72 Β±1.26 / 42.16 ms β 37.55 / 38.85 Β±0.81 / 39.85 ms β no change β
β QQuery 21 β 18.00 / 18.25 Β±0.23 / 18.65 ms β 17.58 / 17.93 Β±0.21 / 18.14 ms β no change β
β QQuery 22 β 70.91 / 72.14 Β±0.87 / 73.53 ms β 70.75 / 71.96 Β±0.66 / 72.66 ms β no change β
β QQuery 23 β 334.37 / 338.45 Β±2.50 / 342.14 ms β 333.19 / 338.72 Β±3.14 / 342.32 ms β no change β
β QQuery 24 β 207.99 / 211.73 Β±4.89 / 220.71 ms β 209.78 / 212.09 Β±1.78 / 214.64 ms β no change β
β QQuery 25 β 111.85 / 113.52 Β±1.58 / 116.41 ms β 111.93 / 112.74 Β±0.63 / 113.76 ms β no change β
β QQuery 26 β 47.66 / 50.02 Β±3.46 / 56.88 ms β 47.25 / 47.83 Β±0.40 / 48.32 ms β no change β
β QQuery 27 β 6.40 / 6.54 Β±0.14 / 6.80 ms β 6.34 / 6.45 Β±0.09 / 6.59 ms β no change β
β QQuery 28 β 59.59 / 62.09 Β±1.29 / 63.02 ms β 61.76 / 62.77 Β±0.95 / 64.37 ms β no change β
β QQuery 29 β 98.49 / 99.99 Β±1.40 / 102.47 ms β 98.39 / 99.29 Β±1.21 / 101.62 ms β no change β
β QQuery 30 β 34.43 / 36.94 Β±3.40 / 43.55 ms β 34.13 / 36.13 Β±2.84 / 41.69 ms β no change β
β QQuery 31 β 111.85 / 113.85 Β±1.76 / 117.09 ms β 112.84 / 113.99 Β±0.95 / 115.71 ms β no change β
β QQuery 32 β 21.43 / 21.54 Β±0.09 / 21.70 ms β 22.07 / 22.46 Β±0.33 / 22.86 ms β no change β
β QQuery 33 β 37.60 / 38.08 Β±0.45 / 38.86 ms β 37.44 / 38.38 Β±0.65 / 39.46 ms β no change β
β QQuery 34 β 11.36 / 12.50 Β±1.33 / 14.92 ms β 10.71 / 12.43 Β±3.08 / 18.59 ms β no change β
β QQuery 35 β 78.66 / 80.67 Β±1.15 / 82.23 ms β 79.16 / 79.64 Β±0.40 / 80.31 ms β no change β
β QQuery 36 β 6.52 / 6.69 Β±0.14 / 6.88 ms β 6.33 / 6.54 Β±0.16 / 6.74 ms β no change β
β QQuery 37 β 7.46 / 7.59 Β±0.15 / 7.89 ms β 7.32 / 7.55 Β±0.23 / 7.89 ms β no change β
β QQuery 38 β 66.33 / 67.39 Β±0.75 / 68.25 ms β 66.40 / 68.29 Β±1.47 / 70.76 ms β no change β
β QQuery 39 β 76.86 / 79.32 Β±2.61 / 84.18 ms β 77.22 / 78.49 Β±1.26 / 80.70 ms β no change β
β QQuery 40 β 25.26 / 25.94 Β±0.62 / 26.91 ms β 26.30 / 27.63 Β±1.70 / 30.97 ms β 1.07x slower β
β QQuery 41 β 13.03 / 13.28 Β±0.23 / 13.63 ms β 13.21 / 13.37 Β±0.16 / 13.67 ms β no change β
β QQuery 42 β 25.20 / 25.76 Β±0.54 / 26.59 ms β 24.82 / 25.47 Β±0.50 / 26.22 ms β no change β
β QQuery 43 β 5.34 / 5.49 Β±0.16 / 5.78 ms β 5.23 / 5.29 Β±0.06 / 5.39 ms β no change β
β QQuery 44 β 9.32 / 9.49 Β±0.11 / 9.61 ms β 9.24 / 9.35 Β±0.07 / 9.43 ms β no change β
β QQuery 45 β 47.59 / 48.18 Β±0.37 / 48.63 ms β 44.77 / 45.83 Β±0.83 / 46.93 ms β no change β
β QQuery 46 β 12.54 / 12.66 Β±0.17 / 12.99 ms β 12.05 / 12.23 Β±0.13 / 12.41 ms β no change β
β QQuery 47 β 271.03 / 274.83 Β±3.93 / 281.68 ms β 263.77 / 269.17 Β±4.79 / 275.58 ms β no change β
β QQuery 48 β 94.28 / 95.31 Β±0.63 / 96.08 ms β 93.25 / 94.01 Β±0.52 / 94.75 ms β no change β
β QQuery 49 β 73.09 / 74.54 Β±2.29 / 79.05 ms β 72.57 / 75.26 Β±3.77 / 82.64 ms β no change β
β QQuery 50 β 60.88 / 61.32 Β±0.37 / 61.83 ms β 60.03 / 61.07 Β±0.78 / 62.03 ms β no change β
β QQuery 51 β 96.02 / 96.62 Β±0.43 / 97.07 ms β 95.97 / 97.65 Β±1.53 / 100.25 ms β no change β
β QQuery 52 β 25.35 / 28.32 Β±4.25 / 36.77 ms β 25.13 / 25.65 Β±0.58 / 26.61 ms β +1.10x faster β
β QQuery 53 β 30.15 / 31.31 Β±1.35 / 33.88 ms β 30.22 / 31.18 Β±0.66 / 31.92 ms β no change β
β QQuery 54 β 55.21 / 56.57 Β±0.93 / 57.88 ms β 55.24 / 56.39 Β±1.10 / 57.76 ms β no change β
β QQuery 55 β 24.40 / 24.73 Β±0.39 / 25.47 ms β 24.24 / 24.87 Β±0.47 / 25.59 ms β no change β
β QQuery 56 β 39.20 / 39.66 Β±0.45 / 40.28 ms β 39.22 / 39.66 Β±0.28 / 40.00 ms β no change β
β QQuery 57 β 177.93 / 181.05 Β±2.85 / 186.17 ms β 172.43 / 179.18 Β±4.79 / 186.28 ms β no change β
β QQuery 58 β 110.95 / 114.06 Β±2.94 / 118.27 ms β 109.12 / 111.59 Β±3.33 / 118.08 ms β no change β
β QQuery 59 β 120.29 / 120.95 Β±0.45 / 121.53 ms β 119.92 / 120.76 Β±1.12 / 122.97 ms β no change β
β QQuery 60 β 39.43 / 41.87 Β±2.37 / 46.29 ms β 38.47 / 39.08 Β±0.40 / 39.70 ms β +1.07x faster β
β QQuery 61 β 11.43 / 11.60 Β±0.09 / 11.67 ms β 10.74 / 11.05 Β±0.31 / 11.57 ms β no change β
β QQuery 62 β 45.86 / 46.85 Β±0.87 / 48.47 ms β 44.76 / 45.83 Β±1.07 / 47.68 ms β no change β
β QQuery 63 β 30.20 / 30.68 Β±0.26 / 30.97 ms β 30.26 / 30.82 Β±0.40 / 31.34 ms β no change β
β QQuery 64 β 384.65 / 389.41 Β±6.11 / 401.36 ms β 384.80 / 389.45 Β±5.15 / 399.01 ms β no change β
β QQuery 65 β 138.00 / 140.32 Β±1.20 / 141.27 ms β 132.52 / 137.35 Β±2.66 / 140.06 ms β no change β
β QQuery 66 β 80.11 / 81.61 Β±2.24 / 86.05 ms β 80.74 / 82.96 Β±2.09 / 85.75 ms β no change β
β QQuery 67 β 275.20 / 281.05 Β±4.37 / 288.11 ms β 280.51 / 285.54 Β±2.82 / 288.60 ms β no change β
β QQuery 68 β 13.19 / 17.17 Β±6.61 / 30.37 ms β 12.64 / 12.88 Β±0.20 / 13.25 ms β +1.33x faster β
β QQuery 69 β 58.22 / 59.30 Β±1.17 / 61.58 ms β 58.05 / 59.37 Β±2.08 / 63.51 ms β no change β
β QQuery 70 β 108.36 / 109.78 Β±1.60 / 112.87 ms β 109.94 / 112.67 Β±2.72 / 117.10 ms β no change β
β QQuery 71 β 36.09 / 39.52 Β±4.57 / 48.43 ms β 35.97 / 36.33 Β±0.34 / 36.96 ms β +1.09x faster β
β QQuery 72 β 1821.28 / 1894.82 Β±53.29 / 1971.26 ms β 973.37 / 1014.52 Β±28.40 / 1054.84 ms β +1.87x faster β
β QQuery 73 β 11.13 / 11.64 Β±0.31 / 12.10 ms β 11.24 / 11.57 Β±0.42 / 12.38 ms β no change β
β QQuery 74 β 183.71 / 187.92 Β±4.74 / 197.08 ms β 194.09 / 196.93 Β±3.76 / 204.15 ms β no change β
β QQuery 75 β 144.64 / 150.18 Β±6.11 / 161.99 ms β 146.98 / 148.30 Β±1.27 / 150.53 ms β no change β
β QQuery 76 β 35.39 / 35.62 Β±0.21 / 35.92 ms β 35.56 / 36.04 Β±0.42 / 36.62 ms β no change β
β QQuery 77 β 62.50 / 63.13 Β±0.52 / 63.94 ms β 63.62 / 66.69 Β±3.89 / 74.06 ms β 1.06x slower β
β QQuery 78 β 173.31 / 179.94 Β±7.18 / 190.44 ms β 182.83 / 183.96 Β±0.69 / 184.83 ms β no change β
β QQuery 79 β 70.21 / 72.72 Β±4.52 / 81.74 ms β 69.96 / 70.61 Β±0.42 / 71.09 ms β no change β
β QQuery 80 β 101.12 / 102.39 Β±1.09 / 104.39 ms β 102.86 / 106.51 Β±5.08 / 116.59 ms β no change β
β QQuery 81 β 27.20 / 27.47 Β±0.17 / 27.64 ms β 27.81 / 29.19 Β±1.41 / 30.91 ms β 1.06x slower β
β QQuery 82 β 17.25 / 17.82 Β±0.55 / 18.85 ms β 18.06 / 18.39 Β±0.28 / 18.66 ms β no change β
β QQuery 83 β 33.80 / 34.16 Β±0.22 / 34.45 ms β 34.29 / 34.75 Β±0.29 / 35.14 ms β no change β
β QQuery 84 β 30.30 / 32.90 Β±3.90 / 40.63 ms β 30.46 / 30.80 Β±0.22 / 31.11 ms β +1.07x faster β
β QQuery 85 β 102.86 / 103.67 Β±0.97 / 105.45 ms β 101.24 / 105.04 Β±3.06 / 110.29 ms β no change β
β QQuery 86 β 26.99 / 27.10 Β±0.10 / 27.28 ms β 26.79 / 27.83 Β±0.75 / 28.72 ms β no change β
β QQuery 87 β 64.34 / 66.39 Β±1.94 / 69.77 ms β 66.51 / 67.36 Β±1.02 / 69.29 ms β no change β
β QQuery 88 β 59.65 / 60.35 Β±0.40 / 60.90 ms β 60.78 / 61.52 Β±0.60 / 62.61 ms β no change β
β QQuery 89 β 36.12 / 36.50 Β±0.33 / 36.91 ms β 37.33 / 38.65 Β±2.11 / 42.85 ms β 1.06x slower β
β QQuery 90 β 16.96 / 17.13 Β±0.10 / 17.24 ms β 17.17 / 17.95 Β±0.93 / 19.76 ms β no change β
β QQuery 91 β 42.09 / 42.75 Β±0.42 / 43.19 ms β 42.20 / 43.33 Β±1.08 / 45.26 ms β no change β
β QQuery 92 β 30.52 / 33.83 Β±5.25 / 44.28 ms β 31.48 / 32.06 Β±0.32 / 32.42 ms β +1.06x faster β
β QQuery 93 β 51.29 / 53.16 Β±1.32 / 55.00 ms β 51.88 / 52.94 Β±0.87 / 54.45 ms β no change β
β QQuery 94 β 40.26 / 40.94 Β±0.72 / 42.18 ms β 40.09 / 42.66 Β±2.87 / 48.22 ms β no change β
β QQuery 95 β 84.16 / 84.85 Β±0.81 / 86.41 ms β 81.68 / 82.52 Β±0.83 / 84.06 ms β no change β
β QQuery 96 β 24.53 / 26.18 Β±3.10 / 32.38 ms β 24.22 / 24.45 Β±0.20 / 24.78 ms β +1.07x faster β
β QQuery 97 β 53.77 / 56.15 Β±1.70 / 59.03 ms β 52.79 / 53.53 Β±0.98 / 55.41 ms β no change β
β QQuery 98 β 45.41 / 46.62 Β±0.66 / 47.31 ms β 45.95 / 46.93 Β±1.45 / 49.80 ms β no change β
β QQuery 99 β 67.04 / 67.90 Β±0.53 / 68.53 ms β 67.63 / 68.58 Β±0.93 / 69.94 ms β no change β
βββββββββββββ΄ββββββββββββββββββββββββββββββββββββββββ΄βββββββββββββββββββββββββββββββββββββββ΄ββββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββ³ββββββββββββ
β Benchmark Summary β β
β‘ββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β Total Time (HEAD) β 9790.96ms β
β Total Time (perf-hash-join-flat-chains) β 8901.01ms β
β Average Time (HEAD) β 98.90ms β
β Average Time (perf-hash-join-flat-chains) β 89.91ms β
β Queries Faster β 8 β
β Queries Slower β 5 β
β Queries with No Change β 86 β
β Queries with Failure β 0 β
βββββββββββββββββββββββββββββββββββββββββββββ΄ββββββββββββ
```
</p>
</details>
<details><summary>Resource Usage</summary>
**tpcds β base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 50.0s |
| Peak memory | 1.9 GiB |
| Avg memory | 1.5 GiB |
| CPU user | 211.1s |
| CPU sys | 6.4s |
| Peak spill | 0 B |
**tpcds β branch**
| Metric | Value |
|--------|-------|
| Wall time | 45.0s |
| Peak memory | 2.2 GiB |
| Avg memory | 1.6 GiB |
| CPU user | 166.9s |
| CPU sys | 6.2s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6251281353
π€ Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/26447#issuecomment-6251247997)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c6251247997-3573-dw2v6 6.12.94+ #1 SMP Fri Aug 21 08:00:16 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing perf-hash-join-flat-chains (80c53008bb28094009845fce18a214f256e83ef3) to 484183d (merge-base) [diff](https://github.com/apache/datafusion/compare/484183dc34ea565190d9cd4a66db6d24789f95d0..80c53008bb28094009845fce18a214f256e83ef3)
<details><summary>Run configuration</summary>
```yaml
run benchmark tpcds
```
</details>
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6526017495
run benchmark tpch10 hj
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangbot (via GitHub) via github" <gi...@datafusion.apache.org>.
adriangbot commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6532466276
π€ Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/26447#issuecomment-6532278515)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
Comparing perf-hash-join-flat-chains (71afb43ea7ef43b49f4129d005b17a6325080f9c) to 5f5418e (merge-base) [diff](https://github.com/apache/datafusion/compare/5f5418e2f3abee1020796d673904e8a69c977ca6..71afb43ea7ef43b49f4129d005b17a6325080f9c)
<details><summary>Run configuration</summary>
```yaml
run benchmark tpch10
```
</details>
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
Comparing HEAD and perf-hash-join-flat-chains
--------------------
Benchmark tpch_sf10.json
--------------------
βββββββββββββ³ββββββββββββ³βββββββββββββββββββββββββββββ³βββββββββββββββ
β Query β HEAD β perf-hash-join-flat-chains β Change β
β‘ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β QQuery 1 β 328.37 ms β 327.89 ms β no change β
β QQuery 2 β 89.53 ms β 89.39 ms β no change β
β QQuery 3 β 214.09 ms β 215.36 ms β no change β
β QQuery 4 β 114.45 ms β 115.30 ms β no change β
β QQuery 5 β 341.96 ms β 348.20 ms β no change β
β QQuery 6 β 100.24 ms β 100.46 ms β no change β
β QQuery 7 β 442.86 ms β 441.33 ms β no change β
β QQuery 8 β 354.95 ms β 356.22 ms β no change β
β QQuery 9 β 508.83 ms β 509.05 ms β no change β
β QQuery 10 β 285.41 ms β 285.10 ms β no change β
β QQuery 11 β 61.28 ms β 60.86 ms β no change β
β QQuery 12 β 119.43 ms β 122.04 ms β no change β
β QQuery 13 β 298.84 ms β 300.17 ms β no change β
β QQuery 14 β 166.92 ms β 168.82 ms β no change β
β QQuery 15 β 296.21 ms β 297.93 ms β no change β
β QQuery 16 β 64.16 ms β 63.21 ms β no change β
β QQuery 17 β 577.71 ms β 586.25 ms β no change β
β QQuery 18 β 934.25 ms β 1016.36 ms β 1.09x slower β
β QQuery 19 β 230.16 ms β 235.23 ms β no change β
β QQuery 20 β 271.58 ms β 266.95 ms β no change β
β QQuery 21 β 664.05 ms β 660.93 ms β no change β
β QQuery 22 β 59.16 ms β 58.33 ms β no change β
βββββββββββββ΄ββββββββββββ΄βββββββββββββββββββββββββββββ΄βββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββ³ββββββββββββ
β Benchmark Summary β β
β‘ββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β Total Time (HEAD) β 6524.44ms β
β Total Time (perf-hash-join-flat-chains) β 6625.39ms β
β Average Time (HEAD) β 296.57ms β
β Average Time (perf-hash-join-flat-chains) β 301.15ms β
β Queries Faster β 0 β
β Queries Slower β 1 β
β Queries with No Change β 21 β
β Queries with Failure β 0 β
βββββββββββββββββββββββββββββββββββββββββββββ΄ββββββββββββ
Distribution per query (min / mean Β±stddev / max):
Comparing HEAD and perf-hash-join-flat-chains
--------------------
Benchmark tpch_sf10.json
--------------------
βββββββββββββ³βββββββββββββββββββββββββββββββββββββ³βββββββββββββββββββββββββββββββββββββββ³ββββββββββββββββ
β Query β HEAD β perf-hash-join-flat-chains β Change β
β‘ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β QQuery 1 β 328.37 / 330.08 Β±1.44 / 332.67 ms β 327.89 / 330.77 Β±2.39 / 334.99 ms β no change β
β QQuery 2 β 89.53 / 90.90 Β±1.26 / 92.81 ms β 89.39 / 90.91 Β±1.44 / 92.92 ms β no change β
β QQuery 3 β 214.09 / 220.74 Β±4.74 / 225.21 ms β 215.36 / 219.76 Β±2.64 / 222.95 ms β no change β
β QQuery 4 β 114.45 / 115.61 Β±0.96 / 117.18 ms β 115.30 / 116.95 Β±1.28 / 118.76 ms β no change β
β QQuery 5 β 341.96 / 348.45 Β±6.05 / 356.32 ms β 348.20 / 360.69 Β±13.40 / 386.12 ms β no change β
β QQuery 6 β 100.24 / 101.96 Β±1.56 / 104.88 ms β 100.46 / 103.23 Β±3.83 / 110.42 ms β no change β
β QQuery 7 β 442.86 / 449.75 Β±6.35 / 461.04 ms β 441.33 / 453.18 Β±6.57 / 459.74 ms β no change β
β QQuery 8 β 354.95 / 359.72 Β±3.45 / 365.21 ms β 356.22 / 362.16 Β±3.36 / 365.65 ms β no change β
β QQuery 9 β 508.83 / 510.85 Β±1.64 / 513.28 ms β 509.05 / 522.95 Β±19.62 / 561.68 ms β no change β
β QQuery 10 β 285.41 / 291.53 Β±4.70 / 297.66 ms β 285.10 / 299.13 Β±13.86 / 321.88 ms β no change β
β QQuery 11 β 61.28 / 62.61 Β±0.91 / 63.99 ms β 60.86 / 62.58 Β±1.18 / 63.89 ms β no change β
β QQuery 12 β 119.43 / 121.73 Β±1.71 / 124.36 ms β 122.04 / 127.84 Β±7.06 / 141.02 ms β 1.05x slower β
β QQuery 13 β 298.84 / 311.12 Β±9.83 / 328.50 ms β 300.17 / 310.14 Β±7.44 / 320.04 ms β no change β
β QQuery 14 β 166.92 / 172.31 Β±6.55 / 184.99 ms β 168.82 / 175.15 Β±5.66 / 185.50 ms β no change β
β QQuery 15 β 296.21 / 297.70 Β±1.49 / 300.38 ms β 297.93 / 303.33 Β±4.31 / 309.07 ms β no change β
β QQuery 16 β 64.16 / 73.95 Β±13.41 / 100.53 ms β 63.21 / 65.58 Β±1.84 / 68.46 ms β +1.13x faster β
β QQuery 17 β 577.71 / 584.52 Β±6.11 / 595.86 ms β 586.25 / 594.52 Β±7.00 / 606.49 ms β no change β
β QQuery 18 β 934.25 / 967.60 Β±26.63 / 998.53 ms β 1016.36 / 1025.48 Β±8.85 / 1039.48 ms β 1.06x slower β
β QQuery 19 β 230.16 / 253.65 Β±21.21 / 288.61 ms β 235.23 / 256.23 Β±26.47 / 305.36 ms β no change β
β QQuery 20 β 271.58 / 276.21 Β±2.59 / 279.49 ms β 266.95 / 271.46 Β±4.55 / 279.87 ms β no change β
β QQuery 21 β 664.05 / 667.27 Β±2.18 / 669.72 ms β 660.93 / 668.29 Β±4.21 / 673.51 ms β no change β
β QQuery 22 β 59.16 / 61.87 Β±2.68 / 66.86 ms β 58.33 / 61.25 Β±1.56 / 62.50 ms β no change β
βββββββββββββ΄βββββββββββββββββββββββββββββββββββββ΄βββββββββββββββββββββββββββββββββββββββ΄ββββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββ³ββββββββββββ
β Benchmark Summary β β
β‘ββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β Total Time (HEAD) β 6670.13ms β
β Total Time (perf-hash-join-flat-chains) β 6781.58ms β
β Average Time (HEAD) β 303.19ms β
β Average Time (perf-hash-join-flat-chains) β 308.25ms β
β Queries Faster β 1 β
β Queries Slower β 2 β
β Queries with No Change β 19 β
β Queries with Failure β 0 β
βββββββββββββββββββββββββββββββββββββββββββββ΄ββββββββββββ
```
</p>
</details>
<details><summary>Resource Usage</summary>
**tpch10 β base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 35.0s |
| Peak memory | 14.4 GiB |
| Avg memory | 3.0 GiB |
| CPU user | 338.2s |
| CPU sys | 19.9s |
| Peak spill | 0 B |
**tpch10 β branch**
| Metric | Value |
|--------|-------|
| Wall time | 35.0s |
| Peak memory | 13.0 GiB |
| Avg memory | 2.9 GiB |
| CPU user | 345.0s |
| CPU sys | 19.3s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6251259130
π€ Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/26447#issuecomment-6251247997)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c6251247997-3572-kxz7v 6.12.94+ #1 SMP Fri Aug 21 08:00:16 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing perf-hash-join-flat-chains (80c53008bb28094009845fce18a214f256e83ef3) to 484183d (merge-base) [diff](https://github.com/apache/datafusion/compare/484183dc34ea565190d9cd4a66db6d24789f95d0..80c53008bb28094009845fce18a214f256e83ef3)
<details><summary>Run configuration</summary>
```yaml
run benchmark clickbench_partitioned
```
</details>
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "comphead (via GitHub) via github" <gi...@datafusion.apache.org>.
comphead commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6533395655
`hj` benchmark is good now, thanks @andygrove
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6524775957
@comphead @Dandandan seems like a nice speedup. WDYT?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6525293059
I looked into TPC-DS q15, and this PR doesn't change how it runs. Its three joins build on primary keys (`customer`, `customer_address` and `date_dim`), so no key repeats and nothing is grouped. The join metrics match main's.
Running main and this PR alternately on an M3 Max (`release-nonlto`, 12 partitions) doesn't show the slowdown either. On this PR, q15's median time was 1.007x main's when run on its own (8 rounds of 5 iterations), and 0.988x within the full TPC-DS suite (4 rounds). There, the other queries were within 0.96x to 1.04x of main, apart from q72, which was 1.73x faster. The bot runs main and this PR once each, so the 6% on q15 looks like run-to-run noise.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6251368710
π€ Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/26447#issuecomment-6251247997)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
Comparing perf-hash-join-flat-chains (80c53008bb28094009845fce18a214f256e83ef3) to 484183d (merge-base) [diff](https://github.com/apache/datafusion/compare/484183dc34ea565190d9cd4a66db6d24789f95d0..80c53008bb28094009845fce18a214f256e83ef3)
<details><summary>Run configuration</summary>
```yaml
run benchmark clickbench_partitioned
```
</details>
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
Comparing HEAD and perf-hash-join-flat-chains
--------------------
Benchmark clickbench_partitioned.json
--------------------
βββββββββββββ³βββββββββββββ³βββββββββββββββββββββββββββββ³ββββββββββββββββ
β Query β HEAD β perf-hash-join-flat-chains β Change β
β‘ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β QQuery 0 β 1.18 ms β 1.20 ms β no change β
β QQuery 1 β 11.41 ms β 11.42 ms β no change β
β QQuery 2 β 35.86 ms β 35.96 ms β no change β
β QQuery 3 β 30.94 ms β 30.99 ms β no change β
β QQuery 4 β 229.26 ms β 233.01 ms β no change β
β QQuery 5 β 269.63 ms β 272.81 ms β no change β
β QQuery 6 β 1.22 ms β 1.23 ms β no change β
β QQuery 7 β 12.63 ms β 12.55 ms β no change β
β QQuery 8 β 328.47 ms β 328.49 ms β no change β
β QQuery 9 β 468.28 ms β 457.44 ms β no change β
β QQuery 10 β 63.32 ms β 63.96 ms β no change β
β QQuery 11 β 73.89 ms β 74.14 ms β no change β
β QQuery 12 β 257.85 ms β 261.04 ms β no change β
β QQuery 13 β 355.66 ms β 363.55 ms β no change β
β QQuery 14 β 276.27 ms β 273.84 ms β no change β
β QQuery 15 β 280.91 ms β 278.64 ms β no change β
β QQuery 16 β 612.56 ms β 613.31 ms β no change β
β QQuery 17 β 620.02 ms β 618.38 ms β no change β
β QQuery 18 β 1262.40 ms β 1256.29 ms β no change β
β QQuery 19 β 27.00 ms β 27.12 ms β no change β
β QQuery 20 β 513.28 ms β 517.18 ms β no change β
β QQuery 21 β 503.49 ms β 515.98 ms β no change β
β QQuery 22 β 993.57 ms β 981.48 ms β no change β
β QQuery 23 β 3029.62 ms β 3005.24 ms β no change β
β QQuery 24 β 40.37 ms β 40.38 ms β no change β
β QQuery 25 β 103.64 ms β 103.94 ms β no change β
β QQuery 26 β 42.16 ms β 40.70 ms β no change β
β QQuery 27 β 505.97 ms β 517.36 ms β no change β
β QQuery 28 β 2894.35 ms β 2864.65 ms β no change β
β QQuery 29 β 38.95 ms β 38.77 ms β no change β
β QQuery 30 β 305.70 ms β 299.30 ms β no change β
β QQuery 31 β 281.98 ms β 270.57 ms β no change β
β QQuery 32 β 1090.35 ms β 1082.64 ms β no change β
β QQuery 33 β 1518.73 ms β 1562.20 ms β no change β
β QQuery 34 β 1567.87 ms β 1534.94 ms β no change β
β QQuery 35 β 296.86 ms β 291.67 ms β no change β
β QQuery 36 β 65.06 ms β 66.35 ms β no change β
β QQuery 37 β 34.66 ms β 34.65 ms β no change β
β QQuery 38 β 41.74 ms β 41.43 ms β no change β
β QQuery 39 β 153.63 ms β 134.56 ms β +1.14x faster β
β QQuery 40 β 13.43 ms β 13.71 ms β no change β
β QQuery 41 β 12.94 ms β 13.23 ms β no change β
β QQuery 42 β 12.68 ms β 12.91 ms β no change β
βββββββββββββ΄βββββββββββββ΄βββββββββββββββββββββββββββββ΄ββββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββ³βββββββββββββ
β Benchmark Summary β β
β‘βββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β Total Time (HEAD) β 19279.76ms β
β Total Time (perf-hash-join-flat-chains) β 19199.22ms β
β Average Time (HEAD) β 448.37ms β
β Average Time (perf-hash-join-flat-chains) β 446.49ms β
β Queries Faster β 1 β
β Queries Slower β 0 β
β Queries with No Change β 42 β
β Queries with Failure β 0 β
βββββββββββββββββββββββββββββββββββββββββββββ΄βββββββββββββ
Distribution per query (min / mean Β±stddev / max):
Comparing HEAD and perf-hash-join-flat-chains
--------------------
Benchmark clickbench_partitioned.json
--------------------
βββββββββββββ³βββββββββββββββββββββββββββββββββββββββββ³βββββββββββββββββββββββββββββββββββββββββ³ββββββββββββββββ
β Query β HEAD β perf-hash-join-flat-chains β Change β
β‘ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β QQuery 0 β 1.18 / 4.13 Β±5.82 / 15.77 ms β 1.20 / 4.13 Β±5.81 / 15.75 ms β no change β
β QQuery 1 β 11.41 / 11.59 Β±0.12 / 11.72 ms β 11.42 / 11.84 Β±0.36 / 12.50 ms β no change β
β QQuery 2 β 35.86 / 36.29 Β±0.24 / 36.58 ms β 35.96 / 36.19 Β±0.23 / 36.52 ms β no change β
β QQuery 3 β 30.94 / 31.56 Β±0.73 / 32.99 ms β 30.99 / 31.52 Β±0.34 / 31.99 ms β no change β
β QQuery 4 β 229.26 / 235.34 Β±3.91 / 240.92 ms β 233.01 / 237.48 Β±3.92 / 243.78 ms β no change β
β QQuery 5 β 269.63 / 274.43 Β±2.67 / 277.77 ms β 272.81 / 274.56 Β±1.37 / 275.98 ms β no change β
β QQuery 6 β 1.22 / 1.38 Β±0.24 / 1.85 ms β 1.23 / 1.39 Β±0.23 / 1.84 ms β no change β
β QQuery 7 β 12.63 / 12.74 Β±0.10 / 12.86 ms β 12.55 / 12.79 Β±0.16 / 13.04 ms β no change β
β QQuery 8 β 328.47 / 332.61 Β±2.69 / 336.50 ms β 328.49 / 333.51 Β±3.15 / 336.98 ms β no change β
β QQuery 9 β 468.28 / 471.83 Β±2.28 / 475.44 ms β 457.44 / 470.25 Β±12.00 / 491.68 ms β no change β
β QQuery 10 β 63.32 / 63.82 Β±0.49 / 64.72 ms β 63.96 / 67.76 Β±7.01 / 81.78 ms β 1.06x slower β
β QQuery 11 β 73.89 / 75.14 Β±0.76 / 75.89 ms β 74.14 / 76.87 Β±4.06 / 84.96 ms β no change β
β QQuery 12 β 257.85 / 263.49 Β±5.42 / 273.33 ms β 261.04 / 263.47 Β±3.50 / 270.37 ms β no change β
β QQuery 13 β 355.66 / 367.70 Β±16.35 / 399.81 ms β 363.55 / 370.80 Β±7.42 / 384.70 ms β no change β
β QQuery 14 β 276.27 / 281.06 Β±5.67 / 292.11 ms β 273.84 / 280.81 Β±7.63 / 295.58 ms β no change β
β QQuery 15 β 280.91 / 296.16 Β±9.49 / 306.63 ms β 278.64 / 294.46 Β±10.70 / 310.89 ms β no change β
β QQuery 16 β 612.56 / 627.96 Β±11.08 / 645.04 ms β 613.31 / 626.46 Β±16.14 / 657.66 ms β no change β
β QQuery 17 β 620.02 / 630.51 Β±8.25 / 641.61 ms β 618.38 / 634.93 Β±11.88 / 649.28 ms β no change β
β QQuery 18 β 1262.40 / 1280.86 Β±13.59 / 1304.30 ms β 1256.29 / 1281.95 Β±15.58 / 1295.01 ms β no change β
β QQuery 19 β 27.00 / 30.86 Β±7.02 / 44.89 ms β 27.12 / 44.91 Β±21.33 / 74.97 ms β 1.46x slower β
β QQuery 20 β 513.28 / 523.86 Β±8.33 / 537.69 ms β 517.18 / 526.82 Β±7.80 / 539.44 ms β no change β
β QQuery 21 β 503.49 / 515.14 Β±7.06 / 524.62 ms β 515.98 / 522.54 Β±7.59 / 536.13 ms β no change β
β QQuery 22 β 993.57 / 998.57 Β±4.40 / 1004.13 ms β 981.48 / 989.86 Β±8.52 / 1005.26 ms β no change β
β QQuery 23 β 3029.62 / 3271.84 Β±215.37 / 3651.58 ms β 3005.24 / 3211.37 Β±175.60 / 3523.26 ms β no change β
β QQuery 24 β 40.37 / 53.25 Β±21.63 / 96.38 ms β 40.38 / 71.64 Β±61.54 / 194.72 ms β 1.35x slower β
β QQuery 25 β 103.64 / 136.40 Β±63.47 / 263.33 ms β 103.94 / 219.63 Β±226.56 / 672.75 ms β 1.61x slower β
β QQuery 26 β 42.16 / 48.75 Β±11.29 / 71.30 ms β 40.70 / 41.82 Β±1.27 / 44.10 ms β +1.17x faster β
β QQuery 27 β 505.97 / 518.04 Β±9.98 / 532.04 ms β 517.36 / 524.38 Β±7.07 / 537.63 ms β no change β
β QQuery 28 β 2894.35 / 2905.40 Β±8.96 / 2916.17 ms β 2864.65 / 2916.17 Β±62.40 / 3038.02 ms β no change β
β QQuery 29 β 38.95 / 44.17 Β±7.57 / 58.60 ms β 38.77 / 39.11 Β±0.20 / 39.29 ms β +1.13x faster β
β QQuery 30 β 305.70 / 317.01 Β±15.41 / 346.90 ms β 299.30 / 332.38 Β±39.17 / 406.98 ms β no change β
β QQuery 31 β 281.98 / 291.43 Β±10.34 / 311.51 ms β 270.57 / 285.92 Β±9.79 / 300.15 ms β no change β
β QQuery 32 β 1090.35 / 1340.76 Β±291.57 / 1864.22 ms β 1082.64 / 1251.96 Β±238.76 / 1718.81 ms β +1.07x faster β
β QQuery 33 β 1518.73 / 1574.20 Β±50.02 / 1664.34 ms β 1562.20 / 1596.05 Β±22.32 / 1630.62 ms β no change β
β QQuery 34 β 1567.87 / 1635.05 Β±84.68 / 1793.64 ms β 1534.94 / 1580.68 Β±40.62 / 1637.00 ms β no change β
β QQuery 35 β 296.86 / 344.71 Β±60.52 / 452.43 ms β 291.67 / 335.88 Β±74.50 / 483.98 ms β no change β
β QQuery 36 β 65.06 / 67.94 Β±1.82 / 70.42 ms β 66.35 / 74.26 Β±5.20 / 80.49 ms β 1.09x slower β
β QQuery 37 β 34.66 / 40.90 Β±5.67 / 49.15 ms β 34.65 / 41.58 Β±6.14 / 49.54 ms β no change β
β QQuery 38 β 41.74 / 43.00 Β±1.08 / 44.60 ms β 41.43 / 46.46 Β±5.22 / 56.37 ms β 1.08x slower β
β QQuery 39 β 153.63 / 158.56 Β±7.25 / 172.83 ms β 134.56 / 152.43 Β±14.56 / 176.17 ms β no change β
β QQuery 40 β 13.43 / 14.68 Β±0.65 / 15.30 ms β 13.71 / 18.17 Β±6.00 / 29.84 ms β 1.24x slower β
β QQuery 41 β 12.94 / 13.21 Β±0.15 / 13.37 ms β 13.23 / 13.43 Β±0.18 / 13.74 ms β no change β
β QQuery 42 β 12.68 / 12.85 Β±0.13 / 13.00 ms β 12.91 / 12.98 Β±0.07 / 13.11 ms β no change β
βββββββββββββ΄βββββββββββββββββββββββββββββββββββββββββ΄βββββββββββββββββββββββββββββββββββββββββ΄ββββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββ³βββββββββββββ
β Benchmark Summary β β
β‘βββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β Total Time (HEAD) β 20199.16ms β
β Total Time (perf-hash-join-flat-chains) β 20161.61ms β
β Average Time (HEAD) β 469.75ms β
β Average Time (perf-hash-join-flat-chains) β 468.87ms β
β Queries Faster β 3 β
β Queries Slower β 7 β
β Queries with No Change β 33 β
β Queries with Failure β 0 β
βββββββββββββββββββββββββββββββββββββββββββββ΄βββββββββββββ
```
</p>
</details>
<details><summary>Resource Usage</summary>
**clickbench_partitioned β base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 105.0s |
| Peak memory | 18.3 GiB |
| Avg memory | 6.0 GiB |
| CPU user | 989.2s |
| CPU sys | 97.0s |
| Peak spill | 0 B |
**clickbench_partitioned β branch**
| Metric | Value |
|--------|-------|
| Wall time | 105.0s |
| Peak memory | 18.5 GiB |
| Avg memory | 5.9 GiB |
| CPU user | 987.9s |
| CPU sys | 96.2s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangbot (via GitHub) via github" <gi...@datafusion.apache.org>.
adriangbot commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6532463060
π€ Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/26447#issuecomment-6532278515)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
Comparing perf-hash-join-flat-chains (71afb43ea7ef43b49f4129d005b17a6325080f9c) to 5f5418e (merge-base) [diff](https://github.com/apache/datafusion/compare/5f5418e2f3abee1020796d673904e8a69c977ca6..71afb43ea7ef43b49f4129d005b17a6325080f9c)
<details><summary>Run configuration</summary>
```yaml
run benchmark hj
```
</details>
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
Comparing HEAD and perf-hash-join-flat-chains
--------------------
Benchmark hj.json
--------------------
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ³ββββββββββββ³βββββββββββββββββββββββββββββ³ββββββββββββββββ
β Query β HEAD β perf-hash-join-flat-chains β Change β
β‘βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β QQuery 1_density=1_prob_hit=1_25*1.5M β 1.90 ms β 1.88 ms β no change β
β QQuery 2_density=0.026_prob_hit=1_25*1.5M β 4.60 ms β 4.58 ms β no change β
β QQuery 3_density=1_prob_hit=1_100K*60M β 80.34 ms β 79.05 ms β no change β
β QQuery 4_density=1_prob_hit=0.1_100K*60M β 201.87 ms β 166.38 ms β +1.21x faster β
β QQuery 5_density=0.75_prob_hit=1_100K*60M β 725.22 ms β 180.71 ms β +4.01x faster β
β QQuery 6_density=0.75_prob_hit=0.1_100K*60M β 282.90 ms β 243.02 ms β +1.16x faster β
β QQuery 7_density=0.5_prob_hit=1_100K*60M β 715.89 ms β 174.19 ms β +4.11x faster β
β QQuery 8_density=0.5_prob_hit=0.1_100K*60M β 264.39 ms β 227.89 ms β +1.16x faster β
β QQuery 9_density=0.2_prob_hit=1_100K*60M β 738.14 ms β 174.85 ms β +4.22x faster β
β QQuery 10_density=0.2_prob_hit=0.1_100K*60M β 261.21 ms β 235.00 ms β +1.11x faster β
β QQuery 11_density=0.1_prob_hit=1_100K*60M β 726.60 ms β 175.67 ms β +4.14x faster β
β QQuery 12_density=0.1_prob_hit=0.1_100K*60M β 260.75 ms β 231.65 ms β +1.13x faster β
β QQuery 13_density=0.01_prob_hit=1_100K*60M β 773.08 ms β 195.19 ms β +3.96x faster β
β QQuery 14_density=0.01_prob_hit=0.1_100K*60M β 310.63 ms β 287.72 ms β +1.08x faster β
β QQuery 15_density=0.2_prob_hit=0.1_100K_(20%_dups)*60M β 275.81 ms β 216.34 ms β +1.27x faster β
β QQuery 16_density=1_prob_hit=1_25*1.5M_RightSemi β 2.28 ms β 2.34 ms β no change β
β QQuery 17_density=1_prob_hit=1_100K*60M_RightSemi β 86.91 ms β 82.15 ms β +1.06x faster β
β QQuery 18_density=1_prob_hit=0.1_100K*60M_RightSemi β 101.85 ms β 109.45 ms β 1.07x slower β
β QQuery 19_density=1_prob_hit=1_25*1.5M_RightAnti β 1.83 ms β 1.89 ms β no change β
β QQuery 20_density=1_prob_hit=1_100K*60M_RightAnti β 77.80 ms β 74.04 ms β no change β
β QQuery 21_density=1_prob_hit=0.1_100K*60M_RightAnti β 111.63 ms β 119.41 ms β 1.07x slower β
β QQuery 22_density=1_prob_hit=0.01_100K_(fanout_100)*60M_RightSemi β 86.85 ms β 67.04 ms β +1.30x faster β
β QQuery 23_density=1_prob_hit=1_32K_(fanout~78)*2.3M_long_keys_count β 163.32 ms β 128.41 ms β +1.27x faster β
β QQuery 24_density=1_prob_hit=1_3K_(single_hot_bucket)*20K_long_keys_count β 527.47 ms β 393.79 ms β +1.34x faster β
β QQuery 25_density=1_prob_hit=1_20K_(fanout~78_multi_key)*240K_multi_key_count β 234.26 ms β 198.99 ms β +1.18x faster β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ΄ββββββββββββ΄βββββββββββββββββββββββββββββ΄ββββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββ³ββββββββββββ
β Benchmark Summary β β
β‘ββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β Total Time (HEAD) β 7017.55ms β
β Total Time (perf-hash-join-flat-chains) β 3771.61ms β
β Average Time (HEAD) β 280.70ms β
β Average Time (perf-hash-join-flat-chains) β 150.86ms β
β Queries Faster β 17 β
β Queries Slower β 2 β
β Queries with No Change β 6 β
β Queries with Failure β 0 β
βββββββββββββββββββββββββββββββββββββββββββββ΄ββββββββββββ
Distribution per query (min / mean Β±stddev / max):
Comparing HEAD and perf-hash-join-flat-chains
--------------------
Benchmark hj.json
--------------------
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ³βββββββββββββββββββββββββββββββββββββ³βββββββββββββββββββββββββββββββββββββ³ββββββββββββββββ
β Query β HEAD β perf-hash-join-flat-chains β Change β
β‘ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β QQuery 1_density=1_prob_hit=1_25*1.5M β 1.90 / 2.19 Β±0.45 / 3.09 ms β 1.88 / 2.19 Β±0.47 / 3.13 ms β no change β
β QQuery 2_density=0.026_prob_hit=1_25*1.5M β 4.60 / 4.81 Β±0.13 / 4.99 ms β 4.58 / 4.74 Β±0.17 / 5.01 ms β no change β
β QQuery 3_density=1_prob_hit=1_100K*60M β 80.34 / 81.43 Β±1.06 / 83.05 ms β 79.05 / 79.61 Β±0.50 / 80.42 ms β no change β
β QQuery 4_density=1_prob_hit=0.1_100K*60M β 201.87 / 217.40 Β±19.78 / 255.95 ms β 166.38 / 173.66 Β±8.79 / 190.75 ms β +1.25x faster β
β QQuery 5_density=0.75_prob_hit=1_100K*60M β 725.22 / 748.37 Β±19.11 / 772.63 ms β 180.71 / 186.13 Β±3.62 / 191.30 ms β +4.02x faster β
β QQuery 6_density=0.75_prob_hit=0.1_100K*60M β 282.90 / 302.17 Β±28.11 / 357.67 ms β 243.02 / 259.74 Β±20.91 / 300.98 ms β +1.16x faster β
β QQuery 7_density=0.5_prob_hit=1_100K*60M β 715.89 / 734.71 Β±10.48 / 744.19 ms β 174.19 / 179.22 Β±7.09 / 193.15 ms β +4.10x faster β
β QQuery 8_density=0.5_prob_hit=0.1_100K*60M β 264.39 / 284.04 Β±19.35 / 315.94 ms β 227.89 / 240.96 Β±13.86 / 260.91 ms β +1.18x faster β
β QQuery 9_density=0.2_prob_hit=1_100K*60M β 738.14 / 761.48 Β±17.74 / 791.40 ms β 174.85 / 191.52 Β±21.93 / 230.62 ms β +3.98x faster β
β QQuery 10_density=0.2_prob_hit=0.1_100K*60M β 261.21 / 294.05 Β±35.79 / 352.35 ms β 235.00 / 242.59 Β±6.22 / 249.47 ms β +1.21x faster β
β QQuery 11_density=0.1_prob_hit=1_100K*60M β 726.60 / 754.54 Β±20.14 / 776.11 ms β 175.67 / 185.98 Β±13.68 / 212.55 ms β +4.06x faster β
β QQuery 12_density=0.1_prob_hit=0.1_100K*60M β 260.75 / 281.90 Β±23.01 / 317.20 ms β 231.65 / 245.38 Β±15.58 / 275.25 ms β +1.15x faster β
β QQuery 13_density=0.01_prob_hit=1_100K*60M β 773.08 / 797.12 Β±21.18 / 835.47 ms β 195.19 / 205.70 Β±9.78 / 223.82 ms β +3.88x faster β
β QQuery 14_density=0.01_prob_hit=0.1_100K*60M β 310.63 / 336.42 Β±16.83 / 356.41 ms β 287.72 / 302.77 Β±16.44 / 333.69 ms β +1.11x faster β
β QQuery 15_density=0.2_prob_hit=0.1_100K_(20%_dups)*60M β 275.81 / 303.47 Β±17.04 / 320.32 ms β 216.34 / 238.40 Β±22.10 / 266.09 ms β +1.27x faster β
β QQuery 16_density=1_prob_hit=1_25*1.5M_RightSemi β 2.28 / 2.47 Β±0.13 / 2.66 ms β 2.34 / 2.48 Β±0.15 / 2.78 ms β no change β
β QQuery 17_density=1_prob_hit=1_100K*60M_RightSemi β 86.91 / 91.16 Β±6.90 / 104.77 ms β 82.15 / 96.97 Β±16.36 / 119.01 ms β 1.06x slower β
β QQuery 18_density=1_prob_hit=0.1_100K*60M_RightSemi β 101.85 / 113.17 Β±12.12 / 129.09 ms β 109.45 / 113.68 Β±8.05 / 129.78 ms β no change β
β QQuery 19_density=1_prob_hit=1_25*1.5M_RightAnti β 1.83 / 2.03 Β±0.19 / 2.39 ms β 1.89 / 1.97 Β±0.11 / 2.18 ms β no change β
β QQuery 20_density=1_prob_hit=1_100K*60M_RightAnti β 77.80 / 79.44 Β±1.00 / 80.48 ms β 74.04 / 75.95 Β±1.48 / 78.16 ms β no change β
β QQuery 21_density=1_prob_hit=0.1_100K*60M_RightAnti β 111.63 / 113.26 Β±1.01 / 114.60 ms β 119.41 / 120.26 Β±0.48 / 120.79 ms β 1.06x slower β
β QQuery 22_density=1_prob_hit=0.01_100K_(fanout_100)*60M_RightSemi β 86.85 / 88.55 Β±1.44 / 90.68 ms β 67.04 / 68.11 Β±1.18 / 70.34 ms β +1.30x faster β
β QQuery 23_density=1_prob_hit=1_32K_(fanout~78)*2.3M_long_keys_count β 163.32 / 164.57 Β±1.75 / 168.04 ms β 128.41 / 128.87 Β±0.37 / 129.43 ms β +1.28x faster β
β QQuery 24_density=1_prob_hit=1_3K_(single_hot_bucket)*20K_long_keys_count β 527.47 / 528.09 Β±0.73 / 529.46 ms β 393.79 / 394.59 Β±0.60 / 395.39 ms β +1.34x faster β
β QQuery 25_density=1_prob_hit=1_20K_(fanout~78_multi_key)*240K_multi_key_count β 234.26 / 237.34 Β±2.35 / 241.50 ms β 198.99 / 199.71 Β±0.83 / 201.27 ms β +1.19x faster β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ΄βββββββββββββββββββββββββββββββββββββ΄βββββββββββββββββββββββββββββββββββββ΄ββββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββ³ββββββββββββ
β Benchmark Summary β β
β‘ββββββββββββββββββββββββββββββββββββββββββββββββββββββββ©
β Total Time (HEAD) β 7324.17ms β
β Total Time (perf-hash-join-flat-chains) β 3941.17ms β
β Average Time (HEAD) β 292.97ms β
β Average Time (perf-hash-join-flat-chains) β 157.65ms β
β Queries Faster β 16 β
β Queries Slower β 2 β
β Queries with No Change β 7 β
β Queries with Failure β 0 β
βββββββββββββββββββββββββββββββββββββββββββββ΄ββββββββββββ
```
</p>
</details>
<details><summary>Resource Usage</summary>
**hj β base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 40.0s |
| Peak memory | 2.4 GiB |
| Avg memory | 1.2 GiB |
| CPU user | 336.7s |
| CPU sys | 12.3s |
| Peak spill | 0 B |
**hj β branch**
| Metric | Value |
|--------|-------|
| Wall time | 25.0s |
| Peak memory | 2.3 GiB |
| Avg memory | 946.2 MiB |
| CPU user | 163.0s |
| CPU sys | 8.1s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "andygrove (via GitHub) via github" <gi...@datafusion.apache.org>.
andygrove commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6544865063
Thanks @comphead for the review. I've pushed the changes and replied to each comment inline. On the design questions:
**Following several probe rows' chains at once.** I hadn't tried it, so I prototyped it on main: the probe follows the chains of up to 16 probe rows at once, where the first emits its matches and each other holds up to 128 of its own until it is first, so the output order doesn't change. It needs no pass at build time, but it is slower than grouping wherever the probe follows chains, and slower than main when the chains fit in the cache, as in `hj` Q24, whose 3K build rows share one key:
| `release-nonlto`, M3 Max, 16 partitions | main | Interleaved probe | Grouped rows |
| --- | --- | --- | --- |
| #17494 reproduction, dense keys | 97.3 s, 89.5 s | 29.6 s, 29.5 s | 16.4 s, 15.9 s |
| #17494 reproduction, sparse keys | 90.7 s, 90.3 s | 41.9 s, 43.5 s | 29.4 s, 29.5 s |
| TPC-DS q72, SF1 | 1,061 ms | 811 ms | 676 ms |
| `hj` Q5 to Q13, odd, compared with main | 1 | 0.85 to 0.89 | 0.32 to 0.36 |
| `hj` Q24, compared with main | 1 | 2.09 | 0.77 |
The interleaved probe still makes a random load for every match, while grouped rows are read in order, so I kept grouping.
The `hj` queries run `Partitioned`, where each partition groups its own rows, so no grouping pass holds up the other partitions. On this machine the 10% hit cases (Q4 to Q14, even) take 0.75 to 0.98 of main's time, where they were 1% to 10% slower on the 7950X3D. A small probe still pays for grouping. With the 64M build rows of the reproduction and 16K probe rows, the query takes 0.13 to 0.16 s on main and 0.19 to 0.20 s with this PR in `Partitioned` mode with dense keys, and 0.31 s against 0.41 s in `CollectLeft` mode. With sparse keys it takes 0.27 to 0.31 s against 0.33 s, and 2.1 s against 2.7 to 2.8 s.
**One rule for `ArrayMap` and the hash maps.** Measuring it changed my mind. Grouping whenever a key repeats made a build of 64M rows with 1.1 rows per key, in `CollectLeft` mode, 3.7 times slower: 0.49 s against 0.13 s on main. Both maps now group only when the keys have at least two rows each on average. An `ArrayMap` with at least two rows for every slot still sorts its rows as it is built, and any other keeps main's chain, which `group_rows` groups as for a hash map, after the build's other reservations (see my reply to @adriangb). That query now takes 0.12 s, faster than main, because the build reads the key values directly rather than with the array's iterator, whose `Option` for each row the compiler kept in memory.
**The nits.** The `MidChain` doc covers both layouts, the rationale is only on `JoinHashMapType::group_rows`, and the new `grouped_map_count` metric counts the maps whose rows are grouped, next to `array_map_created_count` in `EXPLAIN ANALYZE`. A hash map that had no room for its groups shows 0.
With these changes, TPC-DS SF1 is within 0.86 to 1.11 of main apart from q72 (0.58), and takes 5.8 s in all against 6.4 s. Thanks for updating the branch: the benchmark bot clones the last 200 commits of main, which no longer reached the merge base, so it needed main merged in to run.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "andygrove (via GitHub) via github" <gi...@datafusion.apache.org>.
andygrove commented on code in PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#discussion_r4432073585
##########
datafusion/physical-plan/src/joins/join_hash_map.rs:
##########
@@ -383,6 +641,33 @@ where
let zero = T::try_from(0).unwrap();
let one = T::try_from(1).unwrap();
+ if !groups.is_empty() {
+ for (row_idx, hash_value) in iter {
+ if let Some((_, pos)) =
+ map.find(*hash_value, |(hash, _)| *hash_value == *hash)
+ {
+ let pos: u64 = (*pos).into();
+ let pos = pos as usize;
+ let len: u64 = groups[pos].into();
+ for &row in &groups[pos + 1..=pos + len as usize] {
+ let match_row_idx = if let Some(offset) = deleted_offset {
+ let offset = T::try_from(offset).unwrap();
+ if row < offset {
Review Comment:
This branch is gone: after @comphead's review, `get_matched_indices` is as on main, since only the symmetric hash join calls it and its map is never grouped, so calling it on grouped rows is `unreachable!`.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "andygrove (via GitHub) via github" <gi...@datafusion.apache.org>.
andygrove commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6544904332
@comphead @adriangb for full transparency, I feel like this PR is getting away from a bit with all the back and forth between our agents. I guess it is fine if everyone is happy with the end state, but I wonder if this should have been multiple PRs building on each other.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6525905017
Q72 is definitely faster thanks.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6526103316
Benchmark for [this request](https://github.com/apache/datafusion/pull/26447#issuecomment-6526017495) failed before finishing (Kubernetes reason: `BackoffLimitExceeded`).
Benchmarks requested: `hj`
<details><summary>Runner log (last 40 lines)</summary>
```
2026-10-30T15:09:34.368441Z INFO runner starting benchmark runner bench_type=Datafusion, pr_url=https://github.com/apache/datafusion/pull/26447, benchmarks=hj
2026-10-30T15:09:34.429975Z INFO benchmark_controller::runner::bench_datafusion === Cloning PR branch ===
2026-10-30T15:09:34.429998Z INFO benchmark_controller::runner::shell running command cmd=git, args=["clone", "--depth=200", "https://github.com/apache/datafusion.git", "/workspace/datafusion-branch"], cwd="/"
2026-10-30T15:09:44.442610Z INFO benchmark_controller::runner::shell running command cmd=git, args=["fetch", "origin", "refs/pull/26447/head:perf-hash-join-flat-chains", "main"], cwd="/workspace/datafusion-branch"
2026-10-30T15:10:19.451644Z INFO benchmark_controller::runner::shell running command cmd=git, args=["checkout", "perf-hash-join-flat-chains"], cwd="/workspace/datafusion-branch"
2026-10-30T15:10:24.453831Z INFO benchmark_controller::runner::shell running command cmd=git, args=["merge-base", "HEAD", "origin/main"], cwd="/workspace/datafusion-branch"
2026-10-30T15:10:29.455935Z ERROR runner benchmark failed error=git merge-base: git merge-base HEAD origin/main exited with code 1
stdout:
stderr:
```
</details>
<details><summary>Kubernetes message</summary>
```
Job has reached the specified backoff limit
```
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: store the build rows of repeated hash join keys together [datafusion]
Posted by "andygrove (via GitHub) via github" <gi...@datafusion.apache.org>.
andygrove commented on PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6951635540
> [@andygrove](https://github.com/andygrove) maybe an easy first step would be to split the benchmarks into their own pr and then stack a pr on top that re-organizes the commits in some logical way that we can review refactors and tests on their own, etc.?
Done. Benchmark now in #27528
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org