[Epic] Unify WindowFunction Interface (remove built in list of BuiltInWindowFunction s)

[alamb]

Is your feature request related to a problem or challenge?

For many of the same reasons as listed on #8045, having two types of aggregate functions ("built in" --BuiltInWindowFunction and WindowUDF is problematic for two reasons:

1. There are some features that may not be available to User Defined Window Functions (such as reversing FIRST_VALUE and LAST_VALUE)
2. Users can not easily choose which window functions to include (which will likely be especially problematic as we work to add more functions)

Describe the solution you'd like

I propose moving DataFusion to only use WindowURFs and remove BuiltInWindowFunction for the same reasons as #8045

We will keep the existing WindowUDF interface as much as possible, while also potentially providing an easier way to define them.

Describe alternatives you've considered

Additional context

Proposed implementation steps:

• Implement trait based API for defining WindowUDF #8711
• Clean internal implementation of WindowUDF to use WindowUDFImpl (rather than the function pointers) #8734
• Add a WindowUDFImpl::simplfy() API #9527
• Convert built-in row_number to user-defined window function #12029
• Convert nth_value to UDAF #11287
• Add field trait method to WindowUDFImpl #12373
• Convert built-in row_number to user-defined window function #12030
• Convert BuiltInWindowFunction::{Rank, PercentRank, DenseRank} to a user defined functions #12648
• Convert BuiltInWindowFunction::{NthValue} to a user defined functions #12649
• Convert BuiltInWindowFunction::Ntile to a user defined window function #12694
• Convert BuiltInWindowFunction::CumeDist to a user defined window function #12695
• Convert BuiltInWindowFunction::{Lead, Lag} to a user defined window function #12802

[comphead]

I'd like to try a small POC and migrate ROW_NUMBER to WindowUDF trait

[alamb]

I'd like to try a small POC and migrate ROW_NUMBER to WindowUDF trait

That would be awesome. Thank you

I recommend trying to put it in its own crate if possible (datfusion-window-functions perhaps?) but that doesn't have to be part of the POC

[timsaucer]

I'm going to move back to working on datafusion-python for a bit, but would like to work on this afterwards.

Also I think we have some functions that are implemented in aggregate that should be moved to window. Namely first_value and last_value but it's worth taking a look through all the functions to see where they are defined.

Notes (for myself) on how postgresql divides them:

• https://www.postgresql.org/docs/current/functions-aggregate.html
• https://www.postgresql.org/docs/current/functions-window.html

[jcsherin]

I filed a few more good first issues because of interest from new contributors,

• Convert BuiltInWindowFunction::Ntile to a user defined window function #12694
• Convert BuiltInWindowFunction::CumeDist to a user defined window function #12695

[alamb]

Thank you @jcsherin -- I added it tothe list above