ブログ

2020/08/27

Beam SQLにおけるパターンマッチング

Mark Zeng

はじめに

SQLはデータ分析の分野でますます強力で有用になっています。2016年に導入された新しいSQLコンポーネントであるMATCH_RECOGNIZEは、追加の分析機能を提供します。このプロジェクトは、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コア変換に基づいています。具体的には、1つのMATCH_RECOGNIZE実行は、次の変換シリーズで構成されます。

  1. パーティション（PARTITION BY）を構築するParDo変換とGroupByKey変換。
  2. 各パーティション内でソートする（ORDER BY）ParDo変換。
  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を満たす可能性があります。相互に排他的な条件は、決定論的なパターンマッチングを与えます。各イベントは、高々1つのパターン分類にのみ属することができます。

SQL 2016ドキュメントで指定されているように、MATCH_RECOGNIZEは正規表現よりも豊富な式のセットを定義します。具体的には、PREVやNEXTなどの行パターンナビゲーション操作を導入しています。これはおそらく、MATCH_RECOGNIZEの最も興味深い機能の1つです。パターン定義がバックリファレンス（PREV）またはフォワードリファレンス（NEXT）になる可能性があるため、正規表現ライブラリではもはや必要ありません。そのため、2番目の実装バージョンでは、NFA正規表現エンジンを使用することを選択しました。NFAは、非決定性に関してより多くの柔軟性を提供します（より詳細な説明については、SQL 2016 Part 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. クリーネプラス

パターン定義の評価はハードコーディングされています。より具体的には、入力行の列参照がコンパレータの左側に存在することを期待しています。さらに、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. PRs
    1. 正規表現ライブラリを使用したMATCH_RECOGNIZEのサポート (マージ済み)
    2. NFAを使用したMATCH_RECOGNIZEのサポート (保留中)
  2. コミット
    1. partition by: commit 064ada7
    2. order by: commit 9cd1a82
    3. regex pattern match: 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コアにComplex Event Processingライブラリを持つことかもしれません。

参考文献