Expand description
SASE+ Pattern Matching Engine
Implementation of the SASE+ algorithm for Complex Event Processing. Based on the paper: “High-Performance Complex Event Processing over Streams” by Wu, Diao, Rizvi (SIGMOD 2006)
Key features:
- NFA-based pattern matching with stack for Kleene closure
- Efficient event selection strategies (skip-till-any-match, skip-till-next-match)
- Negation support with temporal windows
- Partition-by attribute optimization (SASEXT extension)
Pattern syntax supported:
- SEQ(A, B, C): Sequence of events
- AND(A, B): Both events in any order
- OR(A, B): Either event
- NOT(A): Negation (absence of event)
- A+: Kleene plus (one or more)
- A*: Kleene star (zero or more)
- WITHIN(pattern, duration): Temporal constraint
Re-exports§
pub use clock::Timestamp;
Modules§
- clock
- Portable clock abstraction that works in both native and WASM environments.
Structs§
- AndBranch
- Configuration for an AND branch
- AndConfig
- Configuration for AND states in the NFA
- AndState
- Runtime state tracking for AND pattern completion
- Event
Time Config - Configuration for event-time processing
- Event
Time Manager - Manages event-time processing with watermarks and late event handling
- Event
Type Index - Index mapping event types to states that expect them
- Global
Negation - SASE+ Pattern Matching Engine Global negation condition for invalidating active runs
- Kleene
Capture - Compact representation of Kleene captures using Zero-suppressed Decision Diagrams.
- Latency
Histogram - Latency histogram with exponential buckets Buckets: <1µs, <10µs, <100µs, <1ms, <10ms, <100ms, <1s, >1s
- Match
Result - Result of pattern matching
- Metrics
Summary - Summary snapshot of SASE+ engine metrics for easier access.
- Negation
Constraint - Constraint for temporal negation that must be confirmed via timeout
- Negation
Info - Information about what to forbid in negation states
- Nfa
- Non-deterministic finite automaton for SASE+ pattern matching.
- NfaCompiler
- Compiles a SasePattern into an NFA
- Pattern
Builder - Builder for SASE patterns
- Process
Result - Result of processing an event, including matches, warnings, and stats
- Process
Stats - Statistics for a single process() call
- Run
- An active pattern run (partial match in progress)
- RunSnapshot
- Snapshot of an active SASE run for forecast computation.
- Sase
Engine - The SASE+ pattern matching engine.
- Sase
Extended Stats - Extended statistics with backpressure metrics
- Sase
Metrics - Comprehensive metrics for the SASE+ engine
- Sase
Stats - Engine statistics snapshot.
- Sequence
Context - Context for evaluating sequence expressions within SASE predicates.
- Stack
Entry - A stack entry for Kleene closure handling
- State
- A single state in the SASE+ NFA.
Enums§
- Backpressure
Error - Error returned when backpressure prevents run creation
- Backpressure
Strategy - Strategy when the maximum number of runs is reached
- Compare
Op - Comparison operators for predicate evaluation.
- Event
Time Result - Result of event-time processing for an event
- Predicate
- Predicate for event filtering
- Predicate
Class - Classification of a predicate relative to a Kleene closure variable.
- Process
Warning - Warning generated during event processing
- Sase
Pattern - A SASE+ pattern expression
- Selection
Strategy - Event selection strategy
- State
Type - NFA state types
- Time
Semantics - Time semantics for the engine
Constants§
- MAX_
ENUMERATION_ RESULTS - Safety cap on results emitted by
enumerate_with_filter. Prevents unbounded memory growth when the deferred predicate passes most combinations of a large Kleene closure. - MAX_
KLEENE_ EVENTS - Safety cap on events accumulated in a single Kleene closure. With n events the ZDD enumerates up to 2^n - 1 combinations. 20 events → ~1 M combinations (safe); 30 → ~1 B (OOM risk).
Traits§
- Expr
Evaluator - Trait for evaluating custom expressions in SASE predicates.
Functions§
- classify_
predicate - Classify a predicate as consistent or inconsistent for a Kleene state.
Type Aliases§
- Shared
Event - Shared event reference for efficient cloning in pattern matching. Using Arc allows multiple pattern runs to share the same event data without expensive deep copies.