Skip to content

Commit 2627267

Browse files
committed
settle run-end encoded NULL keys by their logical nulls
1 parent 534cb42 commit 2627267

2 files changed

Lines changed: 232 additions & 19 deletions

File tree

‎datafusion/physical-plan/src/joins/piecewise_merge_join/classic_join.rs‎

Lines changed: 99 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -488,8 +488,9 @@ fn resolve_classic_join(
488488
let stream_idx = batch_process_state.start_stream_idx;
489489

490490
// Streamed NULL keys are settled before the sort (see `split_off_never_matching`). One
491-
// that got here would sort before every buffered key and match all of them.
492-
if stream_values[0].null_count() > 0 {
491+
// that got here would sort before every buffered key and match all of them. Logical, as a
492+
// run-end encoded NULL has no physical null buffer.
493+
if stream_values[0].logical_null_count() > 0 {
493494
return internal_err!(
494495
"PiecewiseMergeJoin: streamed NULL keys must be settled before the scan"
495496
);
@@ -589,19 +590,22 @@ fn build_matched_indices_and_mark_buffered(
589590
}
590591

591592
// The last key of the sorted buffered side, or `None` when it is empty or every key is NULL:
592-
// NULLs sort first, so the last key is NULL only when every buffered key is.
593+
// NULLs sort first, so the last key is NULL only when every buffered key is. Logical, as a
594+
// run-end encoded or `Null`-typed NULL has no physical null buffer.
593595
fn buffered_extreme(values: &ArrayRef) -> Result<Option<ColumnarValue>> {
594-
Ok(match values.len().checked_sub(1) {
595-
// `apply_cmp` normalizes `-0.0` only in flat float scalars, not inside a
596-
// `ScalarValue::Dictionary`, so normalize the key before taking it.
597-
Some(last) if values.is_valid(last) => {
598-
let extreme = normalize_float_zero(&values.slice(last, 1));
599-
Some(ColumnarValue::Scalar(ScalarValue::try_from_array(
600-
&extreme, 0,
601-
)?))
602-
}
603-
_ => None,
604-
})
596+
let Some(last) = values.len().checked_sub(1) else {
597+
return Ok(None);
598+
};
599+
let last = values.slice(last, 1);
600+
if last.logical_null_count() > 0 {
601+
return Ok(None);
602+
}
603+
// `apply_cmp` normalizes `-0.0` only in flat float scalars, not inside a
604+
// `ScalarValue::Dictionary`, so normalize the key before taking it.
605+
let extreme = normalize_float_zero(&last);
606+
Ok(Some(ColumnarValue::Scalar(ScalarValue::try_from_array(
607+
&extreme, 0,
608+
)?)))
605609
}
606610

607611
// Which rows of `stream_values` can match at least one buffered row.
@@ -644,8 +648,10 @@ fn matchable_rows(
644648
NullEquality::NullEqualsNothing,
645649
)?;
646650
let last = buffered_values.len() - 1;
651+
// Logical NULLs: a run-end encoded NULL has no physical null buffer.
652+
let nulls = stream_values.logical_nulls();
647653
let matchable = BooleanBuffer::collect_bool(num_rows, |row| {
648-
stream_values.is_valid(row)
654+
nulls.as_ref().is_none_or(|nulls| nulls.is_valid(row))
649655
&& is_match(cmp.compare(row, last), match_on_equal)
650656
});
651657
return Ok(BooleanArray::new(matchable, None));
@@ -1246,7 +1252,9 @@ mod tests {
12461252
}
12471253

12481254
/// An empty streamed batch of run-end encoded keys, sliced past the first run, must not
1249-
/// reach arrow's run-end comparison kernel, which overflows on it.
1255+
/// reach arrow's run-end comparison kernel, which overflows on it. The streamed NULL key
1256+
/// (`a2 = 0`) is a logical NULL with no physical null buffer, and must come out unmatched
1257+
/// rather than join every buffered row.
12501258
#[tokio::test]
12511259
async fn join_right_run_end_encoded_keys_empty_sliced_batch() -> Result<()> {
12521260
use arrow::array::{Int32Array, RunArray};
@@ -1302,7 +1310,60 @@ mod tests {
13021310
Arc::new(Column::new_with_schema("b2", &right.schema())?) as _,
13031311
);
13041312

1305-
join_collect(left, right, on, Operator::Lt, JoinType::Right).await?;
1313+
let (_, batches, _) =
1314+
join_collect(left, right, on, Operator::Lt, JoinType::Right).await?;
1315+
assert_snapshot!(batches_to_string(&batches), @r"
1316+
+----+----+----+----+
1317+
| a1 | b1 | a2 | b2 |
1318+
+----+----+----+----+
1319+
| | | 0 | |
1320+
| 3 | 1 | 1 | 2 |
1321+
| 4 | 1 | 1 | 2 |
1322+
| 3 | 1 | 2 | 2 |
1323+
| 4 | 1 | 2 | 2 |
1324+
| | | 3 | 0 |
1325+
| 1 | 5 | 4 | 6 |
1326+
| 2 | 5 | 4 | 6 |
1327+
| 3 | 1 | 4 | 6 |
1328+
| 4 | 1 | 4 | 6 |
1329+
+----+----+----+----+
1330+
");
1331+
Ok(())
1332+
}
1333+
1334+
/// `buffered_extreme` is `None` when the last buffered key is logically NULL, including
1335+
/// run-end encoded, `Null`-typed and dictionary keys, which have no physical NULL there.
1336+
#[test]
1337+
fn buffered_extreme_is_none_for_logically_null_keys() -> Result<()> {
1338+
use arrow::array::{DictionaryArray, Int32Array, NullArray, RunArray};
1339+
use arrow::datatypes::Int32Type;
1340+
1341+
let null_keys: Vec<(&str, ArrayRef)> = vec![
1342+
("null", Arc::new(NullArray::new(3))),
1343+
(
1344+
"run_end_encoded",
1345+
Arc::new(RunArray::<Int32Type>::try_new(
1346+
&Int32Array::from(vec![3]),
1347+
&Int32Array::from(vec![None::<i32>]),
1348+
)?),
1349+
),
1350+
(
1351+
"dictionary_null_value",
1352+
Arc::new(DictionaryArray::<Int32Type>::try_new(
1353+
Int32Array::from(vec![0, 0]),
1354+
Arc::new(Int32Array::from(vec![None::<i32>])),
1355+
)?),
1356+
),
1357+
];
1358+
for (name, values) in null_keys {
1359+
assert!(buffered_extreme(&values)?.is_none(), "{name}");
1360+
}
1361+
1362+
let values: ArrayRef = Arc::new(Int32Array::from(vec![None, Some(3)]));
1363+
assert!(matches!(
1364+
buffered_extreme(&values)?,
1365+
Some(ColumnarValue::Scalar(ScalarValue::Int32(Some(3))))
1366+
));
13061367
Ok(())
13071368
}
13081369

@@ -1443,6 +1504,23 @@ mod tests {
14431504
Arc::new(Float64Array::from(vec![0.0, -0.0, -0.5])),
14441505
)),
14451506
),
1507+
(
1508+
// NULL *values* behind valid dictionary keys, on both sides.
1509+
"dictionary_null_values",
1510+
Arc::new(DictionaryArray::<Int32Type>::new(
1511+
Int32Array::from(vec![0, 1, 2]),
1512+
Arc::new(StringArray::from(vec![Some("b"), None, Some("d")])),
1513+
)),
1514+
Arc::new(DictionaryArray::<Int32Type>::new(
1515+
Int32Array::from(vec![0, 1, 2, 3, 1]),
1516+
Arc::new(StringArray::from(vec![
1517+
Some("a"),
1518+
None,
1519+
Some("c"),
1520+
Some("e"),
1521+
])),
1522+
)),
1523+
),
14461524
(
14471525
"decimal128",
14481526
Arc::new(
@@ -1569,9 +1647,11 @@ mod tests {
15691647
&[sort_options],
15701648
NullEquality::NullEqualsNothing,
15711649
)?;
1650+
// Logical NULLs, so a dictionary key whose *value* is NULL counts as one.
1651+
let nulls = streamed.logical_nulls();
15721652
for row in 0..streamed.len() {
1573-
let expected = streamed.is_valid(row)
1574-
&& (sorted.null_count()..sorted.len()).any(|idx| {
1653+
let expected = nulls.as_ref().is_none_or(|n| n.is_valid(row))
1654+
&& (sorted.logical_null_count()..sorted.len()).any(|idx| {
15751655
is_match(cmp.compare(row, idx), match_on_equal)
15761656
});
15771657
assert_eq!(

‎datafusion/sqllogictest/test_files/piecewise_merge_join_matrix.slt‎

Lines changed: 133 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -292,6 +292,139 @@ NULL NULL 3 0
292292
NULL NULL 6 NULL
293293
NULL NULL 7 1
294294

295+
# The streamed side arrives in several batches, and the first one has no
296+
# matchable row: it is settled whole, and the scan sees an empty batch.
297+
statement ok
298+
CREATE TABLE cj_mb_r(rid INT, rv INT);
299+
300+
statement ok
301+
INSERT INTO cj_mb_r VALUES (1, 0), (2, 1);
302+
303+
statement ok
304+
INSERT INTO cj_mb_r VALUES (3, 4), (4, NULL), (5, 6);
305+
306+
statement ok
307+
INSERT INTO cj_mb_r VALUES (6, NULL);
308+
309+
query IIII rowsort
310+
SELECT l.lid, l.lv, r.rid, r.rv FROM cj_l l JOIN cj_mb_r r ON l.lv < r.rv;
311+
----
312+
1 1 3 4
313+
1 1 5 6
314+
2 3 3 4
315+
2 3 5 6
316+
3 5 5 6
317+
318+
query IIII rowsort
319+
SELECT l.lid, l.lv, r.rid, r.rv FROM cj_l l FULL JOIN cj_mb_r r ON l.lv < r.rv;
320+
----
321+
1 1 3 4
322+
1 1 5 6
323+
2 3 3 4
324+
2 3 5 6
325+
3 5 5 6
326+
4 NULL NULL NULL
327+
NULL NULL 1 0
328+
NULL NULL 2 1
329+
NULL NULL 4 NULL
330+
NULL NULL 6 NULL
331+
332+
# A buffered side whose keys are all NULL has no key to match against, so every
333+
# streamed row is settled as unmatched.
334+
statement ok
335+
CREATE TABLE cj_alln(lid INT, lv INT);
336+
337+
statement ok
338+
INSERT INTO cj_alln VALUES (1, NULL), (2, NULL);
339+
340+
query IIII rowsort
341+
SELECT l.lid, l.lv, r.rid, r.rv FROM cj_alln l JOIN cj_r r ON l.lv < r.rv;
342+
----
343+
344+
query IIII rowsort
345+
SELECT l.lid, l.lv, r.rid, r.rv FROM cj_alln l RIGHT JOIN cj_r r ON l.lv < r.rv;
346+
----
347+
NULL NULL 1 3
348+
NULL NULL 2 5
349+
NULL NULL 3 NULL
350+
351+
query IIII rowsort
352+
SELECT l.lid, l.lv, r.rid, r.rv FROM cj_alln l FULL JOIN cj_r r ON l.lv >= r.rv;
353+
----
354+
1 NULL NULL NULL
355+
2 NULL NULL NULL
356+
NULL NULL 1 3
357+
NULL NULL 2 5
358+
NULL NULL 3 NULL
359+
360+
# Keys of type Null (columns built only from NULL literals) match nothing.
361+
statement ok
362+
CREATE TABLE cj_nl AS SELECT * FROM (VALUES (1, NULL), (2, NULL)) AS t(lid, lv);
363+
364+
statement ok
365+
CREATE TABLE cj_nr AS SELECT * FROM (VALUES (10, NULL), (20, NULL)) AS t(rid, rv);
366+
367+
query I?I? rowsort
368+
SELECT l.lid, l.lv, r.rid, r.rv FROM cj_nl l JOIN cj_nr r ON l.lv < r.rv;
369+
----
370+
371+
query I?I? rowsort
372+
SELECT l.lid, l.lv, r.rid, r.rv FROM cj_nl l LEFT JOIN cj_nr r ON l.lv <= r.rv;
373+
----
374+
1 NULL NULL NULL
375+
2 NULL NULL NULL
376+
377+
query I?I? rowsort
378+
SELECT l.lid, l.lv, r.rid, r.rv FROM cj_nl l RIGHT JOIN cj_nr r ON l.lv > r.rv;
379+
----
380+
NULL NULL 10 NULL
381+
NULL NULL 20 NULL
382+
383+
query I?I? rowsort
384+
SELECT l.lid, l.lv, r.rid, r.rv FROM cj_nl l FULL JOIN cj_nr r ON l.lv >= r.rv;
385+
----
386+
1 NULL NULL NULL
387+
2 NULL NULL NULL
388+
NULL NULL 10 NULL
389+
NULL NULL 20 NULL
390+
391+
# List keys, which are checked against the buffered extreme with the scan's
392+
# comparator rather than a vectorized comparison. A NULL list on the streamed
393+
# side must still come out unmatched. No list holds a NULL element (#25957).
394+
statement ok
395+
CREATE TABLE cj_ll AS SELECT * FROM (VALUES (1, make_array(1, 2)), (2, make_array(3)), (3, NULL)) AS t(lid, lv);
396+
397+
statement ok
398+
CREATE TABLE cj_lr AS SELECT * FROM (VALUES (1, make_array(2)), (2, make_array(1, 2)), (3, make_array(0)), (4, NULL)) AS t(rid, rv);
399+
400+
query I?I? rowsort
401+
SELECT l.lid, l.lv, r.rid, r.rv FROM cj_ll l RIGHT JOIN cj_lr r ON l.lv < r.rv;
402+
----
403+
1 [1, 2] 1 [2]
404+
NULL NULL 2 [1, 2]
405+
NULL NULL 3 [0]
406+
NULL NULL 4 NULL
407+
408+
query I?I? rowsort
409+
SELECT l.lid, l.lv, r.rid, r.rv FROM cj_ll l FULL JOIN cj_lr r ON l.lv <= r.rv;
410+
----
411+
1 [1, 2] 1 [2]
412+
1 [1, 2] 2 [1, 2]
413+
2 [3] NULL NULL
414+
3 NULL NULL NULL
415+
NULL NULL 3 [0]
416+
NULL NULL 4 NULL
417+
418+
query I?I? rowsort
419+
SELECT l.lid, l.lv, r.rid, r.rv FROM cj_ll l RIGHT JOIN cj_lr r ON l.lv >= r.rv;
420+
----
421+
1 [1, 2] 2 [1, 2]
422+
1 [1, 2] 3 [0]
423+
2 [3] 1 [2]
424+
2 [3] 2 [1, 2]
425+
2 [3] 3 [0]
426+
NULL NULL 4 NULL
427+
295428
# ==================================================================
296429
# Part 2: Existence joins (LeftSemi / LeftAnti; Right/Mark fall back to NLJ)
297430
# ==================================================================

0 commit comments

Comments
 (0)