Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

sql: Add support for specifying window frames for window functions #26464

Closed
yuzefovich opened this issue Jun 6, 2018 · 2 comments
Closed

sql: Add support for specifying window frames for window functions #26464

yuzefovich opened this issue Jun 6, 2018 · 2 comments
Assignees
@yuzefovich
Labels
C-enhancement Solution expected to add code/behavior + preserve backward-compat (pg compat issues are exception)

Comments

@yuzefovich
Copy link
Member

yuzefovich commented Jun 6, 2018 •
edited
Loading

Currently, CRDB cannot execute queries with window functions that use window frames. For example, a query like SELECT avg(price) OVER (PARTITION BY product_type ORDER BY price ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING) AS avg_price FROM products; (that calculates an average price of some item along with one 'before' and one 'after' when ordered by price within items of the same product_type) is not supported.

Window frame can be specified with ROWS (how many physical rows before and after the row in consideration to include into the frame for computing) and RANGE (logical rows before and after - i.e. include only items that cost 100 less and 200 more than current item).

Ideally, CRDB would support at least the same subset of options as PostgreSQL (which, for example, does not support value PRECEDING and value FOLLOWING in RANGE mode).
https://www.postgresql.org/docs/9.1/static/sql-expressions.html#SYNTAX-WINDOW-FUNCTIONS

Implementing basic approaches of computing of window functions over window frames should not be too much of work since almost everything needed is already in place. However, applying more advanced approaches like using Segment Trees as suggested in http://www.vldb.org/pvldb/vol8/p1058-leis.pdf seems to be significantly more involved.
@yuzefovich yuzefovich self-assigned this Jun 6, 2018
@yuzefovich yuzefovich added C-enhancement Solution expected to add code/behavior + preserve backward-compat (pg compat issues are exception) A-sql-local labels Jun 6, 2018
@yuzefovich
Copy link
Member Author

cc @jordanlewis What do you think about using more advanced approaches? PostgreSQL seems to use only basic ideas, and if a particular query will be slow with such approach, they say that such query is not supported.

@yuzefovich yuzefovich mentioned this issue Jun 13, 2018
Merged
yuzefovich added a commit to yuzefovich/cockroach that referenced this issue Jun 13, 2018
@yuzefovich
sql: Add support for specifying window frames for window functions
939b7f5 
WIP on cockroachdb#26464:
ROWS mode is fully supported whereas RANGE works only with
UNBOUNDED PRECEDING/CURRENT ROW/UNBOUNDED FOLLOWING boundaries
(same as in PostgreSQL). Current implementation of aggregate functions
is naive (it simply computes the value of aggregate directly and
discards all the previous computations which results in quadratic time).

Release note (sql change): CockroachDB now supports custom frame
specification for window functions using ROWS (fully-supported)
and RANGE ('value' PRECEDING and 'value' FOLLOWING are not supported)
modes.
yuzefovich added a commit to yuzefovich/cockroach that referenced this issue Jun 13, 2018
@yuzefovich
sql: Add support for specifying window frames for window functions
e6141bb 
WIP on cockroachdb#26464:
ROWS mode is fully supported whereas RANGE works only with
UNBOUNDED PRECEDING/CURRENT ROW/UNBOUNDED FOLLOWING boundaries
(same as in PostgreSQL). Current implementation of aggregate functions
is naive (it simply computes the value of aggregate directly and
discards all the previous computations which results in quadratic time).

Release note (sql change): CockroachDB now supports custom frame
specification for window functions using ROWS (fully-supported)
and RANGE ('value' PRECEDING and 'value' FOLLOWING are not supported)
modes.
yuzefovich added a commit to yuzefovich/cockroach that referenced this issue Jun 14, 2018
@yuzefovich
sql: Add support for specifying window frames for window functions
91476b0 
WIP on cockroachdb#26464:
ROWS mode is fully supported whereas RANGE works only with
UNBOUNDED PRECEDING/CURRENT ROW/UNBOUNDED FOLLOWING boundaries
(same as in PostgreSQL). Current implementation of aggregate functions
is naive (it simply computes the value of aggregate directly and
discards all the previous computations which results in quadratic time).

Release note (sql change): CockroachDB now supports custom frame
specification for window functions using ROWS (fully-supported)
and RANGE ('value' PRECEDING and 'value' FOLLOWING are not supported)
modes.
yuzefovich added a commit to yuzefovich/cockroach that referenced this issue Jun 18, 2018
@yuzefovich
sql: Add support for specifying window frames for window functions
f0a04a1 
WIP on cockroachdb#26464:
ROWS mode is fully supported whereas RANGE works only with
UNBOUNDED PRECEDING/CURRENT ROW/UNBOUNDED FOLLOWING boundaries
(same as in PostgreSQL). Current implementation of aggregate functions
is naive (it simply computes the value of aggregate directly and
discards all the previous computations which results in quadratic time).

Release note (sql change): CockroachDB now supports custom frame
specification for window functions using ROWS (fully-supported)
and RANGE ('value' PRECEDING and 'value' FOLLOWING are not supported)
modes.
yuzefovich added a commit to yuzefovich/cockroach that referenced this issue Jun 19, 2018
@yuzefovich
sql: Add support for specifying window frames for window functions
433d30c 
WIP on cockroachdb#26464:
ROWS mode is fully supported whereas RANGE works only with
UNBOUNDED PRECEDING/CURRENT ROW/UNBOUNDED FOLLOWING boundaries
(same as in PostgreSQL). Current implementation of aggregate functions
is naive (it simply computes the value of aggregate directly and
discards all the previous computations which results in quadratic time).

Release note (sql change): CockroachDB now supports custom frame
specification for window functions using ROWS (fully-supported)
and RANGE ('value' PRECEDING and 'value' FOLLOWING are not supported)
modes.
yuzefovich added a commit to yuzefovich/cockroach that referenced this issue Jun 25, 2018
@yuzefovich
sql: Add support for specifying window frames for window functions
b007aa2 
WIP on cockroachdb#26464:
ROWS mode is fully supported whereas RANGE works only with
UNBOUNDED PRECEDING/CURRENT ROW/UNBOUNDED FOLLOWING boundaries
(same as in PostgreSQL). Current implementation of aggregate functions
is naive (it simply computes the value of aggregate directly and
discards all the previous computations which results in quadratic time).

Release note (sql change): CockroachDB now supports custom frame
specification for window functions using ROWS (fully-supported)
and RANGE ('value' PRECEDING and 'value' FOLLOWING are not supported)
modes.
craig bot pushed a commit that referenced this issue Jun 25, 2018
@yuzefovich
Merge #26666
98d2a12 
26666: sql: Add support for specifying window frames for window functions r=yuzefovich a=yuzefovich

WIP on #26464:
ROWS mode is fully supported whereas RANGE works only with
UNBOUNDED PRECEDING/CURRENT ROW/UNBOUNDED FOLLOWING boundaries
(same as in PostgreSQL). Current implementation of aggregate functions
is naive (it simply computes the value of aggregate directly and
discards all the previous computations which results in quadratic time).

Release note: None

Co-authored-by: yuzefovich <[email protected]>
@yuzefovich yuzefovich mentioned this issue Jun 26, 2018
Merged
yuzefovich added a commit to yuzefovich/cockroach that referenced this issue Jun 27, 2018
@yuzefovich
sql: Add efficient min, max, sum, avg when used as window functions.
a2c99f2 
Adds linear-time implementations of min, max, sum, and avg
(using sliding window approach) instead of naive quadratic
version.

Addresses: cockroachdb#26464.

Bonus: min and max are an order of magnitude faster than PG
(when window frame doesn't include the whole partition).

Release note (performance improvement): min, max, sum, avg
now take linear time when used for aggregation as window
functions.
@yuzefovich yuzefovich mentioned this issue Jun 27, 2018
Merged
yuzefovich added a commit to yuzefovich/cockroach that referenced this issue Jun 27, 2018
@yuzefovich
sql: Add full support for RANGE mode for window frames.
6319132 
Adds support for 'value' PRECEDING and 'value' FOLLOWING types
of bounds for window frames.

Addresses: cockroachdb#26464.

Release note (sql change): CockroachDB now fully supports
RANGE mode for specification of window frames.
yuzefovich added a commit to yuzefovich/cockroach that referenced this issue Jul 2, 2018
@yuzefovich
sql: Add full support for RANGE mode for window frames.
7806682 
Adds support for 'value' PRECEDING and 'value' FOLLOWING types
of bounds for window frames.

Addresses: cockroachdb#26464.

Release note (sql change): CockroachDB now fully supports
RANGE mode for specification of window frames.
yuzefovich added a commit to yuzefovich/cockroach that referenced this issue Jul 3, 2018
@yuzefovich
sql: Add efficient min, max, sum, avg when used as window functions.
d0ef4d6 
Adds linear-time implementations of min, max, sum, and avg
(using sliding window approach) instead of naive quadratic
version.

Addresses: cockroachdb#26464.

Bonus: min and max are an order of magnitude faster than PG
(when window frame doesn't include the whole partition).

Release note (performance improvement): min, max, sum, avg
now take linear time when used for aggregation as window
functions.
yuzefovich added a commit to yuzefovich/cockroach that referenced this issue Jul 10, 2018
@yuzefovich
sql: Add efficient min, max, sum, avg when used as window functions.
77ce2b7 
Adds linear-time implementations of min, max, sum, and avg
(using sliding window approach) instead of naive quadratic
version.

Addresses: cockroachdb#26464.

Bonus: min and max are an order of magnitude faster than PG
(when window frame doesn't include the whole partition).

Release note (performance improvement): min, max, sum, avg
now take linear time when used for aggregation as window
functions.
yuzefovich added a commit to yuzefovich/cockroach that referenced this issue Jul 16, 2018
@yuzefovich
sql: Add efficient min, max, sum, avg when used as window functions
63e6c0a 
Adds linear-time implementations of min, max, sum, and avg
(using sliding window approach) instead of naive quadratic
version.

Addresses: cockroachdb#26464.

Bonus: min and max are an order of magnitude faster than PG
(when window frame doesn't include the whole partition).

Release note (performance improvement): min, max, sum, avg
now take linear time when used for aggregation as window
functions for all supported window frame options.
craig bot pushed a commit that referenced this issue Jul 16, 2018
@yuzefovich
Merge #26988
c974dfb 
26988: sql: Add more efficient implementation of min, max, sum, avg aggregates when used as window functions. r=yuzefovich a=yuzefovich

Adds linear-time implementations of min, max, sum, and avg
(using sliding window approach) instead of naive quadratic
version.

Addresses: #26464.

Bonus: min and max is order of magnitude faster that PG
(when window frame doesn't include the whole partition).

Release note (performance improvement): min, max, sum, avg
now take linear time when used for aggregation as window
functions.

Co-authored-by: yuzefovich <[email protected]>
@yuzefovich
Copy link
Member Author

We now match features currently supported by PostgreSQL, so I'm closing this issue. Future related work will be addressed by #27100.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@yuzefovich yuzefovich

Labels
C-enhancement Solution expected to add code/behavior + preserve backward-compat (pg compat issues are exception)
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@yuzefovich