EXPLAIN EXTENDED

This is article 5 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

Now, let's discuss the mass updates.

In some user interfaces it is needed sometimes to select a whole block of items and move it towards the top or the bottom of the list all at once.

This may be useful to manage MP3 playlists, photo stacks, etc.

With linked lists, it's quite simple. Just like in case of moving a single item, we need to update only three rows.

Moving the items in block, though, requires some more checking:

1. The first and the last id's of the block must exists in the table
2. The last must be the first's descendant
3. The block should not contain the target

The procedure that moves the block looks like this:

CREATE PROCEDURE prc_move_block(first INT, last INT, target INT)
MAIN: BEGIN
        DECLARE lastchild INT;
        DECLARE targetchild INT;
        DECLARE firstparent INT;
        DECLARE _loop INT;
        IF first IS NULL OR last IS NULL OR target IS NULL OR first = target OR last = target THEN
                LEAVE MAIN;
        END IF;
        SELECT  (
                SELECT  id
                FROM    (
                        SELECT  @r AS _current,
                                @r :=
                                (
                                SELECT  id
                                FROM    t_list
                                WHERE   parent = _current
                                ) AS id
                        FROM    (
                                SELECT  @r := parent
                                FROM    t_list
                                WHERE   id = first
                                ) vars,
                                t_list
                        WHERE   @r <> last
                        ) q
                WHERE   id IN (target, last)
                LIMIT 1
                )
        INTO    _loop;
        IF COALESCE(_loop, target) = target THEN
                LEAVE MAIN;
        END IF;
        SELECT  (
                SELECT  id
                FROM    t_list
                WHERE   parent = last
                FOR UPDATE
                ),
                (
                SELECT  id
                FROM    t_list
                WHERE   parent = target
                FOR UPDATE
                ),
                (
                SELECT  parent
                FROM    t_list
                WHERE   id = first
                FOR UPDATE
                )
        INTO    lastchild, targetchild, firstparent;
        IF firstparent = target THEN
                LEAVE MAIN;
        END IF;
        UPDATE  t_list l
        SET     l.parent = NULL
        WHERE   l.id IN (first, lastchild, targetchild);
        UPDATE  t_list l
        SET     l.parent =
                CASE
                        WHEN l.id = first THEN target
                        WHEN l.id = lastchild THEN firstparent
                        WHEN l.id = targetchild THEN last
                END
        WHERE   l.id IN (first, lastchild, targetchild);
END
$$

CREATE PROCEDURE prc_move_after(item INT, target INT)
BEGIN
        CALL prc_move_block(item, item, target);
END
$$

As you can see, I rewrote the old procedure that moved a single row and made it just a wrapper for the new procedure.

All the checks described above are performed in a single SELECT query.

Let's look closer into this query:

SELECT  (
        SELECT  id
        FROM    (
                SELECT  @r AS _current,
                        @r :=
                        (
                        SELECT  id
                        FROM    t_list
                        WHERE   parent = _current
                        ) AS id
                FROM    (
                        SELECT  @r := parent
                        FROM    t_list
                        WHERE   id = first
                        ) vars,
                        t_list
                WHERE   @r <> last
                ) q
        WHERE   id IN (target, last)
        LIMIT 1
        )
INTO    _loop;
IF COALESCE(_loop, target) = target THEN
        LEAVE MAIN;
END IF;

The innermost subquery (aliased as q) selects all the block's rows, starting with the first's parent and ending with last. This also ensures that first exists in the table, because the subquery will return nothing if it does not.

The outermost subquery selects a single id from resultset above. This can be target, last, or no row at all.

This subquery is returned as a field of a single-row SELECT, and the returned id (or NULL if no id is returned) is assigned to the local variable called _loop.

• If target is returned, then target is somewhere between first and last, and is, therefore, a part of the block. This violates the conditions above.
• If NULL is returned then no rows were selected at all. This means that last was not encountered while scanning the first's descendant. This can happen in each of these cases:
  • last does not exist in the table
  • last is not a first's descendant

  In both cases, such a block can not be considered valid.

• Finally, if last is returned, the both first and last exist, last is a first's descendant, and target is not between them. This means the block is valid.

Therefore, we should exit the procedure if target or NULL were returned.

Relinking part did not change much, it uses the same approaches as in case of moving a single row.

Let's create a sample list ordered by id's:

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

, and move the rows with id's from 5 to 10 after the row with id of 2:

CALL prc_move_block(5, 10, 2)

After we select the list again, we see:

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

The whole block moved with only a 3-row UPDATE.

To be continued.