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: 12987
Venue: VLDB
Year: 2023
Pagerank: 5.7275467e-05
Overall Rank: 5,049 | 64.92%
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,342	Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns	2026	VLDB	4.1905499e-05
10,532	Scalable Complex Event Processing on Video Streams	2025	SIGMOD	4.1905499e-05
10,666	LLMLog: Advanced Log Template Generation via LLM-driven Multi-Round Annotation	2025	VLDB	4.1905499e-05
10,800	Democratize MATCH_RECOGNIZE !	2025	VLDB	4.1905499e-05
11,060	Complex Event Recognition with Symbolic Register Transducers	2024	VLDB	4.1905499e-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.0040465394
151	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00041010211
259	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00030155645
309	Extensible Query Processing in Starburst	1989	SIGMOD	0.00028195213
341	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026850764
626	Sequence Query Processing	1994	SIGMOD	0.00018961452
666	The Design and Implementation of a Sequence Database System	1996	VLDB	0.00018431431
772	Efficient Pattern Matching over Event Streams	2008	SIGMOD	0.00016790632
945	Cayuga: A General Purpose Event Monitoring System	2007	CIDR	0.0001512921
1,097	Trill: A High-Performance Incremental Query Processor for Diverse Analytics	2015	VLDB	0.00014083973
1,239	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00013091459
1,417	ZStream: A Cost-based Query Processor for Adaptively Detecting Composite Events	2009	SIGMOD	0.00012084678
1,556	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011383141
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
2,298	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0746479e-05
3,818	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB	6.7279318e-05
4,012	Scalable Pattern Sharing on Event Streams	2016	SIGMOD	6.5338454e-05
4,456	Real-Time Multi-Pattern Detection over Event Streams	2019	SIGMOD	6.1644341e-05
5,091	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	5.7010894e-05
6,618	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	4.9864636e-05
6,789	Index-Accelerated Pattern Matching in Event Stores	2021	SIGMOD	4.9206048e-05
7,247	A Scalable and Generic Approach to Range Joins	2022	VLDB	4.7846107e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,091	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	5.7010894e-05
1,800	An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory	2016	SIGMOD	0.00010494121
1,575	Reverse Engineering Complex Join Queries	2013	SIGMOD	0.00011288804
3,899	Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment	2021	VLDB	6.6513982e-05
3,818	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB	6.7279318e-05
6,647	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	4.9729424e-05
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
4,466	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	6.1545841e-05
772	Efficient Pattern Matching over Event Streams	2008	SIGMOD	0.00016790632
10,800	Democratize MATCH_RECOGNIZE !	2025	VLDB	4.1905499e-05