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

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

Answer 2

If you mean that each user assigns his own sort order to the widgets, then Eric's answer is correct. Presumably you then have to give the user a way to assign the sort value. But if the number is modest as you say, then you can just give him a screen listing all the widgets, and either let him type in the order number, or display them in order and put up and down buttons beside each, of if you want to be fancy, give him a way to drag and drop.

If the order is the same for all users, the question becomes, Where does this order come from? If it's arbitrary, just assign a sequence number as new widgets are created.

Answer 3

I like to use a two-table approach - which can be a bit confusing but if you're using an ORM such as ActiveRecord it's easy, and if you write a bit of clever code it can be manageable.

Use one table to link user to sorting, and one table to link widget and position and sorting. This way it's a lot clearer what's going on, and you can use an SQL join or a seperate query to pull the various data from the various tables. Your structure should look like this:

//Standard user + widgets table, make sure they both have unique IDs
CREATE TABLE users;
CREATE TABLE widgets;

//The sorting tables
CREATE TABLE sortings (
    id INT, //autoincrement etc,
    user_id INT
)

CREATE TABLE sorting_positions (
    sorting_id INT,
    widget_id INT,
    position INT
)

Hopefully this makes sense, if you're still confused, comment on this message and I'll write you up some basic code.

Jamie

Answer 4

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!