再帰クエリを書いてみた - patorashのブログ

まんまなのですが、再帰クエリを書いてみたら一発で処理がキマったのでよかったという話です。

Railsで親子関係を表現するデータで再帰処理をやっていたのですが、当然ですが再帰するたびにクエリが発行されていてなんだか微妙でした。そうこうするあたりで、「再帰クエリ」という文字を見かけたので、「お、これはやってみるチャンスやな」と思ってやってみた次第。

モデルの定義

テーブル作成

Userモデルの親子関係を表現するテーブルとして、familiesテーブルを作ったとします。外部キー制約とユニーク制約を入れておきました（子供が2つの親を持てないようにするため）

class CreateFamilies < ActiveRecord::Migration[5.2]
  def change
    create_table :families do |t|
      t.integer :parent_id, null: false
      t.integer :child_id, null: false

      t.timestamps
    end
    add_foreign_key :families, :users, column: :parent_id
    add_foreign_key :families, :users, column: :child_id
    add_index :families, :child_id, unique: true
  end
end

Familyモデルの定義

検証を定義しておきます。子供が自分の親を子供として登録できないような検証check_circular_referenceを定義しておきました。ここで使っているmy_familiesメソッドで、再帰クエリを使っています。

class Family < ApplicationRecord
  belongs_to :parent, class_name: 'User'
  belongs_to :child, class_name: 'User'

  validates :parent,
            presence: true,
            uniqueness: { scope: :child_id, message: '既に子供として登録済みです' }
  validates :child,
            presence: true,
            uniqueness: { message: '既にどこかの子供として登録済みです' }
  validate :check_circular_reference

  private

    def check_circular_reference
      if parent.my_families.exists?(id: child)
        errors.add(:child, '親や子供の子供を登録することはできません')
      end
    end
end

Userモデルの修正

透過的に親子関係が扱えるように関連を記述し、あとは親子関係とかをチェックするためのメソッドを追加等。再帰クエリはmy_familiesメソッドで使っています。

class User < ApplicationRecord

  # 親子関係を参照するための関連を記述
  has_many :families,
           foreign_key: :parent_id,
           dependent: :destroy

  has_many :children,
           class_name: 'User',
           through: :families,
           foreign_key: :child_id

  has_one  :family,
           foreign_key: :child_id,
           dependent: :destroy

  has_one :parent,
          class_name: 'User',
          through: :family,
          foreign_key: :parent_id


  # 親かどうか確認する
  # @return [Boolean] 子を持っているかルート親であればtrueを、それ以外はfalseを返す
  def parent?
    self.children.exists? || self.root_parent?
  end

  # 子かどうか確認する
  # @return [Boolean] 子ならばtrueを、親ならばfalseを返す
  def child?
    self.parent.present?
  end

  # ルート親かどうか確認する
  # @return [Boolean] ルート親ならばtrueを、そうでなければfalseを返す
  def root_parent?
    !self.child?
  end

  # ルート親を取得する
  # @return [User] ルート親を返す
  def root_parent
    return self if root_parent?
    self.parent.root_parent
  end

  # 親子を全て返す
  # 再帰問い合わせを使って子を取得する
  # @return [User::ActiveRecord_Relation] メソッドを実行したUserの家族を全て返す
  def my_families
    User.from(<<~SQL)
      (
        WITH RECURSIVE my_families AS (
          SELECT
            families.parent_id
            , families.child_id
          FROM families
          WHERE #{User.sanitize_sql_for_conditions(['parent_id = ?', self.root_parent.id])}
          UNION ALL
          SELECT
            families.parent_id
            , families.child_id
          FROM families, my_families
          WHERE families.parent_id = my_families.child_id
        )
        SELECT *
        FROM #{User.quoted_table_name}
        WHERE id IN (
          SELECT parent_id AS user_id
          FROM my_families
          UNION
          SELECT child_id AS user_id
          FROM my_families
        )
      ) users
    SQL
  end
end

再帰クエリ

再帰クエリに関しては、Let's Postgresにちょうどいい説明があって助かりました🙏

lets.postgresql.jp

木構造のデータを取っていくのにちょうどいいです。ただし、複雑な木構造だったりするとパフォーマンスが悪かったり、循環してしまっているような構造だと無限ループになる可能性があるため、取り扱いには注意が必要です。今回は循環しないように検証を追加しているため、単純な木構造のデータですし、そこまで親子関係も深くならない想定での実装です。

WITH句

PostgreSQLにはWITH句があります。これは、サブクエリに名前を付けることができる機能です。複雑なSQLの場合、JOINしたりUNIONしたりする際に同じサブクエリを書くケースがありますが、そういうのはWITH句を使って事前に一時テーブルを作っておけば、シンプルに書くことができます。

Before

なんかいい例が思いつかなかったのですが、例えばcurrent_loginsという今期のログイン実績のテーブルと、previous_loginsという前期のログイン実績のテーブルがあったとして、それの権限がadminのもののみを合わせて抽出したいとします。すると、以下のような感じで、INNER JOINの条件が同じになります。

SELECT current_logins.*
FROM current_logins
INNER JOIN (
  SELECT id, name
  FROM users
  WHERE role_id = 1
) admin_users ON current_logins.user_id = admin_users.id
UNION ALL
SELECT previous_logins.*
FROM previous_logins
INNER JOIN (
  SELECT id, name
  FROM users
  WHERE role_id = 1
) admin_users ON previous_logins.user_id = admin_users.id

After

これをWITH句を使うと、以下のように書くことができます。同じ条件のサブクエリの再利用が捗りますね。

WITH admin_users AS (
  SELECT id, name
  FROM users
  WHERE role_id = 1
)
SELECT current_logins.*
FROM current_logins
INNER JOIN admin_users ON current_logins.user_id = admin_users.id
UNION ALL
SELECT previous_logins.*
FROM previous_logins
INNER JOIN admin_users ON previous_logins.user_id = admin_users.id

WITH RECURSIVE句

WITH RECURSIVE句は初回の取得データを元に再帰的にUNION( ALL)を繰り返す等をしてデータを取得できます。あとはWITH句と同じく、その後に続くクエリで利用することが可能です。わかりやすくするために、さっきのUserモデルで書いていたものを修正したものが以下になります。初回のparent_idを1に指定しています。

WITH RECURSIVE my_families AS (
  SELECT
    families.parent_id
    , families.child_id
  FROM families
  WHERE parent_id = 1
  UNION ALL
  SELECT
    families.parent_id
    , families.child_id
  FROM families, my_families
  WHERE families.parent_id = my_families.child_id
)
SELECT *
FROM users
WHERE id IN (
  SELECT parent_id AS user_id
  FROM my_families
  UNION
  SELECT child_id AS user_id
  FROM my_families
)

UNION ALL以下では、FROMにWITH RECURSIVEで指定したmy_familiesテーブルを追加し、WHERE条件で利用しています。ここでは、User id 1の子供が親になっているデータを抽出、その子がまた親になっているデータを抽出…というように繰り返し処理が行われます。

そして、再帰クエリで取得できたmy_familiesを利用して家族として該当するidのみをusersテーブルから抽出しています。一発で階層構造のデータを取得できるのはいいですね！👍

やってみた感想

最初は同じことをする処理をRubyで実装していたのですが、だんだん頭がこんがらがってきてしまっていました。シンプルな再帰処理ならサクッと書けるのですが、複雑なやつは苦手です😭何度もクエリが発行されてパフォーマンスも悪くなりがちですし。しかしSQLならば1度の発行で済むため、パフォーマンスもよさそうです。とはいえ、プログラムが複雑になるか、SQLが複雑になるか、というトレードオフにはなるんですが、これくらいだったら再帰クエリを使ってもいいかなと思えました。

また、こういう親子関係を管理するgemにancestryというやつがあるのですが、再帰クエリをマスターしたら、これを使わずに済むのではないか？と思えました。ancestryは1つのカラムに/で子idを区切って登録したりしているので、なんとなく辞めたいなという気持ちがあります。再帰クエリを使ったancestry的なgemを作ってみたいと考えています（いつになるやら）