Using Real numbers for explicit sorting in sql database

Question

i'm facing a recurring problem. I've to let a user reorder some list that is stored in a database.

The fist straightforward approach i can think is to have a "position" column with the ordering saved as a integer. p.e.

Data, Order
A     1
B     2
C     3
D     4

Problem here is that if i have to insert FOO in position 2, now my table become

Data, Order
A     1
FOO   2
B     3
C     4
D     5

So to insert a new line, i have to do one CREATE and three UPDATE on a table of five elements.

So my new idea is using Real numbers instead of integers, my new table become

Data, Order
A     1.0
B     2.0
C     3.0
D     4.0

If i want to insert a element FOO after A, this become

Data, Order
A     1.0
FOO   1.5
B     2.0
C     3.0
D     4.0

With only one SQL query executed.

This would work fine with theoretical Real Numbers, but floating point numbers have a limited precision and i wondering how feasible this is and whether and how can i optimize it to avoid exceeding double precision with a reasonable number of modifications

edit:

this is how i implemented it now in python

@classmethod
def get_middle_priority(cls, p, n):
    p = Decimal(str(p))
    n = Decimal(str(n))
    m = p + ((n - p)/2)

    i = 0
    while True:
        m1 = round(m, i)
        if m1 > p and m1 < n:
            return m1
        else:
            i += 1

@classmethod
def create(cls, data, user):
    prev = data.get('prev')

    if prev is None or len(prev)<1:
        first = cls.list().first()

        if first is None:
            priority = 1.0
        else:
            priority = first.priority - 1.0
    else:
        prev = cls.list().filter(Rotator.codice==prev).first()
        next = cls.list().filter(Rotator.priority>prev.priority).first()

        if next is None:
            priority = prev.priority + 1.0
        else:
            priority = cls.get_middle_priority(prev.priority, next.priority)

    r = cls(data.get('codice'),
        priority)

    DBSession.add(r)

    return r

Answer 1

If you want to control the position and there is no ORDER BY solution then a rather simple and robust approach is to point to the next or to the previous. Updates/inserts/deletes (other than the first and last) will require 3 operations.

Insert the new Item
Update the Item Prior the New Item
Update the Item After the New Item

After you have that established you can use a CTE (with a UNION ALL) to create a sorted list that will never have a limit.

I have seen rather large implementations of this that were done via Triggers to keep the list in perfect form. I however am not a fan of triggers and would just put the logic for the entire operation in a stored procedure.

Answer 2

The linked list idea is neat but it's expensive to pull out data in order. If you have a database which supports it, you can use something like connect by to pull it out. linked list in sql is a question dedicated to that problem.

Now if you don't, I was thinking of how one can achieve an infinitely divisable range, and thought of sections in a book. What about storing the list initially as

1
2
3

and then to insert between 1 and two you insert a "subsection under 1" so that your list becomes

1
1.1
2
3

If you want to insert another one between 1.1 and 2 you place a second subsection under 1 and get

1
1.1
1.2
2
3

and lastly if you want to add something between 1.1 and 1.2 you need to introduce a subsubsection and get

1
1.1
1.1.1
1.2
2
3

Maybe using letters instead of numbers would be less confusing.

I'm not sure if there is any standard lexicographic ordering in sql databases which could sort this type of list correctly. But I think you could roll your own with some "order by case" and substringing. Edit: I found a question pertaining to this: linky

Another downside is that the worst case field size of this solution would grow exponentially with the number of input items (You could get long rows like 1.1.1.1.1.1 etc). But in the best case it would be linear or almost constant (Rows like 1.934856.1).

This solution is also quite close to what you already had in mind, and I'm not sure that it's an improvement. A decimal number using the binary partitioning strategy that you mentioned will probably increase the number of decimal points between each insert by one, right? So you would get

1,2 -> 1,1.5,2 -> 1,1.25,1.5,2 -> 1,1.125,1.25,1.5,2

So the best case of the subsectioning-strategy seems better, but the worst case a lot worse.

I'm also not aware of any infinite precision decimal types for sql databases. But you could of course save your number as a string, in which case this solution becomes even more similar to your original one.

Answer 3

You may use a string rather then numbers:

item  order
A     ffga
B     ffgaa
C     ffgb

Here, the problem of finite precision is handled by the possibility of growing the string. String storage is theoretically unlimited in the database, only by the size of the storage device. But there is no better solution for absolute-ordering items. Relative-ordering, like linked-lists, might work better (but you can't do order by query then).

Answer 4

Set all rows to a unique number starting at 1 and incrementing by 1 at the start. When you insert a new row, set it to count(*) of the table + 1 (there are a variety of ways of doing this).

When the user updates the Order of a row, always update it by calling a stored procedure with this Id (PK) of the row to update and the new order. In the stored procedure,

update tableName set Order = Order + 1 where Order >= @updatedRowOrder;

update tablename set Order = @updatedRowOrder where Id = @pk;

That guarantees that there will always be space and a continuous sequence with no duplicates. I haven't worked you what would happen if you put silly new Order numbers of a row (e.g. <= 0) but probably bad things; that's for the Front End app to prevent.

Cheers -