Skip to content

Commit 1fedd67

Browse files
committed
Handle NLJ fallback
1 parent b64e845 commit 1fedd67

5 files changed

Lines changed: 381 additions & 34 deletions

File tree

‎datafusion/core/src/physical_planner.rs‎

Lines changed: 22 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -1646,14 +1646,20 @@ impl DefaultPhysicalPlanner {
16461646
}
16471647
}
16481648

1649+
// `Neither` covers an operand that references no column from
1650+
// either side (e.g. a literal), and `Both` an operand that
1651+
// references columns from both. PWMJ needs one operand pinned
1652+
// to each side, so both fall back to NestedLoopJoin below rather
1653+
// than erroring or (for `Neither`) panicking.
16491654
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
16501655
enum Side {
16511656
Left,
16521657
Right,
16531658
Both,
1659+
Neither,
16541660
}
16551661

1656-
let side_of = |e: &Expr| -> Result<Side> {
1662+
let side_of = |e: &Expr| -> Side {
16571663
let cols = e.column_refs();
16581664
let any_left = cols
16591665
.iter()
@@ -1662,20 +1668,29 @@ impl DefaultPhysicalPlanner {
16621668
.iter()
16631669
.any(|c| right_df_schema.index_of_column(c).is_ok());
16641670

1665-
Ok(match (any_left, any_right) {
1671+
match (any_left, any_right) {
16661672
(true, false) => Side::Left,
16671673
(false, true) => Side::Right,
16681674
(true, true) => Side::Both,
1669-
_ => unreachable!(),
1670-
})
1675+
(false, false) => Side::Neither,
1676+
}
16711677
};
16721678

16731679
let mut lhs_logical = &be.left;
16741680
let mut rhs_logical = &be.right;
16751681

1676-
let left_side = side_of(lhs_logical)?;
1677-
let right_side = side_of(rhs_logical)?;
1678-
if left_side == Side::Both || right_side == Side::Both {
1682+
let left_side = side_of(lhs_logical);
1683+
let right_side = side_of(rhs_logical);
1684+
1685+
if left_side == Side::Right && right_side == Side::Left {
1686+
std::mem::swap(&mut lhs_logical, &mut rhs_logical);
1687+
op = reverse_ineq(op);
1688+
} else if !(left_side == Side::Left && right_side == Side::Right)
1689+
{
1690+
// Anything other than a clean left/right split -- both
1691+
// operands on one side, one referencing neither side, or
1692+
// either referencing both -- isn't a range predicate PWMJ
1693+
// can plan, so let NestedLoopJoin evaluate it instead.
16791694
return Ok(Arc::new(NestedLoopJoinExec::try_new(
16801695
physical_left,
16811696
physical_right,
@@ -1685,17 +1700,6 @@ impl DefaultPhysicalPlanner {
16851700
)?));
16861701
}
16871702

1688-
if left_side == Side::Right && right_side == Side::Left {
1689-
std::mem::swap(&mut lhs_logical, &mut rhs_logical);
1690-
op = reverse_ineq(op);
1691-
} else if !(left_side == Side::Left && right_side == Side::Right)
1692-
{
1693-
return plan_err!(
1694-
"Unsupported operator for PWMJ: {:?}. Expected one of <, <=, >, >=",
1695-
op
1696-
);
1697-
}
1698-
16991703
let on_left = create_physical_expr(
17001704
lhs_logical,
17011705
left_df_schema,

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -743,6 +743,7 @@ impl ExecutionPlan for PiecewiseMergeJoinExec {
743743
streamed,
744744
extreme_fut,
745745
metrics,
746+
batch_size,
746747
)))
747748
}
748749
JoinType::LeftSemi | JoinType::LeftAnti => {

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

Lines changed: 143 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -100,6 +100,7 @@ use std::sync::Arc;
100100
use std::task::{Poll, ready};
101101

102102
use arrow::array::{AsArray, RecordBatch};
103+
use arrow::compute::BatchCoalescer;
103104
use arrow::compute::filter_record_batch;
104105
use arrow::compute::kernels::boolean::not;
105106
use arrow_schema::SchemaRef;
@@ -123,6 +124,8 @@ pub(super) enum RightExistencePWMJStreamState {
123124
/// Fetch streamed batches and emit the rows that do (`RightSemi`) or do not
124125
/// (`RightAnti`) have a buffered match.
125126
ScanStreamBatches,
127+
/// Streamed side exhausted; drain whatever `output_batches` still holds.
128+
Draining,
126129
Completed,
127130
}
128131

@@ -146,9 +149,13 @@ pub(super) struct RightExistencePWMJStream {
146149
/// ever match. Only populated once `buffered_extreme_fut` has resolved.
147150
buffered_extreme: Option<ScalarValue>,
148151
join_metrics: BuildProbeJoinMetrics,
152+
/// Chunks the per-streamed-batch output to `batch_size`, so a low-selectivity join
153+
/// does not hand downstream operators one small batch per streamed batch.
154+
output_batches: Box<BatchCoalescer>,
149155
}
150156

151157
impl RightExistencePWMJStream {
158+
#[expect(clippy::too_many_arguments)]
152159
pub(super) fn try_new(
153160
schema: SchemaRef,
154161
on_streamed: PhysicalExprRef,
@@ -157,8 +164,13 @@ impl RightExistencePWMJStream {
157164
streamed: SendableRecordBatchStream,
158165
buffered_extreme_fut: OnceFut<BufferedExtreme>,
159166
join_metrics: BuildProbeJoinMetrics,
167+
batch_size: usize,
160168
) -> Self {
161169
Self {
170+
output_batches: Box::new(BatchCoalescer::new(
171+
Arc::clone(&schema),
172+
batch_size,
173+
)),
162174
schema,
163175
on_streamed,
164176
join_type,
@@ -183,6 +195,9 @@ impl RightExistencePWMJStream {
183195
RightExistencePWMJStreamState::ScanStreamBatches => {
184196
handle_state!(ready!(self.scan_stream_batch(cx)))
185197
}
198+
RightExistencePWMJStreamState::Draining => {
199+
handle_state!(self.drain_output())
200+
}
186201
RightExistencePWMJStreamState::Completed => Poll::Ready(None),
187202
};
188203
}
@@ -218,29 +233,50 @@ impl RightExistencePWMJStream {
218233
Poll::Ready(Ok(StatefulStreamResult::Continue))
219234
}
220235

221-
/// Fetches one streamed batch and emits the rows it contributes, if any.
236+
/// Fetches one streamed batch, filters it, and pushes the survivors into
237+
/// `output_batches`. Once the streamed side is exhausted, flushes the coalescer's
238+
/// partial batch and hands off to [`Self::drain_output`].
222239
fn scan_stream_batch(
223240
&mut self,
224241
cx: &mut std::task::Context<'_>,
225242
) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
243+
if let Some(batch) = self.output_batches.next_completed_batch() {
244+
return Poll::Ready(Ok(StatefulStreamResult::Ready(Some(batch))));
245+
}
246+
226247
match ready!(self.streamed.poll_next_unpin(cx)) {
227-
None => self.state = RightExistencePWMJStreamState::Completed,
248+
None => {
249+
self.output_batches.finish_buffered_batch()?;
250+
self.state = RightExistencePWMJStreamState::Draining;
251+
}
228252
Some(Ok(batch)) => {
229253
self.join_metrics.input_batches.add(1);
230254
self.join_metrics.input_rows.add(batch.num_rows());
231255

232256
let output = self.filter_streamed_batch(&batch)?;
233257
if output.num_rows() > 0 {
234-
return Poll::Ready(Ok(StatefulStreamResult::Ready(Some(output))));
258+
self.output_batches.push_batch(output)?;
235259
}
236-
// Nothing survived; take the next batch rather than yielding an empty one.
260+
// Nothing pushed, or not enough to complete a batch yet: loop back
261+
// through `poll_next_impl` to poll the next streamed batch.
237262
}
238263
Some(Err(err)) => return Poll::Ready(Err(err)),
239264
}
240265

241266
Poll::Ready(Ok(StatefulStreamResult::Continue))
242267
}
243268

269+
/// Drains whatever `output_batches` still holds once the streamed side is exhausted.
270+
fn drain_output(&mut self) -> Result<StatefulStreamResult<Option<RecordBatch>>> {
271+
match self.output_batches.next_completed_batch() {
272+
Some(batch) => Ok(StatefulStreamResult::Ready(Some(batch))),
273+
None => {
274+
self.state = RightExistencePWMJStreamState::Completed;
275+
Ok(StatefulStreamResult::Ready(None))
276+
}
277+
}
278+
}
279+
244280
/// Keeps the streamed rows that have a buffered match (`RightSemi`) or that have none
245281
/// (`RightAnti`), by comparing each against the single buffered extreme.
246282
fn filter_streamed_batch(&self, batch: &RecordBatch) -> Result<RecordBatch> {
@@ -325,6 +361,7 @@ mod tests {
325361
use arrow_schema::{DataType, Field, Schema};
326362
use datafusion_common::test_util::batches_to_string;
327363
use datafusion_execution::TaskContext;
364+
use datafusion_execution::config::SessionConfig;
328365
use datafusion_execution::memory_pool::GreedyMemoryPool;
329366
use datafusion_execution::runtime_env::RuntimeEnvBuilder;
330367
use datafusion_physical_expr::expressions::Column;
@@ -838,6 +875,108 @@ mod tests {
838875
Ok(())
839876
}
840877

878+
/// Each streamed batch here is one matching row, so without coalescing the stream would
879+
/// hand back 5 one-row batches. `batch_size` 2 packs them into 3 instead, pinning that
880+
/// `output_batches` actually merges across streamed-batch boundaries rather than just
881+
/// forwarding `filter_streamed_batch`'s output directly.
882+
#[tokio::test]
883+
async fn output_is_coalesced_to_batch_size() -> Result<()> {
884+
let join = join(
885+
kv_exec(&[vec![kv_batch(&[(1, Some(10))])]]),
886+
kv_exec(&[vec![
887+
kv_batch(&[(10, Some(1))]),
888+
kv_batch(&[(20, Some(2))]),
889+
kv_batch(&[(30, Some(3))]),
890+
kv_batch(&[(40, Some(4))]),
891+
kv_batch(&[(50, Some(5))]),
892+
]]),
893+
Operator::Gt,
894+
JoinType::RightSemi,
895+
)?;
896+
897+
let task_ctx = Arc::new(
898+
TaskContext::default()
899+
.with_session_config(SessionConfig::new().with_batch_size(2)),
900+
);
901+
let stream = join.execute(0, task_ctx)?;
902+
let batches = common::collect(stream).await?;
903+
904+
assert_eq!(
905+
batches.iter().map(|b| b.num_rows()).collect::<Vec<_>>(),
906+
vec![2, 2, 1],
907+
"5 matching rows over 5 input batches should pack into ceil(5/2) = 3 output \
908+
batches of at most `batch_size` rows each"
909+
);
910+
assert_eq!(
911+
input_batches(&join),
912+
5,
913+
"every streamed batch is still read"
914+
);
915+
Ok(())
916+
}
917+
918+
/// `output_is_coalesced_to_batch_size` above pins that coalescing happens; this pins that
919+
/// it doesn't reorder rows while doing it. The streamed side is genuinely sorted (via
920+
/// `SortExec`, the same claim `output_ordering_follows_the_streamed_side` checks at the
921+
/// planning level), filtering drops rows unevenly across it, and a small `batch_size`
922+
/// forces `output_batches` to repack across what were originally separate sorted
923+
/// `SortExec` output batches. `BatchCoalescer`'s `completed` buffer is a plain FIFO
924+
/// `VecDeque` in arrow-rs (`push_back`/`pop_front`, no sort), so this should hold
925+
/// regardless -- the point is to check it at runtime, not just reason about it.
926+
#[tokio::test]
927+
async fn coalescing_does_not_reorder_a_sorted_streamed_side() -> Result<()> {
928+
let streamed_input = kv_exec(&[vec![kv_batch(&[
929+
(50, Some(5)),
930+
(10, Some(199)),
931+
(90, Some(6)),
932+
(30, Some(200)),
933+
(20, Some(7)),
934+
(70, Some(8)),
935+
(40, Some(199)),
936+
(60, Some(9)),
937+
])]]);
938+
let ordering = LexOrdering::new(vec![PhysicalSortExpr::new(
939+
Arc::new(Column::new_with_schema("id", &streamed_input.schema())?),
940+
SortOptions::new(false, false),
941+
)])
942+
.unwrap();
943+
let streamed = Arc::new(SortExec::new(ordering, streamed_input));
944+
945+
// Buffered max is 100, so `>` keeps only streamed rows with k < 100 -- ids 10, 30, 40
946+
// (k in the 100s) are filtered out, unevenly across the sorted id order, so the
947+
// survivors (20, 50, 60, 70, 90) don't line up with any one original batch boundary.
948+
let join = join(
949+
kv_exec(&[vec![kv_batch(&[(1, Some(100))])]]),
950+
streamed as _,
951+
Operator::Gt,
952+
JoinType::RightSemi,
953+
)?;
954+
955+
let task_ctx = Arc::new(
956+
TaskContext::default()
957+
.with_session_config(SessionConfig::new().with_batch_size(2)),
958+
);
959+
let stream = join.execute(0, task_ctx)?;
960+
let batches = common::collect(stream).await?;
961+
962+
let ids: Vec<i32> = batches
963+
.iter()
964+
.flat_map(|b| b.column(0).as_primitive::<Int32Type>().values().to_vec())
965+
.collect();
966+
assert_eq!(
967+
ids,
968+
vec![20, 50, 60, 70, 90],
969+
"coalescing must not disturb the streamed side's sorted order"
970+
);
971+
assert_eq!(
972+
batches.iter().map(|b| b.num_rows()).collect::<Vec<_>>(),
973+
vec![2, 2, 1],
974+
"5 surviving rows packed to batch_size = 2 confirms the coalescer, not a \
975+
pass-through, produced this shape"
976+
);
977+
Ok(())
978+
}
979+
841980
/// The buffered side is folded to one key as it streams in and never materialized, so this
842981
/// join runs in a memory pool far smaller than that side. 20k buffered rows is >80 KB of
843982
/// Int32 keys alone and ~160 KB of batches; the pool here is 64 KB, which the collecting

‎datafusion/proto/tests/cases/plans/joins.rs‎

Lines changed: 15 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -572,9 +572,10 @@ fn piecewise_join(
572572
/// orderings and plan properties inside `try_new`, so only the six constructor
573573
/// arguments travel on the wire. Cover the full cartesian product of the two
574574
/// enum-valued ones: every range operator against every supported join type --
575-
/// the four classic ones plus the two left existence joins, whose output schema is
576-
/// the buffered side alone. (Right existence joins and Mark joins are rejected by
577-
/// `try_new`, so this is the complete set.)
575+
/// the four classic ones plus the four existence joins, whose output schema is
576+
/// one side alone (buffered for `LeftSemi`/`LeftAnti`, streamed for
577+
/// `RightSemi`/`RightAnti`). Mark joins are rejected by `try_new`, so this is
578+
/// the complete set.
578579
#[test]
579580
fn roundtrip_piecewise_merge_join() -> Result<()> {
580581
let (schema_buffered, schema_streamed) = piecewise_schemas();
@@ -591,6 +592,8 @@ fn roundtrip_piecewise_merge_join() -> Result<()> {
591592
JoinType::Full,
592593
JoinType::LeftSemi,
593594
JoinType::LeftAnti,
595+
JoinType::RightSemi,
596+
JoinType::RightAnti,
594597
] {
595598
let result = roundtrip_test_and_return(
596599
Arc::new(PiecewiseMergeJoinExec::try_new(
@@ -615,17 +618,17 @@ fn roundtrip_piecewise_merge_join() -> Result<()> {
615618
// Both the name and the index have to survive on the correct side.
616619
assert_eq!(result.on.0.to_string(), "a@2");
617620
assert_eq!(result.on.1.to_string(), "b@0");
618-
// The existence joins output the buffered side alone (3 fields) while the
619-
// classic ones output both sides (3 + 2). The before/after comparison
621+
// The left existence joins output the buffered side alone (3 fields),
622+
// the right existence joins the streamed side alone (2 fields), and the
623+
// classic joins output both sides (3 + 2). The before/after comparison
620624
// inside the helper already covers the schema; this pins the expected
621-
// width absolutely, so the existence output contract is stated rather
625+
// width absolutely, so each existence output contract is stated rather
622626
// than merely preserved.
623-
let expected_fields =
624-
if matches!(join_type, JoinType::LeftSemi | JoinType::LeftAnti) {
625-
3
626-
} else {
627-
5
628-
};
627+
let expected_fields = match join_type {
628+
JoinType::LeftSemi | JoinType::LeftAnti => 3,
629+
JoinType::RightSemi | JoinType::RightAnti => 2,
630+
_ => 5,
631+
};
629632
assert_eq!(
630633
result.schema().fields().len(),
631634
expected_fields,

0 commit comments

Comments
 (0)