EXPLAIN EXTENDED

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

Today, I'll expain how to move items in these lists.

To move an item in the linked list we need to relink it. If we move item A after item B, we need to update at most three rows:

1. A's parent is updated to B
2. A's child's parent is updated to A's parent
3. B's child parent is updated to A

B here may be a real row or a surrogate id of 0 which we use to designate the first row's parent.

Moving A after 0 means moving A to the top of the list.

Unfortunately we cannot rely on a single statement to perform these updates, because we have a UNIQUE INDEX on parent.

This is because MySQL does not allow deferred constraint checking. The update statement will fail as soon as the first row is updated to violate the UNIQUE constraint, despite the violation being fixed as soon as the last row is updated.

To work around this, we will do the following:

1. Cache the current parent's of the rows we need to update and lock these rows.
2. Assign NULL's to the parent's of these rows.
3. Update the parent's with the cached values.

What we do here is actually taking the three parent's out of the constraint and then reassigning them to the same rows in the different order. This guarantees that the constraint will never be violated.

The procedure that moves an item after a given target looks like this:

CREATE PROCEDURE prc_move_after(item INT, target INT)
MAIN: BEGIN
DECLARE itemchild INT;
DECLARE targetchild INT;
DECLARE itemparent INT;
IF item = target THEN
LEAVE MAIN;
END IF;
SELECT  (
SELECT  id
FROM    t_list
WHERE   parent = item
FOR UPDATE
),
(
SELECT  id
FROM    t_list
WHERE   parent = target
FOR UPDATE
),
(
SELECT  parent
FROM    t_list
WHERE   id = item
FOR UPDATE
)
INTO    itemchild, targetchild, itemparent;
IF itemparent = target THEN
LEAVE MAIN;
END IF;
UPDATE  t_list l
SET     l.parent = NULL
WHERE   l.id IN (item, itemchild, targetchild);
UPDATE
t_list l
SET     l.parent =
CASE
WHEN l.id = item THEN target
WHEN l.id = itemchild THEN itemparent
WHEN l.id = targetchild THEN item
END
WHERE   l.id IN (item, itemchild, targetchild);
END

This also handles the special cases:

• Moving an item after itself (senseless; no update performed)
• Moving an item after it's parent (nothing changes; no update performed)

To be continued.