You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Commit 83d1960
Browse filesBrowse the repository at this point in the historyBrowse files
Add the `hj_ordered_subset` SQL benchmark suite. The probe table
(`events`, 100 days x 200k rows, 100k-row row groups) is sorted by the
join key, and the build side matches 1 day, 10 days, or a scattered 1%
of the key range (control). The bounds of the hash join dynamic filter
can prune the probe row groups outside the matched range, and the
membership check passes almost every remaining row.
Subgroups `partitioned` (Q01-Q03) and `collect_left` (Q04-Q06) force
the HashJoinExec mode, which `expect_plan` checks. An assert checks
that every build row matches exactly one event. The load SQL writes the
data inline; HJOS_DAYS, HJOS_ROWS_PER_DAY and HJOS_RG_SIZE size it.
Co-Authored-By: Claude Opus 5.5 <[email protected]>
Copy file name to clipboardExpand all lines: benchmarks/README.md
+22Lines changed: 22 additions & 0 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -966,6 +966,28 @@ Several queries are included to test hash joins under various workloads.
966
966
./bench.sh run hj
967
967
```
968
968
969
+
## Hash Join Dynamic Filter on an Ordered Subset
970
+
971
+
This benchmark (`hj_ordered_subset`) measures the dynamic filter that a hash join pushes to its probe-side Parquet scan when the probe table is sorted by the join key and the build side matches an ordered subset of the key range. This is common for time-ordered fact tables: the events of one day, or of a range of days.
972
+
973
+
The load SQL writes an `events` table of 100 days x 200,000 rows (20M rows, 100,000-row row groups) sorted by `event_id`, and two build tables with one row for each event. The queries join `events` to 1 day (Q01, Q04), to 10 days (Q02, Q05), or to 1% of the events scattered over the whole range (Q03, Q06, the control). The bounds of the dynamic filter (`event_id >= min AND event_id <= max`) can prune the `events` row groups outside the matched range, and the membership check passes almost every row that remains. In the control, the bounds cannot prune anything.
974
+
975
+
The `partitioned` subgroup (Q01-Q03) forces `HashJoinExec` mode `Partitioned`, and the `collect_left` subgroup (Q04-Q06) forces mode `CollectLeft`.
976
+
977
+
### Example Run
978
+
979
+
```bash
980
+
# No need to generate data: the suite's load SQL writes the Parquet files
981
+
982
+
./bench.sh run hj_ordered_subset
983
+
984
+
# With parquet filter pushdown
985
+
DATAFUSION_EXECUTION_PARQUET_PUSHDOWN_FILTERS=true ./bench.sh run hj_ordered_subset
986
+
987
+
# Smaller data: 50 days x 100,000 rows
988
+
HJOS_DAYS=50 HJOS_ROWS_PER_DAY=100000 ./bench.sh run hj_ordered_subset
989
+
```
990
+
969
991
## Null-Aware Join
970
992
971
993
This benchmark focuses on `NOT IN` subqueries, which plan as null-aware joins: an
NOT IN across NULL fractions, to measure the per-pair join-filter work the correlated cases do
121
121
(data generated inline by the suite's load SQL from range(); knobs: NAJ_ROWS, NAJ_LARGE_ROWS)
122
+
hj_ordered_subset: Hash join dynamic filter on a probe table sorted by the join key, where the build side matches an ordered subset
123
+
(1 day, 10 days) of the key range, so the filter bounds can prune probe row groups; plus a scattered 1% control
124
+
(subgroups via BENCH_SUBGROUP: partitioned, collect_left)
125
+
(data generated inline by the suite's load SQL; knobs: HJOS_DAYS, HJOS_ROWS_PER_DAY, HJOS_RG_SIZE)
122
126
projection_subquery: IN / NOT IN / EXISTS subqueries in the SELECT list (see https://github.com/apache/datafusion/issues/25341); each query projects the
123
127
boolean subquery result and aggregates it, so the cost is the decorrelation plan and not the output size
124
128
(q07 correlates on '<' instead of '=', so it keeps the nested-loop plan and acts as the control)
@@ -295,6 +299,10 @@ main() {
295
299
# Data is generated inline by the suite's load SQL.
296
300
echo"projection_subquery: no external data to generate"
297
301
;;
302
+
hj_ordered_subset)
303
+
# Data is generated inline by the suite's load SQL (COPY).
304
+
echo"hj_ordered_subset: no external data to generate"
305
+
;;
298
306
asof_join)
299
307
data_asof_join
300
308
;;
@@ -552,6 +560,9 @@ main() {
552
560
projection_subquery)
553
561
run_projection_subquery
554
562
;;
563
+
hj_ordered_subset)
564
+
run_hj_ordered_subset
565
+
;;
555
566
asof_join)
556
567
run_asof_join
557
568
;;
@@ -1009,6 +1020,29 @@ run_null_aware_join() {
1009
1020
bash -c "$SQL_CARGO_COMMAND"
1010
1021
}
1011
1022
1023
+
# Runs the hj_ordered_subset suite: a hash join whose probe table is sorted by
1024
+
# the join key and whose build side matches an ordered subset of the key range,
1025
+
# so the bounds of the join's dynamic filter can prune probe row groups. Data is
1026
+
# generated inline by the load SQL (COPY), so there is no data step. Set
1027
+
# DATAFUSION_EXECUTION_PARQUET_PUSHDOWN_FILTERS to vary how the scan uses the
1028
+
# filter.
1029
+
# Knobs (string-substituted into the load SQL, not engine config):
1030
+
# BENCH_SUBGROUP run one subgroup (partitioned, collect_left)
1031
+
# HJOS_DAYS days in the events table (default 100, at least 50)
1032
+
# HJOS_ROWS_PER_DAY events per day (default 200_000)
Copy file name to clipboardExpand all lines: benchmarks/sql_benchmarks/README.md
+1Lines changed: 1 addition & 0 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -35,6 +35,7 @@ in the community:
35
35
|`clickbench_sorted`| ClickBench benchmark using a pre-sorted hits file. |
36
36
|`h2o`| The `h2o` benchmark |
37
37
|`hj`| Hash join benchmark |
38
+
|`hj_ordered_subset`| Hash join dynamic filter on a probe table sorted by the join key, where the build side matches an ordered subset of the key range (1 day, 10 days) or a scattered 1% (control). Subgroups (`--subgroup`): `partitioned`, `collect_left`. Size the data with `HJOS_DAYS`, `HJOS_ROWS_PER_DAY` and `HJOS_RG_SIZE`. |
38
39
|`imdb`| IMDb benchmark |
39
40
|`nlj`| Nested‑loop join benchmark |
40
41
|`null_aware_join`| Null-aware (`NOT IN`) hash join micro-benchmarks. Q01-Q03 are uncorrelated `NOT IN` across NULL fractions and are linear in the table size (`NAJ_LARGE_ROWS`, default `1000000`). Q04-Q08 are correlated, so the correlation predicate stays behind as a join filter that the join applies per candidate (build row × probe row) pair while deciding which outer rows are UNKNOWN; without an equality correlation there are no scope keys to narrow those pairs, so their cost grows with the square of `NAJ_ROWS` (default `10000`). Q08 adds an equality correlation, which turns those pairs into a hash lookup. All tables are built inline from `range()`, so there is no data step. |
0 commit comments