title: Mysql: Optimizing finding super node in nested set tree
body: <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>