coryodaniel/arbor

Ecto elixir adjacency list and tree traversal. Supports Ecto versions 2 and 3.

arbor's Issues

delete, adoption

:orphan_strategy is already accepted (no action taken).

Not sure that this is the business of this library...

orphan_strategy:

• nilify - makes children root
• destroy - duh
• adopt - makes children children of parent record, or roots them
• nothing - let PG do whatever its doing

Hierarchy Descendants return type option

Add a second descendants option that instead of tracking depth tracks the parent id and organizes the results in a tree structure instead of a list.

Support for multiple parents

The tree name could be prefixed on tree methods...

use Arbor.Tree, my_tree: opts, my_other_tree: more_opts

Depths selector on descendants and subtree

Add to recursive section of CTE:

AND cardinality(tree.ancestors) < XXX

function instead of macro

It might be nice to have this implemented as a function instead of a macro that can be called arbitrarily instead of having to be used.

Arbor.Tree.children(struct)

I had experimented with this originally, but using fragment when postgres objects were interpolated they were interpreted as strings, so you would get stuff like:

SELECT * from 'comments'

Which obviously blows up. I think this could be possible with a custom ecto datatype that type cast postgres objects correctly.

Document tree macros

Can you document macros?

Support dynamic switching of schema prefixes

Howdy!

So right now when we're using Arbor, the fragment/1 call in ancestors/1 and descendants/1 are essentially hard coded at compile time because of the restrictions of fragment/1.

However, it would be really nice if they could use the prefix in the given's struct's :__meta__.prefix field so we're always searching for ancestors and descendants in the same schema as the given struct.

Since all of these strings used in fragment/1 need to be compiled and not interpolated, my initial thought is to allow users to configure a number of prefixes that they want to compile functions for, sort of like this:

for prefix <- opts[:prefixes] do
  def descendants(%{__meta__: %{prefix: unquote(prefix)}} = struct, depth \\ 2_147_483_647) do
    from(
      t in unquote(definition),
      where:
        t.unquote(opts[:primary_key]) in fragment(
          unquote("""
          WITH RECURSIVE #{opts[:tree_name]} AS (
            SELECT #{opts[:primary_key]},
                    0 AS depth
            FROM #{prefix}.#{opts[:table_name]}
            WHERE #{opts[:foreign_key]} = ?
          UNION ALL
            SELECT #{opts[:table_name]}.#{opts[:primary_key]},
                    #{opts[:tree_name]}.depth + 1
            FROM #{prefix}.#{opts[:table_name]}
              JOIN #{opts[:tree_name]}
              ON #{opts[:table_name]}.#{opts[:foreign_key]} = #{opts[:tree_name]}.#{
            opts[:primary_key]
          }
            WHERE #{opts[:tree_name]}.depth + 1 < ?
          )
          SELECT #{opts[:primary_key]} FROM #{opts[:tree_name]}
          """),
          type(^struct.unquote(opts[:primary_key]), unquote(opts[:foreign_key_type])),
          type(^depth, :integer)
        )
    )
  end
end

Then there could be at the end the same definition that you have now with no pattern matching.

So, sound like something that makes sense to you? If so, I'll send along a PR.

parent_key and parent_key_type not registering

In the options definition:

foreign_key
foreign_key_type

Seem to be set incorrectly.

The tests appear to pass only because there isn't one for a custom foreign_key and that the foreign_key_type happens to be the same as the primary_key_type for the test of a custom type.

There is no Test for Foreign Keys, So I'm making a PR
I'm pretty new to Elixir, but would you like a PR for this?
I'm super excited to use this in a project of mine.

Recommanded way of retrieving all roots along with their descendents(n)?

For a basic Post & Comments schema, I have to retrieve the post along with all of its root comments and the descendents for each root comment upto nth level. From the documentation all the built in functions for descendents work on a struct and not a list of struct/ids, so currently I'm having to retrieve the descendents individually. Is there any easier way of fetching this in single preload query?

leafs/0

Get all nodes without children

leafs = Comment.leafs

Support for preloading associations?

I want to be able to do something like:
folder |> Folder.descendants(preload: [:contracts]) |> Repo.all

Right now, I'm using the following solution:
folder |> Folder.descendants |> Repo.all |> Enum.map(&Repo.preload(&1, [:contracts]))
which looks very hack-y.

Add 'path' function

Returns Ancestors + source struct

This is probably pretty easy to do now using the same CTE as ancestors but joining on id rather than parent_id...

breadcrumbs = Comment.path(comment)

prefix not found in struct_fields[:__meta__].source

I am using {:arbor, "~> 1.0.6"}
with table

create table(:comments) do
   add(:body, :text)
   add(:parent_id, references(:comments), on_delete: :delete_all)
end
create index(:comments, [:parent_id])

and a schema

defmodule Test.Comment do
  use Ecto.Schema

  use Arbor.Tree,
    foreign_key: :parent_id,
    foreign_key_type: :integer

  import Ecto.Query

  schema "comments" do
    field(:body, :string)
    belongs_to(:parent, Test.Comment)
  end
end

And I am getting this error

== Compilation error in file lib/test/comment.ex ==
** (MatchError) no match of right hand side value: "comments"
    expanding macro: Arbor.Tree.__before_compile__/1
    lib/test/comment.ex:1: Testpu.Comment (module)
    (elixir) lib/kernel/parallel_compiler.ex:198: anonymous fn/4 in Kernel.ParallelCompiler.spawn_workers/6

It turns out this line

arbor/lib/arbor/tree.ex

Line 40 in 1c63aae

{prefix, source} = struct_fields[:__meta__].source

causing problem.

It is expecting a prefix in the tuple {prefix, source} while struct_fields[:__meta__].source only returns {source} which resulted in a MatchError.

It looks like it has been fixed for Ecto3, is support for Ecto2 still maintained?

Slow Arbor.Tree.ancestor/1 performance w/ table over 1mm records

Descendants, siblings and children perform very well (tested up to 15mm rows). Ancestors runs at about 4s / query at 1mm nodes and times out on 15mm nodes...

See arbor bench

Running siblings
	10000 runs
	Total time: 2.3324530000000046
	Avg: 2.3324530000000046e-4
Running children
	10000 runs
	Total time: 2.1838109999999857
	Avg: 2.1838109999999857e-4
Running descendants
	10000 runs
	Total time: 2.141958000000028
	Avg: 2.1419580000000277e-4

Move subtree

Again, not sure if this is the libraries responsibility since its so simple to change the parent_id...

Ecto struct_fields

arbor/lib/arbor/tree.ex

Line 39 in 1d3c610

struct_fields = Module.get_attribute(definition, :struct_fields)

It is now :ecto_struct_fields in Ecto 3.8

Although switching to :ecto_struct_fields would also imply ecto >= 3.8 and elixir ~> 1.10

Move each query/operation into its own module

Consider moving each of the query/operations into their own module to make Arbor.Tree not so intense.

Support ltree in postgres

Postgres has great native support for trees using the ltree and lquery functions. Maybe it deserves some look to see if it can be inserted into the library.

ancestors error

My table is in other schema, let's say "network", not the public.
the ancestors function output:

SELECT u0."id", u0."name", u0."superior_id" FROM "network"."user" AS u0 INNER JOIN (
  WITH RECURSIVE user_tree AS (
    SELECT id,
          superior_id,
          0 AS depth
    FROM user
    WHERE id = 4
  UNION ALL
    SELECT user.id,
          user.superior_id,
          user_tree.depth + 1
    FROM user
      JOIN user_tree
      ON user_tree.superior_id = user.id
  )
  SELECT *
  FROM user_tree
)
 AS f1 ON u0."id" = f1."superior_id"

but the sql should be:

SELECT u0."id", u0."name", u0."superior_id" FROM "network"."user" AS u0 INNER JOIN (
  WITH RECURSIVE user_tree AS (
    SELECT id,
          superior_id,
          0 AS depth
    FROM "network".user
    WHERE id = 4
  UNION ALL
    SELECT id,
          superior_id,
          user_tree.depth + 1
    FROM user
      JOIN user_tree
      ON user_tree.superior_id = id
  )
  SELECT *
  FROM user_tree
)
 AS f1 ON u0."id" = f1."superior_id"

But I don't know how to add the schema name to the table.

Subtree function

Source struct + descendants

subtree = Comment.subtree(comment)

descendants error

I just call the descendants/1 function but it return the error:

** (Postgrex.Error) ERROR 42601 (syntax_error) syntax error at or near "."
SELECT u0."id", u0."name" FROM "agent_1"."user" AS u0 WHERE (u0."id" = ANY(WITH RECURSIVE user_tree AS (
  SELECT id,
         0 AS depth
  FROM user
  WHERE parent_id = $1::bigint
UNION ALL
  SELECT user.id,
         user_tree.depth + 1
  FROM user
    JOIN user_tree
    ON user.parent_id = user_tree.id
  WHERE user_tree.depth + 1 < $2::bigint
)
SELECT id FROM user_tree
)) [1, 2147483647]

And I execute it in the sql command line, the same error msg.

Passing a root element to siblings raises casting error

value nil in where cannot be cast to type :id (if you want to check for nils, use is_nil/1 instead) in query:

from n in ArborBench.Node,
where: n.id != type(^549844, :id),
where: fragment("parent_id = ?", type(^nil, :id)),
select: n

(elixir) lib/enum.ex:1623: Enum."-reduce/3-lists^foldl/2-0-"/3
(elixir) lib/enum.ex:1247: Enum."-map_reduce/3-lists^mapfoldl/2-0-"/3
(elixir) lib/enum.ex:1247: Enum."-map_reduce/3-lists^mapfoldl/2-0-"/3

initial use UndefinedFunctionError

After adding this dep to my mix.exs & runningmix deps.get which ran fine.

I added to my schema that has a parent_id field
use Arbor.Tree, foreign_key_type: :binary_id
belongs_to :parent, __MODULE__

On mix compile - this error:

** (UndefinedFunctionError) function nil.source/0 is undefined. If you are using the dot syntax, such as map.field or module.function(), make sure the left side of the dot is an atom or a map
    nil.source()
    (arbor 1.1.0) expanding macro: Arbor.Tree.__before_compile__/1