IME, MySQL non riesce a ottimizzare le sottoquery, in particolare non sembra gestire i predicati push.
Sono un po' confuso su ciò che la query è effettivamente destinata a restituire, in particolare il "sotto-genitore"
Otterresti qualche miglioramento inserendo left_id e right_id in un unico indice.
Mentre otterrai anche qualche miglioramento srotolando la query in una stored procedure, dato che sembra che tu stia attraversando quasi l'intero set di dati ogni volta, una soluzione migliore sarebbe denormalizzare la profondità dell'albero e memorizzarla come attributo per ogni nodo. Sembra che tu lo stia attraversando almeno due volte solo nella query esterna.
Tuttavia noto che alla fine della query:
HAVING depth > 0
AND depth <= 1
Che sicuramente è la stessa cosa di
HAVING depth=1
Il che fornisce quindi un modo molto diverso per ottimizzare la query (inizia ottenendo tutti i nodi dove destra=sinistra+1 per trovare i nodi senza figli e procedi per controllare l'id della categoria).
