部落格

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 regex 庫完成。也就是說，我首先將分區內的行轉換為字串，然後套用 regex 模式匹配例程。如果某一行滿足條件，則我會輸出對應的模式變數。這在模式定義互斥的假設下是可行的。也就是說，允許像 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 是基於 UMASS 的一篇論文。

這是一個正在進行的專案。許多組件仍未支援。我將在未來工作部分列出一些未完成的工作。

用法

目前，我支援的組件有

  • 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. Kleene 加號

模式定義評估是硬式編碼的。更具體地說，它期望輸入行的欄位參考位於比較子的左側。此外，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. partition by: commit 064ada7
    2. order by: commit 9cd1a82
    3. regex 模式匹配: commit 8d6ffcc
    4. 支援量詞: commit f529b87
    5. measures: commit 8793574
    6. 新增 NFA 實作: commit fc731f2
    7. 實作函數 PREV 和 LAST: commit 35323da

未來工作

  • 支援 FINAL/RUNNING 關鍵字。
  • 支援更多量詞。
  • 為 NFA 添加最佳化。
  • 實現 MATCH_RECOGNIZE 的更好方法可能是在 BEAM 核心中擁有一個複雜事件處理庫（而不是使用 BEAM 轉換）。

參考資料