博客

2020/08/27

使用 Beam SQL 进行模式匹配

Mark Zeng

简介

SQL 在数据分析领域变得越来越强大和有用。MATCH_RECOGNIZE 是 2016 年引入的一种新的 SQL 组件，它带来了额外的分析功能。这个项目是 Google Summer of Code 的一部分，旨在支持基本的 MATCH_RECOGNIZE 功能。一个基本的 MATCH_RECOGNIZE 查询将类似于以下内容

SELECT T.aid, T.bid, T.cid
FROM MyTable
    MATCH_RECOGNIZE (
      PARTITION BY userid
      ORDER BY proctime
      MEASURES
        A.id AS aid,
        B.id AS bid,
        C.id AS cid
      PATTERN (A B C)
      DEFINE
        A AS name = 'a',
        B AS name = 'b',
        C AS name = 'c'
    ) AS T

上面的查询找出具有名称“a”，“b”和“c”的事件的有序集。除了 MATCH_RECOGNIZE 的基本用法之外，我还支持一些其他关键功能，例如量词和行模式导航。我将在后面的部分详细说明。

方法与讨论

该实现强烈依赖于 BEAM 核心转换。具体来说，一个 MATCH_RECOGNIZE 执行将组成以下一系列转换

  1. 一个 ParDo 转换，然后是一个 GroupByKey 转换，用于构建分区 (PARTITION BY)。
  2. 一个 ParDo 转换，用于对每个分区进行排序 (ORDER BY)。
  3. 一个 ParDo 转换，用于在每个排序的分区中应用模式匹配。

模式匹配操作最初使用 java 正则表达式库完成。也就是说，我首先将分区中的行转换为字符串，然后应用正则表达式模式匹配例程。如果一行满足某个条件，那么我会输出相应的模式变量。这在模式定义互斥的假设下是可以的。也就是说，像 A AS A.price > 0, B AS b.price < 0 这样的模式定义是允许的，而像 A AS A.price > 0, B AS B.proctime > 0 这样的模式定义可能会导致匹配不完整。对于后一种情况，事件可以同时满足条件 A 和 B。互斥条件使模式匹配确定性：每个事件最多只能属于一个模式类。

如 SQL 2016 文档中所述，MATCH_RECOGNIZE 定义了一组比正则表达式更丰富的表达式。具体来说，它引入了行模式导航操作，例如 PREV 和 NEXT。这也许是 MATCH_RECOGNIZE 最吸引人的功能之一。正则表达式库将不再满足需要，因为模式定义可能是反向引用 (PREV) 或正向引用 (NEXT)。因此，对于第二版实现，我们选择使用 NFA 正则表达式引擎。NFA 在非确定性方面带来了更大的灵活性（有关更详细的讨论，请参阅 SQL 2016 第 5 部分第 6 章）。我提出的 NFA 基于马萨诸塞大学的一篇论文。

这是一个正在进行的项目。许多组件仍未得到支持。我将在未来的工作部分列出一些未实现的工作。

用法

目前，我支持的组件是

  • PARTITION BY
  • ORDER BY
  • MEASURES
    1. LAST
    2. FIRST
  • ONE ROW PER MATCH/ALL ROWS PER MATCH
  • DEFINE
    1. 条件的左侧
      1. LAST
    2. 条件的右侧
      1. PREV
  • 量词
    1. 克莱尼加

模式定义评估是硬编码的。更准确地说，它期望传入行的列引用位于比较运算符的左侧。此外，PREV 函数只能出现在比较运算符的右侧。

使用这些有限的工具，我们已经可以编写一些稍微复杂的查询。假设我们有以下表格

transTimeprice
13
22
31
45
56

此表反映了产品相对于交易时间的价格变化。我们可以编写以下查询

SELECT *
FROM MyTable
    MATCH_RECOGNIZE (
      ORDER BY transTime
      MEASURES
        LAST(A.price) AS beforePrice,
        FIRST(B.price) AS afterPrice
      PATTERN (A+ B+)
      DEFINE
        A AS price < PREV(A.price),
        B AS price > PREV(B.price)
    ) AS T

这将找到局部最小价格及其后的价格。对于示例数据集，前 3 行将映射到 A，其余行将映射到 B。因此，我们将得到 (1, 5) 作为结果。

非常重要：对于我的 NFA 实现，它稍微违反了 SQL 标准中的规则。由于缓冲的 NFA 仅在事件与某个模式类匹配时才将事件存储到缓冲区中，因此如果前面的行被丢弃，将无法获取前面的事件。因此，如果使用 PREV，第一行将始终匹配（与标准不同）。

进度

  1. PR
    1. 使用正则表达式库支持 MATCH_RECOGNIZE (已合并)
    2. 使用 NFA 支持 MATCH_RECOGNIZE (待定)
  2. 提交
    1. 分区：commit 064ada7
    2. 排序：commit 9cd1a82
    3. 正则表达式模式匹配：commit 8d6ffcc
    4. 支持量词：commit f529b87
    5. 度量：commit 8793574
    6. 添加 NFA 实现：commit fc731f2
    7. 实现函数 PREV 和 LAST：commit 35323da

未来的工作

  • 支持 FINAL/RUNNING 关键字。
  • 支持更多量词。
  • 对 NFA 添加优化。
  • 实现 MATCH_RECOGNIZE 的一种更好的方法可能是拥有 BEAM 核心中的复杂事件处理库（而不是使用 BEAM 转换）。

参考