Create a randomly ordered playlist from a table of songs and return the name of the current, next, and previous song?

Question

Consider the following table:

Song
----
SongID GUID Primary Key
Name Varchar
dateAdded DateTime

I am creating a website that plays songs from the Song table. I want to generate a randomly ordered playlist for each visitor of the site that persists across requests without using any server-side storage (no session-style or database storage.) The player has Play, Next Song, and Previous Song buttons. What is the most efficient way to persist this data across requests? What is the most efficient query for this information? I have a solution (in mySql) that works, but I am looking to see if something more efficient works. Also, I don't want to bias the answers into using my solution. Please include a query in your answer.

Answer 1

You can use a Pseudo random sequence. Store a gseed and the playlist position in a cookie. The pseudo random seed will guarantee you re-create the same playlist sequence on each request, without actually storing the playlist on the server

Answer 2

Update: Here's the requirements that I followed, spelled out:

• No matter how many songs there are in the table or the current location in a playlist, the information the client is required to store (e.g. in a cookie) must have a constant size.
• Using 'next' 100 times followed by 'prev' 100 times should result in some sequence of 100 songs (possibly including duplicates) followed by that exact sequence reversed, regardless of any insertions that may have been made inbetween any 'next' or 'prev' action. ("Previous song always means the previous song.")
• A song that would have been in a playlist "when it was generated/initialized" and has since been deleted will be skipped.
  • Would not be hard to change my answer below to return a not-found indicator instead.

---

I think you need one more piece of information: a secondary song key of an integer position, in addition to your GUID (or you could replace it with this). Then, combined with a PRNG, you can do the most simple and quick lookup possible. Pseudocode:

def next_song(initial_seed, current_prng_index, high_song_index):
  """Returns the next song and the parameters to be later passed
  to next/prev_song."""
  while True:
    current_prng_index += 1
    current_seed = PRNG_advance(initial_seed, current_prng_index)
    song_index = song_index_from_seed(current_seed, high_song_index)
    song_id = (SELECT SongID FROM Songs WHERE SongIndex=song_index)
    if song_id: # test, somehow, for non-deleted songs
      return song_id, (initial_seed, current_prng_index, high_song_index)
      # include values that must be passed on the next call
# prev is the same, except uses -= 1

def song_index_from_seed(seed, highest):
  return seed % (highest + 1)
  # simple, but better possibilities might exist for your data

def new_playlist():
  """Returns the parameters to be passed to next/prev_song."""
  high_song_index = (SELECT MAX(SongIndex) FROM Songs)
  return get_a_random_number(), 0, high_song_index

This will get progressively slower on each next song and doesn't allow wrapping by going backwards (without some creativity). If you find a suitable reversible PRNG (though uncommon among good PRNGs, AFAIK):

def next_song(current_seed, high_song_index):
  while True:
    current_seed = PRNG_next(current_seed)
    song_index = song_index_from_seed(current_seed, high_song_index)
    song_id = (SELECT SongID FROM Songs WHERE SongIndex=song_index)
    if song_id: # test, somehow, for non-deleted songs
      return song_id, (current_seed, high_song_index)
      # include values that must be passed on the next call
# prev is the same, except uses PRNG_prev

This handles deletions by skipping those songs (or if you never delete that's not even an issue), but otherwise doesn't change the order no matter how many are deleted. Insertions are handled by the song_index_from_seed function, by constraining the index so new songs are never 'seen'. This is also an infinite loop if all the available songs have been deleted, but I think this code handles all other corner cases.

(Refactoring the next/prev versions to be simple wrappers around a common function isn't hard, but left out here to increase clarity.)

I've effectively replaced your dateAdded with my position index, but this is an improvement, since you don't need to keep deleted rows as dummies (but still cannot reuse their index) as you would if the position index was computed by ordering on dateAdded.

Using a PRNG like this seems naive, but works; and you'll have to be careful that the chosen PRNG and song_index_from_seed combination behaves as you expect: it's possible that some initial seeds appear to generate "non-random" playlists. (Not because they're not random, but because listeners expect a mix of songs instead of just 4, 4, 9, 9, ...)

Answer 3

Here is an idea that will make a pseudo-random ordering if the SQL. I don't have a database to test this on right now, so the actual SQL may need to be tweaked. I am also assuming that your ID column is integer.

Choose two multi-digit primes at random, P1 and P2 where P2 is greater than P1.

Select * from song order by (mod ( (ID * P2) , P1)), ID

The idea is to multiply the ID by one prime and then do a mod operation using P1. This should shuffle the songs fairly well and each prime pair will shuffle them differently.

To recreate the exact ordering you would only need to do is have P1 and P2 which should just be a few characters. No problem sending that back and forth during a request. You may need to experiment with your range of primes a bit, but I would guess using all the 4,5,6 digit primes should give you a pretty good number of ranomizations.