Mysql: Optimisation de la recherche super nœud dans l'arbre de jeu imbriqué

Question

I ai données hiérarchiques dans un modèle de série emboîtée (tableau: projets):

Mon tableau (projets):

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

Jolie imprimé:

 1
  2
  3
 4
  5
 6
 7

Pour trouver le super nœud du nœud 3 (connaître sa valeur LFT) le plus proche, je peux faire

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

Ce qui me donne une liste des projets dans le chemin vers le bas au noeud 3. Ensuite, en groupant et trouver MAX (projects.lft) des résultats, je reçois le super nœud le plus proche. Cependant, je ne peux pas sembler obtenir cette requête pour courir vite, il utilise l'habitude les indices que j'ai défini. EXPLIQUER dit:

+----+-------------+----------+-------+----------------+----------+---------+------+------+--------------------------+
| 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 comprend ce que l'indice à utiliser, mais doit encore boucler à travers toutes les 10 lignes (ou 100k dans ma table réelle).

Comment puis-je obtenir MySql pour optimiser cette requête correctement? J'include un script de test sous.

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

Pour optimiser les requêtes imbriquées ensemble dans MySQL, vous devez créer un index de SPATIAL (de R-Tree) sur les boîtes de 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;

Voir cet article dans mon blog pour plus de détails:

• Liste de contiguïté par rapport à des ensembles imbriqués : MySQL

Answer 2

Si vous ne pouvez pas utiliser l'index spatial, ces deux indices:

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

doit être unique. Cela aidera à la base de données beaucoup.

ALTER TABLE projects ADD INDEX lft (lft);

est pas nécessaire -. Il est un double de lftRgt

Answer 3

Nous sommes tombés sur ce tout en essayant de trouver de l'aide sur l'indexation des ensembles imbriqués.

J'atterris avec une autre solution, qui est volumineux mais facilement entièrement indexés. Cependant, il fera des mises à jour encore plus lent. Cependant, je suis annonce ici car il pourrait aider les autres.

Nous avons une table de catégories de produits, qui peuvent avoir des sous-catégories, etc. Ces données sont tout à fait statique.

configurer une table mise en mémoire cache les relations entre les catégories contenant la catégorie et une ligne pour chaque catégorie mère (y compris cette catégorie particulière), ainsi que la différence de profondeur.

Lorsqu'une modification est apportée à la table de catégorie réelle je déclenche juste une procédure pour reconstruire la table en cache.

Ensuite, tout ce qui est vérification de la relation parent / enfant peut simplement utiliser le cache pour relier directement entre une catégorie et tous ses enfants (ou un enfant et tous ses parents).

Le tableau de la catégorie actuelle.

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 table simple 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 procédure: -

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

Cela pourrait probablement être utilement améliorée si la table est grande et fréquemment mis à jour.