EXPLAIN EXTENDED

How to create fast database queries

Sorting lists

with 7 comments

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

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
id parent
1 0
2 3
3 4
4 1
4 rows fetched in 0.0002s (0.0016s)

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
id
1
4
3
2
4 rows fetched in 0.0001s (0.0013s)

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
id select_type table type possible_keys key key_len ref rows filtered Extra
1 PRIMARY <derived3> system 1 100.00
1 PRIMARY t_list index PRIMARY 4 4 100.00 Using index
3 DERIVED No tables used
2 UNCACHEABLE SUBQUERY t_list index ix_list_parent 4 4 100.00 Using where; Using index
4 rows fetched in 0.0022s (0.0029s)

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
_parent id
0 1
1 4
4 3
3 2
4 rows fetched in 0.0012s (0.0012s)

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
id select_type table type possible_keys key key_len ref rows filtered Extra
1 PRIMARY <derived3> system 1 100.00
1 PRIMARY t_list index PRIMARY 4 4 100.00 Using index
3 DERIVED No tables used
2 DEPENDENT SUBQUERY t_list eq_ref ix_list_parent ix_list_parent 4 func 1 100.00 Using where; Using index
4 rows fetched in 0.0020s (0.0030s)

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

To be continued.

Written by Quassnoi

March 25th, 2009 at 11:00 pm

Posted in MySQL

7 Responses to 'Sorting lists'

Subscribe to comments with RSS

  1. Hello,
    It looks good. I did not go much deep into it yet and I have a question. I like to SELECT also by reversed direction. What comes to my mind is to build also reverse linking (so ‘who is my child’). Is this right angle of view or there is something easier for doing that?
    Thanks. Pedro.

    Pedro

    10 Oct 12 at 00:10

  2. @Pedro: yes, that would be a double-linked list. Relinking it would be a little harder, however, since you would need to update 5 items when moving (moved item, old parent, old child, new parent, new child).

    Quassnoi

    10 Oct 12 at 00:13

  3. This looks very useful. What I don’t understand is how to set which record/node to start from? Like if I wanted to start from id 3 in your example. And how does it know when it hits the end of the list and should stop? I’ve tried it out and it just runs forever (likely due to improper use). Thanks!

    Ben

    8 Jul 13 at 08:47

  4. Ben

    10 Jul 13 at 02:57

  5. I’m getting an error with these queries: “Reference ‘id’ not supported (forward reference in item list)”.

    geoidesic

    12 Dec 14 at 18:52

  6. I also get “Sub-query returns more than one row”

    geoidesic

    12 Dec 14 at 18:55

  7. @geoidesic: please create a setup on http://sqlfiddle.com, fill it with your data and post the link.

    Quassnoi

    12 Dec 14 at 20:42

Leave a Reply