Ich habe hierarchische Daten in einem verschachtelten Mengenmodell (Tabelle: Projekte):

Mein Tisch (Projekte):

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

Schön gedruckt:

 1
  2
  3
 4
  5
 6
 7

Um den nächsten Superknoten von Knoten 3 zu finden (mit Kenntnis seines LFT-Werts), kann ich tun

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

Das gibt mir eine Liste der Projekte im Pfad bis zu Knoten 3. Durch Gruppieren und Finden von MAX (projects.lft) der Ergebnisse erhalte ich den nächsten Superknoten. Es scheint jedoch nicht möglich zu sein, dass diese Abfrage schnell ausgeführt wird. Die von mir definierten Indizes werden nicht verwendet. EXPLAIN sagt:

+----+-------------+----------+-------+----------------+----------+---------+------+------+--------------------------+
| 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 versteht, welchen Index es verwenden soll, muss aber trotzdem alle 10 Zeilen durchlaufen (oder 100k in meiner aktuellen Tabelle).

Wie kann ich MySQL dazu bringen, diese Abfrage richtig zu optimieren? Ich füge unten ein Testskript ein.

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