Mysql – Queue Implementation with Custom Consistent Absolute Ordering

MySQLqueue

I need to create a schema for a queue. Elements in this queue will be processed in an order based on a column. However, this is not always the e.g. date_added column.

Users should be able to freely re-order items in the queue, thus setting a custom position – let's call that field position. Therefore, queue items that have a position >= to the new position I set for a specific item need to be re-ordered on each update.

I really want to avoid using a server-side script to manually go through each of the now outdated elements and updating their position.

Is there a way to do this automatically, and with relatively low resource usage? I'm sure people have implemented such a queue in MySQL before, but there don't seem to be relevant answers anywhere, although the task sounds trivial. Any ideas?

I know I shouldn't rely on the order the records are stored in. But I am maybe considering using ALTER TABLE ORDER BY. How bad is this really? And how useful is it in achieving my goal?

There's some PK, likely an auto-increment, or maybe the date_added with more precision. The version is InnoDB, MySQL >= 5.6.

The queue position can be changed an unlimited number of times. It should work without failure. The UI with HTML and JS is trivial: On any change of immediate hierarchy within a container, you just read the order of elements with a specific attribute. It's also pretty common. Possibly hundreds of items in the list.

By "outdated elements" I mean those that no longer have the position field set correctly, and need to be "reindexed". Naturally, something in MySQL would deal with that.

As for finished, I need those to be retrievable too, so they stay in the table, and are marked as done with a boolean field. There is another table that takes care of more complicated status transition, as it is not a part of what makes a queue.

Best Answer

(I'll compete with myself. Here's an Answer for a "large" number of items.)

Updating 1K rows is not very fast, due to saving rows in case of rollback. Incrementing/decrementing the sequence numbers (column seq) for a range of rows, then changing one the sequence in the one row that was moved. That's 3 UPDATEs -- one slow, one fast.

The UI would need to provide some way for the user to specify which item to move from some seq to a new seq.

A column in the table would contain the sequence number. seq would effectively be UNIQUE, but saying so might slow it down.

Suppose the UI tells the db that "Seq=222 needs to move to after seq=567. (after "0" for inserting at front.)

BEGIN;   -- need atomicity
-- Move item out of the way (assuming "0" is not otherwise used):
UPDATE t SET seq = 0 WHERE seq = 222;
-- Shift the items that need to move:
UPDATE t SET seq = seq - 1   -- "-" or "+" depending
    WHERE seq BETWEEN 222+1 AND 567;
-- move the item in question:
UPDATE t SET seq = 567 WHERE seq = 0;
COMMIT;

Moving the other direction needs a couple of changes.

Related Question