mils mils - 3 months ago 23
MySQL Question

MySql - Self Join - Full Table Scan (Cannot Scan Index)

I have the following self-join query:

SELECT A.id
FROM mytbl AS A
LEFT JOIN mytbl AS B
ON (A.lft BETWEEN B.lft AND B.rgt)


The query is quite slow, and after looking at the execution plan the cause appears to be a full table scan in the JOIN. The table has only 500 rows, and suspecting this to be the issue I increased it to 100,000 rows in order to see if it made a difference to the optimizer's selection.
It did not, with 100k rows it was still doing a full table scan.

My next step was to try and force indexes with the following query, but the same situation arises, a full table scan:

SELECT A.id
FROM categories_nested_set AS A
LEFT JOIN categories_nested_set AS B
FORCE INDEX (idx_lft, idx_rgt)
ON (A.lft BETWEEN B.lft AND B.rgt)


Execution plan for full table scan query :/

All columns (id, lft, rgt) are integers, all are indexed.

Why is MySql doing a full table scan here?

How can I change my query to use indexes instead of a full table scan?

CREATE TABLE mytbl ( lft int(11) NOT NULL DEFAULT '0',
rgt int(11) DEFAULT NULL,
id int(11) DEFAULT NULL,
category varchar(128) DEFAULT NULL,
PRIMARY KEY (lft),
UNIQUE KEY id (id),
UNIQUE KEY rgt (rgt),
KEY idx_lft (lft),
KEY idx_rgt (rgt) ) ENGINE=InnoDB DEFAULT CHARSET=utf8


Thanks

Answer

The following SO question is critical to the solution, as there is very little information on the combination of adjacency lists and indices:

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

It appears that adding a basic comparison condition triggers the use of an index, like so:

SELECT A.id
FROM mytbl      AS A
LEFT JOIN mytbl AS B ON (A.lft BETWEEN B.lft AND B.rgt)
-- THE FOLLOWING DUMMY CONDITIONS TRIGGER INDEX
WHERE A.lft > 0
AND B.lft > 0
AND B.rgt > 0

And no more table scans.

EDIT: Comparison of EXPLAIN function between fixed and unfixed version of the query: EXPLAIN function results, top is fixed, bottom is not

Comments