[Question] Performance

[mikaeljorhult]

First of all, thank you for all the great work you're doing for the Laravel community!

I've been using Nested Sets for dealing with a category tree and while it works fine it introduces some complexity into the application that I would like to avoid if possible.

Adjacency List and CTE seem to be a good solution to this so I'm wondering if you know how Adjacency List holds up against Nested Sets performance vice?

Thank you again for your time!

[staudenmeir]

Thanks! Unfortunately, it's hard for me to answer that. I haven't used the package with large datasets and I haven't gotten feedback about that from other users either (positive or negative).

However, I would expect the performance to be comparable (with the right indexes and depending on the database). There's a clear advantage for write-heavy applications as inserting/updating/deleting nodes is much more efficient in adjacency lists.

What database are you using? How big is the table?

[mikaeljorhult]

Yes, I realise that it's a bit of a "how long is a piece of rope" kind of question where it always depends on the specific situation. I thought that I would at least ask in case you've tested or even read anything as I even struggle to find any good articles comparing the approaches.

I run the application on MySQL and SQLite and uses Nested Sets to create a tree view of nested categories (similar to a file tree within Finder/Explorer) that doesn't change very often so it's mainly reading from the database. Right now it has 100-200 categories in totalt including the nested ones and I have a hard time seeing anyone ever reaching even 500 items so the it isn't very large.

[staudenmeir]

I don't think performance will be an issue here, but I'd love to hear from your results.

[mikaeljorhult]

Okay, so I did some testing between Adjacency List and Nested Set today and I didn't notice any difference in performance at all.

Did the testing in two phases - I first measured the time inserting 850 nodes divided over 17 root nodes and then measured the time to build the complete tree. I tested both SQLite and MySQL and the results where within 1-2 milliseconds of each other on both tests.

So, at least for smaller trees (<1000 nodes), it don't seem to be much of a difference.

[staudenmeir]

Thanks for the update 👍