2014年03月12日

ここ最近の大規模サービス関連したデータページング考です。

mysql 5.5.34 で試して記事書いてます。 bigdata テーブルは id BIGINT UNSIGNED NOT NULL AUTO_INCREMENT, PRIMARY KEY (id) なカラムがある前提です。もちろん InnoDB です。

2014年なんだからCOUNT(*)とかSQL_CALC_FOUND_ROWSとかLIMIT OFFSETのページングはやめようぜ - Togetterまとめが発端にみえるけど、わりと昔から話されてる事なんだけど、「nippondanji SQL_CALC_FOUND_ROWS」でググっても有用な情報ないし文書化されてないからしとく。

SQL_CALC_FOUND_ROWS

ページング処理で使われがちな機能です。
SQL_CALC_FOUND_ROWS と言うのは LIMIT 付きのクエリでも、そのクエリから LIMIT を抜いたら実際何件の結果が取得できるかを計算してくれる MySQL 4.0 から追加された SELECT 文の拡張機能である。
SELECT SQL_CALC_FOUND_ROWS * FROM bigdata WHERE id > 10 LIMIT 10;
のように使うと、次のクエリでSELECT FOUND_ROWS();と打ち込むと LIMIT なしで得られるはずの行数が貰える。

ある程度のデータサイズのサービスを実践で開発していない人だと SQL_CALC_FOUND_ROWS はとても便利に使えます。しかし bigdata テーブルの中身が膨大になってくると徐々に「あれ、、どっかが重い。。。」っていう異変が出てくるんですね。

理由は単純で SQL_CALC_FOUND_ROWS を付けると、内部的には LIMIT 無しの状態で全てのレコードを読み込むまで処理をして、結果を返す時に LIMIT で指定された行数に絞り込んでるだけなんです。内部処理的には LIMIT してないので遅い。
簡単な理由です。

実際手元に1000万行近くかつ2GBくらいのデータの bigdata テーブルがあったのでSELECT * FROM bigdata WHERE id > 10 LIMIT 10;を実行すると即座に結果が帰るのに対してSELECT SQL_CALC_FOUND_ROWS * FROM bigdata WHERE id > 10 LIMIT 10;は30秒くらいかかってました。

「じゃぁ COUNT() 使えばいいじゃん」っていう突っ込みもあるでしょうがSELECT COUNT(*) FROM bigdata WHERE id > 10;も遅いしSELECT COUNT(*) FROM bigdata FORCE INDEX(PRIMARY) WHERE id > 10;も変わらないです。詰んでます。

両方とも、全ての結果行数を得る為には全部読み込まなきゃいけないのでとても遅い。


それでも何とか早く COUNT() する時にはnipondanjiさんの解説を良く読むといい。小さいサイズの index を読むだけで済むようにしたら早く COUNT() 出来るみたいな話である。
結局は結果の行数が多ければ多い程読む場所増えるので遅くなっていくんですけどね。


LIMIT OFFSET

これは、ページング処理で利用されやすいポピュラーな機能ですね。
というか SQL_CALC_FOUND_ROWS/COUNT() と組み合わせて「全件n件あるうちx行からy行まで表示しています」みたいな UI の為だけに使ってる人も多そう。

まぁこれも、マイクロなデータセットのサービスでは機能するでしょう。これが
SELECT * FROM bigdata WHERE id > 10 LIMIT 10 OFFSET 3000000;
とかになってくると事情は変わってきます。

これも理由は簡単ですが、与えられた条件から300万行目を正しく出す為に mysql は律儀に300万行分のデータに到達出来るまで条件判断していってるのです。
「この条件なら id=3000000 までスキップすれば良いじゃん」とか思う人も居るかもしれないけど、途中の行とか消されてたら無理ゲーすよね?

一つの index でクエリが処理出来れば少しは早くなるけど、それでも index の中を OFFSET の所まで読み進めるのでおそい。

(追記)あと、わりと言及が少ないけど URL パラメータに offset を渡す方式だと、レスポンスの HTML を作った後にユーザがリンクをクリックするまでの間にレコードの削除とか追加が行われて順番が変わった時に対応できないよね。ヘタするとさっき見せた行を次のページでももう一度出しちゃうよねってのある。

落とし穴

SQL_CALC_FOUND_ROWS を使う対象のクエリは件数が1000件以内とかの超小規模なので問題が起きないのは自明。
ページング処理で1000件以上のリクエストは受け付けないから LIMIT OFFSET でもほぼ問題が起きない。

などの意思を持って実装するかもしれませんが、自宅用のプログラムで無い限りは避けるべきです。
なぜなら自分以外の誰かがメンテナンスをする事になった時に、その誰かが良くわからないでコピペで新機能を作ってしまう、その新機能がわりとデカイデータを取り扱う仕様だった!
という状況は日常にありふれていて、そういう時に急にアラートが鳴りだしてオフィスから椅子が無くなってしまう。
そんな悲劇が起こりえるので、業務用のコードではなるべくこれらを使わないように行きていくのが処世術です。

ちなみに 他人=未来の自分 でもあるので、自分で自分の首を絞める可能性も大きい。

解決方法

SQL_CALC_FOUND_ROWS の件に関して言うなら、件数を取りたい WHERE 条件が index だけで済むケース等では、カウント用の別テーブル(例えば bigdata_count)を bigdata テーブルへの WHERE と同じ WHERE を処理出来るカラムと count 用のカラムを用意しておき bigdata 側の TRIGGER を仕掛けておいて、 bigdata テーブルに write 処理をするたびに bigdata_count を書き換えておく。そして検索時に bigdata テーブルへの検索と同時に bigdata_count テーブルも検索かければ時間がかかるスキャン等を行わないで、一度の index 探索で全件数取得が可能になる。
これは、検索条件に対する全件数表示がやむなく必要な時によく使う手段です。
(追記)いわゆるサマリーテーブルってやつです。

LIMIT OFFSET に関しては WHERE 条件の中に必ず PRIMARY KEY を含める事が可能になるような index を貼っておいて
SELECT * FROM bigdata WHERE id > ? ORDER BY id LIMIT 10;
のようなクエリを使います。次ページへのパラメータは上記クエリの最後の行の id の値を渡す事で OFFSET の代わりとなり得るのである。
しゅぱっ!と目的の OFFSET まで index で飛んでってさくっと結果を返すのでちょうはやい!

PRIMARY KEY 以外のカラムで WHERE した場合でも安心で、 WHERE 対象にちゃんと index が貼られてれば(常識的に index 貼ってないカラムに WHERE とかしないよね?) PRIMARY KEY 以外の index 定義では暗黙的に PRIMARY KEY が含まれたと同等になるので、KEY (foo)のような index を貼っておいてもWHERE foo=? AND id > ? ORDER BY idというクエリを投げても処理速度を落とさなくても同等の事が可能です。ただ EXPLAIN でちゃんと確認した上で必要なら FOURCE INDEX とかが必要です。
参考文献: 漢(オトコ)のコンピュータ道: 知って得するInnoDBセカンダリインデックス活用術!

暗黙的に主キーの値が含まれるのである。そのため、次のような検索は自ずとCovering Indexとなるため高速である。そして、ソートにもインデックスが利用される。

逆順ソートにしたい場合は普通に DESC とか付ければいい。

(追記の追記)
これじゃ次にページがあるかどうかわからない!っていう人のために、必要数 + 1 の数だけ LIMIT に指定して、結果が全部帰ってきたら最後の行だけ抜いて返して、 "hasNext":true みたいな response を返すといいと思います。
前のページが有るかどうかは UI 工夫してパラメータ引き回すでもいいし、そんなの信用出来ない場所だったら(SELECT * FROM bigdata WHERE id <= ? LIMIT 1 ORDER BY id DESC) UNION (SELECT * FROM bigdata WHERE id > ? LIMIT 10 ORDER BY id)とかして、前のレコードが存在してたら "hasMaenopage":true とか返せばいいですね。 UNION 使ったらクエリは一個なんでそんなにパフォーマンス落ちない。
(/追記の追記)


ちなみに index とかはりきれないような全文検索とか必要なケースだと Groonga を mysql の外部 index として利用してますね。
Groonga の _key に PRIMARY KEY をつっこんでる。え、ぐるんがってすとれーじえんじんだったけ、そうだっけぼくよくわかんない。

まとめ

SQL_CALC_FOUND_ROWS や LIMIT ? OFFSET ? でのページング処理がなぜ遅いのかと、その代替手段の紹介をしてみました。
もちろん「前へ 1 2 3 4 5 6 次へ」みたいなリッチなページングの実装には役に立たないかもしれません、でも果たしてそういったページング処理は本当に必要なんでしょうか?
「なんとなく Google っぽいのにしたいから」みたいな安易な理由じゃないですか?
正しくスケールするサービスを提供するには、企画書段階から UI の妥当性とパフォーマンスにどの程度影響するかを考えて取り組む必要があります。
UI を工夫する事でサーバ側の処理負担を大幅に減らせる機会は沢山あるので積極的にサービス全体を見ていく能力も2014年代のスケールするサービス構築には必要な能力だと思ってます。
それでもやっちゃいけないのが、技術的にむづいから企画をねじ曲げる事ですね。使える手段は常に多く持っておいて、適材適所できる人間になりたいものですね!

ちなみに SELECT * FROM bigdata WHERE id > ? ORDER BY id LIMIT 10; に一番相性がいいのはスマホのリストビューです。理由はきっと誰かがはてなに書く。

という事を「ISUCON3 の本戦行ったけど見事に空中分解して惨敗したよ」と「 CROSS 2014 コードレビューぶつかり稽古に登壇してきた」という報告の代わりとしてこのエントリを役立ててくださいということをもちまして、このエントリを〆させていただきます。

追記

ちなみにこれが具体的にどんなにコストがかかるかってことを僕は9年くらい前から mysql のソースコードレベルで理解していた。

深遠な理由でこれやって大変な事になってる人が「paging できる API とかは hasNext とかそういうのにすべき」って言ってた。サーバ側で totalRows みたいなのは出さないで hasNext/hasHitotumae みたいなのだけ返せば軽い API 設計ができるとかそういうの。

Posted by Yappo at 2014年03月12日 13:08 | TrackBack | tech
Comments
Post a comment









Remember personal info?






コメントを投稿する前に↓の場所にnospamと入力してください。