Насколько дорого обходятся соединения в SQL? И / или каков компромисс между производительностью и нормализацией?

Отличная почта, обрабатывающая несколько случаев: от простых до промежутков до неравномерных с зазорами.

http://jan.kneschke.de/projects/mysql/order-by -rand /

Для наиболее общего случая, вот как вы это делаете:

SELECT name
  FROM random AS r1 JOIN
       (SELECT CEIL(RAND() *
                     (SELECT MAX(id)
                        FROM random)) AS id)
        AS r2
 WHERE r1.id >= r2.id
 ORDER BY r1.id ASC
 LIMIT 1

Это предполагает, что распределение идентификаторов равно, и что быть пробелы в списке идентификаторов. См. Статью для более сложных примеров