One Nested Set Table for Multiple Users

Question

I apologize if this has been asked before, however I'm wondering if anyone has any insight to the performance of having one nested set table for potentially thousands of users?

I need every registered user to be able to create infinite nested categories. Right now, my structure is a belongsToMany() relation:

users -> user_categories (pivot) -> categories

Users would only have access to their categories, and cannot modify other users categories.

Would there be a massive performance hit for (potentially) tens of thousands of records inside one nested set table? Should each user get their own nested set categories table?

Thanks in advance!

Answer 1

Nested sets allow to fetch all descendants of a node in a single query so for reading categories the performance hit will be similar to the one on a normal (non nested set) table. The drawback of nested sets comes when you are inserting because it requires updating left and right values for all records in the table after the insert.

So the performance hit will depend on how often do you insert and how big your insets are.

You can significantly reduce the overhead if, instead of having a single big tree, you have one root node per user, all stored in the same table, and therefore inserts will involve updating only a small subtree.

If you want to test the performance by yourself you can use the Laravel Baum package and use this seeder to see how inserting 26*10*3 categories perform:

<?php

use App\Category;
use Illuminate\Database\Seeder;

class CategoriesTableSeeder extends Seeder
{
    public function run()
    {
        // Helper function to populate model attributes
        $node = function () {
            $args = implode(' ', func_get_args());

            return ['name' => "Category $args"];
        };

        // Create first level nodes
        foreach(range('A', 'Z') as $letter)
        {
            $node0 = Category::create($node($letter));

            // Create second level nodes
            foreach(range(1, 10) as $number)
            {
                $node1 = $node0->children()->create($node($letter, $number));

                // Create third level nodes
                foreach(['Δ', 'Σ', 'Ω'] as $greek)
                {
                    $node2 = $node1->children()->create($node($letter, $number, $greek));
                }
            }
        }
    }
}