EXPLAIN EXTENDED

How to create fast database queries

Sorting lists: adding items

Comments enabled. I *really* need your comment

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

In this article I'll cover inserting items into the linked list.

This is quite a simple task, but has some issues we will need to handle.

When we insert a new item A after an existing item B in the linked list, we need to do the following:

  1. Insert the new item and set its parent to B
  2. Update the B's child's parent to A

This seems OK, but what if we want the id of A to be autogenerated?

We cannot insert the new first as it would violate the UNIQUE CONSTRAINT on parent for the B's child, and we cannot update B's child first because we don't know the A's id yet.

That's why we need to do it in three steps:

  1. Insert the new item and set its parent to NULL
  2. Update the parent's of both the new item and the B's child's to appropriate values

Here is the procedure to do this:

CREATE PROCEDURE prc_insert_after (item INT, target INT)
BEGIN
        INSERT
        INTO    t_list (id)
        VALUES  (item);
        SET item = COALESCE(item, LAST_INSERT_ID());
        UPDATE  t_list lo
        JOIN    (
                SELECT  id AS _id, item AS _parent
                FROM    t_list lo
                WHERE   lo.parent = target
                UNION ALL
                SELECT  item, target
                ) q
        ON      id = _id
        SET     parent = _parent;
END

To be continued.

Written by Quassnoi

March 27th, 2009 at 11:00 pm

Posted in MySQL

Leave a Reply