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.1254016e-05
Overall Rank: 5,449 | 63.37%
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
10,001	Democratize MATCH_RECOGNIZE !	2025	VLDB	5.0979044e-05
11,074	Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns	2026	VLDB	4.9793485e-05
11,210	Scalable Complex Event Processing on Video Streams	2025	SIGMOD	4.9793485e-05
11,303	LLMLog: Advanced Log Template Generation via LLM-driven Multi-Round Annotation	2025	VLDB	4.9793485e-05
11,593	Complex Event Recognition with Symbolic Register Transducers	2024	VLDB	4.9793485e-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.0023947656
208	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024884544
220	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024344086
241	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00023419748
273	Extensible Query Processing in Starburst	1989	SIGMOD	0.00022504729
315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021246
580	Efficient Pattern Matching over Event Streams	2008	SIGMOD	0.00016085679
653	The Design and Implementation of a Sequence Database System	1996	VLDB	0.00015106313
685	Trill: A High-Performance Incremental Query Processor for Diverse Analytics	2015	VLDB	0.00014782777
692	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014741011
706	Sequence Query Processing	1994	SIGMOD	0.00014643264
755	Cayuga: A General Purpose Event Monitoring System	2007	CIDR	0.00014232741
1,029	ZStream: A Cost-based Query Processor for Adaptively Detecting Composite Events	2009	SIGMOD	0.00012416974
1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	0.00010127607
1,725	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.7902443e-05
1,812	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.5803973e-05
3,400	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB	7.3336355e-05
3,410	Scalable Pattern Sharing on Event Streams	2016	SIGMOD	7.3258817e-05
4,023	Real-Time Multi-Pattern Detection over Event Streams	2019	SIGMOD	6.8476587e-05
4,621	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	6.4987856e-05
6,673	Index-Accelerated Pattern Matching in Event Stores	2021	SIGMOD	5.7131264e-05
6,721	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6981399e-05
7,348	A Scalable and Generic Approach to Range Joins	2022	VLDB	5.5454832e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,266	An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory	2016	SIGMOD
2	1,345	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,400	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB
5	10,508	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
6	5,487	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD
7	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
8	3,153	Robust Join Processing with Diamond Hardened Joins	2024	VLDB
9	580	Efficient Pattern Matching over Event Streams	2008	SIGMOD
10	10,001	Democratize MATCH_RECOGNIZE !	2025	VLDB