IME, MySQL klarer sig ikke godt til at optimere underforespørgsler - især ser det ikke ud til, at det håndterer push-prædikater.
Jeg er lidt forvirret over, hvad forespørgslen egentlig er beregnet til at returnere - især "underforælderen"
Du vil opnå en vis forbedring ved at sætte left_id og right_id i et enkelt indeks.
Selvom du også vil få en vis forbedring ved at rulle forespørgslen ud i en lagret procedure, givet at du ser ud til at krydse næsten hele datasættet hver gang, ville en bedre løsning være at denormalisere trædybden og gemme den som en attribut for hver node. Det ser faktisk ud til, at du krydser det mindst to gange alene i den ydre forespørgsel.
Jeg bemærker dog, at i slutningen af forespørgslen:
HAVING depth > 0
AND depth <= 1
Hvilket sikkert er det samme som
HAVING depth=1
Hvilket så giver en meget anderledes måde at optimere forespørgslen på (start med at få alle noderne hvor højre=venstre+1 for at finde noderne uden børn og arbejde dig frem til at tjekke kategori-id'et).