How to implement a graph of nodes without duplicate descendants?

[bluesheep100]

I'm not sure if the title is clear, but essentially I have a structure with a single table containing Nodes, where each Node (through a pivot table node_node) can have an indeterminate amount of parents and/or children.

I set this up just fine, using a model like so:

use Staudenmeir\LaravelAdjacencyList\Eloquent\HasGraphRelationships;

class Node extends Model
{
    use HasGraphRelationships;

    // Override methods for custom table/column names here
}

This seems to work, but I don't get the output I expect. Say I have 1 root Node, with 36 direct children. Each of these 36 children are parents to the same 1 grandchild Node. In this case, I'd expect $node->descendants()->count() to return 37, as it has 37 rows in the nodes table that exist below it in the "family tree". However, I instead get a much larger number, where the counted set contains 36 copies of the grandchild Node.
In the simplest terms, I expect this situation to behave essentially like a BelongsToManyDeep kind of relationship.

My understanding of why this occurs is that the descendants() method returns a result for each direct child, and a copy of the grandchild for each child of the root Node, based on this issue.

One workaround I could potentially implement would look like this:

$ids = $node->descendants()->getQuery()->select('nodes.id')->distinct()->get()->pluck('id');
$descendants = Node::whereIn('id', $ids)->get();

I get the feeling I'm misunderstanding a concept in how to use this package, and I'd like to avoid using this workaround as performance is important, and I need to do it in many places throughout the application.

As per the above issue, I understand that this behaviour won't be implemented as default, as it's a breaking change, but would it be possible to add an option to the relationship methods to support this? Simply chaining ->distinct() to the relationship query doesn't work in general, as it compares the entire row, and not the single column I want to use to determine uniqueness.

Thanks for your time and help in advance.

[staudenmeir]

Hi @bluesheep100,

However, I instead get a much larger number, where the counted set contains 36 copies of the grandchild Node.

The descendants query traverses the graph to discover all possible paths and return the nodes it finds on the way. The grandchild node is returned 36 times because 36 different paths lead to it. Each query result is a "combination" of a node and a path leading to it (represented by the depth and path attributes).

From the other issue:

If you have additional columns in the category_company pivot table, they can also be different for "duplicate" companies.

If your pivot table contains additional columns, the different grandchild query results have different pivot values depending on the path.

As per the above issue, I understand that this behaviour won't be implemented as default

The current behavior is the default because it's the SQL query's "natural" behavior (it's also the most useful behavior for the applications that I know). Removing "duplicate" nodes can only be an additional step on top of that.

but would it be possible to add an option to the relationship methods to support this?

I've looked into this topic quite a bit because it's also relevant for another one of my packages, but it's quite the nightmare.

Simply chaining ->distinct() to the relationship query doesn't work in general, as it compares the entire row, and not the single column I want to use to determine uniqueness.

That's exactly the reason why the whole topic is so complicated. A general solution also needs to work with eager loading etc.

[bluesheep100]

Thank you for the fast response!

The descendants query traverses the graph to discover all possible paths and return the nodes it finds on the way. The grandchild node is returned 36 times because 36 different paths lead to it. Each query result is a "combination" of a node and a path leading to it (represented by the depth and path attributes).

This helped me lots with understanding the concepts, actually, thank you.

If your pivot table contains additional columns, the different grandchild query results have different pivot values depending on the path.

I do have additional columns, although they're simply the standard $table->timestamps() fields. On that note, since all the relationships on Graphs are predefined, how would I keep these timestamps updated like with $this->belongsToMany(Foo::class)->withTimestamps()? Would I need to chain ->withTimestamps to all my descendant queries, make wrapper methods for the relationships, or something else?

[staudenmeir]

To retrieve the timestamp columns, you need to add them to getPivotColumns().

When you create/update pivot records, you can apply withTimestamps() to the package's children()/parents() relationships:

$node->children()->withTimestamps()->attach(...);

[bluesheep100]

That did it, although the records seemed to need recreating for it to work, but now it does. 😄

Thank you very much.

[staudenmeir]

One workaround I could potentially implement would look like this:

The easiest solution is removing duplicates from the result collection:

$uniqueDescendants = $node->descendants->unique();

I'd like to avoid using this workaround as performance is important, and I need to do it in many places throughout the application.

Are you having performance issues?

[bluesheep100]

Hi @staudenmeir

I did some rudimentary benchmarking in my application where this workaround applies, and yeah, it has performance issues, but they definitely have nothing to do with this package. This is specifically about querying for jobs to do, where said job is fetching a large JSON package from a remote API, parsing it to filter out undesirable data, then saving it in MySQL.

For a reasonably large process, the workaround code is called ~40 times. The total time spent on database queries is ~1300ms, where the graph queries (ones that contain 'with recursive' specifically) make up ~20ms, which is about 1.58% of the total query time.

I found a greater timesave (albeit ultimately very minor regardless) of ~60% on that query by simply excluding the JSON column, since it's not needed in that section.
Suffice to say, I have bigger fish to fry 😅

Thank you very much for the quick response!