私が歌川です

@utgwkk が書いている

SQLite で ORDER BY RANDOM() を使わずに10連ガチャを実現する

技術

tl;dr

  • WITH RECURSIVE で主キーの乱数列を作って絞り込むと爆速

ナイーブな実装

SQLite でガチャを実装しようとすると通常次のようになるかと思われます．

SELECT * FROM idols ORDER BY RANDOM() LIMIT 10;

よく知られているように，このクエリは非常に重いです．45万件ほどのデータに対してこのクエリを投げると，結果が返ってくるまでに待たされることが多いです．

WITH 句で乱数列を生成する

WITH句でとりあえず仮想的な一時テーブルのようなものを作っていると考えてください．rowid はテーブルの主キーとします．

WITH random_id(id)
AS (
  SELECT ABS(RANDOM() % (SELECT MAX(rowid) FROM idols))
  UNION ALL SELECT ABS(RANDOM() % (SELECT MAX(rowid) FROM idols)) FROM random_id
)
SELECT DISTINCT id FROM random_id LIMIT 10;

これによって，0〜MAX(idols.rowid) の範囲をとる乱数列が生成できます．

rowid の乱数列で絞り込む

あとはこれを組み込んでみましょう．

WITH random_id(id)
AS (
  SELECT ABS(RANDOM() % (SELECT MAX(rowid) FROM idols))
  UNION ALL SELECT ABS(RANDOM() % (SELECT MAX(rowid) FROM idols)) FROM random_id
)
SELECT * FROM idols JOIN (SELECT DISTINCT id AS rid FROM random_id LIMIT 1000) ON idols.id == rid LIMIT 10;

こうして爆速の10連ガチャを実装することができました．よかったですね*1．

注意

  • 主キーが連番になってないときの動作は保証しません
  • 追記したのですが， WHERE id IN (SELECT DISTINCT id FROM random_id LIMIT 100000) による判定では偏りが出てしまいます．これは random_id の取得数を減らすか，もしくは上の修正されたクエリのように JOIN を使うことによって解決できるようです

おまけ: rowid について

SQLite のテーブルには必ず rowid という INTEGER PRIMARY KEY AUTOINCREMENT があるので*2，主キーを設定するの忘れてた……というときにも使うことができます． この主キーは隠しカラムであり，これを元にして主キーを再設定することができます．

*1:部内のガチャシステムが40倍高速になりました

*2:実は INTEGER の主キーはこれを参照している