High-Performance Row Pattern Recognition Using Joins

Summary: Rewrites historical MATCH_RECOGNIZE plans to prefilter rows via joins over selected pattern symbols, then applies the NFA. Cost/cardinality models choose symbols, yielding median speedups of 5.4–57.5× across Trino and SQL Server. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h622b682ad2e1f68b
Venue: VLDB
Year: 2023
Pagerank: 6.1022571e-05
Overall Rank: 5,469 | 63.35%
DOI: 10.14778/3579075.3579090
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Erkang Zhu (Microsoft)
2. Silu Huang (Microsoft)
3. Surajit Chaudhuri (Microsoft)

BibTeX Citation

@article{zhu_vldb23,
        title = {{High-Performance Row Pattern Recognition Using Joins}},
        author = {Zhu, Erkang and Huang, Silu and Chaudhuri, Surajit},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {5},
        pages = {1181--1194},
        doi = {10.14778/3579075.3579090},
        url = {https://doi.org/10.14778/3579075.3579090},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

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

Outgoing Citations (Sorted by Pagerank)

Showing 23 of 23 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.0023948467
208	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024929198
220	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024275691
241	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00023332645
275	Extensible Query Processing in Starburst	1989	SIGMOD	0.000224395
318	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021178303
582	Efficient Pattern Matching over Event Streams	2008	SIGMOD	0.00016025959
657	The Design and Implementation of a Sequence Database System	1996	VLDB	0.00015050854
688	Trill: A High-Performance Incremental Query Processor for Diverse Analytics	2015	VLDB	0.00014736145
690	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014703258
712	Sequence Query Processing	1994	SIGMOD	0.00014588907
762	Cayuga: A General Purpose Event Monitoring System	2007	CIDR	0.00014179183
1,034	ZStream: A Cost-based Query Processor for Adaptively Detecting Composite Events	2009	SIGMOD	0.00012370157
1,603	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	0.00010090639
1,734	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.7545941e-05
1,821	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.5466386e-05
3,410	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB	7.3075605e-05
3,422	Scalable Pattern Sharing on Event Streams	2016	SIGMOD	7.298206e-05
4,041	Real-Time Multi-Pattern Detection over Event Streams	2019	SIGMOD	6.8217898e-05
4,640	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	6.4742349e-05
6,690	Index-Accelerated Pattern Matching in Event Stores	2021	SIGMOD	5.6917141e-05
6,743	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6766099e-05
7,373	A Scalable and Generic Approach to Range Joins	2022	VLDB	5.5245298e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,640	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB
2	1,353	Reverse Engineering Complex Join Queries	2013	SIGMOD
3	2,886	Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment	2021	VLDB
4	3,410	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB
5	10,585	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
6	5,514	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD
7	1,603	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
8	3,165	Robust Join Processing with Diamond Hardened Joins	2024	VLDB
9	582	Efficient Pattern Matching over Event Streams	2008	SIGMOD
10	10,041	Democratize MATCH_RECOGNIZE !	2025	VLDB