Prevent duplicates in MySql without using unique constraint

Question

I have a rules table consist of a column called priority, that must be gapless, incremental and unique.
A user must be able to re-order priority of the rules. For example, if there are 10 rules for a user and she moves the last rule to the 5th place, all of the other records between must get updated.
To prevent race condition during updates, I can use a select ... for update lock. But I can't find a way to guarantee the uniqueness of priority during inserts.
Firstly I wanted to use a deferred unique constraint, but figured out that MySql does not support this feature as Postgres do.
Then I thought about using a trigger on before insert, to calculate the priority, but I found that duplications still can show up.
What must I do? Is there any way to create a unique check that only works during inserts not updates?

Answer 1

Using SELECT ... FOR UPDATE on repeatable read (which is the default isolation level in MySql) may lead to gap locks and poor performance.

If the list you're maintaining has limited items (e.g. ~100 rules for each user), I suggest to add a column named version and hold a unique constraint/index on <priority, version> and then try to mimic eventual consistency. Here's an example:

CREATE TABLE rules (
    id INT UNSIGNED NOT NULL AUTO_INCREMENT,
    priority INT NOT NULL,
    version INT NOT NULL,
    user_id INT NOT NULL, -- foreign key of user
    PRIMARY KEY (id),
    UNIQUE(priority, version)
) ENGINE=InnoDB;

INSERT INTO rules (priority, version, user_id) VALUES (5,1,0),(4,1,0),(3,1,0),(2,1,0),(1,1,0);

To bring up the 4th row (with priority = 2) to the 2nd place (which has priority = 4), you should:

1. Set the priority of the 4th row to 4 and increment version
2. Decrement priority and increment version of the rules with priority between 3 and 4
3. Increment version of the remaining rules

BEGIN;

SELECT GROUP_CONCAT(DISTINCT CONCAT('(', priority, ',', version, ')') ORDER BY id) FROM rules WHERE user_id = 0;
-- (5,1),(4,1),(3,1),(2,1),(1,1)

UPDATE rules SET version = version + 1, priority = priority - 1 WHERE user_id = 0 AND version = 1 AND priority BETWEEN 3 AND 4;
-- (5,1),(3,2),(2,2),(2,1),(1,1)

UPDATE rules SET version = version + 1, priority = 4 WHERE user_id = 0 AND version = 1 AND priority = 2;
-- (5,1),(3,2),(2,2),(4,2),(1,1)

UPDATE rules SET version = version + 1 WHERE user_id = 0 AND version = 1 AND priority NOT BETWEEN 2 AND 4;
-- (5,2),(3,2),(2,2),(4,2),(1,2)

COMMIT;

This way, all of the rows will eventually have the same version and there will be no duplicate priorities (in that version).

Answer 2

Here's a complete test case, annotated:

CREATE TABLE t_rearr (
    id INT UNSIGNED NOT NULL AUTO_INCREMENT,
    priority INT NOT NULL,
    PRIMARY KEY (id),
    UNIQUE(priority)
) ENGINE=InnoDB;

INSERT INTO t_rearr (priority) VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10);


BEGIN;

SELECT GROUP_CONCAT(id ORDER BY priority) FROM t_rearr FOR UPDATE;  
-- Expect 1,2,3,4,5,6,7,8,9,10  
-- Note the FOR UPDATE  

-- 3 steps to swap:
-- First, move out of way (this assumes 0 is not a valid priority)
UPDATE t_rearr SET priority =  0 WHERE priority =  5;

UPDATE t_rearr SET priority =  5 WHERE priority = 10;

UPDATE t_rearr SET priority = 10 WHERE priority =  0;

COMMIT;

SELECT GROUP_CONCAT(id ORDER BY priority) FROM t_rearr;
# Expect 1,2,3,4,10,6,7,8,9,5