mils mils - 1 year ago 137
MySQL Question

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

I have the following self-join query:

FROM mytbl AS A
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:

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,
UNIQUE KEY id (id),
UNIQUE KEY rgt (rgt),
KEY idx_lft (lft),
KEY idx_rgt (rgt) ) ENGINE=InnoDB DEFAULT CHARSET=utf8


Answer Source

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:

FROM mytbl      AS A
LEFT JOIN mytbl AS B ON (A.lft BETWEEN B.lft AND B.rgt)
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

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download