# PostgreSQL and Rails, sitting in a tree

> ActiveRecord allows different approaches for storing hierarchical structures in a database. In this article, I will try to determine what pattern is best to use when it comes to huge data.

- Date: 2016-03-09T00:00:00.000Z
- Authors: Viktor Sokolov
- Categories: Rails, Performance
- URL: https://evilmartians.com/chronicles/postgresql-and-rails-sitting-in-a-tree

---

The [Closure Table](https://github.com/mceachen/closure_tree) pattern has something that other tree storage methods don’t—a good design. Let's see why it rocks.

Some time ago I was involved in a project aiming to systemize a pandemonium of databases. Especially hard were the toponym ones. The source data was a deep XML tree with regions and cities at the top and streets and houses at the bottom.

```
| id         | parent_id  | name       |
| ---------- |------------|------------|
| 1          | 2          | Kremlin    |
| 2          |            | Moscow     |
| 3          | 2          | Red Square |
| …   (1M+ unsorted records)         … |
```

I had to put this tree into PostgreSQL to allow queries. A typical query was, for example, to fetch all the streets of the cities within a specific region or to fetch the whole path from a particular street at the bottom up to the root node, etc.

Since there were quite a few queries to make, it was a must to process them as fast as possible. Therefore, I needed a hierarchical storage pattern to speed them up.

[The most complete list](http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database) of hierarchical storage patterns

## So I did the following:

* Imported the table;
* Chose the suitable hierarchical pattern;
* Calculated the extra reference data used by the chosen pattern.

At each of the three stages, it was the speed that mattered. I wanted to do everything in next to no time, because there are not many things worse than having your server not responding, and downtimes are unacceptable.

## Importing the initial data

In PostgreSQL, a table is best populated by the [`COPY FROM`](http://www.postgresql.org/docs/9.5/static/sql-copy.html) statement. It works significantly faster than multiple `INSERT` statements. Ensure to prepare the input data for `COPY FROM`. It accepts CSV or a binary file/string at the input. Binary is faster.

Check the [PostgreSQL documentation](http://www.postgresql.org/docs/9.5/static/populate.html) for the details

The [pg_data_encoder](https://github.com/pbrumm/pg_data_encoder) gem can be used to convert data to a binary format to be used by PostgreSQL. It is designed to work with [postgres-copy](https://github.com/diogob/postgres-copy), but I prefer [Sequel](http://sequel.jeremyevans.net/) because it is very lightweight compared to ActiveRecord and allows to work with with tables directly, without using the application model layer.

MySQL has a similar feature called [`LOAD DATA INFILE`](http://dev.mysql.com/doc/refman/5.7/en/load-data.html)

The import script might look like this:

```ruby
### import.rb

# Will connect to the database configured in Rails' database.yml
db = Sequel.connect(ActiveRecord::Base.connection_config)

encoder = PgDataEncoder::EncodeForCopy.new

# Suppose the data have already been read.
# In my case, I had a set of DBF's (doh! at 2015!).
[
  [1, 2, "Kremlin"],
  [2, nil, "Moscow"],
  [3, 2, "Red Square"]
  # …
].each { |line| encoder.add(line) }

db.copy_into(
  "tax_authorities",
  columns: %i[id parent_id name],
  format: :binary,
  data: encoder.get_io
)

# Run it with something like:
# > bundle exec rails runner import.rb
```

If your data set does not fit in memory, you have two options:

* Import incrementally, part by part (read-copy loop).
* Specify `use_tempfile: true` as an option for `PgDataEncoder#new` to enable file buffering.

Incremental import might be faster.

## Choosing a tree pattern

There are only a few ready to use ActiveRecord hierarchy plugins:

[An excellent presentation](http://www.slideshare.net/billkarwin/models-for-hierarchical-data) explaining all the patterns

* [awesome_nested_set](https://github.com/collectiveidea/awesome_nested_set) implements Nested Set;
* [ancestry](https://github.com/stefankroes/ancestry) implements Materialized Path;
* and [closure_tree](https://github.com/mceachen/closure_tree) is for Closure Table.

Let's try to choose one.

### Nested Set is the worst option:

* The [slowest](http://habrahabr.ru/post/47280) one.
* The most [complicated algorithm](https://en.wikipedia.org/wiki/Nested_set_model) with [complex queries](http://www.codeproject.com/Articles/4155/Improve-hierarchy-performance-using-nested-sets).
* Has [issues with concurrency](https://github.com/collectiveidea/awesome_nested_set/issues/86)—updates always [require locks](http://robsite.net/nested-sets-suck-on-how-not-to-map-trees-into-a-relational-database/).

Even though I am going to read the tree way more often than update it, still such problems scare me. Anything but this.

### Materialized Path is much better:

* The [fastest](http://www.hilman.io/blog/2015/09/comparing-ancestry-and-closure_tree) one.
* Can be used [natively](http://www.postgresql.org/docs/9.1/static/ltree.html) with PostgreSQL.
* However, the internals [are still complicated](https://github.com/stefankroes/ancestry/blob/master/lib/ancestry/instance_methods.rb#L9).

#### Reference columns are required

Two additional columns have to be added and calculated to make everything work: `ancestry` and `ancestry_depth`. The gem contains `#build_ancestry_from_parent_ids!` method which calculates initial values.

It took about 44 minutes to calculate 1 188 483 records and save the values in the two columns. The production server won’t be so write-friendly as the local machine, the source database needs to be updated and will grow in size. And the more it grows, the slower it works. Much better but still unacceptable.

### Closure Table is something in-between:

* Slower than Materialized Path but competitive.
* The [easiest algorithm](https://coderwall.com/p/lixing/closure-tables-for-browsing-trees-in-sql) which best fits in with the relational model.
* Can use foreign keys to maintain referential integrity.
* No need to modify existing table schema.

In this case, an extra [table](https://github.com/mceachen/closure_tree#installation) is to be created. This table will contain the links between each parent and all its descendants. Сall the `#rebuild!` method to fill this table with the initial values.

#### Default `#rebuild!` method works slow

By default, it enumerates each record in the source table and creates corresponding records in the hierarchies table by calling the `INSERT INTO … SELECT` statement. Therefore, it does an N number of inserts per each source row. It is never fast with millions of inserts. It takes hours to rebuild the hierarchy from scratch. Unacceptable.

## Boosting up the closure_tree `#rebuild!`

The reference table can be populated much quicker if calculated in memory and stored by the `COPY FROM` statement.

Take a look at [this slide](http://www.slideshare.net/billkarwin/models-for-hierarchical-data/46?src=clipshare) for more details about the reference table structure.

The data for your reference table might look like this:

```
  | ancestor_id | descendant_id | generations |
  |-------------------------------------------|
  | 1           | 1             | 0           |
  | 2           | 2             | 0           | # Moscow itself
  | 3           | 3             | 0           |
  | 2           | 1             | 1           | # Moscow/Kremlin
  | 2           | 3             | 1           | # Moscow/R. Sq.
  | … (long long array) …                     |
```

Eventually, we need to:

* Fetch the source table `id` and `parent_id` columns via a single `SELECT`.
* Find all the descendants of each fetched `id`.
* Make an in-memory array with the resulting values as shown above.
* Save it to the reference table using the `COPY FROM` statement.

I have encapsulated these steps into a reusable library.

## My [pg_closure_tree_rebuild](https://github.com/gzigzigzeo/pg_closure_tree_rebuild) gem will do the job!

You can use it from the command line:

```
> bundle exec rake closure_tree:rebuild DATABASE_URL=postgres://localhost/tax_authorities TABLE=tax_authorities
```

or from your code:

```ruby
# seeds.rb
PgClosureTreeRebuild::Runner.new(
  Sequel.connect(ActiveRecord::Base.connection_config), 'tax_authorities'
).run
```

## Result

It only took 3.5 minutes to deal with 1 188 483 records, which otherwise would have taken hours:

```
138.100000   4.060000 142.160000 (203.340859)
```

12.5 times faster compared to Materialized Path. Awesome.

---

[The result](https://github.com/gzigzigzeo/pg_closure_tree_rebuild) was indeed worth the time and effort spent. It was exactly the solution I wanted. Of course, the fact that it did pay off in my case does not mean that you should stick to it too. If your task is different from the one I had, then another pattern or a set of patterns might do a better job. Anyway, whatever option you prefer, remember to avoid Nested Set. Below is a summary of what I’ve learned. I hope you will find it useful.

* Use `COPY FROM` to populate tables whenever possible.
* Use the Closure Table pattern (and [the closure_tree](https://github.com/mceachen/closure_tree) gem) as it is the simplest tree pattern especially if you don’t do anything but read.
* Use [the pg_closure_tree_rebuild](https://github.com/gzigzigzeo/pg_closure_tree_rebuild) gem instead of the standard `#rebuild!` method of [closure_tree](https://github.com/mceachen/closure_tree) as it is faster.

---

This article was written by [Evil Martians](https://evilmartians.com), a product development consultancy trusted by teams from early-stage startups to public companies. If you're working through a hard problem, [we can help](https://evilmartians.com/contact-us)