Skip to content

Commit 2b73c41

Browse files
committed
pick the streamed extreme key with arrow min/max kernels
1 parent 1dda519 commit 2b73c41

2 files changed

Lines changed: 149 additions & 23 deletions

File tree

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

Lines changed: 31 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -67,9 +67,8 @@
6767
//!
6868
//! Rows whose join key is NULL never satisfy a comparison predicate. Buffered NULLs sort to
6969
//! the front, so the scan starts past them and null-keyed buffered rows are left unmarked —
70-
//! correctly excluded from `LeftSemi` and included in `LeftAnti`. Each streamed batch is
71-
//! sorted NULLs-*last* instead, so the extreme key taken from it is non-null unless the whole
72-
//! batch is.
70+
//! correctly excluded from `LeftSemi` and included in `LeftAnti`. The extreme key is picked
71+
//! from each streamed batch with NULLs ignored, so it is non-null unless the whole batch is.
7372
//!
7473
//! # Output
7574
//!
@@ -91,11 +90,12 @@ use std::sync::atomic::Ordering as AtomicOrdering;
9190
use std::task::{Poll, ready};
9291

9392
use arrow::array::{Array, ArrayRef, RecordBatch};
94-
use arrow::compute::{BatchCoalescer, sort_to_indices, take};
93+
use arrow::compute::BatchCoalescer;
9594
use arrow_schema::{SchemaRef, SortOptions};
9695
use datafusion_common::{NullEquality, Result, internal_err};
9796
use datafusion_execution::{RecordBatchStream, SendableRecordBatchStream};
9897
use datafusion_expr::{JoinType, Operator};
98+
use datafusion_functions_aggregate_common::min_max::{max_batch, min_batch};
9999
use datafusion_physical_expr::PhysicalExprRef;
100100
use futures::{Stream, StreamExt};
101101

@@ -109,7 +109,7 @@ use crate::stream::EmptyRecordBatchStream;
109109
pub(super) enum ExistencePWMJStreamState {
110110
/// Load the buffered side into memory.
111111
WaitBufferedSide,
112-
/// Fetch, sort and scan streamed batches, lowering the watermark. Emits nothing.
112+
/// Fetch and scan streamed batches, lowering the watermark. Emits nothing.
113113
ScanStreamBatches,
114114
/// Emit the result. Reached only by the last streamed partition.
115115
EmitMatched,
@@ -210,7 +210,8 @@ impl ExistencePWMJStream {
210210
Poll::Ready(Ok(StatefulStreamResult::Continue))
211211
}
212212

213-
/// Fetches one streamed batch, sorts it, and marks the buffered rows it matches.
213+
/// Fetches one streamed batch, reduces it to its extreme compare key, and marks the
214+
/// buffered rows that key matches.
214215
/// Never produces output: existence results come from the watermark in `emit_matched`.
215216
fn scan_stream_batch(
216217
&mut self,
@@ -237,23 +238,10 @@ impl ExistencePWMJStream {
237238
self.join_metrics.input_batches.add(1);
238239
self.join_metrics.input_rows.add(batch.num_rows());
239240

240-
// Only the batch's extreme key is ever compared against the buffered
241-
// side, so ask arrow for just that one index. `nulls_first: false` makes
242-
// the chosen row non-null whenever the batch holds any non-null key, and
243-
// leaves a null row only for an all-null batch, which marks nothing.
244-
//
245-
// The limit truncates the returned indices, not the work: `sort_impl`
246-
// feeds it into the sort only when `nulls_first` is true, so this still
247-
// fully sorts the batch's non-null keys.
248-
let indices = sort_to_indices(
249-
stream_values.as_ref(),
250-
Some(SortOptions {
251-
descending: self.sort_option.descending,
252-
nulls_first: false,
253-
}),
254-
Some(1),
255-
)?;
256-
let stream_values = take(stream_values.as_ref(), &indices, None)?;
241+
// Only the batch's extreme key is ever compared against the buffered side,
242+
// so reduce the batch to that one key.
243+
let stream_values =
244+
extreme_key(&stream_values, self.sort_option.descending)?;
257245

258246
self.mark_matched_buffered_rows(&stream_values)?;
259247
}
@@ -451,6 +439,26 @@ impl ExistencePWMJStream {
451439
}
452440
}
453441

442+
/// Reduces `values` to a one-row array holding the batch's extreme compare key: the maximum
443+
/// when the batch's sort is `descending`, the minimum otherwise. Nulls are ignored, so that
444+
/// row is null only when every key in the batch is (or the batch is empty), which marks
445+
/// nothing.
446+
///
447+
/// Ordered the same way as [`JoinKeyComparator`]: both use IEEE 754 totalOrder for floats,
448+
/// and the comparator normalizes `-0.0` on either side of it.
449+
///
450+
/// Numeric, temporal, string, binary and boolean keys get a typed arrow kernel -- a linear
451+
/// scan that allocates nothing. Dictionary and nested keys fall to `min_max_batch_generic`, a
452+
/// `ScalarValue`-per-row comparator loop; specializing those is left to a follow-up.
453+
fn extreme_key(values: &ArrayRef, descending: bool) -> Result<ArrayRef> {
454+
let extreme = if descending {
455+
max_batch(values)?
456+
} else {
457+
min_batch(values)?
458+
};
459+
extreme.to_array_of_size(1)
460+
}
461+
454462
impl RecordBatchStream for ExistencePWMJStream {
455463
fn schema(&self) -> SchemaRef {
456464
Arc::clone(&self.schema)

‎datafusion/sqllogictest/test_files/pwmj.slt‎

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1046,5 +1046,123 @@ SELECT l.id FROM ex_fl l WHERE NOT EXISTS (SELECT 1 FROM ex_fr r WHERE l.v <= r.
10461046
----
10471047
2
10481048

1049+
# ------------------------------------------------------------------
1050+
# Classic joins: final pass when the streamed side has fewer partitions than
1051+
# `target_partitions`
1052+
# ------------------------------------------------------------------
1053+
# The final pass -- the only thing that emits unmatched buffered rows for `Left`/`Full` -- runs
1054+
# on the last streamed partition to finish, gated by a counter seeded with the number of
1055+
# partitions that will call `execute`. That is the streamed side's partition count, not
1056+
# `target_partitions`: the streamed side carries no distribution requirement, so a small input
1057+
# stays single-partition while `target_partitions` is 4 (asserted by the plan below). Seeding
1058+
# from `target_partitions` leaves the counter at 3, no partition ever emits, and `x = 10`
1059+
# disappears from both queries.
1060+
statement ok
1061+
CREATE TABLE pwmj_unmatched_l(x INT);
1062+
1063+
statement ok
1064+
INSERT INTO pwmj_unmatched_l VALUES (1), (10);
1065+
1066+
statement ok
1067+
CREATE TABLE pwmj_unmatched_r(y INT);
1068+
1069+
statement ok
1070+
INSERT INTO pwmj_unmatched_r VALUES (5);
1071+
1072+
query II
1073+
SELECT l.x, r.y FROM pwmj_unmatched_l l LEFT JOIN pwmj_unmatched_r r ON l.x < r.y ORDER BY 1;
1074+
----
1075+
1 5
1076+
10 NULL
1077+
1078+
query II
1079+
SELECT l.x, r.y FROM pwmj_unmatched_l l FULL JOIN pwmj_unmatched_r r ON l.x < r.y ORDER BY 1;
1080+
----
1081+
1 5
1082+
10 NULL
1083+
1084+
query TT
1085+
EXPLAIN SELECT l.x, r.y FROM pwmj_unmatched_l l LEFT JOIN pwmj_unmatched_r r ON l.x < r.y ORDER BY 1;
1086+
----
1087+
logical_plan
1088+
01)Sort: l.x ASC NULLS LAST
1089+
02)--Left Join: Filter: l.x < r.y
1090+
03)----SubqueryAlias: l
1091+
04)------TableScan: pwmj_unmatched_l projection=[x]
1092+
05)----SubqueryAlias: r
1093+
06)------TableScan: pwmj_unmatched_r projection=[y]
1094+
physical_plan
1095+
01)SortExec: expr=[x@0 ASC NULLS LAST], preserve_partitioning=[false]
1096+
02)--PiecewiseMergeJoin: operator=Lt, join_type=Left, on=(x < y)
1097+
03)----SortExec: expr=[x@0 DESC], preserve_partitioning=[false]
1098+
04)------DataSourceExec: partitions=1, partition_sizes=[1]
1099+
05)----DataSourceExec: partitions=1, partition_sizes=[1]
1100+
1101+
# ------------------------------------------------------------------
1102+
# Existence joins: dictionary-encoded keys
1103+
# ------------------------------------------------------------------
1104+
# Each streamed batch is reduced to its extreme key. Dictionaries have no typed arrow min/max
1105+
# kernel, so they take the generic `ScalarValue`-per-row path -- this is the only coverage of
1106+
# that path.
1107+
statement ok
1108+
CREATE TABLE ex_dict_l AS
1109+
SELECT column1 AS id, arrow_cast(column2, 'Dictionary(Int32, Utf8)') AS v
1110+
FROM (VALUES (1, 'a'), (2, 'c'), (3, 'e'), (4, NULL));
1111+
1112+
statement ok
1113+
CREATE TABLE ex_dict_r AS
1114+
SELECT arrow_cast(column1, 'Dictionary(Int32, Utf8)') AS v FROM (VALUES ('c'));
1115+
1116+
query T
1117+
SELECT arrow_typeof(v) FROM ex_dict_l LIMIT 1;
1118+
----
1119+
Dictionary(Int32, Utf8)
1120+
1121+
# `>` : only 'e' exceeds 'c'. The NULL key is never marked, so it stays in NOT EXISTS.
1122+
query I
1123+
SELECT l.id FROM ex_dict_l l WHERE EXISTS (SELECT 1 FROM ex_dict_r r WHERE l.v > r.v) ORDER BY 1;
1124+
----
1125+
3
1126+
1127+
query I
1128+
SELECT l.id FROM ex_dict_l l WHERE NOT EXISTS (SELECT 1 FROM ex_dict_r r WHERE l.v > r.v) ORDER BY 1;
1129+
----
1130+
1
1131+
2
1132+
4
1133+
1134+
# `<=` : 'a' and 'c'.
1135+
query I
1136+
SELECT l.id FROM ex_dict_l l WHERE EXISTS (SELECT 1 FROM ex_dict_r r WHERE l.v <= r.v) ORDER BY 1;
1137+
----
1138+
1
1139+
2
1140+
1141+
query I
1142+
SELECT l.id FROM ex_dict_l l WHERE NOT EXISTS (SELECT 1 FROM ex_dict_r r WHERE l.v <= r.v) ORDER BY 1;
1143+
----
1144+
3
1145+
4
1146+
1147+
query TT
1148+
EXPLAIN SELECT l.id FROM ex_dict_l l WHERE EXISTS (SELECT 1 FROM ex_dict_r r WHERE l.v > r.v) ORDER BY 1;
1149+
----
1150+
logical_plan
1151+
01)Sort: l.id ASC NULLS LAST
1152+
02)--Projection: l.id
1153+
03)----LeftSemi Join: Filter: l.v > __correlated_sq_1.v
1154+
04)------SubqueryAlias: l
1155+
05)--------TableScan: ex_dict_l projection=[id, v]
1156+
06)------SubqueryAlias: __correlated_sq_1
1157+
07)--------SubqueryAlias: r
1158+
08)----------TableScan: ex_dict_r projection=[v]
1159+
physical_plan
1160+
01)SortExec: expr=[id@0 ASC NULLS LAST], preserve_partitioning=[false]
1161+
02)--ProjectionExec: expr=[id@0 as id]
1162+
03)----PiecewiseMergeJoin: operator=Gt, join_type=LeftSemi, on=(v > v)
1163+
04)------SortExec: expr=[v@1 ASC], preserve_partitioning=[false]
1164+
05)--------DataSourceExec: partitions=1, partition_sizes=[1]
1165+
06)------DataSourceExec: partitions=1, partition_sizes=[1]
1166+
10491167
statement ok
10501168
set datafusion.optimizer.enable_piecewise_merge_join = false;

0 commit comments

Comments
 (0)