[forrest2]

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.

[danielheath]

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.

[Tostino]

This is the exact solution I came up with.