How to create fast database queries

Sorting lists: moving items

Comments enabled. I *really* need your comment

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

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)
        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);
                t_list l
        SET     l.parent =
                        WHEN l.id = item THEN target
                        WHEN l.id = itemchild THEN itemparent
                        WHEN l.id = targetchild THEN item
        WHERE   l.id IN (item, itemchild, targetchild);

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.

Written by Quassnoi

March 26th, 2009 at 11:00 pm

Posted in MySQL

Leave a Reply