Implementing Row Pattern
Recognition
2024/05/29
PGConf.dev at
Vancouver Canada
SRA OSS LLC
Tatsuo Ishii

Who am I?
Working for SRA OSS LLC as an advisor●
PostgreSQL committer●

Internationalization of PostgreSQL●
pgbench, pgstattuple, pgrowlocks, Pgpool-II (anexternal project)●

Copyright(c) 2024 SRA OSS LLC

2

Today’s talk
What is Row Pattern Recognition?
●
Syntax of Row Pattern Recognition●
Implementation of Row Pattern Recognition
and future plans●
Demonstrations●

Copyright(c) 2024 SRA OSS LLC

3

What is Row Pattern Recognition (RPR)?
One of the features defined by the SQL standard●
Allow to search for a sequence of rows (e.g. time series data) by “pattern”●
Pattern definition list●

LOWPRICE AS price < 100●
UP AS price > PREV(price)●
DOWN AS price < PREV(price)●●

A pattern can be defined by using pattern variables and regular expressions●●

LOWPRICE UP+ DOWN+

Applications
Searching for stock price fluctuation patterns●
Detecting anomalous values●
And more●

Copyright(c) 2024 SRA OSS LLC

4

Row Pattern Recognition:
definition and implementation●

Relatively new feature first appeared in
SQL:2016●●

Called “SQL/RPR” in the standard

Only Oracle has this at present. No OSS
RDBMS has implemented this yet●

Some Analytics tools implement RPR–

https://trino.io/
Copyright(c) 2024 SRA OSS LLC

5

RPR example 1：detecting patterns in a time series data
Detail explained later
Value
Pattern of rising and then falling

Pattern of rising

Pattern of falling and then risingTime
Copyright(c) 2024 SRA OSS LLC

6

Search for patterns of rising and thenfallingcompany |tdate| priceRequirement----------+------------+------Company1 | 2023-07-01 |100
Company1 | 2023-07-02 |200
Company1 | 2023-07-03 |150
Company1 | 2023-07-04 |140
company1 | 2023-07-05 |150
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

START
UP
DOWN
DOWN
START
UP
UP
DOWN

Find sequences of rows of risingonce or more and then falling
once or more
Define “row patternvariables”
START AS TRUE,
UP AS price > PREV(price),
DOWN AS price < PREV(price)

Mapped to the first row
Mapped to the second or subsequent rows
Mapped to the third or subsequent rows
Copyright(c) 2024 SRA OSS LLC

START
UP+
DOWN+

Define sequenceof patterns using
regularexpressions
7

Actual query
SELECT company, tdate, price,
first_value(price) OVER w, -- the first row of the frame
last_value(price) OVER w-- the last row of the frame
FROM stock
WINDOW w AS (PARTITION BY company
ORDER BY tdate
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGAFTER MATCH SKIP PAST LAST ROWINITIALPATTERN (START UP+ DOWN+) -- define patterns
DEFINE-- define pattern variables
START AS TRUE,
UP AS price > PREV(price),
DOWN AS price < PREV(price));
Copyright(c) 2024 SRA OSS LLC

8

The resultcompany |tdate| price | first_value | last_value----------+------------+-------+-------------+-----------company1 | 2023-07-01 |
100 |
100 |
140
company1 | 2023-07-02 |200 ||company1 | 2023-07-03 |150 ||company1 | 2023-07-04 |140 ||company1 | 2023-07-05 |150 ||company1 | 2023-07-06 |
90 |
90 |
120
company1 | 2023-07-07 |110 ||company1 | 2023-07-08 |130 ||company1 | 2023-07-09 |120 ||company1 | 2023-07-10 |130 ||(10 rows)

Copyright(c) 2024 SRA OSS LLC

9

Example 2：detecting specific consecutive events
alert_time|
alert_msg|
first_alert|
last_alert---------------------+------------------------------+---------------------+--------------------2023-11-24 09:00:00 | Warning: device is not ready ||2023-11-24 09:01:00 | Log: device is busy||
2023-11-24 09:02:00 | Log: device is busy||
2023-11-24 09:03:00 | Warning: device is not ready ||2023-11-24 09:04:00 | Warning: device is not ready ||2023-11-24 09:05:00 | Warning: device is not ready ||2023-11-24 09:10:00 | Log: device is busy||
2023-11-24 09:20:00 | Log: device is busy||
2023-11-24 09:21:00 | Warning: device is not ready | 2023-11-24 09:21:00 | 2023-11-24 09:21:20
2023-11-24 09:21:10 | Warning: device is not ready ||2023-11-24 09:21:20 | Warning: device is not ready ||2023-11-24 09:22:00 | Log: device is busy||

Detect events where “Warning”
messages appear consecutively
within 30 seconds more than 3
times
Copyright(c) 2024 SRA OSS LLC

10

RPR expression
alert_time|
alert_msg---------------------+-----------------------------2023-11-24 09:00:00 | Warning: device is not ready2023-11-24 09:01:00 | Log: device is busy
2023-11-24 09:02:00 | Log: device is busy
2023-11-24 09:03:00 | Warning: device is not ready2023-11-24 09:04:00 | Warning: device is not ready2023-11-24 09:05:00 | Warning: device is not ready2023-11-24 09:10:00 | Log: device is busy
2023-11-24 09:20:00 | Log: device is busy
2023-11-24 09:21:00 | Warning: device is not ready2023-11-24 09:21:10 | Warning: device is not ready2023-11-24 09:21:20 | Warning: device is not ready2023-11-24 09:22:00 | Log: device is busy

Three or more consecutive messages
starting with "Warning" appear
within 30 seconds more than 3 times
Define “row patternvariable”
START AS alert_msg LIKE ‘Warning%’,WARNING AS alert_msg LIKE
‘Warning%’ AND (alert_time – PREV
(alert_time) < interval ‘30 seconds’

START
WARNINGWARNING+
Copyright(c) 2024 SRA OSS LLC

Define sequenceof patterns using
regularexpressions
11

Actual query
SELECT alert_time, alert_msg,
first_value(alert_time) OVER w AS first_alert,
last_value(alert_time) OVER w AS last_alert
FROM alerts
WINDOW w AS (PARTITION BY device_id
ORDER BY alert_time
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGINITIALPATTERN (START WARNING WARNING+)
DEFINESTART AS alert_msg LIKE 'Warning%',WARNING AS alert_msg LIKE 'Warning%' AND(alert_time - PREV(alert_time)) < interval '30 seconds');
Copyright(c) 2024 SRA OSS LLC

12

The result
alert_time|
alert_msg|
first_alert|
last_alert---------------------+------------------------------+---------------------+--------------------2023-11-24 09:00:00 | Warning: device is not ready ||2023-11-24 09:01:00 | Log: device is busy||
2023-11-24 09:02:00 | Log: device is busy||
2023-11-24 09:03:00 | Warning: device is not ready ||2023-11-24 09:04:00 | Warning: device is not ready ||2023-11-24 09:05:00 | Warning: device is not ready ||2023-11-24 09:10:00 | Log: device is busy||
2023-11-24 09:20:00 | Log: device is busy||
2023-11-24 09:21:00 | Warning: device is not ready | 2023-11-24 09:21:00 | 2023-11-24 09:21:20
2023-11-24 09:21:10 | Warning: device is not ready ||2023-11-24 09:21:20 | Warning: device is not ready ||2023-11-24 09:22:00 | Log: device is busy||

Copyright(c) 2024 SRA OSS LLC

13

Two different types of RPR●

Actually there are two different RPRs●

R010: Row pattern recognition: FROM clause–●

R020: Row pattern recognition: WINDOW clause–●●“MATCH_RECOGNIZE” clause after FROM. RPR is defined there
Define RPR in Window clause

R010 and R020 have many common definitions.

Why I wanted to implement RPR in WINDOW clause?
●

RPR needs to scan a set of tuples over and over again
Scanning in FROM clause in the same way is difficult as far as I know
WINDOW clause already has such an infrastructure–●●

We could be the first implementer of RPR in WINDOW clause in RDBMSs!
Copyright(c) 2024 SRA OSS LLC

14

Example query in R010
SELECT company, tdate, price, m.first_val, m.last_val
FROM stock
MATCH_RECOGNIZE(
PARTITION BY company
ORDER BY tdate
MEASURESFIRST(price) AS first_val,
LAST(price) AS last_val,
AFTER MATCH SKIP PAST LAST ROWPATTERN (START UP+ DOWN+)
DEFINESTART AS TRUE,
UP AS price > PREV(price),
DOWN AS price < PREV(price)) AS m;Copyright(c) 2024 SRA OSS LLC

15

Syntax of RPR
WINDOW window_name AS ([ PARTITION BY ... ][ ORDER BY... ][ MEASURES ... ]ROWS BETWEEN CURRENT ROW AND ...
[ AFTER MATCH SKIP ... ][ INITIAL|SEEK ]PATTERN (...)[ SUBSET ... ]DEFINE ...
)PARTITION BY, ORDER BY are same as in the Window clause without RPR
MEASURES and SUBSET are not implemented yet●
Some of sub clauses are not implemented yet●●

Copyright(c) 2024 SRA OSS LLC

16

ROWS BETWEENCURRENT ROW...
●

Specify the frame’s start and end. Same as
Window clause without RPR except only
below are allowed in RPR
ROWS BETWEEN CURRENT ROW AND
UNBOUNDED FOLLOWING●ROWS BETWEEN CURRENT ROW AND n
FOLLOWING●

Copyright(c) 2024 SRA OSS LLC

17

AFTER MATCH SKIP...
Only valid with RPR●
Specify where to start the next
pattern matching after the patternmatching ends

Current match●●

AFTER MATCH SKIP TO NEXT ROW–●AFTER MATCH SKIP PAST LAST ROW–●Skip to next row regardless the previous
matching rows
Skip current matching rows and move tonext row

AFTER MATCH SKIP TO FIRST|LAST
pattern_variable–

company |tdate| price----------+------------+------company1 | 2023-07-01 |100
company1 | 2023-07-02 |200
company1 | 2023-07-03 |150
company1 | 2023-07-04 |140
company1 | 2023-07-05 |150
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

Not supported

Copyright(c) 2024 SRA OSS LLC

18

INITIAL|SEEK
Only valid with RPR●
INITIAL●

Pattern match succeeds only when the set of matching rows
starts from the first row of a frame●
The default
●

●

SEEK
Pattern match succeeds even if the set of matching rows do notstarts from the first row of a frame●
Not supported in the current patches●

Copyright(c) 2024 SRA OSS LLC

19

DEFINE (1)Only valid with RPR●
Define pattern_definition _ist●●

DEFINE variable_name AS search_condition, …
–●

search_condition is a boolean logical expression

Example pattern definitions
START AS TRUE
– LOWPRICE AS price < 100– UP AS price > PREV(price)– UP AS price > 100 AND price < PREV(price)–

Copyright(c) 2024 SRA OSS LLC

20

DEFINE (2)●Row pattern navigation operations can be used in
DEFINE clause
FIRST, LAST, PREV, NEXT●
Only PREV/NEXT are supported in the current patches●●

Following are not supported in the current patch
CLASSIFIER (function returning the variable name whichmatches the pattern)●
Aggregates●
Subqueries●

Copyright(c) 2024 SRA OSS LLC

21

PATTERN (1)●Describe the patterns to be matched using
variables in the DEFINE clause●

PATTERN (START UP+ DOWN+)
Match with START (the first row)
– 1 or more rows matching UP follow– 1 or more rows matching DOWN follow–●

If a variable A which was not defined in DEFINE
clause appears, it is regarded AS “A is TRUE”

Copyright(c) 2024 SRA OSS LLC

22

PATTERN(2)●The standard allows following regular expressions with pattern variable+: 1 or more rows●*: 0 or more rows●?: 0 or 1 row●
A | B: OR condition●(A B): grouping●{n}: n rows●{n,}: n or more rows●{n,m}: greater or equal to n rows and less than or equal to m rows●{,m}: more than 0 and less than or equal to m rows●●

The current patch only supports “+”and“*”Copyright(c) 2024 SRA OSS LLC

23

Handling aggregates in the target list
Basically same as aggregates in Windowclause without RPR●
Except that the aggregate is applied to only
matched rows if RPR clause exists●

Copyright(c) 2024 SRA OSS LLC

24

Example aggregate functions
SELECT company, tdate, price,
count(*) OVER w1 AS count1,
count(*) OVER w2 AS count2
FROM stock
WINDOW w1 AS (PARTITION BY company
ORDER BY tdate
ROWS BETWEEN CURRENT ROW AND
UNBOUNDED FOLLOWING),
w2 AS (PARTITION BY company
ORDER BY tdate
ROWS BETWEEN CURRENT ROW AND
UNBOUNDED FOLLOWINGAFTER MATCH SKIP PAST LAST ROWINITIALPATTERN (START UP+ DOWN+)
DEFINESTART AS TRUE,
UP AS price > PREV(price),
DOWN AS price < PREV(price));company |tdate| price | count1 | count2----------+------------+-------+--------+-------company1 | 2023-07-01 |
100 |
10 |
4
company1 | 2023-07-02 |
200 |
9 |
0
company1 | 2023-07-03 |
150 |
8 |
0
company1 | 2023-07-04 |
140 |
7 |
0
company1 | 2023-07-05 |
150 |
6 |
0
company1 | 2023-07-06 |
90 |
5 |
4
company1 | 2023-07-07 |
110 |
4 |
0
company1 | 2023-07-08 |
130 |
3 |
0
company1 | 2023-07-09 |
120 |
2 |
0
company1 | 2023-07-10 |
130 |
1 |
0
(10 rows)

Copyright(c) 2024 SRA OSS LLC

25

About RPR Patch
Implemented in the WINDOW clause●
Proposing patches for PostgreSQL 18 in pgsql-hackers●

https://www.postgresql.org/message-id/
20230625.210509.1276733411677577841.t-ishii%40sranhm.sra.co.jp●
Patches are for the parser, planner, executor, tests and docs.
about 3,000 lines (without tests and documents)●
New regression test is added to src/test/regress/sql/rpr.sql●

Copyright(c) 2024 SRA OSS LLC

26

Implementation of patternmatching using regular expressions
PATTERN (START UP+ DOWN+)
DEFINESTART AS TRUE,
UP AS price > PREV(price),
DOWN AS price < PREV(price)

price matched variables-------------------------------100
START
200
START UP
150
START DOWN
140
START DOWN
150
START UPThe pattern match results
are expressed as strings.
Then do regular expression
Pattern matching
Using regular expression search against the strings

Generate possible combinations
START START START START START
START UP START START START
START UP DOWN START START
START UP DOWN START START::
START UP DOWN DOWN UP

START UP+ DOWN+

The longest match is the
Final result

START UP DOWN DOWN UP

Copyright(c) 2024 SRA OSS LLC

27

Future plans●

TODO toward PostgreSQL v18●

Enhance the pattern matching engine–●

Less memory consumption

TODO after the first commit●

Implement more features
MEASURE, SUBSET– More regular expressions– And more...
–Copyright(c) 2024 SRA OSS LLC

28

Demonstrations

Copyright(c) 2024 SRA OSS LLC

29

Search for “extreme hot days”●

What is “extreme hot day”?
●●

A day whose maximum temperature exceeds 35
degrees Celsius (95 degrees Fahrenheit)

What are “extreme hot days”?
●

Consecutive extreme hot days

Copyright(c) 2024 SRA OSS LLC

30

The data
Max temperature in a
day in major cities
around Tokyo, Japan●
Data wasdownloaded fromJapan Meteorological
Agency web page●https://www.data.jma.go.jp/risk/obsdl/index.php
Copyright(c) 2024 SRA OSS LLC

Map: Wikipedia
31

The table
CREATE TABLE summer_temperature (city text NOT NULL,
date date NOT NULL,
highest_tmp numeric(4,2) NOT NULL,
lowest_tmp numeric(4,2) NOT NULL);

Copyright(c) 2024 SRA OSS LLC

32

Search for the number ofconsecutive extreme hot days
Step 1: create a query to find consecutive extreme hot days
SELECT city, date, highest_tmp, lowest_tmp,
first_value(highest_tmp) OVER w,
last_value(highest_tmp) OVER w,
max(highest_tmp) OVER w AS high_max,
Number of rows matching
count(*) OVER w AS duration,
the pattern “M”
avg(highest_tmp) OVER w AS average
FROM summer_temperature
WINDOW w AS (Frames are created for
PARTITION BY cityeach city and rows are
ORDER BY date
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
ordered by date
AFTER MATCH SKIP PAST LAST ROWINITIALPATTERN (START M+)
Max temperature in the
DEFINE
current row exceeds 35
START AS TRUE,
M AS highest_tmp >= 35 AND PREV(highest_tmp) >= 35
and the one in the);previous row also exceeds

35
Copyright(c) 2024 SRA OSS LLC

33

Search for consecutive extreme hot days
longer than 5 days
Step 2: create a view from the step 1 query
CREATE VIEW extreme_hot_days AS
SELECT city, date, highest_tmp, lowest_tmp,
first_value(highest_tmp) OVER w,
last_value(highest_tmp) OVER w,
max(highest_tmp) OVER w AS high_max,
count(*) OVER w AS duration,
avg(highest_tmp) OVER w AS average
FROM summer_temperature
WINDOW w AS (PARTITION BY city
ORDER BY date
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWINGAFTER MATCH SKIP PAST LAST ROWINITIALPATTERN (START M+)
DEFINESTART AS TRUE,
M AS highest_tmp >= 35 AND PREV(highest_tmp) >= 35);
Copyright(c) 2024 SRA OSS LLC

34

Search for the number ofconsecutive extreme hot days
longer than 5 days
Step 3: query against the view
SELECT city, date as start_date, high_max,
duration, trunc(average,2) AS avg FROM extreme_hot_days
WHERE duration::integer >= 5
ORDER BY duration::integer DESC;
city| start_date | high_max | duration | avg------------+------------+----------+----------+------Kofu| 2023-07-23 |38.70 |
9 | 37.32
Maebashi| 2023-07-24 |38.90 |
8 | 38.05
Saitama| 2023-07-24 |38.80 |
8 | 37.72
Tokyo| 2023-07-24 |37.70 |
8 | 36.43
Utsunomiya | 2023-07-25 |37.00 |
7 | 36.35
Maebashi| 2023-08-02 |38.20 |
6 | 36.70
Maebashi| 2023-08-17 |36.00 |
5 | 35.64(7 rows)
Copyright(c) 2024 SRA OSS LLC

35

References
ISO/IEC 19075-5 “Information technology – Guidance for the useof database language SQL – Part5: Row Pattern Recognition”●
Specification of Row Pattern Recognition in the SQL Standard andits Implementations●●●

Trino 426 Documentation (MATCH_RECOGNIZE)●●

https://link.springer.com/article/10.1007/s13222-022-00404-3
https://trino.io/docs/current/sql/match-recognize.html

Trino 426 Documentation (Row pattern recognition in window
structures)●https://trino.io/docs/current/sql/pattern-recognition-in-window.htm
Copyright(c) 2024 SRA OSS LLC

36