Skip to content

Commit 83d1960

Browse files
adriangbclaude
andcommitted
bench: add ordered-subset hash join dynamic filter benchmark
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]>
1 parent 2fee0f1 commit 83d1960

16 files changed

Lines changed: 270 additions & 0 deletions

‎benchmarks/README.md‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -966,6 +966,28 @@ Several queries are included to test hash joins under various workloads.
966966
./bench.sh run hj
967967
```
968968

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+
969991
## Null-Aware Join
970992

971993
This benchmark focuses on `NOT IN` subqueries, which plan as null-aware joins: an

‎benchmarks/bench.sh‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -119,6 +119,10 @@ spill_views: Sort and GROUP BY queries that spill StringView/BinaryVi
119119
null_aware_join: Null-aware (NOT IN) hash join micro-benchmarks: uncorrelated, non-equality-correlated and equality-correlated
120120
NOT IN across NULL fractions, to measure the per-pair join-filter work the correlated cases do
121121
(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)
122126
projection_subquery: IN / NOT IN / EXISTS subqueries in the SELECT list (see https://github.com/apache/datafusion/issues/25341); each query projects the
123127
boolean subquery result and aggregates it, so the cost is the decorrelation plan and not the output size
124128
(q07 correlates on '<' instead of '=', so it keeps the nested-loop plan and acts as the control)
@@ -295,6 +299,10 @@ main() {
295299
# Data is generated inline by the suite's load SQL.
296300
echo "projection_subquery: no external data to generate"
297301
;;
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+
;;
298306
asof_join)
299307
data_asof_join
300308
;;
@@ -552,6 +560,9 @@ main() {
552560
projection_subquery)
553561
run_projection_subquery
554562
;;
563+
hj_ordered_subset)
564+
run_hj_ordered_subset
565+
;;
555566
asof_join)
556567
run_asof_join
557568
;;
@@ -1009,6 +1020,29 @@ run_null_aware_join() {
10091020
bash -c "$SQL_CARGO_COMMAND"
10101021
}
10111022

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)
1033+
# HJOS_RG_SIZE parquet row-group size (default 100_000)
1034+
run_hj_ordered_subset() {
1035+
echo "Running hj_ordered_subset benchmark (subgroup=${BENCH_SUBGROUP:-all}, days=${HJOS_DAYS:-100}, rows_per_day=${HJOS_ROWS_PER_DAY:-200000}, rg_size=${HJOS_RG_SIZE:-100000})..."
1036+
debug_run env BENCH_NAME=hj_ordered_subset \
1037+
BENCH_RESULTS_FILE="$(sql_results_file hj_ordered_subset)" \
1038+
${BENCH_SUBGROUP:+BENCH_SUBGROUP="${BENCH_SUBGROUP}"} \
1039+
HJOS_DAYS="${HJOS_DAYS:-100}" \
1040+
HJOS_ROWS_PER_DAY="${HJOS_ROWS_PER_DAY:-200000}" \
1041+
HJOS_RG_SIZE="${HJOS_RG_SIZE:-100000}" \
1042+
${QUERY:+BENCH_QUERY="${QUERY}"} \
1043+
bash -c "$SQL_CARGO_COMMAND"
1044+
}
1045+
10121046
# Runs the projection_subquery suite: IN / NOT IN / EXISTS subqueries that sit
10131047
# in the SELECT list instead of a filter (see
10141048
# https://github.com/apache/datafusion/issues/25341). The load SQL builds the

‎benchmarks/sql_benchmarks/README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,7 @@ in the community:
3535
| `clickbench_sorted` | ClickBench benchmark using a pre-sorted hits file. |
3636
| `h2o` | The `h2o` benchmark |
3737
| `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`. |
3839
| `imdb` | IMDb benchmark |
3940
| `nlj` | Nested‑loop join benchmark |
4041
| `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. |
Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
# Partitioned join, build side = 1 day (1% of the event_id range, ordered).
2+
# The bounds of the dynamic filter can prune ~99% of the events row groups.
3+
subgroup partitioned
4+
5+
template sql_benchmarks/hj_ordered_subset/hj_ordered_subset.benchmark.template
6+
NAME=Q01_partitioned_ordered_1_day
7+
JOIN_MODE=partitioned
8+
PLAN_MODE=Partitioned
9+
BUILD_TABLE=labels_by_day
10+
BUILD_FILTER=l.day = 42
Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
# Partitioned join, build side = 10 days (10% of the event_id range, ordered).
2+
# The bounds of the dynamic filter can prune ~90% of the events row groups.
3+
subgroup partitioned
4+
5+
template sql_benchmarks/hj_ordered_subset/hj_ordered_subset.benchmark.template
6+
NAME=Q02_partitioned_ordered_10_days
7+
JOIN_MODE=partitioned
8+
PLAN_MODE=Partitioned
9+
BUILD_TABLE=labels_by_day
10+
BUILD_FILTER=l.day BETWEEN 40 AND 49
Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
# Control: partitioned join, build side = 1% of the events, scattered over the
2+
# whole event_id range. The bounds cannot prune anything; only the membership
3+
# check of the dynamic filter rejects rows.
4+
subgroup partitioned
5+
6+
template sql_benchmarks/hj_ordered_subset/hj_ordered_subset.benchmark.template
7+
NAME=Q03_partitioned_scattered_1_pct
8+
JOIN_MODE=partitioned
9+
PLAN_MODE=Partitioned
10+
BUILD_TABLE=labels_by_bucket
11+
BUILD_FILTER=l.bucket = 42
Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
# Same as Q01 with a CollectLeft join.
2+
subgroup collect_left
3+
4+
template sql_benchmarks/hj_ordered_subset/hj_ordered_subset.benchmark.template
5+
NAME=Q04_collect_left_ordered_1_day
6+
JOIN_MODE=collect_left
7+
PLAN_MODE=CollectLeft
8+
BUILD_TABLE=labels_by_day
9+
BUILD_FILTER=l.day = 42
Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
# Same as Q02 with a CollectLeft join.
2+
subgroup collect_left
3+
4+
template sql_benchmarks/hj_ordered_subset/hj_ordered_subset.benchmark.template
5+
NAME=Q05_collect_left_ordered_10_days
6+
JOIN_MODE=collect_left
7+
PLAN_MODE=CollectLeft
8+
BUILD_TABLE=labels_by_day
9+
BUILD_FILTER=l.day BETWEEN 40 AND 49
Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
# Control: same as Q03 with a CollectLeft join.
2+
subgroup collect_left
3+
4+
template sql_benchmarks/hj_ordered_subset/hj_ordered_subset.benchmark.template
5+
NAME=Q06_collect_left_scattered_1_pct
6+
JOIN_MODE=collect_left
7+
PLAN_MODE=CollectLeft
8+
BUILD_TABLE=labels_by_bucket
9+
BUILD_FILTER=l.bucket = 42
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
# Shared template for the hj_ordered_subset suite. Each qNN.benchmark sets its
2+
# `subgroup` directive and includes this template with parameters:
3+
# NAME criterion display name
4+
# JOIN_MODE init script stem under init/ (partitioned, collect_left)
5+
# PLAN_MODE expected HashJoinExec mode (Partitioned, CollectLeft)
6+
# BUILD_TABLE build table (labels_by_day, labels_by_bucket)
7+
# BUILD_FILTER filter on the build table, which selects the build side
8+
#
9+
# Every query joins the full `events` table (probe side) to a filtered build
10+
# table on `event_id`. Every build row matches exactly one event.
11+
12+
load sql_benchmarks/hj_ordered_subset/init/load.sql
13+
14+
init sql_benchmarks/hj_ordered_subset/init/${JOIN_MODE}.sql
15+
16+
name ${NAME}
17+
group hj_ordered_subset
18+
19+
# The queries select days 40..49 and bucket 42 of 100.
20+
assert I
21+
SELECT max(day) >= 49 FROM events;
22+
----
23+
true
24+
25+
# Correctness canary: every build row matches exactly one event. A dynamic
26+
# filter that drops a matching row group or row trips this assert.
27+
assert I
28+
SELECT (SELECT count(*) FROM events e JOIN ${BUILD_TABLE} l ON e.event_id = l.event_id WHERE ${BUILD_FILTER})
29+
= (SELECT count(*) FROM ${BUILD_TABLE} l WHERE ${BUILD_FILTER});
30+
----
31+
true
32+
33+
expect_plan HashJoinExec: mode=${PLAN_MODE}
34+
35+
run
36+
SELECT count(*) AS n, sum(e.amount_cents) AS amount_cents, sum(e.v1) AS v1, max(e.note) AS note
37+
FROM events e
38+
JOIN ${BUILD_TABLE} l ON e.event_id = l.event_id
39+
WHERE ${BUILD_FILTER};
40+
41+
cleanup sql_benchmarks/hj_ordered_subset/init/cleanup.sql

0 commit comments

Comments
 (0)