feat: add windowrel support in proto

[JkSelf]

No description provided.

[CLAassistant]

All committers have signed the CLA.

[JkSelf]

@jacques-n Please help to review if you have available time. Thanks for your help!

[JkSelf]

cc @FelixYBW @baibaichen

[PHILO-HE]

Just a small suggestion. I think using window frame is more proper and more clear to user than using window type. Right?

  enum WindowFrame {
    WINDOW_FRAME_UNSPECIFIED = 0;
    WINDOW_FRAME_ROWS = 1;
    WINDOW_FRAME_RANGE = 2;
  }

[JkSelf]

Thanks for you suggestion. And very sorry that I did not reply in time. I have already changed to WindowFrame.

[github-actions]

ACTION NEEDED

Substrait follows the Conventional Commits specification for release automation.

The PR title and description are used as the merge commit message. Please update your PR title and description to match the specification.

[JkSelf]

@jacques-n Can you help to review again?

[westonpace]

I have a few questions but this seems like a good start.

[JkSelf]

@westonpace @cpcloud Can you help to review again? Thanks for your help!

[westonpace]

@JkSelf thanks for the update. Based on previous discussion I think this is a physical counterpart to WindowFunction. In other words:

A logical plan will only need WindowFunction
A physical (or less logical plan) may instead use WindowRel.

If you agree I think we should make a few changes:

• WindowRel should not use WindowFunction. Instead, copy the fields that you need (I think it will be similar to ScalarFunction) into a separate message that is local to WindowRel.
  • For example, WindowRel::Function will not have sorts. This way there is no confusion which instance of sorts should be used.
• Similar to above, but should lower_bound/upper_bound be added to WindowRel?
• We should update physical_relations.md to reflect this new operator. Currently, there is "Hashing Window Operator" and "Streaming Window Operator". Does this replace one of these? Or is it a third kind of node? Or does "Hashing" and "Streaming" not make sense and we should combine them into this?
• Does this operator handle "scalar window functions" (e.g. SELECT RANK() OVER (ORDER BY time)) or "window aggregates" (e.g. SELECT SUM(val) OVER (PARTITION BY month)) or both? I think it is best if it only does one or the other. That way the number of output rows is clear.

[JkSelf]

@westonpace Thanks for your reply.

WindowRel should not use WindowFunction. Instead, copy the fields that you need (I think it will be similar to ScalarFunction) into a separate message that is local to WindowRel. For example, WindowRel::Function will not have sorts. This way there is no confusion which instance of sorts should be used.

Yes. We can define a WindowRel::Function with not sorts. But this will bring ambiguity in understanding, because WindowRel is originally designed to perform a series of Window functions on a specific partition. And it will also bring redundancy in the code, because both functions need to define Bound. Can we remove the sort in WindowFunction here? If not, I will add a new Function later.

We should update physical_relations.md to reflect this new operator. Currently, there is "Hashing Window Operator" and "Streaming Window Operator". Does this replace one of these? Or is it a third kind of node? Or does "Hashing" and "Streaming" not make sense and we should combine them into this?

The difference between Hashing and Steaming is whether it is necessary to obtain the entire partition before execution described in WindowType. For example, SUM does not need it, but NTILE does. The WindowRel we support here includes these two situations.

Does this operator handle "scalar window functions" (e.g. SELECT RANK() OVER (ORDER BY time)) or "window aggregates" (e.g. SELECT SUM(val) OVER (PARTITION BY month)) or both? I think it is best if it only does one or the other. That way the number of output rows is clear.

If we use WindowFunction without sort here, we need to support both here. Because the current WindowFunction supports both here.

[westonpace]

Yes. We can define a WindowRel::Function with not sorts. But this will bring ambiguity in understanding, because WindowRel is originally designed to perform a series of Window functions on a specific partition. And it will also bring redundancy in the code, because both functions need to define Bound.

I think this redundancy is expected when we have logical and physical operators. For example, the physical HashJoinRel::left_keys and HashJoinRel::right_keys are narrower, but redundant, when compared with the logical JoinRel::expression.

Can we remove the sort in WindowFunction here?

No, because the logical representation needs to be able to stand alone. It should be legal to have a "purely logical plan" that has WindowFunction but no WindowRel (the window functions would be part of a ProjectRel).

The difference between Hashing and Steaming is whether it is necessary to obtain the entire partition before execution described in WindowType. For example, SUM does not need it, but NTILE does.

Yes. Also, streaming could make sense if the data was also sorted by the partition field.

The WindowRel we support here includes these two situations.

Ok, then I think we need to add a new relation to physical_relations.md which is WindowOperation. Perhaps:

## Window Operation

A window operation is a special type of project operation where every function
is a window function and all of the window functions share the same sorting and
partitioning.  This allows for the sort and partition to be calculated once and
shared between the various function evaluations.

| Signature | Value |
...

### Window Operation Properties

| Property | Description | Required |
...

## Hashing Window Operation
...

[westonpace]

If we use WindowFunction without sort here, we need to support both here. Because the current WindowFunction supports both here.

Ok, I agree this should support both. However, the output of an aggregate window function is scalar. In other words:

Given x=[1,2,3,4] then SUM(x) OVER () is [10, 10, 10, 10] and not [10].

[JkSelf]

If we use WindowFunction without sort here, we need to support both here. Because the current WindowFunction supports both here.

Ok, I agree this should support both. However, the output of an aggregate window function is scalar. In other words:

Given x=[1,2,3,4] then SUM(x) OVER () is [10, 10, 10, 10] and not [10].

Yes. the sum(x) over() return [10, 10, 10, 10] and also the rank() over() return [1, 2, 3, 4]. They all return a single value for each row. So I think the output of rows is same both "scalar window functions" and "window aggregates".

[JkSelf]

@westonpace Thanks for your detailed explanation. I will define a new function without sort to replace the Window function. And also update the physical_relations.md based on your suggestions later.

[baibaichen]

@westonpace is this ok to merge?

[JkSelf]

@westonpace Can you help to review again? Thanks for your help.

[jacques-n]

A few minor comments. I'm not sure I understand the comparison to hashing and streaming yet.

@jacques-n is there any engine out there that uses hashing to calculate window functions? If not, then we should get rid of the hashing and streaming operators.

I'm fine with not implementing this for now.

[vbarua]

Per discussion in the sync this morning, @westonpace and I have merged in main and applied some small changes to move this along.

[westonpace]

Structurally I think we've reached the correct point for this PR. I have some minor suggestions regarding how we document this. We recently updated (or are updating) the wording of WindowFunction.function_reference to state that we allow both window and aggregate functions. However, that change is not mirrored here.

Rather than try and keep the comments in sync between the two definitions I think we should only have one set of definitions and only document the parts that are different here.

I'm marking this as approved because this PR has been around for a while. If these changes are not addressed then I propose we merge it as is and clean up the docs in a follow-up PR.

[JkSelf]

@vbarua @westonpace @jacques-n
Sorry for the late response. I have updated the changes. Can you help to review again?

[jacques-n]

lgtm