Skip to content

Commit 242b96c

Browse files
Xuanwojayzhan211
andauthored
perf: mirror compound ASOF key predicates to right (#25728)
## Which issue does this PR close? - Part of #318. - Follow-up to #25574. ## Rationale for this change #25574 mirrors a selective `left_key = literal` filter to the right side of an ASOF join. The same equality guarantee applies to any deterministic predicate that references only direct left equality-key columns, including `IN`, ranges, and `OR` expressions. Mirroring those predicates avoids sorting and broadcasting right-side groups that cannot match a surviving left row. ## Performance Q10 has 50M rows on each side across 500K equality groups. `WHERE l.key IN (42, 43)` retains two groups and produces 200 rows with both revisions. On an Apple M4 Max, using independent release builds and two 7-iteration runs per revision, the median elapsed time across all 14 iterations was: | Revision | Median elapsed | | --- | ---: | | Current main after #25574 (`acf5c89e6`) | 984.9 ms | | This change (`5763d505a`) | 82.3 ms | This selective compound-key workload is about **12.0x faster** (91.6% lower elapsed time). The benchmark file and command were the same for both binaries: ```shell target/release/benchmark_runner asof_join --query 10 --iterations 7 ``` ## What changes are included in this PR? - Build an ASOF-specific column mapping for direct equality keys. - Mirror a pushed deterministic predicate only when every referenced column has a right-key mapping. - Support compound `IN`, range, and `OR` predicates while leaving mixed key/non-key predicates entirely off the right input. - Add plan coverage and ASOF benchmark Q10. Coerced and expression-based equality keys remain excluded because they cannot be replaced column-for-column. ## What is the testing strategy for this PR? The new `asof_join.slt` cases verify compound predicate mirroring and the all-or-nothing behavior for a mixed key/non-key `OR` predicate. Q10 covers the user-visible selective workload. Also run: - `cargo fmt --all -- --check` - `cargo clippy --all-targets --all-features -- -D warnings` - The extended workspace test suite, including all 524 sqllogictest files ## Are there any user-facing changes? No API or result changes. More eligible ASOF joins can sort and retain fewer right-side rows. --------- Co-authored-by: Jay Zhan <[email protected]>
1 parent 3fa5bc7 commit 242b96c

4 files changed

Lines changed: 105 additions & 34 deletions

File tree

‎benchmarks/sql_benchmarks/asof_join/asof_join.suite‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,3 +29,7 @@ description = "Run the selective left-filter ASOF join query."
2929
[[examples]]
3030
command = "cargo run --release --bin benchmark_runner -- asof_join --query 9"
3131
description = "Run the equality-key filter ASOF join query."
32+
33+
[[examples]]
34+
command = "cargo run --release --bin benchmark_runner -- asof_join --query 10"
35+
description = "Run the compound equality-key filter ASOF join query."
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
name Q10
2+
group asof_join
3+
4+
expect_plan AsOfJoinExec
5+
6+
run
7+
-- Both sides: 50M rows in 500K equality groups. The IN predicate retains
8+
-- two groups; mirroring it prunes the right input before sorting and broadcast.
9+
WITH left_input AS (
10+
SELECT value % 500000 AS key,
11+
value / 500000 + 1 AS ts,
12+
value AS payload
13+
FROM range(50000000)
14+
),
15+
right_input AS (
16+
SELECT value % 500000 AS key,
17+
value / 500000 AS ts,
18+
value AS payload
19+
FROM range(50000000)
20+
)
21+
SELECT l.key, l.ts, l.payload, r.payload AS right_payload
22+
FROM left_input l
23+
ASOF JOIN right_input r MATCH_CONDITION (l.ts >= r.ts)
24+
ON l.key = r.key
25+
WHERE l.key IN (42, 43);

‎datafusion/optimizer/src/push_down_filter.rs‎

Lines changed: 20 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -38,7 +38,7 @@ use datafusion_expr::utils::{
3838
conjunction, expr_to_columns, split_conjunction, split_conjunction_owned,
3939
};
4040
use datafusion_expr::{
41-
BinaryExpr, Distinct, Expr, ExprSchemable, Filter, Operator, Projection,
41+
BinaryExpr, Distinct, Expr, Filter, Operator, Projection,
4242
TableProviderFilterPushDown, and, or,
4343
};
4444

@@ -1168,41 +1168,27 @@ impl OptimizerRule for PushDownFilter {
11681168
})
11691169
});
11701170

1171-
// A literal comparison on an equal, same-typed key has the
1172-
// same value for every matching pair. Mirroring it to the
1173-
// right can prune groups without changing the ASOF candidate.
1171+
// Every matching pair has equal key values, so a deterministic
1172+
// predicate that refers only to left keys also holds for the
1173+
// corresponding right keys. Expression-based join keys are not
1174+
// mirrored because they cannot be replaced column-for-column.
1175+
let key_replacements = join
1176+
.on
1177+
.iter()
1178+
.filter_map(|(left, right)| {
1179+
Some((left.try_as_col()?, right.try_as_col()?))
1180+
})
1181+
.collect::<HashMap<_, _>>();
11741182
let mut right_predicates = Vec::new();
11751183
for predicate in &push_predicates {
1176-
let Expr::BinaryExpr(BinaryExpr {
1177-
left,
1178-
op: Operator::Eq,
1179-
right,
1180-
}) = predicate
1181-
else {
1182-
continue;
1183-
};
1184-
let ((Expr::Column(left_column), Expr::Literal(_, _))
1185-
| (Expr::Literal(_, _), Expr::Column(left_column))) =
1186-
(left.as_ref(), right.as_ref())
1187-
else {
1188-
continue;
1189-
};
1190-
for (left_key, right_key) in &join.on {
1191-
let (Some(left_key_column), Some(right_key_column)) =
1192-
(left_key.try_as_col(), right_key.try_as_col())
1193-
else {
1194-
continue;
1195-
};
1196-
if left_column == left_key_column
1197-
&& left_key.get_type(join.left.schema())?
1198-
== right_key.get_type(join.right.schema())?
1199-
{
1200-
let replacements =
1201-
HashMap::from([(left_key_column, right_key_column)]);
1202-
right_predicates
1203-
.push(replace_col(predicate.clone(), &replacements)?);
1204-
break;
1205-
}
1184+
let columns = predicate.column_refs();
1185+
if !columns.is_empty()
1186+
&& columns
1187+
.iter()
1188+
.all(|column| key_replacements.contains_key(column))
1189+
{
1190+
right_predicates
1191+
.push(replace_col(predicate.clone(), &key_replacements)?);
12061192
}
12071193
}
12081194
if let Some(predicate) = conjunction(right_predicates) {

‎datafusion/sqllogictest/test_files/asof_join.slt‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -413,6 +413,62 @@ physical_plan
413413
07)----FilterExec: grp@0 = A
414414
08)------DataSourceExec: partitions=1, partition_sizes=[1]
415415

416+
# Any deterministic predicate that only references equality keys can be
417+
# mirrored, including compound IN, range, and OR expressions.
418+
query TT
419+
EXPLAIN SELECT l.id, r.val
420+
FROM asof_left l
421+
ASOF JOIN asof_right r
422+
MATCH_CONDITION (l.ts >= r.ts)
423+
ON l.grp = r.grp
424+
WHERE l.grp IN ('A', 'B') OR l.grp > 'C';
425+
----
426+
logical_plan
427+
01)Projection: l.id, r.val
428+
02)--AsOf Join: match=[l.ts >= r.ts], constraint=On, on=[l.grp = r.grp]
429+
03)----SubqueryAlias: l
430+
04)------Filter: asof_left.grp = Utf8View("A") OR asof_left.grp = Utf8View("B") OR asof_left.grp > Utf8View("C")
431+
05)--------TableScan: asof_left projection=[id, grp, ts]
432+
06)----SubqueryAlias: r
433+
07)------Filter: asof_right.grp = Utf8View("A") OR asof_right.grp = Utf8View("B") OR asof_right.grp > Utf8View("C")
434+
08)--------TableScan: asof_right projection=[grp, ts, val]
435+
physical_plan
436+
01)AsOfJoinExec: on=[(grp = grp)], match=[ts >= ts], projection=[id@0, val@5]
437+
02)--SortExec: expr=[grp@1 ASC, ts@2 ASC], preserve_partitioning=[true]
438+
03)----RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
439+
04)------FilterExec: grp@1 = A OR grp@1 = B OR grp@1 > C
440+
05)--------DataSourceExec: partitions=1, partition_sizes=[1]
441+
06)--SortExec: expr=[grp@0 ASC, ts@1 ASC], preserve_partitioning=[false]
442+
07)----FilterExec: grp@0 = A OR grp@0 = B OR grp@0 > C
443+
08)------DataSourceExec: partitions=1, partition_sizes=[1]
444+
445+
# If any referenced column is not an equality key, the entire predicate must
446+
# stay off the right input.
447+
query TT
448+
EXPLAIN SELECT l.id, r.val
449+
FROM asof_left l
450+
ASOF JOIN asof_right r
451+
MATCH_CONDITION (l.ts >= r.ts)
452+
ON l.grp = r.grp
453+
WHERE l.grp = 'A' OR l.id = 4;
454+
----
455+
logical_plan
456+
01)Projection: l.id, r.val
457+
02)--AsOf Join: match=[l.ts >= r.ts], constraint=On, on=[l.grp = r.grp]
458+
03)----SubqueryAlias: l
459+
04)------Filter: asof_left.grp = Utf8View("A") OR asof_left.id = Int32(4)
460+
05)--------TableScan: asof_left projection=[id, grp, ts]
461+
06)----SubqueryAlias: r
462+
07)------TableScan: asof_right projection=[grp, ts, val]
463+
physical_plan
464+
01)AsOfJoinExec: on=[(grp = grp)], match=[ts >= ts], projection=[id@0, val@5]
465+
02)--SortExec: expr=[grp@1 ASC, ts@2 ASC], preserve_partitioning=[true]
466+
03)----RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
467+
04)------FilterExec: grp@1 = A OR id@0 = 4
468+
05)--------DataSourceExec: partitions=1, partition_sizes=[1]
469+
06)--SortExec: expr=[grp@0 ASC, ts@1 ASC], preserve_partitioning=[false]
470+
07)----DataSourceExec: partitions=1, partition_sizes=[1]
471+
416472
# An ASOF join emits each left row exactly once, so the primary key from
417473
# asof_left remains unique. Because the outer LEFT JOIN does not use columns
418474
# from the ASOF side, it can be removed entirely.

0 commit comments

Comments
 (0)