MySQL:优化在嵌套集树中查找超级节点 [英] Mysql: Optimizing finding super node in nested set tree
问题描述
我在嵌套集合模型中有分层数据(表:项目):
I have hierarchical data in a nested set model (table:projects):
我的桌子(项目):
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值),我可以做
To find the nearest super node of node 3 (knowing its lft value), i can do
explain
SELECT projects.*
FROM projects
WHERE 4 BETWEEN projects.lft AND projects.rgt
哪一个给了我直到节点3的路径中的项目列表,然后通过分组并找到结果的MAX(projects.lft),我得到了最近的超级节点.但是,我似乎无法使该查询快速运行,它不会使用我定义的索引.解释说:
Which gives me a list of the projects in the path down to node 3. Then by grouping and finding MAX(projects.lft) of the results, i get the nearest super node. However, I cannot seem to get this query to run fast, it wont use the indexes i've defined. EXPLAIN says:
+----+-------------+----------+-------+----------------+----------+---------+------+------+--------------------------+
| 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 understands what index to use, but still has to loop through all 10 rows (or 100k in my actual table).
如何获取MySql以正确优化此查询?我在下面添加了测试脚本.
How can i get MySql to optimize this query properly? I include a test script beneath.
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
推荐答案
要优化MySQL
中的嵌套集查询,应在集合框上创建SPATIAL
(R-Tree
)索引:
To optimize nested set queries in MySQL
, you should create a SPATIAL
(R-Tree
) index on the set boxes:
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;
有关更多详细信息,请参见我的博客中的这篇文章:
See this article in my blog for more detail:
这篇关于MySQL:优化在嵌套集树中查找超级节点的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!