FacebookLinkedInShare

Intro

A while when we were designing our business logic service which is holding rules, that represented by trees and describing our web sites behaviour. We encountered with a need of eager loading those trees.

In this post we will cover the popular solutions for creating trees in ruby and introduce our Gem that was designed specially for eager loading trees in Rails:

Acts as tree

It’s one of the oldest Gems in ruby for trees creation.
The Gem extents Active records models by mixing tree navigation methods such as:

ancestors          Returns list of ancestors, starting from parent until root.
root               Returns the root node of the tree.
siblings           Returns all siblings of the current node.
self_and_siblings  Returns all siblings and a reference to the current node.

Usage

class Comment < ActiveRecord::Base
  acts_as_tree
end

The gem mostly used for creation of navigation menus as it is demonstrated in the following RailsCast.

Ancestry

Ancestry is more advanced Gem, it's provides a longer list of navigation methods, attributes and scopes than acts as a tree (In fact they can be both integrated in the same model as from 1.2.0 version of acts as tree)

parent          Returns the parent of the record, nil for a root node
parent_id       Returns the id of the parent of the record, nil for a root node
root            Returns the root of the tree the record is in, self for a root node
root_id         Returns the id of the root of the tree the record is in
root?, is_root? Returns true if the record is a root node, false otherwise
ancestor_ids    Returns a list of ancestor ids, starting with the root id and ending with the parent id
ancestors       Scopes the model on ancestors of the record
path_ids        Returns a list the path ids, starting with the root id and ending with the node's own id
path            Scopes model on path records of the record
children        Scopes the model on children of the record
child_ids       Returns a list of child ids
has_children?   Returns true if the record has any children, false otherwise
is_childless?   Returns true is the record has no children, false otherwise
siblings        Scopes the model on siblings of the record, the record itself is included*
sibling_ids     Returns a list of sibling ids
has_siblings?   Returns true if the record's parent has more than one child
is_only_child?  Returns true if the record is the only child of its parent
descendants     Scopes the model on direct and indirect children of the record
descendant_ids  Returns a list of a descendant ids
subtree         Scopes the model on descendants and itself
subtree_ids     Returns a list of all ids in the record's subtree
depth           Return the depth of the node, root nodes are at depth 0

It also provides cascade create and deletion of objects.

Usage

The usage is similiar and has_ancestry should be mixed in the Active recored.
This Gem was also demonstrated in RailsCast.

Closure tree

This Gem was the closest solution for our problem, it provides a methods for eager load of the tree, but unfortunately it allows only one model in the tree as the gems before, when our tree as build from multiple active record models.
This gem also can be along side of the acts as tree gem, and usage are very similar, the following code must be mixed in the active record has_closure_tree.

Index tree

When non of the above were suited for our problem we decided to create our own gem that only eager loads the tree.
The eager load works by indexing the nodes of the tree. The number of queries needed for loading a tree is N,
Where N is the number of different models(ActiveRecords) in the tree.

Each inner object in the tree have an index node instance that is connecting it to the root.
When the root of the tree is loaded, only the objects that are in the tree are fetched(Pruning).
The index nodes are created when the root element is saved and stored in the IndexNode model.

Example

class Equation < ActiveRecord::Base
  acts_as_indexed_node :root => true do
    has_many :expressions
  end
      
  has_one :not_tree_association_a
        
  def traverse
    expression.traverse
  end        
end
    
class Expression < ActiveRecord::Base
  belongs_to :equation, inverse_of: :expressions      
  acts_as_indexed_node do
    has_many :expressions
  end
        
  has_one :not_tree_association_b
        
  def traverse
    expressions.map(&:traverse)
  end
end

Database initialisation

        
            +-----------+                               +-----------+
            |Equation  1|                               |Equation  2|
            +-----+-----+                               +-----+-----+
                  |                                           |
                  v                                           v
            +-----------+                               +-----------+
            |Expression1|                               |Expression6|
            +-+-------+-+                               +-+-------+-+
              ^       ^                                   ^       ^
              |       |                                   |       |
      +-------+       +-------+                   +-------+       +-------+
      |                       |                   |                       |
      |                       |                   |                       |
+-----+-----+           +-----+-----+       +-----+-----+           +-----+-----+
|Expression3|           |Expression2|       |Expression8|           |Expression7|
+-----------+           +-----------+       +-----------+           +-----------+
                          ^       ^                                   ^       ^
                          |       |                                   |       |
                  +-------+       +-------+                   +-------+       +-------+
                  |                       |                   |                       |
                  |                       |                   |                       |
            +-----+-----+           +-----+-----+       +-----+-----+          +------+-----+
            |Expression4|           |Expression5|       |Expression9|          |Expression10|
            +-----------+           +-----------+       +-----------+          +------------+                       

Traversal example without tree pre-loading:

Equation.find(1).traverse

Those are the queries that is executed:

Equation Load (0.2ms)  SELECT  "equations".* FROM "equations"   ORDER BY "equations"."id" ASC LIMIT 1
Expression Load (0.2ms)  SELECT  "expressions".* FROM "expressions"  WHERE "expressions"."id" = ? LIMIT 1  [["id", 1]]
Expression Load (0.1ms)  SELECT "expressions".* FROM "expressions"  WHERE "expressions"."expression_id" = ?  [["expression_id", 1]]
Expression Load (0.1ms)  SELECT "expressions".* FROM "expressions"  WHERE "expressions"."expression_id" = ?  [["expression_id", 2]]
Expression Load (0.1ms)  SELECT "expressions".* FROM "expressions"  WHERE "expressions"."expression_id" = ?  [["expression_id", 4]]
Expression Load (0.1ms)  SELECT "expressions".* FROM "expressions"  WHERE "expressions"."expression_id" = ?  [["expression_id", 5]]
Expression Load (0.1ms)  SELECT "expressions".* FROM "expressions"  WHERE "expressions"."expression_id" = ?  [["expression_id", 3]]

It can be improved with eager loading such as 'includes', but eager loading will be fixed to the tree height.

Traversal example with tree pre-loading:

Equation.find(1).preload_tree.traverse

The statement fetches only the objects in the Equation1 tree in two

Equation Load (0.1ms)  SELECT  "equations".* FROM "equations"   ORDER BY "equations"."id" ASC LIMIT 1
Expression Load (0.2ms)  SELECT "expressions".* FROM "expressions" 
INNER JOIN "index_tree_index_nodes" ON "index_tree_index_nodes"."node_element_id" = "expressions"."id" 
AND "index_tree_index_nodes"."node_element_type" = 'Expression' 
WHERE "index_tree_index_nodes"."root_element_type" = 'Equation' AND "index_tree_index_nodes"."root_element_id" IN (1)

One query to fetch Equations, and the second query is to fetch Expressions(Doesn't matter how deep is the tree it is still one query)

Usage

RootModel.find(1).preload_tree
RootModel.all.preload_tree
RootModel.where(color: 'red').all.preload_tree