Organizational Research By

Surprising Reserch Topic

mysql optimizing finding super node in nested set tree using -'sql,mysql,nested-sets'


mysql optimizing finding super node in nested set tree  using -'sql,mysql,nested-sets'

I have hierarchical data in a nested set model (table:projects):

My table (projects):

id, lft, rgt
1, 1, 6
2, 2, 3
3, 4, 5
4, 7, 10
5, 8, 9
6, 11, 12
7, 13, 14
...


Pretty printed:

 1
  2
  3
 4
  5
 6
 7


To find the nearest super node of node 3 (knowing its lft value), i can do

explain
SELECT projects.*
FROM projects
WHERE 4 BETWEEN projects.lft AND projects.rgt


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:

+----+-------------+----------+-------+----------------+----------+---------+------+------+--------------------------+
| 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 |
+----+-------------+----------+-------+----------------+----------+---------+------+------+--------------------------+


Mysql understands what index to use, but still has to loop through all 10 rows (or 100k in my actual table).

How can i get MySql to optimize this query properly? I include a test script beneath.

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

    
asked Sep 7, 2015 by rajesh
0 votes
11 views



Related Hot Questions



Government Jobs Opening


...