Re: Row pattern recognition

On 6/25/23 14:05, Tatsuo Ishii wrote:
> Attached is a PoC patch to implement "Row pattern recognition" (RPR)
> in SQL:2016 (I know SQL:2023 is already out, but I don't have access
> to it). Actually SQL:2016 defines RPR in two places[1]:
> 
>      Feature R010, “Row pattern recognition: FROM clause”
>      Feature R020, “Row pattern recognition: WINDOW clause”
> 
> The patch includes partial support for R020 part.

I have been dreaming of and lobbying for someone to pick up this 
feature.  I will be sure to review it from a standards perspective and 
will try my best to help with the technical aspect, but I am not sure to 
have the qualifications for that.

THANK YOU!

 > (I know SQL:2023 is already out, but I don't have access to it)

If you can, try to get ISO/IEC 19075-5 which is a guide to RPR instead 
of just its technical specification.

https://www.iso.org/standard/78936.html

> - What is RPR?
> 
> RPR provides a way to search series of data using regular expression
> patterns. Suppose you have a stock database.
> 
> CREATE TABLE stock (
>         company TEXT,
>         tdate DATE,
>         price BIGINT);
> 
> You want to find a "V-shaped" pattern: i.e. price goes down for 1 or
> more days, then goes up for 1 or more days. If we try to implement the
> query in PostgreSQL, it could be quite complex and inefficient.
> 
> RPR provides convenient way to implement the query.
> 
> SELECT company, tdate, price, rpr(price) OVER w FROM stock
>   WINDOW w AS (
>   PARTITION BY company
>   ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
>   PATTERN (START DOWN+ UP+)
>   DEFINE
>    START AS TRUE,
>    UP AS price > PREV(price),
>    DOWN AS price < PREV(price)
> );
> 
> "PATTERN" and "DEFINE" are the key clauses of RPR. DEFINE defines 3
> "row pattern variables" namely START, UP and DOWN. They are associated
> with logical expressions namely "TRUE", "price > PREV(price)", and
> "price < PREV(price)". Note that "PREV" function returns price column
> in the previous row. So, UP is true if price is higher than previous
> day. On the other hand, DOWN is true if price is lower than previous
> day.  PATTERN uses the row pattern variables to create a necessary
> pattern.  In this case, the first row is always match because START is
> always true, and second or more rows match with "UP" ('+' is a regular
> expression representing one or more), and subsequent rows match with
> "DOWN".
> 
> Here is the sample output.
> 
>   company  |   tdate    | price | rpr
> ----------+------------+-------+------
>   company1 | 2023-07-01 |   100 |
>   company1 | 2023-07-02 |   200 |  200 -- 200->150->140->150
>   company1 | 2023-07-03 |   150 |  150 -- 150->140->150
>   company1 | 2023-07-04 |   140 |
>   company1 | 2023-07-05 |   150 |  150 -- 150->90->110->130
>   company1 | 2023-07-06 |    90 |
>   company1 | 2023-07-07 |   110 |
>   company1 | 2023-07-08 |   130 |
>   company1 | 2023-07-09 |   120 |
>   company1 | 2023-07-10 |   130 |
> 
> rpr shows the first row if all the patterns are satisfied. In the
> example above 200, 150, 150 are the cases.  Other rows are shown as
> NULL. For example, on 2023-07-02 price starts with 200, then goes down
> to 150 then 140 but goes up 150 next day.

I don't understand this.  RPR in a window specification limits the 
window to the matched rows, so this looks like your rpr() function is 
just the regular first_value() window function that we already have?

> As far as I know, only Oracle implements RPR (only R010. R020 is not
> implemented) among OSS/commercial RDBMSs. There are a few DWH software
> having RPR. According to [2] they are Snowflake and MS Stream
> Analytics. It seems Trino is another one[3].

I thought DuckDB had it already, but it looks like I was wrong.

> - Note about the patch
> 
> The current implementation is not only a subset of the standard, but
> is different from it in some places. The example above is written as
> follows according to the standard:
> 
> SELECT company, tdate, startprice OVER w FROM stock
>   WINDOW w AS (
>   PARTITION BY company
>   MEASURES
>    START.price AS startprice
>   ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
>   PATTERN (START DOWN+ UP+)
>   DEFINE
>    START AS TRUE,
>    UP AS UP.price > PREV(UP.price),
>    DOWN AS DOWN.price < PREV(DOWN.price)
> );
> 
> Notice that rpr(price) is written as START.price and startprice in the
> standard. MEASURES defines variable names used in the target list used
> with "OVER window". As OVER only allows functions in PostgreSQL, I had
> to make up a window function "rpr" which performs the row pattern
> recognition task.  I was not able to find a way to implement
> expressions like START.price (START is not a table alias). Any
> suggestion is greatly appreciated.

As in your example, you cannot have START.price outside of the window 
specification; it can only go in the MEASURES clause.  Only startprice 
is allowed outside and it gets its qualification from the OVER.  Using 
w.startprice might have been better but that would require window names 
to be in the same namespace as range tables.

This currently works in Postgres:

   SELECT RANK() OVER w
   FROM (VALUES (1)) AS w (x)
   WINDOW w AS (ORDER BY w.x);

> The differences from the standard include:
> 
> o MEASURES is not supported
 > o FIRST, LAST, CLASSIFIER are not supported
 > o PREV/NEXT in the standard accept more complex arguments
 > o INITIAL or SEEK are not supported ((behaves as if INITIAL is specified)

Okay, for now.

> o SUBSET is not supported

Is this because you haven't done it yet, or because you ran into 
problems trying to do it?

> o Regular expressions other than "+" are not supported

This is what I had a hard time imagining how to do while thinking about 
it.  The grammar is so different here and we allow many more operators 
(like "?" which is also the standard parameter symbol).  People more 
expert than me will have to help here.

> o Only AFTER MATCH SKIP TO NEXT ROW is supported (if AFTER MATCH is
>    not specified, AFTER MATCH SKIP TO NEXT ROW is assumed. In the
>    standard AFTER MATCH SKIP PAST LAST ROW is assumed in this case). I
>    have a plan to implement AFTER MATCH SKIP PAST LAST ROW though.

In this case, we should require the user to specify AFTER MATCH SKIP TO 
NEXT ROW so that behavior doesn't change when we implement the standard 
default.  (Your patch might do this already.)

> o Aggregate functions associated with window clause using RPR do not respect RPR

I do not understand what this means.

> It seems RPR in the standard is quite complex. I think we can start
> with a small subset of RPR then we could gradually enhance the
> implementation.

I have no problem with that as long as we don't paint ourselves into a 
corner.

> Comments and suggestions are welcome.

I have not looked at the patch yet, but is the reason for doing R020 
before R010 because you haven't done the MEASURES clause yet?

In any case, I will be watching this with a close eye, and I am eager to 
help in any way I can.
-- 
Vik Fearing