Support window functions with empty OVER clause

[Dandandan]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.
Window functions are a very valuable feature to have for DataFusion, as it allows to do analytical queries and things like deduplication to happen.

Describe the solution you'd like
Initial support for window functions with OVER () clause. This allows us to gradually add more features, like support for PARTITION BY and ORDER BY.

Describe alternatives you've considered
A more complete implementation in one go. Window functions however are a big feature and we probably need quite some iterations to get it in shape.

Additional context
Some material:
http://www.vldb.org/pvldb/vol8/p1058-leis.pdf&ved=2ahUKEwj80-3OjrfwAhUJPOwKHfdRAssQFjAMegQIEhAC&usg=AOvVaw2KKUPeYhyc-pEFTmlqyboj

[jimexist]

@Dandandan i wonder how window function shall fit into the logical planner? it shall be folded into aggregate functions? but the actual output schema might be different.

[Dandandan]

@jimexist I think a new operator might be the best to do here. They have very different semantics and needs.

Between the operators there probably is still a lot of opportunity for reuse and in the planner we can use different operators (repartition, merge, sort, etc.)

What do you think?

@jorgecarleitao @alamb

[alamb]

I think a new operator might be the best to do here. They have very different semantics and needs.

I agree that a new operator (along with a new kind of aggregate) is probably best here -- the way window aggregate functions are applied is different than "normal" aggregates -- among other things for a window function there is typically one row of output for each row of input whereas normal aggregates produce one row of output for each distinct value of grouping keys.

[jimexist]

See #334 for a general idea of how much code change is needed if we'd add window function side by side with aggregates

[jimexist]

We'd like to support window function in three or more steps:

1. Support window functions with basic logical planning and physical planning #359 basic structure
2. Support window functions with empty OVER clause #298 empty over clause (this one)
3. Support window functions with PARTITION BY clause #299 with partition clause
4. Support window functions with order by #360 with order by
5. Support window functions with window frame #361 with window frame

[jimexist]

• add window expression stream, delegated window aggregation to aggregate functions, and implement row_number #375 to add window function support, streaming, and row_number
• add first_value, last_value, and nth_value built-in window functions #403 first_value, last_value, and nth_value
• implement lead and lag built-in window function #429 lead and lag

[jimexist]

• add window expression stream, delegated window aggregation to aggregate functions, and implement row_number #375 to add window function support, streaming, and row_number
• add first_value, last_value, and nth_value built-in window functions #403 first_value, last_value, and nth_value
• implement lead and lag built-in window function #429 lead and lag

@alamb and @Dandandan feel free to review in order