You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "alamb (via GitHub)" <gi...@apache.org> on 2023/10/27 15:47:05 UTC
[PR] Minor: Improve `HashJoinExec` documentation [arrow-datafusion]
alamb opened a new pull request, #7953:
URL: https://github.com/apache/arrow-datafusion/pull/7953
## Which issue does this PR close?
Related to https://github.com/apache/arrow-datafusion/issues/7949
## Rationale for this change
To explain https://github.com/apache/arrow-datafusion/issues/7949 I needed to explain the background of how HashJoinExec works, and so I wanted to encode that information into the documentation
## What changes are included in this PR?
Improved documentation. For example:
## 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)?
-->
N/A
## Are there any user-facing changes?
Better `HashJoinExec` documentation.
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please add the `api change` label.
-->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Minor: Improve `HashJoinExec` documentation [arrow-datafusion]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7953:
URL: https://github.com/apache/arrow-datafusion/pull/7953#discussion_r1374906259
##########
datafusion/physical-plan/src/joins/hash_join.rs:
##########
@@ -78,29 +77,140 @@ use futures::{ready, Stream, StreamExt, TryStreamExt};
type JoinLeftData = (JoinHashMap, RecordBatch, MemoryReservation);
-/// Join execution plan executes partitions in parallel and combines them into a set of
-/// partitions.
+/// Join execution plan: Evaluates eqijoin predicates in parallel on multiple
+/// partitions using a hash table and an optional filter list to apply post
+/// join.
///
-/// Filter expression expected to contain non-equality predicates that can not be pushed
-/// down to any of join inputs.
-/// In case of outer join, filter applied to only matched rows.
+/// # Join Expressions
+///
+/// This implementation is optimized for evaluating eqijoin predicates (
+/// `<col1> = <col2>`) expressions, which are represented as a list of `Columns`
+/// in [`Self::on`].
+///
+/// Non-equality predicates, which can not pushed down to a join inputs (e.g.
+/// `<col1> != <col2>`) are known as "filter expressions" and are evaluated
+/// after the equijoin predicates.
+///
+/// # "Build Side" vs "Probe Side"
+///
+/// HashJoin takes two inputs, which are referred to as the "build" and the
+/// "probe". The build side is the first child, and the probe side is the second
+/// child.
+///
+/// The two inputs are treated differently and it is VERY important that the
+/// *smaller* input is placed on the build side to minimize the work of creating
+/// the hash table.
+///
+/// ```text
+/// ┌───────────┐
+/// │ HashJoin │
+/// │ │
+/// └───────────┘
+/// │ │
+/// ┌─────┘ └─────┐
+/// ▼ ▼
+/// ┌────────────┐ ┌─────────────┐
+/// │ Input │ │ Input │
+/// │ [0] │ │ [1] │
+/// └────────────┘ └─────────────┘
+///
+/// "build side" "probe side"
+/// ```
+///
+/// Execution proceeds in 2 stages:
+///
+/// 1. the **build phase** where a hash table is created from the tuples of the
+/// build side.
+///
+/// 2. the **probe phase** where the tuples of the probe side are streamed
+/// through, checking for matches of the join keys in the hash table.
+///
+/// ```text
+/// ┌────────────────┐ ┌────────────────┐
+/// │ ┌─────────┐ │ │ ┌─────────┐ │
+/// │ │ Hash │ │ │ │ Hash │ │
+/// │ │ Table │ │ │ │ Table │ │
+/// │ │(keys are│ │ │ │(keys are│ │
+/// │ │equi join│ │ │ │equi join│ │ Stage 2: batches from
+/// Stage 1: the │ │columns) │ │ │ │columns) │ │ the probe side are
+/// *entire* build │ │ │ │ │ │ │ │ streamed through, and
+/// side is read │ └─────────┘ │ │ └─────────┘ │ checked against the
+/// into the hash │ ▲ │ │ ▲ │ contents of the hash
+/// table │ HashJoin │ │ HashJoin │ table
+/// └──────┼─────────┘ └──────────┼─────┘
+/// ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
+/// │ │
+///
+/// │ │
+/// ┌────────────┐ ┌────────────┐
+/// │RecordBatch │ │RecordBatch │
+/// └────────────┘ └────────────┘
+/// ┌────────────┐ ┌────────────┐
+/// │RecordBatch │ │RecordBatch │
+/// └────────────┘ └────────────┘
+/// ... ...
+/// ┌────────────┐ ┌────────────┐
+/// │RecordBatch │ │RecordBatch │
+/// └────────────┘ └────────────┘
+///
+/// build side probe side
+///
+/// ```
+///
+/// # Exampe "Optimial" Plans
+///
+/// The differences in the inputs means that for classic "Star Schema Query",
Review Comment:
```suggestion
/// The differences in the inputs means that for classic "Star Schema Query",
```
--
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] Minor: Improve `HashJoinExec` documentation [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #7953:
URL: https://github.com/apache/arrow-datafusion/pull/7953
--
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] Minor: Improve `HashJoinExec` documentation [arrow-datafusion]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7953:
URL: https://github.com/apache/arrow-datafusion/pull/7953#discussion_r1374907638
##########
datafusion/physical-plan/src/joins/hash_join.rs:
##########
@@ -78,29 +77,140 @@ use futures::{ready, Stream, StreamExt, TryStreamExt};
type JoinLeftData = (JoinHashMap, RecordBatch, MemoryReservation);
-/// Join execution plan executes partitions in parallel and combines them into a set of
-/// partitions.
+/// Join execution plan: Evaluates eqijoin predicates in parallel on multiple
+/// partitions using a hash table and an optional filter list to apply post
+/// join.
///
-/// Filter expression expected to contain non-equality predicates that can not be pushed
-/// down to any of join inputs.
-/// In case of outer join, filter applied to only matched rows.
+/// # Join Expressions
+///
+/// This implementation is optimized for evaluating eqijoin predicates (
+/// `<col1> = <col2>`) expressions, which are represented as a list of `Columns`
+/// in [`Self::on`].
+///
+/// Non-equality predicates, which can not pushed down to a join inputs (e.g.
+/// `<col1> != <col2>`) are known as "filter expressions" and are evaluated
+/// after the equijoin predicates.
+///
+/// # "Build Side" vs "Probe Side"
+///
+/// HashJoin takes two inputs, which are referred to as the "build" and the
+/// "probe". The build side is the first child, and the probe side is the second
+/// child.
+///
+/// The two inputs are treated differently and it is VERY important that the
+/// *smaller* input is placed on the build side to minimize the work of creating
+/// the hash table.
+///
+/// ```text
+/// ┌───────────┐
+/// │ HashJoin │
+/// │ │
+/// └───────────┘
+/// │ │
+/// ┌─────┘ └─────┐
+/// ▼ ▼
+/// ┌────────────┐ ┌─────────────┐
+/// │ Input │ │ Input │
+/// │ [0] │ │ [1] │
+/// └────────────┘ └─────────────┘
+///
+/// "build side" "probe side"
+/// ```
+///
+/// Execution proceeds in 2 stages:
+///
+/// 1. the **build phase** where a hash table is created from the tuples of the
+/// build side.
+///
+/// 2. the **probe phase** where the tuples of the probe side are streamed
+/// through, checking for matches of the join keys in the hash table.
+///
+/// ```text
+/// ┌────────────────┐ ┌────────────────┐
+/// │ ┌─────────┐ │ │ ┌─────────┐ │
+/// │ │ Hash │ │ │ │ Hash │ │
+/// │ │ Table │ │ │ │ Table │ │
+/// │ │(keys are│ │ │ │(keys are│ │
+/// │ │equi join│ │ │ │equi join│ │ Stage 2: batches from
+/// Stage 1: the │ │columns) │ │ │ │columns) │ │ the probe side are
+/// *entire* build │ │ │ │ │ │ │ │ streamed through, and
+/// side is read │ └─────────┘ │ │ └─────────┘ │ checked against the
+/// into the hash │ ▲ │ │ ▲ │ contents of the hash
+/// table │ HashJoin │ │ HashJoin │ table
+/// └──────┼─────────┘ └──────────┼─────┘
+/// ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
+/// │ │
+///
+/// │ │
+/// ┌────────────┐ ┌────────────┐
+/// │RecordBatch │ │RecordBatch │
+/// └────────────┘ └────────────┘
+/// ┌────────────┐ ┌────────────┐
+/// │RecordBatch │ │RecordBatch │
+/// └────────────┘ └────────────┘
+/// ... ...
+/// ┌────────────┐ ┌────────────┐
+/// │RecordBatch │ │RecordBatch │
+/// └────────────┘ └────────────┘
+///
+/// build side probe side
+///
+/// ```
+///
+/// # Exampe "Optimial" Plans
+///
+/// The differences in the inputs means that for classic "Star Schema Query",
+/// the optimal plan will be a **"Right Deep Tree"** . A Star Schema Query is
+/// one where there is one large table and several smaller "dimension" tables,
+/// joined on `Foreign Key = Primary Key` predicates. with predicates.
+///
+/// A "Right Deep Tree" looks like this large table as the probe side on the
Review Comment:
```suggestion
/// A "Right Deep Tree" looks like this large table as the probe side on the
```
--
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] Minor: Improve `HashJoinExec` documentation [arrow-datafusion]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7953:
URL: https://github.com/apache/arrow-datafusion/pull/7953#discussion_r1374907253
##########
datafusion/physical-plan/src/joins/hash_join.rs:
##########
@@ -78,29 +77,140 @@ use futures::{ready, Stream, StreamExt, TryStreamExt};
type JoinLeftData = (JoinHashMap, RecordBatch, MemoryReservation);
-/// Join execution plan executes partitions in parallel and combines them into a set of
-/// partitions.
+/// Join execution plan: Evaluates eqijoin predicates in parallel on multiple
+/// partitions using a hash table and an optional filter list to apply post
+/// join.
///
-/// Filter expression expected to contain non-equality predicates that can not be pushed
-/// down to any of join inputs.
-/// In case of outer join, filter applied to only matched rows.
+/// # Join Expressions
+///
+/// This implementation is optimized for evaluating eqijoin predicates (
+/// `<col1> = <col2>`) expressions, which are represented as a list of `Columns`
+/// in [`Self::on`].
+///
+/// Non-equality predicates, which can not pushed down to a join inputs (e.g.
+/// `<col1> != <col2>`) are known as "filter expressions" and are evaluated
+/// after the equijoin predicates.
+///
+/// # "Build Side" vs "Probe Side"
+///
+/// HashJoin takes two inputs, which are referred to as the "build" and the
+/// "probe". The build side is the first child, and the probe side is the second
+/// child.
+///
+/// The two inputs are treated differently and it is VERY important that the
+/// *smaller* input is placed on the build side to minimize the work of creating
+/// the hash table.
+///
+/// ```text
+/// ┌───────────┐
+/// │ HashJoin │
+/// │ │
+/// └───────────┘
+/// │ │
+/// ┌─────┘ └─────┐
+/// ▼ ▼
+/// ┌────────────┐ ┌─────────────┐
+/// │ Input │ │ Input │
+/// │ [0] │ │ [1] │
+/// └────────────┘ └─────────────┘
+///
+/// "build side" "probe side"
+/// ```
+///
+/// Execution proceeds in 2 stages:
+///
+/// 1. the **build phase** where a hash table is created from the tuples of the
+/// build side.
+///
+/// 2. the **probe phase** where the tuples of the probe side are streamed
+/// through, checking for matches of the join keys in the hash table.
+///
+/// ```text
+/// ┌────────────────┐ ┌────────────────┐
+/// │ ┌─────────┐ │ │ ┌─────────┐ │
+/// │ │ Hash │ │ │ │ Hash │ │
+/// │ │ Table │ │ │ │ Table │ │
+/// │ │(keys are│ │ │ │(keys are│ │
+/// │ │equi join│ │ │ │equi join│ │ Stage 2: batches from
+/// Stage 1: the │ │columns) │ │ │ │columns) │ │ the probe side are
+/// *entire* build │ │ │ │ │ │ │ │ streamed through, and
+/// side is read │ └─────────┘ │ │ └─────────┘ │ checked against the
+/// into the hash │ ▲ │ │ ▲ │ contents of the hash
+/// table │ HashJoin │ │ HashJoin │ table
+/// └──────┼─────────┘ └──────────┼─────┘
+/// ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
+/// │ │
+///
+/// │ │
+/// ┌────────────┐ ┌────────────┐
+/// │RecordBatch │ │RecordBatch │
+/// └────────────┘ └────────────┘
+/// ┌────────────┐ ┌────────────┐
+/// │RecordBatch │ │RecordBatch │
+/// └────────────┘ └────────────┘
+/// ... ...
+/// ┌────────────┐ ┌────────────┐
+/// │RecordBatch │ │RecordBatch │
+/// └────────────┘ └────────────┘
+///
+/// build side probe side
+///
+/// ```
+///
+/// # Exampe "Optimial" Plans
+///
+/// The differences in the inputs means that for classic "Star Schema Query",
+/// the optimal plan will be a **"Right Deep Tree"** . A Star Schema Query is
+/// one where there is one large table and several smaller "dimension" tables,
+/// joined on `Foreign Key = Primary Key` predicates. with predicates.
Review Comment:
```suggestion
/// joined on `Foreign Key = Primary Key` predicates.
```
--
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] Minor: Improve `HashJoinExec` documentation [arrow-datafusion]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7953:
URL: https://github.com/apache/arrow-datafusion/pull/7953#discussion_r1374906045
##########
datafusion/physical-plan/src/joins/hash_join.rs:
##########
@@ -78,29 +77,140 @@ use futures::{ready, Stream, StreamExt, TryStreamExt};
type JoinLeftData = (JoinHashMap, RecordBatch, MemoryReservation);
-/// Join execution plan executes partitions in parallel and combines them into a set of
-/// partitions.
+/// Join execution plan: Evaluates eqijoin predicates in parallel on multiple
+/// partitions using a hash table and an optional filter list to apply post
+/// join.
///
-/// Filter expression expected to contain non-equality predicates that can not be pushed
-/// down to any of join inputs.
-/// In case of outer join, filter applied to only matched rows.
+/// # Join Expressions
+///
+/// This implementation is optimized for evaluating eqijoin predicates (
+/// `<col1> = <col2>`) expressions, which are represented as a list of `Columns`
+/// in [`Self::on`].
+///
+/// Non-equality predicates, which can not pushed down to a join inputs (e.g.
+/// `<col1> != <col2>`) are known as "filter expressions" and are evaluated
+/// after the equijoin predicates.
+///
+/// # "Build Side" vs "Probe Side"
+///
+/// HashJoin takes two inputs, which are referred to as the "build" and the
+/// "probe". The build side is the first child, and the probe side is the second
+/// child.
+///
+/// The two inputs are treated differently and it is VERY important that the
+/// *smaller* input is placed on the build side to minimize the work of creating
+/// the hash table.
+///
+/// ```text
+/// ┌───────────┐
+/// │ HashJoin │
+/// │ │
+/// └───────────┘
+/// │ │
+/// ┌─────┘ └─────┐
+/// ▼ ▼
+/// ┌────────────┐ ┌─────────────┐
+/// │ Input │ │ Input │
+/// │ [0] │ │ [1] │
+/// └────────────┘ └─────────────┘
+///
+/// "build side" "probe side"
+/// ```
+///
+/// Execution proceeds in 2 stages:
+///
+/// 1. the **build phase** where a hash table is created from the tuples of the
+/// build side.
+///
+/// 2. the **probe phase** where the tuples of the probe side are streamed
+/// through, checking for matches of the join keys in the hash table.
+///
+/// ```text
+/// ┌────────────────┐ ┌────────────────┐
+/// │ ┌─────────┐ │ │ ┌─────────┐ │
+/// │ │ Hash │ │ │ │ Hash │ │
+/// │ │ Table │ │ │ │ Table │ │
+/// │ │(keys are│ │ │ │(keys are│ │
+/// │ │equi join│ │ │ │equi join│ │ Stage 2: batches from
+/// Stage 1: the │ │columns) │ │ │ │columns) │ │ the probe side are
+/// *entire* build │ │ │ │ │ │ │ │ streamed through, and
+/// side is read │ └─────────┘ │ │ └─────────┘ │ checked against the
+/// into the hash │ ▲ │ │ ▲ │ contents of the hash
+/// table │ HashJoin │ │ HashJoin │ table
+/// └──────┼─────────┘ └──────────┼─────┘
+/// ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
+/// │ │
+///
+/// │ │
+/// ┌────────────┐ ┌────────────┐
+/// │RecordBatch │ │RecordBatch │
+/// └────────────┘ └────────────┘
+/// ┌────────────┐ ┌────────────┐
+/// │RecordBatch │ │RecordBatch │
+/// └────────────┘ └────────────┘
+/// ... ...
+/// ┌────────────┐ ┌────────────┐
+/// │RecordBatch │ │RecordBatch │
+/// └────────────┘ └────────────┘
+///
+/// build side probe side
+///
+/// ```
+///
+/// # Exampe "Optimial" Plans
Review Comment:
```suggestion
/// # Example "Optimal" Plans
```
--
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