SQL Server – Features and Patterns for Managing Ordered Lists

database-designsql server

I have a common scenario in app design, where I need to store an ordered list, and make the ordering easily accessible and adjustable via an application UI.

The ordering operations are simple and operate on only one item at a time – move to top, move to bottom, move up one position, or down one position. These positioning operations may be interspersed in with typical add / edit / delete list operations. For discussion, this is a single-user app and db store.

Because the objects can be highly complex, I'd like to avoid caching the entire list client-side, and tracking newly created objects in memory until a big save operation occurs.

I am using MS-SQL almost exclusively on these projects, and I'm wondering if there are db features, SQL features, or design patterns I should be using to better support the management of ordered lists.

My current approach is to use a DECIMAL column to store the list positions, which become fractional during the item move process. Then I sort the list and re-generate integer positions to normalize list. Following this operation, it's ready for another item move.

In an example implementation, I create a column named Seq for position tracking. Once decimal place is enough for the .5 storage. 

[Seq] [decimal](10, 1) NOT NULL

When an item is re-positioned in the app UI,

  1. I UPDATE that record with new Seq value
  2. I retrieve the full table, sorted ascending by Seq and regenerate all Seq values in the table from a 1-based integer series

The new Seq value is easily calculated-

  • Move to top = 0
  • Move to bottom = MAX(Seq) + 1
  • Move up = subtract 1.5 from the current Seq value
  • Move down = add 1.5 to the current Seq value

As lists get longer, updates get slower, since I'm doing N UPDATE statements, where N is the number of rows in the table, so it seems only suitable for small tables.

  • Is there some kind of in-built capability for managing an ordered list in SQL or MS-SQL?
  • Is there a means to update multiple rows in one call?

A far more performant approach would be to allow more decimal places, and then position at the median of the two adjacent items, with no re-sequencing on the list.

  • Move to top = Min(Seq) – 1
  • Move to bottom = MAX(Seq) + 1
  • Move up = median of the 2 previous item Seq values
  • Move down = median of the 2 following item Seq values

This approach only requires one SELECT (containing 2 rows max) and one UPDATE.

However with enough re-positions I imagine the field would run out of decimal places. For example, if I start with items at positions 10 and 11, and keep moving items down the list from position 9, they'd be given sequences of 10.5, then 10.25, then 10.125. After 10 moves, the positions get lengthy… 10.0009765625.

UPDATE #1 – IMPROVED RE-SEQUENCING OF THE LIST

Regarding re-sequencing, I'm more caught up on row_number(), OVER, and WITH capabilities in MS-SQL. It's nice to find that there's a much smoother way to re-sequence the list in a single UPDATE operation;

with OrderedItems as 
(
    select
        ItemID,
        Seq,
        row_number() over (order by Seq asc) NewSeq
    from 
        Items
)
update OrderedItems
set Seq = NewSeq

Best Answer

The last is a technique used quite often, and that works. If you're afraid of running out of decimals you can refine it to detect when the average between the next two previous/following values cannot be distinguished from one of them (i.e.: you run out of decimals).

When this happens, you should resequence as many rows up or down as needed.

Let's assume you work with just 2 decimals, and you have two rows with Seq 1.00 and 1.01; the next value being 2.00. If you want to move a row using your technique between these two, you would have Seq = (1.00, 1.005, 1.01, 2.00). This would need more decimals than are available and, depending on the rounding rules, 1.005 would either be rounded to 1.00 or 1.01. In any case, you can detect that the inserted value is not distinguishable from either 1.00 or 1.01.

In that case, you need to "push down (or up) and make room". That is, you should change one more row, and have (1.00, 1.25, 1.50, 2.00). You've spread the change to two rows instead of just one.

This might need to be done recursively (or iteratively) if you ever run into a situation such as (1.01, 1.02, 1.03, 1.04, ...).

With this extensions to your original technique, you don't need to renormalize. This is taken care of only in an "as needed" basis, and scales quite well.

NOTEs:

  1. Implementing the algorithm might be a bit tricky, because you need to take into account when you're at the first or last rows, and how to handle those, and when your Seq numbers reach the maximum or minimum available values.

  2. The algorithm works with any number of decimals, including 0. That is, you can use it as well with integer values instead of decimal, which might prove more computing efficient, or, depending on how decimals are implemented, be also more space efficient.

Related Question