StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POMysql: Optimizing finding super node in nested set tree
text
Body
copied!<p>I have hierarchical data in a nested set model (table:projects):</p> <p>My table (projects):</p> <pre><code>id, lft, rgt 1, 1, 6 2, 2, 3 3, 4, 5 4, 7, 10 5, 8, 9 6, 11, 12 7, 13, 14 ... </code></pre> <p>Pretty printed:</p> <pre><code> 1 2 3 4 5 6 7 </code></pre> <p>To find the nearest super node of node 3 (knowing its lft value), i can do</p> <pre><code>explain SELECT projects.* FROM projects WHERE 4 BETWEEN projects.lft AND projects.rgt </code></pre> <p>Which gives me a list of the projects in the path down to node 3. Then by grouping and finding MAX(projects.lft) of the results, i get the nearest super node. However, I cannot seem to get this query to run fast, it wont use the indexes i've defined. EXPLAIN says:</p> <pre><code>+----+-------------+----------+-------+----------------+----------+---------+------+------+--------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+----------+-------+----------------+----------+---------+------+------+--------------------------+ | 1 | SIMPLE | projects | index | lft,rgt,lftRgt | idLftRgt | 12 | NULL | 10 | Using where; Using index | +----+-------------+----------+-------+----------------+----------+---------+------+------+--------------------------+ </code></pre> <p>Mysql understands what index to use, but still has to loop through all 10 rows (or 100k in my actual table). </p> <p><strong>How can i get MySql to optimize this query properly?</strong> I include a test script beneath.</p> <pre><code>DROP TABLE IF EXISTS projects; CREATE TABLE projects ( id INT NOT NULL , lft INT NOT NULL , rgt INT NOT NULL , PRIMARY KEY ( id ) ) ENGINE = MYISAM ; ALTER TABLE projects ADD INDEX lft (lft); ALTER TABLE projects ADD INDEX rgt (rgt); ALTER TABLE projects ADD INDEX lftRgt (lft, rgt); ALTER TABLE projects ADD INDEX idLftRgt (id, lft, rgt); INSERT INTO projects (id,lft,rgt) VALUES (1,1,6); INSERT INTO projects (id,lft,rgt) VALUES (2,2,3); INSERT INTO projects (id,lft,rgt) VALUES (3,4,5); INSERT INTO projects (id,lft,rgt) VALUES (4,7,10); INSERT INTO projects (id,lft,rgt) VALUES (5,8,9); INSERT INTO projects (id,lft,rgt) VALUES (6,11,12); INSERT INTO projects (id,lft,rgt) VALUES (7,13,14); INSERT INTO projects (id,lft,rgt) VALUES (8,15,16); INSERT INTO projects (id,lft,rgt) VALUES (9,17,18); INSERT INTO projects (id,lft,rgt) VALUES (10,19,20); explain SELECT projects.* FROM projects WHERE 4 BETWEEN projects.lft AND projects.rgt </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload