# Eager loading trees in Rails

## 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
```