How to get maximum performance in a many-to-many relationship?

I want to ask for advice:

Let's assume that the site has 1 million products and 3 thousand categories. The category table has category_id and parent_id. Many-to-many relationship.

What is the best way to link a product to a category?

Option 1: Link to one final category. For example, “handbags”. When requesting products from the “handbags” category, everything is simple and fast. But when requesting products from the “clothing, shoes and accessories” category, I first, through recursion, get a list of all nested category IDs from the category table, and then I request all products associated with these categories (I list a thousand category IDs). Since nesting can be large, for example: Clothes, shoes and accessories -> Accessories -> Bags and backpacks -> Bags -> Handbags.

Option 2: Link a product to all categories from the final category to the highest parent category at once. That is, first I get a list of parent category IDs from the categories table through recursion and write several rows into the categories_products table. In this case, when requesting items from the "clothing, shoes and accessories" category, I will only request items related to that one category.

How, then, can you get maximum performance when displaying products to the user?

Now I do this:

$allCategories = Category::where('total_products', '!=', 0)->get();
$idsChildCategories = Functions::getIdsChildCategories($allCategories, $category->title, $category->category_id, $category->id);

$allProducts = Product::whereHas('categories', function ($query) use ($idsChildCategories){
                $allProducts = Product::whereHas('categories', function ($query) use ($idsChildCategories) {
                $query->whereIn('categories.id', $idsChildCategories);
            })
                ->where('price', '!=', null)
                ->orderBy($sort['value'], $sort['flags'])
                ->with('categories', 'genders', 'brands', 'colors', 'styles', 'materials', 'seasons', 'countries', 'features', 'ages')
                ->get();

static function getIdsChildCategories($allCategories, $category_title, $category_id, $id) {
        if (isset($category_title)) {
            $array = [$id];
        } else {
            $array = [];
        }
        foreach ($allCategories as $key => $value) {

            if ($value->parent_id == $category_id && $value->total_products > 0) {
                $array[] = $value->id;
                $array[] = self::getIdsChildCategories($allCategories, null, $value->category_id, $value->id);
            }
        }
        $flattened = Arr::flatten($array);
        return $flattened;
    }