読者です 読者をやめる 読者になる 読者になる

mongoDBとMySQLのlimit offset skip

MySQL mongoDB

mongoDBにはMySQLのoffset limitに似たskip limitという機能がありますが、名前だけでなく機能的にも差異があります。

意外と知られていないようなのですが、MySQLでは以下のようなSQLで最初の10件を取り出す場合でもテーブルフルスキャンされてしまいます。

select * from hoge limit 10 offset 0 ;
mysql> explain select * from hoge limit 10 offset 0 ;
+----+-------------+-------+------+---------------+------+---------+------+------+-------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra |
+----+-------------+-------+------+---------------+------+---------+------+------+-------+
|  1 | SIMPLE      | hoge  | ALL  | NULL          | NULL | NULL    | NULL | 1000 |       |
+----+-------------+-------+------+---------------+------+---------+------+------+-------+
1 row in set (0.00 sec)

mongoDBでは期待通り10件目で検索を打ち切ってくれます。

db.Hoge.find().skip(0).limit(10);
> db.Hoge.find().skip(0).limit(10).explain();
{
	"cursor" : "BasicCursor",
	"nscanned" : 10,
	"nscannedObjects" : 10,
	"n" : 10,
	"millis" : 0,
	"nYields" : 0,
	"nChunkSkips" : 0,
	"isMultiKey" : false,
	"indexOnly" : false,
	"indexBounds" : {
		
	}
}

MySQL等のRDBのデータモデルは集合モデルであり、テーブルには順番という概念が存在していません。このため、まず最初に必要なデータを全て取得して、ソートした後でなければ、offset limitを適用することができないのです。

一方、mongoDBは、先日ブログに書いたようにnatural orderという順序付けをコレクションが持っているので、必要なデータだけ取得して処理を打ち切ることができます。

もちろん、mongoDBでもfindにsort条件があると必要なデータを取り出して並び替えるまで順番が不明になるので、途中で検索を打ち切ることはできなくなります。

> db.Hoge.find().sort({ date:1 }).skip(0).limit(10).explain();
{
	"cursor" : "BasicCursor",
	"nscanned" : 1000,
	"nscannedObjects" : 1000,
	"n" : 10,
	"scanAndOrder" : true,
	"millis" : 9,
	"nYields" : 0,
	"nChunkSkips" : 0,
	"isMultiKey" : false,
	"indexOnly" : false,
	"indexBounds" : {
		
	}
}

このような場合は、sort条件となるフィールドにB-Treeインデックスを作成しておくと、取得時にインデックスの順番が利用されてフルスキャンが回避されます。

> db.Hoge.ensureIndex({date: 1});
> db.Hoge.find().sort({ date:1 }).skip(0).limit(10).explain();
{
	"cursor" : "BtreeCursor date_1",
	"nscanned" : 10,
	"nscannedObjects" : 10,
	"n" : 10,
	"millis" : 7,
	"nYields" : 0,
	"nChunkSkips" : 0,
	"isMultiKey" : false,
	"indexOnly" : false,
	"indexBounds" : {
		"date" : [
			[
				{
					"$minElement" : 1
				},
				{
					"$maxElement" : 1
				}
			]
		]
	}
}

MySQLではB-Treeインデックスを持つカラムでsortしてもフルスキャンされてしまいます。limit offsetの適用は取得・並び替えの後なので、取得時点でインデックスの順番を利用できないのです。

mysql> explain select * from hoge order by date limit 10 offset 0 ;
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra          |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
|  1 | SIMPLE      | hoge  | ALL  | NULL          | NULL | NULL    | NULL | 1063 | Using filesort |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
1 row in set (0.00 sec)

ただしMySQLでもB-Treeインデックスの順番をlimit、offsetで利用できる方法があります。ヒントはテーブルには順番がないという点、逆に言うとインデックスだけで処理が完結すれば、その順番が利用可能であるという事です。

mysql> explain select h1.* from hoge h1 inner join (select id from hoge order by date limit 10 offset 0) h2 on h1.id = h2.id;
+----+-------------+------------+--------+---------------+------------+---------+-------+------+-------------+
| id | select_type | table      | type   | possible_keys | key        | key_len | ref   | rows | Extra       |
+----+-------------+------------+--------+---------------+------------+---------+-------+------+-------------+
|  1 | PRIMARY     | <derived2> | ALL    | NULL          | NULL       | NULL    | NULL  |   10 |             |
|  1 | PRIMARY     | h1         | eq_ref | PRIMARY       | PRIMARY    | 4       | h2.id |    1 |             |
|  2 | DERIVED     | hoge       | index  | NULL          | date | 8       | NULL  |   10 | Using index |
+----+-------------+------------+--------+---------------+------------+---------+-------+------+-------------+
3 rows in set (0.00 sec)

MySQL高速化の常套手段 type index なクエリが利用できます。