IME、MySQLはサブクエリの最適化に適していません。特に、プッシュ述語を管理していないようです。
クエリが実際に何を返すことを意図しているのか、特に「サブペアレント」について少し混乱しています。
left_idとright_idを1つのインデックスに入れることで、ある程度の改善が得られます。
クエリをストアドプロシージャに展開することである程度の改善も得られますが、毎回データセットのほぼ全体をトラバースしているように見える場合、ツリーの深さを非正規化し、各ノードの属性として保存するのがより良い解決策になります。実際、外部クエリだけで少なくとも2回はトラバースしているようです。
ただし、クエリの最後に次のことに気付きました：
HAVING depth > 0
AND depth <= 1
これは確かに
と同じことですHAVING depth=1
これにより、クエリを最適化する非常に異なる方法が提供されます（right =left + 1のすべてのノードを取得して、子のないノードを見つけ、カテゴリIDを確認する方法を検討します）。