You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "berkaysynnada (via GitHub)" <gi...@apache.org> on 2024/03/28 06:54:57 UTC
[PR] CrossJoin Refactor [arrow-datafusion]
berkaysynnada opened a new pull request, #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
Closes #.
## Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
`CrossJoinExec` does some unnecessary operations, and does not preserve the batch size and order of any child. We can preserve the order of one child in the resulting table, and give results in the batch size of a child.
## What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
New join returns ready for each poll after pairing the current left batch and the current right row. By that way, we can preserve the batch size of left child and order of right child.
As further improvements, I think we can even return results without collecting the whole left data at first.
## Are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
-->
Fuzz test is added which both checks results and batch sizes.
## Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please add the `api change` label.
-->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "korowa (via GitHub)" <gi...@apache.org>.
korowa commented on PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#issuecomment-2028430188
And one more thing to consider (and this is the second concern) -- if LeftData will be relatively small (it's natural behaviour, due to the fact that CrossJoin supports input reordering basing on statistics), switching from "left row + right batch" to "right row + left batch" might potentially produce a massive amount of small batches -- to avoid it we might need to either wrap CrossJoin into CoalesceBatches (via this [rule](https://github.com/apache/arrow-datafusion/blob/main/datafusion/core/src/physical_optimizer/coalesce_batches.rs)), or to add some built-in buffering.
In current implementation small left side seems to be +- safe as we assume that right side is either large enough to provide full-size batches, and it's OK to produce output batch per left-side row, or, if right-side is small, due to reordering, left-side should be even smaller, so it won't make much harm.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "korowa (via GitHub)" <gi...@apache.org>.
korowa commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1546448558
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -374,64 +376,147 @@ impl Stream for CrossJoinStream {
}
impl CrossJoinStream {
- /// Separate implementation function that unpins the [`CrossJoinStream`] so
- /// that partial borrows work correctly
+ /// Separate implementation function that unpins the [`CrossJoinStream`]
+ /// so that partial borrows work correctly
fn poll_next_impl(
&mut self,
cx: &mut std::task::Context<'_>,
) -> std::task::Poll<Option<Result<RecordBatch>>> {
+ loop {
+ return match self.state {
+ CrossJoinStreamState::WaitBuildSide => {
+ handle_state!(ready!(self.collect_build_side(cx)))
+ }
+ CrossJoinStreamState::FetchProbeBatch => {
+ handle_state!(ready!(self.fetch_probe_batch(cx)))
+ }
+ CrossJoinStreamState::GenerateResult => {
+ handle_state!(self.generate_result())
+ }
+ CrossJoinStreamState::Completed => Poll::Ready(None),
+ };
+ }
+ }
+
+ /// Waits until the left data computation completes. After it is ready,
+ /// copies it into the state and continues with fetching probe side. If we
+ /// cannot receive any row from left, the operation ends without polling right.
+ fn collect_build_side(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
let build_timer = self.join_metrics.build_time.timer();
let (left_data, _) = match ready!(self.left_fut.get(cx)) {
Ok(left_data) => left_data,
- Err(e) => return Poll::Ready(Some(Err(e))),
+ Err(e) => return Poll::Ready(Err(e)),
};
build_timer.done();
- if left_data.num_rows() == 0 {
- return Poll::Ready(None);
+ // If the left batch is empty, we can return `Poll::Ready(None)` immediately.
+ if left_data.iter().all(|batch| batch.num_rows() == 0) {
+ self.state = CrossJoinStreamState::Completed;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ } else {
+ self.left_data = left_data
Review Comment:
`CrossJoinExec::execute(partition)` will create stream per each partition, so there will be multiple objects. And you're right, cloning vector of RecordBatches (cloning RecordBatches) is ok memory-wise, as columns are already behind Arcs, so it doesn't look like an issue :ok_hand:
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1543098458
##########
datafusion/sqllogictest/test_files/group_by.slt:
##########
@@ -4477,13 +4477,19 @@ LIMIT 5
query ITIPTR rowsort
SELECT r.*
FROM sales_global_with_pk as l, sales_global_with_pk as r
-LIMIT 5
+LIMIT 10
----
0 GRC 0 2022-01-01T06:00:00 EUR 30
+0 GRC 0 2022-01-01T06:00:00 EUR 30
+0 GRC 0 2022-01-01T06:00:00 EUR 30
+0 GRC 0 2022-01-01T06:00:00 EUR 30
+0 GRC 0 2022-01-01T06:00:00 EUR 30
1 FRA 1 2022-01-01T08:00:00 EUR 50
-1 FRA 3 2022-01-02T12:00:00 EUR 200
-1 TUR 2 2022-01-01T11:30:00 TRY 75
-1 TUR 4 2022-01-03T10:00:00 TRY 100
+1 FRA 1 2022-01-01T08:00:00 EUR 50
+1 FRA 1 2022-01-01T08:00:00 EUR 50
+1 FRA 1 2022-01-01T08:00:00 EUR 50
+1 FRA 1 2022-01-01T08:00:00 EUR 50
+
Review Comment:
These test results are updated since we preserve the order of the right table now.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1549442563
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -253,9 +254,11 @@ impl ExecutionPlan for CrossJoinExec {
schema: self.schema.clone(),
left_fut,
right: stream,
- right_batch: Arc::new(parking_lot::Mutex::new(None)),
+ right_batch: RecordBatch::new_empty(self.right().schema()),
Review Comment:
Done, thanks
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak commented on PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#issuecomment-2036671207
I will go ahead and merge this. Let us know if there are any overlooked issues and we will promptly fix.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "korowa (via GitHub)" <gi...@apache.org>.
korowa commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1550149513
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -380,58 +403,84 @@ impl CrossJoinStream {
&mut self,
cx: &mut std::task::Context<'_>,
) -> std::task::Poll<Option<Result<RecordBatch>>> {
+ loop {
+ return match self.state {
+ CrossJoinStreamState::WaitBuildSide => {
+ handle_state!(ready!(self.collect_build_side(cx)))
+ }
+ CrossJoinStreamState::FetchProbeBatch => {
+ handle_state!(ready!(self.fetch_probe_batch(cx)))
+ }
+ CrossJoinStreamState::BuildBatches(_) => {
+ handle_state!(self.build_batches())
+ }
+ };
+ }
+ }
+
+ /// Collects build (left) side of the join into the state. In case of an empty build batch,
+ /// the execution terminates. Otherwise, the state is updated to fetch probe (right) batch.
+ fn collect_build_side(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
let build_timer = self.join_metrics.build_time.timer();
let (left_data, _) = match ready!(self.left_fut.get(cx)) {
Ok(left_data) => left_data,
- Err(e) => return Poll::Ready(Some(Err(e))),
+ Err(e) => return Poll::Ready(Err(e)),
};
build_timer.done();
- if left_data.num_rows() == 0 {
- return Poll::Ready(None);
- }
+ let result = if left_data.num_rows() == 0 {
+ StatefulStreamResult::Ready(None)
+ } else {
+ self.left_data = left_data.clone();
+ self.state = CrossJoinStreamState::FetchProbeBatch;
+ StatefulStreamResult::Continue
+ };
+ Poll::Ready(Ok(result))
+ }
+
+ /// Fetches the probe (right) batch, updates the metrics, and save the batch in the state.
+ /// Then, the state is updated to build result batches.
+ fn fetch_probe_batch(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
+ self.left_index = 0;
+ let right_data = match ready!(self.right.poll_next_unpin(cx)) {
+ Some(Ok(right_data)) => right_data,
+ Some(Err(e)) => return Poll::Ready(Err(e)),
+ None => return Poll::Ready(Ok(StatefulStreamResult::Ready(None))),
+ };
+ self.join_metrics.input_batches.add(1);
+ self.join_metrics.input_rows.add(right_data.num_rows());
+
+ self.state = CrossJoinStreamState::BuildBatches(right_data);
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ }
- if self.left_index > 0 && self.left_index < left_data.num_rows() {
+ /// Joins the the indexed row of left data with the current probe batch.
+ /// If all the results are produced, the state is set to fetch new probe batch.
+ fn build_batches(&mut self) -> Result<StatefulStreamResult<Option<RecordBatch>>> {
+ let right_batch = self.state.try_as_record_batch()?;
+ if self.left_index < self.left_data.num_rows() {
let join_timer = self.join_metrics.join_time.timer();
- let right_batch = {
- let right_batch = self.right_batch.lock();
- right_batch.clone().unwrap()
- };
let result =
- build_batch(self.left_index, &right_batch, left_data, &self.schema);
+ build_batch(self.left_index, right_batch, &self.left_data, &self.schema);
+ join_timer.done();
self.join_metrics.input_rows.add(right_batch.num_rows());
Review Comment:
This metrics increment looks like a duplicate of one in `fetch_probe_batch`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#issuecomment-2029397635
> And one more thing to consider (and this is the second concern) -- if LeftData will be relatively small (it's natural behaviour, due to the fact that CrossJoin supports input reordering basing on statistics), switching from "left row + right batch" to "right row + left batch" might potentially produce a massive amount of small batches -- to avoid it we might need to either wrap CrossJoin into CoalesceBatches (via this [rule](https://github.com/apache/arrow-datafusion/blob/main/datafusion/core/src/physical_optimizer/coalesce_batches.rs)), or to add some built-in buffering.
>
> In current implementation small left side seems to be +- safe as we assume that right side is either large enough to provide full-size batches, and it's OK to produce output batch per left-side row, or, if right-side is small, due to reordering, left-side should be even smaller, so it won't make much harm.
I can add a `CoalesceBatchesExec` into the left child, but it requires more analysis such that what is the batch size of left child, is it already a `CoalesceBatchesExec`, if it is so how would they be merged etc. What I observe is that the rule adds `CoalesceBatchesExec` above the plans which reduces/filters the number of rows. CrossJoin does not do such a thing. I think all streams are written assuming they receive the correct number of batch size.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "korowa (via GitHub)" <gi...@apache.org>.
korowa commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1550149513
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -380,58 +403,84 @@ impl CrossJoinStream {
&mut self,
cx: &mut std::task::Context<'_>,
) -> std::task::Poll<Option<Result<RecordBatch>>> {
+ loop {
+ return match self.state {
+ CrossJoinStreamState::WaitBuildSide => {
+ handle_state!(ready!(self.collect_build_side(cx)))
+ }
+ CrossJoinStreamState::FetchProbeBatch => {
+ handle_state!(ready!(self.fetch_probe_batch(cx)))
+ }
+ CrossJoinStreamState::BuildBatches(_) => {
+ handle_state!(self.build_batches())
+ }
+ };
+ }
+ }
+
+ /// Collects build (left) side of the join into the state. In case of an empty build batch,
+ /// the execution terminates. Otherwise, the state is updated to fetch probe (right) batch.
+ fn collect_build_side(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
let build_timer = self.join_metrics.build_time.timer();
let (left_data, _) = match ready!(self.left_fut.get(cx)) {
Ok(left_data) => left_data,
- Err(e) => return Poll::Ready(Some(Err(e))),
+ Err(e) => return Poll::Ready(Err(e)),
};
build_timer.done();
- if left_data.num_rows() == 0 {
- return Poll::Ready(None);
- }
+ let result = if left_data.num_rows() == 0 {
+ StatefulStreamResult::Ready(None)
+ } else {
+ self.left_data = left_data.clone();
+ self.state = CrossJoinStreamState::FetchProbeBatch;
+ StatefulStreamResult::Continue
+ };
+ Poll::Ready(Ok(result))
+ }
+
+ /// Fetches the probe (right) batch, updates the metrics, and save the batch in the state.
+ /// Then, the state is updated to build result batches.
+ fn fetch_probe_batch(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
+ self.left_index = 0;
+ let right_data = match ready!(self.right.poll_next_unpin(cx)) {
+ Some(Ok(right_data)) => right_data,
+ Some(Err(e)) => return Poll::Ready(Err(e)),
+ None => return Poll::Ready(Ok(StatefulStreamResult::Ready(None))),
+ };
+ self.join_metrics.input_batches.add(1);
+ self.join_metrics.input_rows.add(right_data.num_rows());
+
+ self.state = CrossJoinStreamState::BuildBatches(right_data);
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ }
- if self.left_index > 0 && self.left_index < left_data.num_rows() {
+ /// Joins the the indexed row of left data with the current probe batch.
+ /// If all the results are produced, the state is set to fetch new probe batch.
+ fn build_batches(&mut self) -> Result<StatefulStreamResult<Option<RecordBatch>>> {
+ let right_batch = self.state.try_as_record_batch()?;
+ if self.left_index < self.left_data.num_rows() {
let join_timer = self.join_metrics.join_time.timer();
- let right_batch = {
- let right_batch = self.right_batch.lock();
- right_batch.clone().unwrap()
- };
let result =
- build_batch(self.left_index, &right_batch, left_data, &self.schema);
+ build_batch(self.left_index, right_batch, &self.left_data, &self.schema);
+ join_timer.done();
self.join_metrics.input_rows.add(right_batch.num_rows());
Review Comment:
`input_rows` increment looks like a duplicate of one in `fetch_probe_batch`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "korowa (via GitHub)" <gi...@apache.org>.
korowa commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1550161525
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -380,58 +403,84 @@ impl CrossJoinStream {
&mut self,
cx: &mut std::task::Context<'_>,
) -> std::task::Poll<Option<Result<RecordBatch>>> {
+ loop {
+ return match self.state {
+ CrossJoinStreamState::WaitBuildSide => {
+ handle_state!(ready!(self.collect_build_side(cx)))
+ }
+ CrossJoinStreamState::FetchProbeBatch => {
+ handle_state!(ready!(self.fetch_probe_batch(cx)))
+ }
+ CrossJoinStreamState::BuildBatches(_) => {
+ handle_state!(self.build_batches())
+ }
+ };
+ }
+ }
+
+ /// Collects build (left) side of the join into the state. In case of an empty build batch,
+ /// the execution terminates. Otherwise, the state is updated to fetch probe (right) batch.
+ fn collect_build_side(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
let build_timer = self.join_metrics.build_time.timer();
let (left_data, _) = match ready!(self.left_fut.get(cx)) {
Ok(left_data) => left_data,
- Err(e) => return Poll::Ready(Some(Err(e))),
+ Err(e) => return Poll::Ready(Err(e)),
};
build_timer.done();
- if left_data.num_rows() == 0 {
- return Poll::Ready(None);
- }
+ let result = if left_data.num_rows() == 0 {
+ StatefulStreamResult::Ready(None)
+ } else {
+ self.left_data = left_data.clone();
+ self.state = CrossJoinStreamState::FetchProbeBatch;
+ StatefulStreamResult::Continue
+ };
+ Poll::Ready(Ok(result))
+ }
+
+ /// Fetches the probe (right) batch, updates the metrics, and save the batch in the state.
+ /// Then, the state is updated to build result batches.
+ fn fetch_probe_batch(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
+ self.left_index = 0;
+ let right_data = match ready!(self.right.poll_next_unpin(cx)) {
+ Some(Ok(right_data)) => right_data,
+ Some(Err(e)) => return Poll::Ready(Err(e)),
+ None => return Poll::Ready(Ok(StatefulStreamResult::Ready(None))),
+ };
+ self.join_metrics.input_batches.add(1);
+ self.join_metrics.input_rows.add(right_data.num_rows());
+
+ self.state = CrossJoinStreamState::BuildBatches(right_data);
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ }
- if self.left_index > 0 && self.left_index < left_data.num_rows() {
+ /// Joins the the indexed row of left data with the current probe batch.
+ /// If all the results are produced, the state is set to fetch new probe batch.
+ fn build_batches(&mut self) -> Result<StatefulStreamResult<Option<RecordBatch>>> {
+ let right_batch = self.state.try_as_record_batch()?;
+ if self.left_index < self.left_data.num_rows() {
let join_timer = self.join_metrics.join_time.timer();
- let right_batch = {
- let right_batch = self.right_batch.lock();
- right_batch.clone().unwrap()
- };
let result =
- build_batch(self.left_index, &right_batch, left_data, &self.schema);
+ build_batch(self.left_index, right_batch, &self.left_data, &self.schema);
+ join_timer.done();
self.join_metrics.input_rows.add(right_batch.num_rows());
Review Comment:
(I mean `input_rows`)
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -380,58 +403,84 @@ impl CrossJoinStream {
&mut self,
cx: &mut std::task::Context<'_>,
) -> std::task::Poll<Option<Result<RecordBatch>>> {
+ loop {
+ return match self.state {
+ CrossJoinStreamState::WaitBuildSide => {
+ handle_state!(ready!(self.collect_build_side(cx)))
+ }
+ CrossJoinStreamState::FetchProbeBatch => {
+ handle_state!(ready!(self.fetch_probe_batch(cx)))
+ }
+ CrossJoinStreamState::BuildBatches(_) => {
+ handle_state!(self.build_batches())
+ }
+ };
+ }
+ }
+
+ /// Collects build (left) side of the join into the state. In case of an empty build batch,
+ /// the execution terminates. Otherwise, the state is updated to fetch probe (right) batch.
+ fn collect_build_side(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
let build_timer = self.join_metrics.build_time.timer();
let (left_data, _) = match ready!(self.left_fut.get(cx)) {
Ok(left_data) => left_data,
- Err(e) => return Poll::Ready(Some(Err(e))),
+ Err(e) => return Poll::Ready(Err(e)),
};
build_timer.done();
- if left_data.num_rows() == 0 {
- return Poll::Ready(None);
- }
+ let result = if left_data.num_rows() == 0 {
+ StatefulStreamResult::Ready(None)
+ } else {
+ self.left_data = left_data.clone();
+ self.state = CrossJoinStreamState::FetchProbeBatch;
+ StatefulStreamResult::Continue
+ };
+ Poll::Ready(Ok(result))
+ }
+
+ /// Fetches the probe (right) batch, updates the metrics, and save the batch in the state.
+ /// Then, the state is updated to build result batches.
+ fn fetch_probe_batch(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
+ self.left_index = 0;
+ let right_data = match ready!(self.right.poll_next_unpin(cx)) {
+ Some(Ok(right_data)) => right_data,
+ Some(Err(e)) => return Poll::Ready(Err(e)),
+ None => return Poll::Ready(Ok(StatefulStreamResult::Ready(None))),
+ };
+ self.join_metrics.input_batches.add(1);
+ self.join_metrics.input_rows.add(right_data.num_rows());
+
+ self.state = CrossJoinStreamState::BuildBatches(right_data);
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ }
- if self.left_index > 0 && self.left_index < left_data.num_rows() {
+ /// Joins the the indexed row of left data with the current probe batch.
+ /// If all the results are produced, the state is set to fetch new probe batch.
+ fn build_batches(&mut self) -> Result<StatefulStreamResult<Option<RecordBatch>>> {
+ let right_batch = self.state.try_as_record_batch()?;
+ if self.left_index < self.left_data.num_rows() {
let join_timer = self.join_metrics.join_time.timer();
- let right_batch = {
- let right_batch = self.right_batch.lock();
- right_batch.clone().unwrap()
- };
let result =
- build_batch(self.left_index, &right_batch, left_data, &self.schema);
+ build_batch(self.left_index, right_batch, &self.left_data, &self.schema);
+ join_timer.done();
self.join_metrics.input_rows.add(right_batch.num_rows());
Review Comment:
(I mean `input_rows`)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1546066877
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -374,64 +376,147 @@ impl Stream for CrossJoinStream {
}
impl CrossJoinStream {
- /// Separate implementation function that unpins the [`CrossJoinStream`] so
- /// that partial borrows work correctly
+ /// Separate implementation function that unpins the [`CrossJoinStream`]
+ /// so that partial borrows work correctly
fn poll_next_impl(
&mut self,
cx: &mut std::task::Context<'_>,
) -> std::task::Poll<Option<Result<RecordBatch>>> {
+ loop {
+ return match self.state {
+ CrossJoinStreamState::WaitBuildSide => {
+ handle_state!(ready!(self.collect_build_side(cx)))
+ }
+ CrossJoinStreamState::FetchProbeBatch => {
+ handle_state!(ready!(self.fetch_probe_batch(cx)))
+ }
+ CrossJoinStreamState::GenerateResult => {
+ handle_state!(self.generate_result())
+ }
+ CrossJoinStreamState::Completed => Poll::Ready(None),
+ };
+ }
+ }
+
+ /// Waits until the left data computation completes. After it is ready,
+ /// copies it into the state and continues with fetching probe side. If we
+ /// cannot receive any row from left, the operation ends without polling right.
+ fn collect_build_side(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
let build_timer = self.join_metrics.build_time.timer();
let (left_data, _) = match ready!(self.left_fut.get(cx)) {
Ok(left_data) => left_data,
- Err(e) => return Poll::Ready(Some(Err(e))),
+ Err(e) => return Poll::Ready(Err(e)),
};
build_timer.done();
- if left_data.num_rows() == 0 {
- return Poll::Ready(None);
+ // If the left batch is empty, we can return `Poll::Ready(None)` immediately.
+ if left_data.iter().all(|batch| batch.num_rows() == 0) {
+ self.state = CrossJoinStreamState::Completed;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ } else {
+ self.left_data = left_data
Review Comment:
Isn't `CrossJoinExecStream` created once and execution continues on the same object? If it is so, it will be only one copy since `CrossJoinStreamState::WaitBuildSide` state is only visited once at the start of the execution. I believe the clone is not expensive here also, just a vector of references.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1546081287
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -311,20 +311,27 @@ fn stats_cartesian_product(
}
}
-/// A stream that issues [RecordBatch]es as they arrive from the right of the join.
+/// A stream that issues [RecordBatch]es as they arrive from the right of the join.
+/// Right column orders are preserved.
struct CrossJoinStream {
/// Input schema
schema: Arc<Schema>,
- /// future for data from left side
+ /// Future for data from left side
left_fut: OnceFut<JoinLeftData>,
- /// right
+ /// Right stream
right: SendableRecordBatchStream,
- /// Current value on the left
- left_index: usize,
- /// Current batch being processed from the right side
- right_batch: Arc<parking_lot::Mutex<Option<RecordBatch>>>,
- /// join execution metrics
+ /// Join execution metrics
join_metrics: BuildProbeJoinMetrics,
+ /// State information
+ state: CrossJoinStreamState,
+ /// Left data
+ left_data: Vec<RecordBatch>,
+ /// Current right batch
+ right_batch: RecordBatch,
+ /// Indexes the next processed build side batch
+ left_batch_index: usize,
Review Comment:
`build_batch` also uses them. I have tried it now but the current version seems more simple rather than adding them to function parameters as `&mut` or unwrapping the state to extract them.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1549261424
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -253,9 +254,11 @@ impl ExecutionPlan for CrossJoinExec {
schema: self.schema.clone(),
left_fut,
right: stream,
- right_batch: Arc::new(parking_lot::Mutex::new(None)),
+ right_batch: RecordBatch::new_empty(self.right().schema()),
Review Comment:
Might be cleaner to store right batch in `state` (i.e. in `BuildBatches`)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1550390077
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -380,58 +403,84 @@ impl CrossJoinStream {
&mut self,
cx: &mut std::task::Context<'_>,
) -> std::task::Poll<Option<Result<RecordBatch>>> {
+ loop {
+ return match self.state {
+ CrossJoinStreamState::WaitBuildSide => {
+ handle_state!(ready!(self.collect_build_side(cx)))
+ }
+ CrossJoinStreamState::FetchProbeBatch => {
+ handle_state!(ready!(self.fetch_probe_batch(cx)))
+ }
+ CrossJoinStreamState::BuildBatches(_) => {
+ handle_state!(self.build_batches())
+ }
+ };
+ }
+ }
+
+ /// Collects build (left) side of the join into the state. In case of an empty build batch,
+ /// the execution terminates. Otherwise, the state is updated to fetch probe (right) batch.
+ fn collect_build_side(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
let build_timer = self.join_metrics.build_time.timer();
let (left_data, _) = match ready!(self.left_fut.get(cx)) {
Ok(left_data) => left_data,
- Err(e) => return Poll::Ready(Some(Err(e))),
+ Err(e) => return Poll::Ready(Err(e)),
};
build_timer.done();
- if left_data.num_rows() == 0 {
- return Poll::Ready(None);
- }
+ let result = if left_data.num_rows() == 0 {
+ StatefulStreamResult::Ready(None)
+ } else {
+ self.left_data = left_data.clone();
+ self.state = CrossJoinStreamState::FetchProbeBatch;
+ StatefulStreamResult::Continue
+ };
+ Poll::Ready(Ok(result))
+ }
+
+ /// Fetches the probe (right) batch, updates the metrics, and save the batch in the state.
+ /// Then, the state is updated to build result batches.
+ fn fetch_probe_batch(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
+ self.left_index = 0;
+ let right_data = match ready!(self.right.poll_next_unpin(cx)) {
+ Some(Ok(right_data)) => right_data,
+ Some(Err(e)) => return Poll::Ready(Err(e)),
+ None => return Poll::Ready(Ok(StatefulStreamResult::Ready(None))),
+ };
+ self.join_metrics.input_batches.add(1);
+ self.join_metrics.input_rows.add(right_data.num_rows());
+
+ self.state = CrossJoinStreamState::BuildBatches(right_data);
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ }
- if self.left_index > 0 && self.left_index < left_data.num_rows() {
+ /// Joins the the indexed row of left data with the current probe batch.
+ /// If all the results are produced, the state is set to fetch new probe batch.
+ fn build_batches(&mut self) -> Result<StatefulStreamResult<Option<RecordBatch>>> {
+ let right_batch = self.state.try_as_record_batch()?;
+ if self.left_index < self.left_data.num_rows() {
let join_timer = self.join_metrics.join_time.timer();
- let right_batch = {
- let right_batch = self.right_batch.lock();
- right_batch.clone().unwrap()
- };
let result =
- build_batch(self.left_index, &right_batch, left_data, &self.schema);
+ build_batch(self.left_index, right_batch, &self.left_data, &self.schema);
+ join_timer.done();
self.join_metrics.input_rows.add(right_batch.num_rows());
Review Comment:
@berkaysynnada let's make sure we don't double count
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1546074123
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -374,64 +376,147 @@ impl Stream for CrossJoinStream {
}
impl CrossJoinStream {
- /// Separate implementation function that unpins the [`CrossJoinStream`] so
- /// that partial borrows work correctly
+ /// Separate implementation function that unpins the [`CrossJoinStream`]
+ /// so that partial borrows work correctly
fn poll_next_impl(
&mut self,
cx: &mut std::task::Context<'_>,
) -> std::task::Poll<Option<Result<RecordBatch>>> {
+ loop {
+ return match self.state {
+ CrossJoinStreamState::WaitBuildSide => {
+ handle_state!(ready!(self.collect_build_side(cx)))
+ }
+ CrossJoinStreamState::FetchProbeBatch => {
+ handle_state!(ready!(self.fetch_probe_batch(cx)))
+ }
+ CrossJoinStreamState::GenerateResult => {
+ handle_state!(self.generate_result())
+ }
+ CrossJoinStreamState::Completed => Poll::Ready(None),
+ };
+ }
+ }
+
+ /// Waits until the left data computation completes. After it is ready,
+ /// copies it into the state and continues with fetching probe side. If we
+ /// cannot receive any row from left, the operation ends without polling right.
+ fn collect_build_side(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
let build_timer = self.join_metrics.build_time.timer();
let (left_data, _) = match ready!(self.left_fut.get(cx)) {
Ok(left_data) => left_data,
- Err(e) => return Poll::Ready(Some(Err(e))),
+ Err(e) => return Poll::Ready(Err(e)),
};
build_timer.done();
- if left_data.num_rows() == 0 {
- return Poll::Ready(None);
+ // If the left batch is empty, we can return `Poll::Ready(None)` immediately.
+ if left_data.iter().all(|batch| batch.num_rows() == 0) {
+ self.state = CrossJoinStreamState::Completed;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ } else {
+ self.left_data = left_data
+ .clone()
+ .into_iter()
+ .filter(|batch| batch.num_rows() > 0)
+ .collect();
+ self.state = CrossJoinStreamState::FetchProbeBatch;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
}
+ }
- if self.left_index > 0 && self.left_index < left_data.num_rows() {
- let join_timer = self.join_metrics.join_time.timer();
- let right_batch = {
- let right_batch = self.right_batch.lock();
- right_batch.clone().unwrap()
- };
- let result =
- build_batch(self.left_index, &right_batch, left_data, &self.schema);
- self.join_metrics.input_rows.add(right_batch.num_rows());
- if let Ok(ref batch) = result {
- join_timer.done();
- self.join_metrics.output_batches.add(1);
- self.join_metrics.output_rows.add(batch.num_rows());
+ /// Polls the right (probe) side until a non-empty batch is ready.
+ /// Then, the next state is set as the result generation step after
+ /// the polled batch is stored in the state and indices are reset.
+ fn fetch_probe_batch(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
+ match ready!(self.right.poll_next_unpin(cx)) {
+ None => {
+ self.state = CrossJoinStreamState::Completed;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
}
- self.left_index += 1;
- return Poll::Ready(Some(result));
- }
- self.left_index = 0;
- self.right
- .poll_next_unpin(cx)
- .map(|maybe_batch| match maybe_batch {
- Some(Ok(batch)) => {
- let join_timer = self.join_metrics.join_time.timer();
- let result =
- build_batch(self.left_index, &batch, left_data, &self.schema);
- self.join_metrics.input_batches.add(1);
- self.join_metrics.input_rows.add(batch.num_rows());
- if let Ok(ref batch) = result {
- join_timer.done();
- self.join_metrics.output_batches.add(1);
- self.join_metrics.output_rows.add(batch.num_rows());
- }
- self.left_index = 1;
-
- let mut right_batch = self.right_batch.lock();
- *right_batch = Some(batch);
-
- Some(result)
+ Some(Ok(right_batch)) => {
+ // Update the metrics.
+ self.join_metrics.input_batches.add(1);
+ self.join_metrics.input_rows.add(right_batch.num_rows());
+ if right_batch.num_rows() == 0 {
+ return Poll::Ready(Ok(StatefulStreamResult::Continue));
}
- other => other,
- })
+ // New batch arrives, reset the indices.
+ self.left_batch_index = 0;
+ self.right_row_index = 0;
+ // Store the new batch into the state.
+ self.right_batch = right_batch;
+ self.state = CrossJoinStreamState::GenerateResult;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ }
+ Some(Err(err)) => Poll::Ready(Err(err)),
+ }
+ }
+
+ /// If there is non-paired rows in the probe batch, the function process them.
+ /// If not, it directs the state to fetching probe side.
+ fn generate_result(&mut self) -> Result<StatefulStreamResult<Option<RecordBatch>>> {
+ if self.right_row_index < self.right_batch.num_rows() {
+ // Right batch has some unpaired rows, continue with the next row.
+ let result_batch = self.build_batch()?;
+ Ok(StatefulStreamResult::Ready(Some(result_batch)))
+ } else {
+ self.state = CrossJoinStreamState::FetchProbeBatch;
+ Ok(StatefulStreamResult::Continue)
+ }
+ }
+
+ /// This function constructs a new `RecordBatch` by joining the left and right batches
+ /// based on the current indices. It also updates the metrics.
+ ///
+ /// # Arguments
+ /// * `self.left_data` - Array of `RecordBatch`es from the left side to be joined.
+ /// * `self.right_batch` - The current `RecordBatch` from the right side to be joined.
+ /// * `self.left_batch_index` - Index of the current left batch being processed.
+ /// * `self.right_row_index` - Index of the current row in the right batch to be joined.
+ /// * `join_metrics` - Metrics container to track performance of the join operation.
+
+ fn build_batch(&mut self) -> Result<RecordBatch> {
Review Comment:
The function uses a few field from self object, so I think leaving it in the struct impl is better. But I move the metric and index updates to `generate_result` as you suggested.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#issuecomment-2025818219
cc @korowa
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1546084513
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -374,64 +376,147 @@ impl Stream for CrossJoinStream {
}
impl CrossJoinStream {
- /// Separate implementation function that unpins the [`CrossJoinStream`] so
- /// that partial borrows work correctly
+ /// Separate implementation function that unpins the [`CrossJoinStream`]
+ /// so that partial borrows work correctly
fn poll_next_impl(
&mut self,
cx: &mut std::task::Context<'_>,
) -> std::task::Poll<Option<Result<RecordBatch>>> {
+ loop {
+ return match self.state {
+ CrossJoinStreamState::WaitBuildSide => {
+ handle_state!(ready!(self.collect_build_side(cx)))
+ }
+ CrossJoinStreamState::FetchProbeBatch => {
+ handle_state!(ready!(self.fetch_probe_batch(cx)))
+ }
+ CrossJoinStreamState::GenerateResult => {
+ handle_state!(self.generate_result())
+ }
+ CrossJoinStreamState::Completed => Poll::Ready(None),
+ };
+ }
+ }
+
+ /// Waits until the left data computation completes. After it is ready,
+ /// copies it into the state and continues with fetching probe side. If we
+ /// cannot receive any row from left, the operation ends without polling right.
+ fn collect_build_side(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
let build_timer = self.join_metrics.build_time.timer();
let (left_data, _) = match ready!(self.left_fut.get(cx)) {
Ok(left_data) => left_data,
- Err(e) => return Poll::Ready(Some(Err(e))),
+ Err(e) => return Poll::Ready(Err(e)),
};
build_timer.done();
- if left_data.num_rows() == 0 {
- return Poll::Ready(None);
+ // If the left batch is empty, we can return `Poll::Ready(None)` immediately.
+ if left_data.iter().all(|batch| batch.num_rows() == 0) {
+ self.state = CrossJoinStreamState::Completed;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ } else {
+ self.left_data = left_data
+ .clone()
+ .into_iter()
+ .filter(|batch| batch.num_rows() > 0)
+ .collect();
+ self.state = CrossJoinStreamState::FetchProbeBatch;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
}
+ }
- if self.left_index > 0 && self.left_index < left_data.num_rows() {
- let join_timer = self.join_metrics.join_time.timer();
- let right_batch = {
- let right_batch = self.right_batch.lock();
- right_batch.clone().unwrap()
- };
- let result =
- build_batch(self.left_index, &right_batch, left_data, &self.schema);
- self.join_metrics.input_rows.add(right_batch.num_rows());
- if let Ok(ref batch) = result {
- join_timer.done();
- self.join_metrics.output_batches.add(1);
- self.join_metrics.output_rows.add(batch.num_rows());
+ /// Polls the right (probe) side until a non-empty batch is ready.
+ /// Then, the next state is set as the result generation step after
+ /// the polled batch is stored in the state and indices are reset.
+ fn fetch_probe_batch(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
+ match ready!(self.right.poll_next_unpin(cx)) {
+ None => {
+ self.state = CrossJoinStreamState::Completed;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
}
- self.left_index += 1;
- return Poll::Ready(Some(result));
- }
- self.left_index = 0;
- self.right
- .poll_next_unpin(cx)
- .map(|maybe_batch| match maybe_batch {
- Some(Ok(batch)) => {
- let join_timer = self.join_metrics.join_time.timer();
- let result =
- build_batch(self.left_index, &batch, left_data, &self.schema);
- self.join_metrics.input_batches.add(1);
- self.join_metrics.input_rows.add(batch.num_rows());
- if let Ok(ref batch) = result {
- join_timer.done();
- self.join_metrics.output_batches.add(1);
- self.join_metrics.output_rows.add(batch.num_rows());
- }
- self.left_index = 1;
-
- let mut right_batch = self.right_batch.lock();
- *right_batch = Some(batch);
-
- Some(result)
+ Some(Ok(right_batch)) => {
+ // Update the metrics.
+ self.join_metrics.input_batches.add(1);
+ self.join_metrics.input_rows.add(right_batch.num_rows());
+ if right_batch.num_rows() == 0 {
+ return Poll::Ready(Ok(StatefulStreamResult::Continue));
}
- other => other,
- })
+ // New batch arrives, reset the indices.
+ self.left_batch_index = 0;
+ self.right_row_index = 0;
+ // Store the new batch into the state.
+ self.right_batch = right_batch;
+ self.state = CrossJoinStreamState::GenerateResult;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ }
+ Some(Err(err)) => Poll::Ready(Err(err)),
+ }
+ }
+
+ /// If there is non-paired rows in the probe batch, the function process them.
+ /// If not, it directs the state to fetching probe side.
+ fn generate_result(&mut self) -> Result<StatefulStreamResult<Option<RecordBatch>>> {
+ if self.right_row_index < self.right_batch.num_rows() {
+ // Right batch has some unpaired rows, continue with the next row.
+ let result_batch = self.build_batch()?;
+ Ok(StatefulStreamResult::Ready(Some(result_batch)))
+ } else {
+ self.state = CrossJoinStreamState::FetchProbeBatch;
+ Ok(StatefulStreamResult::Continue)
+ }
+ }
+
+ /// This function constructs a new `RecordBatch` by joining the left and right batches
+ /// based on the current indices. It also updates the metrics.
+ ///
+ /// # Arguments
+ /// * `self.left_data` - Array of `RecordBatch`es from the left side to be joined.
+ /// * `self.right_batch` - The current `RecordBatch` from the right side to be joined.
+ /// * `self.left_batch_index` - Index of the current left batch being processed.
+ /// * `self.right_row_index` - Index of the current row in the right batch to be joined.
+ /// * `join_metrics` - Metrics container to track performance of the join operation.
+
+ fn build_batch(&mut self) -> Result<RecordBatch> {
+ let join_timer = self.join_metrics.join_time.timer();
+ // Create copies of the indexed right-side row for joining.
+ let right_copies: Vec<Arc<dyn Array>> = get_arrayref_at_indices(
Review Comment:
I believed it to be so. Other joins use the same approach. But unfortunately I have no concrete evidence.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak merged PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1543098458
##########
datafusion/sqllogictest/test_files/group_by.slt:
##########
@@ -4477,13 +4477,19 @@ LIMIT 5
query ITIPTR rowsort
SELECT r.*
FROM sales_global_with_pk as l, sales_global_with_pk as r
-LIMIT 5
+LIMIT 10
----
0 GRC 0 2022-01-01T06:00:00 EUR 30
+0 GRC 0 2022-01-01T06:00:00 EUR 30
+0 GRC 0 2022-01-01T06:00:00 EUR 30
+0 GRC 0 2022-01-01T06:00:00 EUR 30
+0 GRC 0 2022-01-01T06:00:00 EUR 30
1 FRA 1 2022-01-01T08:00:00 EUR 50
-1 FRA 3 2022-01-02T12:00:00 EUR 200
-1 TUR 2 2022-01-01T11:30:00 TRY 75
-1 TUR 4 2022-01-03T10:00:00 TRY 100
+1 FRA 1 2022-01-01T08:00:00 EUR 50
+1 FRA 1 2022-01-01T08:00:00 EUR 50
+1 FRA 1 2022-01-01T08:00:00 EUR 50
+1 FRA 1 2022-01-01T08:00:00 EUR 50
+
Review Comment:
These test results are updated since we preserve the order of the right table now.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "korowa (via GitHub)" <gi...@apache.org>.
korowa commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1545459833
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -374,64 +376,147 @@ impl Stream for CrossJoinStream {
}
impl CrossJoinStream {
- /// Separate implementation function that unpins the [`CrossJoinStream`] so
- /// that partial borrows work correctly
+ /// Separate implementation function that unpins the [`CrossJoinStream`]
+ /// so that partial borrows work correctly
fn poll_next_impl(
&mut self,
cx: &mut std::task::Context<'_>,
) -> std::task::Poll<Option<Result<RecordBatch>>> {
+ loop {
+ return match self.state {
+ CrossJoinStreamState::WaitBuildSide => {
+ handle_state!(ready!(self.collect_build_side(cx)))
+ }
+ CrossJoinStreamState::FetchProbeBatch => {
+ handle_state!(ready!(self.fetch_probe_batch(cx)))
+ }
+ CrossJoinStreamState::GenerateResult => {
+ handle_state!(self.generate_result())
+ }
+ CrossJoinStreamState::Completed => Poll::Ready(None),
+ };
+ }
+ }
+
+ /// Waits until the left data computation completes. After it is ready,
+ /// copies it into the state and continues with fetching probe side. If we
+ /// cannot receive any row from left, the operation ends without polling right.
+ fn collect_build_side(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
let build_timer = self.join_metrics.build_time.timer();
let (left_data, _) = match ready!(self.left_fut.get(cx)) {
Ok(left_data) => left_data,
- Err(e) => return Poll::Ready(Some(Err(e))),
+ Err(e) => return Poll::Ready(Err(e)),
};
build_timer.done();
- if left_data.num_rows() == 0 {
- return Poll::Ready(None);
+ // If the left batch is empty, we can return `Poll::Ready(None)` immediately.
+ if left_data.iter().all(|batch| batch.num_rows() == 0) {
+ self.state = CrossJoinStreamState::Completed;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ } else {
+ self.left_data = left_data
Review Comment:
Will this code clone all contents of collected LeftData for each CrossJoinExec stream? If so -- could we avoid having multiple copies of left-side batches and use only the original data from left_fut, accessed via Arc?
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -311,20 +311,27 @@ fn stats_cartesian_product(
}
}
-/// A stream that issues [RecordBatch]es as they arrive from the right of the join.
+/// A stream that issues [RecordBatch]es as they arrive from the right of the join.
+/// Right column orders are preserved.
struct CrossJoinStream {
/// Input schema
schema: Arc<Schema>,
- /// future for data from left side
+ /// Future for data from left side
left_fut: OnceFut<JoinLeftData>,
- /// right
+ /// Right stream
right: SendableRecordBatchStream,
- /// Current value on the left
- left_index: usize,
- /// Current batch being processed from the right side
- right_batch: Arc<parking_lot::Mutex<Option<RecordBatch>>>,
- /// join execution metrics
+ /// Join execution metrics
join_metrics: BuildProbeJoinMetrics,
+ /// State information
+ state: CrossJoinStreamState,
+ /// Left data
+ left_data: Vec<RecordBatch>,
+ /// Current right batch
+ right_batch: RecordBatch,
+ /// Indexes the next processed build side batch
+ left_batch_index: usize,
Review Comment:
minor: Could batch & row indices be a contents of GenerateResult state (as they seem to be valid only while result generation)?
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -311,20 +311,27 @@ fn stats_cartesian_product(
}
}
-/// A stream that issues [RecordBatch]es as they arrive from the right of the join.
+/// A stream that issues [RecordBatch]es as they arrive from the right of the join.
+/// Right column orders are preserved.
struct CrossJoinStream {
/// Input schema
schema: Arc<Schema>,
- /// future for data from left side
+ /// Future for data from left side
left_fut: OnceFut<JoinLeftData>,
- /// right
+ /// Right stream
right: SendableRecordBatchStream,
- /// Current value on the left
- left_index: usize,
- /// Current batch being processed from the right side
- right_batch: Arc<parking_lot::Mutex<Option<RecordBatch>>>,
- /// join execution metrics
+ /// Join execution metrics
join_metrics: BuildProbeJoinMetrics,
+ /// State information
+ state: CrossJoinStreamState,
+ /// Left data
+ left_data: Vec<RecordBatch>,
Review Comment:
minor: we store both fut & data -- won't it make sense to store `stream.left_data` as enum (with initial/ready variants, wrapping future and data respectively)?
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -374,64 +376,147 @@ impl Stream for CrossJoinStream {
}
impl CrossJoinStream {
- /// Separate implementation function that unpins the [`CrossJoinStream`] so
- /// that partial borrows work correctly
+ /// Separate implementation function that unpins the [`CrossJoinStream`]
+ /// so that partial borrows work correctly
fn poll_next_impl(
&mut self,
cx: &mut std::task::Context<'_>,
) -> std::task::Poll<Option<Result<RecordBatch>>> {
+ loop {
+ return match self.state {
+ CrossJoinStreamState::WaitBuildSide => {
+ handle_state!(ready!(self.collect_build_side(cx)))
+ }
+ CrossJoinStreamState::FetchProbeBatch => {
+ handle_state!(ready!(self.fetch_probe_batch(cx)))
+ }
+ CrossJoinStreamState::GenerateResult => {
+ handle_state!(self.generate_result())
+ }
+ CrossJoinStreamState::Completed => Poll::Ready(None),
+ };
+ }
+ }
+
+ /// Waits until the left data computation completes. After it is ready,
+ /// copies it into the state and continues with fetching probe side. If we
+ /// cannot receive any row from left, the operation ends without polling right.
+ fn collect_build_side(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
let build_timer = self.join_metrics.build_time.timer();
let (left_data, _) = match ready!(self.left_fut.get(cx)) {
Ok(left_data) => left_data,
- Err(e) => return Poll::Ready(Some(Err(e))),
+ Err(e) => return Poll::Ready(Err(e)),
};
build_timer.done();
- if left_data.num_rows() == 0 {
- return Poll::Ready(None);
+ // If the left batch is empty, we can return `Poll::Ready(None)` immediately.
+ if left_data.iter().all(|batch| batch.num_rows() == 0) {
+ self.state = CrossJoinStreamState::Completed;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ } else {
+ self.left_data = left_data
+ .clone()
+ .into_iter()
+ .filter(|batch| batch.num_rows() > 0)
+ .collect();
+ self.state = CrossJoinStreamState::FetchProbeBatch;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
}
+ }
- if self.left_index > 0 && self.left_index < left_data.num_rows() {
- let join_timer = self.join_metrics.join_time.timer();
- let right_batch = {
- let right_batch = self.right_batch.lock();
- right_batch.clone().unwrap()
- };
- let result =
- build_batch(self.left_index, &right_batch, left_data, &self.schema);
- self.join_metrics.input_rows.add(right_batch.num_rows());
- if let Ok(ref batch) = result {
- join_timer.done();
- self.join_metrics.output_batches.add(1);
- self.join_metrics.output_rows.add(batch.num_rows());
+ /// Polls the right (probe) side until a non-empty batch is ready.
+ /// Then, the next state is set as the result generation step after
+ /// the polled batch is stored in the state and indices are reset.
+ fn fetch_probe_batch(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
+ match ready!(self.right.poll_next_unpin(cx)) {
+ None => {
+ self.state = CrossJoinStreamState::Completed;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
}
- self.left_index += 1;
- return Poll::Ready(Some(result));
- }
- self.left_index = 0;
- self.right
- .poll_next_unpin(cx)
- .map(|maybe_batch| match maybe_batch {
- Some(Ok(batch)) => {
- let join_timer = self.join_metrics.join_time.timer();
- let result =
- build_batch(self.left_index, &batch, left_data, &self.schema);
- self.join_metrics.input_batches.add(1);
- self.join_metrics.input_rows.add(batch.num_rows());
- if let Ok(ref batch) = result {
- join_timer.done();
- self.join_metrics.output_batches.add(1);
- self.join_metrics.output_rows.add(batch.num_rows());
- }
- self.left_index = 1;
-
- let mut right_batch = self.right_batch.lock();
- *right_batch = Some(batch);
-
- Some(result)
+ Some(Ok(right_batch)) => {
+ // Update the metrics.
+ self.join_metrics.input_batches.add(1);
+ self.join_metrics.input_rows.add(right_batch.num_rows());
+ if right_batch.num_rows() == 0 {
+ return Poll::Ready(Ok(StatefulStreamResult::Continue));
}
- other => other,
- })
+ // New batch arrives, reset the indices.
+ self.left_batch_index = 0;
+ self.right_row_index = 0;
+ // Store the new batch into the state.
+ self.right_batch = right_batch;
+ self.state = CrossJoinStreamState::GenerateResult;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ }
+ Some(Err(err)) => Poll::Ready(Err(err)),
+ }
+ }
+
+ /// If there is non-paired rows in the probe batch, the function process them.
+ /// If not, it directs the state to fetching probe side.
+ fn generate_result(&mut self) -> Result<StatefulStreamResult<Option<RecordBatch>>> {
+ if self.right_row_index < self.right_batch.num_rows() {
+ // Right batch has some unpaired rows, continue with the next row.
+ let result_batch = self.build_batch()?;
+ Ok(StatefulStreamResult::Ready(Some(result_batch)))
+ } else {
+ self.state = CrossJoinStreamState::FetchProbeBatch;
+ Ok(StatefulStreamResult::Continue)
+ }
+ }
+
+ /// This function constructs a new `RecordBatch` by joining the left and right batches
+ /// based on the current indices. It also updates the metrics.
+ ///
+ /// # Arguments
+ /// * `self.left_data` - Array of `RecordBatch`es from the left side to be joined.
+ /// * `self.right_batch` - The current `RecordBatch` from the right side to be joined.
+ /// * `self.left_batch_index` - Index of the current left batch being processed.
+ /// * `self.right_row_index` - Index of the current row in the right batch to be joined.
+ /// * `join_metrics` - Metrics container to track performance of the join operation.
+
+ fn build_batch(&mut self) -> Result<RecordBatch> {
Review Comment:
minor: Got the idea, but it may be a bit confusing that docstring doesn't match signature.
BTW won't it be cleaner to leave it as a standalone function (as it was before) and leave mertics & offsets updates to `generate_result`?
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -374,64 +376,147 @@ impl Stream for CrossJoinStream {
}
impl CrossJoinStream {
- /// Separate implementation function that unpins the [`CrossJoinStream`] so
- /// that partial borrows work correctly
+ /// Separate implementation function that unpins the [`CrossJoinStream`]
+ /// so that partial borrows work correctly
fn poll_next_impl(
&mut self,
cx: &mut std::task::Context<'_>,
) -> std::task::Poll<Option<Result<RecordBatch>>> {
+ loop {
+ return match self.state {
+ CrossJoinStreamState::WaitBuildSide => {
+ handle_state!(ready!(self.collect_build_side(cx)))
+ }
+ CrossJoinStreamState::FetchProbeBatch => {
+ handle_state!(ready!(self.fetch_probe_batch(cx)))
+ }
+ CrossJoinStreamState::GenerateResult => {
+ handle_state!(self.generate_result())
+ }
+ CrossJoinStreamState::Completed => Poll::Ready(None),
+ };
+ }
+ }
+
+ /// Waits until the left data computation completes. After it is ready,
+ /// copies it into the state and continues with fetching probe side. If we
+ /// cannot receive any row from left, the operation ends without polling right.
+ fn collect_build_side(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
let build_timer = self.join_metrics.build_time.timer();
let (left_data, _) = match ready!(self.left_fut.get(cx)) {
Ok(left_data) => left_data,
- Err(e) => return Poll::Ready(Some(Err(e))),
+ Err(e) => return Poll::Ready(Err(e)),
};
build_timer.done();
- if left_data.num_rows() == 0 {
- return Poll::Ready(None);
+ // If the left batch is empty, we can return `Poll::Ready(None)` immediately.
+ if left_data.iter().all(|batch| batch.num_rows() == 0) {
+ self.state = CrossJoinStreamState::Completed;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ } else {
+ self.left_data = left_data
+ .clone()
+ .into_iter()
+ .filter(|batch| batch.num_rows() > 0)
+ .collect();
+ self.state = CrossJoinStreamState::FetchProbeBatch;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
}
+ }
- if self.left_index > 0 && self.left_index < left_data.num_rows() {
- let join_timer = self.join_metrics.join_time.timer();
- let right_batch = {
- let right_batch = self.right_batch.lock();
- right_batch.clone().unwrap()
- };
- let result =
- build_batch(self.left_index, &right_batch, left_data, &self.schema);
- self.join_metrics.input_rows.add(right_batch.num_rows());
- if let Ok(ref batch) = result {
- join_timer.done();
- self.join_metrics.output_batches.add(1);
- self.join_metrics.output_rows.add(batch.num_rows());
+ /// Polls the right (probe) side until a non-empty batch is ready.
+ /// Then, the next state is set as the result generation step after
+ /// the polled batch is stored in the state and indices are reset.
+ fn fetch_probe_batch(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
+ match ready!(self.right.poll_next_unpin(cx)) {
+ None => {
+ self.state = CrossJoinStreamState::Completed;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
}
- self.left_index += 1;
- return Poll::Ready(Some(result));
- }
- self.left_index = 0;
- self.right
- .poll_next_unpin(cx)
- .map(|maybe_batch| match maybe_batch {
- Some(Ok(batch)) => {
- let join_timer = self.join_metrics.join_time.timer();
- let result =
- build_batch(self.left_index, &batch, left_data, &self.schema);
- self.join_metrics.input_batches.add(1);
- self.join_metrics.input_rows.add(batch.num_rows());
- if let Ok(ref batch) = result {
- join_timer.done();
- self.join_metrics.output_batches.add(1);
- self.join_metrics.output_rows.add(batch.num_rows());
- }
- self.left_index = 1;
-
- let mut right_batch = self.right_batch.lock();
- *right_batch = Some(batch);
-
- Some(result)
+ Some(Ok(right_batch)) => {
+ // Update the metrics.
+ self.join_metrics.input_batches.add(1);
+ self.join_metrics.input_rows.add(right_batch.num_rows());
+ if right_batch.num_rows() == 0 {
+ return Poll::Ready(Ok(StatefulStreamResult::Continue));
}
- other => other,
- })
+ // New batch arrives, reset the indices.
+ self.left_batch_index = 0;
+ self.right_row_index = 0;
+ // Store the new batch into the state.
+ self.right_batch = right_batch;
+ self.state = CrossJoinStreamState::GenerateResult;
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ }
+ Some(Err(err)) => Poll::Ready(Err(err)),
+ }
+ }
+
+ /// If there is non-paired rows in the probe batch, the function process them.
+ /// If not, it directs the state to fetching probe side.
+ fn generate_result(&mut self) -> Result<StatefulStreamResult<Option<RecordBatch>>> {
+ if self.right_row_index < self.right_batch.num_rows() {
+ // Right batch has some unpaired rows, continue with the next row.
+ let result_batch = self.build_batch()?;
+ Ok(StatefulStreamResult::Ready(Some(result_batch)))
+ } else {
+ self.state = CrossJoinStreamState::FetchProbeBatch;
+ Ok(StatefulStreamResult::Continue)
+ }
+ }
+
+ /// This function constructs a new `RecordBatch` by joining the left and right batches
+ /// based on the current indices. It also updates the metrics.
+ ///
+ /// # Arguments
+ /// * `self.left_data` - Array of `RecordBatch`es from the left side to be joined.
+ /// * `self.right_batch` - The current `RecordBatch` from the right side to be joined.
+ /// * `self.left_batch_index` - Index of the current left batch being processed.
+ /// * `self.right_row_index` - Index of the current row in the right batch to be joined.
+ /// * `join_metrics` - Metrics container to track performance of the join operation.
+
+ fn build_batch(&mut self) -> Result<RecordBatch> {
+ let join_timer = self.join_metrics.join_time.timer();
+ // Create copies of the indexed right-side row for joining.
+ let right_copies: Vec<Arc<dyn Array>> = get_arrayref_at_indices(
Review Comment:
Just a question -- is this version of build-batch more performant due to avoiding conversion through `ScalarValue`?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#issuecomment-2033920565
@korowa, can you take a quick look when you have time? I've just restructured the code and removed the unnecessary lock. Benchmarks indicate that copying the rows with `ScalarValue::to_array_of_size` is faster than using `get_arrayref_at_indices` and `PrimitiveArray::from_value`, so I've left it as is.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "korowa (via GitHub)" <gi...@apache.org>.
korowa commented on PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#issuecomment-2030022146
> I can add a `CoalesceBatchesExec` into the left child, but it requires more analysis such that what is the batch size of left child, is it already a `CoalesceBatchesExec`, if it is so how would they be merged etc. What I observe is that the rule adds `CoalesceBatchesExec` above the plans which reduces/filters the number of rows. CrossJoin does not do such a thing. I think all streams are written assuming they receive the correct number of batch size.
Yes, I was pointing out that output of CrossJoin might require to be coalesced (even if both inputs are fine in terms of batch-sizes). Here is an example: for query
```
EXPLAIN ANALYZE SELECT * FROM nation JOIN lineitem ON TRUE
```
(both tables are from tpch-sf1), I've obtained following metrics for Join:
```
-- current version from main
CrossJoinExec, metrics=[output_rows=150030375, build_input_rows=25, build_input_batches=1, input_batches=733, input_rows=150030375, output_batches=18325, build_mem_used=3376, build_time=5.742028ms, join_time=14.925451535s]
-- version from this PR
CrossJoinExec, metrics=[output_rows=150030375, build_input_batches=1, input_rows=6001215, output_batches=6001215, input_batches=733, build_input_rows=25, build_mem_used=3376, join_time=433.554947232s, build_time=1.836068ms]
```
In case build-side is relatively small in comparison with target_batch_size, cross-join produces massive amount of "undersaturated" batches.
+ these are metrics collected while running in debug mode, but still -- they show significant slowdown for such inputs case (may be explained by x300 more output batches, and work related to their construction) -- if such slowdown retains in release mode, I suppose, coalescing batches won't be a good option, and it's better to figure out how to produce proper batches right in join execution.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#issuecomment-2032103953
> > I can add a `CoalesceBatchesExec` into the left child, but it requires more analysis such that what is the batch size of left child, is it already a `CoalesceBatchesExec`, if it is so how would they be merged etc. What I observe is that the rule adds `CoalesceBatchesExec` above the plans which reduces/filters the number of rows. CrossJoin does not do such a thing. I think all streams are written assuming they receive the correct number of batch size.
>
> Yes, I was pointing out that output of CrossJoin might require to be coalesced (even if both inputs are fine in terms of batch-sizes). Here is an example: for query
>
Thank you for the detailed review and benchmark results. Yes, you are right. In those cases (where left batch sizes are less than target batch size) this strategy shows a drastic regression. I tried to concat all builded batch results until target batch size is reached, but it still shows a bad performance (approximately x20 slower). I think I should revert the changes and just remove the lock and ScalarValue conversions.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] CrossJoin Refactor [arrow-datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on code in PR #9830:
URL: https://github.com/apache/arrow-datafusion/pull/9830#discussion_r1550969889
##########
datafusion/physical-plan/src/joins/cross_join.rs:
##########
@@ -380,58 +403,84 @@ impl CrossJoinStream {
&mut self,
cx: &mut std::task::Context<'_>,
) -> std::task::Poll<Option<Result<RecordBatch>>> {
+ loop {
+ return match self.state {
+ CrossJoinStreamState::WaitBuildSide => {
+ handle_state!(ready!(self.collect_build_side(cx)))
+ }
+ CrossJoinStreamState::FetchProbeBatch => {
+ handle_state!(ready!(self.fetch_probe_batch(cx)))
+ }
+ CrossJoinStreamState::BuildBatches(_) => {
+ handle_state!(self.build_batches())
+ }
+ };
+ }
+ }
+
+ /// Collects build (left) side of the join into the state. In case of an empty build batch,
+ /// the execution terminates. Otherwise, the state is updated to fetch probe (right) batch.
+ fn collect_build_side(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
let build_timer = self.join_metrics.build_time.timer();
let (left_data, _) = match ready!(self.left_fut.get(cx)) {
Ok(left_data) => left_data,
- Err(e) => return Poll::Ready(Some(Err(e))),
+ Err(e) => return Poll::Ready(Err(e)),
};
build_timer.done();
- if left_data.num_rows() == 0 {
- return Poll::Ready(None);
- }
+ let result = if left_data.num_rows() == 0 {
+ StatefulStreamResult::Ready(None)
+ } else {
+ self.left_data = left_data.clone();
+ self.state = CrossJoinStreamState::FetchProbeBatch;
+ StatefulStreamResult::Continue
+ };
+ Poll::Ready(Ok(result))
+ }
+
+ /// Fetches the probe (right) batch, updates the metrics, and save the batch in the state.
+ /// Then, the state is updated to build result batches.
+ fn fetch_probe_batch(
+ &mut self,
+ cx: &mut std::task::Context<'_>,
+ ) -> Poll<Result<StatefulStreamResult<Option<RecordBatch>>>> {
+ self.left_index = 0;
+ let right_data = match ready!(self.right.poll_next_unpin(cx)) {
+ Some(Ok(right_data)) => right_data,
+ Some(Err(e)) => return Poll::Ready(Err(e)),
+ None => return Poll::Ready(Ok(StatefulStreamResult::Ready(None))),
+ };
+ self.join_metrics.input_batches.add(1);
+ self.join_metrics.input_rows.add(right_data.num_rows());
+
+ self.state = CrossJoinStreamState::BuildBatches(right_data);
+ Poll::Ready(Ok(StatefulStreamResult::Continue))
+ }
- if self.left_index > 0 && self.left_index < left_data.num_rows() {
+ /// Joins the the indexed row of left data with the current probe batch.
+ /// If all the results are produced, the state is set to fetch new probe batch.
+ fn build_batches(&mut self) -> Result<StatefulStreamResult<Option<RecordBatch>>> {
+ let right_batch = self.state.try_as_record_batch()?;
+ if self.left_index < self.left_data.num_rows() {
let join_timer = self.join_metrics.join_time.timer();
- let right_batch = {
- let right_batch = self.right_batch.lock();
- right_batch.clone().unwrap()
- };
let result =
- build_batch(self.left_index, &right_batch, left_data, &self.schema);
+ build_batch(self.left_index, right_batch, &self.left_data, &self.schema);
+ join_timer.done();
self.join_metrics.input_rows.add(right_batch.num_rows());
Review Comment:
@korowa is right. Removed that increment. Thanks again @korowa
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org