{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T16:41:31Z","timestamp":1773247291790,"version":"3.50.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:p>The SQL standard introduced MATCH_RECOGNIZE in 2016 for row pattern recognition. Since then, MATCH_RECOGNIZE has been supported by several leading relation systems, they implemented this function using Non-Deterministic Finite Automaton (NFA). While NFA is suitable for pattern recognition in streaming scenarios, the current uses of NFA by the relational systems for historical data analysis scenarios overlook important optimization opportunities. We propose a new approach to use Join to speed up row pattern recognition in historical analysis scenarios for relational systems. Implemented as a logical plan rewrite rule, the new approach first filters the input relation to MATCH_RECOGNIZE using Joins constructed based on a subset of symbols taken from the PATTERN expression, then run the NFA-based MATCH_RECOGNIZE on the filtered rows, reducing the net cost. The rule also includes a specialized cardinality model for the Joins and a cost model for the NFA-based MATCH_RECOGNIZE operator for choosing an appropriate symbol set. The rewrite rule is applicable when the query pattern's definition is self-contained and either the input table has no duplicates or there is a window condition. Applying the rewrite rule to a query benchmark with 1,800 queries spanning over 6 patterns and 3 pattern definitions, we observed median speedups of 5.4X on Trino (v373 with ORC files on Hive), 57.5X on SQL Server (2019) using column store and 41.6X on row store.<\/jats:p>","DOI":"10.14778\/3579075.3579090","type":"journal-article","created":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T17:10:26Z","timestamp":1678122626000},"page":"1181-1195","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["High-Performance Row Pattern Recognition Using Joins"],"prefix":"10.14778","volume":"16","author":[{"given":"Erkang","family":"Zhu","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, Washington, U.S.A."}]},{"given":"Silu","family":"Huang","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, Washington, U.S.A."}]},{"given":"Surajit","family":"Chaudhuri","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, Washington, U.S.A."}]}],"member":"320","published-online":{"date-parts":[[2023,3,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2022. Citus. https:\/\/github.com\/citusdata\/citus. 2022. Citus. https:\/\/github.com\/citusdata\/citus."},{"key":"e_1_2_1_2_1","unstructured":"2022. Columnstore indexes: Overview. https:\/\/docs.microsoft.com\/en-us\/sql\/relational-databases\/indexes\/columnstore-indexes-overview. 2022. Columnstore indexes: Overview. https:\/\/docs.microsoft.com\/en-us\/sql\/relational-databases\/indexes\/columnstore-indexes-overview."},{"key":"e_1_2_1_3_1","unstructured":"2022. Index Accelerated Pattern Matching on Persistent Event Streams. https:\/\/github.com\/sigmod2021-index-pattern\/index-pattern. 2022. Index Accelerated Pattern Matching on Persistent Event Streams. https:\/\/github.com\/sigmod2021-index-pattern\/index-pattern."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008","author":"Agrawal Jagrati","year":"2008","unstructured":"Jagrati Agrawal , Yanlei Diao , Daniel Gyllstrom , and Neil Immerman . 2008 . Efficient pattern matching over event streams . In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008 , Vancouver, BC, Canada , June 10-12, 2008, Jason Tsong-Li Wang (Ed.). ACM, 147--160. 10.1145\/1376616.1376634 Jagrati Agrawal, Yanlei Diao, Daniel Gyllstrom, and Neil Immerman. 2008. Efficient pattern matching over event streams. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008, Jason Tsong-Li Wang (Ed.). ACM, 147--160. 10.1145\/1376616.1376634"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Apache Flink. 2022. Pattern Recognition. https:\/\/nightlies.apache.org\/flink\/flink-docs-release-1.14\/docs\/dev\/table\/sql\/queries\/match_recognize\/. Apache Flink. 2022. Pattern Recognition. https:\/\/nightlies.apache.org\/flink\/flink-docs-release-1.14\/docs\/dev\/table\/sql\/queries\/match_recognize\/.","DOI":"10.1007\/978-3-319-63962-8_303-2"},{"key":"e_1_2_1_7_1","unstructured":"Brian Olsen. 2020. A gentle introduction to the Hive connector. https:\/\/trino.io\/blog\/2020\/10\/20\/intro-to-hive-connector.html. Brian Olsen. 2020. A gentle introduction to the Hive connector. https:\/\/trino.io\/blog\/2020\/10\/20\/intro-to-hive-connector.html."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735503"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920873"},{"key":"e_1_2_1_10_1","unstructured":"Chicago. 2022. Chicago Crimes. https:\/\/www.kaggle.com\/chicago\/chicago-crime. Chicago. 2022. Chicago Crimes. https:\/\/www.kaggle.com\/chicago\/chicago-crime."},{"key":"e_1_2_1_11_1","volume-title":"White","author":"Demers Alan J.","year":"2007","unstructured":"Alan J. Demers , Johannes Gehrke , Biswanath Panda , Mirek Riedewald , Varun Sharma , and Walker M . White . 2007 . Cayuga : A General Purpose Event Monitoring System. In Third Biennial Conference on Innovative Data Systems Research, CIDR 2007, Asilomar, CA, USA, January 7-10, 2007, Online Proceedings . www.cidrdb.org, 412--422. http:\/\/cidrdb.org\/cidr2007\/papers\/cidr07p47.pdf Alan J. Demers, Johannes Gehrke, Biswanath Panda, Mirek Riedewald, Varun Sharma, and Walker M. White. 2007. Cayuga: A General Purpose Event Monitoring System. In Third Biennial Conference on Innovative Data Systems Research, CIDR 2007, Asilomar, CA, USA, January 7-10, 2007, Online Proceedings. www.cidrdb.org, 412--422. http:\/\/cidrdb.org\/cidr2007\/papers\/cidr07p47.pdf"},{"key":"e_1_2_1_12_1","volume-title":"An Evaluation of Non-Equijoin Algorithms. In 17th International Conference on Very Large Data Bases","author":"DeWitt David J.","year":"1991","unstructured":"David J. DeWitt , Jeffrey F. Naughton , and Donovan A. Schneider . 1991 . An Evaluation of Non-Equijoin Algorithms. In 17th International Conference on Very Large Data Bases , September 3-6, 1991 , Barcelona, Catalonia, Spain, Proceedings, Guy M. Lohman, Am\u00edlcar Sernadas, and Rafael Camps (Eds.). Morgan Kaufmann, 443--452. http:\/\/www.vldb.org\/conf\/ 1991\/P443.PDF David J. DeWitt, Jeffrey F. Naughton, and Donovan A. Schneider. 1991. An Evaluation of Non-Equijoin Algorithms. In 17th International Conference on Very Large Data Bases, September 3-6, 1991, Barcelona, Catalonia, Spain, Proceedings, Guy M. Lohman, Am\u00edlcar Sernadas, and Rafael Camps (Eds.). Morgan Kaufmann, 443--452. http:\/\/www.vldb.org\/conf\/1991\/P443.PDF"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Fifth ACM International Conference on Distributed Event-Based Systems, DEBS 2011","author":"Dindar Nihal","year":"2011","unstructured":"Nihal Dindar , Peter M. Fischer , Merve Soner , and Nesime Tatbul . 2011 . Efficiently correlating complex events over live and archived data streams . In Proceedings of the Fifth ACM International Conference on Distributed Event-Based Systems, DEBS 2011 , New York, NY, USA , July 11-15, 2011, David M. Eyers, Opher Etzion, Avigdor Gal, Stanley B. Zdonik, and Paul Vincent (Eds.). ACM, 243--254. 10.1145\/2002259.2002293 Nihal Dindar, Peter M. Fischer, Merve Soner, and Nesime Tatbul. 2011. Efficiently correlating complex events over live and archived data streams. In Proceedings of the Fifth ACM International Conference on Distributed Event-Based Systems, DEBS 2011, New York, NY, USA, July 11-15, 2011, David M. Eyers, Opher Etzion, Avigdor Gal, Stanley B. Zdonik, and Paul Vincent (Eds.). ACM, 243--254. 10.1145\/2002259.2002293"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329780"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Erkang Zhu and Silu Huang and Surajit Chaudhuri. 2022. High-Performance Row Pattern Recognition Using Joins (Technical Report). https:\/\/www.microsoft.com\/en-us\/research\/publication\/high-performance-row-pattern-recognition-using-joins-technical-report\/. Erkang Zhu and Silu Huang and Surajit Chaudhuri. 2022. High-Performance Row Pattern Recognition Using Joins (Technical Report). https:\/\/www.microsoft.com\/en-us\/research\/publication\/high-performance-row-pattern-recognition-using-joins-technical-report\/.","DOI":"10.14778\/3579075.3579090"},{"key":"e_1_2_1_17_1","unstructured":"Felipe Hoffa. 2021. Funnel analytics with SQL: MATCH_RECOGNIZE() on Snowflake. https:\/\/towardsdatascience.com\/funnel-analytics-with-sql-match-recognize-on-snowflake-8bd576d9b7b1. Felipe Hoffa. 2021. Funnel analytics with SQL: MATCH_RECOGNIZE() on Snowflake. https:\/\/towardsdatascience.com\/funnel-analytics-with-sql-match-recognize-on-snowflake-8bd576d9b7b1."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"1891","DOI":"10.14778\/3407790.3407797","article-title":"Adopting Worst-Case Optimal Joins in Relational Database Systems","volume":"13","author":"Freitag Michael J.","year":"2020","unstructured":"Michael J. Freitag , Maximilian Bandle , Tobias Schmidt , Alfons Kemper , and Thomas Neumann . 2020 . Adopting Worst-Case Optimal Joins in Relational Database Systems . Proc. VLDB Endow. 13 , 11 (2020), 1891 -- 1904 . http:\/\/www.vldb.org\/pvldb\/vol13\/p1891-freitag.pdf Michael J. Freitag, Maximilian Bandle, Tobias Schmidt, Alfons Kemper, and Thomas Neumann. 2020. Adopting Worst-Case Optimal Joins in Relational Database Systems. Proc. VLDB Endow. 13, 11 (2020), 1891--1904. http:\/\/www.vldb.org\/pvldb\/vol13\/p1891-freitag.pdf","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_19_1","unstructured":"Hector Garcia-Molina Jeffrey D. Ullman and Jennifer Widom. 2009. Database systems - the complete book (2. ed.). Pearson Education. Hector Garcia-Molina Jeffrey D. Ullman and Jennifer Widom. 2009. Database systems - the complete book (2. ed.). Pearson Education."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00557-w"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"e_1_2_1_22_1","first-page":"19","article-title":"The Cascades Framework for Query Optimization","volume":"18","author":"Graefe Goetz","year":"1995","unstructured":"Goetz Graefe . 1995 . The Cascades Framework for Query Optimization . IEEE Data Eng. Bull. 18 , 3 (1995), 19 -- 29 . http:\/\/sites.computer.org\/debull\/95SEP-CD.pdf Goetz Graefe. 1995. The Cascades Framework for Query Optimization. IEEE Data Eng. Bull. 18, 3 (1995), 19--29. http:\/\/sites.computer.org\/debull\/95SEP-CD.pdf","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_23_1","volume-title":"The Volcano Optimizer Generator: Extensibility and Efficient Search. In Proceedings of the Ninth International Conference on Data Engineering","author":"Graefe Goetz","year":"1993","unstructured":"Goetz Graefe and William J . McKenna. 1993 . The Volcano Optimizer Generator: Extensibility and Efficient Search. In Proceedings of the Ninth International Conference on Data Engineering , April 19-23, 1993 , Vienna, Austria. IEEE Computer Society, 209--218. 10.1109\/ICDE. 1993.344061 Goetz Graefe and William J. McKenna. 1993. The Volcano Optimizer Generator: Extensibility and Efficient Search. In Proceedings of the Ninth International Conference on Data Engineering, April 19-23, 1993, Vienna, Austria. IEEE Computer Society, 209--218. 10.1109\/ICDE.1993.344061"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data","author":"Haas Laura M.","year":"1989","unstructured":"Laura M. Haas , Johann Christoph Freytag , Guy M. Lohman , and Hamid Pirahesh . 1989 . Extensible Query Processing in Starburst . In Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data , Portland, Oregon, USA, May 31 - June 2, 1989, James Clifford, Bruce G. Lindsay, and David Maier (Eds.). ACM Press, 377--388. 10.1145\/67544.66962 Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, and Hamid Pirahesh. 1989. Extensible Query Processing in Starburst. In Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, USA, May 31 - June 2, 1989, James Clifford, Bruce G. Lindsay, and David Maier (Eds.). ACM Press, 377--388. 10.1145\/67544.66962"},{"key":"e_1_2_1_25_1","unstructured":"ISO\/IEC JTC 1\/SC 32 Data management and interchange. 2016. ISO\/IEC TR 19075-5:2016 Information technology - Database languages - SQL Technical Reports - Part 5: Row Pattern Recognition in SQL. https:\/\/www.iso.org\/standard\/65143.html. ISO\/IEC JTC 1\/SC 32 Data management and interchange. 2016. ISO\/IEC TR 19075-5:2016 Information technology - Database languages - SQL Technical Reports - Part 5: Row Pattern Recognition in SQL. https:\/\/www.iso.org\/standard\/65143.html."},{"key":"e_1_2_1_26_1","unstructured":"Kasia Findeisen. 2021. Row pattern recognition with MATCH_RECOGNIZE. https:\/\/trino.io\/blog\/2021\/05\/19\/row_pattern_matching.html. Kasia Findeisen. 2021. Row pattern recognition with MATCH_RECOGNIZE. https:\/\/trino.io\/blog\/2021\/05\/19\/row_pattern_matching.html."},{"key":"e_1_2_1_27_1","unstructured":"Keith Laker. 2017. MATCH_RECOGNIZE and predicates - everything you need to know. https:\/\/blogs.oracle.com\/datawarehousing\/post\/match_recognize-and-predicates-everything-you-need-to-know. Keith Laker. 2017. MATCH_RECOGNIZE and predicates - everything you need to know. https:\/\/blogs.oracle.com\/datawarehousing\/post\/match_recognize-and-predicates-everything-you-need-to-know."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2967101"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236189"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019","author":"Kolchinsky Ilya","year":"2019","unstructured":"Ilya Kolchinsky and Assaf Schuster . 2019 . Real-Time Multi-Pattern Detection over Event Streams . In Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019 , Amsterdam, The Netherlands, June 30 - July 5, 2019, Peter A. Boncz, Stefan Manegold, Anastasia Ailamaki, Amol Deshpande, and Tim Kraska (Eds.). ACM, 589--606. 10.1145\/3299869.3319869 Ilya Kolchinsky and Assaf Schuster. 2019. Real-Time Multi-Pattern Detection over Event Streams. In Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, Peter A. Boncz, Stefan Manegold, Anastasia Ailamaki, Amol Deshpande, and Tim Kraska (Eds.). ACM, 589--606. 10.1145\/3299869.3319869"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems, DEBS '15","author":"Kolchinsky Ilya","year":"2015","unstructured":"Ilya Kolchinsky , Izchak Sharfman , and Assaf Schuster . 2015 . Lazy evaluation methods for detecting complex events . In Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems, DEBS '15 , Oslo, Norway, June 29 - July 3, 2015, Frank Eliassen and Roman Vitenberg (Eds.). ACM, 34--45. 10.1145\/2675743.2771832 Ilya Kolchinsky, Izchak Sharfman, and Assaf Schuster. 2015. Lazy evaluation methods for detecting complex events. In Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems, DEBS '15, Oslo, Norway, June 29 - July 3, 2015, Frank Eliassen and Roman Vitenberg (Eds.). ACM, 34--45. 10.1145\/2675743.2771832"},{"key":"e_1_2_1_33_1","volume-title":"Index-Accelerated Pattern Matching in Event Stores. In SIGMOD '21: International Conference on Management of Data","author":"K\u00f6rber Michael","year":"2021","unstructured":"Michael K\u00f6rber , Nikolaus Glombiewski , and Bernhard Seeger . 2021 . Index-Accelerated Pattern Matching in Event Stores. In SIGMOD '21: International Conference on Management of Data , Virtual Event, China , June 20-25, 2021, Guoliang Li, Zhanhuai Li, Stratos Idreos, and Divesh Srivastava (Eds.). ACM, 1023--1036. 10.1145\/3448016.3457245 Michael K\u00f6rber, Nikolaus Glombiewski, and Bernhard Seeger. 2021. Index-Accelerated Pattern Matching in Event Stores. In SIGMOD '21: International Conference on Management of Data, Virtual Event, China, June 20-25, 2021, Guoliang Li, Zhanhuai Li, Stratos Idreos, and Divesh Srivastava (Eds.). ACM, 1023--1036. 10.1145\/3448016.3457245"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA]","author":"Li Rundong","year":"2020","unstructured":"Rundong Li , Wolfgang Gatterbauer , and Mirek Riedewald . 2020 . Near-Optimal Distributed Band-Joins through Recursive Partitioning . In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA] , June 14-19, 2020, David Maier, Rachel Pottinger, AnHai Doan, Wang-Chiew Tan, Abdussalam Alawini, and Hung Q. Ngo (Eds.). ACM, 2375--2390. 10.1145\/33 18464.3389750 Rundong Li, Wolfgang Gatterbauer, and Mirek Riedewald. 2020. Near-Optimal Distributed Band-Joins through Recursive Partitioning. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020, David Maier, Rachel Pottinger, AnHai Doan, Wang-Chiew Tan, Abdussalam Alawini, and Hung Q. Ngo (Eds.). ACM, 2375--2390. 10.1145\/3318464.3389750"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 27th International Conference on Data Engineering, ICDE 2011","author":"Liu Mo","year":"2011","unstructured":"Mo Liu , Elke A. Rundensteiner , Daniel J. Dougherty , Chetan Gupta , Song Wang , Ismail Ari , and Abhay Mehta . 2011 . High-performance nested CEP query processing over event streams . In Proceedings of the 27th International Conference on Data Engineering, ICDE 2011 , April 11-16, 2011, Hannover, Germany, Serge Abiteboul, Klemens B\u00f6hm, Christoph Koch, and Kian-Lee Tan (Eds.). IEEE Computer Society, 123--134. 10.1109\/ICDE. 2011.5767839 Mo Liu, Elke A. Rundensteiner, Daniel J. Dougherty, Chetan Gupta, Song Wang, Ismail Ari, and Abhay Mehta. 2011. High-performance nested CEP query processing over event streams. In Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11-16, 2011, Hannover, Germany, Serge Abiteboul, Klemens B\u00f6hm, Christoph Koch, and Kian-Lee Tan (Eds.). IEEE Computer Society, 123--134. 10.1109\/ICDE.2011.5767839"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/62061.62063"},{"key":"e_1_2_1_37_1","unstructured":"Marta Paes. 2019. MATCH_RECOGNIZE: where Flink SQL and Complex Event Processing meet. https:\/\/www.ververica.com\/blog\/match_recognize-where-flink-sql-and-complex-event-processing-meet. Marta Paes. 2019. MATCH_RECOGNIZE: where Flink SQL and Complex Event Processing meet. https:\/\/www.ververica.com\/blog\/match_recognize-where-flink-sql-and-complex-event-processing-meet."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2009","author":"Mei Yuan","year":"2009","unstructured":"Yuan Mei and Samuel Madden . 2009 . ZStream: a cost-based query processor for adaptively detecting composite events . In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2009 , Providence, Rhode Island, USA, June 29 - July 2, 2009, Ugur \u00c7etintemel, Stanley B. Zdonik, Donald Kossmann, and Nesime Tatbul (Eds.). ACM, 193--206. 10.1145\/1559845.1559867 Yuan Mei and Samuel Madden. 2009. ZStream: a cost-based query processor for adaptively detecting composite events. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2009, Providence, Rhode Island, USA, June 29 - July 2, 2009, Ugur \u00c7etintemel, Stanley B. Zdonik, Donald Kossmann, and Nesime Tatbul (Eds.). ACM, 193--206. 10.1145\/1559845.1559867"},{"key":"e_1_2_1_39_1","unstructured":"Microsoft Azure. 2021. MATCH_RECOGNIZE (Stream Analytics). https:\/\/docs.microsoft.com\/en-us\/stream-analytics-query\/match-recognize-stream-analytics. Microsoft Azure. 2021. MATCH_RECOGNIZE (Stream Analytics). https:\/\/docs.microsoft.com\/en-us\/stream-analytics-query\/match-recognize-stream-analytics."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'14","author":"Ngo Hung Q.","year":"2014","unstructured":"Hung Q. Ngo , Dung T. Nguyen , Christopher R\u00e9 , and Atri Rudra . 2014 . Beyond worst-case analysis for joins with minesweeper . In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'14 , Snowbird, UT, USA , June 22-27, 2014, Richard Hull and Martin Grohe (Eds.). ACM, 234--245. 10.1145\/2594538.2594547 Hung Q. Ngo, Dung T. Nguyen, Christopher R\u00e9, and Atri Rudra. 2014. Beyond worst-case analysis for joins with minesweeper. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'14, Snowbird, UT, USA, June 22-27, 2014, Richard Hull and Martin Grohe (Eds.). ACM, 234--245. 10.1145\/2594538.2594547"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_1_42_1","unstructured":"Oracle. 2022. Pattern Recognition With MATCH_RECOGNIZE. https:\/\/docs.oracle.com\/en\/middleware\/fusion-middleware\/osa\/19.1\/cqlreference\/pattern-recognition-match_recognize.html. Oracle. 2022. Pattern Recognition With MATCH_RECOGNIZE. https:\/\/docs.oracle.com\/en\/middleware\/fusion-middleware\/osa\/19.1\/cqlreference\/pattern-recognition-match_recognize.html."},{"key":"e_1_2_1_43_1","volume-title":"SRQL: Sorted Relational Query Language. In 10th International Conference on Scientific and Statistical Database Management","author":"Ramakrishnan Raghu","year":"1998","unstructured":"Raghu Ramakrishnan , Donko Donjerkovic , Arvind Ranganathan , Kevin S. Beyer , and Muralidhar Krishnaprasad . 1998 . SRQL: Sorted Relational Query Language. In 10th International Conference on Scientific and Statistical Database Management , Proceedings, Capri, Italy , July 1-3, 1998, Maurizio Rafanelli and Matthias Jarke (Eds.). IEEE Computer Society, 84--95. 10.1109\/SSDM.1998.688114 Raghu Ramakrishnan, Donko Donjerkovic, Arvind Ranganathan, Kevin S. Beyer, and Muralidhar Krishnaprasad. 1998. SRQL: Sorted Relational Query Language. In 10th International Conference on Scientific and Statistical Database Management, Proceedings, Capri, Italy, July 1-3, 1998, Maurizio Rafanelli and Matthias Jarke (Eds.). IEEE Computer Society, 84--95. 10.1109\/SSDM.1998.688114"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016","author":"Ray Medhabi","year":"2016","unstructured":"Medhabi Ray , Chuan Lei , and Elke A. Rundensteiner . 2016. Scalable Pattern Sharing on Event Streams . In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016 , San Francisco, CA, USA, June 26 - July 01, 2016 , Fatma \u00d6zcan, Georgia Koutrika, and Sam Madden (Eds.). ACM, 495--510. 10.1145\/2882903.2882947 Medhabi Ray, Chuan Lei, and Elke A. Rundensteiner. 2016. Scalable Pattern Sharing on Event Streams. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016, Fatma \u00d6zcan, Georgia Koutrika, and Sam Madden (Eds.). ACM, 495--510. 10.1145\/2882903.2882947"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","first-page":"3018","DOI":"10.14778\/3551793.3551849","article-title":"A Scalable and Generic Approach to Range Joins","volume":"15","author":"Reif Maximilian","year":"2022","unstructured":"Maximilian Reif and Thomas Neumann . 2022 . A Scalable and Generic Approach to Range Joins . Proc. VLDB Endow. 15 , 11 (2022), 3018 -- 3030 . https:\/\/www.vldb.org\/pvldb\/vol15\/p3018-reif.pdf Maximilian Reif and Thomas Neumann. 2022. A Scalable and Generic Approach to Range Joins. Proc. VLDB Endow. 15, 11 (2022), 3018--3030. https:\/\/www.vldb.org\/pvldb\/vol15\/p3018-reif.pdf","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_46_1","unstructured":"Rodrigo Alves. 2019. Azure Stream Analytics now supports MATCH_RECOGNIZE. https:\/\/azure.microsoft.com\/en-us\/blog\/azure-stream-analytics-now-supports-match-recognize\/. Rodrigo Alves. 2019. Azure Stream Analytics now supports MATCH_RECOGNIZE. https:\/\/azure.microsoft.com\/en-us\/blog\/azure-stream-analytics-now-supports-match-recognize\/."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005566.1005568"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data","author":"Selinger Patricia G.","year":"2095","unstructured":"Patricia G. Selinger , Morton M. Astrahan , Donald D. Chamberlin , Raymond A. Lorie , and Thomas G. Price . 1979. Access Path Selection in a Relational Database Management System . In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data , Boston, Massachusetts, USA, May 30 - June 1, Philip A. Bernstein (Ed.). ACM, 23--34. 10.1145\/58 2095 .582099 Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, and Thomas G. Price. 1979. Access Path Selection in a Relational Database Management System. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston, Massachusetts, USA, May 30 - June 1, Philip A. Bernstein (Ed.). ACM, 23--34. 10.1145\/582095.582099"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data","author":"Seshadri Praveen","year":"1994","unstructured":"Praveen Seshadri , Miron Livny , and Raghu Ramakrishnan . 1994 . Sequence Query Processing . In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data , Minneapolis, Minnesota, USA , May 24-27, 1994, Richard T. Snodgrass and Marianne Winslett (Eds.). ACM Press, 430--441. 10.1145\/191839.191926 Praveen Seshadri, Miron Livny, and Raghu Ramakrishnan. 1994. Sequence Query Processing. In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, USA, May 24-27, 1994, Richard T. Snodgrass and Marianne Winslett (Eds.). ACM Press, 430--441. 10.1145\/191839.191926"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the Eleventh International Conference on Data Engineering","author":"Seshadri Praveen","year":"1995","unstructured":"Praveen Seshadri , Miron Livny , and Raghu Ramakrishnan . 1995 . SEQ: A Model for Sequence Databases . In Proceedings of the Eleventh International Conference on Data Engineering , March 6-10, 1995, Taipei, Taiwan, Philip S. Yu and Arbee L. P. Chen (Eds.). IEEE Computer Society, 232--239. 10.1109\/ICDE. 1995.380388 Praveen Seshadri, Miron Livny, and Raghu Ramakrishnan. 1995. SEQ: A Model for Sequence Databases. In Proceedings of the Eleventh International Conference on Data Engineering, March 6-10, 1995, Taipei, Taiwan, Philip S. Yu and Arbee L. P. Chen (Eds.). IEEE Computer Society, 232--239. 10.1109\/ICDE.1995.380388"},{"key":"e_1_2_1_51_1","volume-title":"VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases","author":"Seshadri Praveen","year":"1996","unstructured":"Praveen Seshadri , Miron Livny , and Raghu Ramakrishnan . 1996. The Design and Implementation of a Sequence Database System . In VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases , September 3-6, 1996 , Mumbai (Bombay), India, T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, and Nandlal L. Sarda (Eds.). Morgan Kaufmann , 99--110. http:\/\/www.vldb.org\/conf\/1996\/P099.PDF Praveen Seshadri, Miron Livny, and Raghu Ramakrishnan. 1996. The Design and Implementation of a Sequence Database System. In VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India, T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, and Nandlal L. Sarda (Eds.). Morgan Kaufmann, 99--110. http:\/\/www.vldb.org\/conf\/1996\/P099.PDF"},{"key":"e_1_2_1_52_1","unstructured":"Snowflake. 2021. Identifying Sequences of Rows That Match a Pattern. https:\/\/docs.snowflake.com\/en\/user-guide\/match-recognize-introduction.html. Snowflake. 2021. Identifying Sequences of Rows That Match a Pattern. https:\/\/docs.snowflake.com\/en\/user-guide\/match-recognize-introduction.html."},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the Ninth International Conference on Data Engineering","author":"Soloviev Valery","year":"1993","unstructured":"Valery Soloviev . 1993 . A Truncating Hash Algorithm for Processing Band-Join Queries . In Proceedings of the Ninth International Conference on Data Engineering , April 19-23, 1993, Vienna, Austria. IEEE Computer Society, 419--427. 10.1109\/ICDE. 1993.344039 Valery Soloviev. 1993. A Truncating Hash Algorithm for Processing Band-Join Queries. In Proceedings of the Ninth International Conference on Data Engineering, April 19-23, 1993, Vienna, Austria. IEEE Computer Society, 419--427. 10.1109\/ICDE.1993.344039"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3226595.3226638"},{"key":"e_1_2_1_55_1","unstructured":"Trino. 2022. MATCH_RECOGNIZE. https:\/\/trino.io\/docs\/current\/sql\/match-recognize.html. Trino. 2022. MATCH_RECOGNIZE. https:\/\/trino.io\/docs\/current\/sql\/match-recognize.html."},{"key":"e_1_2_1_56_1","volume-title":"Worst-Case Optimal Join Algorithm. In Proc. 17th International Conference on Database Theory (ICDT)","author":"Veldhuizen Todd L.","year":"2014","unstructured":"Todd L. Veldhuizen . 2014 . Triejoin: A Simple , Worst-Case Optimal Join Algorithm. In Proc. 17th International Conference on Database Theory (ICDT) , Athens, Greece , March 24-28, 2014, Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy (Eds.). OpenProceedings.org, 96--106. 10.5441\/002\/icdt.2014.13 Todd L. Veldhuizen. 2014. Triejoin: A Simple, Worst-Case Optimal Join Algorithm. In Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014, Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy (Eds.). OpenProceedings.org, 96--106. 10.5441\/002\/icdt.2014.13"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Wu Eugene","year":"2006","unstructured":"Eugene Wu , Yanlei Diao , and Shariq Rizvi . 2006 . High-performance complex event processing over streams . In Proceedings of the ACM SIGMOD International Conference on Management of Data , Chicago, Illinois, USA , June 27-29, 2006, Surajit Chaudhuri, Vagelis Hristidis, and Neoklis Polyzotis (Eds.). ACM, 407--418. 10.1145\/1142473.1142520 Eugene Wu, Yanlei Diao, and Shariq Rizvi. 2006. High-performance complex event processing over streams. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, USA, June 27-29, 2006, Surajit Chaudhuri, Vagelis Hristidis, and Neoklis Polyzotis (Eds.). ACM, 407--418. 10.1145\/1142473.1142520"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3579075.3579090","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T17:06:40Z","timestamp":1679936800000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3579075.3579090"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1]]},"references-count":56,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["10.14778\/3579075.3579090"],"URL":"https:\/\/doi.org\/10.14778\/3579075.3579090","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,1]]},"assertion":[{"value":"2023-03-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}