You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "mustafasrepo (via GitHub)" <gi...@apache.org> on 2024/01/12 14:20:25 UTC

[PR] Track causal window frames to produce early results. [arrow-datafusion]

mustafasrepo opened a new pull request, #8842:
URL: https://github.com/apache/arrow-datafusion/pull/8842

   ## Which issue does this PR close?
   
   <!--
   We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
   -->
   
   Closes #.
   
   ## Rationale for this change
   In streaming execution, window functions generate result when frame end is smaller than batch size (This guarantees that future rows may not extend up the current window frame). However, for causal window frame (e.g window frame that doesn't include future rows than the current row). We can generate results even if frame end is same with batch size. 
   
   With this support we can decrease latency for causal queries.
   <!--
    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?
   This PR adds support for causality analysis for window frame to decrease latency and memory during generating window function results.
   <!--
   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?
   Yes
   
   <!--
   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 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] Determine causal window frames to produce early results. [arrow-datafusion]

Posted by "mustafasrepo (via GitHub)" <gi...@apache.org>.
mustafasrepo commented on code in PR #8842:
URL: https://github.com/apache/arrow-datafusion/pull/8842#discussion_r1451993293


##########
datafusion/sql/src/expr/function.rs:
##########
@@ -102,6 +103,21 @@ impl<'a, S: ContextProvider> SqlToRel<'a, S> {
                 // Numeric literals in window function ORDER BY are treated as constants
                 false,
             )?;
+
+            let func_deps = schema.functional_dependencies();

Review Comment:
   Sure, updated 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


Re: [PR] Determine causal window frames to produce early results. [arrow-datafusion]

Posted by "mustafasrepo (via GitHub)" <gi...@apache.org>.
mustafasrepo commented on PR #8842:
URL: https://github.com/apache/arrow-datafusion/pull/8842#issuecomment-1891533997

   > Thank you for this PR @mustafasrepo -- I feel I lack the context to review it properly, maybe could you explain the usecase (ideally in doc comments somewhere) with an example or two?
   > 
   > Also, the PR description talks about emitting batches earlier, but I didn't see any test coverage of that. Was that intended?
   
    
   
   > Add new test
   
   
   
   > Thank you for this PR @mustafasrepo -- I feel I lack the context to review it properly, maybe could you explain the usecase (ideally in doc comments somewhere) with an example or two?
   > 
   > Also, the PR description talks about emitting batches earlier, but I didn't see any test coverage of that. Was that intended?
   
   At first, I thought it would be hard to exactly test this behaviour. However, after some thinking I found out it wouldn't be that hard. I have added a test for this case in [commit](https://github.com/apache/arrow-datafusion/pull/8842/commits/4723dc687699787ebbeb950173c785ab7f39110b) 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] Determine causal window frames to produce early results. [arrow-datafusion]

Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak merged PR #8842:
URL: https://github.com/apache/arrow-datafusion/pull/8842


-- 
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] Determine causal window frames to produce early results. [arrow-datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #8842:
URL: https://github.com/apache/arrow-datafusion/pull/8842#discussion_r1453301756


##########
datafusion/expr/src/window_frame.rs:
##########
@@ -23,32 +23,76 @@
 //! - An ending frame boundary,
 //! - An EXCLUDE clause.
 
+use std::convert::{From, TryFrom};
+use std::fmt::{self, Formatter};
+use std::hash::Hash;
+
 use crate::expr::Sort;
 use crate::Expr;
+
 use datafusion_common::{plan_err, sql_err, DataFusionError, Result, ScalarValue};
 use sqlparser::ast;
 use sqlparser::parser::ParserError::ParserError;
-use std::convert::{From, TryFrom};
-use std::fmt;
-use std::fmt::Formatter;
-use std::hash::Hash;
 
-/// The frame-spec determines which output rows are read by an aggregate window function.
-///
-/// The ending frame boundary can be omitted (if the BETWEEN and AND keywords that surround the
-/// starting frame boundary are also omitted), in which case the ending frame boundary defaults to
-/// CURRENT ROW.
+/// The frame specification determines which output rows are read by an aggregate
+/// window function. The ending frame boundary can be omitted if the `BETWEEN`
+/// and `AND` keywords that surround the starting frame boundary are also omitted,
+/// in which case the ending frame boundary defaults to `CURRENT ROW`.
 #[derive(Clone, PartialEq, Eq, Hash)]
 pub struct WindowFrame {
-    /// A frame type - either ROWS, RANGE or GROUPS
+    /// Frame type - either `ROWS`, `RANGE` or `GROUPS`
     pub units: WindowFrameUnits,
-    /// A starting frame boundary
+    /// Starting frame boundary
     pub start_bound: WindowFrameBound,
-    /// An ending frame boundary
+    /// Ending frame boundary
     pub end_bound: WindowFrameBound,
-    /// Flag indicates whether window frame is causal
-    /// See documentation for [is_frame_causal] for what causal means in this context and how it is calculated.
-    is_causal: bool,
+    /// Flag indicating whether the frame is causal (i.e. computing the result

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


Re: [PR] Determine causal window frames to produce early results. [arrow-datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #8842:
URL: https://github.com/apache/arrow-datafusion/pull/8842#issuecomment-1900890120

   This slightly changed the API to create `WindowFrame` (can't use struct syntax to create anymore) so marking as API change. You can still create the struct using `WindowFrame::new_bounds`


-- 
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] Determine causal window frames to produce early results. [arrow-datafusion]

Posted by "mustafasrepo (via GitHub)" <gi...@apache.org>.
mustafasrepo commented on code in PR #8842:
URL: https://github.com/apache/arrow-datafusion/pull/8842#discussion_r1451994413


##########
datafusion/expr/src/window_frame.rs:
##########
@@ -30,21 +30,24 @@ use sqlparser::ast;
 use sqlparser::parser::ParserError::ParserError;
 use std::convert::{From, TryFrom};
 use std::fmt;
+use std::fmt::Formatter;
 use std::hash::Hash;
 
 /// The frame-spec determines which output rows are read by an aggregate window function.
 ///
 /// The ending frame boundary can be omitted (if the BETWEEN and AND keywords that surround the
 /// starting frame boundary are also omitted), in which case the ending frame boundary defaults to
 /// CURRENT ROW.
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+#[derive(Clone, PartialEq, Eq, Hash)]
 pub struct WindowFrame {
     /// A frame type - either ROWS, RANGE or GROUPS
     pub units: WindowFrameUnits,
     /// A starting frame boundary
     pub start_bound: WindowFrameBound,
     /// An ending frame boundary
     pub end_bound: WindowFrameBound,
+    /// Flag indicates whether window frame is causal.

Review Comment:
   Added a docstring to `is_frame_causal` and link it here for explanation. 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] Determine causal window frames to produce early results. [arrow-datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #8842:
URL: https://github.com/apache/arrow-datafusion/pull/8842#discussion_r1450985891


##########
datafusion/expr/src/window_frame.rs:
##########
@@ -30,21 +30,24 @@ use sqlparser::ast;
 use sqlparser::parser::ParserError::ParserError;
 use std::convert::{From, TryFrom};
 use std::fmt;
+use std::fmt::Formatter;
 use std::hash::Hash;
 
 /// The frame-spec determines which output rows are read by an aggregate window function.
 ///
 /// The ending frame boundary can be omitted (if the BETWEEN and AND keywords that surround the
 /// starting frame boundary are also omitted), in which case the ending frame boundary defaults to
 /// CURRENT ROW.
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+#[derive(Clone, PartialEq, Eq, Hash)]
 pub struct WindowFrame {
     /// A frame type - either ROWS, RANGE or GROUPS
     pub units: WindowFrameUnits,
     /// A starting frame boundary
     pub start_bound: WindowFrameBound,
     /// An ending frame boundary
     pub end_bound: WindowFrameBound,
+    /// Flag indicates whether window frame is causal.

Review Comment:
   Can you please document what `causal` means in this context (I am not sure I understand what it means)? Perhaps you can update the doc comments on `WindowFrame` to explain what the concept is and give an example of a causal bound and non causal bound and then link to that definition when referred to elsewhere?



##########
datafusion/sqllogictest/test_files/window.slt:
##########
@@ -3871,3 +3871,31 @@ FROM (SELECT c1, c2, ROW_NUMBER() OVER(PARTITION BY c1) as rn
     LIMIT 5)
 GROUP BY rn
 ORDER BY rn;
+
+# create a table for testing
+statement ok
+CREATE TABLE table_with_pk (
+          sn INT PRIMARY KEY,
+          ts TIMESTAMP,
+          currency VARCHAR(3),
+          amount FLOAT
+        ) as VALUES
+          (0, '2022-01-01 06:00:00'::timestamp, 'EUR', 30.0),
+          (1, '2022-01-01 08:00:00'::timestamp, 'EUR', 50.0),
+          (2, '2022-01-01 11:30:00'::timestamp, 'TRY', 75.0),
+          (3, '2022-01-02 12:00:00'::timestamp, 'EUR', 200.0),
+          (4, '2022-01-03 10:00:00'::timestamp, 'TRY', 100.0)
+
+query TT
+EXPLAIN SELECT *, SUM(amount) OVER(ORDER BY sn) as sum1

Review Comment:
   Could you add some comments here explaining what this test is validating (specifically so if it changes in the future we will have some additional context on the intent of the test)?



##########
datafusion/sql/src/expr/function.rs:
##########
@@ -102,6 +103,21 @@ impl<'a, S: ContextProvider> SqlToRel<'a, S> {
                 // Numeric literals in window function ORDER BY are treated as constants
                 false,
             )?;
+
+            let func_deps = schema.functional_dependencies();

Review Comment:
   Could you document what ordering is stable means ?



-- 
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] Determine causal window frames to produce early results. [arrow-datafusion]

Posted by "mustafasrepo (via GitHub)" <gi...@apache.org>.
mustafasrepo commented on code in PR #8842:
URL: https://github.com/apache/arrow-datafusion/pull/8842#discussion_r1451993814


##########
datafusion/sqllogictest/test_files/window.slt:
##########
@@ -3871,3 +3871,31 @@ FROM (SELECT c1, c2, ROW_NUMBER() OVER(PARTITION BY c1) as rn
     LIMIT 5)
 GROUP BY rn
 ORDER BY rn;
+
+# create a table for testing
+statement ok
+CREATE TABLE table_with_pk (
+          sn INT PRIMARY KEY,
+          ts TIMESTAMP,
+          currency VARCHAR(3),
+          amount FLOAT
+        ) as VALUES
+          (0, '2022-01-01 06:00:00'::timestamp, 'EUR', 30.0),
+          (1, '2022-01-01 08:00:00'::timestamp, 'EUR', 50.0),
+          (2, '2022-01-01 11:30:00'::timestamp, 'TRY', 75.0),
+          (3, '2022-01-02 12:00:00'::timestamp, 'EUR', 200.0),
+          (4, '2022-01-03 10:00:00'::timestamp, 'TRY', 100.0)
+
+query TT
+EXPLAIN SELECT *, SUM(amount) OVER(ORDER BY sn) as sum1

Review Comment:
   Thanks @alamb, added a comment to explain rationale



-- 
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] Determine causal window frames to produce early results. [arrow-datafusion]

Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak commented on PR #8842:
URL: https://github.com/apache/arrow-datafusion/pull/8842#issuecomment-1892616404

   I will go ahead and merge this since it is a fairly simple change that is an incremental improvement to existing functionality without any major change to code structure. In case of any issues related to this PR, let us know and we will address with a quick follow-on 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