MySQL: Optimización de la búsqueda de súper nodo en el árbol conjunto anidado

Question

tengo datos jerárquicos en un modelo conjunto anidado (tabla: proyectos):

mi mesa (proyectos):

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

Bastante impresa:

1 
    2 
    3 
4 
    5 
6 
7 

Para encontrar el nodo de súper más cercano de nodo 3 (saber su valor LFT), puedo hacer

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

Lo que me da una lista de los proyectos en el camino hasta el nodo 3. Luego, al agrupar y encontrar MAX (projects.lft) de los resultados, obtengo el super nodo más cercano. Sin embargo, no puedo hacer que esta consulta se ejecute rápido, no usará los índices que he definido. EXPLICAR 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 entiende lo que el índice de usar, pero todavía tiene que recorrer todos 10 filas (o 100k en mi tabla real).

¿Cómo puedo obtener MySql para optimizar esta consulta correctamente? Incluyo un script de prueba debajo.

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

para optimizar las consultas conjunto anidado en MySQL, se debe crear un (R-Tree) Índice SPATIAL en las cajas 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; 

Lee este artículo en mi blog para más detalles:

• Adjacency list vs. nested sets: MySQL

Answer 2

Si no puede utilizar el índice espacial, entonces estos dos índices:

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

debe ser único. Eso ayudará mucho a la base de datos.

ALTER TABLE projects ADD INDEX lft (lft); 

No es necesario, es un duplicado de lftRgt.

Answer 3

Encontré esto mientras trataba de encontrar ayuda para indexar conjuntos anidados.

Aterrize con una solución diferente, que es voluminosa pero fácilmente indexable. Sin embargo, hará las actualizaciones aún más lentas. Sin embargo, lo estoy publicando aquí, ya que podría ayudar a otros.

Tenemos una tabla de categorías de productos, que puede tener subcategorías, etc. Esta información es bastante estática.

Configuré una tabla en el caché de las relaciones entre las categorías que contienen la categoría y una fila para cada categoría principal (incluida esta categoría en particular), junto con la diferencia en profundidad.

Cuando se realiza un cambio en la tabla de categorías reales, solo desencadenaré un procedimiento para reconstruir la tabla en caché.

Luego, cualquier cosa que esté comprobando la relación padre/hijo solo puede usar el caché para vincular directamente entre una categoría y todos sus hijos (o un hijo y todos sus padres).

La tabla de categoría real.

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 sencilla tabla de caché: -

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; 

El procedimiento: -

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 

Esto probablemente se podría mejorar de manera útil si la tabla es grande y comúnmente actualizada.