28

A common need when using a database is to access records in order. For example, if I have a blog, I want to be able to reorder my blog posts in arbitrary order. These entries often have lots of relationships, so a relational database seems to make sense.

The common solution that I have seen is to add an integer column order:

CREATE TABLE AS your_table (id, title, sort_order)
AS VALUES
  (0, 'Lorem ipsum',   3),
  (1, 'Dolor sit',     2),
  (2, 'Amet, consect', 0),
  (3, 'Elit fusce',    1);

Then, we can sort the rows by order to get them in the proper order.

However, this seems clumsy:

  • If I want to move record 0 to the start, I have to reorder every record
  • If I want to insert a new record in the middle, I have to reorder every record after it
  • If I want to remove a record, I have to reorder every record after it

It's easy to imagine a situations like:

  • Two records have the same order
  • There are gaps in the order between records

These could happen fairly easily for a number of reasons.

This is the approach that applications like Joomla take:

Example of Joomla's approach to ordering

You could argue that the interface here is bad, and that instead of humans directly editing numbers, they should use arrows or drag-and-drop—and you'd probably be right. But behind the scenes, the same thing is happening.

Some people have proposed using a decimal to store order, so that you can use "2.5" to insert a record in between the records at order 2 and 3. And while that helps a little, it's arguably even messier because you can end up with weird decimals (where do you stop? 2.75? 2.875? 2.8125?)

Is there a better way to store order in a table?

  • 4
    Just so you know . . . "The reason such systems are called "relational" is that the term relation is basically just a mathematical term for a table . . ." -- An Introduction to Database Systems, CJ Date, 7th ed. p 25 – Mike Sherrill 'Cat Recall' Mar 17 '13 at 20:06
  • 1
    Possible duplicate of Features and Patterns for Managing Ordered Lists – Evan Carroll Mar 21 '18 at 19:10
  • @MikeSherrill'CatRecall' that I didn't catch, I've fixed the question with the old orders and ddl. – Evan Carroll Mar 23 '18 at 3:03
15

If I want to move record 0 to the start, I have to reorder every record

No, there's a simpler way.

update your_table
set order = -1 
where id = 0;

If I want to insert a new record in the middle, I have to reorder every record after it

That's true, unless you use a data type that supports "between" values. Float and numeric types allow you to update a value to, say, 2.5. But varchar(n) works, too. (Think 'a', 'b', 'c'; then think 'ba', 'bb', 'bc'.)

If I want to remove a record, I have to reorder every record after it

No, there's a simpler way. Just delete the row. The remaining rows will still sort correctly.

It's easy to imagine a situations like:

Two records have the same order

A unique constraint can prevent that.

There are gaps in the order between records

Gaps have no effect on how a dbms sorts values in a column.

Some people have proposed using a decimal to store order, so that you can use "2.5" to insert a record in between the records at order 2 and 3. And while that helps a little, it's arguably even messier because you can end up with weird decimals (where do you stop? 2.75? 2.875? 2.8125?)

You don't stop until you have to. The dbms has no problem sorting values that have 2, 7, or 15 places after the decimal point.

I think your real problem is that you'd like to see values in sorted order as integers. You can do that.

create table your_table (
  id int primary key, 
  title varchar(13), 
  sort_order float
);

insert into your_table values
(0, 'Lorem ipsum', 2.0),
(1, 'Dolor sit', 1.5),
(2, 'Amet, consect', 0.0),
(3, 'Elit fusce', 1.0);

-- This windowing function will "transform" the floats into sorted integers.
select id, title,
       row_number() over (order by sort_order)
from your_table
  • For the sake of neatness, you could finish the job with something like with cte as (select *,row_number() over (order by sort_order desc) as row from test) update cte set sort_order=row; – Manngo Mar 28 '17 at 11:23
  • Here is an additional hint: If you want it to be really perfect, you should check if you're moving more rows then you wish to keep untouched. If so, then update the less numerous - the "untouched" - ones ;D – Ruben Boeck May 12 '18 at 11:00
7

It is very simple. You need to have a "cardinality hole" structure:

You need to have 2 columns:

  1. pk = 32bit integer
  2. order = 64bit bigint (not double)

Insert/update

  1. When inserting the first new record, set order = round(max_bigint / 2).
  2. When inserting at the beginning of the table, set order = round("order of first record" / 2)
  3. When inserting at the end of table, set order = round("max_bigint - order of last record" / 2) 4) When inserting in the middle, set order = round("order of record before - order of record after" / 2)

This method has a very big cardinality. If you have constraint error or if you think what you have small cardinality you can rebuild order column (normalize).

In maximal situation with normalization (with this structure) you can have "cardinality hole" in 32 bit.

Remember not to use floating point types - order must be a precise value!

4

Generally, ordering is done according to some information in the records, title, ID, or whatever is appropriate for that particular situation.

If you do need a special ordering, using an integer column isn't as bad as it might seem. For example, to make room for a record to go into 5th place, you could do something like:

update table_1 set place = place + 1 where place > 5.

Hopefully you can declare the column to be unique and maybe have a procedure to make rearrangements "atomic". The details depend on the system but that's the general idea.

4

…it's arguably even messier because you can end up with weird decimals (where do you stop? 2.75? 2.875? 2.8125?)

Who cares? These numbers are only there for the computer to deal with so it doesn't matter how many fractional digits they have or how ugly they appear to us.

Using decimal values means that to move item F between items J and K all you need to do is select the order values for J and K then average them then update F. Two SELECT statements and one UPDATE statement (probably done using serializable isolation to avoid deadlocks).

If you want to see integers rather than fractions in the output then either calculate integers in the client application or use the ROW_NUMBER() or RANK() functions (if your RDBMS includes them).

0

In my own project, I'm planning to try a solution like this:

def pad(x, x_len, length):
    if x_len >= length:
        return x
    else:
        for _ in range(length - x_len):
            x += b"\x00"
        return x

def order_index(_from, _to, count):
    assert _from != _to
    assert _from < _to

    from_len = len(_from)
    to_len = len(_to)
    length = max(from_len, to_len)

    _from = pad(_from, from_len, length)
    _to = pad(_to, to_len, length)

    from_int = int.from_bytes(_from, "big")
    to_int = int.from_bytes(_to, "big")
    inc = (to_int - from_int)//(count + 1)
    if not inc:
        length += 1
        _from += b"\x00"
        _to += b"\x00"
        return order_index(_from, _to, count)

    return (int.to_bytes(from_int + ((x+1)*inc), length, "big") for x in range(count))
>>> index = order_index(b"A", b"Z", 24)
>>> [x for x in index]
[b'B', b'C', b'D', b'E', b'F', b'G', b'H', b'I', b'J', b'K', b'L', b'M', b'N', b'O', b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W', b'X', b'Y']
>>> 
>>> index = order_index(b"A", b"Z", 25)
>>> [x for x in index]
[b'A\xf6', b'B\xec', b'C\xe2', b'D\xd8', b'E\xce', b'F\xc4', b'G\xba', b'H\xb0', b'I\xa6', b'J\x9c', b'K\x92', b'L\x88', b'M~', b'Nt', b'Oj', b'P`', b'QV', b'RL', b'SB', b'T8', b'U.', b'V$', b'W\x1a', b'X\x10', b'Y\x06']

This is similar to the decimal numbers solution, but instead it uses a byte-array.

The idea is that you can never run out of possible in-between values because you just append a b"\x00" to the records involved if you need more values.

E.g., say you have two records, b"\x00" and b"\x01", and you want a record to go between them. There aren't any available values between 0x00 and 0x01, so you append b"\x00" to both, and now you have a bunch of values between them you can use to insert new values.

>>> records = [b"\x00", b"\x01", b"\x02"]
>>> values = [x for x in order_index(records[0], records[1], 3)]
>>> records = records + values
>>> records.sort()
>>> records
[b'\x00', b'\x00@', b'\x00\x80', b'\x00\xc0', b'\x01', b'\x02']

The database can easily sort it because everything ends up in lexicographic order. If you delete a record, it's still in order. It would probably be easiest not to ever use b"\x00" or b"\xff" as first and last records, though, since you can use those as virtual "from" and "to" values to prepend/append new records:

>>> records = []
>>> value = next(order_index(b"\x00", b"\xff", 1))
>>> value
b'\x7f'
>>> records.append(value)
>>> value = next(order_index(records[0], b"\xff", 1))
>>> value
b'\xbf'
>>> records.append(value)
>>> records.sort()
>>> records
[b'\x7f', b'\xbf']
>>> value = next(order_index(b"\x00", records[0], 1))
>>> value
b'?'
>>> records.append(value)
>>> records.sort()
>>> records
[b'?', b'\x7f', b'\xbf']
New contributor
tjb1982 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.