Queue Implementation with Custom Consistent Absolute Ordering

Question

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.

Answer 1

(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.

Answer 2

So, here's my answer that came out of a very productive discussion with @RickJames. Thanks a lot!

So, create the queue table like this. Please note that it supports multiple queues at once, and some other features. Also, the position can actually be added optionally as another table, which could be better if you're into modularity (I know I am).

CREATE TABLE `queue_jobs` (
    `id` int unsigned PRIMARY KEY AUTO_INCREMENT,
    `queue_name` varchar(255),
    `added_on` datetime DEFAULT CURRENT_TIMESTAMP,
    `processed_on` datetime,
    `data` text,
    `position` int unsigned
);

Every time I insert a record, I just assign to it the position that is the current greatest position value +1.

INSERT INTO `queue_jobs` (
  `id`,
  `queue_name`,
  `added_on`,
  `processed_on`,
  `data`,
  `position`)
VALUES (
  NULL,
  'people',
  NULL,
  NULL,
  'Richard',
  ( -- This is the subquery that is responsible for getting the next available position
    SELECT MAX(`position`)
    FROM `queue_jobs` `qj`
    WHERE `queue_name` = 'people'
    LIMIT 1)
  + 1);

Every time I move a record, I do it in 2 steps:

1. Shift all jobs, whose position is >= the target position of the job I want to move, by 1.
2. Change the position of the job I want to move to what is desired, as that position is now guaranteed to be free.

BEGIN;
-- 6: Move queue item up
UPDATE `queue_jobs` SET `position` = `position` + 1
WHERE `position` >= 2; -- 2 is the new position we want out item to be at
-- 7: Assign new position to target item
UPDATE `queue_jobs` SET `position` = 2
WHERE `id` = 3;
COMMIT;

Note: This cannot be done if the position field is unique, because a position of a shifted job may conflict with the current position of the job I want to move.

This works for moving a job in both directions. It allows for over 4 billion insertions or movements before the value starts overflowing. In that case, something like BIGINT UNSIGNED should be used which allows up to 18 quintillion. Also, the position values of this solution will not be very dense. The density can be improved by perhaps re-assigning position once in a while on a schedule, by using variables, i.e. something like this.

Answer 3

For a "small" set of items, here is a design for both the UI and the sorting. It centers around a commalist of ids.

The UI would list all the items. Let's say it is practical to show the items horizontally like wrapped text. The items could be represented as names, task-numbers, thumbnails, whatever.

Now have some JavaScript to allow the user to drag & drop one item into a space between two other items (or off either end). The JS would immediately:

1. Rearrange its internal array
2. Redisplay the list
3. Build a commalist if ids in a single string
4. Use AJAX to send that commalist to the server.

The MySQL server:

1. store that single string in some place.
2. Use that string to provide ordering: ORDER BY FIND_IN_SET(item, commalist)

Caveat: If two users are making changes to the list at the "same time", one person's change will be lost.

If the set is too big for that solution, I'll scratch my head some more. But be gentle, I am going bald.