by Matt Fuller, Vertica
By 2015, it is estimated the annual global internet traffic will reach almost 1 zettabyte. To put it into more familiar units, this is equivalent to about 1 billion terabytes. Web, email, instant messaging, etc. will account for about 30% of this figure. I found this fascinating, but not surprising, given the rate of new applications and users entering the market. Whether you believe these estimates or interpret the data differently, I think we can agree there is a vast amount of data out there.
As users perform their online activities, such as playing Farmville, reading tweets, or browsing for slick deals on Groupon, web server logs may store their clicks. This raw data, , or “data exhaust,” may appear to be junk to many, but in reality this “data exhaust” can be monetized given the right tools.
In funnel analysis, a funnel is the flow, or path, a user may take before reaching an end goal, such as a purchase, sign up, or download. The path may consist of a series of web clicks to different pages on the site until finally ending up at the goal. Along this path, users may drop out after any point, thus reducing the percentage of users that make it to the goal.
Analyzing the funnel can provide insight to improve the site flow. For example, if a site knew the registration page is the page where most users dropped out, the site could improve the usability of that page to engage more customers and then analyze those improvements.
In Vertica 5.0, we introduced the latest addition to our in-database analytics package: Event Series Pattern Matching. In this article we will discuss how you can use Vertica’s Event Series Pattern Matching to discover user click events that match funnels.
Suppose we used a user-defined transform (UDT) to help load your server’s web click log into a Vertica table, where each row corresponds to a single click in your log (user_id may actually be an ip address).
Next, we would like to search for sequences of web clicks that match a particular funnel. For example, we would like to identify the series of clicks where a user viewed an item for sale, filled out the form to purchase, and then ultimately made the purchase. Additionally, we would like to include any other items the user visited during the flow. The funnel may look like:
Let’s now construct an Event Series Pattern Matching SQL query in Vertica to find the sequence of clicks matching our funnel. This can be done in 3 simple steps by defining our funnel as a regular expression, defining an alphabet for our regular expression, and defining the logical window over which we want to match our regular expression. The next sections describe these steps in more detail.
Step 1: Pattern Specification
Event Series Pattern Matching goes far beyond simple Funnel Analysis. So let’s start to use event series pattern matching terminology. First, think of each click record as an “event” and a clickstream (or sequence of many clicks) as an “event series.” And let’s also think of our funnel as a “pattern.”
Our pattern is specified using regular expression notation consisting of events from our event alphabet (more details in the next section) with optional quantifiers such as the Kleene Star (i.e. “*”):
(EntryItemView ItemView* Checkout Purchase)
For a contiguous sequence of events, this notation describes all the pattern instances starting with an item page view referred from another site event, zero or more page views of other items, proceeding to the checkout page to buy an item, and then ultimately ending with a purchase by landing on the purchase confirmation page.
Step 2: Event Definitions
Next, we must define our event alphabet. We use SQL Boolean expressions aliased to an event name. The event names are what we used in the pattern specification.
EntryItemView as referring_url NOT ILIKE ‘%groupon.com%’
…………..and page_url ILIKE ‘%groupon.com%’
ItemView as page_url ILIKE ‘%groupon.com%’ and action = ‘VIEW’
Checkout as page_url ILIKE ‘%groupon.com%’ and action = ‘CHECKOUT’
Purchase as page_url ILIKE ‘%groupon.com%’ and action = ‘PURCHASE’
A row is considered to be of an event type if the Boolean expression yields TRUE for that row. For example, the below row from the clickstream table is considered to be of event “Purchase” because the predicate is TRUE given the values of the row.
Step 3: Window Definition
A window is the logical grouping of data. In our example, we are trying to discover matching pattern instances per user. Therefore, we would like to logically group all the data per user together and perform Event Series Pattern Matching for each user. And since we wish to find the pattern instances of a contiguous sequence of events, the data must be ordered. In this example, processing the data sorted on the timestamp is the logical choice. We define our window using the PARTITION BY and ORDER BY clause:
PARTITION BY user_id ORDER BY timestamp
Optionally, you may want to group the data per user per session. This is simple and efficient to do with Vertica’s in-database sessionization. In our example, we added the session id to the table already for simplicity:
PARTITION BY user_id, session_id ORDER BY timestamp
(NOTE: In these two examples, what is the “Window” – we talk about it but don’t point out the final result (i.e. the window))
Putting it all together…
Let’s combine the steps from above into a SQL SELECT:
SELECT user_id, referring_url, page_url,
event_name(), match_id(), pattern_id()
…….PARTITION BY user_id, session_id ORDER BY timestamp
…………EntryItemView as referring_url NOT ILIKE ‘%groupon.com%’
…………….and page_url ILIKE ‘%groupon.com%’,
…………ItemView as page_url ILIKE ‘%groupon.com%’
…………….and action = ‘VIEW’,
…………Checkout as page_url ILIKE ‘%groupon.com%’
…………….and action = ‘CHECKOUT’,
…………Purchase as page_url ILIKE ‘%groupon.com%’
…………….and action = ‘PURCHASE’
…………PATTERN P as (EntryItemView ItemView* Checkout Purchase)
Run on Vertica, and Voila!
The results above consist of all rows that contributed to a discovered pattern instance. You may have noticed three new functions in the SELECT list: event_name(), match_id(), pattern_id(). These return data for additional analysis as well as demarcate the different pattern instances:
- - event_name() returns the name of the event for which that row contributed in the pattern instance
- - match_id() is a monotonically increasing integer to serve as a unique identifier for the row within the pattern instance
- - pattern_id() is a monotonically increasing integer serving as a unique identifier with the pattern instance within the partition/group
For simplicity, our example doesn’t demonstrate more than one pattern match per partition/group. But imagine that if user 100 made another set of clicks matching the funnel, its pattern identifier would be 2. And if user 300 also made another set of clicks matching the funnel, its pattern identifier would also be 2 since we reset the starting identifier for each new partition.
We immediately notice from the results that Twitter user ABC has referred users to the website, but more importantly, referred users with a high success rate of making purchases. And of course further analysis, such as aggregation and pivoting, can be performed on the results of this Event Series Pattern Matching.
It might be said this could be done with SQL OLAP windowing functions such as LAG. For simple funnels, this is certainly true. But this would be difficult, if not impossible, using SQL OLAP for funnels defined by more complex pattern specifications including quantifiers such as Kleene Star or Kleene Plus.
And since Event Series Pattern Matching is in-database, you get Vertica’s performance and scalability. As an MPP system, Vertica automatically parallelizes the work across the cluster. The figure below illustrates finding the pattern instances in parallel across a Vertica cluster. First the data is segmented based on the partition window definition. Then each node independently processes and finds the pattern instances in the data segments. Finally, the pattern instance results from each node are combined at the node that issued the query and the final result is sent back to the user.
Vertica is an ideal platform for monetizing ALL of your data, and we’ve shown you how event series pattern matching can be used to analyze seemingly unimportant web log data to find the top patterns that lead to conversion events on a web site. Just by using our new SQL “match” clause in three very simple and straightforward steps.
In a future post, we will discuss how one can use event series pattern matching to perform more advanced sessionization and compare it to Google Analytics.