The goal of the MADlib path function is to perform regular pattern matching over a sequence of rows, and to extract useful information about the pattern matches. The useful information could be a simple count of matches or something more involved like aggregations or window functions.
Symbols are used to identify particular rows of interest. Then, standard PostgreSQL pattern matching using symbols can be applied to identify patterns across the rows of interest. (This is similar in concept to regular expressions which match patterns within strings of text.)
For example, a symbol can be defined for purchase events by on-line shoppers. Then, preceding events that led to the purchase can be identified and operated on, perhaps to find the common actions that resulted in a purchase. Or conversely, to find actions that resulted in an exit without a purchase having been made.
Steps on how to use path functions:
path( source_table, output_table, partition_expr, order_expr, symbol, pattern, aggregate_func, persist_rows, overlapping_patterns )
Arguments
VARCHAR. Name of the source table, containing data for path analysis.
VARCHAR. Name of the result table.
VARCHAR. The 'partition_expr' can be a single column or a list of comma-separated columns/expressions to divide all rows into groups, or partitions. Matching is applied across the rows that fall into the same partition. This can be NULL or '' to indicate the matching is to be applied to the whole table.
VARCHAR. This expression controls the order in which rows are processed or matched in a partition. For example, time is a common way to order partitions.
VARCHAR. Symbols enable you to express patterns of interest in a simple way (see definition of ‘pattern’ argument below). A symbol identifies a row of a particular type that you’re searching for as part of a pattern match. Symbol definition uses the standard PostgreSQL assignment statement 'identifier := expression;' [1]. A given row can only match one symbol. If a row matches multiple symbols, the symbol that comes first in the symbol definition list will take precedence.
VARCHAR. The 'pattern' clause defines the pattern that the path algorithm searches for. You express the pattern using symbols and operators following regular PostgreSQL pattern matching syntax and rules [2].
The following pattern matching metacharacters are supported:
VARCHAR, default NULL. A comma-separated list of aggregates to be applied to the pattern matches [3]. You can think of this input parameter as being like a SELECT clause. Please note that window functions cannot currently be used in the parameter 'aggregate_func'. If you want to use a window function [4], output the pattern matches and write a SQL query with a window function over the output tuples (see 'persist_rows' parameter below).
If you just want to output the pattern matched rows and not compute any aggregates, you can put NULL or '' in the 'aggregate_func' parameter.
BOOLEAN, default FALSE. If TRUE the matched rows are persisted in a separate output table. This table is named as <output_table>_tuples (the string "_tuples" is added as suffix to the value of output_table).
BOOLEAN, default FALSE. If TRUE find every occurrence of the pattern in the partition, regardless of whether it might have been part of a previously found match.
The data set describes shopper behavior on a notional web site that sells beer and wine. A beacon fires an event to a log file when the shopper visits different pages on the site: landing page, beer selection page, wine selection page, and checkout. Other pages on the site like help pages show up in the logs as well. Let’s assume that the log has been sessionized.
DROP TABLE IF EXISTS eventlog; CREATE TABLE eventlog (event_timestamp TIMESTAMP, user_id INT, session_id INT, page TEXT, revenue FLOAT); INSERT INTO eventlog VALUES ('04/15/2015 01:03:00', 100821, 100, 'LANDING', 0), ('04/15/2015 01:04:00', 100821, 100, 'WINE', 0), ('04/15/2015 01:05:00', 100821, 100, 'CHECKOUT', 39), ('04/15/2015 02:06:00', 100821, 101, 'WINE', 0), ('04/15/2015 02:09:00', 100821, 101, 'WINE', 0), ('04/15/2015 01:15:00', 101121, 102, 'LANDING', 0), ('04/15/2015 01:16:00', 101121, 102, 'WINE', 0), ('04/15/2015 01:17:00', 101121, 102, 'CHECKOUT', 15), ('04/15/2015 01:18:00', 101121, 102, 'LANDING', 0), ('04/15/2015 01:19:00', 101121, 102, 'HELP', 0), ('04/15/2015 01:21:00', 101121, 102, 'WINE', 0), ('04/15/2015 01:22:00', 101121, 102, 'CHECKOUT', 23), ('04/15/2015 02:15:00', 101331, 103, 'LANDING', 0), ('04/15/2015 02:16:00', 101331, 103, 'WINE', 0), ('04/15/2015 02:17:00', 101331, 103, 'HELP', 0), ('04/15/2015 02:18:00', 101331, 103, 'WINE', 0), ('04/15/2015 02:19:00', 101331, 103, 'CHECKOUT', 16), ('04/15/2015 02:22:00', 101443, 104, 'BEER', 0), ('04/15/2015 02:25:00', 101443, 104, 'CHECKOUT', 12), ('04/15/2015 02:29:00', 101881, 105, 'LANDING', 0), ('04/15/2015 02:30:00', 101881, 105, 'BEER', 0), ('04/15/2015 01:05:00', 102201, 106, 'LANDING', 0), ('04/15/2015 01:06:00', 102201, 106, 'HELP', 0), ('04/15/2015 01:09:00', 102201, 106, 'LANDING', 0), ('04/15/2015 02:15:00', 102201, 107, 'WINE', 0), ('04/15/2015 02:16:00', 102201, 107, 'BEER', 0), ('04/15/2015 02:17:00', 102201, 107, 'WINE', 0), ('04/15/2015 02:18:00', 102871, 108, 'BEER', 0), ('04/15/2015 02:19:00', 102871, 108, 'WINE', 0), ('04/15/2015 02:22:00', 102871, 108, 'CHECKOUT', 21), ('04/15/2015 02:25:00', 102871, 108, 'LANDING', 0), ('04/15/2015 02:17:00', 103711, 109, 'BEER', 0), ('04/15/2015 02:18:00', 103711, 109, 'LANDING', 0), ('04/15/2015 02:19:00', 103711, 109, 'WINE', 0);
DROP TABLE IF EXISTS path_output, path_output_tuples; SELECT madlib.path( 'eventlog', -- Name of input table 'path_output', -- Table name to store path results 'session_id', -- Partition input table by session 'event_timestamp ASC', -- Order partitions in input table by time 'buy:=page=''CHECKOUT''', -- Define a symbol for checkout events '(buy)', -- Pattern search: purchase 'sum(revenue) as checkout_rev', -- Aggregate: sum revenue by checkout TRUE -- Persist matches ); SELECT * FROM path_output ORDER BY session_id, match_id;Result:
session_id | match_id | checkout_rev ------------+----------+-------------- 100 | 1 | 39 102 | 1 | 15 102 | 2 | 23 103 | 1 | 16 104 | 1 | 12 108 | 1 | 21 (6 rows)Note that there are 2 checkouts within session 102, which is apparent from the 'match_id' column. This serves to illustrate that the 'aggregate_func' operates on a per pattern match basis, not on a per partition basis. If in fact we wanted revenue by partition ('session_id' in this example), then we could do:
SELECT session_id, sum(checkout_rev) FROM path_output GROUP BY session_id ORDER BY session_id;Result:
session_id | sum ------------+----- 100 | 39 102 | 38 103 | 16 104 | 12 108 | 21 (5 rows)Since we set TRUE for 'persist_rows', we can view the associated pattern matches:
SELECT * FROM path_output_tuples ORDER BY session_id ASC, event_timestamp ASC;Result:
event_timestamp | user_id | session_id | page | revenue | symbol | match_id ---------------------+---------+------------+----------+---------+--------+---------- 2015-04-15 01:05:00 | 100821 | 100 | CHECKOUT | 39 | buy | 1 2015-04-15 01:17:00 | 101121 | 102 | CHECKOUT | 15 | buy | 1 2015-04-15 01:22:00 | 101121 | 102 | CHECKOUT | 23 | buy | 2 2015-04-15 02:19:00 | 101331 | 103 | CHECKOUT | 16 | buy | 1 2015-04-15 02:25:00 | 101443 | 104 | CHECKOUT | 12 | buy | 1 2015-04-15 02:22:00 | 102871 | 108 | CHECKOUT | 21 | buy | 1 (6 rows)Notice that the 'symbol' and 'match_id' columns are added to the right of the matched rows.
DROP TABLE IF EXISTS path_output, path_output_tuples; SELECT madlib.path( 'eventlog', -- Name of input table 'path_output', -- Table name to store path results 'session_id', -- Partition input table by session 'event_timestamp ASC', -- Order partitions in input table by time 'land:=page=''LANDING'', wine:=page=''WINE'', beer:=page=''BEER'', buy:=page=''CHECKOUT'', other:=page<>''LANDING'' AND page<>''WINE'' AND page<>''BEER'' AND page<>''CHECKOUT''', -- Symbols for page types '(land)[^(land)(buy)]{0,2}(buy)', -- Purchase within 4 pages entering site 'sum(revenue) as checkout_rev', -- Aggregate: sum revenue by checkout TRUE -- Persist matches ); SELECT * FROM path_output ORDER BY session_id, match_id;Result:
session_id | match_id | session_rev ------------+----------+------------- 100 | 1 | 39 102 | 1 | 15 102 | 2 | 23 (3 rows)Now view the associated pattern matches:
SELECT * FROM path_output_tuples ORDER BY session_id ASC, event_timestamp ASC;Result:
event_timestamp | user_id | session_id | page | revenue | symbol | match_id ---------------------+---------+------------+----------+---------+--------+---------- 2015-04-15 01:03:00 | 100821 | 100 | LANDING | 0 | land | 1 2015-04-15 01:04:00 | 100821 | 100 | WINE | 0 | wine | 1 2015-04-15 01:05:00 | 100821 | 100 | CHECKOUT | 39 | buy | 1 2015-04-15 01:15:00 | 101121 | 102 | LANDING | 0 | land | 1 2015-04-15 01:16:00 | 101121 | 102 | WINE | 0 | wine | 1 2015-04-15 01:17:00 | 101121 | 102 | CHECKOUT | 15 | buy | 1 2015-04-15 01:18:00 | 101121 | 102 | LANDING | 0 | land | 2 2015-04-15 01:19:00 | 101121 | 102 | HELP | 0 | other | 2 2015-04-15 01:21:00 | 101121 | 102 | WINE | 0 | wine | 2 2015-04-15 01:22:00 | 101121 | 102 | CHECKOUT | 23 | buy | 2 (10 rows)
SELECT DATE(event_timestamp), user_id, session_id, revenue, avg(revenue) OVER (PARTITION BY DATE(event_timestamp)) as avg_checkout_rev FROM path_output_tuples WHERE page='CHECKOUT' ORDER BY user_id, session_id;Result:
date | user_id | session_id | revenue | avg_checkout_rev ------------+---------+------------+---------+------------------ 2015-04-15 | 100821 | 100 | 39 | 25.6666666666667 2015-04-15 | 101121 | 102 | 15 | 25.6666666666667 2015-04-15 | 101121 | 102 | 23 | 25.6666666666667 (3 rows)Here we are partitioning the window function by day because we want daily averages, although our sample data set only has a single day.
DROP TABLE IF EXISTS path_output, path_output_tuples; SELECT madlib.path( 'eventlog', -- Name of input table 'path_output', -- Table name to store path results 'session_id', -- Partition input table by session 'event_timestamp ASC', -- Order partitions in input table by time 'land:=page=''LANDING'', wine:=page=''WINE'', beer:=page=''BEER'', buy:=page=''CHECKOUT'', other:=page<>''LANDING'' AND page<>''WINE'' AND page<>''BEER'' AND page<>''CHECKOUT''', -- Symbols for page types '[^(buy)](buy)', -- Pattern to match 'array_agg(page ORDER BY session_id ASC, event_timestamp ASC) as page_path', -- Build array with shopper paths FALSE -- Don't persist matches );Now count the common paths and print the most frequent:
SELECT count(*), page_path from (SELECT * FROM path_output) q GROUP BY page_path ORDER BY count(*) DESC LIMIT 10;Result:
count | page_path -------+----------------- 5 | {WINE,CHECKOUT} 1 | {BEER,CHECKOUT} (2 rows)There are only 2 different paths. The wine page is viewed more frequently than the beer page just before checkout.
DROP TABLE IF EXISTS path_output, path_output_tuples; SELECT madlib.path( 'eventlog', -- Name of the table 'path_output', -- Table name to store the path results 'session_id', -- Partition by session 'event_timestamp ASC', -- Order partitions in input table by time $$ nobuy:=page<>'CHECKOUT', buy:=page='CHECKOUT' $$, -- Definition of symbols used in the pattern definition '(nobuy)+(buy)', -- At least one page followed by and ending with a CHECKOUT. 'array_agg(page ORDER BY session_id ASC, event_timestamp ASC) as page_path', FALSE, -- Don't persist matches TRUE -- Turn on overlapping patterns ); SELECT * FROM path_output ORDER BY session_id, match_id;Result with overlap turned on:
session_id | match_id | page_path ------------+----------+----------------------------------- 100 | 1 | {LANDING,WINE,CHECKOUT} 100 | 2 | {WINE,CHECKOUT} 102 | 1 | {LANDING,WINE,CHECKOUT} 102 | 2 | {WINE,CHECKOUT} 102 | 3 | {LANDING,HELP,WINE,CHECKOUT} 102 | 4 | {HELP,WINE,CHECKOUT} 102 | 5 | {WINE,CHECKOUT} 103 | 1 | {LANDING,WINE,HELP,WINE,CHECKOUT} 103 | 2 | {WINE,HELP,WINE,CHECKOUT} 103 | 3 | {HELP,WINE,CHECKOUT} 103 | 4 | {WINE,CHECKOUT} 104 | 1 | {BEER,CHECKOUT} 108 | 1 | {BEER,WINE,CHECKOUT} 108 | 2 | {WINE,CHECKOUT} (14 rows)With overlap turned off, the result would be:
session_id | match_id | page_path ------------+----------+----------------------------------- 100 | 1 | {LANDING,WINE,CHECKOUT} 102 | 1 | {LANDING,WINE,CHECKOUT} 102 | 2 | {LANDING,HELP,WINE,CHECKOUT} 103 | 1 | {LANDING,WINE,HELP,WINE,CHECKOUT} 104 | 1 | {BEER,CHECKOUT} 108 | 1 | {BEER,WINE,CHECKOUT} (6 rows)
Partition
Order
Symbol
Pattern
Pattern match
NOTE: The following links refer to documentation resources for the current PostgreSQL database version. Depending upon your database platform version, you may need to change "current" references in the links to your database version.
If your database platform uses the Greenplum Database (or related variants), please check with the project community and/or your database vendor to identify the PostgreSQL version it is based on.
[1] PostgreSQL basic statements/assignment operator, http://www.postgresql.org/docs/current/static/plpgsql-statements.html
[2] PostgreSQL pattern matching, http://www.postgresql.org/docs/current/static/functions-matching.html
[3] PostgreSQL aggregate functions, http://www.postgresql.org/docs/current/static/tutorial-agg.html
[4] PostgreSQL window functions, http://www.postgresql.org/docs/current/static/tutorial-window.html