Skip to content

Commit af752e5

Browse files
fix(smj): compare all key types across batch boundaries in semi/anti/mark joins (apache#26830)
## Which issue does this PR close? Closes apache#26003. ## Rationale for this change `EXISTS`, `IN` and `NOT EXISTS` queries planned as sort-merge joins fail with "Unsupported data type in sort merge join comparator" on timezone-aware timestamp, `Dictionary`, `Decimal256` and `Time32`/`Time64` keys, once a key group runs to the end of a batch. Inner sort-merge join and hash join already work on these keys. ## What changes are included in this PR? The bitwise stream compares keys with `JoinKeyComparator` everywhere except in `keys_match`, the check for whether a key group continues into the next batch. That function still called `compare_join_arrays` for non-float keys, and `compare_join_arrays` only knows a fixed list of types. apache#25134 moved float keys over to `JoinKeyComparator`; this moves the rest. `keys_match` now builds a one-row comparator each time a key group reaches the end of a batch. The scan already rebuilds its comparators on every new batch, so I don't expect a measurable cost. One edge case changes: `compare_join_arrays` treated `DataType::Null` keys as always equal, while `JoinKeyComparator` treats them as unequal under `NullEqualsNothing`. As far as I can tell this can't change any output, because such keys never compare equal in the scan either, so the code paths that call `keys_match` don't run for them. `compare_join_arrays` has no callers left, but it's public in `joins::utils`, so I left it alone. Happy to deprecate it here or in a follow-up if you prefer. ## What is the testing strategy for this PR? - `sort_merge_join.slt`: the reproducer from the issue, plus `batch_size = 2` queries for `Dictionary`, `Decimal256` and `Time64` keys. - `join_key_type_batch_boundaries` in `sort_merge_join/tests.rs`: the same matrix as `join_float_key_batch_boundaries` (join type, null equality, sort direction, 1- and 2-row batches) for the five key types above. I moved the body of the float test into a shared helper so the two don't duplicate it. Like apache#25134, it's a physical-plan test, so batches split at exact rows regardless of what the optimizer does. Without the fix, all of the new cases fail with the error from the issue. The change also covers other types `compare_join_arrays` didn't handle (e.g. `Duration`, `Interval`, `Decimal32`/`Decimal64`, nested types), but I haven't added tests for those. ## Are there any user-facing changes? Those queries now return results instead of an error. No API changes.
1 parent d1684ab commit af752e5

3 files changed

Lines changed: 184 additions & 42 deletions

File tree

‎datafusion/physical-plan/src/joins/sort_merge_join/bitwise_stream.rs‎

Lines changed: 10 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -110,7 +110,7 @@ use std::cmp::Ordering;
110110
use std::sync::Arc;
111111

112112
use crate::EmptyRecordBatchStream;
113-
use crate::joins::utils::{JoinFilter, JoinKeyComparator, compare_join_arrays};
113+
use crate::joins::utils::{JoinFilter, JoinKeyComparator};
114114
use crate::metrics::{
115115
BaselineMetrics, Count, ExecutionPlanMetricsSet, Gauge, MetricBuilder, Time,
116116
};
@@ -1215,30 +1215,15 @@ fn keys_match(
12151215
null_equality: NullEquality,
12161216
) -> Result<bool> {
12171217
debug_assert!(left_arrays.iter().all(|a| a.len() == 1));
1218-
if left_arrays
1219-
.iter()
1220-
.any(|array| array.data_type().is_floating())
1221-
{
1222-
// The scalar comparator's partial_cmp panics on NaN. Match the merge
1223-
// scan's floating-point equality, including its signed-zero handling.
1224-
let right_keys = slice_keys(right_arrays, 0);
1225-
return Ok(JoinKeyComparator::new(
1226-
left_arrays,
1227-
&right_keys,
1228-
sort_options,
1229-
null_equality,
1230-
)?
1231-
.is_equal(0, 0));
1232-
}
1233-
let cmp = compare_join_arrays(
1234-
left_arrays,
1235-
0,
1236-
right_arrays,
1237-
0,
1238-
sort_options,
1239-
null_equality,
1240-
)?;
1241-
Ok(cmp == Ordering::Equal)
1218+
// Use the merge scan's comparator so every key type it supports, and its
1219+
// floating-point equality (NaN, signed zero), also applies across batches.
1220+
// Slicing the right side to one row keeps construction independent of the
1221+
// batch size.
1222+
let right_keys = slice_keys(right_arrays, 0);
1223+
Ok(
1224+
JoinKeyComparator::new(left_arrays, &right_keys, sort_options, null_equality)?
1225+
.is_equal(0, 0),
1226+
)
12421227
}
12431228

12441229
/// Evaluate the join filter for one inner row against a slice of outer rows.

‎datafusion/physical-plan/src/joins/sort_merge_join/tests.rs‎

Lines changed: 99 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -5268,32 +5268,114 @@ async fn join_float_key_batch_boundaries(
52685268
#[values(false, true)] descending: bool,
52695269
#[values(1, 2)] input_batch_size: usize,
52705270
) -> Result<()> {
5271-
let input = |unmatched_key| -> Result<Arc<dyn ExecutionPlan>> {
5272-
let mut keys = vec![
5271+
let keys = |unmatched_key| {
5272+
arrow::compute::cast(
5273+
&arrow::array::Float64Array::from(vec![
5274+
None,
5275+
Some(f64::NEG_INFINITY),
5276+
Some(-0.0),
5277+
Some(0.0),
5278+
Some(unmatched_key),
5279+
Some(f64::INFINITY),
5280+
Some(f64::NAN),
5281+
Some(f64::NAN),
5282+
Some(f64::NAN),
5283+
]),
5284+
&key_type,
5285+
)
5286+
};
5287+
assert_key_batch_boundaries(
5288+
keys(1.0)?,
5289+
keys(2.0)?,
5290+
join_type,
5291+
null_equality,
5292+
descending,
5293+
input_batch_size,
5294+
)
5295+
.await
5296+
}
5297+
5298+
// Key types `compare_join_arrays` did not support (#26003) must also compare
5299+
// across batches.
5300+
#[rstest::rstest]
5301+
#[tokio::test]
5302+
async fn join_key_type_batch_boundaries(
5303+
#[values(
5304+
DataType::Timestamp(arrow::datatypes::TimeUnit::Microsecond, Some("UTC".into())),
5305+
DataType::Dictionary(Box::new(DataType::Int32), Box::new(DataType::Utf8)),
5306+
DataType::Decimal256(40, 2),
5307+
DataType::Time32(arrow::datatypes::TimeUnit::Second),
5308+
DataType::Time64(arrow::datatypes::TimeUnit::Nanosecond)
5309+
)]
5310+
key_type: DataType,
5311+
#[values(LeftMark, RightMark, LeftSemi, RightSemi, LeftAnti, RightAnti)]
5312+
join_type: JoinType,
5313+
#[values(NullEquality::NullEqualsNothing, NullEquality::NullEqualsNull)]
5314+
null_equality: NullEquality,
5315+
#[values(false, true)] descending: bool,
5316+
#[values(1, 2)] input_batch_size: usize,
5317+
) -> Result<()> {
5318+
// Single-digit keys so Utf8 dictionary values sort like the integers.
5319+
let keys = |unmatched_key| -> Result<arrow::array::ArrayRef> {
5320+
let keys = arrow::array::Int64Array::from(vec![
52735321
None,
5274-
Some(f64::NEG_INFINITY),
5275-
Some(-0.0),
5276-
Some(0.0),
5322+
Some(1),
5323+
Some(2),
5324+
Some(3),
52775325
Some(unmatched_key),
5278-
Some(f64::INFINITY),
5279-
Some(f64::NAN),
5280-
Some(f64::NAN),
5281-
Some(f64::NAN),
5282-
];
5326+
Some(6),
5327+
Some(7),
5328+
Some(7),
5329+
Some(7),
5330+
]);
5331+
// Int64 cannot be cast to Time32 directly.
5332+
let keys = match key_type {
5333+
DataType::Time32(_) => arrow::compute::cast(&keys, &DataType::Int32)?,
5334+
_ => Arc::new(keys),
5335+
};
5336+
Ok(arrow::compute::cast(&keys, &key_type)?)
5337+
};
5338+
assert_key_batch_boundaries(
5339+
keys(4)?,
5340+
keys(5)?,
5341+
join_type,
5342+
null_equality,
5343+
descending,
5344+
input_batch_size,
5345+
)
5346+
.await
5347+
}
5348+
5349+
/// Joins two inputs of nine ascending keys split into `input_batch_size`-row
5350+
/// batches. Row 0 must be null, row 4 must differ between the sides, and all
5351+
/// remaining rows must match.
5352+
async fn assert_key_batch_boundaries(
5353+
left_keys: arrow::array::ArrayRef,
5354+
right_keys: arrow::array::ArrayRef,
5355+
join_type: JoinType,
5356+
null_equality: NullEquality,
5357+
descending: bool,
5358+
input_batch_size: usize,
5359+
) -> Result<()> {
5360+
let key_type = left_keys.data_type().clone();
5361+
let input = |mut keys: arrow::array::ArrayRef| -> Result<Arc<dyn ExecutionPlan>> {
52835362
let mut ids: Vec<i32> = (0..keys.len() as i32).collect();
52845363
if descending {
5285-
keys.reverse();
52865364
ids.reverse();
5365+
keys = arrow::compute::take(
5366+
&keys,
5367+
&arrow::array::UInt32Array::from_iter_values(
5368+
(0..keys.len() as u32).rev(),
5369+
),
5370+
None,
5371+
)?;
52875372
}
52885373
let batch = RecordBatch::try_from_iter(vec![
52895374
(
52905375
"id",
52915376
Arc::new(Int32Array::from(ids)) as arrow::array::ArrayRef,
52925377
),
5293-
(
5294-
"key",
5295-
arrow::compute::cast(&arrow::array::Float64Array::from(keys), &key_type)?,
5296-
),
5378+
("key", keys),
52975379
])?;
52985380
Ok(build_table_from_batches(
52995381
(0..batch.num_rows())
@@ -5309,8 +5391,8 @@ async fn join_float_key_batch_boundaries(
53095391
Arc::new(Column::new("key", 1)),
53105392
)];
53115393
let (_, output) = join_collect_with_options(
5312-
input(1.0)?,
5313-
input(2.0)?,
5394+
input(left_keys)?,
5395+
input(right_keys)?,
53145396
on,
53155397
join_type,
53165398
vec![SortOptions {

‎datafusion/sqllogictest/test_files/sort_merge_join.slt‎

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1054,6 +1054,81 @@ DROP TABLE smj_nocol_a;
10541054
statement ok
10551055
DROP TABLE smj_nocol_b;
10561056

1057+
# Regression test for #26003: semi/anti/mark joins must compare key groups
1058+
# that cross an input batch boundary for key types `compare_join_arrays`
1059+
# did not handle.
1060+
statement ok
1061+
CREATE TABLE smj_tz_events AS
1062+
SELECT arrow_cast(to_timestamp(value), 'Timestamp(Microsecond, Some("UTC"))') AS ts
1063+
FROM generate_series(1, 100000);
1064+
1065+
statement ok
1066+
CREATE TABLE smj_tz_alerts AS
1067+
SELECT arrow_cast(to_timestamp(value * 7), 'Timestamp(Microsecond, Some("UTC"))') AS ts
1068+
FROM generate_series(1, 20000);
1069+
1070+
query I
1071+
SELECT count(*) FROM smj_tz_events e WHERE EXISTS (SELECT 1 FROM smj_tz_alerts a WHERE a.ts = e.ts);
1072+
----
1073+
14285
1074+
1075+
query I
1076+
SELECT count(*) FROM smj_tz_events e WHERE e.ts IN (SELECT ts FROM smj_tz_alerts);
1077+
----
1078+
14285
1079+
1080+
query I
1081+
SELECT count(*) FROM smj_tz_events e WHERE NOT EXISTS (SELECT 1 FROM smj_tz_alerts a WHERE a.ts = e.ts);
1082+
----
1083+
85715
1084+
1085+
statement ok
1086+
DROP TABLE smj_tz_events;
1087+
1088+
statement ok
1089+
DROP TABLE smj_tz_alerts;
1090+
1091+
statement ok
1092+
set datafusion.execution.batch_size = 2;
1093+
1094+
statement ok
1095+
CREATE TABLE smj_key_l AS SELECT
1096+
arrow_cast(k, 'Dictionary(Int32, Utf8)') AS d,
1097+
arrow_cast(k, 'Decimal256(40, 2)') AS dec,
1098+
arrow_cast(arrow_cast(k, 'Int64'), 'Time64(Nanosecond)') AS t
1099+
FROM (VALUES ('1'), ('2'), ('2'), ('2'), ('3'), ('4')) v(k);
1100+
1101+
statement ok
1102+
CREATE TABLE smj_key_r AS SELECT
1103+
arrow_cast(k, 'Dictionary(Int32, Utf8)') AS d,
1104+
arrow_cast(k, 'Decimal256(40, 2)') AS dec,
1105+
arrow_cast(arrow_cast(k, 'Int64'), 'Time64(Nanosecond)') AS t
1106+
FROM (VALUES ('2'), ('2'), ('2'), ('4'), ('5')) v(k);
1107+
1108+
query I
1109+
SELECT count(*) FROM smj_key_l l WHERE EXISTS (SELECT 1 FROM smj_key_r r WHERE r.d = l.d);
1110+
----
1111+
4
1112+
1113+
query I
1114+
SELECT count(*) FROM smj_key_l l WHERE NOT EXISTS (SELECT 1 FROM smj_key_r r WHERE r.dec = l.dec);
1115+
----
1116+
2
1117+
1118+
query I
1119+
SELECT count(*) FROM smj_key_l l WHERE l.t IN (SELECT t FROM smj_key_r);
1120+
----
1121+
4
1122+
1123+
statement ok
1124+
DROP TABLE smj_key_l;
1125+
1126+
statement ok
1127+
DROP TABLE smj_key_r;
1128+
1129+
statement ok
1130+
RESET datafusion.execution.batch_size;
1131+
10571132
# Config reset
10581133
statement ok
10591134
RESET datafusion.optimizer.prefer_hash_join;

0 commit comments

Comments
 (0)