How to query Ancestry fast

Ancestry is a great library to organize models in a tree structure.

For example, if you have Location model, which may be City, State, and Country, and you want to easily organize and query between all those entities.

By default Ancestry makes requests with LIKE query, e.g.

SELECT
  locations.*
FROM 
  locations 
WHERE
  "locations"."ancestry" LIKE '4a5b7a5d-1147-4d09-8a5d-a1a476c5be50/88fd88b7-eecd-4fc0-b18d-e2b6a077ab66/550f9809-e875-4fab-8cac-db8e6d59e0e5/%' 
OR 
  "locations"."ancestry" = '4a5b7a5d-1147-4d09-8a5d-a1a476c5be50/88fd88b7-eecd-4fc0-b18d-e2b6a077ab66/550f9809-e875-4fab-8cac-db8e6d59e0e5'

Sometimes you need to write a query to check all descendants, like

SELECT
  locations.*, count(distinct cities.id)
FROM 
  locations 
LEFT JOIN locations as cities ON 
  cities.ancestry LIKE '%' || locations.id || '%'
WHERE
  cities.location_type = 'CITY'
GROUP BY
  locations.id

(in this example locations.id is uuid, so we can use simplified LIKE query with '%' || locations.id || '%'. With int id it requires a different request)

But this request is running too long.
PostgreSQL does have indexes that may speed up LIKE queries, for example GIN and GiST.

But before using index, we can change that query to this

SELECT
  locations.*, count(distinct cities.id)
FROM 
  locations 
LEFT JOIN locations as cities ON 
  locations.id = ANY((string_to_array(cities.ancestry, '/')::uuid[]))
WHERE
  cities.location_type = 'CITY'
GROUP BY
  locations.id

And it runs MUCH faster. On our data, we get an improvement from 5 seconds to 6 ms(!).

And it's possible to use it with int ids, just change uuid[] to int[].

After we can also add GIN index to it, if we want to.

add_index :locations, "(string_to_array(ancestry, '/')::uuid[])", using: :gin

But it already runs much faster.

Another way to speed up Ancestry queries is to use ltree index, but it requires a diffent syntax.

Sources:

string_to_array: https://github.com/stefankroes/ancestry/issues/466
GIN and GiST index documentation: https://www.postgresql.org/docs/9.1/textsearch-indexes.html

ltree: https://github.com/stefankroes/ancestry/issues/102
ltree index documentation: https://www.postgresql.org/docs/9.1/ltree.html