Mysql: оптимизация поиска супер-узла в дереве вложенных множеств - PullRequest
Новая
       11

Mysql: оптимизация поиска супер-узла в дереве вложенных множеств

8 голосов
/ 16 ноября 2009

У меня есть иерархические данные в модели вложенного набора (таблица: проекты):

Мой стол (проекты): 

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

Довольно напечатано: 

 1
  2
  3
 4
  5
 6
 7

Чтобы найти ближайший супер узел узла 3 (зная его lft-значение), я могу сделать 

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

Что дает мне список проектов на пути к узлу 3. Затем, группируя и находя МАКС (projects.lft) результатов, я получаю ближайший супер узел. Однако я не могу заставить этот запрос выполняться быстро, он не будет использовать индексы, которые я определил. ОБЪЯСНЕНИЕ говорит: 

+----+-------------+----------+-------+----------------+----------+---------+------+------+--------------------------+
| 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 понимает, какой индекс использовать, но все еще должен пройти через все 10 строк (или 100 КБ в моей реальной таблице).

Как я могу заставить MySql правильно оптимизировать этот запрос? Я включил тестовый скрипт ниже. 

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

Ответы [ 3 ]

11 голосов
/ 16 ноября 2009

Чтобы оптимизировать запросы вложенных множеств в MySQL, вы должны создать индекс SPATIAL (R-Tree) для полей набора: 

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;

См. Эту статью в моем блоге для более подробной информации:

1 голос
/ 17 марта 2011

Если вы не можете использовать пространственный индекс, тогда эти два индекса: 

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

Должно быть уникальным. Это очень поможет базе данных. 

ALTER TABLE projects ADD INDEX lft (lft);

Не обязательно - это дубликат lftRgt.

0 голосов
/ 17 июня 2016

С этим сталкивался при попытке найти справку по индексации для вложенных множеств.

Я нашел другое решение, громоздкое, но легко индексируемое. Однако это сделает обновления еще медленнее. Однако я публикую это здесь, поскольку это может помочь другим.

У нас есть таблица категорий товаров, которая может иметь подкатегории и т. Д. Эти данные довольно статичны.

Я создал таблицу, в которой кешируются отношения между категориями, содержащими категорию, и строкой для каждой родительской категории (включая данную конкретную категорию), а также разницу в глубине.

Когда вносятся изменения в таблицу фактических категорий, я просто запускаю процедуру для восстановления кэшированной таблицы.

Тогда все, что проверяет отношения родитель / потомок, может просто использовать кеш для прямой связи между категорией и всеми ее дочерними элементами (или потомком и всеми ее родителями).

Таблица фактических категорий. 

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 ;

Простая кеш-таблица: - 

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;

Процедура: - 

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

Возможно, это будет полезно улучшить, если таблица большая и обычно обновляется.

...