一尘不染

MySQL:优化在嵌套集树中查找超级节点

sql

我在嵌套集合模型(表:项目)中具有分层数据:

我的桌子(项目):

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的路径中的项目列表。然后通过分组并找到结果的MAX(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行(或者在我的实际表中为100k)。

我如何获得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

阅读 139

收藏
2021-03-17

共1个答案

一尘不染

要优化中的嵌套集合查询MySQL,您应该在集合框上创建SPATIALR-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;

有关更多详细信息,请参见我的博客中的这篇文章:

2021-03-17