Item — HN Reader

Use numeric data type instead of integer, and update the position to the midpoint of the other 2 you're trying to place the record between.

    update ... set position = (prev + next)/2;

To get better performance you can choose to use the float data type, but then you'd be limited to a fixed precision; sufficient for most cases, though.

3 comments

That still requires you to look up the element in the target position, instead of just saying “put this element in the 3rd position.”

Also, you’ll still eventually need to go clean up the entire sequence because you’ll run out of gaps between adjacent numbers. Because of this, I’d probably rather use a more predictable type (like one of the integer types) and explicitly plan my cleanup schedule.

> Also, you’ll still eventually need to go clean up the entire sequence

If you're using a numeric type, you get up to 16383 digits after the decimal. That's... Probably more precision than you'll be able to reasonably use up in almost any use case. Any time you're reordering in bulk, you're resetting the order value to a nice integer, so it would take many thousands of ad-hoc reordering operations near a single position to get it close to the precision limit, yeah?

https://www.postgresql.org/docs/current/datatype-numeric.htm...

Sure, but if it’s orders of magnitude more than you’ll ever need, you’re just using way more storage than you need. That’s what I meant by being more explicit about your plan and using more predictable storage. As a basic example, you could also use integer (or bigint) and start by number things like 1000, 2000, 3000, etc. Now you know exactly how many slots between items you have, and can more easily query for cases where you’re running low on slots.

Capacity doesn't mean storage. The default text field can store orders of magnitude more than I might need for a field, but that doesn't mean it takes orders of magnitude more storage.

Or model it as a linked list and you can sidestep the limitations / complexity of some kind of numeric (or bytes / text based ordering field)

------------

playlists {

}

------------

playlist_members {

playlist_id

prev_playlist_member_id

(and/or next_playlist_member_id)

song_id

}

------------

you could then just select * from playlist_members where playlist_id = ... and sort on the client side. you'd probably add an application limit where playlists have a max length of some kind.

re-orders can be done in a fixed number of row updates and typical application queries are still possible / fast.

or perhaps for some applications it would be sufficient to do

playlists {

  id

  song_ids []

}

-------------

and just store the ordering in an array. Some postgres drivers might start shitting the bed though at some gigantic array sizes, but a playlist probably has reasonable enough limits that you wouldn't have a big problem.

ID arrays can't use FK constraints (requested elsewhere in these comments), otherwise that would be pretty good. Performance-wise it means more IO than optimal, but that's not necessarily a huge problem.

This is the exact solution I came up with.

If you were going to enforce a maximum size so that you could sort on the client, I bet you could just use an integer and rewrite the entire sequence from 1 to N on every reorder operation. Unless you were expecting to have way more writes than reads, which is a little hard to imagine.

> so that you could sort on the client

You could probably also sort in the database with a recursive cte or with PL/pgSQL.

Indeed, but AFAIK that is still much slower than sorting on an indexed integer column, which probably means you still need to enforce a maximum list length.

Writing a linked list in the database might sound good in theory; as someone maintaining a system that uses that technique, please please please do not ever do it. You lose access to basically every database-provided consistency technique.

Usual downsides of linked lists apply (i.e. traditional limit/offset pagination isn’t really viable).

I’ve never considered doing this though! I imagine I must’ve come across some problem where this would’ve been better than whatever I came up with.

What if two rows use the same prev_playlist_member_id?

You make that impossible with application logic or constraints. Just like any linked list, you need to update the other pointers

Example constraint would be a unique index for the Playlist member table on the combination of Playlist id and previous Playlist member ID.

That's exactly what I want the ordinal type to do transparently under the hood, automatically touching the minimum possible rows when I specify EG `position = 3`. Bonus points if there's an autovacuum-style procedure to move records apart if they're sitting too close together.