ruby-on-rails - 自己参照レコードの列挙中の N+1

Question

私は非常に基本的なことをしています - カテゴリのツリーをトポロジー順に表示し、ActiveRecord は各カテゴリの子を列挙するための追加のクエリを発行します。

class Category < ActiveRecord::Base
  attr_accessible :name, :parent_id

  belongs_to :parent, :class_name => 'Category'
  has_many :children, :class_name => 'Category', :foreign_key => 'parent_id'

  def self.in_order
    all = Category.includes(:parent, :children).all  # Three queries as it should be
    root = all.find{|c| c.parent_id == nil}
    queue = [root]
    result = []
    while queue.any?
      current = queue.shift
      result << current
      current.children.each do |child|  # SELECT * FROM categories WHERE parent_id = ?
        queue << child
      end
    end
    result
  end
end

アップデート。ここで何が起こっているかを理解している限り、カテゴリが何らかのカテゴリの子として参照される場合、それは最初のリストのオブジェクトと同じオブジェクトではないため、読み込まれた子ではありません。追加の隣接リストを作成せずに目的の動作を実装する方法はありますか?

UPD2: 手動隣接リスト ソリューションは次のとおりです。使用するクエリは 1 つだけですが、もっと慣用的なものを使用したいと思います

  def self.in_order_manual
    cache = {}
    adj = {}
    root = nil
    all.each do |c| 
      cache[c.id] = c
      if c.parent_id != nil
        (adj[c.parent_id] ||= []) << c.id
      else
        root = c.id
      end
    end

    queue = [root]
    result = []
    while queue.any?
      current = queue.shift
      result << current
      (adj[current] || []).each{|child| queue << child}
    end
    result.map{|id| cache[id]}
  end