User-defined Order in SQL
begriffs.com
begriffs.com
(1) If updates fail, you don't get a resulting broken state
(2) The size of the lists is not that large (<50), so the extra writes are not that expensive.
Essentially, with any variation on fractional updates (where only 1-2 rows are updated per list update), the client is sending to the server "move item a to position x". Then, shortly after, "move item b to position y", etc. And if any intermediate step fails, the server and client are out of sync.
If, instead, the client message is "here is the new state of the list: (a,b,c)" and the server updates, failed requests only leave the state temporarily out of sync. The client will continue to send the complete correct state at each update.
Implement a specific call that takes a list of all IDs in the new order, and batch run the UPDATEs on the server side.
I did enjoy the article, but did not realize it was PostgreSQL specific until towards the end.
Very clever, Argyle.
If your problem is there are too many items in the list, that's going to be a usability problem so you'd probably need to categorize the items.
If performance is such an issue that ordering <50 items with approach 1 is unacceptable you undoubtedly have performance issues with the rest of your app too.
I guess you can always swap pairs of rows with subtraction, like swapping row 5 and 7 would be:
update t set user_order = 5 + (7 - user_order) where id in (123, 456)
http://sqlfiddle.com/#!17/b3d19/1
You can do something similar in MySQL with temp tables.
Bulk update through upsert (slightly different than a bulk update, since it can create rows too)
MySQL: http://sqlfiddle.com/#!9/a6f050/1
Postgres: http://sqlfiddle.com/#!17/a8367/1
UPDATE example
SET position = CAST(temp.position AS INTEGER)
FROM unnest(:ids, :positions) AS temp (id, position)
WHERE example.id = CAST(temp.id AS INTEGER); update t
set user_order =
case
when id = 123
then 500
else user_order + 1
end
where id = 123 or user_order >= 500; update items
set pos = case
when pos = P then Q
when P < Q and pos between P and Q then pos - 1
when Q < P and pos between Q and P then pos + 1
else pos
end
I had considered most of the solutions listed in the article except for the true fraction method. I believe that solution was explored by the author as they thought floating points were somehow solving a problem that couldn't be solved by integers. I settled on an approach that is essentially Solution 2 but using integers instead, each time bisecting the other two integers. The important aspect is that when inserting at the head or tail of the list, you bisect between MININT (-2^63) or MAXINT (2^63-1) respectively.
It might be possible to have a table that keys to the first that has a level and a value. For 1.1.26.1 above, it would have the rows (1, 1), (2, 1), (3, 26), (4, 1) (with keys to the table rows). Not sure exactly how to write the sql to join it all together and sort it, but it seems possible, at least if you have some known maximum number of levels.
I think the author missed a pathological case with using the Stern-Brocot tree.
The goal is to sort each item with a score. Then to insert something between two items, you calculate a new score that is "between" their existing scores.
- Option 1) Take the average of the two score a/b and c/d:
(ad+bc)/(2bd)
(a+c)/(b+d)
So the mediant is better because the precision requirements is limited by the number of times you can add instead of multiply. This might seem to grow a lot slower at first. And the author even showed that if you're repeatedly averaging 0/1 with the new score, you would get the pattern 1/2, 1/3, 1/4, 1/5, 1/6, .... Which means you can handle up 2^precision number of inserts which is much better than before.
But this only applies to inserting to front (medianting with 0/1) or back (medianting with 1/1) because this will only add a 0 or 1 each time.
If you go down a zigzag path down the middle of the tree instead, you can get the two numbers added to be much closer in magnitude and explode. For example: 1/1, 1/2, 2/3, 3/5, 5/8, 8/13, 13/21, 21/34, ... (it's fibonacci!).
So essentially you get the same thing as the averaging case where the precision required roughly doubles(1.6180339887...) at each step and it will overflow quickly.
This isn't a purely theoretical edge case either. The example from before can be realized by repeatedly inserting between the last two items inserted, which arises naturally if you're repeatedly adding to the middle of a list.
The decimal solution is really not bad. You could improve on it by not taking the midpoint between the two values you're inserting between, but rather another point which doesn't require an extra digit, when that's possible, but really that's very likely to be an unnecessary optimisation. So continual insertion on the end might give 0.5, 0.8, 0.9, 0.95, 0.98 0.99, 0.995...
And maybe periodically do the same for all values in your table? Like when users are not interacting with the items maybe.
You can apply the same logic of finding the midpoint between two integers using very simple integer math, store the result as an integer, and get high performance. Just don't start by populating your list with small numbers, the first number would be 0 and the second one would be the midpoint between 0 and either MAXINT or MININT depending on if it came before or after. This ought to have all the advantages of approach 3 (True Fractions) with none of the disadvantages. I'd create a function integer_intermediate just like the rational_intermediate function documented in the article too.
The problem with floating points is that the available precision is highly variable. Sure you can bisect between 0 and 1 many times, but what about between 1000 and 1001? Those 10 bits are lost.
bisect(a,b) = (coalesce(a, MININT)/2) + (coalesce(b, MAXINT)/2)
gns24 is right, if you're using 64 bits of precision, no matter the format, there must be some combination of at most 64 insertions that trigger the edge case of trying to insert between two items that have no representable value between them. I feel like there's a simple proof with e.g. pigeonhole principle.
So all of these approaches will have to be paired with a normalization routine that takes takes the bisected values and spreads them back out across the space to allow insertion again. Probably an after update/insert trigger that only kicks in when a new item is placed directly next to another, and spreads out all the nearby keys so that there is some minimum distance between them.
id | name | at | date_modified
1 | foo | 1 | 2018-03-21 12:00
2 | bar | 2 | 2018-03-21 12:01
3 | baz | 3 | 2018-03-21 12:02
-- Move last item to top
UPDATE ordered_set SET at = 1, date_modified = NOW() WHERE id = 3;
SELECT * FROM ordered_set ORDER BY at ASC, date_modified DESC;
id | name | at | date_modified
3 | baz | 1 | 2018-03-21 12:10
1 | foo | 1 | 2018-03-21 12:00
2 | bar | 2 | 2018-03-21 12:01
That said, this seems like a pretty trivial non-issue. You wouldn't want to do this on very large datasets, and updating many rows for small sets performs just fine in my experience.
>The solution shouldn't require complicated PL/pgSQL functions or parsing lists of numbers in strings.
Not to be overly pedantic, but if creating an extension that implements a new data type isn't "[requiring] complicated PL/pgSQL functions", I don't know what is.
The table could be designed with a unique PK, the todo item, and some binary or bool field to determine first (head) and last (tail). You would then add 'previous' and 'next' fields that would be updated for insert/delete/updates.
Let's say you have a 1M element list, and you want to get the first 100 elements. Normally you would write something like:
> select top(100) * ... order by itemPosition asc
- walk it on the client, one query per element, resulting in way too many roundtrips to the server.
- get all the data in one go and then walk it on the client. Here we're selecting and returning 1M records and throwing most of those away.
- walk the list in the database with a recursive common table expression. CTE's aren't appropriate for this; it'll be slow, and we'll run up against a recursion limit for large lists.
- walk the list in the database with cursors/loops/etc. Very icky, and breaks composability.
That being said, this would not alleviate the problems you mentioned when walking the list. It would need to be arranged once retrieved either by the client, or by the backend before passing to the client. I imagined that I would traverse the list recursively to order it before passing it off to the client. This should take O(n) time, since we only need to traverse the list once, and we haven't retrieved from the database any unrelated rows (list ID, user ID, etc - there has to be some boundary in place).
with recursive cte (udo_id, prv, nxt, label) as (
select *
from udo
where udo_id = :first_item_id
union all
select u.*
from udo u
join cte
on u.prv = cte.udo_id
) select * from cte limit 100 with recursive todo_list_sorted as (
select
*
from
todo_list tl1 where prev_id is null
union all
select
tl1.*
from
todo_list tl1
join
todo_list_sorted tl2 on tl1.prev_id = tl2.id
)
select * from todo_list_sortedIt's also a lot harder to query results in order while specifying an offset.
nworks=# create table todo (todo_id int primary key, task text, preceded_by int not null references todo (todo_id));
CREATE TABLE
nworks=# insert into todo values(1, 'do homework', 1);
INSERT 0 1
nworks=# insert into todo values(2, 'clean bedroom', 1);
INSERT 0 1
nworks=# insert into todo values(3, 'walk the dog', 2);
INSERT 0 1
nworks=# insert into todo values(4, 'call mom', 3);
INSERT 0 1
nworks=# select * from todo;
todo_id | task | preceded_by
---------+---------------+-------------
1 | do homework | 1
2 | clean bedroom | 1
3 | walk the dog | 2
4 | call mom | 3
(4 rows)
nworks=# update todo set preceded_by = 1 where todo_id = 4; -- call your mother first, it's more important
UPDATE 1
nworks=# select * from todo order by preceded_by;
todo_id | task | preceded_by
---------+---------------+-------------
2 | clean bedroom | 1
1 | do homework | 1
4 | call mom | 1
3 | walk the dog | 2
(4 rows)
It has no limit imposed by precision, the benefit of a compact and well-supported storage format (just one BIGINT) will probably compensate for any inefficiency caused by updating several rows, and the multiple steps are not fragile at all if you trust PostgreSQL to handle trasactions properly. If you're really worried, just increment the sequence before you update a bunch of rows, not afterward.
But what if you have millions of users reordering billions of todo items?
Well, change the uniqueness constraint to (user_id, list_id, pos) or something composite like that. Only reorder items belonging to the same list owned by the same user. If a person is manually reordering items, there can't be too many items in any given list in the first place. There's no need to touch billions of other items belonging to other lists and other users.
As for storage, the rational datatype described in the submission has the same size as a BIGINT (64 bits), so there's no storage disadvantage there.
I’ll never brush aside the SQL-object impedance mismatch like many people do, as something to work around in an otherwise great system that you can adapt to anything. SQL and relational modeling is an abstraction that leaks way too easily when it comes to these sorts of “human” use cases, wherein you want to do something that’s not perfectly rectangular like arbitrary sort. SQL probably didn’t leak like this when used for enterprise invoice-orders that it was designed for, but using it for applications where a touch screen is the primary user input that motivates the model: I’m not so sure it holds up.
- The first item added has rank "m"
- If I want to add an item before that, it's m-a/2 (somewhere around "f")
- If I want to put something between "b" and "c" that's "bm"
- The database can sort it just fine.
Suppose you have 3 items:
id pos name
1 'a' apple
2 'm' banana
3 'z' cherry
id pos name
1 'a' apple
3 'g' cherry
2 'm' banana
id pos name
1 'a' apple
2 'd' banana
3 'g' cherry
(Let's assume that your db is very fast, and let your app update all needed positions on save)
Keep a (balanced) binary tree where each node contains a pointer to one of the items you want to keep ordered. (In this case, each node has the primary key of one of your database rows.)
Every node also contains an integer which tells the size of that subtree (the tree whose root is that node).
To enumerate the entire list, do an in-order traversal of the tree.
To find the Nth item in the list, check the left child to see if it contains enough nodes that your Nth item would be in that subtree. If so, go left. If not, it's either the current node (if off by exactly one) or you go right. But if you go right, you must reduce N by 1 to account for the current node and also reduce N by the size of the left subtree.
To enumerate a range, you basically combine the previous two.
To move an item, just move it in the normal way you'd delete/add a node in any regular tree, but remember to update the counts stored inside any nodes that are affected, i.e. all parents/ancestors of any node that is removed or added. If you delete an internal node, you need to be careful to preserve the order of everything, but there are ways to do that by exchange
This data structure can definitely be modeled in database tables. Whether the operations on it can all be expressed in SQL is an interesting question. It might be impossible, or it might just be really tricky.
> A column of type hierarchyid does not automatically represent a tree. It is up to the application to generate and assign hierarchyid values in such a way that the desired relationship between rows is reflected in the values. Some applications might have a column of type hierarchyid that indicates the location in a hierarchy defined in another table.
[0] https://www.postgresql.org/docs/current/static/ltree.html
id | text | prev | next
1 | "steal underpants" | NULL | 2
2 | "???" | 1 | 3
3 | "profit" | 2 | NULL
I'd say, unless the list is really large, just change all the "pos" values in a concatenated set of update queries (transactioned of course). Also, don't forget the unique constraint on whatever makes the list unique + the pos.
There is also the issue of how many writes you do: finding a fraction between two others let’s you do just one INSERT or UPDATE (effectively the same thing in MVCC); but rewiring a linked list implies altering two rows. That may be okay but it’s not ideal.
The point of the solution here is so you can simply go `SELECT * FROM list ORDER BY pos` and have the correct order.
with recursive todo_list_sorted as (
select
*
from
todo_list tl1 where prev_id is null
union all
select
tl1.*
from
todo_list tl1
join
todo_list_sorted tl2 on tl1.prev_id = tl2.id
)
select * from todo_list_sorted select * from (items) order by `prev` --`next` doesn't help
-- also hope that NULL is at the beginning
Exercise for the reader: what happens when item id #3 is moved in between item id #1 and #2, how many update statements are needed?
id | text | prev | next
1 | "profit" | 2 | NULL
2 | "???" | 3 | 1
3 | "steal underpants" | NULL | 2Say I wanted to present a list of users with their top three to-do items, that's impossible using the above method.
select
u.user, item1=i1.text, item2=i2.text, item3=i3.text
from
users u
join items i1 on i1.user = u.user and i1.pos = 1
left join items i2 on i2.user = u.user and i2.pos = 2
left join items i3 on i3.user = u.user and i3.pos = 3
Floats only solve two issues: Making inserting easier while still being able to use `order by`. But reasoning about your data becomes a lot harder.
Would you elaborate on why you consider these types unfit for sorting? Their orderings are deterministic, and efficiency depends on the implementation of the indexes for those specific types, not inherent in the data types themselves.
> "select u.user, item1=i1.text, item2=i2.text, item3=i3.text"
It would be more natural in SQL to return three rows than return three columns.
SELECT u.user, i.text
FROM users AS u
JOIN items AS i USING (user)
WHERE u.user = ?
ORDER BY i.pos ASC LIMIT 3;
I should have changed that language, what I meant was that they were unfit for reasoning about your data from an isolated point of view, i.e. standing with just one row. To understand an item's position using floats, you must know the entire context.
> It would be more natural in SQL to return three rows than return three columns.
Look at my select again, yours have a specific user in mind, mine doesn't. I want a list of all users who have at least one to-do item. And I want to see their top three to-do items in the report.
Without doing sub-selects in the joins, there is no way to limit this to three when the position is stored as float. And even your sub-selects are going to be complicated.
It might be better to create a temporary table first with each user and their first three items, but that's hardly efficient.
> Why would you prefer to do it the way you describe?
Because I need an overview. And I don't want up to three rows per user, particularly because some users will only get one row, some only two and most three rows. That creates an inconsistent overview.
(And that's assuming you write some SQL to properly limit the joins to three rows.)
As for the report query you describe, you can get at the data you want with windowing functions. There are strategies for performing the pivot as well, but I'd likely do that in application code rather than in the SQL query.
If there's an index on pos, there's no cost to the sort.
Now I want a full select of those 800 users with their first three to-do items in neat columns next to the user.
Your select doesn't do that.
items[0].text + items[1].text + items[2].text
items.slice(0,2).map((e) => e.text).concat('');
Not really:
SELECT u.user, i.text
FROM users u,
LATERAL (SELECT * FROM items WHERE items.user = u.user ORDER BY items.pos DESC LIMIT 3) i;
My point being, there are some issues with regards to data purity and reasoning, particularly if you want a system where users can build custom reports.
And I just wish the original article highlighted that using floats would have these issues, and if writing SQL like this is important to you, then you might want to reconsider.
(As for your note in brackets, where I work, SQL is basically used as a scripting language. So we would do my example in SQL.)
[0] Yes, I know there is 'set rowcount', but you cannot do that within a sub select.
Are you looking for SELECT TOP 3 ...?
But you are right, I should have clarified that.
1. Subquery
SELECT * FROM (
SELECT u.user, i.text, row_number() OVER (PARTITION BY i.user ORDER BY i.pos) AS row
FROM users u INNER JOIN items i USING(user)
) numbered
WHERE row <= 3;
WITH numbered AS (
SELECT u.user, i.text, row_number() OVER (PARTITION BY i.user ORDER BY i.pos) AS row
FROM users u INNER JOIN items i USING(user)
)
SELECT * FROM numbered WHERE row <= 3;
SELECT user, text FROM (
SELECT u.user, text, row_number() OVER (PARTITION BY user ORDER BY rank) as rank
FROM users u
LEFT JOIN items using(user)
) ranked_items
WHERE rank < 4
Honestly I don't think there is a "best" solution here. Even in a "regular" programming language where you can easily use any data structure, it's not obvious which is best for maintaining the order.
Updating the order "value" of all the rows = moving a value around in an array (causing you to also shift a bunch of other values around).
Storing the ID of the row that should show up next in the list (not mentioned in the article, but mentioned in the comments below) = moving nodes around in a linked list.
Creating a new index that will fit in between two existing rows = inserting a value into a tree (because of the index).
It is a little bit trickier in a database, just because, no matter what you do, you also have to pay the price of putting something into a tree as well. Still... I can think of situations where I'd use any of these techniques. In general, this is not a problem with a clean solution for every use case.
https://medium.com/@Pinterest_Engineering/how-we-built-rearr...
int[]
And while the submission uses it as an example, the use case of reordering items in a list needn’t be limited to lists manually ordered by a user.
I use an unsigned int "pos" column in the db.
For a new list the "pos" starts with 1..n
When the user changes the order I find the largest "pos" in the list and with a for I set largest + n "pos" for every item.
There will be about 20 items in a list but let's just assume it's a 1000, so with this I'm good if the user edits the list less than 4 294 967 295 / 1000 times.
And if the largest + count(list) < lowest I can set the largest to zero and start over the pos with 1.
Curious if there is some obvious flaw with this plan or if I really need the power of true fractions.
Then wouldn't A and B both have a "SortVal" that's 1 less than C's SortVal? That would make your SortVals non-unique and order arbitrary.
Timestamp would only represent position and enables to put something in between, rather than an integer which adds +1. If put A (timestamp = 100) between B (timestamp = 200) and C (timestamp = 300), just set that order value to middle (150). Naive
It actually looks the same as "What about leaving room?" and, yeah, introduces complexity when you organize items for too long.
[1]: http://www.dbis.informatik.hu-berlin.de/fileadmin/lectures/W...
Personally, I'd probably add a second table with FKs to the todos table PK. That allows you to remove the calls to nexval. It doesn't remove the need for a processing language, but it's a much cleaner solution, I think.
That's fine if you sort everything on the front end though. It's product-dependent.
Like someone else said, usually these kinds of lists are small enough and PCs/databases are fast enough for it to not really matter.
Moreover once the relation data gets filtered (`WHERE`) then some links get broken/lost.
You could very easily build a link-list type datastore in SQL and use a CTE to build the list, but if your main use-case is viewing the list rather than updating the order, then it's a slower compromise than something like the solutions OP was discussing.
Pro: simple
Con: might as well use a flat file