Eloquent: How to Recursively get the details of the top of the tree for a given child

If you were using Oracle RDBMS I'd say use CONNECT BY PRIOR but I'm guessing MySQL.

Here is a little guide for hierarchical queries.

https://explainextended.com/2009/03/17/hierarchical-queries-in-mysql/

@tray2 yes I am using MySQL. Looking for a Laravel-way of doing the hierarchical queries.

Not sure you can do that in Eloquent and still keep the readabilty.

Complex queries like this is better imho to do in SQL rather than Eloquent.

@tray2 would something like this be efficient in your opinion? https://stackoverflow.com/a/29972187/11491070

Though I have to admit, I do find it a bit confusing. Any idea how I would need to modify the code in StackOverflow? Some sample code would be helpful!

It depends on how deep you can nest.

If it's just 2-3 levels then sure it would work but the more levels you got the slower it will get and the more resources it will use.

It's usually better to let the database do the heavy lifting.

Agreed. Still trying to find an efficient MySQL query to do this, though. I found https://stackoverflow.com/questions/20215744/how-to-create-a-mysql-hierarchical-recursive-query and tried these

select @pv:=id as id, comment_hash, commentable_id, commentable_type, body
from comments
join
(select @pv:=15)tmp
where commentable_id=@pv;

select
    @pv:=c1.id as id
  , c2.body as parent_body
  , c1.body body
  , c1.commentable_id
  , c1.commentable_type
from comments c1
join (select @pv:=15)tmp
left join comments c2 on c2.id=c1.commentable_id -- optional join to get parent name
where c1.commentable_id=@pv;

but honestly have no clue what I am doing. None of these are giving the result I expect (post id#5) I (think?) these are going down the hierarchy chain instead of up.

Why not use php to generate the tree? I have a dedicated class for this very purpose:

class CollectionRecursive
{
  public $result = [];
  
  
  public function generate(array &$collection, $start, $branch)
  {
    $result = [];
    foreach ($collection as $item)
    {
      if ($item->{$branch} === $start)
      {
        $branches = $this->generate($collection, $item->id, $branch);
        
        if ($branches)
          $item->branches = $branches;
        
        $result[] = $item;
      }
    }
    
    return $result;
  }
  
  
  public function generateAll(array &$collection, string $start, string $branch)
  {
    foreach ($collection as $item)
    {
      if ($item->{$branch} === $start)
      {
        $branches = $this->generate($collection, $item->id, $branch);
        
        if ($branches)
          $item->branches = $branches;
        
        $this->result[] = $item;
      }
      else
        $this->result[] = $item;
    }
    
    return $this->result;
  }

In your controller for instance:

public function handle(CollectionRecursive $collectionRecursive)
  {
    
    return $collectionRecursive->generateAll(Comment::all(), 0, 'comment_id');
  }

It takes an array of objects, the start of the tree you want to get into and the parent_id or branch that denotes the hierarchy.

Hi @connecteev ,

$comment = \App\Comment::find(17);

do{
    if ($comment->commentable){
        print_r('comment id #'.$comment->id.' (with comment_hash: '.$comment->comment_hash.') which is the child of:');
        print_r('<br>');
    }
    else{
        print_r('post id #'.$comment->id);
        print_r('<br>');
    }
}while($comment = $comment->commentable);

1. Find the last comment using "id" or "comment_hash".
2. Loop over it till there are "commentable" relationship exists.
3. If no more "commentable" relationship exists then you have reached the top of the comment tree i.e. Post in your case.

Hopefully, this will help.

Regards

HI @connecteev

Reading through your problem description, i would store post_id in a separate column. I read you do not intend to store it but it actually makes sense as a Comment "Belongs To" a post regardless of its depth. This seems to me an indicative of this relation with the Post model in your Comment instances regardless of their relation to other comments.

Querying recursively for a tree root when using deeply nested hierarchies can be very costly. A bit of redundancy is sometimes worth it, think of a Bank needing to loop over all of a customer's transactions to just show their balance.

So if adding a post_id column is something you won't do for some reason, regardless of the performance or any other impacts. You could try this if you are running MySQL 8.

Create a view to run a recursive CTE:

$ php artisan make:migration create_comment_post_view

And then

<?php

use Illuminate\Database\Migrations\Migration;
use Illuminate\Support\Facades\DB;

class CreateCommentPostView extends Migration
{
    public function up()
    {
        $sql = <<<SQL
CREATE VIEW comment_post AS
WITH RECURSIVE tree (comment_id, post_id) AS (
    SELECT id AS comment_id, commentable_id AS post_id
    FROM comments
    WHERE commentable_type = 'App\\\\Post'
    UNION ALL
    SELECT comments.id, tree.post_id
    FROM comments
    INNER JOIN tree
        ON tree.comment_id = comments.commentable_id
        AND comments.commentable_type = 'App\\\\Comment'
)
SELECT comment_id, post_id FROM tree;
SQL;

        DB::statement($sql);
    }

    public function down()
    {
        DB::statement('DROP VIEW comment_post');
    }
}

You'll need 4 backslashes (\) in the query definition to circumvent PHP and MySQL escaping of this character. (I had to type 8 backslahes to get the output correct in the code sample above).

(Note: Regarding this I recommend you to read about custom polymorphic maps: https://laravel.com/docs/6.x/eloquent-relationships#custom-polymorphic-types so you don't need to store PHP classpath in MySQL and avoid problems if you choose to change your code structure).

Then add this relation in you Comment model:

<?php

namespace App;

use Illuminate\Database\Eloquent\Model;

class Comment extends Model
{
    // ... other code

    public function commentable()
    {
        return $this->morphTo();
    }

    public function comments()
    {
        return $this->morphMany(Comment::class, 'commentable');
    }

    public function post()
    {
        $query = Post::query()
            // JOIN with the created view
            ->join('comment_post', 'comment_post.post_id', '=', 'posts.id');

        return $this->newHasOne($query, $this, 'comment_post.comment_id', 'id');
    }
}

The you can even eager load your post relation:

// routes/web.php


Route::get('/comments', function () {
    $comments = \App\Comment::query()
        ->with(['post'])
        ->get();

    return $comments;
});

Again, I don't know your business requirements and can't say why you don't intend to add a post_id column in you comments table as there is a clear relation between comments and post. It is not up to me to judge this decisions and maybe there are other restrictions.

But, If you can, I would definitively prefer to add a post_id column to the comments table to avoid running these high cost queries if the need to know a comment's post is something usual in your app.

@artcore thank you for sharing your solution...I really appreciate it. I tried but could not get this to work....I am not sure how to use your code.

@jatinkumar thank you as well. I also tried your solution (a simple loop), with some edits:

        $commentId = 17;

        $k = [];
        do {
            $myComment = Comment::find($commentId);
            $k[] = $commentId;
            $commentId = $myComment['commentable_id'];
        } while ($commentId && $myComment['commentable_type'] == "App\Comment");

This works by navigating up the hierarchy, but wondering if there's a more efficient way....maybe with a single MySQL query..

@rodrigo.pedra hi again! Thank you for your help last time, and now with this.

To address your first comment: You're right, I should probably include a post_id relation in my comments table / model, and then the problem becomes trivial. That also is the right way to do things, I'm sure. The problem is I don't have this relation already, and have a lot of code that is working fine without it. I don't have any unit tests (I know, I should add some, and that's on my roadmap...just not something I can get into now, because that would be quite a big tangent). To reduce the number of moving parts for now I am trying not to introduce a post_id field.

On your second comment: I am on MySQL 5.7 (sorry I should have mentioned this earlier)

$ mysql --version
mysql  Ver 14.14 Distrib 5.7.27, for Linux (x86_64) using  EditLine wrapper

Is there a way to get your solution working with 5.7? Btw, what is newHasOne? I don't see that defined...curious if something is missing in the snippet. Again, thanks for your help.

Hi @connecteev ,

Well, I don't know any straightforward solution with MySQL (before 8) that doesn't involve some kind of variable initialization (as you already posted before, the one with @pv := ...) or using stored procedures for using while loops or something like that.

In your case I would:

1. Add a post_id to the comments table
2. Use a closure table (as described here: https://www.percona.com/live/17/sites/default/files/slides/Recursive%20Query%20Throwdown.pdf )

Actually Bill Karwin, the author of the slides linked above, is the author of a very good book on SQL anti-patterns. In a chapter he described several solutions about managing tree-like data with SQL.

I used the closure table approach in several projects, it is kinda hard to add/delete/update, but it is very easy to select and performance when selecting is not a problem.

As you told before that you don't want to introduce changes to the project's data model, as you don't have many (or any) unit tests in place, I would go with some PHP solution, although that would run a lot of individual queries to get the data.

I would use a PHP-based solution instead of an initialization based solution because that would require MySQL to scan all the comments table before finding a solution. When you have few comments it will be fast, but when your comments table grows a lot it will be slower than making individual queries to find the tree root from a comment.

Also, as the initialization solution relies on MySQL session variables (@pv = ...) in long running queries you could get wrong results if two queries run in the same session/connection.

About newHasOne

Generally when defining relations we use some helper methods such as:

public function post() {
    return $this->hasOne(Post::class);
}

If you look on the implementation of the hasOne(...) method used above you will see that it uses newHasOne(...) internally. ( https://github.com/laravel/framework/blob/6.x/src/Illuminate/Database/Eloquent/Concerns/HasRelationships.php#L63 )

Which in turn is just a proxy to a new HasOne(...) where HasOne is a class that knows how to build a has-one relation.

I stepped one level below from hasOne(...) to newHasOne as the formwe expect a class name whereas the second accepts a query builder. So I could attach the join to the query builder from the Post model.

The proxy methods for each relation exist to allow the user to use custom relationship objects without loosing the ability to perform customization on the query objects passed to these relation objects.

One more thing.

If you want to profile theses queries in your project:

SELECT post_id
FROM (
    SELECT
        @post_id := (SELECT commentable_id FROM comments WHERE id = @comment_id and commentable_type = 'App\\Post') AS post_id,
        @comment_id := (SELECT commentable_id FROM comments WHERE id = @comment_id and commentable_type = 'App\\Comment') AS comment_id
    FROM
        comments, (SELECT @comment_id := 3500, @post_id := NULL) AS initialization
    WHERE @post_id IS NULL
) AS recurse
WHERE post_id IS NOT NULL;

Other approach:

SELECT
    commentable_id as post_id
from comments
WHERE id = (SELECT MIN(comment_id) FROM (SELECT
    @comment_id := (SELECT commentable_id FROM comments WHERE id = @comment_id and commentable_type = 'App\Comment') AS comment_id
FROM
    comments, (SELECT @comment_id := 3500, @post_id := NULL) AS initialization
WHERE @comment_id IS NOT NULL) AS recurse);

They took around 1 second to run on my machine on a comments table with about 125K records for a comment in the 20th level.

For a comment in the 5th level both queries run under 500ms.

In both scenarios the first query runs a bit faster than the second.

500ms to 1 second is a lot for user interaction, but if your need is to run in some kind of queued job or console command it might be ok depending on the frequency of those jobs/commands.

Also there might be some easy optimizations on the queries above as I am bit rust on writing this kind of queries.

A I had that view in place and internally it uses a recursive CTE (in MySQL 8) it might be worth to add that for the same number of rows querying that view runs in about 500-600ms.

For reference I made a script to seed around 6000 posts with 20 nested comments each.

I don't know the performance requirements for your application. If it is a corporate blog that will have around 20-50 posts a year go with a query-only or PHP based solution.

If you expect high volume of posts and comments it seems that having some redundancy (a post_id column or maintain a closure table) to speed up those queries is a good idea.

Hi @rodrigo.pedra, this is phenomenal, thank you for the detailed response. I spent the day thinking and trying out your solutions....

I do have to eventually get to the point of adding the post_id to the comments table....but for now, this works quite well :)

SELECT post_id
FROM (
    SELECT
        @post_id := (SELECT commentable_id FROM comments WHERE id = @comment_id and commentable_type = 'App\Post') AS post_id,
        @comment_id := (SELECT commentable_id FROM comments WHERE id = @comment_id and commentable_type = 'App\Comment') AS comment_id
    FROM
        comments, (SELECT @comment_id := 3500, @post_id := NULL) AS initialization
    WHERE @post_id IS NULL
) AS recurse
WHERE post_id IS NOT NULL;

Thank you again..and I will be coming back to this to try the other approaches you suggested.

Great ! Glad to help =)

One info that might help you in the future is that the order of columns on that SELECT clause matters. As the first columns (@post_id:= ...) will be executed before updating the @comment_id column.

I didn't know that. Thank you @rodrigo.pedra !