Задача поиска по образцу на последовательности строк БД может возникать в различных сферах деятельности. Например, в финансовой аналитике — поиск определённых паттернов изменения цены акций; в системах борьбы с мошенничеством (AntiFraud) — поиск последовательностей событий, которые могут свидетельствовать о подозрительной активности, а также в IoT и многих других.

Для реализации таких запросов к базам данных в стандарте SQL:2016 была введена конструкция MATCH_RECOGNIZE, которая постепенно появляется в популярных базах данных с тем или иным набором ограничений, т. к. конструкция довольно сложная и имеет большое количество особенностей и режимов работы.

В своём докладе я расскажу о реализации MATCH_RECOGNIZE в YDB: о том, как это работает под капотом, какие подходы и алгоритмы реализованы, с какими сложностями мы столкнулись.

Отдельная часть выступления будет посвящена отличиям в обработке аналитических запросов на табличках и обработке на потоках «живых» данных. Какие возникают ограничения при обработке потоков, как бороться с большим стейтом, необходимым для накопления цепочек совпадений на сложных образцах и пр.