47

The guys at the top want sort order to be customizable in our app. So I have a table that effectively defines the data type. What is the best way to store our sort order. If I just created a new column called 'Order' or something, every time I updated the order of one row I imagine I would have to update the order of every row to ensure posterity. Is there a better way to do it?

Anthony
  • 12,177
  • 9
  • 69
  • 105

5 Answers5

20

None of the answers so far have touched on the real problem with custom sort order and that is what happens when two different people want the same records sorted differently.

If you need a custom sort order, you need a related table to store it in, not an additional field. The table would have the userid, the recordId of the data and the sort order for the record. That way Joe Smith can have one order and Sally Jones another for the same data. Now you have the problem of new records being added to the data set. Do you put them at the beginning of the sort order or the end or do you require the person to set an order for them before they can be added to the set. This is in actuality a very complex problem that is generally not worth the amount of time it takes to implement because almost no one ever uses that system once it's in place (I mean do I really want to go through a hundred records and mark the individual order of each one?). Now it gets complicated in terms of saving the order of all the records (which will of course require changes the next time the query is run since there will be new records.) This is very painful process of limited untility.

I did this once in a proposal writing application because we needed to be able to sort the parts and tasks on the proposal in the order we thought would be most impressive to the customer. Even then, we had to institute a default order, so that they only need to move around the two or three things they really wanted to show up first instead of ordering 10,000 individual parts.

A better choice if you can get them to buy off on it, is to allow them to sort the data by columns (desc or asc). Usually the user interface can be designed so that if you click on a column header, it will resort the data by that column. This is relatively straightforward to do and meets most needs for custom ordering.

You really need to discuss this requirement with management and get details of how they want it to work beyond, I want custom ordering. This is often one of those things people think they want, but don't really use.

Philipp Kyeck
  • 18,402
  • 15
  • 86
  • 123
HLGEM
  • 94,695
  • 15
  • 113
  • 186
  • +1 for getting spec from the end user but moreover for the detail in explanation – Kris.Mitchell May 13 '10 at 18:22
  • Good answer. I will check with them about requirements but I believe it's going to end up completely customisable order, but probably one global order. The order will only be editable by admin and will be used by all users. – Anthony May 13 '10 at 22:53
  • "(I mean do I really want to go through a hundred records and mark the individual order of each one?)" Umm... Yes? And who's to say that you won't want to sort the records as they're inserted? In reality, this is a demonstrable disadvantage of using a SQL DB. – Andrew Jun 24 '20 at 19:01
19

The basic algorithm might be like one described below. Initially the sort field varies from item to item by 1000 (you may consider another interval). The items in the table are in ordered state just for the sake of simplicity. Btw, I've create Yii2 component to manage this stuff. And this one if you need a sortable tree sortable tree. 

id | sort
---+-----
1  | 1000
---+-----
2  | 2000
---+-----
3  | 3000
---+-----

Lets imagine we are going to add an item (id 4) after id 1:

id | sort
---+-----
1  | 1000
---+-----
4  | 1500
---+-----
2  | 2000
---+-----
3  | 3000
---+-----

So to calculate sort value for id 4 we took the sort value of the item before, which is 1000 and the item after - 2000 and took the mean. If you get a float, just round it to the nearest integer. If you need to insert an item at the beginning of the list, then you take a mean of (1000 and 0, which is 500).

Now, if we need to insert an item (id 5) after id 1, we do the same:

id | sort
---+-----
1  | 1000
---+-----
5  | 1250
---+-----
4  | 1500
---+-----
2  | 2000
---+-----
3  | 3000
---+-----

Later on, you might face to this scenario:

id | sort
---+-----
1  | 1000
---+-----
15 | 1001
---+-----
...
---+-----
5  | 1250
---+-----
...
---+-----

So if you need to insert an item (id 16) between 1 and 15, first you should increment sort field by 1000 of all items followed by 1:

id | sort
---+-----
1  | 1000
---+-----
15 | 2001
---+-----
...
---+-----
5  | 2250
---+-----
...
---+-----

Now you can insert the item (id 16):

id | sort
---+-----
1  | 1000
---+-----
16 | 1501
---+-----
15 | 2001
---+-----
...
---+-----
5  | 2250
---+-----
...
---+-----
Sergey Onishchenko
  • 6,943
  • 4
  • 44
  • 51
  • 1
    Yeah that works great until you get to the part where you have to increment a field for every single posterior item in the table just to insert 1. – Andrew Jun 24 '20 at 19:03
  • @Andrew exactly because of this issue you have an interval of 1000 (or any you choose ) do not alter all items on every single write. – Sergey Onishchenko Nov 16 '20 at 06:34
  • But that's not a permanent solution. Eventually you will run into a situation where what I said takes place, and then you're failing to uphold a consistent quick speed. Even worse, once it happens, it's likely to happen many times over. – Andrew Nov 17 '20 at 16:21
  • @Andrew if you look at Yii2 component mentioned in the answer - once this situation comes all the sort fields will be recalculated and updated. And it must not affect performance a lot, because it's a rare action, especially if the interval is big enough, which you choose depending on how often your table is updated. – Sergey Onishchenko Nov 24 '20 at 11:41
  • You're going to update every single field in the entire table. That's not acceptable. – Andrew Nov 28 '20 at 03:16
  • @Andrew this case happens very rarely and you update it once and the next time you will update it after a long while. Even if you have a million records in the table this update is just a matter of seconds. – Sergey Onishchenko Feb 26 '21 at 07:46
  • But that's just not true. If you insert 10k items at, say, position 2,000, then you'll reach a point where every single insert requires you to re-index thousands of items at a time. ***This is not a solution.*** – Andrew Feb 27 '21 at 23:20
  • @Andrew yeah, here you caught me)) But I can't even think of a real world use case where you need sorted tree with 10k inserts at a time. I mean manually maintained sorted tree... Sure, this solution is not for every possible case. I guess that's why we have many other invented. – Sergey Onishchenko Mar 03 '21 at 07:53
1

You can use a float instead, and as long as you have enough precision you can always just set ordinal column for the moved record to the midpoint between the records on either side.

Joel Coehoorn
  • 399,467
  • 113
  • 570
  • 794
  • 8
    Would you need to periodically realign these? I imagine that after a few hundred thousand operations, relying on the precision of fp could get sketchy. – Anthony May 13 '10 at 02:54
  • Right, floating point numbers don't have infinite precision, so this is a very similar solution to using a integer, although I prefer the integer since it's easier to reason about. – Garrett Aug 22 '22 at 22:51
1

Use an int field. When you update the sort order of one row, you only have to update the field on the row you're updating and any rows between the row's old and new positions. This means that swapping two rows only involves touching those two rows. Also, for rows you're updating that aren't your "active" row, you only need to increment or decrement the field; the queries are easy to write.

regularfry
  • 3,248
  • 2
  • 21
  • 27
  • 1
    what happens when rows are deleted in between and new rows are added – msanjay Mar 19 '14 at 08:18
  • 1
    or when you run out of in-between numbers - same problem in Sergey's answer – Andrew Jun 24 '20 at 19:03
  • 2
    Store the int, but sort as a string. When you run out of slots between adjacent rows and want to do an insert, stick a '5' on the end of the lower bound. So if your first three inserts were 'a', 'c', 'b', your sort order column entries might be '1', '2', '15'. That allows either situation without too many gymnastics. – regularfry Jun 29 '20 at 12:15
  • Then you eventually have really long strings. Not a permanent solution. Similar to Sergey's answer. – Andrew Nov 17 '20 at 16:23
  • 1
    Yes, but the question is whether that matters for your dataset. Unless the insertion order is pathological, the average string length will be O(log(n)), and string comparison speed depends on the length of the shorter of the two. Also, unless you've got a reason to make the stored string decimal digits, you can use the base64 character set and make it O(log64(n)), which is a really nice way of squeezing it further. If your database allows string comparisons of binaries, you can get it to O(log256(n)). – regularfry Nov 19 '20 at 09:45
  • This does have the downside that adding elements in already-sorted order behaves badly, though, so that case alone might mean you want to take the trade-off of implementing a b-tree as a nested set and live with the added data complexity and tree management that needs. – regularfry Nov 19 '20 at 09:53
0

Generally the application would add the approriate ORDER BY clause to the query. If the result sets to be sorted are relatively small you can have keys on the selection criteria. Even with large results it is often better to sort the selected data than retrieve in order by index.

If the requirement is to have orders like B A Z T Q M K, then you will need a column to place the relative order into. The appropriate value would need to be determined each time you add a row. However, this works well for code tables which are relatively static.

BillThor
  • 7,306
  • 1
  • 26
  • 19