IME, MySQL не се справя добре с оптимизирането на подзаявките - особено не изглежда да управлява push-предикати.
Малко съм объркан какво всъщност е предназначено да върне заявката - особено „под-родителя“
Ще получите известно подобрение, като поставите left_id и right_id в един индекс.
Докато вие също ще получите известно подобрение чрез разгръщане на заявката в съхранена процедура, като се има предвид, че изглежда, че обхождате почти целия набор от данни всеки път, по-добро решение би било да денормализирате дълбочината на дървото и да го съхраните като атрибут за всеки възел. Наистина изглежда, че го обхождате поне два пъти само във външната заявка.
Забелязвам обаче, че в края на заявката:
HAVING depth > 0
AND depth <= 1
Което със сигурност е същото като
HAVING depth=1
Което след това предоставя много различен начин за оптимизиране на заявката (започнете, като поставите всички възли там, където right=left+1, за да намерите възлите без деца и да изработите начина за проверка на идентификатора на категорията).