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.1225019e-05
Overall Rank: 5,454 | 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,006	Democratize MATCH_RECOGNIZE !	2025	VLDB	5.0954911e-05
11,083	Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns	2026	VLDB	4.9769913e-05
11,219	Scalable Complex Event Processing on Video Streams	2025	SIGMOD	4.9769913e-05
11,311	LLMLog: Advanced Log Template Generation via LLM-driven Multi-Round Annotation	2025	VLDB	4.9769913e-05
11,599	Complex Event Recognition with Symbolic Register Transducers	2024	VLDB	4.9769913e-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.0023943337
208	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024899872
220	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024333068
241	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00023408695
273	Extensible Query Processing in Starburst	1989	SIGMOD	0.00022498382
315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021236408
580	Efficient Pattern Matching over Event Streams	2008	SIGMOD	0.0001607809
653	The Design and Implementation of a Sequence Database System	1996	VLDB	0.00015099306
685	Trill: A High-Performance Incremental Query Processor for Diverse Analytics	2015	VLDB	0.00014778299
691	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014737455
706	Sequence Query Processing	1994	SIGMOD	0.0001463663
755	Cayuga: A General Purpose Event Monitoring System	2007	CIDR	0.00014226048
1,029	ZStream: A Cost-based Query Processor for Adaptively Detecting Composite Events	2009	SIGMOD	0.00012411098
1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	0.00010122962
1,726	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.7857214e-05
1,813	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.5759542e-05
3,400	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB	7.330164e-05
3,410	Scalable Pattern Sharing on Event Streams	2016	SIGMOD	7.322416e-05
4,024	Real-Time Multi-Pattern Detection over Event Streams	2019	SIGMOD	6.8444194e-05
4,623	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	6.4957114e-05
6,677	Index-Accelerated Pattern Matching in Event Stores	2021	SIGMOD	5.7105065e-05
6,725	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6954425e-05
7,351	A Scalable and Generic Approach to Range Joins	2022	VLDB	5.542858e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,623	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB
2	1,345	Reverse Engineering Complex Join Queries	2013	SIGMOD
3	2,887	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,519	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
6	5,491	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,154	Robust Join Processing with Diamond Hardened Joins	2024	VLDB
9	580	Efficient Pattern Matching over Event Streams	2008	SIGMOD
10	10,006	Democratize MATCH_RECOGNIZE !	2025	VLDB