MySQL & nested set: slow JOIN (not using index)

Question

I have two tables:

settlements:

CREATE TABLE `localities` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(100) NOT NULL, `type` varchar(30) NOT NULL, `parent_id` int(11) DEFAULT NULL, `lft` int(11) DEFAULT NULL, `rgt` int(11) DEFAULT NULL, PRIMARY KEY (`id`), KEY `index_localities_on_parent_id_and_type` (`parent_id`,`type`), KEY `index_localities_on_name` (`name`), KEY `index_localities_on_lft_and_rgt` (`lft`,`rgt`) ) ENGINE=InnoDB; 

locatings:

 CREATE TABLE `locatings` ( `id` int(11) NOT NULL AUTO_INCREMENT, `localizable_id` int(11) DEFAULT NULL, `localizable_type` varchar(255) DEFAULT NULL, `locality_id` int(11) NOT NULL, `category` varchar(50) DEFAULT NULL, PRIMARY KEY (`id`), KEY `index_locatings_on_locality_id` (`locality_id`), KEY `localizable_and_category_index` (`localizable_type`,`localizable_id`,`category`), KEY `index_locatings_on_category` (`category`) ) ENGINE=InnoDB; 

Location table

implemented as a nested set.

Now, when the user belongs to any locality (through some localization), he also belongs to all his ancestors (higher levels). I need a query that selects all the points at which all users enter the view.

Here is my attempt:

 select distinct lca.*, lt.localizable_type, lt.localizable_id from locatings lt join localities lc on lc.id = lt.locality_id left join localities lca on (lca.lft <= lc.lft and lca.rgt >= lc.rgt) 

The problem is that it takes too much time to complete.

I consulted with EXPLAIN:

 +----+-------------+-------+--------+---------------------------------+---------+---------+----------------------------------+-------+----------+-----------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+--------+---------------------------------+---------+---------+----------------------------------+-------+----------+-----------------+ | 1 | SIMPLE | lt | ALL | index_locatings_on_locality_id | NULL | NULL | NULL | 4926 | 100.00 | Using temporary | | 1 | SIMPLE | lc | eq_ref | PRIMARY | PRIMARY | 4 | bzzik_development.lt.locality_id | 1 | 100.00 | | | 1 | SIMPLE | lca | ALL | index_localities_on_lft_and_rgt | NULL | NULL | NULL | 11439 | 100.00 | | +----+-------------+-------+--------+---------------------------------+---------+---------+----------------------------------+-------+----------+-----------------+ 3 rows in set, 1 warning (0.00 sec) 

The last connection does not explicitly use the lft, rgt index, as I expect. I'm desperate.

UPDATE: After adding a condition as suggested by @cairnz, the request takes too much time to process.

UPDATE 2: column names instead of asterisk

Updated request:

 SELECT DISTINCT lca.id, lt.`localizable_id`, lt.`localizable_type` FROM locatings lt FORCE INDEX(index_locatings_on_category) JOIN localities lc ON lc.id = lt.locality_id INNER JOIN localities lca ON lca.lft <= lc.lft AND lca.rgt >= lc.rgt WHERE lt.`category` != "Unknown"; 

Updated EXAPLAIN:

 +----+-------------+-------+--------+-----------------------------------------+-----------------------------+---------+---------------------------------+-------+----------+-------------------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+--------+-----------------------------------------+-----------------------------+---------+---------------------------------+-------+----------+-------------------------------------------------+ | 1 | SIMPLE | lt | range | index_locatings_on_category | index_locatings_on_category | 153 | NULL | 2545 | 100.00 | Using where; Using temporary | | 1 | SIMPLE | lc | eq_ref | PRIMARY,index_localities_on_lft_and_rgt | PRIMARY | 4 | bzzik_production.lt.locality_id | 1 | 100.00 | | | 1 | SIMPLE | lca | ALL | index_localities_on_lft_and_rgt | NULL | NULL | NULL | 11570 | 100.00 | Range checked for each record (index map: 0x10) | +----+-------------+-------+--------+-----------------------------------------+-----------------------------+---------+---------------------------------+-------+----------+-------------------------------------------------+ 

Any help was appreciated.

Answer 1

And, it only occurred to me.

Since you are querying everything in the table, mysql decides to use a full table scan instead, as it considers it more efficient.

To get some use of the key, add some filters to limit the search for each row in all tables anyway.

Response update:

The second request does not make sense. You remain attached to lca, but you have a filter in it, this negates the left join. You are also looking for data in the last step of the query, that is, you will need to look at all lt, lc and lca to find your data. In addition, you do not have an index with a left column of “type” in places, so you still need a full table scan to find your data.

If you had data samples and an example of what you are trying to achieve, it might be easier to help.

Answer 2

try experimenting with a boost index - http://dev.mysql.com/doc/refman/5.1/en/index-hints.html , maybe this is just an optimizer problem.

Answer 3

It looks like you want your parents to get a single result.

According to the person who is assigned the definition of Nested Sets in SQL, Joe Celko at http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html "This model is a natural way to show an explosion of parts because the final assembly is made from physically nested assemblies that are broken into separate parts. "

In other words, nested sets are used to effectively filter children into an arbitrary number of independent levels within the same collection. You have two tables, but I don’t see where the properties of the "locatings" set cannot be de-normalized in the "location"?

If the terrain table has a geometry column, can I find one terrain from "localization" and then select one table with one filter: parent.lft <= row.left AND parent.rgt> = row.rgt?

UPDATED

In this answer, https://stackoverflow.com/a/312947/ is an example from http://explainextended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql/ where the following example returns all the ancestors to arbitrary depth 100,000:

 SELECT hp.id, hp.parent, hp.lft, hp.rgt, hp.data FROM ( SELECT @r AS _id, @level := @level + 1 AS level, ( SELECT @r := NULLIF(parent, 0) FROM t_hierarchy hn WHERE id = _id ) FROM ( SELECT @r := 1000000, @level := 0 ) vars, t_hierarchy hc WHERE @r IS NOT NULL ) hc JOIN t_hierarchy hp ON hp.id = hc._id ORDER BY level DESC