ActiveRecord Recursive Tree Scopes

Using ActiveRecord scopes, recursively traverse trees using a single SQL query.

Let's say you've got an ActiveRecord model Employee with attributes id, name, and manager_id. Using stock belongs_to and has_many relations it's easy to query for an Employee's manager and directly managed Employee's.

class Employee < ActiveRecord::Base
  belongs_to :manager,          class_name: 'Employee'
  has_many   :directly_managed, class_name: 'Employee', foreign_key: :manager_id
...

ActiveRecord Recursive Tree Scopes provides two scopes. These scopes, using a single SQL query, match all ancestors or descendants for a record in a tree.

...
  has_ancestors   :managers, key: :manager_id
  has_descendants :managed,  key: :manager_id
end

A Single Query

Yep, a single query. Thanks to PostgreSQL's WITH RECURSIVE it's possible to recursively match records in a single query.

Using the model above as an example, let's say you've got an Employee with an id of 42. Here's the SQL that would be generated for employee.managed

SELECT "employees".* 
FROM "employees" 
WHERE (
  employees.id IN (
    WITH RECURSIVE descendants_search(id, path) AS (
      SELECT id, ARRAY[id]
      FROM employees
      WHERE id = 42
      UNION ALL
        SELECT employees.id, path || employees.id
        FROM descendants_search
        JOIN employees
        ON employees.manager_id = descendants_search.id
        WHERE NOT employees.id = ANY(path)
    )
    SELECT id
    FROM descendants_search
    WHERE id != 42
    ORDER BY path
  )
)
ORDER BY employees.id

Advanced Usage

Multiple key trees are supported. For example, a Person model may have mother_id and father_id keys. That's no problem, just tell the scope about both keys. person.progenitors will return all ancestors, mothers and fathers.

class Person < ActiveRecord::Base
  belongs_to :mother, class_name: 'Person'
  belongs_to :father, class_name: 'Person'

  has_ancestors   :progenitors, key: [ :mother_id, :father_id ]
  has_descendants :progeny,     key: [ :mother_id, :father_id ]
end

Friendly

Go ahead, chain away:

employee.managers.where(name: 'Bob').exists?

SELECT "employees".* 
FROM "employees" 
WHERE 
  "employees"."name" = 'Bob' AND 
  (
    employees.id IN (
      WITH RECURSIVE descendants_search(id, path) AS (
        SELECT id, ARRAY[id]
        FROM employees
        WHERE id = 42
        UNION ALL
          SELECT employees.id, path || employees.id
          FROM descendants_search
          JOIN employees
          ON employees.manager_id = descendants_search.id
          WHERE NOT employees.id = ANY(path)
      )
      SELECT id
      FROM descendants_search
      WHERE id != 42
      ORDER BY path
    )
  )
ORDER BY employees.id

Requirements

• ActiveRecord >= 3.1.0
• PostgreSQL >= 8.4

Installation

Add gem 'activerecord-recursive_tree_scopes' to your Gemfile.

Alternatives

The Edge gem is similar but makes better use of Arel and relations.

Thanks

Thanks to Joshua Davey, his blog post inspired this gem.

Copyright

Copyright (c) 2013 John Wulff. See LICENSE.txt for further details.