While the OP briefly touched on the notion of using a Linked-List to store sort-order, it has a lot of advantages for cases where items will be reordered frequently.
I have seen people using a self-reference to refer to the previous (or next) value, but again, it seems like you would have to update a whole lot of other items in the list.
The thing is - you don't! When using a linked-list, insertion, deletion, and re-ordering are O(1) operations, and database-imposed referential integrity ensures there aren't any broken references, orphaned records, or loops.
Here's an example:
CREATE TABLE Wishlists (
WishlistId int NOT NULL IDENTITY(1,1) PRIMARY KEY,
[Name] nvarchar(200) NOT NULL
);
CREATE TABLE WishlistItems (
ItemId int NOT NULL IDENTITY(1,1),
WishlistId int NOT NULL,
Text nvarchar(200) NOT NULL,
SortAfter int NULL,
CONSTRAINT PK_WishlistItem PRIMARY KEY ( ItemId, WishlistId ),
CONSTRAINT FK_Wishlist_WishlistItem FOREIGN KEY ( WishlistId ) REFERENCES Wishlists ( WishlistId ),
CONSTRAINT FK_Sorting FOREIGN KEY ( SortAfter, WishlistId ) REFERENCES WishlistItems ( ItemId, WishlistId )
);
CREATE UNIQUE INDEX UX_Sorting ON WishlistItems ( SortAfter, WishlistId );
-----
SET IDENTITY_INSERT Wishlists ON;
INSERT INTO Wishlists ( WishlistId, [Name] ) VALUES
( 1, 'Wishlist 1' ),
( 2, 'Wishlist 2' );
SET IDENTITY_INSERT Wishlists OFF;
SET IDENTITY_INSERT WishlistItems ON;
INSERT INTO WishlistItems ( ItemId, WishlistId, [Text], SortAfter ) VALUES
( 1, 1, 'One', NULL ),
( 2, 1, 'Two', 1 ),
( 3, 1, 'Three', 2 ),
( 4, 1, 'Four', 3 ),
( 5, 1, 'Five', 4 ),
( 6, 1, 'Six', 5 ),
( 7, 1, 'Seven', 6 ),
( 8, 1, 'Eight', 7 );
SET IDENTITY_INSERT WishlistItems OFF;
Note the following:
- Using a composite primary-key and foreign-key in
FK_Sorting to prevent items from accidentally referring to the wrong parent item.
- The
UNIQUE INDEX UX_Sorting performs two roles:
- As it allows a single
NULL value each list can have only 1 "head" item.
- It prevents two or more items from claiming to be in the same sorting place (by preventing duplicate
SortAfter values).
The main advantages to this approach:
- Never requires rebalancing or maintenance - as with
int or real-based sort-orders that eventually run out of space between items after frequent reordering.
- Only items that are re-ordered (and their siblings) need to be updated.
This approach does have disadvantages, however:
- You can only sort this list in SQL using a Recursive CTE because you cannot do a straightforward
ORDER BY.
- As a workaround, you could create a wrapper
VIEW or TVF that uses a CTE to add a derived containing an incrementing sort-order - but this would be expensive to use in large operations.
- You must load the entire list into your program in order to display it - you cannot operate on a subset of the rows because then the
SortAfter column will refer to items that aren't loaded into your program.
- However loading all items for a list is easy due to the composite primary key (i.e. just do
SELECT * FROM WishlistItems WHERE WishlistId = @wishlistToLoad).
- Performing any operation while
UX_Sorting is enabled requires DBMS support for Deferred Constraints.
- i.e. the ideal implementation of this approach won't work in SQL Server until they add-back support for Deferrable Constraints and indexes.
- A workaround is to make the Unique Index a Filtered Index that allows multiple
NULL values in the column - which unfortunately means that a List could have multiple HEAD items.
- A workaround-for-this-workaround is to add a third column
State which is a simple flag to declare if a list item is "active" or not - and the unique index ignores inactive items.
- This is something SQL Server used to support back in the 1990s and then they inexplicably removed support for it.
Workaround 1: Need ability to perform a trivial ORDER BY.
Here's a VIEW using a recursive CTE that adds a SortOrder column:
CREATE VIEW OrderableWishlistItems AS
WITH c ( ItemId, WishlistId, [Text], SortAfter, SortOrder )
AS
(
SELECT
ItemId, WishlistId, [Text], SortAfter, 1 AS SortOrder
FROM
WishlistItems
WHERE
SortAfter IS NULL
UNION ALL
SELECT
i.ItemId, i.WishlistId, i.[Text], i.SortAfter, c.SortOrder + 1
FROM
WishlistItems AS i
INNER JOIN c ON
i.WishlistId = c.WishlistId
AND
i.SortAfter = c.ItemId
)
SELECT
ItemId, WishlistId, [Text], SortAfter, SortOrder
FROM
c;
You can use this VIEW in other queries where you need to sort values using ORDER BY:
Query:
SELECT * FROM OrderableWishlistItems
Results:
ItemId WishlistId Text SortAfter SortOrder
1 1 One (null) 1
2 1 Two 1 2
3 1 Three 2 3
4 1 Four 3 4
5 1 Five 4 5
6 1 Six 5 6
7 1 Seven 6 7
8 1 Eight 7 8
Workaround 2: Preventing UNIQUE INDEX violation constraints when performing operations:
Add a State column to the WishlistItems table. The column is marked as HIDDEN so most ORM tools (like Entity Framework) won't include it when generating models, for example.
CREATE TABLE WishlistItems (
ItemId int NOT NULL IDENTITY(1,1),
WishlistId int NOT NULL,
Text nvarchar(200) NOT NULL,
SortAfter int NULL,
[State] bit NOT NULL HIDDEN,
CONSTRAINT PK_WishlistItem PRIMARY KEY ( ItemId, WishlistId ),
CONSTRAINT FK_Wishlist_WishlistItem FOREIGN KEY ( WishlistId ) REFERENCES Wishlists ( WishlistId ),
CONSTRAINT FK_Sorting FOREIGN KEY ( SortAfter, WishlistId ) REFERENCES WishlistItems ( ItemId, WishlistId )
);
CREATE UNIQUE INDEX UX_Sorting ON WishlistItems ( SortAfter, WishlistId ) WHERE [State] = 1;
Operations:
Adding a new item to the tail end of the list:
- Load the list first to determine the
ItemId of the current last item in the list and store in @tailItemId - or use SELECT MAX( SortOrder ) FROM OrderableWishlistItems WHERE WishlistId = @listId.
INSERT INTO WishlistItems ( WishlistId, [Text], SortAfter ) VALUES ( @listId, @text, @tailItemId ).
Reordering item 4 to be below item 7
BEGIN TRANSACTION
DECLARE @itemIdToMove int = 4
DECLARE @itemIdToMoveAfter int = 7
DECLARE @prev int = ( SELECT SortAfter FROM WishlistItems WHERE ItemId = @itemIdToMove )
UPDATE WishlistItems SET [State] = 0 WHERE ItemId IN ( @itemIdToMove , @itemIdToMoveAfter )
UPDATE WishlistItems SET [SortAfter] = @itemIdToMove WHERE ItemId = @itemIdToMoveAfter
UPDATE WishlistItems SET [SortAfter] = @prev WHERE SortAfter = @itemIdToMove
UPDATE WishlistItems SET [State] = 1 WHERE ItemId IN ( @itemIdToMove, @itemIdToMoveAfter )
COMMIT;
Removing item 4 from the middle of the list:
If an item is at the tail end of the list (i.e. where NOT EXISTS ( SELECT 1 FROM WishlistItems WHERE SortAfter = @itemId )) then you can do a single DELETE.
If an item has an item sorted after it, you perform the same steps as reordering an item, except you DELETE it afterwards instead of setting State = 1;.
BEGIN TRANSACTION
DECLARE @itemIdToRemove int = 4
DECLARE @prev int = ( SELECT SortAfter FROM WishlistItems WHERE ItemId = @itemIdToRemove )
UPDATE WishlistItems SET [State] = 0 WHERE ItemId = @itemIdToRemove
UPDATE WishlistItems SET [SortAfter] = @prev WHERE SortAfter = @itemIdToRemove
DELETE FROM WishlistItems WHERE ItemId = @itemIdToRemove
COMMIT;
