5 ms·

I'll put in my vote for an 'ordering' type. Currently, supporting a feature like "users can reorder the items in a playlist" is typically done using an integer

I'll put in my vote for an 'ordering' type. Currently, supporting a feature like "users can reorder the items in a playlist" is typically done using an integer position column. However, this doesn't prevent gaps (so e.g. the third item in the playlist might have `position = 42`), and inserting between two other items requires updating every row with a greater position value. I'd like to be able to say `update ... set position = 3` to make the record the third item in the list. You'd need to be able to set the scope (eg `add column position ORDINAL WINDOW BY playlist_id` or something).

gurjeet 4y ago
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.
- forrest2 4y ago
  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 { id } ------------ playlist_members { id 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.
  - forrest2 4y ago
    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.
    - Tostino 4y ago
      This is the exact solution I came up with.
    - danielheath 4y ago
      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.
  - tshaddox 4y ago
    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.
    - eatonphil 4y ago
      > so that you could sort on the client You could probably also sort in the database with a recursive cte or with PL/pgSQL.
      - tshaddox 4y ago
        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.
  - KyeRussell 4y ago
    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.
  - topicseed 4y ago
    What if two rows use the same prev_playlist_member_id?
    - forrest2 4y ago
      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.
  - danielheath 4y ago
    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.
- tshaddox 4y ago
  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.
  - bastawhiz 4y ago
    > 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.html#DATATYPE-NUMERIC-DECIMAL https://www.postgresql.org/docs/current/datatype-numeric.htm...
    - tshaddox 4y ago
      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.
      - bastawhiz 4y ago
        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.
- danielheath 4y ago
  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.
gregwebs 4y ago
Maybe you could use the technique of maintaining a separate adjacency list column and materializing the ordering list. It would be a simplified version of what is done for hierarchy to materialize a nested set: https://www.sqlservercentral.com/articles/hierarchies-on-steroids-1-convert-an-adjacency-list-to-nested-sets https://www.sqlservercentral.com/articles/hierarchies-on-ste... A DB type could be nice to hide away the adjacency list. The other suggestion here to use fractional numbers is similar to materialized path (ltree data type in Postgres) and has been formalized to apply to hierarchies with Farey Fractions: https://sigmodrecord.org/publications/sigmodRecord/0506/p47-article-tropashko.pdf https://sigmodrecord.org/publications/sigmodRecord/0506/p47-...
- danielheath 4y ago
  If I were happy to rewrite the queries, I could use something like (forgetting the exact incantation)`select row_number(), rest_of_table as position partition by playlist_id order by position` to get the position column.

gurjeet 4y ago

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.

forrest2 4y ago
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 { id } ------------ playlist_members { id 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.
- forrest2 4y ago
  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.
  - Tostino 4y ago
    This is the exact solution I came up with.
  - danielheath 4y ago
    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.
- tshaddox 4y ago
  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.
  - eatonphil 4y ago
    > so that you could sort on the client You could probably also sort in the database with a recursive cte or with PL/pgSQL.
    - tshaddox 4y ago
      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.
- KyeRussell 4y ago
  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.
- topicseed 4y ago
  What if two rows use the same prev_playlist_member_id?
  - forrest2 4y ago
    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.
- danielheath 4y ago
  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.
tshaddox 4y ago
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.
- bastawhiz 4y ago
  > 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.html#DATATYPE-NUMERIC-DECIMAL https://www.postgresql.org/docs/current/datatype-numeric.htm...
  - tshaddox 4y ago
    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.
    - bastawhiz 4y ago
      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.
danielheath 4y ago
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.

gregwebs 4y ago

Maybe you could use the technique of maintaining a separate adjacency list column and materializing the ordering list. It would be a simplified version of what is done for hierarchy to materialize a nested set: https://www.sqlservercentral.com/articles/hierarchies-on-steroids-1-convert-an-adjacency-list-to-nested-sets https://www.sqlservercentral.com/articles/hierarchies-on-ste... A DB type could be nice to hide away the adjacency list. The other suggestion here to use fractional numbers is similar to materialized path (ltree data type in Postgres) and has been formalized to apply to hierarchies with Farey Fractions: https://sigmodrecord.org/publications/sigmodRecord/0506/p47-article-tropashko.pdf https://sigmodrecord.org/publications/sigmodRecord/0506/p47-...

danielheath 4y ago
If I were happy to rewrite the queries, I could use something like (forgetting the exact incantation)`select row_number(), rest_of_table as position partition by playlist_id order by position` to get the position column.