IME, MySQL não se sai bem na otimização de subconsultas - particularmente, não parece gerenciar predicados de push.
Estou um pouco confuso sobre o que a consulta realmente pretende retornar - particularmente o 'sub-pai'
Você obteria alguma melhoria colocando left_id e right_id em um único índice.
Embora você também obtenha algumas melhorias ao desenrolar a consulta em um procedimento armazenado, já que você parece estar percorrendo quase todo o conjunto de dados toda vez que uma solução melhor seria desnormalizar a profundidade da árvore e armazená-la como um atributo para cada nó. Na verdade, você parece estar percorrendo-o pelo menos duas vezes apenas na consulta externa.
No entanto, noto que no final da consulta:
HAVING depth > 0
AND depth <= 1
O que certamente é a mesma coisa que
HAVING depth=1
O que fornece uma maneira muito diferente de otimizar a consulta (comece obtendo todos os nós onde direita =esquerda + 1 para encontrar os nós sem filhos e trabalhe para verificar o ID da categoria).
