Skip to content

Commit 22a147d

Browse files
orlpritchie46
andauthored
perf: Fix phases ending too soon due to join sampling (#29752)
Co-authored-by: ritchie46 <[email protected]>
1 parent e319cca commit 22a147d

4 files changed

Lines changed: 55 additions & 55 deletions

File tree

‎crates/polars-stream/src/nodes/joins/equi_join.rs‎

Lines changed: 20 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -404,6 +404,8 @@ struct SampleState {
404404
left_len: usize,
405405
right: Vec<Morsel>,
406406
right_len: usize,
407+
/// The number of rows each side may sample.
408+
limits: [Arc<RelaxedCell<usize>>; 2],
407409
/// The only side being read: the preferred build side of a join with runtime
408410
/// filters, until it ends or reaches the sample limit. A side that ends is
409411
/// complete, so its key ranges are published before the other side is read.
@@ -1673,11 +1675,24 @@ impl ComputeNode for EquiJoinNode {
16731675
EquiJoinState::Sample(sample_state) => {
16741676
send[0] = PortState::Blocked;
16751677
for (idx, left) in [(0, true), (1, false)] {
1678+
// While both sides are sampled, sampling stops once a side has
1679+
// `LOPSIDED_SAMPLE_FACTOR` times the rows of the other, done, side.
1680+
let lopsided =
1681+
sample_state.only_side.is_none() && recv[1 - idx] == PortState::Done;
1682+
let limit = if lopsided {
1683+
let lopsided_limit = sample_state
1684+
.len(!left)
1685+
.saturating_mul(LOPSIDED_SAMPLE_FACTOR);
1686+
self.params.sample_limit.min(lopsided_limit)
1687+
} else {
1688+
self.params.sample_limit
1689+
};
1690+
sample_state.limits[idx].store(limit);
16761691
if recv[idx] == PortState::Done {
16771692
continue;
16781693
}
16791694
let open = sample_state.is_open(left);
1680-
recv[idx] = if open && sample_state.len(left) < self.params.sample_limit {
1695+
recv[idx] = if open && sample_state.len(left) < limit {
16811696
PortState::Ready
16821697
} else {
16831698
PortState::Blocked
@@ -1756,30 +1771,15 @@ impl ComputeNode for EquiJoinNode {
17561771
match &mut self.state {
17571772
EquiJoinState::Sample(sample_state) => {
17581773
assert!(send_ports[0].is_none());
1759-
// A side without a port is done, unless it is not being read.
1760-
let final_len = |left: bool| {
1761-
let idx = if left { 0 } else { 1 };
1762-
let known = recv_ports[idx].is_none() && sample_state.is_open(left);
1763-
let len = if known {
1764-
sample_state.len(left)
1765-
} else {
1766-
usize::MAX
1767-
};
1768-
Arc::new(RelaxedCell::from(len))
1769-
};
1770-
let left_final_len = final_len(true);
1771-
let right_final_len = final_len(false);
1772-
17731774
if let Some(left_recv) = recv_ports[0].take() {
17741775
join_handles.push(scope.spawn_task(
17751776
TaskPriority::High,
17761777
sample_sink(
17771778
left_recv.serial(),
17781779
&mut sample_state.left,
17791780
&mut sample_state.left_len,
1780-
left_final_len.clone(),
1781-
right_final_len.clone(),
1782-
self.params.sample_limit,
1781+
sample_state.limits[0].clone(),
1782+
sample_state.limits[1].clone(),
17831783
),
17841784
));
17851785
}
@@ -1790,9 +1790,8 @@ impl ComputeNode for EquiJoinNode {
17901790
right_recv.serial(),
17911791
&mut sample_state.right,
17921792
&mut sample_state.right_len,
1793-
right_final_len,
1794-
left_final_len,
1795-
self.params.sample_limit,
1793+
sample_state.limits[1].clone(),
1794+
sample_state.limits[0].clone(),
17961795
),
17971796
));
17981797
}

‎crates/polars-stream/src/nodes/joins/mod.rs‎

Lines changed: 9 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -57,31 +57,28 @@ async fn select_key_columns(
5757
unsafe { DataFrame::new_unchecked_with_broadcast(df.height(), key_columns) }
5858
}
5959

60-
/// Buffers the morsels of one side of a join until it ends, the sample limit
61-
/// is reached, or the other side ended and this side has many times its rows.
60+
/// Buffers the morsels of one side of a join until its stream ends or it has
61+
/// `limit` rows. When its stream ends, the other side is limited to
62+
/// `LOPSIDED_SAMPLE_FACTOR` times its rows: if this input is done, sampling ends
63+
/// there, and otherwise it continues in the next phase.
6264
async fn sample_sink(
6365
mut recv: PortReceiver,
6466
morsels: &mut Vec<Morsel>,
6567
len: &mut usize,
66-
this_final_len: Arc<RelaxedCell<usize>>,
67-
other_final_len: Arc<RelaxedCell<usize>>,
68-
join_sample_limit: usize,
68+
limit: Arc<RelaxedCell<usize>>,
69+
other_limit: Arc<RelaxedCell<usize>>,
6970
) -> PolarsResult<()> {
7071
while let Ok(mut morsel) = recv.recv().await {
7172
*len += morsel.height();
72-
if *len >= join_sample_limit
73-
|| *len
74-
>= other_final_len
75-
.load()
76-
.saturating_mul(LOPSIDED_SAMPLE_FACTOR)
77-
{
73+
if *len >= limit.load() {
7874
morsel.source_token().stop();
7975
}
8076

8177
drop(morsel.take_consume_token());
8278
morsels.push(morsel);
8379
}
84-
this_final_len.store(*len);
80+
let lopsided_limit = len.saturating_mul(LOPSIDED_SAMPLE_FACTOR);
81+
other_limit.store(other_limit.load().min(lopsided_limit));
8582
Ok(())
8683
}
8784

‎crates/polars-stream/src/nodes/joins/semi_anti_join.rs‎

Lines changed: 20 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -199,6 +199,8 @@ struct SampleState {
199199
left_len: usize,
200200
right: Vec<Morsel>,
201201
right_len: usize,
202+
/// The number of rows each side may sample.
203+
limits: [Arc<RelaxedCell<usize>>; 2],
202204
/// The only side being read: the preferred build side of a join with runtime
203205
/// filters, until it ends or reaches the sample limit. A side that ends is
204206
/// complete, so its keys are published before the other side is read.
@@ -1048,11 +1050,24 @@ impl ComputeNode for SemiAntiJoinNode {
10481050
SemiAntiJoinState::Sample(sample_state) => {
10491051
send[0] = PortState::Blocked;
10501052
for (idx, left) in [(0, true), (1, false)] {
1053+
// While both sides are sampled, sampling stops once a side has
1054+
// `LOPSIDED_SAMPLE_FACTOR` times the rows of the other, done, side.
1055+
let lopsided =
1056+
sample_state.only_side.is_none() && recv[1 - idx] == PortState::Done;
1057+
let limit = if lopsided {
1058+
let lopsided_limit = sample_state
1059+
.len(!left)
1060+
.saturating_mul(LOPSIDED_SAMPLE_FACTOR);
1061+
self.params.sample_limit.min(lopsided_limit)
1062+
} else {
1063+
self.params.sample_limit
1064+
};
1065+
sample_state.limits[idx].store(limit);
10511066
if recv[idx] == PortState::Done {
10521067
continue;
10531068
}
10541069
let open = sample_state.is_open(left);
1055-
recv[idx] = if open && sample_state.len(left) < self.params.sample_limit {
1070+
recv[idx] = if open && sample_state.len(left) < limit {
10561071
PortState::Ready
10571072
} else {
10581073
PortState::Blocked
@@ -1129,30 +1144,15 @@ impl ComputeNode for SemiAntiJoinNode {
11291144
match &mut self.state {
11301145
SemiAntiJoinState::Sample(sample_state) => {
11311146
assert!(send_ports[0].is_none());
1132-
// A side without a port is done, unless it is not being read.
1133-
let final_len = |left: bool| {
1134-
let idx = if left { 0 } else { 1 };
1135-
let known = recv_ports[idx].is_none() && sample_state.is_open(left);
1136-
let len = if known {
1137-
sample_state.len(left)
1138-
} else {
1139-
usize::MAX
1140-
};
1141-
Arc::new(RelaxedCell::from(len))
1142-
};
1143-
let left_final_len = final_len(true);
1144-
let right_final_len = final_len(false);
1145-
11461147
if let Some(left_recv) = recv_ports[0].take() {
11471148
join_handles.push(scope.spawn_task(
11481149
TaskPriority::High,
11491150
sample_sink(
11501151
left_recv.serial(),
11511152
&mut sample_state.left,
11521153
&mut sample_state.left_len,
1153-
left_final_len.clone(),
1154-
right_final_len.clone(),
1155-
self.params.sample_limit,
1154+
sample_state.limits[0].clone(),
1155+
sample_state.limits[1].clone(),
11561156
),
11571157
));
11581158
}
@@ -1163,9 +1163,8 @@ impl ComputeNode for SemiAntiJoinNode {
11631163
right_recv.serial(),
11641164
&mut sample_state.right,
11651165
&mut sample_state.right_len,
1166-
right_final_len,
1167-
left_final_len,
1168-
self.params.sample_limit,
1166+
sample_state.limits[1].clone(),
1167+
sample_state.limits[0].clone(),
11691168
),
11701169
));
11711170
}

‎py-polars/tests/unit/sql/test_correlated_subqueries.py‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@
1313
from pathlib import Path
1414

1515
from polars._typing import EngineType
16+
from tests.conftest import PlMonkeyPatch
1617

1718

1819
def _frames() -> dict[str, pl.DataFrame]:
@@ -759,10 +760,14 @@ def source(
759760
return register_io_source(source, schema=df.schema, is_pure=True)
760761

761762

762-
def test_correlated_aggregate_unknown_outer_size_not_restricted() -> None:
763+
def test_correlated_aggregate_unknown_outer_size_not_restricted(
764+
plmonkeypatch: PlMonkeyPatch,
765+
) -> None:
763766
# A source without a row count could be arbitrarily large, so the aggregate
764767
# is not restricted to its keys: caching it would read it whole before a
765768
# LIMIT could stop it.
769+
# The join may sample this many rows of the outer before the LIMIT applies.
770+
plmonkeypatch.setenv("POLARS_JOIN_SAMPLE_LIMIT", "1000")
766771
outer = pl.DataFrame({"k": range(2_000_000), "s": range(2_000_000)})
767772
yielded = 0
768773

0 commit comments

Comments
 (0)