You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "suremarc (via GitHub)" <gi...@apache.org> on 2024/03/26 16:55:16 UTC
[PR] initial impl [arrow-datafusion]
suremarc opened a new pull request, #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
Closes #9812.
## 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.
-->
Eliminate redundant sorts
## 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.
-->
Adds a new function, `collapse_monotonic_lex_req` that eliminates sorts like `f(a), a` if it is known that `f` preserves ordering, and uses it in the `normalize_sort_requirements` function of `EquivalenceProperties`.
## 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)?
-->
Yes, there is a unit test. I also wanted to add a sqllogictest as demonstrated in the write-up in #9812:
```sql
CREATE UNBOUNDED EXTERNAL TABLE data (
"date" DATE,
"ticker" VARCHAR,
"timestamp" TIMESTAMP,
) STORED AS CSV
WITH ORDER ("date", "ticker", "timestamp")
LOCATION './a.parquet';
explain SELECT * FROM data
WHERE ticker = 'A' AND date = CAST(timestamp AS DATE)
ORDER BY "timestamp";
```
but filter equality predicates are not converted into equivalence classes, so the only way to demonstrate this change is with custom equivalence properties.
## Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please add the `api change` label.
-->
There are no public API changes, but sorts may be removed in certain 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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#discussion_r1559856903
##########
datafusion/physical-expr/src/equivalence/mod.rs:
##########
@@ -45,6 +46,46 @@ pub fn collapse_lex_req(input: LexRequirement) -> LexRequirement {
output
}
+/// This function constructs a normalized [`LexRequirement`] by filtering out entries
+/// that are ordered if the next entry is.
Review Comment:
It seems like there are no additional callsites of `collapse_lex_ordering` -- perhaps we should simply update `collapse_lex_ordering` instead of making a new function 🤔
https://github.com/search?q=repo%3Aapache%2Farrow-datafusion+collapse_lex_ordering&type=code
##########
datafusion/sqllogictest/test_files/filter_without_sort_exec.slt:
##########
@@ -43,19 +43,36 @@ SortPreservingMergeExec: [date@0 ASC NULLS LAST,time@2 ASC NULLS LAST]
------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
--------StreamingTableExec: partition_sizes=1, projection=[date, ticker, time], infinite_source=true, output_ordering=[date@0 ASC NULLS LAST, ticker@1 ASC NULLS LAST, time@2 ASC NULLS LAST]
+# query
+query TT
Review Comment:
Could you also test some similar queries that should also have their sorts removed? LIke
```sql
SELECT * FROM data
WHERE ticker = 'A' AND CAST(time AS DATE) = date
ORDER BY "date"
```
```sql
SELECT * FROM data
WHERE ticker = 'A' AND CAST(time AS DATE) = date
ORDER BY "ticker"
```
As well as some cases where it should not:
```sql
SELECT * FROM data
WHERE ticker = 'A' AND CAST(time AS DATE) <> date
ORDER BY "timestamp"
```
##########
datafusion/physical-expr/src/equivalence/properties.rs:
##########
@@ -2212,6 +2212,97 @@ mod tests {
);
}
+ Ok(())
+ }
+ #[test]
+ fn test_eliminate_redundant_monotonic_sorts() -> Result<()> {
+ let schema = Arc::new(Schema::new(vec![
+ Field::new("a", DataType::Date32, true),
+ Field::new("b", DataType::Utf8, true),
+ Field::new("c", DataType::Timestamp(TimeUnit::Nanosecond, None), true),
+ ]));
+ let base_properties = EquivalenceProperties::new(schema.clone()).with_reorder(
+ ["a", "b", "c"]
+ .into_iter()
+ .map(|c| {
+ col(c, schema.as_ref()).map(|expr| PhysicalSortExpr {
+ expr,
+ options: SortOptions {
+ descending: false,
+ nulls_first: true,
+ },
+ })
+ })
+ .collect::<Result<Vec<_>>>()?,
+ );
+
+ struct TestCase {
+ name: &'static str,
+ constants: Vec<Arc<dyn PhysicalExpr>>,
+ equal_conditions: Vec<[Arc<dyn PhysicalExpr>; 2]>,
+ sort_columns: &'static [&'static str],
+ should_satisfy_ordering: bool,
+ }
+
+ let cases = vec![
Review Comment:
I would find these cases easier to read if they were written like
```rust
let col_a = col("a", schema.as_ref())?;
let col_b = col("b", schema.as_ref())?;
let cast_c = Arc::new(CastExpr::new(
col("c", schema.as_ref())?,
DataType::Date32,
None,
));
...
TestCase {
name: "(date, ticker, time) -> (time)",
// b is constant, so it should be removed from the sort order
constants: vec![col_b.clone()?],
equal_conditions: vec![[cast_c.clone(), col_a.clone()]],
sort_columns: &["c"],
should_satisfy_ordering: true,
...
```
##########
datafusion/physical-expr/src/equivalence/properties.rs:
##########
@@ -2212,6 +2212,97 @@ mod tests {
);
}
+ Ok(())
+ }
+ #[test]
+ fn test_eliminate_redundant_monotonic_sorts() -> Result<()> {
+ let schema = Arc::new(Schema::new(vec![
+ Field::new("a", DataType::Date32, true),
Review Comment:
Would it be possible to use the same names in the schema `(a, b, c)` that are used in the test description `(date, ticker, time)`? I found it hard to mentally map between the two while reviewing this code
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "suremarc (via GitHub)" <gi...@apache.org>.
suremarc commented on code in PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#discussion_r1561563972
##########
datafusion/physical-expr/src/equivalence/mod.rs:
##########
@@ -35,14 +36,59 @@ pub use properties::{join_equivalence_properties, EquivalenceProperties};
/// This function constructs a duplicate-free `LexOrderingReq` by filtering out
/// duplicate entries that have same physical expression inside. For example,
/// `vec![a Some(ASC), a Some(DESC)]` collapses to `vec![a Some(ASC)]`.
+///
+/// It will also filter out entries that are ordered if the next entry is;
+/// for instance, `vec![floor(a) Some(ASC), a Some(ASC)]` will be collapsed to
+/// `vec![a Some(ASC)]`.
pub fn collapse_lex_req(input: LexRequirement) -> LexRequirement {
let mut output = Vec::<PhysicalSortRequirement>::new();
for item in input {
if !output.iter().any(|req| req.expr.eq(&item.expr)) {
output.push(item);
}
}
- output
+ collapse_monotonic_lex_req(output)
+}
+
+/// This function constructs a normalized [`LexRequirement`] by filtering out entries
+/// that are ordered if the next entry is.
+/// Used in `collapse_lex_req`
+fn collapse_monotonic_lex_req(input: LexRequirement) -> LexRequirement {
+ input
Review Comment:
I tried it, it seems challenging to avoid clones since the iteration looks ahead at the next item. I think it could be done if we rewrote it as a fold or reduce.
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "suremarc (via GitHub)" <gi...@apache.org>.
suremarc commented on code in PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#discussion_r1563020840
##########
datafusion/sqllogictest/test_files/filter_without_sort_exec.slt:
##########
@@ -43,19 +43,111 @@ SortPreservingMergeExec: [date@0 ASC NULLS LAST,time@2 ASC NULLS LAST]
------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
--------StreamingTableExec: partition_sizes=1, projection=[date, ticker, time], infinite_source=true, output_ordering=[date@0 ASC NULLS LAST, ticker@1 ASC NULLS LAST, time@2 ASC NULLS LAST]
+# constant ticker, CAST(time AS DATE) = time, order by time
+query TT
+explain SELECT * FROM data
+WHERE ticker = 'A' AND CAST(time AS DATE) = date
+ORDER BY "time"
+----
+logical_plan
+Sort: data.time ASC NULLS LAST
+--Filter: data.ticker = Utf8("A") AND CAST(data.time AS Date32) = data.date
+----TableScan: data projection=[date, ticker, time]
+physical_plan
+SortPreservingMergeExec: [time@2 ASC NULLS LAST]
+--CoalesceBatchesExec: target_batch_size=8192
+----FilterExec: ticker@1 = A AND CAST(time@2 AS Date32) = date@0
+------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
+--------StreamingTableExec: partition_sizes=1, projection=[date, ticker, time], infinite_source=true, output_ordering=[date@0 ASC NULLS LAST, ticker@1 ASC NULLS LAST, time@2 ASC NULLS LAST]
+
+# same thing but order by date
+query TT
+explain SELECT * FROM data
+WHERE ticker = 'A' AND CAST(time AS DATE) = date
+ORDER BY "date"
+----
+logical_plan
+Sort: data.date ASC NULLS LAST
+--Filter: data.ticker = Utf8("A") AND CAST(data.time AS Date32) = data.date
+----TableScan: data projection=[date, ticker, time]
+physical_plan
+SortPreservingMergeExec: [date@0 ASC NULLS LAST]
+--CoalesceBatchesExec: target_batch_size=8192
+----FilterExec: ticker@1 = A AND CAST(time@2 AS Date32) = date@0
+------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
+--------StreamingTableExec: partition_sizes=1, projection=[date, ticker, time], infinite_source=true, output_ordering=[date@0 ASC NULLS LAST, ticker@1 ASC NULLS LAST, time@2 ASC NULLS LAST]
+
+# same thing but order by ticker
+query TT
+explain SELECT * FROM data
+WHERE ticker = 'A' AND CAST(time AS DATE) = date
+ORDER BY "ticker"
+----
+logical_plan
+Sort: data.ticker ASC NULLS LAST
+--Filter: data.ticker = Utf8("A") AND CAST(data.time AS Date32) = data.date
+----TableScan: data projection=[date, ticker, time]
+physical_plan
+CoalescePartitionsExec
Review Comment:
Oh, I finally realized what you mean. Since `ticker` is constant the order is arbitrary. That is indeed very cool
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#issuecomment-2021840748
Thanks @suremarc -- I am behind on reviews -- I hope to review this PR over the next day or two.
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#issuecomment-2046100733
I am sorry -- I ran out of brainpower today to review this PR. I will try again tomorrow
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "suremarc (via GitHub)" <gi...@apache.org>.
suremarc commented on PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#issuecomment-2052397924
@alamb While testing out this feature, I've noticed that the sort elimination doesn't work when certain projections are involved. E.g.,
```sql
EXPLAIN
SELECT "time" FROM data
WHERE "ticker" = 'A'
ORDER BY "time"
```
fails to eliminate the sort, but `SELECT *` works.
It seems like some substantial work has been done for propagating ordering through projections (#7363), but I guess it didn't work in this case. Curious what your thoughts are here @mustafasrepo
I still think this PR can be merged as-is, but I will make a follow-up issue unless anyone has any objections
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "suremarc (via GitHub)" <gi...@apache.org>.
suremarc commented on code in PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#discussion_r1560059028
##########
datafusion/sqllogictest/test_files/filter_without_sort_exec.slt:
##########
@@ -43,19 +43,36 @@ SortPreservingMergeExec: [date@0 ASC NULLS LAST,time@2 ASC NULLS LAST]
------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
--------StreamingTableExec: partition_sizes=1, projection=[date, ticker, time], infinite_source=true, output_ordering=[date@0 ASC NULLS LAST, ticker@1 ASC NULLS LAST, time@2 ASC NULLS LAST]
+# query
+query TT
Review Comment:
I added those in addition to (time, date)
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "mustafasrepo (via GitHub)" <gi...@apache.org>.
mustafasrepo commented on PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#issuecomment-2022183722
I suggested an alternative solution it can be found in the [PR](https://github.com/polygon-io/arrow-datafusion/pull/1).
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "suremarc (via GitHub)" <gi...@apache.org>.
suremarc commented on PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#issuecomment-2032477164
@alamb @mustafasrepo re-opening this for feedback after discussion in [polygon-io/arrow-datafusion#1](https://github.com/polygon-io/arrow-datafusion/pull/1).
Thanks to PR #9819, I was able to add that sqllogictest I mentioned in the original post. I also added a negative test case based on the counterexample described [here](https://github.com/polygon-io/arrow-datafusion/pull/1#discussion_r1541387171).
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "suremarc (via GitHub)" <gi...@apache.org>.
suremarc commented on PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#issuecomment-2048417077
> Also, I think it would make sense to always apply code (aka update `collapse_lex_ordering` rather than add a new function). What do you think?
I think this makes sense, in fact that was my initial idea. The only thing stopping me from doing that is I'm not sure if it interferes with how orderings are normalized, and generally I wasn't sure if it just might cause bugs. I can give it a shot and see what happens.
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#discussion_r1561549294
##########
datafusion/physical-expr/src/equivalence/mod.rs:
##########
@@ -35,14 +36,59 @@ pub use properties::{join_equivalence_properties, EquivalenceProperties};
/// This function constructs a duplicate-free `LexOrderingReq` by filtering out
/// duplicate entries that have same physical expression inside. For example,
/// `vec![a Some(ASC), a Some(DESC)]` collapses to `vec![a Some(ASC)]`.
+///
+/// It will also filter out entries that are ordered if the next entry is;
+/// for instance, `vec![floor(a) Some(ASC), a Some(ASC)]` will be collapsed to
+/// `vec![a Some(ASC)]`.
pub fn collapse_lex_req(input: LexRequirement) -> LexRequirement {
let mut output = Vec::<PhysicalSortRequirement>::new();
for item in input {
if !output.iter().any(|req| req.expr.eq(&item.expr)) {
output.push(item);
}
}
- output
+ collapse_monotonic_lex_req(output)
+}
+
+/// This function constructs a normalized [`LexRequirement`] by filtering out entries
+/// that are ordered if the next entry is.
+/// Used in `collapse_lex_req`
+fn collapse_monotonic_lex_req(input: LexRequirement) -> LexRequirement {
+ input
Review Comment:
Nit: we could probably save a copy by using `into_iter()` here rather than `iter()` -- then we could skip the `cloned()` at the end too
##########
datafusion/sqllogictest/test_files/filter_without_sort_exec.slt:
##########
@@ -43,19 +43,111 @@ SortPreservingMergeExec: [date@0 ASC NULLS LAST,time@2 ASC NULLS LAST]
------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
--------StreamingTableExec: partition_sizes=1, projection=[date, ticker, time], infinite_source=true, output_ordering=[date@0 ASC NULLS LAST, ticker@1 ASC NULLS LAST, time@2 ASC NULLS LAST]
+# constant ticker, CAST(time AS DATE) = time, order by time
+query TT
+explain SELECT * FROM data
+WHERE ticker = 'A' AND CAST(time AS DATE) = date
+ORDER BY "time"
+----
+logical_plan
+Sort: data.time ASC NULLS LAST
+--Filter: data.ticker = Utf8("A") AND CAST(data.time AS Date32) = data.date
+----TableScan: data projection=[date, ticker, time]
+physical_plan
+SortPreservingMergeExec: [time@2 ASC NULLS LAST]
+--CoalesceBatchesExec: target_batch_size=8192
+----FilterExec: ticker@1 = A AND CAST(time@2 AS Date32) = date@0
+------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
+--------StreamingTableExec: partition_sizes=1, projection=[date, ticker, time], infinite_source=true, output_ordering=[date@0 ASC NULLS LAST, ticker@1 ASC NULLS LAST, time@2 ASC NULLS LAST]
+
+# same thing but order by date
+query TT
+explain SELECT * FROM data
+WHERE ticker = 'A' AND CAST(time AS DATE) = date
+ORDER BY "date"
+----
+logical_plan
+Sort: data.date ASC NULLS LAST
+--Filter: data.ticker = Utf8("A") AND CAST(data.time AS Date32) = data.date
+----TableScan: data projection=[date, ticker, time]
+physical_plan
+SortPreservingMergeExec: [date@0 ASC NULLS LAST]
+--CoalesceBatchesExec: target_batch_size=8192
+----FilterExec: ticker@1 = A AND CAST(time@2 AS Date32) = date@0
+------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
+--------StreamingTableExec: partition_sizes=1, projection=[date, ticker, time], infinite_source=true, output_ordering=[date@0 ASC NULLS LAST, ticker@1 ASC NULLS LAST, time@2 ASC NULLS LAST]
+
+# same thing but order by ticker
+query TT
+explain SELECT * FROM data
+WHERE ticker = 'A' AND CAST(time AS DATE) = date
+ORDER BY "ticker"
+----
+logical_plan
+Sort: data.ticker ASC NULLS LAST
+--Filter: data.ticker = Utf8("A") AND CAST(data.time AS Date32) = data.date
+----TableScan: data projection=[date, ticker, time]
+physical_plan
+CoalescePartitionsExec
Review Comment:
this is cool to see it knows it doesn't need to preserve the order at all (doesn't have to use sort preserving merge)
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "suremarc (via GitHub)" <gi...@apache.org>.
suremarc commented on code in PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#discussion_r1560043391
##########
datafusion/physical-expr/src/equivalence/properties.rs:
##########
@@ -2212,6 +2212,97 @@ mod tests {
);
}
+ Ok(())
+ }
+ #[test]
+ fn test_eliminate_redundant_monotonic_sorts() -> Result<()> {
+ let schema = Arc::new(Schema::new(vec![
+ Field::new("a", DataType::Date32, true),
Review Comment:
Ah yeah sorry that's a typo by me
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "mustafasrepo (via GitHub)" <gi...@apache.org>.
mustafasrepo commented on PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#issuecomment-2056188152
> While testing out this feature, I've noticed that the sort elimination doesn't work when certain projections are involved.
(Brainstorming) The reason might be that, datafusion with current implementation infers that with existing orderings, constant expressions, equivalent expressions some of the sort expressions are already satisfied.
However, projection cannot propagate information about the pruned out expressions. This may result, equivalence or constantness information to be lost. This might be the root cause of the problem.
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#issuecomment-2022736405
Converting to draft as we discuss options on this PR. Thanks again @suremarc and @mustafasrepo
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "mustafasrepo (via GitHub)" <gi...@apache.org>.
mustafasrepo commented on PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#issuecomment-2022013170
> @mustafasrepo do you perhaps have time to review this PR?
Sure
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#discussion_r1541059976
##########
datafusion/physical-expr/src/equivalence/mod.rs:
##########
@@ -45,6 +46,46 @@ pub fn collapse_lex_req(input: LexRequirement) -> LexRequirement {
output
}
+/// This function constructs a normalized [`LexRequirement`] by filtering out entries
+/// that are ordered if the next entry is.
+pub(crate) fn collapse_monotonic_lex_req(input: LexRequirement) -> LexRequirement {
+ input
+ .iter()
+ .enumerate()
+ .filter_map(|(i, item)| {
+ // If it's the last entry, there is no next entry
+ if i == input.len() - 1 {
+ return Some(item);
+ }
+ let next_expr = &input[i + 1];
+
+ // Only handle expressions with exactly one child
+ // TODO: it should be possible to handle expressions orderings f(a, b, c), a, b, c
+ // if f is monotonic in all arguments
+ if !(item.expr.children().len() == 1
Review Comment:
I don't really understand how this check for the expression being `monotonic` -- specifically I think [monotonicity](https://en.wikipedia.org/wiki/Monotonic_function) is a function of the actual function, not just the number of inputs
For example, `abs(x)` is NOT monotonic even though it has a single argument.
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "suremarc (via GitHub)" <gi...@apache.org>.
suremarc commented on PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#issuecomment-2057205243
@alamb @mustafasrepo false alarm, I just realized I forgot to include `CAST(time AS DATE) = date` in the example query above 🤦
That said, I have been seeing issues trying to integrate this feature into my project, but I'm still unsure if it's an issue on my side or in DataFusion yet. Most likely the former, but if not I will file an issue
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#issuecomment-2043709063
I plan to review this PR carefully tomorrow. Thanks @suremarc
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#issuecomment-2021841289
@mustafasrepo do you perhaps have time to review 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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "suremarc (via GitHub)" <gi...@apache.org>.
suremarc commented on code in PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#discussion_r1541288899
##########
datafusion/physical-expr/src/equivalence/mod.rs:
##########
@@ -45,6 +46,46 @@ pub fn collapse_lex_req(input: LexRequirement) -> LexRequirement {
output
}
+/// This function constructs a normalized [`LexRequirement`] by filtering out entries
+/// that are ordered if the next entry is.
+pub(crate) fn collapse_monotonic_lex_req(input: LexRequirement) -> LexRequirement {
+ input
+ .iter()
+ .enumerate()
+ .filter_map(|(i, item)| {
+ // If it's the last entry, there is no next entry
+ if i == input.len() - 1 {
+ return Some(item);
+ }
+ let next_expr = &input[i + 1];
+
+ // Only handle expressions with exactly one child
+ // TODO: it should be possible to handle expressions orderings f(a, b, c), a, b, c
+ // if f is monotonic in all arguments
+ if !(item.expr.children().len() == 1
Review Comment:
Ah, well you're right that this doesn't check monotonicity. I just restricted to the single argument case for simplicity. The actual monotonicity check happens on line 76
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "suremarc (via GitHub)" <gi...@apache.org>.
suremarc commented on code in PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#discussion_r1560045190
##########
datafusion/physical-expr/src/equivalence/mod.rs:
##########
@@ -45,6 +46,46 @@ pub fn collapse_lex_req(input: LexRequirement) -> LexRequirement {
output
}
+/// This function constructs a normalized [`LexRequirement`] by filtering out entries
+/// that are ordered if the next entry is.
Review Comment:
I think in this case we'd be modifying `collapse_lex_req` which is almost the same, although it has a couple more callsites. I'll see if it works
--
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] feat: eliminate redundant sorts on monotonic expressions [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9813:
URL: https://github.com/apache/arrow-datafusion/pull/9813#issuecomment-2052597750
I think a follow on PR would be great. Thanks again @suremarc -- this is a great contribution
--
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