ねぎ嫌い

始業前に学んだことを小出しに。最近はHacker Newsの人気記事をまとめてみたり。

2017-10-16 Efficient pagination of a SQL table with 100M records

原文:allyouneedisbackend.com

巨大なデータを持つテーブルを効率的に読み込む方法についてのお話。

1億行のレコードを持つテーブルからデータを読み込む時、どのように読むべきか。

1. 明らかに間違った解決策

SELECT user_id, external_id, name, metadata, date_created FROM users;

シンプルに上のようにやってしまうと、処理は終わらない。

おそらく、取得するデータをすべてRAMに展開するためである。
あるいは、データを送る前のプリロードに時間がかかり、クエリーがタイムアウトをしている。
どちらにしろ、この方法でデータを取得することは出来ない。

2. ページング

SELECT user_id, external_id, name, metadata, date_created FROM users
ORDER BY user_id ASC LIMIT 0, 10 000;

データをページに入れて取得する方法がある。
データの取得順は物理的/論理的に保証されないため、ソートする必要がある。
これの実行時間は10 000 rows in set (0.03 sec)で行われている。

それでは、5,000ページ目を取得するとどうだろうか。

SELECT user_id, external_id, name, metadata, date_created FROM users
ORDER BY user_id ASC 
LIMIT 50 000 000, 10 000; --- 5 000th page * 10 000 page size

この実行時間は、10 000 rows in set (40.81 sec)となる。
確かに、めちゃめちゃ遅い。

さらに最後のページを取ろうとするとどうなるか。

SELECT user_id, external_id, name, metadata, date_created FROM users
ORDER BY user_id ASC
LIMIT 99 990 000, 10 000; --- 9999th page * 10 000 page size

実行時間は、10 000 rows in set (1 min 20.61 sec)となる。
実際に使うには、バックグラウンドで動くようなタスクにしか使えない。

実行時間のほかにもう1つ問題になりうるケースがある。
例えば、既に10ページめくっている状態(100,000 件のデータにアクセス)で、
次のページ(100,001 から 101,000)へアクセスしようとしている時を考える。
そのタイミングで、99,998と99,999レコードが消されてしまったら、
ページの最初の結果は、100,003からになってしまう。

つまり、ミュータブルなデータセットの場合、この方法は使えないということになる。

3. indexを利用したページング

一つ前と非常に似ているが、レコード数でページングをするのではなく、
indexのついたuser_idをオフセットとして利用している。
アルゴリズムとしては、以下のようになる。
1. テーブルからレコードのPAGE_SIZEを取得し、オフセットを0とする 2. 次ページのために取得したuser_idの最大値をオフセットとする 3. 現在のオフセットよりも大きいuser_idを取得する

1ページあたり10,000件のデータを持たせ、5,000ページ目を取得する場合は次のようになる。

SELECT user_id, external_id, name, metadata, date_created FROM users
WHERE user_id > 51 234 123 --- value of user_id for 50 000 000th record
ORDER BY user_id ASC
LIMIT 10 000;

驚くことに実行時間は10 000 rows in set (0.03 sec)とあるように、1000倍も速い。
user_idの値は連続的ではなく、例えば25345の次は25348となっている。
これならば、読み込む次のデータが消されても問題なく動作する。

まとめ

この記事では1億行のレコードを持つテーブルを読み込む時に、
プライマリーキーを指定しているオフセットを使うこととしている。