アソビュー！ Advent Calendar 2022の10日目です。

8月に入社しアソビューでバックエンドエンジニアをしている長友です。

みなさま再帰クエリ使っていらっしゃるでしょうか！
最近アソビューではmysqlの8系へのバージョンアップを行った為、再帰クエリの利用が可能となりました。
そこで本日は、アソビュー競馬部にも所属しておりサラブレッドの血統好きな私が再帰クエリを使ってツリー構造の血統表を作成してみるというお話です。

血統表とは ~ 本稿の目的
再帰クエリについて
- mysqlにおける再帰クエリの構文
- 再帰クエリとナイーブツリー構造
血統表作成における再帰クエリ
- 血統表のデータ構造
- 血統表を作成するクエリ
おわりに

血統表とは ~ 本稿の目的

みなさまそもそも「血統表」がどのようなものかご存知でしょうか？
例えばペットショップからやってきた犬や猫であれば「血統書」というものが発行されており、その出自と数世代前の祖先までが記されています。

それに対して「血統表」は、父系母系それぞれの祖先にどの個体が存在しその配置さえも重要*1であるサラブレッドなどにおいて、祖先とその配置を一覧で確認するために用いられる表です。*2

特にサラブレッドは少なくとも8世代以上の祖先が全て明らかとなっている純血種であると同時に、近親交配を繰り返すことで競争能力の向上を図ってきた種でもあり、血統表を見ることでどのような近親交配が行われてきたか・どの祖先が繰り返し登場するかを見ることもできます。

こんなロマン心くすぐる血統表を自分で好きな世代まで遡って、更にどんな祖先が繰り返し登場するかまで見られたらそれはさぞ楽しいですね！！

そこで最終的には以下のようにサラブレッドの血統表をビジュアライズできることを目標とし、本稿では肝となる「再帰クエリを用いてナイーブツリーからツリー構造の血統表データを取得すること」に絞って解説していきたいと思います。

再帰クエリについて

再帰クエリは共通テーブル式(cte)の拡張機能として提供されています。詳細は公式ドキュメントやさまざまな記事で紹介されているため、今回はデモで利用するmysql(version 8.0)における構文の確認に留めます。

mysqlにおける再帰クエリの構文

公式ドキュメントの通り、mysqlにおける再帰クエリの構文は以下です。

-- 再帰クエリ定義
WITH RECURSIVE cte (n) AS
(
    SELECT ...      -- 最初の取得内容
    WHERE  ...      -- 最初の取得内容の抽出条件
    UNION ALL
    SELECT ...      -- 追加で取得する内容
    FROM   ...      -- cteと結合するテーブル
    JOIN   ...      -- cteとの結合
    ON     ...      -- cteとの結合条件
)
-- n はcteからSELECTした値。SELECT抽出条件等に利用することができる

-- 呼び出しを行うメインクエリ
SELECT * FROM cte;

また再帰クエリの最大再帰回数はデフォルトで1000に設定されているため、以下のようにcte_max_recursion_depthで変更可能です。

SET SESSION cte_max_recursion_depth = 1000000;

再帰クエリとナイーブツリー構造

再帰クエリはナイーブツリーとなっているデータを取得する際に利用されることも多いです。以下のような自身のIDと親のIDを持つものがその典型です。

このようなデータ構造に対し、指定の子孫から祖先を辿る場合は以下のようなクエリを組みます。

WITH RECURSIVE FAMILY_TREE (id, parent_id, name, name_tree) AS (
    SELECT
        SAMPLE.ID,
        SAMPLE.PARENT_ID,
        SAMPLE.NAME,
        SAMPLE.NAME
    FROM
        SAMPLE
    WHERE
        SAMPLE.ID = 3
    UNION ALL
    SELECT
        SAMPLE.ID,
        SAMPLE.PARENT_ID,
        SAMPLE.NAME,
        CONCAT(CAST(name_tree AS CHAR), ' > ', SAMPLE.NAME)
    FROM
        FAMILY_TREE
    JOIN
        SAMPLE
    ON
        SAMPLE.ID = FAMILY_TREE.PARENT_ID
)

SELECT * FROM FAMILY_TREE;

name_treeに各世代の名前が順番に羅列されているのが分かると思います。

血統表作成における再帰クエリ

血統表のデータ構造

それでは今回のテーマである血統表のデータ構造を見ていきましょう。利用するデータは簡易的な戸籍テーブルを想定し以下のような形となります。

ここから太郎君の血統表を取得する際のポイントは3つあります。

父と母の両方を再帰的に辿る必要があること
何世代遡るかを任意で指定する必要があること
太郎君から見た祖先の世代とその並び順が保たれていること

取得後の完成イメージは以下になります。
各代に並ぶ祖先の数は2の(代数)乗となります。
太郎君を0代目と見た場合、3代前は2の3乗なので8人の祖先がいる計算になります。

血統表を作成するクエリ

この血統表は次のクエリで取得することが出来ます。

WITH RECURSIVE PEDIGREE(
  generation, -- ポイント1
  position, -- ポイント2
  side, -- ポイント3
  id, 
  name, 
  sex, 
  father_id, 
  mother_id
) AS (
    SELECT
        0
        ,1
        ,'FATHER_SIDE'
        ,FAMILY_REGISTER.ID
        ,FAMILY_REGISTER.NAME
        ,FAMILY_REGISTER.SEX
        ,FAMILY_REGISTER.FATHER_ID
        ,FAMILY_REGISTER.MOTHER_ID
    FROM FAMILY_REGISTER
    WHERE FAMILY_REGISTER.ID = #{targetId} -- ポイント4
    UNION ALL
    SELECT
        PEDIGREE.GENERATION + 1
        ,CASE FAMILY_REGISTER.SEX
            WHEN 'MALE' THEN PEDIGREE.POSITION * 2 - 1
            ELSE PEDIGREE.POSITION * 2
        END
        ,CASE
            WHEN (
                (
                    CASE FAMILY_REGISTER.SEX
                        WHEN 'MALE' THEN PEDIGREE.POSITION * 2 - 1
                        ELSE PEDIGREE.POSITION * 2
                    END
                ) > pow(2, GENERATION + 1) / 2
            ) THEN 'MOTHER_SIDE'
            ELSE 'FATHER_SIDE'
        END
        ,FAMILY_REGISTER.ID
        ,FAMILY_REGISTER.NAME
        ,FAMILY_REGISTER.SEX
        ,FAMILY_REGISTER.FATHER_ID
        ,FAMILY_REGISTER.MOTHER_ID
    FROM
        PEDIGREE
    JOIN
        FAMILY_REGISTER
    ON
        FAMILY_REGISTER.ID IN (PEDIGREE.FATHER_ID, PEDIGREE.MOTHER_ID) -- ポイント5
        AND #{maxGeneration} >= PEDIGREE.GENERATION + 1 -- ポイント6
)
SELECT
    *
FROM
    PEDIGREE
ORDER BY
    GENERATION ASC
    ,POSITION ASC; -- ポイント7

取得結果は以下となります。

それではクエリに記載したポイントを以下で説明していきます。

ポイント1. 世代を表すgenerationを0で初期化し、各再帰の中でインクリメントする

UNION ALL
SELECT
    PEDIGREE.GENERATION + 1

ポイント2. 世代内での配置を表すpositionを初期値1で定義し、再帰で取得するレコードの性別によって値を振り分ける

CASE FAMILY_REGISTER.SEX
  WHEN 'MALE' THEN PEDIGREE.POSITION * 2 - 1 -- 男の場合は子供のpositionの2倍から1引いたものが自身のposition
  ELSE PEDIGREE.POSITION * 2 -- 女の場合は子供のpositionの2倍
END

ポイント3. 血統表の取得起点(今回は太郎君)から見た場合、父方・母方どちらに属するかをsideで表す

注意点として、再帰クエリでは初期値に入れた値の型で固定されます。よって初期値で空文字ではない十分な文字列を入れなければなりません。
各再帰における父方母方の判定は、前段のポイントである世代内配置(position)がその世代に存在し得る祖先数の半分より上回っている場合は母方、そうでない場合は父方として判定しています。

CASE
    WHEN (
        (
            CASE FAMILY_REGISTER.SEX
                WHEN 'MALE' THEN PEDIGREE.POSITION * 2 - 1
                ELSE PEDIGREE.POSITION * 2
            END -- ここはpositionと同じ計算
        ) > pow(2, GENERATION + 1) / 2
    ) THEN 'MOTHER_SIDE'
    ELSE 'FATHER_SIDE'
END

ポイント4. 血統表の起点となるレコードのIDを指定

ここでは太郎君のID(=15)を指定します。

FROM FAMILY_REGISTER
WHERE FAMILY_REGISTER.ID = #{targetId} -- ポイント4

ポイント5. JOIN ON の条件にIN句を利用する

通常のJOINではあまり使用することがないと思いますが、今回は両親を再帰的に遡る必要があるためIN句を用いて結合を行います。
再帰の仕様として、IN句で見つかったそれぞれの両親に対して更に個別に再帰探索が走っていきます。

JOIN
    FAMILY_REGISTER
ON
    FAMILY_REGISTER.ID IN (PEDIGREE.FATHER_ID, PEDIGREE.MOTHER_ID) -- ポイント5

ポイント6. JOIN句の条件に複合して遡る世代を指定する

遡りたい世代をここで指定することで今回のテーマである「好きな世代まで遡る血統表」の作成が可能となります。
ここで世代を指定しない場合、遡れるだけ遡るか再帰上限に達してエラーになるため指定する方がベターです。

AND #{maxGeneration} >= PEDIGREE.GENERATION + 1 -- ポイント6

ポイント7. 取得元のクエリでGENEATIONとPOSITIONで昇順に並び替える

実際に血統表を表示する際の並び順を整えるため、ここで世代と世代内配置でソートします

SELECT
    *
FROM
    PEDIGREE
ORDER BY
    GENERATION ASC
    ,POSITION ASC;

おわりに

今回は弊社のアドベントカレンダーの中でも少し毛色が変わり、「血統表」というニッチなテーマを普段業務で利用しているmysqlと再帰クエリを応用した事例として紹介させていただきました。
今回はあくまでクエリの解説として人間の戸籍データを利用しましたが、競走馬で同じデータ構造を用いればその血統表を再現することが勿論可能となります。
競走馬の血統表をビジュアライズする際のポイントについてはまたいつかご紹介できたらと思います！

昨今ウマ娘の影響もあって競馬人気が非常に高まっており、競馬に関心持つ方、実際に競馬場に足を運ぶ方も多くなっているのではないでしょうか。
アソビューでは引退後の著名な競走馬が暮らしているノーザンホースパークさんや、乗馬体験施設なども数多く掲載しております。
是非この様な施設に足を運び馬と触れ合って頂き、時にはその馬のルーツとなる血統表に思いを馳せて頂きたいです！ www.asoview.com

www.asoview.com

アソビューでは一緒に働くメンバーを大募集しています！カジュアル面談もありますので、少しでも興味があればお気軽にご応募いただければと思います！