railsとWITH RECURSIVE対応RDBでツリー構造

概要

検索機能で「こだわり検索」の項目のカテゴリーを一つのテーブルで表現します。

• 経験
  　 * 5年以上
  　 * 3年以上5年未満
  　 * 1年以上3年未満
  　 * 1年未満
  　 * 未経験
• 保有資格
  　 * ほにゃらら検定
  　 　* 1級
  　 　* 2級
  　 　* 3級
  　 * なにそれ検定
  　 　* AAA級
  　 　* AA級
  　 　* A級

（あ、zenn.devのマークダウンのリストがバグってる・・・２階層目までしか認識しない。みづらくてすいませんが、全角スペースで無理やりインデントしてます。）

のようなマスターデータを一つのテーブルで作ろうって作戦です。本来であれば・・・

• experience_categories
• experiences
• skill_categories
• skill_sub_categories
• skills

と5個のテーブルを用意するのが定石ですし、それがいいと思いますが、今回は、汎用性を優先するためにツリー構造を採用しました。

ツリー構造をRDBで実現するのにはいくつか方法が考案されていて、それぞれrails対応のgemがあるようですね。

こちらのサイトで詳しく解説されてる方がいらっしゃいますので詳細はその辺を参照してください。

今回は隣接リストを採用しました。理由は、隣接リストは別名NaiveTree（素朴な木）とも言われてますが、データ構造が単純で、尚且つデメリットはRDBがWITH RECURSIVE構文に対応していればほぼ無いこと。そして、railsの機能で一括で全リストを取得できたので採用しました。WITH RECURSIVEを想定してるのでgemは使いませんでした。

一応「SQLアンチパターン」というお馴染みの書籍ではアンチターン（つまりやってはダメなパターン）として記載されてるので、上記サイトでよくデメリットを理解の上、参考にしてください。

環境

• ruby 3.0.3p157
• Rails 6.1.4.4
• Server version: 10.7.3-MariaDB

コード

テーブル定義

class MasterApi2 < ActiveRecord::Migration[6.1]
  def change
    create_table :profession_detail_categories, id: :integer, unsigned: true,
                                                options: 'ENGINE=InnoDB
      # `parent`というテーブルはありません。これは`parent_id`というカラム名を作るため。`to_table`で実際のテーブル名を指定しています。
      t.references :parent, type: :integer, unsigned: true, null: true,
                            foreign_key: { to_table: :profession_detail_categories, on_delete: :restrict, on_update: :restrict }
      t.string :name, limit: 120, null: false
      # 並び順用のカラム。DESCでorderします。
      t.integer :sequence, unsigned: true, null: false, unique: true
    end

    create_table :profession_details, id: :integer, unsigned: true, options: 'ENGINE=InnoDB DEFAULT CHARSET=utf8mb4' do |t|
      t.references :profession_detail_category, type: :integer, unsigned: true, null: false,
                                                foreign_key: { on_delete: :restrict, on_update: :restrict }
      t.string :name, limit: 120, null: false
      # 並び順用のカラム。DESCでorderします。
      t.integer :sequence, unsigned: true, null: false, unique: true
    end
  end
end

profession_detail_categoriesは先ほどのcategories系全てを、profession_detailsが実際に検索対象と結びつくexperiences、skillsを表したテーブルです。

実際に検索対象と結びつくテーブルもツリー構造に入れるのもありだと思いますが、既に検索対象と関連づいたレコードに子レコードを作るのを阻止するコードが必要になるし、分けた方が後々いいことがありそうな予感がしたので今回は分けました。

client

早めにSQLを組み立てるコードを見せた方がイメージしやすそうなので。

profession_detail_categories = ProfessionDetailCategory.eager_load(
    :profession_details,
    ProfessionDetailCategory.joins_children(joins: { profession_details: :user_profession_details }, once_more: true)
  )
  # rootのリストはparent_idがNULLのものだけ
  .merge(ProfessionDetailCategory.where(parent_id: nil))
  # それぞれsequence descでsort
  # each_nodeでJOINした全てをorder。node.aliasはrailsのルールに従ってテーブルの別名（AS句）を返します。
  .merge(ProfessionDetailCategory.each_node {|q, node| q.order({ node.alias(:sequence) => :desc }) })
  .merge(ProfessionDetail.each_node {|q, node| q.order({ node.alias(:sequence) => :desc }) })

model

先に今回は他のテーブル階層でも使う予定があったので関連機能はNaiveTreeという名前のmoduleに切り出してincludeしました。moduleが割と複雑なので先にmodelのコードを提示します。

# app/models/profession_detail_category.rb

class ProfessionDetailCategory < ApplicationRecord
  # ツリーを構成するのノードになるモデルにinclude
  include NaiveTree

　# parentで親を取得可能にする。`class_name`で実際のmodel名を指定します。class_nameを指定するようなイレギュラーなrelation指定はinverse_ofを指定しないと親子関係が自動で識別できないようです。
  belongs_to :parent, class_name: 'ProfessionDetailCategory', inverse_of: :children, optional: true
  # childrenで子供たちを取得可能にする。
  has_many :children, class_name: 'ProfessionDetailCategory', foreign_key: :parent_id, inverse_of: :parent
  has_many :profession_details
end

# app/models/profession_detail.rb

class ProfessionDetail < ApplicationRecord
  # ツリーのリーフにJOINされるモデルにinclude
  include NaiveTree::Descendants
  # NaiveTree::Descendants内で定義。each_nodeで別名を生成するのに階層の深さや親のテーブル名が必要なので保持します。
  self.ancestor_model = ProfessionDetailCategory

  belongs_to :profession_detail_category
end

module

NaiveTreeとNaiveTree::Descendantsの詳細です。

# app/models/concerns/naive_tree.rb

module NaiveTree
  extend ActiveSupport::Concern

  class Node
    def initialize(table_name, depth)
      @table_name = table_name
      @depth = depth
    end

    def alias(column = nil)
      result = @table_name.to_s
      result = "children_#{result}" if @depth.positive?
      result = "#{result}_#{@depth}" if @depth > 1
      result = "#{result}.#{column}" if column.present?

      result
    end
  end

  module ClassMethods
    # 全てのノードに同じクエリーを実行したい時に使う。
    # Category.each_node do |q, node|
    #   # node.aliasでSQL内でのalias（AS句）を取得可能。カラム名を渡すとalias_name.columnを返す。
    #   # scopeと同じようにselfはActiveRecord::Relation
    #   q.order({node.alias(:sequence) => :desc})
    # end
    def each_node(id = nil)
      query = all
      (0..children_depth(id)).reduce(query) do |q, depth|
        node = Node.new(table_name, depth)
	yield(q, node)
      end
    end

    # DBの階層状態をチェックしてそれに応じたeager_loadに渡す`Hash|Array|Symbol`を組み立てます。
    # options
    #   joins:     childrenにjoinしたいテーブルがある場合渡してください。
    #   id:        特定のIDのレコードの配下のみ取得する場合は渡してください。
    #   once_more: trueにするとchildren_depthより一回多くJOINします。末端で存在確認をする時`children.present?`でSQLが発行されるのを防ぎます。
    #              defaultはfalse。children_depthで繰り返す回数を制御することでSQLの発行を阻止することも可能です。
    def joins_children(options = {})
      return joins_children_with(options) if options[:joins].present?

      joins_children_alone(options)
    end

    # joinされたテーブルのSQL内でのalias（AS句）を返します。
    # depth: joinの階層。
    # column: カラムを.で付与します。
    def node_alias(depth, column = nil)
      node = Node.new(table_name, depth)
      node.alias(column)
    end

    # 指定したレコードの親を数えます。今回使ってないけど取れたので残してみた・・・
    # 一番上の階層だと0
    def parents_depth(id)
      result = ActiveRecord::Base.connection.select_all(<<~"SQL".squish)
        WITH RECURSIVE parent(depth, id, parent_id) as (
          SELECT 0, #{table_name}.id, #{table_name}.parent_id
          FROM #{table_name}
          WHERE #{table_name}.id = #{id}
          UNION ALL
          SELECT
            depth + 1,
            #{table_name}.id,
            #{table_name}.parent_id
          FROM #{table_name}
          INNER JOIN parent ON parent.parent_id = #{table_name}.id
        )
        SELECT MAX(depth) as depth FROM parent;
      SQL

      # レコードがないとnilが返って無限ループに。
      result.first['depth'] || 0
    end

    # 指定したレコードの子供を数えます。idを指定しないと一番深い階層を返します。
    # 1階層の場合は0が返ります。
    def children_depth(id = nil)
      where_clause = "WHERE #{table_name}.id = #{id}" if id.present?
      result = ActiveRecord::Base.connection.select_all(<<~"SQL".squish)
        WITH RECURSIVE children(depth, id, parent_id) as (
          SELECT 0, #{table_name}.id, #{table_name}.parent_id FROM #{table_name}
          #{where_clause}
          UNION ALL
          SELECT
            depth + 1,
            #{table_name}.id,
            #{table_name}.parent_id
          FROM #{table_name}
          INNER JOIN children ON children.id = #{table_name}.parent_id
        )
        SELECT MAX(depth) as depth FROM children;
      SQL

      # レコードがないとnilが返って無限ループに。
      result.first['depth'] || 0
    end

    private

      # { children: :profession_details }
      # { children: [:profession_details, { children: :profession_details }] }
      # { children: [:profession_details, { children: [:profession_details, { children: :profession_details }] }] }
      # { children: [:profession_details, { children: [:profession_details, { children: [:profession_details, { children: :profession_details }] }] }] }
      def joins_children_with(options)
        max_depth = children_depth(options[:id])
        range = options[:once_more] ? (0..max_depth) : (0...max_depth)
        range.reduce(nil) do |result, num|
          next { children: options[:joins] } if num.zero?
          next { children: [options[:joins], { children: options[:joins] }] } if num == 1

          last = NaiveTree::Util.find_last_joins_hash_in_eager_load(result, :children)
          last[:children] = [options[:joins], { children: options[:joins] }]

          result
        end
      end

      # :children
      # { children: :children }
      # { children: { children: :children } }
      # { children: { children: { children: :children } } }
      def joins_children_alone(options)
        max_depth = children_depth(options[:id])
        range = options[:once_more] ? (0..max_depth) : (0...max_depth)
        range.reduce(nil) do |result, num|
          next :children if num.zero?
          next { children: :children } if num == 1

          last = NaiveTree::Util.find_last_hash_in_eager_load(result, :children)
          last[:children] = { children: :children }

          result
        end
      end
  end

  module Descendants
    extend ActiveSupport::Concern

    class Node
      def initialize(ancestor_model, table_name, depth)
        @ancestor_model = ancestor_model
        @table_name = table_name
        @depth = depth
      end

      def alias(column = nil)
        result = @table_name.to_s
        result = "#{result}_#{@ancestor_model.table_name}" if @depth.positive?
        result = "#{result}_#{@depth}" if @depth > 1
        result = "#{result}.#{column}" if column.present?

        result
      end
    end

    module ClassMethods
      def ancestor_model=(model)
        @ancestor_model = model
      end

      def ancestor_model
        @ancestor_model
      end
      
      # self.ancestor_modelを辿ってNaiveTreeをincludeした祖先を見つける
      # 孫テーブルをJOINした時にchildren_depthが必要なので。
      def root_ancestor
        target_model = @ancestor_model
        loop do
          break if target_model.include? NaiveTree

          target_model = target_model.ancestor_model
        end

        target_model
      end

      def each_node(id = nil)
        query = all
        (0..root_ancestor.children_depth(id)).reduce(query) do |q, depth|
          node = Node.new(@ancestor_model, table_name, depth)
	  yield(q, node)
        end
      end

      # joinされたテーブルの別名（AS句）を返します。
      # depth: joinの階層。
      # column: カラムを.で付与します。
      def node_alias(depth, column = nil)
        node = Node.new(@ancestor_model, table_name, depth)
        node.alias(column)
      end
    end
  end

  # joins_childrenでeager_loadをするためのHashを再起的に作るための補助関数
  module Util
    module_function

    def find_last_hash_in_eager_load(hash, key)
      return hash unless hash[key].is_a? Hash

      find_last_hash_in_eager_load(hash[key], key)
    end

    def find_last_joins_hash_in_eager_load(item, key)
      next_item = item[key].find {|e| e.is_a?(Hash) && e.key?(key) }
      return next_item unless next_item[key].is_a? Array

      find_last_joins_hash_in_eager_load(next_item, key)
    end
  end
end

解説

SQLの組み立て

SQLを組み立てる際の課題は二つあります。

• eager_loadに渡すJOIN用のSymbol|Hash|Arrayを組み立てる。
• WHERE句やORDER句を生成する時のalias（AS句）を取得する（組み立てる）。

そして、この二つをするのに一番深い階層が何階層あるのかを調べる必要があり、それを一撃で取得するのにWITH RECURSIVEが必要というわけです。

once_moreオプションについて

JSONを組み立てる時、再起的処理の中で再起を抜けるのにリーフのレコードでchildren.present?で、子供がいなければもう取得しない、というチェックをすると、当然SQLが発行されるわけですね。children_depthで階層がわかるので、再起のカウントをみて再起を抜ければ無駄なSQLの発行は阻止できますが、コードが複雑になるのであまりスマートじゃありませんでした。そこで、一回多くJOINするオプションonce_moreをつけました。必ず一回多くJOINしちゃおうとか、once_moreをデフォルトでtrueにしちゃおうか悩みましたが、後で何で一回多いの？とか思いそうだと思ったのでオプションにしました。

さらにJOIN

NativeTree（profession_detail_categories）の外側のJOIN（このコードでいうところのprofession_details）ですが、試しにprofession_detailsの下にもう一個リレーション貼ってJOINしてみましたが、そのモデルにもNativeTree::Descendantsをincludeしてself.ancestor_model = ProfessionDetailと親を設定してやればeager_loadの組み立ても、each_nodeでaliasの取得もうまくいきました。root_ancestorはそのためですね。複雑な構造は試してません。

ネーミング

大きく分けて

• NaiveTree（隣接リスト）
• Descendants（その下にJOINされるモデル）

の二つのグループがあり、NaiveTreeの中では親子はparent/child。その下にJOINするモデルの中で親子はancestor/descendantにしました。root_ancestorはNativeTeeの一番子供、リーフに相当します。両方とも各要素はnode。SQL内でテーブルに付与されるAS句はaliasと呼んでいます。

似たような階層で別物が二つ出てくるので名前が混乱したのでこの方針で統一しました。

native_tree.rb

全てのmoduleを一つにまとめて見づらいですよね。私も一度分けてみたんですけどapp/models/concerns/の中ってサブフォルダはautoloadしないんですよね。今回初めて気づきました。libなどautoloadパスに追加してあるところに置くのも手ですが、ActiveSupport::Concernでextendしてモデルにincludeするならapp/models/concernsかな〜と。これも少し悩みました。

ベンチ的な話

今回検索用のマスターデータの分類で使うのでそこまで大きなデータはためしてませんが、最大５階層250レコードを突っ込んで一撃でとってみたベンチは下記の通りです。

• WITH RECURSIVE: 3.8ms
• SELECT文: 12.3ms
• JSONを組み立てて返すページの総レスポンス: 96ms

SSDのMacBookPro（M1Max）のローカルなのであくまで参考ですが、経験則で言えば一般的なサーバーでも問題ないと思います。マスターデータなので滅多に更新されないからキャッシュも効きますしね。

参考

https://www.wantedly.com/companies/tutorial/post_articles/299434

https://qiita.com/yuyasat/items/1200d7a6b56bae0c6f57

https://qiita.com/neko_the_shadow/items/d401e0c23892b0d53c2a

https://dev.mysql.com/doc/refman/8.0/ja/with.html

https://mariadb.com/kb/en/recursive-common-table-expressions-overview/

最後に

割とニッチな記事で、正直、どうしてこうしたんだっけ？と思った時の備忘録的な側面も大きいのですが、参考になる人がいないとも限らないので公開しておきます。

実はもう10年以上も前ですが、WITH RECURSIVEなしのMySQL＋PHP（ZendFramework）アンドSQLite＋ObjectiveCでiPadのカタログアプリを作った時、カタログ検索のタグでこの構造を採用しました。今でもそのアプリはその部分は同じ構造で現役で稼働してますが問題を感じたことないです。WITH RECURSIVEがなくてもデータの規模や使用ケースが限定される状況においてはありだと思ってましたが、さらに安心して使えるようになったと思います。

それにしても情報が増えましたね。当時はRDBでツリー構造をつくろうなんて人はあんまりいなかったのかも。WITH RECURSIVEが一般化したからかもしれませんが、日本語でも山ほど記事が出てきて非常に助かりました。まあ、当時は検索が下手だった可能性は捨てきれませんが。

2022/08/11編集

    def each_node(id = nil, &block)
      query = all
      (0..children_depth(id)).reduce(query) do |q, depth|
        node = Node.new(table_name, depth)
        q.instance_exec(node, &block)
      end
    end

を

      def each_node(id = nil)
        query = all
        (0..root_ancestor.children_depth(id)).reduce(query) do |q, depth|
          node = Node.new(@ancestor_model, table_name, depth)
          yield(q, node)
        end
      end

に変更しました。modelのscopeみたいに書けたらかっこいい？かと思って前者にしましたが、あれだと当然ActiveRecord::Relationのスコープで実行されるので、例えばcontrollerでメンバー変数@recordなにかにアクセスできません。なので、下記に変更しました。