行パターン認識の概要とその実装について

行パターン認識とは

SQL標準では「行パターン認識」(英語では Row Pattern Recognition, 略してRPR)という機能が定義されており、従来からあるWHERE句やHAVINGなどを使った検索機能では対応が難しかった、ある種の問い合わせに対応しています。

行パターン認識がよく使われる検索対象データは、一定の順で行が並んだデータ、とりわけ時系列データです。すなわち、時間とともに変化するデータです。
たとえば毎日の最高気温が記録されたテーブルがあるとします。

日にち 最高気温
2024/8/1 29
2024/8/2 30
2024/8/3 31
2024/8/4 32
2024/8/5 28
2024/8/6 30
2024/8/7 29

ここで、当日よりも翌日の最高気温が高かった日をRPRを用いないで従来のSQLで求めるには、たとえば次のようなクエリを使います。

SELECT s1.date, s1.degree FROM temperature s1, temperature s2
WHERE s1.date = (s2.date - '1day'::INTERVAL) AND s1.degree < s2.degree;

テーブル名はtemperature、日付の列名が"date"、最高気温の列名は"degree"です。自己結合を使い、テーブル別名s1が当日、s2が翌日となっています。

結果は次のようになります。

    date    | degree 
------------+--------
 2024-08-01 |     29
 2024-08-02 |     30
 2024-08-03 |     31
 2024-08-05 |     28
(4 rows)

では、2日間の比較ではなく、「3日続けて当日よりも翌日の最高気温が高かった日付」を求めるにはどうした良いでしょう?この場合はs1, s2に加えてs3を作れば問い合わせ可能です。s3が「3日目」になるわけですね[注1]

それでは「2日以上続けて当日よりも翌日の最高気温が高かった日付」はどうでしょう?これは難しいです。「2日以上」は2日かもしれないし、3日かもしれません。日数が確定しないと自己結合は使えません。

このような時系列データの問い合わせを簡単にし、かつ更に複雑な検索を可能にするのが行パターン認識です。

行パターン認識の使い方

SQL標準が定義する行パターン認識は2種類の構文がありますが、ここでは現在PostgreSQLコミュニティに実装が提案されている、Window句で使用する行パターン認識を例にとって説明します。(もう一種類の構文は[1]で紹介されています。
また、このブログは行パターン認識をわかりやすく解説しており、おすすめです)

まず、Window句で上記テーブルを検索するクエリを作ります。

SELECT date, degree, count(*) OVER w  FROM temperature
 WINDOW w AS (
 ORDER BY date
 ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
);

    date    | degree | count 
------------+--------+-------
 2024-08-01 |     29 |     7
 2024-08-02 |     30 |     6
 2024-08-03 |     31 |     5
 2024-08-04 |     32 |     4
 2024-08-05 |     28 |     3
 2024-08-06 |     30 |     2
 2024-08-07 |     29 |     1
(7 rows)

この例では、単にテーブル内容を全件表示しているだけです。count列は各フレームの行数です。ここでは ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING を指定しているため、各フレームは現在行から最後の行までになっています。

先ほどの「当日よりも翌日の最高気温が高かった日」を行パターン認識で求めるには、これに2行ほど追加します。

SELECT date, degree, count(*) OVER w  FROM temperature
 WINDOW w AS (
 ORDER BY date
 ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
 PATTERN (UP)	-- 追加
 DEFINE UP AS degree < NEXT(degree)	-- 追加
);

DEFINE... は、行パターン認識で使用する変数の定義です。ここでは"UP"という変数は"degree < NEXT(degree)"という論理式を満たすことが定義されています。NEXTは行パターン認識で使用できる関数(正確には関数ではなく"row navigation operation"と呼ばれます)で、「次の行」を指しています。ですからこの定義の意味は、「現在行のdegreeが次の行より小さい」です。つまり「当日よりも翌日の最高気温が高かった」という意味で、これは最初の自己結合の例と同じです。 次に、一致させたい行のパターンを"PATTERN (UP)"で定義します。 これは「UPを満たす行を検索する」という意味です。 このクエリを実行すると、以下の結果が得られます。

    date    | degree | count 
------------+--------+-------
 2024-08-01 |     29 |     1
 2024-08-02 |     30 |     1
 2024-08-03 |     31 |     1
 2024-08-04 |     32 |     0
 2024-08-05 |     28 |     1
 2024-08-06 |     30 |     0
 2024-08-07 |     29 |     0
(7 rows)

行パターンにマッチしたかどうかはcount列で確認でき、1になっている行がマッチした行です。
countが0の行を無視すれば、自己結合のクエリと同じ結果になっていることがわかります。

では、自己結合の例で難しいとした、「2日以上続けて当日よりも翌日の最高気温が高かった日付」を求めてみましょう。

SELECT date, degree, count(*) OVER w  FROM temperature
 WINDOW w AS (
 ORDER BY date
 ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
 PATTERN (UP UP+)
 DEFINE UP AS degree < NEXT(degree)
);

    date    | degree | count 
------------+--------+-------
 2024-08-01 |     29 |     3
 2024-08-02 |     30 |     0
 2024-08-03 |     31 |     0
 2024-08-04 |     32 |     0
 2024-08-05 |     28 |     0
 2024-08-06 |     30 |     0
 2024-08-07 |     29 |     0
(7 rows)

検索結果を満たす行は、8/1, 8/2, 8/3の3日で、countもその分3になっています。

前回のクエリからは、

 PATTERN (UP+)

 PATTERN (UP UP+)

にしただけです。最初の"UP"で1日だけパターンマッチし、次の"UP+"で更に1日以上パターンマッチすることが指定されています。これで合計2日以上のパターンマッチになったわけです。

次に、行パターン認識ならではのもう少し複雑な問い合わせの例を考えてみます。最高気温が一旦下がった後、再び上昇した日にちを求めてみましょう。今回の例で言うと、8/4、8/5、8/6がその答えになります。クエリは以下のようになります。

SELECT date, degree, count(*) OVER w  FROM temperature
 WINDOW w AS (
 ORDER BY date
 ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
 PATTERN (START DOWN+ UP+)
 DEFINE
  START AS TRUE,
  DOWN AS degree < PREV(degree),
  UP AS degree > PREV(degree)
);

PATTERN句では、まず必ず真になるSTARTという変数を使って、最初の行をパターンマッチ開始の開始行とします[注2]。その次の"DOWN"は、前日よりも最高気温が低いという論理式を、NEXTと逆の意味(前の行)を持つPREVを使って定義しています[注3]。"UP"はDOWNの反対の意味ですね。以上で、「ある行からスタートし、2日目以降前日よりも最高気温が低下する日が続き、その後前日よりも最高気温が上昇する」というパターンが定義できました。早速実行してみると、予想通り、8/4から3日間が求めるパターンにマッチしていることが確認できました。

   date    | degree | count 
------------+--------+-------
 2024-08-01 |     29 |     0
 2024-08-02 |     30 |     0
 2024-08-03 |     31 |     0
 2024-08-04 |     32 |     3
 2024-08-05 |     28 |     0
 2024-08-06 |     30 |     0
 2024-08-07 |     29 |     0
(7 rows)

このように、行パターンに認識を使うと、従来の構文では難しかった問い合わせを表現するクエリを簡単に作成することができます。

[2][3]に行パターン認識を使った他のクエリの例が紹介されていますので、よろしければそちらもご覧ください。

行パターン認識の実装について

強力な表現力を持つ行パターン認識ですが、まだまだ実装例は少なく、PostgreSQLにも実装されていません。そこで筆者はPostgreSQL向けの開発を進めており、すでに開発コミュニティに対してパッチを提案中です[4]。先ほどの例も、実際にそのパッチを適用したPostgreSQLで出力したものです。

SQL標準では2種類の行パターン認識の構文を定義しており、今回ご紹介するパッチはWindow句で行パターン認識を記述するものです。ここでは、現時点(2024年10月)でパッチに含まれている機能をご紹介します。

PATTERN句における正規表現の利用

先ほどの例で"UP+"が正規表現です。"UP+"と"UP"の違いは、"UP"がある1行がマッチしているのに対し、"UP+"は1行以上の行がマッチしていることを表します。パッチでは、"+"以外に"*"(0行以上にマッチ)が使えます。ちなみにSQL標準では他に以下の正規表現が定義されています。

?: 0または1行
A | B: OR条件
(A B): グルーピング
{n}: n行
{n,}: n行以上
{n,m}: n行以上m行以下
{,m}: 0行以上m行以下

AFTER MATCH SKIP句

パターンマッチした後、次のパターンマッチをどの行から再開するか指定します。先ほどの例では、AFTER MATCH SKIP句が省略されていたのでデフォルトのAFTER MATCH SKIP PAST LAST ROWが指定されていると見なされました。

    date    | degree | count 
------------+--------+-------
 2024-08-01 |     29 |     3
 2024-08-02 |     30 |     0
 2024-08-03 |     31 |     0
 2024-08-04 |     32 |     0

そして8/1-3の3行にマッチした後、8/4からパターンマッチが再開されました。
AFTER MATCH SKIP TO NEXT ROWを指定すると、次のパターンマッチは8/2から再開されます。その結果、8/2, 8/3の2行にパターンマッチします。

SELECT date, degree, count(*) OVER w  FROM temperature
 WINDOW w AS (
 ORDER BY date
 ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
 AFTER MATCH SKIP TO NEXT ROW
 PATTERN (UP+)
 DEFINE UP AS degree < NEXT(degree)
);
    date    | degree | count 
------------+--------+-------
 2024-08-01 |     29 |     3
 2024-08-02 |     30 |     2
 2024-08-03 |     31 |     1
 2024-08-04 |     32 |     0
 2024-08-05 |     28 |     1
 2024-08-06 |     30 |     0
 2024-08-07 |     29 |     0
(7 rows)

このようにAFTER MATCH SKIP TO NEXT ROWを指定するとパターンマッチした行の集合の重なりが発生します。

DEFINE句

NEXTの他に、逆の意味(一つ前の行)のPREVもサポートされています。
なお、SQL標準では、DEFINE句で集約関数や副問合せも使用できることになっていますが、パッチではサポートしていません。

まとめ

行パターン認識の基礎と簡単な使用例、そして実装中のパッチをご紹介しました。

行パターン認識は重要な機能であり、是非PostgreSQLにも実装されることが望まれます。

現在開発中のパッチはSQL標準で定められたすべての機能を実装しているわけではなく、実用上必須と思われる機能のみを実装しています。PostgreSQLコミュニティでは、作れば直ちにそのパッチが採用されるわけではなく、他の開発者の厳格なレビューに合格してはじめてパッチが採用されます。パッチが大きくなれば、レビューする人の負担も増えるのでは、まずは必要最低限の機能で極力レビューの負担を減らした上でPostgreSQLに取り込み、その後で徐々に機能を追加して充実させていきたいと考えています。

  • [注1] Window句を使っても同じクエリが書けます。

    SELECT * FROM (SELECT date, degree, lead(degree) OVER w next1,
    lead(degree, 2) OVER w next2 FROM temperature WINDOW w AS (ORDER BY
    date ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)) s WHERE next1 > degree
    AND next1 > next2;
    
  • [注2] パターン句で使用する変数の定義がDEFINE句にない場合は、"変数 AS TRUE"と定義したものと見なされます。よって、今回の例では、DEFINE句でSTARTの定義を省略することが可能です。
  • [注3] PREVではなく、NEXTを使っても同じ意味を持つクエリを書けますが、少し直感的にわかりにくいかも知れません。

参考URL