T-Rex: Optimizing Pattern Search on Time Series

• Published in: Proceedings of the ACM on management of data 2023-06, Vol.1 (2), p.1-26, Article 130
• Main Authors: Huang, Silu, Zhu, Erkang, Chaudhuri, Surajit, Spiegelberg, Leonhard
• Format: Article
• Language: English
• Subjects: Data management systems; Database management system engines; Information systems; Online analytical processing engines
• ISSN: 2836-6573; 2836-6573
• DOI: 10.1145/3589275

Pattern search is an important class of queries for time series data. Time series patterns often match variable-length segments with a large search space, thereby posing a significant performance challenge. The existing pattern search systems, for example, SQL query engines supporting MATCH_RECOGNIZE, are ineffective in pruning the large search space of variable-length segments. In many cases, the issue is due to the use of a restrictive query language modeled on time series points and a computational model that limits search space pruning. We built T-ReX to address this problem using two main building blocks: first, a MATCH_RECOGNIZE language extension that exposes the notion of segment variable and adds new operators, lending itself to better optimization; second, an executor capable of pruning the search space of matches and minimizing total query time using an optimizer. We conducted experiments using 5 real-world datasets and 11 query templates, including those from existing works. T-ReX outperformed an optimized NFA-based pattern search executor by 6x in median query time and an optimized tree-based executor by 19X.