Skip to content

Instantly share code, notes, and snippets.

@jimsynz

jimsynz/ash_recursive_cte_wip.md

Last active July 9, 2023 21:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jimsynz/9557a2ad3ec23693f06f8588ba7ed57d to your computer and use it in GitHub Desktop.
Save jimsynz/9557a2ad3ec23693f06f8588ba7ed57d to your computer and use it in GitHub Desktop.
Download ZIP
A half-finished blog post about using recursive CTEs with Ash.
Raw
ash_recursive_cte_wip.md

Relationships to recursive common table expressions

Let me lead by saying that this is a probably a bad idea and if you're starting from scratch you should instead look at using a Postgres extension like ltree instead.

Recently I was working on a client's application and they have a Location resource which represents a physical location. Locations are a tree - ie they have a belongs_to :parent_location, Location relationship that if loaded essentially performs a self-join on the locations table. Likewise it has a has_many :child_locations, Location relationship which can be used to load all direct children of a given location. This has worked fine until now, when a new requirement arrived from the client - "users can be assigned to locations, and can only access their assigned location and any sub-locations". This sounds straight-forward enough until you get to the "and any sub-locations" - as you'll see that really throws a wrench into the works.

The first thing we need to do is add the relationships to our resources:

defmodule MyApp.User do
  # ...

  relationships do
    # ...

    has_one :location, MyApp.Location
  end
end

defmodule MyApp.Location do
  # ...

  relationships do
    # ...

    belongs_to :user, MyApp.User
  end
end

Next, we need to set up the policy to allow users to access their assigned location.

defmodule MyApp.Location do
  # ...

  policies do
    policy action_type(:read) do
      authorize_if relates_to_actor_via([:user])
    end
  end
end

It's about here that I realised how much trouble I was in. I needed a way to express "authorize if the location is assigned to the actor or any of the ancestor locations are assigned to the actor. After some thinking (and a bit of googling) I realised that I was going to have to use a recursive common table expression to find all the locations which are ancestors of the location being accessed.

A quick check of the Ecto hexdocs showed that Ecto does provide a way to execute recursive CTEs, but that behaviour is not exposed by AshPostgres, so I was going to have to implement a manual relationship. To make this work.

I started by adding the relationship to the location resource:

defmodule MyApp.Location do
  # ...

  relationships do
    # ...

    has_many :ancestor_locations, MyApp.Location do
      manual MyApp.Location.RecursiveAncestorRelationship
    end
  end
end

How we need to implement our manual relationship behaviour module:

defmodule MyApp.Location.RecursiveAncestorRelationship do
  use Ash.Resource.ManualRelationship

  @impl true
  def load(locations, _opts, _context) do
    # what goes here?
  end
end

Sadly, the documentation for manual relationships is not great (which is part of why I'm writing this), so I had to do a bit of hunting to figure out that what is expects is a map with Location IDs as the keys and a list of related records as the values. So in our case we may want something like this:

# if locations contains [%MyApp.Location{id: 3, name: "Wellington", parent_location_id: 2}]

%{
  3 => [
    %MyApp.Location{id: 2, name: "North Island", parent_location_id: 1},
    %MyApp.Location{id: 1, name: "New Zealand", parent_location_id: nil}
  ]
}

Now that we know what we need to generate, let's start by writing a SQL query which will get us what we want. Here's the query that will give us the location with the ID 3 and all it's ancestors.

WITH RECURSIVE location_tree AS (
  SELECT
    l0.id,
    l0.name,
    l0.parent_location_id
  FROM
    locations l0
  WHERE
    l0.id = 3

  UNION

  SELECT
    l2.id,
    l2.name,
    l2.parent_location_id
  FROM
    locations l2
  INNER JOIN
    location_tree
  ON
    l2.id = location_tree.parent_location_id
)
SELECT
  id,
  name,
  parent_location_id
FROM
  location_tree

The query above is a little complicated, but it breaks down fairly simply. The WITH RECURSIVE location_tree creates a recursive CTE and gives it a name. The first select within the CTE gives us the initial rows (ie select location 3). The second select performs the recursion - Postgres will use the output of the first select as the input to the second select, and then recursively pump the last output into the second select until it emits no more rows. The UNION says that we want all the unique rows from the results. If you want all the results, regardless of uniqueness use UNION ALL instead.

The last select query basically says "select the contents of the cte" which is what actually executes the query.

I have the following seed data in my database:

| id | name              | parent_location_id |
| 1  | New Zealand       |               null |
| 2  | North Island      |                  1 |
| 3  | Wellington        |                  2 |
| 4  | Te Papa Tongarewa |                  3 |

And running the query above returns:

| id | name              | parent_location_id |
| 3  | Wellington        |                  2 |
| 2  | North Island      |                  1 |
| 1  | New Zealand       |               null |

So now we know we can get the data we need, let's start converting this into an Ecto query which will load the data we need.

I'm going to start by just executing the query once for every row, which is horribly inefficient but does provide us the data we need to validate our assumptions:

defmodule MyApp.Location.RecursiveAncestorRelationship do
  use Ash.Resource.ManualRelationship
  import Ecto.Query

  @impl true
  def load(locations, _opts, _context) do
    Enum.reduce(locations, {:ok, %{}}, fn %{id: id, parent_location_id: parent_id},
                                          {:ok, results} ->
      immediate_parents =
        MyApp.Location
        |> where([l], l.id == ^parent_id)

      recursion_query =
        MyApp.Location
        |> join(:inner, [l], lt in "location_tree", on: l.id == lt.parent_location_id)

      ancestors_query =
        immediate_parents
        |> union(^recursion_query)

      ancestors =
        {"location_tree", Location}
        |> recursive_ctes(true)
        |> with_cte("location_tree", as: ^ancestors_query)
        |> MyApp.Repo.all()

      {:ok, Map.put(results, id, ancestors)}
    end)
  end
end

Now we can run the following in IEx:

iex> require Ash.Query
...> {:ok, [wellington]} = MyApp.Location |> Ash.Query.filter(id: 3) |> MyApp.read()
{:ok,
[
  #MyApp.Location<
    ancestor_locations: #Ash.NotLoaded<:relationship>,
    child_locations: #Ash.NotLoaded<:relationship>,
    parent_location: #Ash.NotLoaded<:relationship>,
    __meta__: #Ecto.Schema.Metadata<:loaded, "locations">,
    id: 3,
    name: "Wellington",
    parent_location_id: 2,
    aggregates: %{},
    calculations: %{},
    __order__: nil,
    ...
  >
]}

...> wellington |> MyApp.load(:ancestor_locations)
{:ok,
#MyApp.Location<
  ancestor_locations: [
    #MyApp.Location<
      ancestor_locations: #Ash.NotLoaded<:relationship>,
      child_locations: #Ash.NotLoaded<:relationship>,
      parent_location: #Ash.NotLoaded<:relationship>,
      __meta__: #Ecto.Schema.Metadata<:loaded, "location_tree">,
      id: 2,
      name: "North Island",
      parent_location_id: 1,
      aggregates: %{},
      calculations: %{},
      __order__: nil,
      ...
    >,
    #MyApp.Location<
      ancestor_locations: #Ash.NotLoaded<:relationship>,
      child_locations: #Ash.NotLoaded<:relationship>,
      parent_location: #Ash.NotLoaded<:relationship>,
      __meta__: #Ecto.Schema.Metadata<:loaded, "location_tree">,
      id: 1,
      name: "New Zealand",
      parent_location_id: nil,
      aggregates: %{},
      calculations: %{},
      __order__: nil,
      ...
    >
  ],
  child_locations: #Ash.NotLoaded<:relationship>,
  parent_location: #Ash.NotLoaded<:relationship>,
  __meta__: #Ecto.Schema.Metadata<:loaded, "locations">,
  id: 3,
  name: "Wellington",
  parent_location_id: 2,
  aggregates: %{},
  calculations: %{},
  __order__: nil,
  ...
>}

Awesome! Now we can go back and write our policy:

defmodule MyApp.Location do
  # ...

  policies do
    policy action_type(:read) do
      authorize_if relates_to_actor_via([:user])
      authorize_if relates_to_actor_via([:ancestor_locations, :user])
    end
  end
end

I've created a user who is linked to the Wellington location, and so should be able to see both "Wellington" and "Te Papa Tongarewa". Let's try it:

iex> require Ash.Query
...> {:ok, [user]} = MyApp.User |> Ash.Query.filter(id: 1) |> MyApp.read()
...> MyApp.read(MyApp.Location, actor: user, authorize?: true)
** (RuntimeError) No such relationship  for Elixir.MyApp.Location, required in `relates_to_actor` check

Oh no!

This is the point where I realised that I was in over my head and I asked Zach for help. It turns out that this supremely unhelpful error message is caused by the fact that Ash is trying to get the data layer (AshPostgres) to turn the relationship into a JOIN so that it can be used in the filter. Sadly, my implementation of Ash.Resource.ManualRelationship is not enough for Ash to go on in this case. I also need to implement the even worse documented AshPostgres.ManualRelationship behaviour.

Raw
recursive_ancestor_relationship.ex
defmodule MyApp.Location.RecursiveAncestorRelationship do
@moduledoc """
A manual relationship which uses a recursive CTE to find all locations which
are ancestors of this location.
"""
use Ash.Resource.ManualRelationship
use AshPostgres.ManualRelationship
alias Ash.Resource
alias MyApp.Location
alias MyApp.Repo
import Ecto.Query
@doc false
@impl true
@spec load([Resource.record()], keyword, map) ::
{:ok, %{Ecto.UUID.t() => [Location.t()]}} | {:error, any}
def load(locations, _opts, _context) do
Enum.reduce(locations, {:ok, %{}}, fn %{id: id, location_id: location_id}, {:ok, result} ->
ancestors =
Location
|> where([l], l.id == ^location_id)
|> recursive_cte_query("location_tree", Location, :dont_hack)
|> Repo.all()
{:ok, Map.put(result, id, ancestors)}
end)
end
@doc false
@impl true
@spec ash_postgres_join(Ecto.Query.t(), keyword, any, any, :inner | :left, Ecto.Query.t()) ::
{:ok, Ecto.Query.t()} | {:error, any}
def ash_postgres_join(query, _opts, current_binding, as_binding, join_type, destination_query) do
immediate_parents =
from(destination in destination_query,
where: parent_as(^current_binding).location_id == destination.id
)
cte_name = "🌳#{as_binding}"
ancestor_query =
recursive_cte_query(
immediate_parents,
cte_name,
destination_query,
:add_hack
)
case join_type do
:inner ->
{:ok,
from(row in query,
inner_lateral_join: ancestor in subquery(ancestor_query),
on: true,
as: ^as_binding
)}
:left ->
{:ok,
from(row in query,
left_lateral_join: ancestor in subquery(ancestor_query),
on: true,
as: ^as_binding
)}
end
end
@impl true
@spec ash_postgres_subquery(keyword, any, any, Ecto.Query.t()) ::
{:ok, Ecto.Query.t()} | {:error, any}
def ash_postgres_subquery(_opts, _current_binding, _as_binding, _destination_query) do
{:error, "We don't support aggregates of recursive relationships"}
end
defp recursive_cte_query(immediate_parents, cte_name, query, :add_hack) do
# The reason we have to do this bodgy stuff is because of Ecto being awesome.
# https://elixirforum.com/t/ecto-cte-queries-without-a-prefix/33148/2
# https://stackoverflow.com/questions/39458572/ecto-declare-schema-for-a-query
location_keys = Location.__schema__(:fields)
cte_name_hack =
from(cte in fragment("?", literal(^cte_name)), select: map(cte, ^location_keys))
recursion_query =
query
|> join(:inner, [l], lt in ^cte_name_hack, on: l.id == lt.location_id)
ancestors_query =
immediate_parents
|> union(^recursion_query)
cte_name_hack
|> recursive_ctes(true)
|> with_cte(^cte_name, as: ^ancestors_query)
end
defp recursive_cte_query(immediate_parents, cte_name, query, _) do
recursion_query =
query
|> join(:inner, [l], lt in ^cte_name, on: l.id == lt.location_id)
ancestors_query =
immediate_parents
|> union(^recursion_query)
{cte_name, query}
|> recursive_ctes(true)
|> with_cte(^cte_name, as: ^ancestors_query)
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment