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.

This is the exact solution I came up with.

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.

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.

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.

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.