​ ​
1__tmux.png

再帰 CTE で牛の授精回数を数えてみる

こんにちは、ファームノートクラウド開発グループの永沼です。先日、山の日という祝日が増えているのに気づきびっくりしました。山登りするならもうちょっと涼しくなってきてからがいいなあと思っています。

Farmnote は現在バックエンドとして PostgreSQL を利用しています。PostgreSQL といえば最近は MySQL との内部の実装アーキテクチャ比較の話が話題となっていました。ご覧になった方も多いのではないでしょうか?

内部のアーキテクチャもそうなのですが、PostgreSQL と MySQL では機能面でも多々違いがあります。今回は PostgreSQL に実装されていて MySQL での実装がない内のひとつである CTE を紹介したいと思います。

CTE とは

PostgreSQL日本語ドキュメントによると以下のように説明されています。

WITHは、より大規模な問い合わせで使用される補助文を記述する方法を提供します。 これらの文は共通テーブル式(Common Table Expressions)またはCTEとよく呼ばれるものであり、1つの問い合わせのために存在する一時テーブルを定義すると考えることができます。

個人的には以下のような場面で利用することが多いように思います。

  1. 2つ以上の同じ問い合わせを行うサブクエリをCTEに移動し、問い合わせ回数を減らす
  2. 一時的なデータセットを CTE で定義する
  3. 再帰した問い合わせを行う

上に挙げたものの中で 3 については通常の SQL では実現できません。今回はこちらについて Farmnote での実際の利用例にもとづいて紹介していきます。

再帰 CTE で授精回数を数えてみる

今日の日本では乳牛や肉牛の多くが人工授精で繁殖が行われています。牛の発情を目安として精液の注入を行うのですが、発情の間で複数回注入を行うことがあります。これは牛の1回の生理周期(平均21日と言われている)に対する授精のため、日本では慣例として注入当日、翌日、翌々日の注入をまとめて1回の授精として数えることが多いそうです。

今回はこの授精回数のカウントを再帰 CTE で実装してみたいと思います。ここでは簡単のため、注入があった場合、そこからさらに翌々日までの注入も1回としてカウントすることとします。

注入日と授精回数は以下のような関係になっていれば OK です。

  • 1/1、1/3 に注入:1回
  • 1/1、1/4 に注入:2回
  • 1/1、1/2、1/4 に注入:1回

実装してみた

ざっくり書いてみたところ以下のようになりました。まずはご覧ください。

      -- 注入実施(牛, 日付)データ
    WITH introductions(cow_id, date) AS
         (
           VALUES (1, '2016-01-01'::DATE), (1, '2016-01-03'::DATE),
                  (2, '2016-01-01'::DATE), (2, '2016-01-04'::DATE),
                  (3, '2016-01-01'::DATE), (3, '2016-01-02'::DATE), (3, '2016-01-04'::DATE)
         ),
      -- 人口授精(牛, 最初の注入日, 最後の注入日)
         inseminations(cow_id, begin_at, end_at) AS
         (
                       -- 再帰 CTE で1回の授精と数える区間をつなげていく
           WITH RECURSIVE midstream(cow_id, begin_at, end_at) AS
                          (
                                -- 初期データ
                            SELECT cow_id,
                                   date,
                                   date
                              FROM introductions
                             UNION
                                -- 再帰処理部分
                            SELECT cow_id,
                                   begin_at,
                                   CASE WHEN end_at + INTERVAL '2 DAYS' >= LEAD(begin_at) OVER same_cow
                                        THEN LEAD(end_at) OVER same_cow
                                        ELSE NULL
                                   END
                              FROM midstream
                             WHERE NOT end_at IS NULL
                            WINDOW same_cow AS (PARTITION BY cow_id ORDER BY begin_at, end_at)
                          )
                       -- 計算途中の区間を除去して結果だけを取り出す                                                                                                                                                                                    SELECT *
                     FROM midstream
                    WHERE NOT end_at IS NULL
                      AND NOT DATERANGE(begin_at, end_at, '[]') <@ ANY
                          (
                            SELECT DATERANGE(sub.begin_at, sub.end_at, '[]')
                              FROM midstream AS sub
                             WHERE NOT sub.end_at IS NULL
                               AND midstream.cow_id = sub.cow_id
                               AND DATERANGE(midstream.begin_at, midstream.end_at, '[]') <> DATERANGE(sub.begin_at, sub.end_at, '[]')
                          )
         )
      -- CTE の結果に問い合わせ
  SELECT *
    FROM inseminations
ORDER BY cow_id, begin_at

長いですね・・・チョット難しい題材を選んでしまったような気がします。

説明しますと先頭の個所の CTE で投入するデータを定義しています。

    WITH introductions(cow_id, date) AS
         (
           VALUES (1, '2016-01-01'::DATE), (1, '2016-01-03'::DATE),
                  (2, '2016-01-01'::DATE), (2, '2016-01-04'::DATE),
                  (3, '2016-01-01'::DATE), (3, '2016-01-02'::DATE), (3, '2016-01-04'::DATE)
         ),

この CTE に対して SELECT をかけると以下のような結果が返ってくることが確認できます。

 cow_id |    date
--------+------------
      1 | 2016-01-01
      1 | 2016-01-03
      2 | 2016-01-01
      2 | 2016-01-04
      2 | 2016-01-04
      3 | 2016-01-01
      3 | 2016-01-02
      3 | 2016-01-04
(8 rows)

これが入力になっています。これがそれぞれ cow_id = 1 が 1回、cow_id = 2 が 2回、cow_id = 3 が1回の授精としてまとまれば OK です。では実行してみましょう。なむなむ。

 cow_id |  begin_at  |   end_at
--------+------------+------------
      1 | 2016-01-01 | 2016-01-03
      2 | 2016-01-01 | 2016-01-01
      2 | 2016-01-04 | 2016-01-04
      3 | 2016-01-01 | 2016-01-04
(4 rows)

おっ、期待通りになっているようですね。1行が授精1回に相当します。

ふー、やれやれ。

どうなってんの?

いくつかポイントはあるのですが、ここでは今回のアプローチの中心となる再帰 CTE を利用した個所の実装方針のみ説明したいと思います。考え方としては"区間を並べてつなげていく"という方式です。

  1. 注入日〜注入日の区間を作る(再帰 CTE の初期データセット)
  2. 並べた隣の区間を見て、条件を満たすなら再帰的につなげる(再帰 CTE での再帰処理部分)
  3. 再帰 CTE にクエリをかけると1と2のすべてのデータが返ってくるので、不要なものを除去する

1, 2 での再帰処理の実行イメージは次のようになっています。

recursive_process.png

さてさて実はこの処理方法には条件によっては以下の様なパフォーマンス上の問題が発生する可能性があります。よりベターな実装方法があるぜッという方がいらっしゃいましたらインターネットのどこかに放流してくださると僕が喜びますm(__)m

  • 連続した注入日が大量に存在すると再帰が深くなり速度が遅くなる
  • CTE 結果に対して同じ CTE 結果を利用してフィルタリングするので CTE 結果行数が多くなると速度が遅くなる

おわりに

ということで PostgreSQL で利用できる機能のひとつ、再帰 CTE を紹介してきました。他の言語で再帰処理を書くよりは少し扱いが難しいところがあるかとは思うのですが、道具箱に入れておくと役に立つこともあるかもしれません。

ちなみにこれは余談なのですが、Ruby on Rails の Arel でも CTE を利用したクエリを出力することができます。上の例を Arel で起こそうと思っていたのですが途中で力尽きました。Arel 力の不足を感じます・・・。

ときに弊社ではお客様により素早く、より多く価値を提供するための技術のひとつとして、SQL やパフォーマンス・チューニングに精通したエンジニアを求めています!弊社HPWantedlyからのご応募お待ちしています。

このエントリーをはてなブックマークに追加