How to build a big tree that changes frequently?

Question

MySQL

Good afternoon experts.
In general, the question is this:
There is a large tree that changes steadily once a month. Now everything is implemented according to the Nested set model, because it is very easy to pull out the whole tree (and it is done often) without using recursion. But if you just need to pull out a tree - everything is simple. But this JOIN tree has data from other tables, and there is a lot of data (about 20-30 thousand rows).
To understand the issue, the application does the following: there is a structure of the sales department (structure), such as Region->City->Manager->Sales representative. Those. the tree is usually 5 to 7 levels. There is also a table of plans (plans), which stores monthly sales plans (structure_id, month, plan). And the sales table (sales) daily (structure_id, date, sale).
There is a request like:

SELECT
DISTINCT s1.id as id,
s1.name as name,
s1.left_key as left_key,
s1.right_key as right_key,
s1.level as level,
(SELECT s2.id FROM structure s2
 WHERE s2.left_key < s1.left_key AND s2.right_key > s1.right_key
 ORDER BY s2.right_key-s1.right_key ASC LIMIT 1) as parent,
(SELECT SUM(sum) FROM structure s3
 JOIN sales r ON s3.id = r.structure_id
 WHERE s3.left_key >= s1.left_key AND s3.right_key <= s1.right_key
 AND r.date BETWEEN $startDate AND $endDate) as sum,
p.plan as plan
FROM structure s1
LEFT JOIN plans p ON s1.id = p.structure_id
AND p.month = $month
WHERE s1.left_key >= $leftKey AND s1.right_key <= $rightKey
ORDER BY s1.left_key ASC

The query takes an unforgivably long time, especially when the number of queries to the database increases (usually this happens in the morning when everyone is watching the current execution of plans).
In general, there are several questions
. 1. Is it worth rebuilding the tree into the Adjacency list model or leaving the Nested set for this task?
2. How to index the structure table correctly (an index including left_key and right_key and two separate indexes does not work, or rather mysql does not use them, and the entire structure table is scanned).
3. It might be worth fixing the request, but I don't know how. If anyone knows, please advise.
Thanks in advance.