Using unique index to enforce strict order numbers (that are picked by users)

Using unique index to enforce strict order numbers (that are picked by users)

Can I enforce strict user-editable order numbers, either using a unique constraint or otherwise, in a way that enables my website users to reorder a list of n entries using at most n database writes?

So I have a table:

SET NOCOUNT OFF;

CREATE TABLE UserOrderableThing
(
    Id INT NOT NULL IDENTITY (1, 1) CONSTRAINT PK_UserOrderableThing_Id PRIMARY KEY CLUSTERED,
    ParentId INT NOT NULL, --foreign key to other table
    OrderNumber INT NOT NULL,
    Inactive BIT NOT NULL CONSTRAINT DF_UserOrderableThing_Inactive DEFAULT(CAST(0 AS BIT)),
    --other columns
    CONSTRAINT CH_UserOrderableThing_OrderNumber CHECK (OrderNumber > 0)    
);

INSERT INTO UserOrderableThing (ParentId, OrderNumber) VALUES (1, 1);
INSERT INTO UserOrderableThing (ParentId, OrderNumber) VALUES (1, 2);
INSERT INTO UserOrderableThing (ParentId, OrderNumber) VALUES (1, 3);
INSERT INTO UserOrderableThing (ParentId, OrderNumber) VALUES (2, 1);
INSERT INTO UserOrderableThing (ParentId, OrderNumber) VALUES (2, 2);

This represents things in a UI that my users can create and reorder to their liking, for example by dragging and dropping them into a list. For any non-empty list of things, there should be a thing marked as first, all the way down to a thing marked as nth. I would like to (partially) enforce this strict ordering from 1 to n by using a unique index:

CREATE UNIQUE NONCLUSTERED INDEX UQ_UserOrderableThing_ParentId_OrderNumber
ON UserOrderableThing
(ParentId, OrderNumber)
WHERE Inactive = CAST(0 AS BIT)
;
--INSERT INTO UserOrderableThing (ParentId, OrderNumber) VALUES (1, 3);
--above line would throw an error, because we already used order number 3 for parent 1 earlier

It's true that this does not prevent the order numbers from being non-contiguous:

INSERT INTO UserOrderableThing (ParentId, OrderNumber) VALUES (1, 999) --works fine

But this is not a problem. The app code handles non-contiguous orderings correctly.

The problem is that my users may well want to reorder these things later, but trying to reorder these rows slams into errors raised by the index. I'll try to switch around parent 1's first two entries:

UPDATE UserOrderableThing SET OrderNumber = 2 WHERE Id = 1;
--this raises an error because parent 1 would have two entries with order number 2
UPDATE UserOrderableThing SET OrderNumber = 1 WHERE Id = 2;
--depending on app code, either this never gets executed, or it also raises an error because parent 1 would have two entries with order number 1

I know that running those two updates would yield a valid ordering at the end, but the unique constraint is checked upon every insert & update, and the intermediate ordering is invalid.

I can see three approaches to solve this problem, none of which I like:

  1. Remove the unique index. The app code can probably enforce the strict ordering correctly. But it would be nice if the database could provide an extra level of validation.

  2. Write careful code that prevents the duplicates from appearing in the intermediate stages. I know that these lists will never get close to having 1,000 entries (enforced by app code). So I can increase their order numbers by that much to prevent the duplication from appearing:

UPDATE UserOrderableThing SET OrderNumber = 1001 WHERE Id = 1;
UPDATE UserOrderableThing SET OrderNumber = 1002 WHERE Id = 2;
UPDATE UserOrderableThing SET OrderNumber = 2 WHERE Id = 1;
UPDATE UserOrderableThing SET OrderNumber = 1 WHERE Id = 2;
--no error

Obviously, this is not very practical. I'm executing extra writes just to dodge index problems. In higher-throughput scenarios, it might not be possible to come up with a hard number that's high enough such that the sum of it and an order number definitely won't clash with a real order number, and which also won't cause an integer overflow. (I could switch out the INT for BIGINT to handle those scenarios, but that depends on whether or not the server can handle 64-bit arithmetic. Plus, I'd just be pushing the problem further along the number line, rather than evading the problem entirely.)

I know that I could yank the rows out of the index first:

UPDATE UserOrderableThing SET Inactive = CAST(1 AS BIT) WHERE Id IN (1, 2);
UPDATE UserOrderableThing SET OrderNumber = 2, Inactive = CAST(0 AS BIT) WHERE Id = 1;
UPDATE UserOrderableThing SET OrderNumber = 1, Inactive = CAST(0 AS BIT) WHERE Id = 2;

This still involves writing data to a row 4 times, and hence doesn't improve anything. That IN clause reduces the number of UPDATE statements, but not the number of rows affected. We won't even discuss the workaround of preliminarily changing the parent ID during the write, because the same thing still happens.

I know that executing the UPDATES in a better order can reduce the number of writes:

UPDATE UserOrderableThing SET OrderNumber = 1001 WHERE Id = 1;
UPDATE UserOrderableThing SET OrderNumber = 1 WHERE Id = 2;
UPDATE UserOrderableThing SET OrderNumber = 2 WHERE Id = 1;

But this still requires 3 writes to update 2 rows. I want to do this in n writes for n updated rows. And identifying the correct order in which to execute the updates to minimise the number of writes is non-trivial.

  1. Disable the constraint during multi-write operations, then re-enable the constraint when I'm finished updating all rows. I like this option the least, since it means giving DDL permissions to the process that handles our website's database stuff, which is a security problem.

Is there some 4th approach that I'm missing? Can I enforce strict user-editable order numbers, either using a unique constraint or otherwise, that avoids this index issue entirely, enabling my users to reorder a list of n entries using at most n writes instead of 2n writes or n+1 writes? (Perhaps with a bulk insert?)

P.S. I've left this code tagged with sql as well as t-sql and sql-server, even though any solution would specifically have to work with T-SQL for me to use it. Other people may be interested in solutions that work for other databases, so please share! But such an answer will not be marked as correct.

Answer

You can swap all the intervening IDs in one UPDATE statement. Change the one you want to change, and all other rows move up or down by one.

DECLARE @ParentId int = 1;
DECLARE @OldNumber int = 1;
DECLARE @NewNumber int = 2;

UPDATE UserOrderableThing
SET OrderNumber =
  CASE WHEN OrderNumber = @OldNumber THEN @NewNumber
       WHEN @OldNumber > @NewNumber THEN OrderNumber + 1
       ELSE OrderNumber - 1
  END
WHERE OrderNumber BETWEEN LEAST(@OldNumber, @NewNumber) AND GREATEST(@OldNumber, @NewNumber)
  AND ParentId = @ParentId;

SQL Server (unlike some DBMSs) will ensure that the updates are done in a manner that the unique constraint is never violated, even in the middle of the transaction.
It does this using a Split-Sort-Collapse combination in the execution plan.

db<>fiddle

Changing multiple rows at once is going to be more complicated. You would need a Tabel Valued Parameter, as well as some careful coding to ensure everything moves in the right direction.

Enjoyed this article?

Check out more content on our blog or follow us on social media.

Browse more articles