A user-defined order *is* an explicit index. EDIT: To expand further, I would ge...

A user-defined order is an explicit index.

EDIT: To expand further, I would generally model a playlist as its own tables anyways. Something like:

  CREATE TABLE playlist (
    id ID_TYPE_FOR_DB PRIMARY KEY,
    name varchar(4096), /* Or whatever storage size makes sense */
  )

  CREATE TABLE playlist_entry (
    id ID_TYPE_FOR_DB PRIMARY KEY,
    song_ref ID_TYPE_FOR_DB FOREIGN KEY REFERENCES songs(id),
    order INT, /* Or bigint or whatever you want */
  )