Я долго думал как без костылей, а только на уровне базы (PostgreSQL) сделать быстрый select * from table order by random(); К сожалению ничего хорошего найти не получилось. Вот explain на базе из около 300 000 записей:

     Limit  (cost=29127.46..29127.71 rows=100 width=358) (actual time=2531.542..2531.900 rows=100 loops=1)

       ->  Sort  (cost=29127.46..29850.98 rows=289406 width=358) (actual time=2531.536..2531.658 rows=100 loops=1)

             Sort Key: (random())

             Sort Method:  top-N heapsort  Memory: 67kB

             ->  Seq Scan on wall_wallpapper  (cost=0.00..18066.58 rows=289406 width=358) (actual time=0.033..1139.509 rows=276459 loops=1)

     Total runtime: 2532.240 ms

Не очень быстро. Очевидным решением было генерировать массив случайных значений на уровне кода и выбирать жанные по ключу. Чтобы выбирать по сгенерированным в коде значениям нам нужен непрерывный интервал значений (чтобы не было “дырок”). Это решение мне не очень нравится, но работает оно очень быстро. Итак для этого я создал таблицу с непрерывным интервалом значений, и ключом на исходную таблицу (в моем случае таблицу с обоями) -

Column  |  Type   |                         Modifiers                          | Storage | Description 

–––+–––+––––––––––––––––––––+–––+––––-

 id      | integer | not null default nextval(‘wall_wallhash_id_seq’::regclass) | plain   | 

 h_id    | integer | not null                                                   | plain   | 

 w_id_id | integer | not null                                                   | plain   | 

Indexes:

    “wall_wallhash_pkey” PRIMARY KEY, btree (id)

    “wall_wallhash_h_id_key” UNIQUE, btree (h_id)

    “wall_wallhash_w_id_id” btree (w_id_id)

Foreign-key constraints:

    “wall_wallhash_w_id_id_fkey” FOREIGN KEY (w_id_id) REFERENCES wall_wallpapper(id) DEFERRABLE INITIALLY DEFERRED

Has OIDs: no

 В коде я генерирую случайные значения в интервале от 0 до max() значения таблицы ключей. И выбираю данные примерно следующим запросом - 

    select * from wall_wallpapper where active=TRUE and id in (select w_id_id from wall_wallhash where h_id in (23260,79052,115503,235463,22031,17547,91859,95542,17186,244111,136111, …. 101076,218414,227782,120009,25861))

     Nested Loop  (cost=722.88..1526.57 rows=100 width=358) (actual time=3.687..6.449 rows=100 loops=1)

       ->  HashAggregate  (cost=722.88..723.88 rows=100 width=4) (actual time=3.605..3.740 rows=100 loops=1)

             ->  Bitmap Heap Scan on wall_wallhash  (cost=397.92..722.63 rows=100 width=4) (actual time=2.180..3.390 rows=100 loops=1)

                   Recheck Cond: (h_id = ANY     (‘{23260,79052,115503,235463,22031,17547,……..101076,218414,227782,120009,25861}’::integer[]))

                   ->  Bitmap Index Scan on wall_wallhash_h_id_key  (cost=0.00..397.90 rows=100 width=0) (actual time=2.140..2.140 rows=100 loops=1)

                         Index Cond: (h_id = ANY     (‘{23260,79052,115503,235463,….. 227782,120009,25861}’::integer[]))

       ->  Index Scan using wall_wallpapper_pkey on wall_wallpapper  (cost=0.00..8.01 rows=1 width=358) (actual time=0.021..0.023 rows=1 loops=100)

             Index Cond: (wall_wallpapper.id = wall_wallhash.w_id_id)

             Filter: (wall_wallpapper.active)

     Total runtime: 6.737 ms

Как видно время уменьшилось почти в 400 раз! И чем больше база тем больше будет разница в этих значениях. 

Очень жаль, что в order by random() работает так невыносимо медленно.

Поддержка таблицы с непрерывным интервалом в актуальном состоянии. 

У меня было 2 мысли как обновлять таблицу непрерывных значений в случае удаления записей (т.к. если ее не обновлять появятся “дырки” на интервале). Первый варинт — триггеры, безусловно самый быстрый. Но я от него отказался в пользу переопределения методов save()/delete() у джанговской модели — т.к. в данном случае проще контролироть процесс в случае ошибки, а большая скорость на delete()/save() мне не нужна. 

С методом save() все просто — добавляем новое значение в интервал (max()+1). Для метода delete() — берем максимальное значение интервала и обновляем эту запись -> затыкаем им дырку образовавщуюся в результате delete(). Вот собственно и все.