Mysql: Ottimizzazione trovare super-nodo albero set nidificato

Question

ho dati gerarchici in un modello di serie nidificato (tabella: progetti):

mio tavolo (progetti):

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

Abbastanza stampata:

1 
    2 
    3 
4 
    5 
6 
7 

Per trovare il nodo più vicino eccellente del nodo 3 (conoscendo il suo valore LFT), posso fare

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

Quale mi dà un elenco dei progetti nel percorso fino al nodo 3. Quindi raggruppando e trovando MAX (projects.lft) dei risultati, ottengo il super-nodo più vicino. Tuttavia, non posso sembrare che questa query sia veloce, non userà gli indici che ho definito. SPIEGARE dice:

+----+-------------+----------+-------+----------------+----------+---------+------+------+--------------------------+ 
| 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 capisce quello dell'indice da usare, ma ha ancora a scorrere tutti 10 righe (o 100k nel mio tabella effettiva).

Come posso ottenere MySql per ottimizzare correttamente questa query? Includo uno script di test sotto.

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 

Answer 1

per ottimizzare le query set nidificati in MySQL, è necessario creare un (R-Tree) Indice SPATIAL sulle scatole set:

ALTER TABLE projects ADD sets LINESTRING; 

UPDATE projects 
SET  sets = LineString(Point(-1, lft), Point(1, rgt)); 

ALTER TABLE projects MODIFY sets LINESTRING NOT NULL; 

CREATE SPATIAL INDEX sx_projects_sets ON projects (sets); 

SELECT hp.* 
FROM projects hp 
WHERE MBRWithin(Point(0, 4), hp.sets) 
ORDER BY 
     lft; 

si veda questo articolo nel mio blog per maggiori dettagli:

• Adjacency list vs. nested sets: MySQL

Answer 2

Se non è possibile utilizzare l'indice spaziale, allora questi due indici:

ALTER TABLE projects ADD INDEX lftRgt (lft, rgt); 
ALTER TABLE projects ADD INDEX idLftRgt (id, lft, rgt); 

deve essere univoco. Ciò aiuterà molto il database.

ALTER TABLE projects ADD INDEX lft (lft); 

Non necessario: è un duplicato di lftRgt.

Answer 3

Si è verificato questo durante il tentativo di trovare aiuto sull'indicizzazione per i set annidati.

Sono atterrato con una soluzione diversa, che è ingombrante ma facilmente indicizzabile. Tuttavia renderà gli aggiornamenti ancora più lenti. Comunque lo sto postando qui perché potrebbe aiutare gli altri.

Abbiamo una tabella di categorie di prodotti, che possono avere sottocategorie, ecc. Questi dati sono abbastanza statici.

Ho impostato una tabella memorizzando nella cache le relazioni tra le categorie contenenti la categoria e una riga per ogni categoria principale (inclusa questa particolare categoria), insieme alla differenza di profondità.

Quando viene apportata una modifica alla tabella della categoria effettiva, viene semplicemente attivata una procedura per ricostruire la tabella memorizzata nella cache.

Quindi tutto ciò che controlla la relazione genitore/figlio può semplicemente utilizzare la cache per collegarsi direttamente tra una categoria e tutti i suoi figli (o un bambino e tutti i suoi genitori).

La tabella della categoria effettiva.

CREATE TABLE `category` (
    `id` int(11) NOT NULL AUTO_INCREMENT, 
    `name` varchar(128) NOT NULL, 
    `depth` int(11) NOT NULL, 
    `left_index` int(4) NOT NULL, 
    `right_index` int(4) NOT NULL, 
    `mmg_code` varchar(30) NOT NULL 
    PRIMARY KEY (`id`), 
    UNIQUE KEY `mmg_code` (`mmg_code`), 
    UNIQUE KEY `left_index_right_index` (`left_index`,`right_index`), 
    UNIQUE KEY `depth_left_index_right_index` (`depth`,`left_index`,`right_index`) 
) ENGINE=InnoDB DEFAULT CHARSET=latin1; 


DELIMITER ;; 

CREATE TRIGGER `category_ai` AFTER INSERT ON `category` FOR EACH ROW 
CALL `proc_rebuild_category_parents_cache`();; 

CREATE TRIGGER `category_au` AFTER UPDATE ON `category` FOR EACH ROW 
CALL `proc_rebuild_category_parents_cache`();; 

DELIMITER ; 

La semplice tabella di cache: -

CREATE TABLE `category_parents_cache` (
    `id` int(11) NOT NULL AUTO_INCREMENT, 
    `category_id` int(11) NOT NULL, 
    `parent_category_id` int(11) NOT NULL, 
    `depth_difference` int(11) NOT NULL, 
    PRIMARY KEY (`id`), 
    KEY `category_id` (`category_id`), 
    KEY `parent_category_id` (`parent_category_id`) 
) ENGINE=InnoDB DEFAULT CHARSET=latin1; 

La procedura: -

BEGIN 
    TRUNCATE category_parents_cache; 

    INSERT INTO category_parents_cache (id, category_id, parent_category_id, depth_difference) 
    SELECT NULL, 
      child_category.id AS category_id, 
      category.id AS parent_category_id, 
      child_category.depth - category.depth AS depth_difference 
    FROM category 
    INNER JOIN category child_category ON child_category.left_index BETWEEN category.left_index AND category.right_index 
    ORDER BY category.id, child_category.id; 
END 

Questo potrebbe probabilmente essere utilmente migliorata se la tabella è di grandi dimensioni e comunemente aggiornato.