EXPLAIN EXTENDED

This is article 1 of 6 on linked lists in MySQL:

• Sorting lists
• Sorting lists: moving items
• Sorting lists: adding items
• Sorting lists: deleting items
• Sorting lists: moving blocks
• Sorting lists: deleting blocks

From Stack Overflow:

I have an app which has tasks in it and you can reorder them.

Now I was wondering how to best store them. Should I have a column for the order number and recalculate all of them everytime I change one?

Please tell me a version which doesn't require me to update all order numbers since that is very time consuming (from the execution's point of view).

It's probably better to keep it in a linked list:

SELECT  *
FROM    t_list
ORDER BY
        id

To return the ordered list, we query it like this:

SELECT  @r := (
        SELECT  id
        FROM    t_list
        WHERE   parent = @r
        ) AS id
FROM    (
        SELECT  @r := 0
        ) vars,
        t_list

Note that if we look into the query execution plan, we will note, that the index on parent is not used for value lookup:

EXPLAIN EXTENDED
SELECT  @r := (
        SELECT  id
        FROM    t_list
        WHERE   parent = @r
        ) AS id
FROM    (
        SELECT  @r := 0
        ) vars,
        t_list

Note there is no ref in the UNCACHEABLE SUBQUERY.

This is because MySQL does not treat a variable as a constant.

To work around this, we can select the variable earlier in the SELECT clause, and just refer to the field it produces:

SELECT  @r AS _parent,
        @r := (
        SELECT  id
        FROM    t_list
        WHERE   parent = _parent
        ) AS id
FROM    (
        SELECT  @r := 0
        ) vars,
        t_list

The plan now looks like this:

EXPLAIN EXTENDED
SELECT  @r AS _parent,
        @r := (
        SELECT  id
        FROM    t_list
        WHERE   parent = _parent
        ) AS id
FROM    (
        SELECT  @r := 0
        ) vars,
        t_list

The subquery became a DEPENDENT SUBQUERY now, and the index is being used as it should.

To be continued.