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: 13174
Venue: VLDB
Year: 2023
Pagerank: 6.2659937e-05
Overall Rank: 5,321 | 63.50%
DOI: 10.14778/3579075.3579090

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
9,813	Democratize MATCH_RECOGNIZE !	2025	VLDB	5.214913e-05
10,628	Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns	2026	VLDB	5.093636e-05
10,795	Scalable Complex Event Processing on Video Streams	2025	SIGMOD	5.093636e-05
10,909	LLMLog: Advanced Log Template Generation via LLM-driven Multi-Round Annotation	2025	VLDB	5.093636e-05
11,265	Complex Event Recognition with Symbolic Register Transducers	2024	VLDB	5.093636e-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.0024089429
210	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024797689
211	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024797217
229	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00023927582
268	Extensible Query Processing in Starburst	1989	SIGMOD	0.00022788687
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
565	Efficient Pattern Matching over Event Streams	2008	SIGMOD	0.00016445548
639	The Design and Implementation of a Sequence Database System	1996	VLDB	0.00015434427
687	Sequence Query Processing	1994	SIGMOD	0.00014948592
697	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014888851
710	Trill: A High-Performance Incremental Query Processor for Diverse Analytics	2015	VLDB	0.00014715033
732	Cayuga: A General Purpose Event Monitoring System	2007	CIDR	0.00014536846
1,005	ZStream: A Cost-based Query Processor for Adaptively Detecting Composite Events	2009	SIGMOD	0.000126998
1,699	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.975915e-05
1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.875587e-05
1,857	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.6047945e-05
3,342	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB	7.4999147e-05
3,352	Scalable Pattern Sharing on Event Streams	2016	SIGMOD	7.4932699e-05
3,946	Real-Time Multi-Pattern Detection over Event Streams	2019	SIGMOD	7.0046969e-05
4,588	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	6.6167545e-05
6,549	Index-Accelerated Pattern Matching in Event Stores	2021	SIGMOD	5.8442558e-05
6,596	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.828647e-05
7,207	A Scalable and Generic Approach to Range Joins	2022	VLDB	5.6727648e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,265	An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory	2016	SIGMOD
2	1,313	Reverse Engineering Complex Join Queries	2013	SIGMOD
3	3,134	Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment	2021	VLDB
4	3,342	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB
5	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
6	5,364	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD
7	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
8	3,622	Robust Join Processing with Diamond Hardened Joins	2024	VLDB
9	565	Efficient Pattern Matching over Event Streams	2008	SIGMOD
10	9,813	Democratize MATCH_RECOGNIZE !	2025	VLDB