User-sortable records

Question

For each user in my webapp, there are n related Widgets. Each widget is represented in the database in a Widgets table. Users can sort their widgets, they'll never have more than a couple dozen widgets, and they will frequently sort widgets.

I haven't dealt with database items that have an inherent order to them very frequently. What's a good strategy for ordering them? At first, I thought a simple "sortIndex" column would work just fine, but then I started wondering how to initialize this value. It presumably has to be a unique value, and it should be greater or less than every other sort index. I don't want to have to check all of the other sort indexes for that user every time I create a new widget, though. That seems unnecessary.

Perhaps I could have a default "bottom-priority" sort index? But then how do I differentiate between those? I suppose I could use a creation date flag, but then what if a user wants to insert a widget in the middle of all of those bottom-priority widgets?

What's the standard way to handle this sort of thing?

Answer 1

If you have users sorting widgets for their own personal tastes, you want to create a lookup table, like so:

create table widgets_sorting
(
    SortID int primary key,
    UserID int,
    WidgetID int,
    SortIndex int
)

Then, to sort a user's widgets:

select
    w.*
from
    widgets w
    inner join widgets_sorting s on
        w.WidgetID = s.WidgetID
    inner join users u on
        s.UserID = u.UserID
order by
    s.SortIndex asc

This way, all you'll have to do for new users is add new rows to the widgets_sorting table. Make sure you put a foreign key constraint and an index on both the WidgetID and the UserID columns.

These lookup tables are really the best way to solve the many-to-many relationships that are common with this sort of personalized listing. Hopefully this points you in the right direction!

Answer 2

The best way for user-editable sorting is to keep the id's in a linked list:

user_id   widget_id  prev_widget_id
   ----        ----            ----
      1           1               0
      1           2               8
      1           3               7
      1           7               1
      1           8               3
      2           3               0
      2           2               3

This will make 5 widgets for user 1 in this order: 1, 7, 3, 8, 2; and 2 widgets for user 2 in this order: 3, 2

You should make UNIQUE indexes on (user_id, widget_id) and (user_id, prev_widget_id).

To get widgets in intended order, you can query like this, say, in Oracle:

SELECT  w.*
FROM    (
        SELECT  widget_id, level AS widget_order
        FROM    widget_orders
        START WITH
                user_id = :myuser
                AND prev_widget_id = 0
        CONNECT BY
                user_id = PRIOR user_id
                AND prev_widget_id = PRIOR widget_id
        ) o
JOIN    widgets w
ON      w.widget_id = o.widget_id
ORDER BY
        widget_order

To update the order, you will need to update at most 3 rows (even if you move the whole block of widgets).

SQL Server and PostgreSQL 8.4 implement this functionality using recursive CTEs:

WITH    
-- RECURSIVE
-- uncomment the previous line in PostgreSQL
         q AS
         (
         SELECT  widget_id, prev_widget_id, 1 AS widget_order
         FROM    widget_orders
         WHERE   user_id = @user_id
         UNION ALL
         SELECT  wo.widget_id, wo.prev_widget_id, q.widget_order + 1
         FROM    q
         JOIN    wo.widget_orders wo
         ON      wo.user_id = @user_id
                 AND wo.prev_widget_id = q.widget_id
        )
SELECT  w.*
FROM    q
JOIN    widgets w
ON      w.widget_id = q.widget_id
ORDER BY
        widget_order

See this article in my blog on how to implement this functionality in MySQL:

• Sorting lists