High-Performance Row Pattern Recognition Using Joins

Summary: Replace standard NFA-only MATCH_RECOGNIZE with a logical-plan rewrite that first constructs Joins on a chosen subset of pattern symbols to prefilter rows, then runs the NFA on the reduced input, guided by specialized join cardinality and NFA cost models. Applicable to self-contained patterns on duplicate-free or windowed inputs; achieves median speedups of 5.4x (Trino), 57.5x (SQL Server columnstore) and 41.6x (rowstore). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 12986
Venue: VLDB
Year: 2023
Pagerank: 5.7277656e-05
Overall Rank: 5,059 | 64.81%
DOI: 10.14778/3579075.3579090

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,330	Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns	2026	VLDB	4.1945683e-05
10,523	Scalable Complex Event Processing on Video Streams	2025	SIGMOD	4.1945683e-05
10,658	LLMLog: Advanced Log Template Generation via LLM-driven Multi-Round Annotation	2025	VLDB	4.1945683e-05
10,794	Democratize MATCH_RECOGNIZE !	2025	VLDB	4.1945683e-05
11,057	Complex Event Recognition with Symbolic Register Transducers	2024	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040449103
152	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00040963225
259	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00030174924
307	Extensible Query Processing in Starburst	1989	SIGMOD	0.00028211308
342	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026795977
625	Sequence Query Processing	1994	SIGMOD	0.00018980669
666	The Design and Implementation of a Sequence Database System	1996	VLDB	0.00018449748
776	Efficient Pattern Matching over Event Streams	2008	SIGMOD	0.00016799754
944	Cayuga: A General Purpose Event Monitoring System	2007	CIDR	0.00015141297
1,098	Trill: A High-Performance Incremental Query Processor for Diverse Analytics	2015	VLDB	0.00014114442
1,254	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00013027411
1,418	ZStream: A Cost-based Query Processor for Adaptively Detecting Composite Events	2009	SIGMOD	0.00012089363
1,557	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011392493
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
2,296	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0776226e-05
3,815	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB	6.7333316e-05
4,007	Scalable Pattern Sharing on Event Streams	2016	SIGMOD	6.5397067e-05
4,457	Real-Time Multi-Pattern Detection over Event Streams	2019	SIGMOD	6.1702339e-05
5,097	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	5.7011496e-05
6,619	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	4.9910152e-05
6,788	Index-Accelerated Pattern Matching in Event Stores	2021	SIGMOD	4.9252064e-05
7,250	A Scalable and Generic Approach to Range Joins	2022	VLDB	4.78908e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,804	An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory	2016	SIGMOD	0.00010501185
5,097	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	5.7011496e-05
1,572	Reverse Engineering Complex Join Queries	2013	SIGMOD	0.00011298251
3,898	Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment	2021	VLDB	6.6551268e-05
3,815	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB	6.7333316e-05
6,647	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	4.9772122e-05
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
4,465	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	6.1604282e-05
776	Efficient Pattern Matching over Event Streams	2008	SIGMOD	0.00016799754
10,794	Democratize MATCH_RECOGNIZE !	2025	VLDB	4.1945683e-05