esper.codehaus.org and espertech.comDocumentation

Chapter 7. EPL Reference: Match Recognize

7.1. Overview
7.2. Comparison of Match Recognize and EPL Patterns
7.3. Syntax
7.3.1. Syntax Example
7.4. Pattern and Pattern Operators
7.4.1. Operator Precedence
7.4.2. Concatenation
7.4.3. Alternation
7.4.4. Quantifiers Overview
7.4.5. Variables Can be Singleton or Group
7.4.6. Eliminating Duplicate Matches
7.4.7. Greedy Or Reluctant
7.4.8. Quantifier - One Or More (+ and +?)
7.4.9. Quantifier - Zero Or More (* and *?)
7.4.10. Quantifier - Zero Or One (? and ??)
7.5. Define Clause
7.5.1. The Prev Operator
7.6. Measure Clause
7.7. Datawindow-Bound
7.8. Interval
7.9. Use with Different Event Types
7.10. Limitations

Using match recognize patterns are defined in the familiar syntax of regular expressions.

The match recognize syntax presents an alternative way to specify pattern detection as compared to the EPL pattern language described in the previous chapter. A comparison of match recognize and EPL patterns is below.

The match recognize syntax is a proposal for incorporation into the SQL standard. It is thus subject to change as the standard evolves and finalizes (it has not finalized yet). Please consult row-pattern-recogniton-11-public for further information.

You may be familiar with regular expressions in the context of finding text of interest in a string, such as particular characters, words, or patterns of characters. Instead of matching characters, match recognize matches sequences of events of interest.

Esper can apply match-recognize patterns in real-time upon arrival of new events in a stream of events (also termed incrementally, streaming or continuous). Esper can also match patterns on-demand via the iterator pull-API, if specifying a named window or data window on a stream.

This section compares pattern detection via match recognize and via the EPL pattern language.

Table 7.1. Comparison Match Recognize to EPL Patterns

CategoryEPL PatternsMatch Recognize
PurposePattern detection in sequences of events.Same.
StandardsNot standardized, similar to Rapide pattern language.Proposal for incorporation into the SQL standard.
Real-time ProcessingYes.Yes.
On-Demand query via IteratorNo.Yes.
LanguageNestable expressions consisting of boolean AND, OR, NOT and time or arrival-based constructs such as -> (followed-by), timer:within and timer:interval.Regular expression consisting of variables each representing conditions on events.
Event TypesAn EPL pattern may react to multiple different types of events.The input is a single type of event (unless used with variant streams).
Data Window InteractionDisconnected, i.e. an event leaving a data window does not change pattern state.Connected, i.e. an event leaving a data window removes the event from match selection.
Semantic EvaluationTruth-value based: A EPL pattern such as (A and B) can fire when a single event arrives that satisfies both A and B conditions.Sequence-based: A regular expression (A B) requires at least two events to match.
Time Relationship Between EventsThe timer:within, timer:interval and NOT operator can expressively search for absence of events or other more complex timing relationships.Some support for detecting absence of events using the interval clause.
ExtensibilityCustom pattern objects, user-defined functions.User-defined functions, custom aggregation functions.
Memory UseLikely between 500 bytes to 2k per open sequence, depends on pattern.Likely between 100 bytes to 1k per open sequence, depends on pattern.

The synopsis is as follows:

match_recognize (
  [ partition by partition_expression [, partition_expression] [,...]  ]
  measures  measure_expression as col_name [, measure_expression as col_name ] [,...]
  [ all matches ]
  [ after match skip (past last row | to next row | to current row) ]
  pattern ( variable_regular_expr [, variable_regular_expr] [,...] )
  [ interval time_period ]
  define  variable as variable_condition [, variable as variable_condition]  [,...] 
)

The match_recognize keyword starts the match recognize definition and occurs right after the from clause in an EPL select statement. It is followed by parenthesis that surround the match recognize definition.

Partition by is optional and may be used to specify that events are to be partitioned by one or more event properties or expressions. If there is no Partition by then all rows of the table constitute a single partition. The regular expression applies to events in the same partition and not across partitions.

The measures clause defines columns that contain expressions over the pattern variables. The expressions can reference partition columns, singleton variables, aggregates as well as indexed properties on the group variables. Each measure_expression expression must be followed by the as keyword and a col_name column name.

The all matches keywords are optional and instructs the engine to find all possible matches. By default matches are ranked and the engine returns a single match following an algorithm to eliminate duplicate matches, as described below. When specifying all matches, matches may overlap and may start at the same row.

The after match skip keywords are optional and serve to determine the resumption point of pattern matching after a match has been found. By default the behavior is after match skip past last row. This means that after eliminating duplicate matches, the logic skips to resume pattern matching at the next event after the last event of the current match.

The pattern component is used to specify a regular expression. The regular expression is built from variable names, and may use the operators such as *, +, ?, *?, +?, ?? quantifiers and | alteration (concatenation is indicated by the absence of any operator sign between two successive items in a pattern).

With the optional interval keyword and time period you can control how long the engine should wait for further events to arrive that may be part of a matching event sequence, before indicating a match (or matches) (not applicable to on-demand pattern matching).

Define is a mandatory component, used to specify the boolean condition that defines a variable name that is declared in the pattern. A variable name does not require a definition and if there is no definition, the default is a predicate that is always true. Such a variable name can be used to match any row.

For illustration, the examples in this chapter use the TemperatureSensorEvent event. Each event has 3 properties: the id property is a unique event id, the device is a sensor device number and the temp property is a temperature reading. An event described as "id=E1, device=1, temp=100" is a TemperatureSensorEvent event with id "E1" for device 1 with a reading of 100.

This example statement looks for two TemperatureSensorEvent events from the same device, directly following each other, that indicate a jump in temperature of 10 or more between the two events:

select * from TemperatureSensorEvent
match_recognize (
  partition by device
  measures A.id as a_id, B.id as b_id, A.temp as a_temp, B.temp as b_temp
  pattern (A B)
  define 
    B as Math.abs(B.temp - A.temp) >= 10
)

The partition by ensures that the regular expression applies to sequences of events from the same device.

The measures clause provides a list of properties or expressions to be selected from matching events. Each property name must be prefixed by the variable name.

In the pattern component the statement declares two variables: A and B. As a matter of convention, variable names are uppercase characters.

The define clause specifies no condition for variable A. This means that A defaults to true and any event matches A. Therefore, the pattern can start at any event.

The pattern A B indicates to look for a pattern in which an event that fulfills the condition for variable A is immediately followed by an event that fulfills the condition for variable B. A pattern thus defines the sequence (or sequences) of conditions that must be met for the pattern to fire.

Below table is an example sequence of events and output of the pattern:


At time 4000 when event with id E4 (or event E4 or just E4 for short) arrives the pattern matches and produces an output event. Matching then skips past the last event of the current match (E4) and begins at event E5 (the default skip clause is past last row). Therefore events E4 and E5 do not constitute a match.

At time 3000, events E1 and E3 do not constitute a match as E3 does not immediately follow E, since there is E2 in between.

At time 7000, event E7 does not constitute a match as it is from device 2 and thereby not in the same partition as prior events.

The pattern specifies the pattern to be recognized in the ordered sequence of events in a partition using regular expression syntax. Each variable name in a pattern corresponds to a boolean condition, which is specified later using the define component of the syntax. Thus the pattern can be regarded as implicitly declaring one or more variable names; the definition of those variable names appears later in the syntax. If a variable is not defined the variable defaults to true.

It is permitted for a variable name to occur more than once in a pattern, for example pattern (A B A).

The execution of match recognize is continuous and real-time by default. This means that every arriving event, or batch of events if using batching, evaluates against the pattern and matches are immediately indicated. Elimination of duplicate matches occurs between all matches of the arriving events (or batch of events) at a given time.

As an alternative, and if your application does not require continuous pattern evaluation, you may use the iterator API to perform on-demand matching of the pattern. For the purpose of indicating to the engine to not generate continuous results, specify the @Hint('iterate_only') hint.

When using one-or-more, zero-or-more or zero-or-one quantifiers (?, +, *, ??, +?, *?), the output of the real-time continuous query can differ from the output of the on-demand iterator execution: The continuous query will output a match (or multiple matches) as soon as matches are detected at a given time upon arrival of events (not knowing what further events may arrive). The on-demand execution, since it knows all possible events in advance, can determine the longest match(es). Thus elimination of duplicate matches can lead to different results between real-time and on-demand use.

If the all matches keywords are specified, then all matches are returned as the result and no elimination of duplicate matches as below occurs.

Otherwise matches to a pattern in a partition are ordered by preferment. Preferment is given to matches based on the following priorities:

After ranking matches by preferment, matches are chosen as follows:

Within define are listed the boolean conditions that defines a variable name that is declared in the pattern.

A variable name does not require a definition and if there is no definition, the default is a predicate that is always true. Such a variable name can be used to match any row.

The definitions of variable names may reference the same or other variable names as prior examples have shown.

If a variable in your condition expression is a singleton variable, then only individual columns may be referenced. If the variable is not matched by an event, a null value is returned.

If a variable in your condition expression is a group variable, then only indexed columns may be referenced. If the variable is not matched by an event, a null value is returned.

Aggregation functions are not allowed within expressions of the define clause.

The prev function may be used in a define expression to access columns of the previous row of a variable name. If there is no previous row, the null value is returned.

The prev function can accept an optional non-negative integer argument indicating the offset to the previous rows. That argument must be a constant. In this case, the engine returns the property from the N-th row preceding the current row, and if the row doesn’t exist, it returns null.

This function can access variables currently defined, for example:

Y as Y.price < prev(Y.price, 2)

It is not legal to use prev with another variable then the one being defined:

// not allowed
Y as Y.price < prev(X.price, 2)

The prev function returns properties of events in the same partition. Also, it returns properties of events according to event order-of-arrival. When using data windows or deleting events from a named window, the remove stream does not remove events from the prev function.

The pattern looks for an event in which the temperature is greater or equal 100 and that, relative to that event, has an event preceding it by 2 events that also had a temperature greater or equal 100:

select * from TemperatureSensorEvent
match_recognize (
  partition by device
  measures A.id as a_id
  pattern (A)
  define 
	A as A.temp > 100 and prev(A.temp, 2) > 100)

An example sequence of events that matches the pattern above is:


The measures clause defines exported columns that contain expressions over the pattern variables. The expressions can reference partition columns, singleton variables and any aggregation functions including last and first on the group variables.

Expressions in the measures clause must use the as keyword to assign a column name.

If a variable is a singleton variable then only individual columns may be referenced, not aggregates. If the variable is not matched by an event, a null value is returned.

If a variable is a group variable and used in an aggregate, then the aggregate is performed over all rows that have matched the variable. If a group variable is not in an aggregate function, its variable name must be post-fixed with an index. See Section 7.4.5, “Variables Can be Singleton or Group” for more information.

When using match recognize with a named window or stream bound by a data window, all events removed from the named window or data window also removed the match-in-progress that includes the event(s) removed.

The next example looks for four sensor events from the same device immediately following each other and indicating a rising temperature, but only events that arrived in the last 10 seconds are considered:

select * from TemperatureSensorEvent.win:time(10 sec)
match_recognize (
partition by device
measures A.id as a_id
pattern (A B C D)
define 
B as B.temp > A.temp,
C as C.temp > B.temp,
D as D.temp > C.temp)

An example sequence of events that matches the pattern above is:


Note that E8, E9, E10 and E11 doe not constitute a match since E8 leaves the data window at 25000.

With the optional interval keyword and time period you can control how long the engine should wait for further events to arrive that may be part of a matching event sequence, before indicating a match (or matches). This is not applicable to on-demand pattern matching.

The interval timer starts are the arrival of the first event matching a sequence for a partition. When the time interval passes and an event sequence matches, duplicate matches are eliminated and output occurs.

The next example looks for sensor events indicating a temperature of over 100 waiting for any number of additional events with a temperature of over 100 for 10 seconds before indicating a match:

select * from TemperatureSensorEvent
match_recognize (
partition by device
measures A.id as a_id, count(B.id) as count_b, first(B.id) as first_b, last(B.id) as last_b
pattern (A B*)
interval 5 seconds
define 
  A as A.temp > 100,
  B as B.temp > 100)

An example sequence of events that matches the pattern above is:


Notice that the engine waits 5 seconds (5000 milliseconds) after the arrival time of the first event E2 of the match at 2000, to indicate the match at 7000.

You may match different types of events using match-recognize by following any of these strategies:

A short example that demonstrates variant streams and match-recognize is listed below:

// Declare one sample type
create schema S0 as (col string)
// Declare second sample type
create schema S1 as (col string)
// Declare variant stream holding either type
create variant schema MyVariantStream as S0, S1
// Populate variant stream
insert into MyVariantStream select * from S0
// Populate variant stream
insert into MyVariantStream select * from S1
// Simple pattern to match S0 S1 pairs
select * from MyVariantType.win:time(1 min)
match_recognize (
  measures A.id? as a, B.id? as b
  pattern (A B)
  define
    A as typeof(A) = 'S0',
    B as typeof(B) = 'S1'
)

Please note the following limitations: