You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "zanmato1984 (via GitHub)" <gi...@apache.org> on 2024/01/06 18:58:37 UTC
[PR] GH-20339: [C++] Add residual predicate support to swiss join [arrow]
zanmato1984 opened a new pull request, #39487:
URL: https://github.com/apache/arrow/pull/39487
<!--
Thanks for opening a pull request!
If this is your first pull request you can find detailed information on how
to contribute here:
* [New Contributor's Guide](https://arrow.apache.org/docs/dev/developers/guide/step_by_step/pr_lifecycle.html#reviews-and-merge-of-the-pull-request)
* [Contributing Overview](https://arrow.apache.org/docs/dev/developers/overview.html)
If this is not a [minor PR](https://github.com/apache/arrow/blob/main/CONTRIBUTING.md#Minor-Fixes). Could you open an issue for this pull request on GitHub? https://github.com/apache/arrow/issues/new/choose
Opening GitHub issues ahead of time contributes to the [Openness](http://theapacheway.com/open/#:~:text=Openness%20allows%20new%20users%20the,must%20happen%20in%20the%20open.) of the Apache Arrow project.
Then could you also rename the pull request title in the following format?
GH-${GITHUB_ISSUE_ID}: [${COMPONENT}] ${SUMMARY}
or
MINOR: [${COMPONENT}] ${SUMMARY}
In the case of PARQUET issues on JIRA the title also supports:
PARQUET-${JIRA_ISSUE_ID}: [${COMPONENT}] ${SUMMARY}
-->
### 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.
-->
### 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.
-->
### 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)?
-->
### 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 uncomment the line below and explain which changes are breaking.
-->
<!-- **This PR includes breaking changes to public APIs.** -->
<!--
Please uncomment the line below (and provide explanation) if the changes fix either (a) a security vulnerability, (b) a bug that caused incorrect or invalid data to be produced, or (c) a bug that causes a crash (even when the API contract is upheld). We use this to highlight fixes to issues that may affect users without their knowledge. For this reason, fixing bugs that cause errors don't count, since those are usually obvious.
-->
<!-- **This PR contains a "Critical 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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1462897193
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1893,58 +1893,146 @@ TEST(HashJoin, CheckHashJoinNodeOptionsValidation) {
}
}
-TEST(HashJoin, ResidualFilter) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
-
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [1, 6, "alpha"],
- [2, 5, "beta"],
- [3, 4, "alpha"]
- ])")};
- input_left.schema =
- schema({field("l1", int32()), field("l2", int32()), field("l_str", utf8())});
-
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [5, 11, "alpha"],
- [2, 12, "beta"],
- [4, 16, "alpha"]
- ])")};
- input_right.schema =
- schema({field("r1", int32()), field("r2", int32()), field("r_str", utf8())});
+class ResidualFilterCaseRunner {
+ public:
+ ResidualFilterCaseRunner(BatchesWithSchema left_input, BatchesWithSchema right_input)
+ : left_input_(std::move(left_input)), right_input_(std::move(right_input)) {}
+
+ void Run(JoinType join_type, const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(filter)},
+ expected);
+ }
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
+ const std::vector<FieldRef> right_keys, std::vector<FieldRef> left_output,
+ const std::vector<FieldRef> right_output, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(left_output),
+ std::move(right_output), std::move(filter)},
+ expected);
+ }
+
+ private:
+ void RunInternal(const HashJoinNodeOptions& options,
+ const std::vector<ExecBatch>& expected) const {
+ auto join_type_str = JoinTypeString(options.join_type);
+ auto join_cond_str =
+ JoinConditionString(options.left_keys, options.right_keys, options.filter);
+ auto output_str = OutputString(options.left_output, options.right_output);
+ for (bool parallel : {false, true}) {
+ auto parallel_str = parallel ? "parallel" : "serial";
+ SCOPED_TRACE(join_type_str + " " + join_cond_str + " " + output_str + " " +
+ parallel_str);
- Declaration left{
- "source",
- SourceNodeOptions{input_left.schema, input_left.gen(parallel, /*slow=*/false)}};
- Declaration right{
- "source",
- SourceNodeOptions{input_right.schema, input_right.gen(parallel, /*slow=*/false)}};
+ Declaration left{"source",
+ SourceNodeOptions{left_input_.schema,
+ left_input_.gen(parallel, /*slow=*/false)}};
+ Declaration right{"source",
+ SourceNodeOptions{right_input_.schema,
+ right_input_.gen(parallel, /*slow=*/false)}};
- Expression mul = call("multiply", {field_ref("l1"), field_ref("l2")});
- Expression combination = call("add", {mul, field_ref("r1")});
- Expression residual_filter = less_equal(combination, field_ref("r2"));
+ Declaration join{"hashjoin", {std::move(left), std::move(right)}, options};
- HashJoinNodeOptions join_opts{
- JoinType::FULL_OUTER,
- /*left_keys=*/{"l_str"},
- /*right_keys=*/{"r_str"}, std::move(residual_filter), "l_", "r_"};
+ ASSERT_OK_AND_ASSIGN(auto result,
+ DeclarationToExecBatches(std::move(join), parallel));
+ AssertExecBatchesEqualIgnoringOrder(result.schema, expected, result.batches);
+ }
+ }
- Declaration join{"hashjoin", {std::move(left), std::move(right)}, join_opts};
+ private:
+ BatchesWithSchema left_input_;
+ BatchesWithSchema right_input_;
- ASSERT_OK_AND_ASSIGN(auto result,
- DeclarationToExecBatches(std::move(join), parallel));
+ private:
+ static std::string JoinTypeString(JoinType t) {
+ switch (t) {
+ case JoinType::LEFT_SEMI:
+ return "LEFT_SEMI";
+ case JoinType::RIGHT_SEMI:
+ return "RIGHT_SEMI";
+ case JoinType::LEFT_ANTI:
+ return "LEFT_ANTI";
+ case JoinType::RIGHT_ANTI:
+ return "RIGHT_ANTI";
+ case JoinType::INNER:
+ return "INNER";
+ case JoinType::LEFT_OUTER:
+ return "LEFT_OUTER";
+ case JoinType::RIGHT_OUTER:
+ return "RIGHT_OUTER";
+ case JoinType::FULL_OUTER:
+ return "FULL_OUTER";
+ }
+ ARROW_DCHECK(false);
+ return "";
+ }
+
+ static std::string JoinConditionString(const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys,
+ const Expression& filter) {
+ ARROW_DCHECK(left_keys.size() > 0);
+ ARROW_DCHECK(left_keys.size() == right_keys.size());
+ std::stringstream ss;
+ ss << "on (";
+ for (size_t i = 0; i < left_keys.size(); ++i) {
+ ss << left_keys[i].ToString() << " = " << right_keys[i].ToString() << " and ";
+ }
+ ss << filter.ToString();
+ ss << ")";
+ return ss.str();
+ }
+
+ static std::string OutputString(const std::vector<FieldRef>& left_output,
Review Comment:
Sure. I'm looking at the `HashJoin.Random` case and I found that `ARROW_SCOPE_TRACE` information could be improved with more verboseness, which could leverage these util functions quite well. I think I can do it in a follow up PR. Thanks for pointing this out!
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "vibhatha (via GitHub)" <gi...@apache.org>.
vibhatha commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1462880166
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1959,47 +2047,993 @@ TEST(HashJoin, TrivialResidualFilter) {
std::vector<std::string> expected_strings = {expected_true, expected_false};
std::vector<Expression> filters = {always_true, always_false};
+ BatchesWithSchema input_left;
+ input_left.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
+ [1, "alpha"]])")};
+ input_left.schema = schema({field("l1", int32()), field("l_str", utf8())});
+
+ BatchesWithSchema input_right;
+ input_right.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
+ [1, "alpha"]])")};
+ input_right.schema = schema({field("r1", int32()), field("r_str", utf8())});
Review Comment:
Thanks for cleaning this up.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "vibhatha (via GitHub)" <gi...@apache.org>.
vibhatha commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1905658324
> > @zanmato1984 I have added a few comments, though I need more time to fully review the core change to the join. Test cases seems to be fine to me, but I will checkout and validate it again.
>
> Thanks a lot @vibhatha . Reviewing something complex as hash join is even more harder than implementing it. Really appreciate that. Let me know if there is anything I can do to help on your review.
Thanks a lot @zanmato1984, I will keep you posted.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "conbench-apache-arrow[bot] (via GitHub)" <gi...@apache.org>.
conbench-apache-arrow[bot] commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1993092389
After merging your PR, Conbench analyzed the 7 benchmarking runs that have been run so far on merge-commit 0ce72675f4dd755b2696eb6597850b21df647bb8.
There were no benchmark performance regressions. 🎉
The [full Conbench report](https://github.com/apache/arrow/runs/22590316020) has more details. It also includes information about 11 possible false positives for unstable benchmarks that are known to sometimes produce 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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1882471169
> @zanmato1984 would it be possible to add some test cases?
Yes, I am working on that.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "vibhatha (via GitHub)" <gi...@apache.org>.
vibhatha commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1882431431
@zanmato1984 would it be possible to add some test cases?
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "vibhatha (via GitHub)" <gi...@apache.org>.
vibhatha commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1462823946
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1893,58 +1893,146 @@ TEST(HashJoin, CheckHashJoinNodeOptionsValidation) {
}
}
-TEST(HashJoin, ResidualFilter) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
-
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [1, 6, "alpha"],
- [2, 5, "beta"],
- [3, 4, "alpha"]
- ])")};
- input_left.schema =
- schema({field("l1", int32()), field("l2", int32()), field("l_str", utf8())});
-
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [5, 11, "alpha"],
- [2, 12, "beta"],
- [4, 16, "alpha"]
- ])")};
- input_right.schema =
- schema({field("r1", int32()), field("r2", int32()), field("r_str", utf8())});
+class ResidualFilterCaseRunner {
+ public:
+ ResidualFilterCaseRunner(BatchesWithSchema left_input, BatchesWithSchema right_input)
+ : left_input_(std::move(left_input)), right_input_(std::move(right_input)) {}
+
+ void Run(JoinType join_type, const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(filter)},
+ expected);
+ }
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
Review Comment:
nit:
```suggestion
void Run(JoinType join_type, const std::vector<FieldRef> left_keys,
```
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1462853221
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1893,58 +1893,146 @@ TEST(HashJoin, CheckHashJoinNodeOptionsValidation) {
}
}
-TEST(HashJoin, ResidualFilter) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
-
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [1, 6, "alpha"],
- [2, 5, "beta"],
- [3, 4, "alpha"]
- ])")};
- input_left.schema =
- schema({field("l1", int32()), field("l2", int32()), field("l_str", utf8())});
-
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [5, 11, "alpha"],
- [2, 12, "beta"],
- [4, 16, "alpha"]
- ])")};
- input_right.schema =
- schema({field("r1", int32()), field("r2", int32()), field("r_str", utf8())});
+class ResidualFilterCaseRunner {
+ public:
+ ResidualFilterCaseRunner(BatchesWithSchema left_input, BatchesWithSchema right_input)
+ : left_input_(std::move(left_input)), right_input_(std::move(right_input)) {}
+
+ void Run(JoinType join_type, const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(filter)},
+ expected);
+ }
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
Review Comment:
My bad. I forgot double-checking these function signatures. I meant to use pass by (right) value then move. I've updated the PR. Truly sorry about that.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1969404238
I tried to rebase and get things messy. Let me fix my branch first. Sorry for the trouble, guys :(
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "vibhatha (via GitHub)" <gi...@apache.org>.
vibhatha commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1462832334
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1893,58 +1893,146 @@ TEST(HashJoin, CheckHashJoinNodeOptionsValidation) {
}
}
-TEST(HashJoin, ResidualFilter) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
-
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [1, 6, "alpha"],
- [2, 5, "beta"],
- [3, 4, "alpha"]
- ])")};
- input_left.schema =
- schema({field("l1", int32()), field("l2", int32()), field("l_str", utf8())});
-
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [5, 11, "alpha"],
- [2, 12, "beta"],
- [4, 16, "alpha"]
- ])")};
- input_right.schema =
- schema({field("r1", int32()), field("r2", int32()), field("r_str", utf8())});
+class ResidualFilterCaseRunner {
+ public:
+ ResidualFilterCaseRunner(BatchesWithSchema left_input, BatchesWithSchema right_input)
+ : left_input_(std::move(left_input)), right_input_(std::move(right_input)) {}
+
+ void Run(JoinType join_type, const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(filter)},
+ expected);
+ }
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
+ const std::vector<FieldRef> right_keys, std::vector<FieldRef> left_output,
+ const std::vector<FieldRef> right_output, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(left_output),
+ std::move(right_output), std::move(filter)},
+ expected);
+ }
+
+ private:
+ void RunInternal(const HashJoinNodeOptions& options,
+ const std::vector<ExecBatch>& expected) const {
+ auto join_type_str = JoinTypeString(options.join_type);
Review Comment:
maybe we could do something similar to: https://github.com/apache/arrow/blob/main/cpp/src/arrow/acero/hash_join_node_test.cc#L1049-L1058
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "vibhatha (via GitHub)" <gi...@apache.org>.
vibhatha commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1462866811
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1893,58 +1893,146 @@ TEST(HashJoin, CheckHashJoinNodeOptionsValidation) {
}
}
-TEST(HashJoin, ResidualFilter) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
-
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [1, 6, "alpha"],
- [2, 5, "beta"],
- [3, 4, "alpha"]
- ])")};
- input_left.schema =
- schema({field("l1", int32()), field("l2", int32()), field("l_str", utf8())});
-
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [5, 11, "alpha"],
- [2, 12, "beta"],
- [4, 16, "alpha"]
- ])")};
- input_right.schema =
- schema({field("r1", int32()), field("r2", int32()), field("r_str", utf8())});
+class ResidualFilterCaseRunner {
+ public:
+ ResidualFilterCaseRunner(BatchesWithSchema left_input, BatchesWithSchema right_input)
+ : left_input_(std::move(left_input)), right_input_(std::move(right_input)) {}
+
+ void Run(JoinType join_type, const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(filter)},
+ expected);
+ }
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
Review Comment:
No worries, please take your time, I am still reviewing, this might take a while. :slightly_smiling_face:
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1888359186
Hi @vibhatha , I've updated the tests and the PR is ready for review. PTAL. Thanks.
cc @westonpace
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1444355487
##########
cpp/src/arrow/acero/swiss_join.cc:
##########
@@ -1123,29 +1143,6 @@ uint32_t SwissTableForJoin::payload_id_to_key_id(uint32_t payload_id) const {
return static_cast<uint32_t>(first_greater - entries) - 1;
}
-void SwissTableForJoin::payload_ids_to_key_ids(int num_rows, const uint32_t* payload_ids,
Review Comment:
Deleted because used nowhere in existing code base.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1905586572
> @zanmato1984 I have added a few comments, though I need more time to fully review the core change to the join. Test cases seems to be fine to me, but I will checkout and validate it again.
Thanks a lot @vibhatha . Reviewing something complex as hash join is even more harder than implementing it. Really appreciate that. Let me know if there is anything I can do to help on your review.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "vibhatha (via GitHub)" <gi...@apache.org>.
vibhatha commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1905426818
@zanmato1984 will take a look. Sorry about the delay.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1506326154
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1893,58 +1893,146 @@ TEST(HashJoin, CheckHashJoinNodeOptionsValidation) {
}
}
-TEST(HashJoin, ResidualFilter) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
-
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [1, 6, "alpha"],
- [2, 5, "beta"],
- [3, 4, "alpha"]
- ])")};
- input_left.schema =
- schema({field("l1", int32()), field("l2", int32()), field("l_str", utf8())});
-
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [5, 11, "alpha"],
- [2, 12, "beta"],
- [4, 16, "alpha"]
- ])")};
- input_right.schema =
- schema({field("r1", int32()), field("r2", int32()), field("r_str", utf8())});
+class ResidualFilterCaseRunner {
+ public:
+ ResidualFilterCaseRunner(BatchesWithSchema left_input, BatchesWithSchema right_input)
+ : left_input_(std::move(left_input)), right_input_(std::move(right_input)) {}
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
+ std::vector<FieldRef> right_keys, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(filter)},
+ expected);
+ }
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
+ std::vector<FieldRef> right_keys, std::vector<FieldRef> left_output,
+ std::vector<FieldRef> right_output, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(left_output),
+ std::move(right_output), std::move(filter)},
+ expected);
+ }
+
+ private:
+ void RunInternal(const HashJoinNodeOptions& options,
+ const std::vector<ExecBatch>& expected) const {
+ auto join_type_str = JoinTypeString(options.join_type);
+ auto join_cond_str =
+ JoinConditionString(options.left_keys, options.right_keys, options.filter);
+ auto output_str = OutputString(options.left_output, options.right_output);
+ for (bool parallel : {false, true}) {
+ auto parallel_str = parallel ? "parallel" : "serial";
+ ARROW_SCOPED_TRACE(join_type_str + " " + join_cond_str + " " + output_str + " " +
+ parallel_str);
- Declaration left{
- "source",
- SourceNodeOptions{input_left.schema, input_left.gen(parallel, /*slow=*/false)}};
- Declaration right{
- "source",
- SourceNodeOptions{input_right.schema, input_right.gen(parallel, /*slow=*/false)}};
+ Declaration left{"source",
+ SourceNodeOptions{left_input_.schema,
+ left_input_.gen(parallel, /*slow=*/false)}};
+ Declaration right{"source",
+ SourceNodeOptions{right_input_.schema,
+ right_input_.gen(parallel, /*slow=*/false)}};
- Expression mul = call("multiply", {field_ref("l1"), field_ref("l2")});
- Expression combination = call("add", {mul, field_ref("r1")});
- Expression residual_filter = less_equal(combination, field_ref("r2"));
+ Declaration join{"hashjoin", {std::move(left), std::move(right)}, options};
- HashJoinNodeOptions join_opts{
- JoinType::FULL_OUTER,
- /*left_keys=*/{"l_str"},
- /*right_keys=*/{"r_str"}, std::move(residual_filter), "l_", "r_"};
+ ASSERT_OK_AND_ASSIGN(auto result,
+ DeclarationToExecBatches(std::move(join), parallel));
+ AssertExecBatchesEqualIgnoringOrder(result.schema, expected, result.batches);
+ }
+ }
- Declaration join{"hashjoin", {std::move(left), std::move(right)}, join_opts};
+ private:
+ BatchesWithSchema left_input_;
+ BatchesWithSchema right_input_;
- ASSERT_OK_AND_ASSIGN(auto result,
- DeclarationToExecBatches(std::move(join), parallel));
+ private:
+ static std::string JoinTypeString(JoinType t) {
+ switch (t) {
+ case JoinType::LEFT_SEMI:
+ return "LEFT_SEMI";
+ case JoinType::RIGHT_SEMI:
+ return "RIGHT_SEMI";
+ case JoinType::LEFT_ANTI:
+ return "LEFT_ANTI";
+ case JoinType::RIGHT_ANTI:
+ return "RIGHT_ANTI";
+ case JoinType::INNER:
+ return "INNER";
+ case JoinType::LEFT_OUTER:
+ return "LEFT_OUTER";
+ case JoinType::RIGHT_OUTER:
+ return "RIGHT_OUTER";
+ case JoinType::FULL_OUTER:
+ return "FULL_OUTER";
+ }
+ ARROW_DCHECK(false);
+ return "";
+ }
+
+ static std::string JoinConditionString(const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys,
+ const Expression& filter) {
+ ARROW_DCHECK(left_keys.size() > 0);
+ ARROW_DCHECK(left_keys.size() == right_keys.size());
+ std::stringstream ss;
+ ss << "on (";
+ for (size_t i = 0; i < left_keys.size(); ++i) {
+ ss << left_keys[i].ToString() << " = " << right_keys[i].ToString() << " and ";
+ }
+ ss << filter.ToString();
+ ss << ")";
+ return ss.str();
+ }
+
+ static std::string OutputString(const std::vector<FieldRef>& left_output,
+ const std::vector<FieldRef>& right_output) {
+ std::vector<FieldRef> both_output;
+ std::copy(left_output.begin(), left_output.end(), std::back_inserter(both_output));
+ std::copy(right_output.begin(), right_output.end(), std::back_inserter(both_output));
Review Comment:
Done.
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1959,47 +2047,993 @@ TEST(HashJoin, TrivialResidualFilter) {
std::vector<std::string> expected_strings = {expected_true, expected_false};
std::vector<Expression> filters = {always_true, always_false};
+ BatchesWithSchema input_left;
+ input_left.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
+ [1, "alpha"]])")};
+ input_left.schema = schema({field("l1", int32()), field("l_str", utf8())});
+
+ BatchesWithSchema input_right;
+ input_right.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
+ [1, "alpha"]])")};
+ input_right.schema = schema({field("r1", int32()), field("r_str", utf8())});
+
+ ResidualFilterCaseRunner runner{std::move(input_left), std::move(input_right)};
+
for (size_t test_id = 0; test_id < 2; test_id++) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
+ runner.Run(JoinType::INNER, {"l_str"}, {"r_str"}, filters[test_id],
+ {ExecBatchFromJSON({int32(), utf8(), int32(), utf8()},
+ expected_strings[test_id])});
+ }
+}
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
- [1, "alpha"]
- ])")};
- input_left.schema = schema({field("l1", int32()), field("l_str", utf8())});
+TEST(HashJoin, FineGrainedResidualFilter) {
+ struct JoinSchema {
+ std::shared_ptr<Schema> left, right;
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
- [1, "alpha"]
- ])")};
- input_right.schema = schema({field("r1", int32()), field("r_str", utf8())});
+ struct Projector {
+ std::shared_ptr<Schema> left, right;
+ std::vector<int> left_output, right_output;
- auto exec_ctx = std::make_unique<ExecContext>(
- default_memory_pool(),
- parallel ? arrow::internal::GetCpuThreadPool() : nullptr);
+ std::vector<FieldRef> LeftOutput(JoinType join_type) const {
+ if (join_type == JoinType::RIGHT_SEMI || join_type == JoinType::RIGHT_ANTI) {
+ return {};
+ }
+ std::vector<FieldRef> output(left_output.size());
+ std::transform(left_output.begin(), left_output.end(), output.begin(),
+ [](int i) { return i; });
+ return output;
+ }
- Declaration left{
- "source",
- SourceNodeOptions{input_left.schema, input_left.gen(parallel, /*slow=*/false)}};
- Declaration right{"source",
- SourceNodeOptions{input_right.schema,
- input_right.gen(parallel, /*slow=*/false)}};
+ std::vector<FieldRef> RightOutput(JoinType join_type) const {
+ if (join_type == JoinType::LEFT_SEMI || join_type == JoinType::LEFT_ANTI) {
+ return {};
+ }
+ std::vector<FieldRef> output(right_output.size());
+ std::transform(right_output.begin(), right_output.end(), output.begin(),
+ [](int i) { return i; });
+ return output;
+ }
- HashJoinNodeOptions join_opts{
- JoinType::INNER,
- /*left_keys=*/{"l_str"},
- /*right_keys=*/{"r_str"}, filters[test_id], "l_", "r_"};
+ ExecBatch Project(JoinType join_type, const ExecBatch& batch) const {
+ std::vector<Datum> values;
+ if (join_type != JoinType::RIGHT_SEMI && join_type != JoinType::RIGHT_ANTI) {
+ for (int i : left_output) {
+ values.push_back(batch[i]);
+ }
+ }
+ if (join_type != JoinType::LEFT_SEMI && join_type != JoinType::LEFT_ANTI) {
+ int left_size =
+ join_type == JoinType::RIGHT_SEMI || join_type == JoinType::RIGHT_ANTI
+ ? 0
+ : left->num_fields();
+ for (int i : right_output) {
+ values.push_back(batch[left_size + i]);
+ }
+ }
+ return {std::move(values), batch.length};
+ }
+ };
- Declaration join{"hashjoin", {std::move(left), std::move(right)}, join_opts};
+ Projector GetProjector(std::vector<int> left_output, std::vector<int> right_output) {
+ return Projector{left, right, std::move(left_output), std::move(right_output)};
+ }
+ };
+
+ BatchesWithSchema left;
+ left.batches = {ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["left_only", null, "payload"],
+ ["left_only", 0, "payload"],
+ ["left_only", 42, "payload"],
+ ["both1", null, "payload"],
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", null, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"]])")};
+ left.schema = schema(
+ {field("l_key", utf8()), field("l_filter", int32()), field("l_payload", utf8())});
+
+ BatchesWithSchema right;
+ right.batches = {ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["both1", null, "payload"],
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", null, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"],
+ ["right_only", null, "payload"],
+ ["right_only", 0, "payload"],
+ ["right_only", 42, "payload"]])")};
Review Comment:
Done.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1905341643
Hi @vibhatha , did you have a chance to take a look? 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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1972630498
Hi @westonpace , I've addressed the comments you previously left except one thing I'm uncertain about in my last post. Would you please take a look again? 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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "westonpace (via GitHub)" <gi...@apache.org>.
westonpace merged PR #39487:
URL: https://github.com/apache/arrow/pull/39487
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "westonpace (via GitHub)" <gi...@apache.org>.
westonpace commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1505997417
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1893,58 +1893,146 @@ TEST(HashJoin, CheckHashJoinNodeOptionsValidation) {
}
}
-TEST(HashJoin, ResidualFilter) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
-
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [1, 6, "alpha"],
- [2, 5, "beta"],
- [3, 4, "alpha"]
- ])")};
- input_left.schema =
- schema({field("l1", int32()), field("l2", int32()), field("l_str", utf8())});
-
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [5, 11, "alpha"],
- [2, 12, "beta"],
- [4, 16, "alpha"]
- ])")};
- input_right.schema =
- schema({field("r1", int32()), field("r2", int32()), field("r_str", utf8())});
+class ResidualFilterCaseRunner {
+ public:
+ ResidualFilterCaseRunner(BatchesWithSchema left_input, BatchesWithSchema right_input)
+ : left_input_(std::move(left_input)), right_input_(std::move(right_input)) {}
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
+ std::vector<FieldRef> right_keys, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(filter)},
+ expected);
+ }
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
+ std::vector<FieldRef> right_keys, std::vector<FieldRef> left_output,
+ std::vector<FieldRef> right_output, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(left_output),
+ std::move(right_output), std::move(filter)},
+ expected);
+ }
+
+ private:
+ void RunInternal(const HashJoinNodeOptions& options,
+ const std::vector<ExecBatch>& expected) const {
+ auto join_type_str = JoinTypeString(options.join_type);
+ auto join_cond_str =
+ JoinConditionString(options.left_keys, options.right_keys, options.filter);
+ auto output_str = OutputString(options.left_output, options.right_output);
+ for (bool parallel : {false, true}) {
+ auto parallel_str = parallel ? "parallel" : "serial";
+ ARROW_SCOPED_TRACE(join_type_str + " " + join_cond_str + " " + output_str + " " +
+ parallel_str);
- Declaration left{
- "source",
- SourceNodeOptions{input_left.schema, input_left.gen(parallel, /*slow=*/false)}};
- Declaration right{
- "source",
- SourceNodeOptions{input_right.schema, input_right.gen(parallel, /*slow=*/false)}};
+ Declaration left{"source",
+ SourceNodeOptions{left_input_.schema,
+ left_input_.gen(parallel, /*slow=*/false)}};
+ Declaration right{"source",
+ SourceNodeOptions{right_input_.schema,
+ right_input_.gen(parallel, /*slow=*/false)}};
- Expression mul = call("multiply", {field_ref("l1"), field_ref("l2")});
- Expression combination = call("add", {mul, field_ref("r1")});
- Expression residual_filter = less_equal(combination, field_ref("r2"));
+ Declaration join{"hashjoin", {std::move(left), std::move(right)}, options};
- HashJoinNodeOptions join_opts{
- JoinType::FULL_OUTER,
- /*left_keys=*/{"l_str"},
- /*right_keys=*/{"r_str"}, std::move(residual_filter), "l_", "r_"};
+ ASSERT_OK_AND_ASSIGN(auto result,
+ DeclarationToExecBatches(std::move(join), parallel));
+ AssertExecBatchesEqualIgnoringOrder(result.schema, expected, result.batches);
+ }
+ }
- Declaration join{"hashjoin", {std::move(left), std::move(right)}, join_opts};
+ private:
+ BatchesWithSchema left_input_;
+ BatchesWithSchema right_input_;
- ASSERT_OK_AND_ASSIGN(auto result,
- DeclarationToExecBatches(std::move(join), parallel));
+ private:
+ static std::string JoinTypeString(JoinType t) {
+ switch (t) {
+ case JoinType::LEFT_SEMI:
+ return "LEFT_SEMI";
+ case JoinType::RIGHT_SEMI:
+ return "RIGHT_SEMI";
+ case JoinType::LEFT_ANTI:
+ return "LEFT_ANTI";
+ case JoinType::RIGHT_ANTI:
+ return "RIGHT_ANTI";
+ case JoinType::INNER:
+ return "INNER";
+ case JoinType::LEFT_OUTER:
+ return "LEFT_OUTER";
+ case JoinType::RIGHT_OUTER:
+ return "RIGHT_OUTER";
+ case JoinType::FULL_OUTER:
+ return "FULL_OUTER";
+ }
+ ARROW_DCHECK(false);
+ return "";
+ }
+
+ static std::string JoinConditionString(const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys,
+ const Expression& filter) {
+ ARROW_DCHECK(left_keys.size() > 0);
+ ARROW_DCHECK(left_keys.size() == right_keys.size());
+ std::stringstream ss;
+ ss << "on (";
+ for (size_t i = 0; i < left_keys.size(); ++i) {
+ ss << left_keys[i].ToString() << " = " << right_keys[i].ToString() << " and ";
+ }
+ ss << filter.ToString();
+ ss << ")";
+ return ss.str();
+ }
+
+ static std::string OutputString(const std::vector<FieldRef>& left_output,
+ const std::vector<FieldRef>& right_output) {
+ std::vector<FieldRef> both_output;
+ std::copy(left_output.begin(), left_output.end(), std::back_inserter(both_output));
+ std::copy(right_output.begin(), right_output.end(), std::back_inserter(both_output));
Review Comment:
Does `std::vector::insert` not work here?
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1959,47 +2047,993 @@ TEST(HashJoin, TrivialResidualFilter) {
std::vector<std::string> expected_strings = {expected_true, expected_false};
std::vector<Expression> filters = {always_true, always_false};
+ BatchesWithSchema input_left;
+ input_left.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
+ [1, "alpha"]])")};
+ input_left.schema = schema({field("l1", int32()), field("l_str", utf8())});
+
+ BatchesWithSchema input_right;
+ input_right.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
+ [1, "alpha"]])")};
+ input_right.schema = schema({field("r1", int32()), field("r_str", utf8())});
+
+ ResidualFilterCaseRunner runner{std::move(input_left), std::move(input_right)};
+
for (size_t test_id = 0; test_id < 2; test_id++) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
+ runner.Run(JoinType::INNER, {"l_str"}, {"r_str"}, filters[test_id],
+ {ExecBatchFromJSON({int32(), utf8(), int32(), utf8()},
+ expected_strings[test_id])});
+ }
+}
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
- [1, "alpha"]
- ])")};
- input_left.schema = schema({field("l1", int32()), field("l_str", utf8())});
+TEST(HashJoin, FineGrainedResidualFilter) {
+ struct JoinSchema {
+ std::shared_ptr<Schema> left, right;
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
- [1, "alpha"]
- ])")};
- input_right.schema = schema({field("r1", int32()), field("r_str", utf8())});
+ struct Projector {
+ std::shared_ptr<Schema> left, right;
+ std::vector<int> left_output, right_output;
- auto exec_ctx = std::make_unique<ExecContext>(
- default_memory_pool(),
- parallel ? arrow::internal::GetCpuThreadPool() : nullptr);
+ std::vector<FieldRef> LeftOutput(JoinType join_type) const {
+ if (join_type == JoinType::RIGHT_SEMI || join_type == JoinType::RIGHT_ANTI) {
+ return {};
+ }
+ std::vector<FieldRef> output(left_output.size());
+ std::transform(left_output.begin(), left_output.end(), output.begin(),
+ [](int i) { return i; });
+ return output;
+ }
- Declaration left{
- "source",
- SourceNodeOptions{input_left.schema, input_left.gen(parallel, /*slow=*/false)}};
- Declaration right{"source",
- SourceNodeOptions{input_right.schema,
- input_right.gen(parallel, /*slow=*/false)}};
+ std::vector<FieldRef> RightOutput(JoinType join_type) const {
+ if (join_type == JoinType::LEFT_SEMI || join_type == JoinType::LEFT_ANTI) {
+ return {};
+ }
+ std::vector<FieldRef> output(right_output.size());
+ std::transform(right_output.begin(), right_output.end(), output.begin(),
+ [](int i) { return i; });
+ return output;
+ }
- HashJoinNodeOptions join_opts{
- JoinType::INNER,
- /*left_keys=*/{"l_str"},
- /*right_keys=*/{"r_str"}, filters[test_id], "l_", "r_"};
+ ExecBatch Project(JoinType join_type, const ExecBatch& batch) const {
+ std::vector<Datum> values;
+ if (join_type != JoinType::RIGHT_SEMI && join_type != JoinType::RIGHT_ANTI) {
+ for (int i : left_output) {
+ values.push_back(batch[i]);
+ }
+ }
+ if (join_type != JoinType::LEFT_SEMI && join_type != JoinType::LEFT_ANTI) {
+ int left_size =
+ join_type == JoinType::RIGHT_SEMI || join_type == JoinType::RIGHT_ANTI
+ ? 0
+ : left->num_fields();
+ for (int i : right_output) {
+ values.push_back(batch[left_size + i]);
+ }
+ }
+ return {std::move(values), batch.length};
+ }
+ };
- Declaration join{"hashjoin", {std::move(left), std::move(right)}, join_opts};
+ Projector GetProjector(std::vector<int> left_output, std::vector<int> right_output) {
+ return Projector{left, right, std::move(left_output), std::move(right_output)};
+ }
+ };
+
+ BatchesWithSchema left;
+ left.batches = {ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["left_only", null, "payload"],
+ ["left_only", 0, "payload"],
+ ["left_only", 42, "payload"],
+ ["both1", null, "payload"],
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", null, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"]])")};
+ left.schema = schema(
+ {field("l_key", utf8()), field("l_filter", int32()), field("l_payload", utf8())});
+
+ BatchesWithSchema right;
+ right.batches = {ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["both1", null, "payload"],
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", null, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"],
+ ["right_only", null, "payload"],
+ ["right_only", 0, "payload"],
+ ["right_only", 42, "payload"]])")};
Review Comment:
Minor nit: If you made the payload on the right side something like `r_payload` it might help clarify some of the test cases (e.g. left_semi and right_semi look identical right now even though they aren't).
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1959,47 +2047,993 @@ TEST(HashJoin, TrivialResidualFilter) {
std::vector<std::string> expected_strings = {expected_true, expected_false};
std::vector<Expression> filters = {always_true, always_false};
+ BatchesWithSchema input_left;
+ input_left.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
+ [1, "alpha"]])")};
+ input_left.schema = schema({field("l1", int32()), field("l_str", utf8())});
+
+ BatchesWithSchema input_right;
+ input_right.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
+ [1, "alpha"]])")};
+ input_right.schema = schema({field("r1", int32()), field("r_str", utf8())});
+
+ ResidualFilterCaseRunner runner{std::move(input_left), std::move(input_right)};
+
for (size_t test_id = 0; test_id < 2; test_id++) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
+ runner.Run(JoinType::INNER, {"l_str"}, {"r_str"}, filters[test_id],
+ {ExecBatchFromJSON({int32(), utf8(), int32(), utf8()},
+ expected_strings[test_id])});
+ }
+}
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
- [1, "alpha"]
- ])")};
- input_left.schema = schema({field("l1", int32()), field("l_str", utf8())});
+TEST(HashJoin, FineGrainedResidualFilter) {
+ struct JoinSchema {
+ std::shared_ptr<Schema> left, right;
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
- [1, "alpha"]
- ])")};
- input_right.schema = schema({field("r1", int32()), field("r_str", utf8())});
+ struct Projector {
+ std::shared_ptr<Schema> left, right;
+ std::vector<int> left_output, right_output;
- auto exec_ctx = std::make_unique<ExecContext>(
- default_memory_pool(),
- parallel ? arrow::internal::GetCpuThreadPool() : nullptr);
+ std::vector<FieldRef> LeftOutput(JoinType join_type) const {
+ if (join_type == JoinType::RIGHT_SEMI || join_type == JoinType::RIGHT_ANTI) {
+ return {};
+ }
+ std::vector<FieldRef> output(left_output.size());
+ std::transform(left_output.begin(), left_output.end(), output.begin(),
+ [](int i) { return i; });
+ return output;
+ }
- Declaration left{
- "source",
- SourceNodeOptions{input_left.schema, input_left.gen(parallel, /*slow=*/false)}};
- Declaration right{"source",
- SourceNodeOptions{input_right.schema,
- input_right.gen(parallel, /*slow=*/false)}};
+ std::vector<FieldRef> RightOutput(JoinType join_type) const {
+ if (join_type == JoinType::LEFT_SEMI || join_type == JoinType::LEFT_ANTI) {
+ return {};
+ }
+ std::vector<FieldRef> output(right_output.size());
+ std::transform(right_output.begin(), right_output.end(), output.begin(),
+ [](int i) { return i; });
+ return output;
+ }
- HashJoinNodeOptions join_opts{
- JoinType::INNER,
- /*left_keys=*/{"l_str"},
- /*right_keys=*/{"r_str"}, filters[test_id], "l_", "r_"};
+ ExecBatch Project(JoinType join_type, const ExecBatch& batch) const {
+ std::vector<Datum> values;
+ if (join_type != JoinType::RIGHT_SEMI && join_type != JoinType::RIGHT_ANTI) {
+ for (int i : left_output) {
+ values.push_back(batch[i]);
+ }
+ }
+ if (join_type != JoinType::LEFT_SEMI && join_type != JoinType::LEFT_ANTI) {
+ int left_size =
+ join_type == JoinType::RIGHT_SEMI || join_type == JoinType::RIGHT_ANTI
+ ? 0
+ : left->num_fields();
+ for (int i : right_output) {
+ values.push_back(batch[left_size + i]);
+ }
+ }
+ return {std::move(values), batch.length};
+ }
+ };
- Declaration join{"hashjoin", {std::move(left), std::move(right)}, join_opts};
+ Projector GetProjector(std::vector<int> left_output, std::vector<int> right_output) {
+ return Projector{left, right, std::move(left_output), std::move(right_output)};
+ }
+ };
+
+ BatchesWithSchema left;
+ left.batches = {ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["left_only", null, "payload"],
+ ["left_only", 0, "payload"],
+ ["left_only", 42, "payload"],
+ ["both1", null, "payload"],
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", null, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"]])")};
+ left.schema = schema(
+ {field("l_key", utf8()), field("l_filter", int32()), field("l_payload", utf8())});
+
+ BatchesWithSchema right;
+ right.batches = {ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["both1", null, "payload"],
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", null, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"],
+ ["right_only", null, "payload"],
+ ["right_only", 0, "payload"],
+ ["right_only", 42, "payload"]])")};
+ right.schema = schema(
+ {field("r_key", utf8()), field("r_filter", int32()), field("r_payload", utf8())});
+
+ JoinSchema join_schema{left.schema, right.schema};
+ std::vector<JoinSchema::Projector> projectors{
+ join_schema.GetProjector({0, 1, 2}, {0, 1, 2}), // Output all.
+ join_schema.GetProjector({0}, {0}), // Output key columns only.
+ join_schema.GetProjector({1}, {1}), // Output filter columns only.
+ join_schema.GetProjector({2}, {2})}; // Output payload columns only.
+
+ const ResidualFilterCaseRunner runner{std::move(left), std::move(right)};
- ASSERT_OK_AND_ASSIGN(auto result,
- DeclarationToExecBatches(std::move(join), parallel));
+ {
+ // Literal true and scalar true.
+ for (Expression filter : {literal(true), equal(literal(1), literal(1))}) {
+ std::vector<FieldRef> left_keys{"l_key", "l_filter"},
+ right_keys{"r_key", "r_filter"};
+ {
+ // Inner join.
+ JoinType join_type = JoinType::INNER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ ["both1", 0, "payload", "both1", 0, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", 0, "payload", "both2", 0, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
- std::vector<ExecBatch> expected = {ExecBatchFromJSON(
- {int32(), utf8(), int32(), utf8()}, expected_strings[test_id])};
+ {
+ // Left outer join.
+ JoinType join_type = JoinType::LEFT_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ [null, null, "payload", null, null, null],
+ [null, 0, "payload", null, null, null],
+ [null, 42, "payload", null, null, null],
+ ["left_only", null, "payload", null, null, null],
+ ["left_only", 0, "payload", null, null, null],
+ ["left_only", 42, "payload", null, null, null],
+ ["both1", null, "payload", null, null, null],
+ ["both2", null, "payload", null, null, null],
+ ["both1", 0, "payload", "both1", 0, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", 0, "payload", "both2", 0, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
- AssertExecBatchesEqualIgnoringOrder(result.schema, result.batches, expected);
+ {
+ // Right outer join.
+ JoinType join_type = JoinType::RIGHT_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ ["both1", 0, "payload", "both1", 0, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", 0, "payload", "both2", 0, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"],
+ [null, null, null, null, null, "payload"],
+ [null, null, null, null, 0, "payload"],
+ [null, null, null, null, 42, "payload"],
+ [null, null, null, "both1", null, "payload"],
+ [null, null, null, "both2", null, "payload"],
+ [null, null, null, "right_only", null, "payload"],
+ [null, null, null, "right_only", 0, "payload"],
+ [null, null, null, "right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Full outer join.
+ JoinType join_type = JoinType::FULL_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ [null, null, "payload", null, null, null],
+ [null, 0, "payload", null, null, null],
+ [null, 42, "payload", null, null, null],
+ ["left_only", null, "payload", null, null, null],
+ ["left_only", 0, "payload", null, null, null],
+ ["left_only", 42, "payload", null, null, null],
+ ["both1", null, "payload", null, null, null],
+ ["both2", null, "payload", null, null, null],
+ ["both1", 0, "payload", "both1", 0, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", 0, "payload", "both2", 0, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"],
+ [null, null, null, null, null, "payload"],
+ [null, null, null, null, 0, "payload"],
+ [null, null, null, null, 42, "payload"],
+ [null, null, null, "both1", null, "payload"],
+ [null, null, null, "both2", null, "payload"],
+ [null, null, null, "right_only", null, "payload"],
+ [null, null, null, "right_only", 0, "payload"],
+ [null, null, null, "right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Left semi join.
+ JoinType join_type = JoinType::LEFT_SEMI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Left anti join.
+ JoinType join_type = JoinType::LEFT_ANTI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["left_only", null, "payload"],
+ ["left_only", 0, "payload"],
+ ["left_only", 42, "payload"],
+ ["both1", null, "payload"],
+ ["both2", null, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Right semi join.
+ JoinType join_type = JoinType::RIGHT_SEMI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Right anti join.
+ JoinType join_type = JoinType::RIGHT_ANTI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["both1", null, "payload"],
+ ["both2", null, "payload"],
+ ["right_only", null, "payload"],
+ ["right_only", 0, "payload"],
+ ["right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+ }
+ }
+
+ {
+ // Literal false, null, and scalar false, null.
+ for (Expression filter :
+ {literal(false), literal(NullScalar()), equal(literal(0), literal(1)),
+ equal(literal(1), literal(NullScalar()))}) {
+ std::vector<FieldRef> left_keys{"l_key", "l_filter"},
+ right_keys{"r_key", "r_filter"};
+ {
+ // Inner join.
+ JoinType join_type = JoinType::INNER;
+ auto expected = ExecBatchFromJSON(
+ {utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Left outer join.
+ JoinType join_type = JoinType::LEFT_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ [null, null, "payload", null, null, null],
+ [null, 0, "payload", null, null, null],
+ [null, 42, "payload", null, null, null],
+ ["left_only", null, "payload", null, null, null],
+ ["left_only", 0, "payload", null, null, null],
+ ["left_only", 42, "payload", null, null, null],
+ ["both1", null, "payload", null, null, null],
+ ["both1", 0, "payload", null, null, null],
+ ["both1", 42, "payload", null, null, null],
+ ["both2", null, "payload", null, null, null],
+ ["both2", 0, "payload", null, null, null],
+ ["both2", 42, "payload", null, null, null]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Right outer join.
+ JoinType join_type = JoinType::RIGHT_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ [null, null, null, null, null, "payload"],
+ [null, null, null, null, 0, "payload"],
+ [null, null, null, null, 42, "payload"],
+ [null, null, null, "both1", null, "payload"],
+ [null, null, null, "both1", 0, "payload"],
+ [null, null, null, "both1", 42, "payload"],
+ [null, null, null, "both2", null, "payload"],
+ [null, null, null, "both2", 0, "payload"],
+ [null, null, null, "both2", 42, "payload"],
+ [null, null, null, "right_only", null, "payload"],
+ [null, null, null, "right_only", 0, "payload"],
+ [null, null, null, "right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Full outer join.
+ JoinType join_type = JoinType::FULL_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ [null, null, "payload", null, null, null],
+ [null, 0, "payload", null, null, null],
+ [null, 42, "payload", null, null, null],
+ ["left_only", null, "payload", null, null, null],
+ ["left_only", 0, "payload", null, null, null],
+ ["left_only", 42, "payload", null, null, null],
+ ["both1", null, "payload", null, null, null],
+ ["both1", 0, "payload", null, null, null],
+ ["both1", 42, "payload", null, null, null],
+ ["both2", null, "payload", null, null, null],
+ ["both2", 0, "payload", null, null, null],
+ ["both2", 42, "payload", null, null, null],
+ [null, null, null, null, null, "payload"],
+ [null, null, null, null, 0, "payload"],
+ [null, null, null, null, 42, "payload"],
+ [null, null, null, "both1", null, "payload"],
+ [null, null, null, "both1", 0, "payload"],
+ [null, null, null, "both1", 42, "payload"],
+ [null, null, null, "both2", null, "payload"],
+ [null, null, null, "both2", 0, "payload"],
+ [null, null, null, "both2", 42, "payload"],
+ [null, null, null, "right_only", null, "payload"],
+ [null, null, null, "right_only", 0, "payload"],
+ [null, null, null, "right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Left semi join.
+ JoinType join_type = JoinType::LEFT_SEMI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Left anti join.
+ JoinType join_type = JoinType::LEFT_ANTI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["left_only", null, "payload"],
+ ["left_only", 0, "payload"],
+ ["left_only", 42, "payload"],
+ ["both1", null, "payload"],
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", null, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Right semi join.
+ JoinType join_type = JoinType::RIGHT_SEMI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Right anti join.
+ JoinType join_type = JoinType::RIGHT_ANTI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["both1", null, "payload"],
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", null, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"],
+ ["right_only", null, "payload"],
+ ["right_only", 0, "payload"],
+ ["right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+ }
+ }
+
+ {
+ // Non-trivial filters referring left columns only.
+ for (Expression filter : {equal(field_ref("l_filter"), literal(42)),
+ not_equal(literal(0), field_ref("l_filter"))}) {
+ std::vector<FieldRef> left_keys{"l_key"}, right_keys{"r_key"};
+ {
+ // Inner join.
+ JoinType join_type = JoinType::INNER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ ["both1", 42, "payload", "both1", null, "payload"],
+ ["both1", 42, "payload", "both1", 0, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", 42, "payload", "both2", null, "payload"],
+ ["both2", 42, "payload", "both2", 0, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Left outer join.
+ JoinType join_type = JoinType::LEFT_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ [null, null, "payload", null, null, null],
+ [null, 0, "payload", null, null, null],
+ [null, 42, "payload", null, null, null],
+ ["left_only", null, "payload", null, null, null],
+ ["left_only", 0, "payload", null, null, null],
+ ["left_only", 42, "payload", null, null, null],
+ ["both1", null, "payload", null, null, null],
+ ["both1", 0, "payload", null, null, null],
+ ["both2", null, "payload", null, null, null],
+ ["both2", 0, "payload", null, null, null],
+ ["both1", 42, "payload", "both1", null, "payload"],
+ ["both1", 42, "payload", "both1", 0, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", 42, "payload", "both2", null, "payload"],
+ ["both2", 42, "payload", "both2", 0, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Right outer join.
+ JoinType join_type = JoinType::RIGHT_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ ["both1", 42, "payload", "both1", null, "payload"],
+ ["both1", 42, "payload", "both1", 0, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", 42, "payload", "both2", null, "payload"],
+ ["both2", 42, "payload", "both2", 0, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"],
+ [null, null, null, null, null, "payload"],
+ [null, null, null, null, 0, "payload"],
+ [null, null, null, null, 42, "payload"],
+ [null, null, null, "right_only", null, "payload"],
+ [null, null, null, "right_only", 0, "payload"],
+ [null, null, null, "right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Full outer join.
+ JoinType join_type = JoinType::FULL_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ [null, null, "payload", null, null, null],
+ [null, 0, "payload", null, null, null],
+ [null, 42, "payload", null, null, null],
+ ["left_only", null, "payload", null, null, null],
+ ["left_only", 0, "payload", null, null, null],
+ ["left_only", 42, "payload", null, null, null],
+ ["both1", null, "payload", null, null, null],
+ ["both1", 0, "payload", null, null, null],
+ ["both2", null, "payload", null, null, null],
+ ["both2", 0, "payload", null, null, null],
+ ["both1", 42, "payload", "both1", null, "payload"],
+ ["both1", 42, "payload", "both1", 0, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", 42, "payload", "both2", null, "payload"],
+ ["both2", 42, "payload", "both2", 0, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"],
+ [null, null, null, null, null, "payload"],
+ [null, null, null, null, 0, "payload"],
+ [null, null, null, null, 42, "payload"],
+ [null, null, null, "right_only", null, "payload"],
+ [null, null, null, "right_only", 0, "payload"],
+ [null, null, null, "right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Left semi join.
+ JoinType join_type = JoinType::LEFT_SEMI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ ["both1", 42, "payload"],
+ ["both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Left anti join.
+ JoinType join_type = JoinType::LEFT_ANTI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["left_only", null, "payload"],
+ ["left_only", 0, "payload"],
+ ["left_only", 42, "payload"],
+ ["both1", null, "payload"],
+ ["both1", 0, "payload"],
+ ["both2", null, "payload"],
+ ["both2", 0, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Right semi join.
+ JoinType join_type = JoinType::RIGHT_SEMI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ ["both1", null, "payload"],
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", null, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Right anti join.
+ JoinType join_type = JoinType::RIGHT_ANTI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["right_only", null, "payload"],
+ ["right_only", 0, "payload"],
+ ["right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+ }
+ }
+
+ {
+ // Non-trivial filters referring right columns only.
+ for (Expression filter : {equal(field_ref("r_filter"), literal(42)),
+ not_equal(literal(0), field_ref("r_filter"))}) {
+ std::vector<FieldRef> left_keys{"l_key"}, right_keys{"r_key"};
+ {
+ // Inner join.
+ JoinType join_type = JoinType::INNER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ ["both1", null, "payload", "both1", 42, "payload"],
+ ["both1", 0, "payload", "both1", 42, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", null, "payload", "both2", 42, "payload"],
+ ["both2", 0, "payload", "both2", 42, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Left outer join.
+ JoinType join_type = JoinType::LEFT_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ [null, null, "payload", null, null, null],
+ [null, 0, "payload", null, null, null],
+ [null, 42, "payload", null, null, null],
+ ["left_only", null, "payload", null, null, null],
+ ["left_only", 0, "payload", null, null, null],
+ ["left_only", 42, "payload", null, null, null],
+ ["both1", null, "payload", "both1", 42, "payload"],
+ ["both1", 0, "payload", "both1", 42, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", null, "payload", "both2", 42, "payload"],
+ ["both2", 0, "payload", "both2", 42, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Right outer join.
+ JoinType join_type = JoinType::RIGHT_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ ["both1", null, "payload", "both1", 42, "payload"],
+ ["both1", 0, "payload", "both1", 42, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", null, "payload", "both2", 42, "payload"],
+ ["both2", 0, "payload", "both2", 42, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"],
+ [null, null, null, "both1", null, "payload"],
+ [null, null, null, "both1", 0, "payload"],
+ [null, null, null, "both2", null, "payload"],
+ [null, null, null, "both2", 0, "payload"],
+ [null, null, null, null, null, "payload"],
+ [null, null, null, null, 0, "payload"],
+ [null, null, null, null, 42, "payload"],
+ [null, null, null, "right_only", null, "payload"],
+ [null, null, null, "right_only", 0, "payload"],
+ [null, null, null, "right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Full outer join.
+ JoinType join_type = JoinType::FULL_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ [null, null, "payload", null, null, null],
+ [null, 0, "payload", null, null, null],
+ [null, 42, "payload", null, null, null],
+ ["left_only", null, "payload", null, null, null],
+ ["left_only", 0, "payload", null, null, null],
+ ["left_only", 42, "payload", null, null, null],
+ ["both1", null, "payload", "both1", 42, "payload"],
+ ["both1", 0, "payload", "both1", 42, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", null, "payload", "both2", 42, "payload"],
+ ["both2", 0, "payload", "both2", 42, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"],
+ [null, null, null, "both1", null, "payload"],
+ [null, null, null, "both1", 0, "payload"],
+ [null, null, null, "both2", null, "payload"],
+ [null, null, null, "both2", 0, "payload"],
+ [null, null, null, null, null, "payload"],
+ [null, null, null, null, 0, "payload"],
+ [null, null, null, null, 42, "payload"],
+ [null, null, null, "right_only", null, "payload"],
+ [null, null, null, "right_only", 0, "payload"],
+ [null, null, null, "right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Left semi join.
+ JoinType join_type = JoinType::LEFT_SEMI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ ["both1", null, "payload"],
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", null, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Left anti join.
+ JoinType join_type = JoinType::LEFT_ANTI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["left_only", null, "payload"],
+ ["left_only", 0, "payload"],
+ ["left_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Right semi join.
+ JoinType join_type = JoinType::RIGHT_SEMI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ ["both1", 42, "payload"],
+ ["both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Right anti join.
+ JoinType join_type = JoinType::RIGHT_ANTI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["both1", null, "payload"],
+ ["both1", 0, "payload"],
+ ["both2", null, "payload"],
+ ["both2", 0, "payload"],
+ ["right_only", null, "payload"],
+ ["right_only", 0, "payload"],
+ ["right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+ }
+ }
+
+ {
+ // Non-trivial filters referring both left and right columns.
+ for (Expression filter :
+ {equal(field_ref("l_filter"), field_ref("r_filter")),
+ equal(call("subtract", {field_ref("l_filter"), field_ref("r_filter")}),
+ literal(0))}) {
+ std::vector<FieldRef> left_keys{"l_key"}, right_keys{"r_key"};
+ {
+ // Inner join.
+ JoinType join_type = JoinType::INNER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ ["both1", 0, "payload", "both1", 0, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", 0, "payload", "both2", 0, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Left outer join.
+ JoinType join_type = JoinType::LEFT_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ [null, null, "payload", null, null, null],
+ [null, 0, "payload", null, null, null],
+ [null, 42, "payload", null, null, null],
+ ["left_only", null, "payload", null, null, null],
+ ["left_only", 0, "payload", null, null, null],
+ ["left_only", 42, "payload", null, null, null],
+ ["both1", null, "payload", null, null, null],
+ ["both2", null, "payload", null, null, null],
+ ["both1", 0, "payload", "both1", 0, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", 0, "payload", "both2", 0, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Right outer join.
+ JoinType join_type = JoinType::RIGHT_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ ["both1", 0, "payload", "both1", 0, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", 0, "payload", "both2", 0, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"],
+ [null, null, null, null, null, "payload"],
+ [null, null, null, null, 0, "payload"],
+ [null, null, null, null, 42, "payload"],
+ [null, null, null, "both1", null, "payload"],
+ [null, null, null, "both2", null, "payload"],
+ [null, null, null, "right_only", null, "payload"],
+ [null, null, null, "right_only", 0, "payload"],
+ [null, null, null, "right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Full outer join.
+ JoinType join_type = JoinType::FULL_OUTER;
+ auto expected =
+ ExecBatchFromJSON({utf8(), int32(), utf8(), utf8(), int32(), utf8()}, R"([
+ [null, null, "payload", null, null, null],
+ [null, 0, "payload", null, null, null],
+ [null, 42, "payload", null, null, null],
+ ["left_only", null, "payload", null, null, null],
+ ["left_only", 0, "payload", null, null, null],
+ ["left_only", 42, "payload", null, null, null],
+ ["both1", null, "payload", null, null, null],
+ ["both2", null, "payload", null, null, null],
+ ["both1", 0, "payload", "both1", 0, "payload"],
+ ["both1", 42, "payload", "both1", 42, "payload"],
+ ["both2", 0, "payload", "both2", 0, "payload"],
+ ["both2", 42, "payload", "both2", 42, "payload"],
+ [null, null, null, null, null, "payload"],
+ [null, null, null, null, 0, "payload"],
+ [null, null, null, null, 42, "payload"],
+ [null, null, null, "both1", null, "payload"],
+ [null, null, null, "both2", null, "payload"],
+ [null, null, null, "right_only", null, "payload"],
+ [null, null, null, "right_only", 0, "payload"],
+ [null, null, null, "right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Left semi join.
+ JoinType join_type = JoinType::LEFT_SEMI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Left anti join.
+ JoinType join_type = JoinType::LEFT_ANTI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["left_only", null, "payload"],
+ ["left_only", 0, "payload"],
+ ["left_only", 42, "payload"],
+ ["both1", null, "payload"],
+ ["both2", null, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Right semi join.
+ JoinType join_type = JoinType::RIGHT_SEMI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
+
+ {
+ // Right anti join.
+ JoinType join_type = JoinType::RIGHT_ANTI;
+ auto expected = ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["both1", null, "payload"],
+ ["both2", null, "payload"],
+ ["right_only", null, "payload"],
+ ["right_only", 0, "payload"],
+ ["right_only", 42, "payload"]])");
+ for (const auto& projector : projectors) {
+ runner.Run(join_type, left_keys, right_keys, projector.LeftOutput(join_type),
+ projector.RightOutput(join_type), filter,
+ {projector.Project(join_type, expected)});
+ }
+ }
Review Comment:
I appreciate the extensive set of readable tests, thank you.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1462862280
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1893,58 +1893,146 @@ TEST(HashJoin, CheckHashJoinNodeOptionsValidation) {
}
}
-TEST(HashJoin, ResidualFilter) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
-
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [1, 6, "alpha"],
- [2, 5, "beta"],
- [3, 4, "alpha"]
- ])")};
- input_left.schema =
- schema({field("l1", int32()), field("l2", int32()), field("l_str", utf8())});
-
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [5, 11, "alpha"],
- [2, 12, "beta"],
- [4, 16, "alpha"]
- ])")};
- input_right.schema =
- schema({field("r1", int32()), field("r2", int32()), field("r_str", utf8())});
+class ResidualFilterCaseRunner {
+ public:
+ ResidualFilterCaseRunner(BatchesWithSchema left_input, BatchesWithSchema right_input)
+ : left_input_(std::move(left_input)), right_input_(std::move(right_input)) {}
+
+ void Run(JoinType join_type, const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(filter)},
+ expected);
+ }
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
+ const std::vector<FieldRef> right_keys, std::vector<FieldRef> left_output,
+ const std::vector<FieldRef> right_output, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(left_output),
+ std::move(right_output), std::move(filter)},
+ expected);
+ }
+
+ private:
+ void RunInternal(const HashJoinNodeOptions& options,
+ const std::vector<ExecBatch>& expected) const {
+ auto join_type_str = JoinTypeString(options.join_type);
+ auto join_cond_str =
+ JoinConditionString(options.left_keys, options.right_keys, options.filter);
+ auto output_str = OutputString(options.left_output, options.right_output);
+ for (bool parallel : {false, true}) {
+ auto parallel_str = parallel ? "parallel" : "serial";
+ SCOPED_TRACE(join_type_str + " " + join_cond_str + " " + output_str + " " +
+ parallel_str);
- Declaration left{
- "source",
- SourceNodeOptions{input_left.schema, input_left.gen(parallel, /*slow=*/false)}};
- Declaration right{
- "source",
- SourceNodeOptions{input_right.schema, input_right.gen(parallel, /*slow=*/false)}};
+ Declaration left{"source",
+ SourceNodeOptions{left_input_.schema,
+ left_input_.gen(parallel, /*slow=*/false)}};
+ Declaration right{"source",
+ SourceNodeOptions{right_input_.schema,
+ right_input_.gen(parallel, /*slow=*/false)}};
- Expression mul = call("multiply", {field_ref("l1"), field_ref("l2")});
- Expression combination = call("add", {mul, field_ref("r1")});
- Expression residual_filter = less_equal(combination, field_ref("r2"));
+ Declaration join{"hashjoin", {std::move(left), std::move(right)}, options};
- HashJoinNodeOptions join_opts{
- JoinType::FULL_OUTER,
- /*left_keys=*/{"l_str"},
- /*right_keys=*/{"r_str"}, std::move(residual_filter), "l_", "r_"};
+ ASSERT_OK_AND_ASSIGN(auto result,
+ DeclarationToExecBatches(std::move(join), parallel));
+ AssertExecBatchesEqualIgnoringOrder(result.schema, expected, result.batches);
+ }
+ }
- Declaration join{"hashjoin", {std::move(left), std::move(right)}, join_opts};
+ private:
+ BatchesWithSchema left_input_;
+ BatchesWithSchema right_input_;
- ASSERT_OK_AND_ASSIGN(auto result,
- DeclarationToExecBatches(std::move(join), parallel));
+ private:
+ static std::string JoinTypeString(JoinType t) {
+ switch (t) {
+ case JoinType::LEFT_SEMI:
+ return "LEFT_SEMI";
+ case JoinType::RIGHT_SEMI:
+ return "RIGHT_SEMI";
+ case JoinType::LEFT_ANTI:
+ return "LEFT_ANTI";
+ case JoinType::RIGHT_ANTI:
+ return "RIGHT_ANTI";
+ case JoinType::INNER:
+ return "INNER";
+ case JoinType::LEFT_OUTER:
+ return "LEFT_OUTER";
+ case JoinType::RIGHT_OUTER:
+ return "RIGHT_OUTER";
+ case JoinType::FULL_OUTER:
+ return "FULL_OUTER";
+ }
+ ARROW_DCHECK(false);
+ return "";
+ }
+
+ static std::string JoinConditionString(const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys,
+ const Expression& filter) {
+ ARROW_DCHECK(left_keys.size() > 0);
+ ARROW_DCHECK(left_keys.size() == right_keys.size());
+ std::stringstream ss;
+ ss << "on (";
+ for (size_t i = 0; i < left_keys.size(); ++i) {
+ ss << left_keys[i].ToString() << " = " << right_keys[i].ToString() << " and ";
+ }
+ ss << filter.ToString();
+ ss << ")";
+ return ss.str();
+ }
+
+ static std::string OutputString(const std::vector<FieldRef>& left_output,
Review Comment:
I thinking maybe we can make obtaining join type string and output string generic in the scope of this test file. So both `HashJoin.Random` and this one can leverage it. How does that sound?
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1905476201
> @zanmato1984 will take a look. Sorry about the delay.
Thank you, really appreciate that!
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1960953762
Hi @vibhatha , did you get a chance to take a look? 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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1969349294
> This appears to be well written, documented, and tested. Thank you. I don't really know the swiss join internals thoroughly enough to validate the logic here or to offer performance advice and my C++ is already getting rusty.
>
> The tests, API, etc. all look correct to me. It might be nice to have a unit test covering the multiple-batches case. I think it is covered implicitly by your benchmark but those aren't run as often.
Thanks a lot for reviewing. Really appreciate it!
I think the current `HashJoin_Random` already has pretty good coverage in terms of multi-batch-ness,
https://github.com/apache/arrow/blob/c6f20a2348b3336f2ceff5b245e5eb10db7f8ce3/cpp/src/arrow/acero/hash_join_node_test.cc#L1112-L1136
though the pattern is rather fixed, i.e., `l_key = r_key`. Do you think we still need the multi-batch cases with more extensive filter patterns?
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1506189416
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1893,58 +1893,146 @@ TEST(HashJoin, CheckHashJoinNodeOptionsValidation) {
}
}
-TEST(HashJoin, ResidualFilter) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
-
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [1, 6, "alpha"],
- [2, 5, "beta"],
- [3, 4, "alpha"]
- ])")};
- input_left.schema =
- schema({field("l1", int32()), field("l2", int32()), field("l_str", utf8())});
-
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [5, 11, "alpha"],
- [2, 12, "beta"],
- [4, 16, "alpha"]
- ])")};
- input_right.schema =
- schema({field("r1", int32()), field("r2", int32()), field("r_str", utf8())});
+class ResidualFilterCaseRunner {
+ public:
+ ResidualFilterCaseRunner(BatchesWithSchema left_input, BatchesWithSchema right_input)
+ : left_input_(std::move(left_input)), right_input_(std::move(right_input)) {}
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
+ std::vector<FieldRef> right_keys, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(filter)},
+ expected);
+ }
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
+ std::vector<FieldRef> right_keys, std::vector<FieldRef> left_output,
+ std::vector<FieldRef> right_output, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(left_output),
+ std::move(right_output), std::move(filter)},
+ expected);
+ }
+
+ private:
+ void RunInternal(const HashJoinNodeOptions& options,
+ const std::vector<ExecBatch>& expected) const {
+ auto join_type_str = JoinTypeString(options.join_type);
+ auto join_cond_str =
+ JoinConditionString(options.left_keys, options.right_keys, options.filter);
+ auto output_str = OutputString(options.left_output, options.right_output);
+ for (bool parallel : {false, true}) {
+ auto parallel_str = parallel ? "parallel" : "serial";
+ ARROW_SCOPED_TRACE(join_type_str + " " + join_cond_str + " " + output_str + " " +
+ parallel_str);
- Declaration left{
- "source",
- SourceNodeOptions{input_left.schema, input_left.gen(parallel, /*slow=*/false)}};
- Declaration right{
- "source",
- SourceNodeOptions{input_right.schema, input_right.gen(parallel, /*slow=*/false)}};
+ Declaration left{"source",
+ SourceNodeOptions{left_input_.schema,
+ left_input_.gen(parallel, /*slow=*/false)}};
+ Declaration right{"source",
+ SourceNodeOptions{right_input_.schema,
+ right_input_.gen(parallel, /*slow=*/false)}};
- Expression mul = call("multiply", {field_ref("l1"), field_ref("l2")});
- Expression combination = call("add", {mul, field_ref("r1")});
- Expression residual_filter = less_equal(combination, field_ref("r2"));
+ Declaration join{"hashjoin", {std::move(left), std::move(right)}, options};
- HashJoinNodeOptions join_opts{
- JoinType::FULL_OUTER,
- /*left_keys=*/{"l_str"},
- /*right_keys=*/{"r_str"}, std::move(residual_filter), "l_", "r_"};
+ ASSERT_OK_AND_ASSIGN(auto result,
+ DeclarationToExecBatches(std::move(join), parallel));
+ AssertExecBatchesEqualIgnoringOrder(result.schema, expected, result.batches);
+ }
+ }
- Declaration join{"hashjoin", {std::move(left), std::move(right)}, join_opts};
+ private:
+ BatchesWithSchema left_input_;
+ BatchesWithSchema right_input_;
- ASSERT_OK_AND_ASSIGN(auto result,
- DeclarationToExecBatches(std::move(join), parallel));
+ private:
+ static std::string JoinTypeString(JoinType t) {
+ switch (t) {
+ case JoinType::LEFT_SEMI:
+ return "LEFT_SEMI";
+ case JoinType::RIGHT_SEMI:
+ return "RIGHT_SEMI";
+ case JoinType::LEFT_ANTI:
+ return "LEFT_ANTI";
+ case JoinType::RIGHT_ANTI:
+ return "RIGHT_ANTI";
+ case JoinType::INNER:
+ return "INNER";
+ case JoinType::LEFT_OUTER:
+ return "LEFT_OUTER";
+ case JoinType::RIGHT_OUTER:
+ return "RIGHT_OUTER";
+ case JoinType::FULL_OUTER:
+ return "FULL_OUTER";
+ }
+ ARROW_DCHECK(false);
+ return "";
+ }
+
+ static std::string JoinConditionString(const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys,
+ const Expression& filter) {
+ ARROW_DCHECK(left_keys.size() > 0);
+ ARROW_DCHECK(left_keys.size() == right_keys.size());
+ std::stringstream ss;
+ ss << "on (";
+ for (size_t i = 0; i < left_keys.size(); ++i) {
+ ss << left_keys[i].ToString() << " = " << right_keys[i].ToString() << " and ";
+ }
+ ss << filter.ToString();
+ ss << ")";
+ return ss.str();
+ }
+
+ static std::string OutputString(const std::vector<FieldRef>& left_output,
+ const std::vector<FieldRef>& right_output) {
+ std::vector<FieldRef> both_output;
+ std::copy(left_output.begin(), left_output.end(), std::back_inserter(both_output));
+ std::copy(right_output.begin(), right_output.end(), std::back_inserter(both_output));
Review Comment:
It does. I'll update.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1907306413
I've also added some benchmarks (w/o touching files in the original PR) to justify this PR perf-wise (I've been curious myself). Swiss join using residual filter still outperforms the legacy implementation by 2x to 4x.
Here attached the detailed benchmarking results.
For trivial filter:
```
Run on (16 X 2400 MHz CPU s)
CPU Caches:
L1 Data 32 KiB
L1 Instruction 32 KiB
L2 Unified 256 KiB (x8)
L3 Unified 16384 KiB
Load Average: 2.98, 2.39, 2.09
------------------------------------------------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
------------------------------------------------------------------------------------------------------------------------------------------
BM_HashJoinBasic_TrivialResidualFilter/"Inner/Literal(true)"/Use basic:0 389846360 ns 389096000 ns 2 rows/sec=2.6949M/s
BM_HashJoinBasic_TrivialResidualFilter/"Inner/Literal(true)"/Use basic:1 1295892233 ns 1291962000 ns 1 rows/sec=811.615k/s
BM_HashJoinBasic_TrivialResidualFilter/"Left Semi/Literal(true)"/Use basic:0 103612682 ns 103334167 ns 6 rows/sec=10.1474M/s
BM_HashJoinBasic_TrivialResidualFilter/"Left Semi/Literal(true)"/Use basic:1 1037879506 ns 1035681000 ns 1 rows/sec=1.01245M/s
BM_HashJoinBasic_TrivialResidualFilter/"Right Semi/Literal(true)"/Use basic:0 263961646 ns 263375000 ns 3 rows/sec=3.9813M/s
BM_HashJoinBasic_TrivialResidualFilter/"Right Semi/Literal(true)"/Use basic:1 1048225307 ns 1045642000 ns 1 rows/sec=1.00281M/s
BM_HashJoinBasic_TrivialResidualFilter/"Left Anti/Literal(true)"/Use basic:0 89647682 ns 89423000 ns 8 rows/sec=11.726M/s
BM_HashJoinBasic_TrivialResidualFilter/"Left Anti/Literal(true)"/Use basic:1 1000408384 ns 997682000 ns 1 rows/sec=1.05101M/s
BM_HashJoinBasic_TrivialResidualFilter/"Right Anti/Literal(true)"/Use basic:0 234920722 ns 234484667 ns 3 rows/sec=4.47183M/s
BM_HashJoinBasic_TrivialResidualFilter/"Right Anti/Literal(true)"/Use basic:1 1004460080 ns 1002335000 ns 1 rows/sec=1.04613M/s
BM_HashJoinBasic_TrivialResidualFilter/"Left Outer/Literal(true)"/Use basic:0 379100088 ns 378471000 ns 2 rows/sec=2.77056M/s
BM_HashJoinBasic_TrivialResidualFilter/"Left Outer/Literal(true)"/Use basic:1 1216676033 ns 1213997000 ns 1 rows/sec=863.739k/s
BM_HashJoinBasic_TrivialResidualFilter/"Right Outer/Literal(true)"/Use basic:0 384570135 ns 383849500 ns 2 rows/sec=2.73174M/s
BM_HashJoinBasic_TrivialResidualFilter/"Right Outer/Literal(true)"/Use basic:1 1209476698 ns 1207006000 ns 1 rows/sec=868.741k/s
BM_HashJoinBasic_TrivialResidualFilter/"Full Outer/Literal(true)"/Use basic:0 388439529 ns 387529000 ns 2 rows/sec=2.7058M/s
BM_HashJoinBasic_TrivialResidualFilter/"Full Outer/Literal(true)"/Use basic:1 1227935150 ns 1224617000 ns 1 rows/sec=856.248k/s
BM_HashJoinBasic_TrivialResidualFilter/"Inner/Literal(false)"/Use basic:0 229299882 ns 228887000 ns 3 rows/sec=4.5812M/s
BM_HashJoinBasic_TrivialResidualFilter/"Inner/Literal(false)"/Use basic:1 1273364989 ns 1259394000 ns 1 rows/sec=832.604k/s
BM_HashJoinBasic_TrivialResidualFilter/"Left Semi/Literal(false)"/Use basic:0 86782869 ns 86548500 ns 8 rows/sec=12.1155M/s
BM_HashJoinBasic_TrivialResidualFilter/"Left Semi/Literal(false)"/Use basic:1 1127901070 ns 1116893000 ns 1 rows/sec=938.833k/s
BM_HashJoinBasic_TrivialResidualFilter/"Right Semi/Literal(false)"/Use basic:0 228116072 ns 225050000 ns 3 rows/sec=4.6593M/s
BM_HashJoinBasic_TrivialResidualFilter/"Right Semi/Literal(false)"/Use basic:1 1176053500 ns 1173668000 ns 1 rows/sec=893.418k/s
BM_HashJoinBasic_TrivialResidualFilter/"Left Anti/Literal(false)"/Use basic:0 103468668 ns 103186500 ns 6 rows/sec=10.1619M/s
BM_HashJoinBasic_TrivialResidualFilter/"Left Anti/Literal(false)"/Use basic:1 1122493432 ns 1119503000 ns 1 rows/sec=936.644k/s
BM_HashJoinBasic_TrivialResidualFilter/"Right Anti/Literal(false)"/Use basic:0 229369068 ns 229005667 ns 3 rows/sec=4.57882M/s
BM_HashJoinBasic_TrivialResidualFilter/"Right Anti/Literal(false)"/Use basic:1 1184838657 ns 1183118000 ns 1 rows/sec=886.282k/s
BM_HashJoinBasic_TrivialResidualFilter/"Left Outer/Literal(false)"/Use basic:0 259581813 ns 258940667 ns 3 rows/sec=4.04948M/s
BM_HashJoinBasic_TrivialResidualFilter/"Left Outer/Literal(false)"/Use basic:1 1268349788 ns 1265511000 ns 1 rows/sec=828.579k/s
BM_HashJoinBasic_TrivialResidualFilter/"Right Outer/Literal(false)"/Use basic:0 261173207 ns 260618333 ns 3 rows/sec=4.02342M/s
BM_HashJoinBasic_TrivialResidualFilter/"Right Outer/Literal(false)"/Use basic:1 1251746568 ns 1249713000 ns 1 rows/sec=839.053k/s
BM_HashJoinBasic_TrivialResidualFilter/"Full Outer/Literal(false)"/Use basic:0 282571779 ns 281992333 ns 3 rows/sec=3.71846M/s
BM_HashJoinBasic_TrivialResidualFilter/"Full Outer/Literal(false)"/Use basic:1 1310180950 ns 1307216000 ns 1 rows/sec=802.144k/s
```
For complex filter:
```
Run on (16 X 2400 MHz CPU s)
CPU Caches:
L1 Data 32 KiB
L1 Instruction 32 KiB
L2 Unified 256 KiB (x8)
L3 Unified 16384 KiB
Load Average: 1.72, 2.11, 2.38
-------------------------------------------------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
-------------------------------------------------------------------------------------------------------------------------------------------
BM_HashJoinBasic_ComplexResidualFilter/"Inner"/Use basic:0/Selectivity:0 285481761 ns 194634667 ns 3 rows/sec=5.38741M/s
BM_HashJoinBasic_ComplexResidualFilter/"Inner"/Use basic:1/Selectivity:0 587371852 ns 586985000 ns 1 rows/sec=1.78638M/s
BM_HashJoinBasic_ComplexResidualFilter/"Inner"/Use basic:0/Selectivity:20 183575289 ns 183389750 ns 4 rows/sec=5.71775M/s
BM_HashJoinBasic_ComplexResidualFilter/"Inner"/Use basic:1/Selectivity:20 532979599 ns 532643000 ns 1 rows/sec=1.96863M/s
BM_HashJoinBasic_ComplexResidualFilter/"Inner"/Use basic:0/Selectivity:40 176078460 ns 175985500 ns 4 rows/sec=5.95831M/s
BM_HashJoinBasic_ComplexResidualFilter/"Inner"/Use basic:1/Selectivity:40 511046166 ns 510599000 ns 1 rows/sec=2.05362M/s
BM_HashJoinBasic_ComplexResidualFilter/"Inner"/Use basic:0/Selectivity:60 176389467 ns 176314250 ns 4 rows/sec=5.9472M/s
BM_HashJoinBasic_ComplexResidualFilter/"Inner"/Use basic:1/Selectivity:60 528644770 ns 528332000 ns 1 rows/sec=1.98469M/s
BM_HashJoinBasic_ComplexResidualFilter/"Inner"/Use basic:0/Selectivity:80 183078951 ns 182949250 ns 4 rows/sec=5.73151M/s
BM_HashJoinBasic_ComplexResidualFilter/"Inner"/Use basic:1/Selectivity:80 532908186 ns 532584000 ns 1 rows/sec=1.96885M/s
BM_HashJoinBasic_ComplexResidualFilter/"Inner"/Use basic:0/Selectivity:100 184142812 ns 183996750 ns 4 rows/sec=5.69888M/s
BM_HashJoinBasic_ComplexResidualFilter/"Inner"/Use basic:1/Selectivity:100 532617027 ns 532321000 ns 1 rows/sec=1.96982M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Semi"/Use basic:0/Selectivity:0 188479785 ns 188310000 ns 3 rows/sec=5.56835M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Semi"/Use basic:1/Selectivity:0 534241536 ns 533837000 ns 1 rows/sec=1.96423M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Semi"/Use basic:0/Selectivity:20 179443772 ns 179317250 ns 4 rows/sec=5.8476M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Semi"/Use basic:1/Selectivity:20 522403702 ns 521697000 ns 1 rows/sec=2.00993M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Semi"/Use basic:0/Selectivity:40 176412223 ns 176280000 ns 4 rows/sec=5.94835M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Semi"/Use basic:1/Selectivity:40 527124676 ns 526709000 ns 1 rows/sec=1.99081M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Semi"/Use basic:0/Selectivity:60 177416077 ns 177299250 ns 4 rows/sec=5.91416M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Semi"/Use basic:1/Selectivity:60 530150134 ns 529786000 ns 1 rows/sec=1.97924M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Semi"/Use basic:0/Selectivity:80 177957742 ns 177785750 ns 4 rows/sec=5.89798M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Semi"/Use basic:1/Selectivity:80 545971256 ns 545724000 ns 1 rows/sec=1.92144M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Semi"/Use basic:0/Selectivity:100 179529899 ns 179404750 ns 4 rows/sec=5.84475M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Semi"/Use basic:1/Selectivity:100 518951980 ns 518568000 ns 1 rows/sec=2.02206M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Semi"/Use basic:0/Selectivity:0 184974336 ns 184872500 ns 4 rows/sec=5.67189M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Semi"/Use basic:1/Selectivity:0 522065103 ns 521769000 ns 1 rows/sec=2.00966M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Semi"/Use basic:0/Selectivity:20 179758309 ns 179583250 ns 4 rows/sec=5.83894M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Semi"/Use basic:1/Selectivity:20 526663280 ns 526209000 ns 1 rows/sec=1.9927M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Semi"/Use basic:0/Selectivity:40 180003493 ns 179896750 ns 4 rows/sec=5.82877M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Semi"/Use basic:1/Selectivity:40 534879948 ns 534417000 ns 1 rows/sec=1.96209M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Semi"/Use basic:0/Selectivity:60 180353825 ns 180226750 ns 4 rows/sec=5.81809M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Semi"/Use basic:1/Selectivity:60 541409091 ns 541002000 ns 1 rows/sec=1.93821M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Semi"/Use basic:0/Selectivity:80 183702215 ns 183532250 ns 4 rows/sec=5.71331M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Semi"/Use basic:1/Selectivity:80 526712733 ns 526192000 ns 1 rows/sec=1.99276M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Semi"/Use basic:0/Selectivity:100 180776824 ns 180456750 ns 4 rows/sec=5.81068M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Semi"/Use basic:1/Selectivity:100 518809284 ns 518548000 ns 1 rows/sec=2.02214M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Anti"/Use basic:0/Selectivity:0 196417916 ns 196242500 ns 4 rows/sec=5.34327M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Anti"/Use basic:1/Selectivity:0 531193590 ns 530667000 ns 1 rows/sec=1.97596M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Anti"/Use basic:0/Selectivity:20 176038193 ns 175937750 ns 4 rows/sec=5.95993M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Anti"/Use basic:1/Selectivity:20 521667365 ns 521384000 ns 1 rows/sec=2.01114M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Anti"/Use basic:0/Selectivity:40 176333421 ns 176244500 ns 4 rows/sec=5.94955M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Anti"/Use basic:1/Selectivity:40 520025232 ns 519592000 ns 1 rows/sec=2.01808M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Anti"/Use basic:0/Selectivity:60 184089512 ns 183949250 ns 4 rows/sec=5.70035M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Anti"/Use basic:1/Selectivity:60 531393536 ns 530291000 ns 1 rows/sec=1.97736M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Anti"/Use basic:0/Selectivity:80 180748829 ns 180365750 ns 4 rows/sec=5.81361M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Anti"/Use basic:1/Selectivity:80 528278354 ns 527309000 ns 1 rows/sec=1.98854M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Anti"/Use basic:0/Selectivity:100 178880600 ns 178628750 ns 4 rows/sec=5.87014M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Anti"/Use basic:1/Selectivity:100 528386902 ns 527277000 ns 1 rows/sec=1.98866M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Anti"/Use basic:0/Selectivity:0 189179963 ns 188718000 ns 4 rows/sec=5.55631M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Anti"/Use basic:1/Selectivity:0 523345927 ns 521986000 ns 1 rows/sec=2.00882M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Anti"/Use basic:0/Selectivity:20 180175063 ns 179780500 ns 4 rows/sec=5.83253M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Anti"/Use basic:1/Selectivity:20 531323506 ns 529992000 ns 1 rows/sec=1.97848M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Anti"/Use basic:0/Selectivity:40 180772606 ns 180394500 ns 4 rows/sec=5.81268M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Anti"/Use basic:1/Selectivity:40 531202038 ns 529978000 ns 1 rows/sec=1.97853M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Anti"/Use basic:0/Selectivity:60 189492603 ns 188326500 ns 4 rows/sec=5.56786M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Anti"/Use basic:1/Selectivity:60 526946246 ns 525795000 ns 1 rows/sec=1.99427M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Anti"/Use basic:0/Selectivity:80 182752845 ns 182347250 ns 4 rows/sec=5.75043M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Anti"/Use basic:1/Selectivity:80 536875460 ns 535497000 ns 1 rows/sec=1.95814M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Anti"/Use basic:0/Selectivity:100 180583913 ns 180121500 ns 4 rows/sec=5.82149M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Anti"/Use basic:1/Selectivity:100 526710394 ns 525293000 ns 1 rows/sec=1.99617M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Outer"/Use basic:0/Selectivity:0 198828306 ns 198465333 ns 3 rows/sec=5.28342M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Outer"/Use basic:1/Selectivity:0 534091873 ns 532720000 ns 1 rows/sec=1.96834M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Outer"/Use basic:0/Selectivity:20 180753539 ns 180452000 ns 4 rows/sec=5.81083M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Outer"/Use basic:1/Selectivity:20 528223043 ns 527199000 ns 1 rows/sec=1.98896M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Outer"/Use basic:0/Selectivity:40 180587603 ns 180228000 ns 4 rows/sec=5.81805M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Outer"/Use basic:1/Selectivity:40 520293827 ns 519533000 ns 1 rows/sec=2.0183M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Outer"/Use basic:0/Selectivity:60 181042479 ns 180625750 ns 4 rows/sec=5.80524M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Outer"/Use basic:1/Selectivity:60 528534807 ns 527300000 ns 1 rows/sec=1.98858M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Outer"/Use basic:0/Selectivity:80 180509562 ns 180041000 ns 4 rows/sec=5.8241M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Outer"/Use basic:1/Selectivity:80 523689658 ns 522577000 ns 1 rows/sec=2.00655M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Outer"/Use basic:0/Selectivity:100 177740579 ns 177503500 ns 4 rows/sec=5.90735M/s
BM_HashJoinBasic_ComplexResidualFilter/"Left Outer"/Use basic:1/Selectivity:100 517799671 ns 517075000 ns 1 rows/sec=2.0279M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Outer"/Use basic:0/Selectivity:0 185748211 ns 185512250 ns 4 rows/sec=5.65233M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Outer"/Use basic:1/Selectivity:0 518887193 ns 517433000 ns 1 rows/sec=2.0265M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Outer"/Use basic:0/Selectivity:20 181622174 ns 181051250 ns 4 rows/sec=5.7916M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Outer"/Use basic:1/Selectivity:20 528306442 ns 527185000 ns 1 rows/sec=1.98901M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Outer"/Use basic:0/Selectivity:40 181670535 ns 181396000 ns 4 rows/sec=5.78059M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Outer"/Use basic:1/Selectivity:40 539240701 ns 537955000 ns 1 rows/sec=1.94919M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Outer"/Use basic:0/Selectivity:60 183705218 ns 183282250 ns 4 rows/sec=5.7211M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Outer"/Use basic:1/Selectivity:60 523264368 ns 521991000 ns 1 rows/sec=2.0088M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Outer"/Use basic:0/Selectivity:80 181231948 ns 180949500 ns 4 rows/sec=5.79485M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Outer"/Use basic:1/Selectivity:80 525961671 ns 524683000 ns 1 rows/sec=1.99849M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Outer"/Use basic:0/Selectivity:100 181300762 ns 181023000 ns 4 rows/sec=5.7925M/s
BM_HashJoinBasic_ComplexResidualFilter/"Right Outer"/Use basic:1/Selectivity:100 530786659 ns 530005000 ns 1 rows/sec=1.97843M/s
BM_HashJoinBasic_ComplexResidualFilter/"Full Outer"/Use basic:0/Selectivity:0 197223385 ns 196858500 ns 4 rows/sec=5.32655M/s
BM_HashJoinBasic_ComplexResidualFilter/"Full Outer"/Use basic:1/Selectivity:0 537305470 ns 536085000 ns 1 rows/sec=1.95599M/s
BM_HashJoinBasic_ComplexResidualFilter/"Full Outer"/Use basic:0/Selectivity:20 184264879 ns 183699750 ns 4 rows/sec=5.7081M/s
BM_HashJoinBasic_ComplexResidualFilter/"Full Outer"/Use basic:1/Selectivity:20 527866244 ns 526748000 ns 1 rows/sec=1.99066M/s
BM_HashJoinBasic_ComplexResidualFilter/"Full Outer"/Use basic:0/Selectivity:40 183477990 ns 183063250 ns 4 rows/sec=5.72794M/s
BM_HashJoinBasic_ComplexResidualFilter/"Full Outer"/Use basic:1/Selectivity:40 527162775 ns 526133000 ns 1 rows/sec=1.99299M/s
BM_HashJoinBasic_ComplexResidualFilter/"Full Outer"/Use basic:0/Selectivity:60 181614194 ns 181277500 ns 4 rows/sec=5.78437M/s
BM_HashJoinBasic_ComplexResidualFilter/"Full Outer"/Use basic:1/Selectivity:60 537843969 ns 536471000 ns 1 rows/sec=1.95458M/s
BM_HashJoinBasic_ComplexResidualFilter/"Full Outer"/Use basic:0/Selectivity:80 180134602 ns 179915750 ns 4 rows/sec=5.82815M/s
BM_HashJoinBasic_ComplexResidualFilter/"Full Outer"/Use basic:1/Selectivity:80 533530920 ns 532607000 ns 1 rows/sec=1.96876M/s
BM_HashJoinBasic_ComplexResidualFilter/"Full Outer"/Use basic:0/Selectivity:100 178655444 ns 178387250 ns 4 rows/sec=5.87809M/s
BM_HashJoinBasic_ComplexResidualFilter/"Full Outer"/Use basic:1/Selectivity:100 544650946 ns 542873000 ns 1 rows/sec=1.93153M/s
```
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1462862280
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1893,58 +1893,146 @@ TEST(HashJoin, CheckHashJoinNodeOptionsValidation) {
}
}
-TEST(HashJoin, ResidualFilter) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
-
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [1, 6, "alpha"],
- [2, 5, "beta"],
- [3, 4, "alpha"]
- ])")};
- input_left.schema =
- schema({field("l1", int32()), field("l2", int32()), field("l_str", utf8())});
-
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [5, 11, "alpha"],
- [2, 12, "beta"],
- [4, 16, "alpha"]
- ])")};
- input_right.schema =
- schema({field("r1", int32()), field("r2", int32()), field("r_str", utf8())});
+class ResidualFilterCaseRunner {
+ public:
+ ResidualFilterCaseRunner(BatchesWithSchema left_input, BatchesWithSchema right_input)
+ : left_input_(std::move(left_input)), right_input_(std::move(right_input)) {}
+
+ void Run(JoinType join_type, const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(filter)},
+ expected);
+ }
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
+ const std::vector<FieldRef> right_keys, std::vector<FieldRef> left_output,
+ const std::vector<FieldRef> right_output, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(left_output),
+ std::move(right_output), std::move(filter)},
+ expected);
+ }
+
+ private:
+ void RunInternal(const HashJoinNodeOptions& options,
+ const std::vector<ExecBatch>& expected) const {
+ auto join_type_str = JoinTypeString(options.join_type);
+ auto join_cond_str =
+ JoinConditionString(options.left_keys, options.right_keys, options.filter);
+ auto output_str = OutputString(options.left_output, options.right_output);
+ for (bool parallel : {false, true}) {
+ auto parallel_str = parallel ? "parallel" : "serial";
+ SCOPED_TRACE(join_type_str + " " + join_cond_str + " " + output_str + " " +
+ parallel_str);
- Declaration left{
- "source",
- SourceNodeOptions{input_left.schema, input_left.gen(parallel, /*slow=*/false)}};
- Declaration right{
- "source",
- SourceNodeOptions{input_right.schema, input_right.gen(parallel, /*slow=*/false)}};
+ Declaration left{"source",
+ SourceNodeOptions{left_input_.schema,
+ left_input_.gen(parallel, /*slow=*/false)}};
+ Declaration right{"source",
+ SourceNodeOptions{right_input_.schema,
+ right_input_.gen(parallel, /*slow=*/false)}};
- Expression mul = call("multiply", {field_ref("l1"), field_ref("l2")});
- Expression combination = call("add", {mul, field_ref("r1")});
- Expression residual_filter = less_equal(combination, field_ref("r2"));
+ Declaration join{"hashjoin", {std::move(left), std::move(right)}, options};
- HashJoinNodeOptions join_opts{
- JoinType::FULL_OUTER,
- /*left_keys=*/{"l_str"},
- /*right_keys=*/{"r_str"}, std::move(residual_filter), "l_", "r_"};
+ ASSERT_OK_AND_ASSIGN(auto result,
+ DeclarationToExecBatches(std::move(join), parallel));
+ AssertExecBatchesEqualIgnoringOrder(result.schema, expected, result.batches);
+ }
+ }
- Declaration join{"hashjoin", {std::move(left), std::move(right)}, join_opts};
+ private:
+ BatchesWithSchema left_input_;
+ BatchesWithSchema right_input_;
- ASSERT_OK_AND_ASSIGN(auto result,
- DeclarationToExecBatches(std::move(join), parallel));
+ private:
+ static std::string JoinTypeString(JoinType t) {
+ switch (t) {
+ case JoinType::LEFT_SEMI:
+ return "LEFT_SEMI";
+ case JoinType::RIGHT_SEMI:
+ return "RIGHT_SEMI";
+ case JoinType::LEFT_ANTI:
+ return "LEFT_ANTI";
+ case JoinType::RIGHT_ANTI:
+ return "RIGHT_ANTI";
+ case JoinType::INNER:
+ return "INNER";
+ case JoinType::LEFT_OUTER:
+ return "LEFT_OUTER";
+ case JoinType::RIGHT_OUTER:
+ return "RIGHT_OUTER";
+ case JoinType::FULL_OUTER:
+ return "FULL_OUTER";
+ }
+ ARROW_DCHECK(false);
+ return "";
+ }
+
+ static std::string JoinConditionString(const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys,
+ const Expression& filter) {
+ ARROW_DCHECK(left_keys.size() > 0);
+ ARROW_DCHECK(left_keys.size() == right_keys.size());
+ std::stringstream ss;
+ ss << "on (";
+ for (size_t i = 0; i < left_keys.size(); ++i) {
+ ss << left_keys[i].ToString() << " = " << right_keys[i].ToString() << " and ";
+ }
+ ss << filter.ToString();
+ ss << ")";
+ return ss.str();
+ }
+
+ static std::string OutputString(const std::vector<FieldRef>& left_output,
Review Comment:
I'm thinking maybe we can make obtaining join type string and output string generic in the scope of this test file. So both `HashJoin.Random` and this one can leverage it. How does that sound?
--
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] GH-20339: [C++] Add residual predicate support to swiss join [arrow]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1879783732
:warning: GitHub issue #20339 **has been automatically assigned in GitHub** to PR creator.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "vibhatha (via GitHub)" <gi...@apache.org>.
vibhatha commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1882495884
@zanmato1984 I will completely review once the test cases are there.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on PR #39487:
URL: https://github.com/apache/arrow/pull/39487#issuecomment-1966192609
Hi @westonpace , would you kindly help on reviewing this? Appreciate it!
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1506190316
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1959,47 +2047,993 @@ TEST(HashJoin, TrivialResidualFilter) {
std::vector<std::string> expected_strings = {expected_true, expected_false};
std::vector<Expression> filters = {always_true, always_false};
+ BatchesWithSchema input_left;
+ input_left.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
+ [1, "alpha"]])")};
+ input_left.schema = schema({field("l1", int32()), field("l_str", utf8())});
+
+ BatchesWithSchema input_right;
+ input_right.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
+ [1, "alpha"]])")};
+ input_right.schema = schema({field("r1", int32()), field("r_str", utf8())});
+
+ ResidualFilterCaseRunner runner{std::move(input_left), std::move(input_right)};
+
for (size_t test_id = 0; test_id < 2; test_id++) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
+ runner.Run(JoinType::INNER, {"l_str"}, {"r_str"}, filters[test_id],
+ {ExecBatchFromJSON({int32(), utf8(), int32(), utf8()},
+ expected_strings[test_id])});
+ }
+}
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
- [1, "alpha"]
- ])")};
- input_left.schema = schema({field("l1", int32()), field("l_str", utf8())});
+TEST(HashJoin, FineGrainedResidualFilter) {
+ struct JoinSchema {
+ std::shared_ptr<Schema> left, right;
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), utf8()}, R"([
- [1, "alpha"]
- ])")};
- input_right.schema = schema({field("r1", int32()), field("r_str", utf8())});
+ struct Projector {
+ std::shared_ptr<Schema> left, right;
+ std::vector<int> left_output, right_output;
- auto exec_ctx = std::make_unique<ExecContext>(
- default_memory_pool(),
- parallel ? arrow::internal::GetCpuThreadPool() : nullptr);
+ std::vector<FieldRef> LeftOutput(JoinType join_type) const {
+ if (join_type == JoinType::RIGHT_SEMI || join_type == JoinType::RIGHT_ANTI) {
+ return {};
+ }
+ std::vector<FieldRef> output(left_output.size());
+ std::transform(left_output.begin(), left_output.end(), output.begin(),
+ [](int i) { return i; });
+ return output;
+ }
- Declaration left{
- "source",
- SourceNodeOptions{input_left.schema, input_left.gen(parallel, /*slow=*/false)}};
- Declaration right{"source",
- SourceNodeOptions{input_right.schema,
- input_right.gen(parallel, /*slow=*/false)}};
+ std::vector<FieldRef> RightOutput(JoinType join_type) const {
+ if (join_type == JoinType::LEFT_SEMI || join_type == JoinType::LEFT_ANTI) {
+ return {};
+ }
+ std::vector<FieldRef> output(right_output.size());
+ std::transform(right_output.begin(), right_output.end(), output.begin(),
+ [](int i) { return i; });
+ return output;
+ }
- HashJoinNodeOptions join_opts{
- JoinType::INNER,
- /*left_keys=*/{"l_str"},
- /*right_keys=*/{"r_str"}, filters[test_id], "l_", "r_"};
+ ExecBatch Project(JoinType join_type, const ExecBatch& batch) const {
+ std::vector<Datum> values;
+ if (join_type != JoinType::RIGHT_SEMI && join_type != JoinType::RIGHT_ANTI) {
+ for (int i : left_output) {
+ values.push_back(batch[i]);
+ }
+ }
+ if (join_type != JoinType::LEFT_SEMI && join_type != JoinType::LEFT_ANTI) {
+ int left_size =
+ join_type == JoinType::RIGHT_SEMI || join_type == JoinType::RIGHT_ANTI
+ ? 0
+ : left->num_fields();
+ for (int i : right_output) {
+ values.push_back(batch[left_size + i]);
+ }
+ }
+ return {std::move(values), batch.length};
+ }
+ };
- Declaration join{"hashjoin", {std::move(left), std::move(right)}, join_opts};
+ Projector GetProjector(std::vector<int> left_output, std::vector<int> right_output) {
+ return Projector{left, right, std::move(left_output), std::move(right_output)};
+ }
+ };
+
+ BatchesWithSchema left;
+ left.batches = {ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["left_only", null, "payload"],
+ ["left_only", 0, "payload"],
+ ["left_only", 42, "payload"],
+ ["both1", null, "payload"],
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", null, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"]])")};
+ left.schema = schema(
+ {field("l_key", utf8()), field("l_filter", int32()), field("l_payload", utf8())});
+
+ BatchesWithSchema right;
+ right.batches = {ExecBatchFromJSON({utf8(), int32(), utf8()}, R"([
+ [null, null, "payload"],
+ [null, 0, "payload"],
+ [null, 42, "payload"],
+ ["both1", null, "payload"],
+ ["both1", 0, "payload"],
+ ["both1", 42, "payload"],
+ ["both2", null, "payload"],
+ ["both2", 0, "payload"],
+ ["both2", 42, "payload"],
+ ["right_only", null, "payload"],
+ ["right_only", 0, "payload"],
+ ["right_only", 42, "payload"]])")};
Review Comment:
Good catch. Will do.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "vibhatha (via GitHub)" <gi...@apache.org>.
vibhatha commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1462834619
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1893,58 +1893,146 @@ TEST(HashJoin, CheckHashJoinNodeOptionsValidation) {
}
}
-TEST(HashJoin, ResidualFilter) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
-
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [1, 6, "alpha"],
- [2, 5, "beta"],
- [3, 4, "alpha"]
- ])")};
- input_left.schema =
- schema({field("l1", int32()), field("l2", int32()), field("l_str", utf8())});
-
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [5, 11, "alpha"],
- [2, 12, "beta"],
- [4, 16, "alpha"]
- ])")};
- input_right.schema =
- schema({field("r1", int32()), field("r2", int32()), field("r_str", utf8())});
+class ResidualFilterCaseRunner {
+ public:
+ ResidualFilterCaseRunner(BatchesWithSchema left_input, BatchesWithSchema right_input)
+ : left_input_(std::move(left_input)), right_input_(std::move(right_input)) {}
+
+ void Run(JoinType join_type, const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(filter)},
+ expected);
+ }
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
+ const std::vector<FieldRef> right_keys, std::vector<FieldRef> left_output,
+ const std::vector<FieldRef> right_output, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(left_output),
+ std::move(right_output), std::move(filter)},
+ expected);
+ }
+
+ private:
+ void RunInternal(const HashJoinNodeOptions& options,
+ const std::vector<ExecBatch>& expected) const {
+ auto join_type_str = JoinTypeString(options.join_type);
+ auto join_cond_str =
+ JoinConditionString(options.left_keys, options.right_keys, options.filter);
+ auto output_str = OutputString(options.left_output, options.right_output);
+ for (bool parallel : {false, true}) {
+ auto parallel_str = parallel ? "parallel" : "serial";
+ SCOPED_TRACE(join_type_str + " " + join_cond_str + " " + output_str + " " +
+ parallel_str);
- Declaration left{
- "source",
- SourceNodeOptions{input_left.schema, input_left.gen(parallel, /*slow=*/false)}};
- Declaration right{
- "source",
- SourceNodeOptions{input_right.schema, input_right.gen(parallel, /*slow=*/false)}};
+ Declaration left{"source",
+ SourceNodeOptions{left_input_.schema,
+ left_input_.gen(parallel, /*slow=*/false)}};
+ Declaration right{"source",
+ SourceNodeOptions{right_input_.schema,
+ right_input_.gen(parallel, /*slow=*/false)}};
- Expression mul = call("multiply", {field_ref("l1"), field_ref("l2")});
- Expression combination = call("add", {mul, field_ref("r1")});
- Expression residual_filter = less_equal(combination, field_ref("r2"));
+ Declaration join{"hashjoin", {std::move(left), std::move(right)}, options};
- HashJoinNodeOptions join_opts{
- JoinType::FULL_OUTER,
- /*left_keys=*/{"l_str"},
- /*right_keys=*/{"r_str"}, std::move(residual_filter), "l_", "r_"};
+ ASSERT_OK_AND_ASSIGN(auto result,
+ DeclarationToExecBatches(std::move(join), parallel));
+ AssertExecBatchesEqualIgnoringOrder(result.schema, expected, result.batches);
+ }
+ }
- Declaration join{"hashjoin", {std::move(left), std::move(right)}, join_opts};
+ private:
+ BatchesWithSchema left_input_;
+ BatchesWithSchema right_input_;
- ASSERT_OK_AND_ASSIGN(auto result,
- DeclarationToExecBatches(std::move(join), parallel));
+ private:
+ static std::string JoinTypeString(JoinType t) {
+ switch (t) {
+ case JoinType::LEFT_SEMI:
+ return "LEFT_SEMI";
+ case JoinType::RIGHT_SEMI:
+ return "RIGHT_SEMI";
+ case JoinType::LEFT_ANTI:
+ return "LEFT_ANTI";
+ case JoinType::RIGHT_ANTI:
+ return "RIGHT_ANTI";
+ case JoinType::INNER:
+ return "INNER";
+ case JoinType::LEFT_OUTER:
+ return "LEFT_OUTER";
+ case JoinType::RIGHT_OUTER:
+ return "RIGHT_OUTER";
+ case JoinType::FULL_OUTER:
+ return "FULL_OUTER";
+ }
+ ARROW_DCHECK(false);
+ return "";
+ }
+
+ static std::string JoinConditionString(const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys,
+ const Expression& filter) {
+ ARROW_DCHECK(left_keys.size() > 0);
+ ARROW_DCHECK(left_keys.size() == right_keys.size());
+ std::stringstream ss;
+ ss << "on (";
+ for (size_t i = 0; i < left_keys.size(); ++i) {
+ ss << left_keys[i].ToString() << " = " << right_keys[i].ToString() << " and ";
+ }
+ ss << filter.ToString();
+ ss << ")";
+ return ss.str();
+ }
+
+ static std::string OutputString(const std::vector<FieldRef>& left_output,
Review Comment:
Just a thought, can this be a util for all joins? Not necessarily required to make things generic in this PR.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "vibhatha (via GitHub)" <gi...@apache.org>.
vibhatha commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1462867828
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1893,58 +1893,146 @@ TEST(HashJoin, CheckHashJoinNodeOptionsValidation) {
}
}
-TEST(HashJoin, ResidualFilter) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
-
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [1, 6, "alpha"],
- [2, 5, "beta"],
- [3, 4, "alpha"]
- ])")};
- input_left.schema =
- schema({field("l1", int32()), field("l2", int32()), field("l_str", utf8())});
-
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [5, 11, "alpha"],
- [2, 12, "beta"],
- [4, 16, "alpha"]
- ])")};
- input_right.schema =
- schema({field("r1", int32()), field("r2", int32()), field("r_str", utf8())});
+class ResidualFilterCaseRunner {
+ public:
+ ResidualFilterCaseRunner(BatchesWithSchema left_input, BatchesWithSchema right_input)
+ : left_input_(std::move(left_input)), right_input_(std::move(right_input)) {}
+
+ void Run(JoinType join_type, const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(filter)},
+ expected);
+ }
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
+ const std::vector<FieldRef> right_keys, std::vector<FieldRef> left_output,
+ const std::vector<FieldRef> right_output, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(left_output),
+ std::move(right_output), std::move(filter)},
+ expected);
+ }
+
+ private:
+ void RunInternal(const HashJoinNodeOptions& options,
+ const std::vector<ExecBatch>& expected) const {
+ auto join_type_str = JoinTypeString(options.join_type);
+ auto join_cond_str =
+ JoinConditionString(options.left_keys, options.right_keys, options.filter);
+ auto output_str = OutputString(options.left_output, options.right_output);
+ for (bool parallel : {false, true}) {
+ auto parallel_str = parallel ? "parallel" : "serial";
+ SCOPED_TRACE(join_type_str + " " + join_cond_str + " " + output_str + " " +
+ parallel_str);
- Declaration left{
- "source",
- SourceNodeOptions{input_left.schema, input_left.gen(parallel, /*slow=*/false)}};
- Declaration right{
- "source",
- SourceNodeOptions{input_right.schema, input_right.gen(parallel, /*slow=*/false)}};
+ Declaration left{"source",
+ SourceNodeOptions{left_input_.schema,
+ left_input_.gen(parallel, /*slow=*/false)}};
+ Declaration right{"source",
+ SourceNodeOptions{right_input_.schema,
+ right_input_.gen(parallel, /*slow=*/false)}};
- Expression mul = call("multiply", {field_ref("l1"), field_ref("l2")});
- Expression combination = call("add", {mul, field_ref("r1")});
- Expression residual_filter = less_equal(combination, field_ref("r2"));
+ Declaration join{"hashjoin", {std::move(left), std::move(right)}, options};
- HashJoinNodeOptions join_opts{
- JoinType::FULL_OUTER,
- /*left_keys=*/{"l_str"},
- /*right_keys=*/{"r_str"}, std::move(residual_filter), "l_", "r_"};
+ ASSERT_OK_AND_ASSIGN(auto result,
+ DeclarationToExecBatches(std::move(join), parallel));
+ AssertExecBatchesEqualIgnoringOrder(result.schema, expected, result.batches);
+ }
+ }
- Declaration join{"hashjoin", {std::move(left), std::move(right)}, join_opts};
+ private:
+ BatchesWithSchema left_input_;
+ BatchesWithSchema right_input_;
- ASSERT_OK_AND_ASSIGN(auto result,
- DeclarationToExecBatches(std::move(join), parallel));
+ private:
+ static std::string JoinTypeString(JoinType t) {
+ switch (t) {
+ case JoinType::LEFT_SEMI:
+ return "LEFT_SEMI";
+ case JoinType::RIGHT_SEMI:
+ return "RIGHT_SEMI";
+ case JoinType::LEFT_ANTI:
+ return "LEFT_ANTI";
+ case JoinType::RIGHT_ANTI:
+ return "RIGHT_ANTI";
+ case JoinType::INNER:
+ return "INNER";
+ case JoinType::LEFT_OUTER:
+ return "LEFT_OUTER";
+ case JoinType::RIGHT_OUTER:
+ return "RIGHT_OUTER";
+ case JoinType::FULL_OUTER:
+ return "FULL_OUTER";
+ }
+ ARROW_DCHECK(false);
+ return "";
+ }
+
+ static std::string JoinConditionString(const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys,
+ const Expression& filter) {
+ ARROW_DCHECK(left_keys.size() > 0);
+ ARROW_DCHECK(left_keys.size() == right_keys.size());
+ std::stringstream ss;
+ ss << "on (";
+ for (size_t i = 0; i < left_keys.size(); ++i) {
+ ss << left_keys[i].ToString() << " = " << right_keys[i].ToString() << " and ";
+ }
+ ss << filter.ToString();
+ ss << ")";
+ return ss.str();
+ }
+
+ static std::string OutputString(const std::vector<FieldRef>& left_output,
Review Comment:
That sounds good, but if it requires too much modification to other test cases in other classes, we can do it in a follow up PR.
--
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] GH-20339: [C++] Add residual filter support to swiss join [arrow]
Posted by "zanmato1984 (via GitHub)" <gi...@apache.org>.
zanmato1984 commented on code in PR #39487:
URL: https://github.com/apache/arrow/pull/39487#discussion_r1462860750
##########
cpp/src/arrow/acero/hash_join_node_test.cc:
##########
@@ -1893,58 +1893,146 @@ TEST(HashJoin, CheckHashJoinNodeOptionsValidation) {
}
}
-TEST(HashJoin, ResidualFilter) {
- for (bool parallel : {false, true}) {
- SCOPED_TRACE(parallel ? "parallel/merged" : "serial");
-
- BatchesWithSchema input_left;
- input_left.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [1, 6, "alpha"],
- [2, 5, "beta"],
- [3, 4, "alpha"]
- ])")};
- input_left.schema =
- schema({field("l1", int32()), field("l2", int32()), field("l_str", utf8())});
-
- BatchesWithSchema input_right;
- input_right.batches = {ExecBatchFromJSON({int32(), int32(), utf8()}, R"([
- [5, 11, "alpha"],
- [2, 12, "beta"],
- [4, 16, "alpha"]
- ])")};
- input_right.schema =
- schema({field("r1", int32()), field("r2", int32()), field("r_str", utf8())});
+class ResidualFilterCaseRunner {
+ public:
+ ResidualFilterCaseRunner(BatchesWithSchema left_input, BatchesWithSchema right_input)
+ : left_input_(std::move(left_input)), right_input_(std::move(right_input)) {}
+
+ void Run(JoinType join_type, const std::vector<FieldRef>& left_keys,
+ const std::vector<FieldRef>& right_keys, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(filter)},
+ expected);
+ }
+
+ void Run(JoinType join_type, std::vector<FieldRef> left_keys,
+ const std::vector<FieldRef> right_keys, std::vector<FieldRef> left_output,
+ const std::vector<FieldRef> right_output, Expression filter,
+ const std::vector<ExecBatch>& expected) const {
+ RunInternal(HashJoinNodeOptions{join_type, std::move(left_keys),
+ std::move(right_keys), std::move(left_output),
+ std::move(right_output), std::move(filter)},
+ expected);
+ }
+
+ private:
+ void RunInternal(const HashJoinNodeOptions& options,
+ const std::vector<ExecBatch>& expected) const {
+ auto join_type_str = JoinTypeString(options.join_type);
Review Comment:
Good hint. Replied together in the following comment.
--
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