You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2022/05/28 14:38:57 UTC
[GitHub] [arrow-datafusion] ming535 opened a new pull request, #2638: Fix limit pushdown
ming535 opened a new pull request, #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638
# Which issue does this PR close?
Closes https://github.com/apache/arrow-datafusion/issues/2624
# Rationale for this change
See below.
# What changes are included in this PR?
1. When SqlToRel build the plan, `Limit` should be the parent of `Offset`, according to https://www.postgresql.org/docs/current/queries-limit.html
(If both OFFSET and LIMIT appear, then OFFSET rows are skipped before starting to count the LIMIT rows that are returned.)
3. fix limit_push_down to consider every combination of `Offset` and `Limit` when traversing down the plan tree.
# Are there any user-facing changes?
The semantic of LogicalPlan#offset, and LogicalPlan#limit is different.
Previously, `builder.limit(100).offset(10)` means ignore the first 10 rows and then starting to count 100 rows. Now it
means returns 100 rows and then skip 10 rows.
The current semantic is consistent with how data is flowing in the plan tree.
# Does this PR break compatibility with Ballista?
--
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
[GitHub] [arrow-datafusion] ming535 commented on pull request #2638: Fix limit pushdown
Posted by GitBox <gi...@apache.org>.
ming535 commented on PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638#issuecomment-1140797256
> > builder.limit(100).offset(10) means ignore the first 10 rows and then starting to count 100 rows. Now it
> > means returns 100 rows and then skip 10 rows.
> > @ming535 If this happened, means only return 90 rows?
Yes. The current design of plan builder tries to mimics the semantics of SQL language; this PR tries to mimics the tree structure of logical operator.
We can add another api for the builder to combines `limit` and `offset` to mimics SQL language. For example:
`fetch(offset: Option<usize>, limit: Option<usize>)`
--
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
[GitHub] [arrow-datafusion] alamb merged pull request #2638: Fix limit + offset pushdown
Posted by GitBox <gi...@apache.org>.
alamb merged PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638
--
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
[GitHub] [arrow-datafusion] Ted-Jiang commented on a diff in pull request #2638: Fix limit pushdown
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on code in PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638#discussion_r885724386
##########
datafusion/core/src/optimizer/limit_push_down.rs:
##########
@@ -608,4 +790,32 @@ mod test {
Ok(())
}
+
+ #[test]
+ fn limit_should_push_down_right_outer_join_with_offset() -> Result<()> {
+ let table_scan_1 = test_table_scan()?;
+ let table_scan_2 = test_table_scan_with_name("test2")?;
+
+ let plan = LogicalPlanBuilder::from(table_scan_1)
+ .join(
+ &LogicalPlanBuilder::from(table_scan_2).build()?,
+ JoinType::Right,
+ (vec!["a"], vec!["a"]),
+ None,
+ )?
+ .offset(10)?
+ .limit(1000)?
+ .build()?;
+
+ // Limit pushdown Not supported in Join
Review Comment:
```suggestion
// Limit pushdown with offset supported in right outer join
```
##########
datafusion/core/src/optimizer/limit_push_down.rs:
##########
@@ -40,29 +40,67 @@ impl LimitPushDown {
}
}
+/// Ancestor indicates the current ancestor in the LogicalPlan tree
+/// when traversing down related to "limit push down".
+enum Ancestor {
+ /// Limit
+ FromLimit,
+ /// Offset
+ FromOffset,
+ /// Other nodes that don't affect the adjustment of "Limit"
+ NotRelevant,
+}
+
+///
+/// When doing limit push down with "offset" and "limit" during traversal,
+/// the "limit" should be adjusted.
+/// limit_push_down is a recursive function that tracks three important information
+/// to make the adjustment.
+///
+/// 1. ancestor: the kind of Ancestor.
+/// 2. ancestor_offset: ancestor's offset value
+/// 3. ancestor_limit: ancestor's limit value
+///
+/// (ancestor_offset, ancestor_limit) is updated in the following cases
+/// 1. Ancestor_Limit(n1) -> .. -> Current_Limit(n2)
+/// When the ancestor is a "Limit" and the current node is a "Limit",
+/// it is updated to (None, min(n1, n2))).
+/// 2. Ancestor_Limit(n1) -> .. -> Current_Offset(m1)
+/// it is updated to (m1, n1 + m1).
+/// 3. Ancestor_Offset(m1) -> .. -> Current_Offset(m2)
Review Comment:
I think without subquery, it should not allowed two `offset`.
--
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
[GitHub] [arrow-datafusion] andygrove commented on pull request #2638: Fix limit pushdown
Posted by GitBox <gi...@apache.org>.
andygrove commented on PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638#issuecomment-1144000155
> Yes. The current design of plan builder tries to mimics the semantics of SQL language; this PR tries to mimics the tree structure of logical operator.
>
> We can add another api for the builder to combines `limit` and `offset` to mimics SQL language. For example: `fetch(offset: Option<usize>, limit: Option<usize>)`
I wonder if we should consider renaming the `DataFrame` / `LogicalPlanBuilder` methods. The terms limit and offset are very SQL-specific and not so intuitive here and I think that adds to confusion about how they might be interpreted. Perhaps we should consider renaming `offset` to `drop` for example. That would be closer to pandas based on a quick look at the documentation.
--
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
[GitHub] [arrow-datafusion] ming535 commented on pull request #2638: Fix limit pushdown
Posted by GitBox <gi...@apache.org>.
ming535 commented on PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638#issuecomment-1141075040
For api of plan builder, I like the way Calcite is doing https://calcite.apache.org/javadocAggregate/org/apache/calcite/tools/RelBuilder.html#limit(int,int)
which combines "limit" and "offset".
--
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
[GitHub] [arrow-datafusion] Ted-Jiang commented on pull request #2638: Fix limit pushdown
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638#issuecomment-1142168827
> I plan to review this later today or tomorrow if no one else has a chance to do so before
@alamb I am reviewing this one, I will finish this evening.
--
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
[GitHub] [arrow-datafusion] alamb commented on pull request #2638: Fix limit + offset pushdown
Posted by GitBox <gi...@apache.org>.
alamb commented on PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638#issuecomment-1144090117
I merged this PR as it has three reviewers and approvers -- I think any additional work can be done as follow on PRs.
Thanks again @ming535 @Ted-Jiang and @andygrove π
--
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
[GitHub] [arrow-datafusion] alamb commented on a diff in pull request #2638: Fix limit + offset pushdown
Posted by GitBox <gi...@apache.org>.
alamb commented on code in PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638#discussion_r887251666
##########
datafusion/core/src/optimizer/limit_push_down.rs:
##########
@@ -40,29 +40,67 @@ impl LimitPushDown {
}
}
+/// Ancestor indicates the current ancestor in the LogicalPlan tree
+/// when traversing down related to "limit push down".
+enum Ancestor {
+ /// Limit
+ FromLimit,
+ /// Offset
+ FromOffset,
+ /// Other nodes that don't affect the adjustment of "Limit"
+ NotRelevant,
+}
+
+///
+/// When doing limit push down with "offset" and "limit" during traversal,
+/// the "limit" should be adjusted.
+/// limit_push_down is a recursive function that tracks three important information
+/// to make the adjustment.
+///
+/// 1. ancestor: the kind of Ancestor.
+/// 2. ancestor_offset: ancestor's offset value
+/// 3. ancestor_limit: ancestor's limit value
+///
+/// (ancestor_offset, ancestor_limit) is updated in the following cases
+/// 1. Ancestor_Limit(n1) -> .. -> Current_Limit(n2)
+/// When the ancestor is a "Limit" and the current node is a "Limit",
+/// it is updated to (None, min(n1, n2))).
+/// 2. Ancestor_Limit(n1) -> .. -> Current_Offset(m1)
+/// it is updated to (m1, n1 + m1).
+/// 3. Ancestor_Offset(m1) -> .. -> Current_Offset(m2)
+/// it is updated to (m2, None).
+/// 4. Ancestor_Offset(m1) -> .. -> Current_Limit(n1)
+/// it is updated to (None, n1). Note that this won't happen when we
+/// generate the plan from SQL, it can happen when we build the plan
+/// using LogicalPlanBuilder.
fn limit_push_down(
_optimizer: &LimitPushDown,
- upper_limit: Option<usize>,
+ ancestor: Ancestor,
+ ancestor_offset: Option<usize>,
+ ancestor_limit: Option<usize>,
Review Comment:
If you wanted to be fancy / more idomatic rust and have the compiler check more of the invariants you could consider encoding the ancestor, offset and limit together.
Something like
```
enum Ancestor {
/// Limit
FromLimit(usize),
/// Offset
FromOffset(usize),
/// Other nodes that don't affect the adjustment of "Limit"
NotRelevant,
}
```
##########
datafusion/core/src/optimizer/limit_push_down.rs:
##########
@@ -421,7 +496,27 @@ mod test {
.build()?;
let expected = "Offset: 10\
- \n Limit: 1010\
+ \n Limit: 1000\
Review Comment:
this plan change is due to the change in semantics of `LogicalPlanBuiler::offset()`, right?
##########
datafusion/core/src/optimizer/limit_push_down.rs:
##########
@@ -421,7 +496,27 @@ mod test {
.build()?;
let expected = "Offset: 10\
- \n Limit: 1010\
+ \n Limit: 1000\
+ \n Projection: #test.a\
+ \n TableScan: test projection=None, limit=1000";
+
+ assert_optimized_plan_eq(&plan, expected);
+
+ Ok(())
+ }
+
+ #[test]
+ fn limit_pushdown_with_limit_after_offset() -> Result<()> {
+ let table_scan = test_table_scan()?;
+
+ let plan = LogicalPlanBuilder::from(table_scan)
+ .project(vec![col("a")])?
+ .offset(10)?
+ .limit(1000)?
+ .build()?;
+
+ let expected = "Limit: 1000\
+ \n Offset: 10\
\n Projection: #test.a\
\n TableScan: test projection=None, limit=1010";
Review 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
[GitHub] [arrow-datafusion] ming535 commented on pull request #2638: Fix limit pushdown
Posted by GitBox <gi...@apache.org>.
ming535 commented on PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638#issuecomment-1140904805
> c70f3378a9364603023924670b8bb0d | ac16e18018a438445e12492bf018cf0f | male
> 13 | 78cecc
In pg, the order of "offset" and "limit" doen't matter. It always means "OFFSET rows are skipped before starting to count the LIMIT rows that are returned".
In the logical plan tree, the order of "offset" and βlimitβ does matter.
This PR makes several "assumptions":
1. The builder api should be independent of SQL language, it only describes the logical tree structure.
2. When users use the builder api to construct the plan tree. If "limit" is the parent of "offset", then the semantic is to ignore some rows first; otherwise, the semantic is to first count the number rows.
3. When translating SQL to logical plan in the planner, we make "limit" to be the parent of "offset" to be compatible with pg.
--
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
[GitHub] [arrow-datafusion] ming535 commented on a diff in pull request #2638: Fix limit pushdown
Posted by GitBox <gi...@apache.org>.
ming535 commented on code in PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638#discussion_r886586708
##########
datafusion/core/src/optimizer/limit_push_down.rs:
##########
@@ -40,29 +40,67 @@ impl LimitPushDown {
}
}
+/// Ancestor indicates the current ancestor in the LogicalPlan tree
+/// when traversing down related to "limit push down".
+enum Ancestor {
+ /// Limit
+ FromLimit,
+ /// Offset
+ FromOffset,
+ /// Other nodes that don't affect the adjustment of "Limit"
+ NotRelevant,
+}
+
+///
+/// When doing limit push down with "offset" and "limit" during traversal,
+/// the "limit" should be adjusted.
+/// limit_push_down is a recursive function that tracks three important information
+/// to make the adjustment.
+///
+/// 1. ancestor: the kind of Ancestor.
+/// 2. ancestor_offset: ancestor's offset value
+/// 3. ancestor_limit: ancestor's limit value
+///
+/// (ancestor_offset, ancestor_limit) is updated in the following cases
+/// 1. Ancestor_Limit(n1) -> .. -> Current_Limit(n2)
+/// When the ancestor is a "Limit" and the current node is a "Limit",
+/// it is updated to (None, min(n1, n2))).
+/// 2. Ancestor_Limit(n1) -> .. -> Current_Offset(m1)
+/// it is updated to (m1, n1 + m1).
+/// 3. Ancestor_Offset(m1) -> .. -> Current_Offset(m2)
Review Comment:
> I think without subquery, it should not allowed two `offset`.
I think the sql parser should forbids this (two `offset` without subquery). As of the plan tree building with builder api, I think it is fine that it is not aware of this as long as the semantics looks right.
--
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
[GitHub] [arrow-datafusion] alamb commented on pull request #2638: Fix limit + offset pushdown
Posted by GitBox <gi...@apache.org>.
alamb commented on PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638#issuecomment-1144089445
> Like @ming535 said, I think combines "limit" and "offset" them is a good way, avoid create a new plan struct. @alamb need your opinion on this
I agree π
--
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
[GitHub] [arrow-datafusion] alamb commented on pull request #2638: Fix limit pushdown
Posted by GitBox <gi...@apache.org>.
alamb commented on PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638#issuecomment-1142056440
I plan to review this later today or tomorrow if no one else has a chance to do so before
--
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
[GitHub] [arrow-datafusion] Ted-Jiang commented on pull request #2638: Fix limit pushdown
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638#issuecomment-1140662369
> builder.limit(100).offset(10) means ignore the first 10 rows and then starting to count 100 rows. Now it
means returns 100 rows and then skip 10 rows.
@ming535 If this happened, means only return 90 rows?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] Ted-Jiang commented on pull request #2638: Fix limit pushdown
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638#issuecomment-1140861506
> > > builder.limit(100).offset(10) means ignore the first 10 rows and then starting to count 100 rows. Now it
> > > means returns 100 rows and then skip 10 rows.
> > > @ming535 If this happened, means only return 90 rows?
>
> Yes. The current design of plan builder tries to mimics the semantics of SQL language; this PR tries to mimics the tree structure of logical operator.
>
> We can add another api for the builder to combines `limit` and `offset` to mimics SQL language. For example: `fetch(offset: Option<usize>, limit: Option<usize>)`
Before i impl the rule i test in pg
```
postgres=# select * from users offset 1 limit 12 ;
id | hash_firstname | hash_lastname | gender
----+----------------------------------+----------------------------------+--------
2 | f5e8f62332c256ebdceea3050a1da595 | 5d6c111b409bd97b5b8e5357668564d7 | male
3 | ff82b6f31f4b4a7647ded507a599147a | cb9a959c8e42ee8f1de33c50c15b2267 | male
4 | a643dd92e5a999e9372d73373cceb407 | 68ae1a597b5b04daa3f029573dde4fb9 | female
5 | f7f6c7f939202806ebe4cdda0821b1f8 | 7a451c9e30238af75001423f17f300ac | male
6 | 37f9869968840feaf441f963e2171254 | 6a06f56a6e66ee457ddc547b7df20de4 | female
7 | e2c4c7cb13dd5f2511d3402d36cb4884 | 7cc3e36824f369b88a3445b5dc2b36d4 | female
8 | aea96778de92539cc9b80864a969c82b | 92517c35f9f1baf0ed831eab4c23757e | male
9 | 363547e325516d28f96b69a8e88deb44 | 4e6cadf5f26aacca0f8c03c115825fbe | female
10 | 340d4e6b3968e80c2fb02704a30fc574 | e0b7b41ae5397ae231c783e4e5d9d848 | female
11 | 3c8e1102dc3c9551be2fb40e4dbc0bc7 | d20d0155652a23c327734fb0e0127247 | female
12 | cc70f3378a9364603023924670b8bb0d | ac16e18018a438445e12492bf018cf0f | male
13 | 78cecc8caaf5c303097eb3816a411e79 | a0a19a4b5b595562fc8b978520401166 | female
(12 rows)
postgres=# select * from users limit 10 offset 1;
id | hash_firstname | hash_lastname | gender
----+----------------------------------+----------------------------------+--------
2 | f5e8f62332c256ebdceea3050a1da595 | 5d6c111b409bd97b5b8e5357668564d7 | male
3 | ff82b6f31f4b4a7647ded507a599147a | cb9a959c8e42ee8f1de33c50c15b2267 | male
4 | a643dd92e5a999e9372d73373cceb407 | 68ae1a597b5b04daa3f029573dde4fb9 | female
5 | f7f6c7f939202806ebe4cdda0821b1f8 | 7a451c9e30238af75001423f17f300ac | male
6 | 37f9869968840feaf441f963e2171254 | 6a06f56a6e66ee457ddc547b7df20de4 | female
7 | e2c4c7cb13dd5f2511d3402d36cb4884 | 7cc3e36824f369b88a3445b5dc2b36d4 | female
8 | aea96778de92539cc9b80864a969c82b | 92517c35f9f1baf0ed831eab4c23757e | male
9 | 363547e325516d28f96b69a8e88deb44 | 4e6cadf5f26aacca0f8c03c115825fbe | female
10 | 340d4e6b3968e80c2fb02704a30fc574 | e0b7b41ae5397ae231c783e4e5d9d848 | female
11 | 3c8e1102dc3c9551be2fb40e4dbc0bc7 | d20d0155652a23c327734fb0e0127247 | female
(10 rows)
postgres=# select * from users offset 1 limit 10 ;
id | hash_firstname | hash_lastname | gender
----+----------------------------------+----------------------------------+--------
2 | f5e8f62332c256ebdceea3050a1da595 | 5d6c111b409bd97b5b8e5357668564d7 | male
3 | ff82b6f31f4b4a7647ded507a599147a | cb9a959c8e42ee8f1de33c50c15b2267 | male
4 | a643dd92e5a999e9372d73373cceb407 | 68ae1a597b5b04daa3f029573dde4fb9 | female
5 | f7f6c7f939202806ebe4cdda0821b1f8 | 7a451c9e30238af75001423f17f300ac | male
6 | 37f9869968840feaf441f963e2171254 | 6a06f56a6e66ee457ddc547b7df20de4 | female
7 | e2c4c7cb13dd5f2511d3402d36cb4884 | 7cc3e36824f369b88a3445b5dc2b36d4 | female
8 | aea96778de92539cc9b80864a969c82b | 92517c35f9f1baf0ed831eab4c23757e | male
9 | 363547e325516d28f96b69a8e88deb44 | 4e6cadf5f26aacca0f8c03c115825fbe | female
10 | 340d4e6b3968e80c2fb02704a30fc574 | e0b7b41ae5397ae231c783e4e5d9d848 | female
11 | 3c8e1102dc3c9551be2fb40e4dbc0bc7 | d20d0155652a23c327734fb0e0127247 | female
(10 rows)
```
Use offset before limit should also return 10 rows.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] andygrove commented on pull request #2638: Fix limit pushdown
Posted by GitBox <gi...@apache.org>.
andygrove commented on PR #2638:
URL: https://github.com/apache/arrow-datafusion/pull/2638#issuecomment-1144002546
I also like the idea of combining limit and offset in one DataFrame / builder method
--
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