【MySQL】大量データで LIMIT と OFFSET を使うと遅い

MySQL

1000万件くらいのテーブルがあって、
そこから LIMIT OFFSET でデータを取得するんだけど、
OFFSET の値が大きければ大きいほど、遅くなる。

なぜ遅いのか?
と思って EXPLAIN を実行したところ、
LIMIT OFFSET は テーブルフルスキャン(ALL) だった・・・。

なんとなくインデックスが効いているものだと思ってたが、
そうでもなかった。
--- 追記 2014/11/10 ---
コメントにて
「ALLになるのは、何らかのキーでソートしないとALLになります」
とのご指摘をいただきました。
----------------------

--- 追記 2014/06/13 ---
なぜかこの記事の閲覧数が増えていたので内容を再確認してみました。
レコード数が多くなると LIMIT OFFSET が遅いというのは間違いないと思う。
ただ、上記の「LIMIT OFFSET は テーブルフルスキャン(ALL) だった」というのは
テストで使ったテーブルで explain してみた結果なので、
テーブルによって違うかもしれません。
---------------------

ほとんどのテーブルには INTEGER型 の主キーが付いているので、
それを BETWEEN AND で指定する。
主キーにはデフォルトでインデックスが付いているので、
範囲検索(range)になる。

SELECT * FROM tb_test WEHRE id BETWEEN 9000000 AND 900100;
or 
SELECT * FROM tb_test WEHRE id >= 9000000 limit 100;

これは便利だ・・・。
ちなみに、LIMIT を使う場合は、採番に抜けがない場合にのみ有効。
抜けがある場合はBETWEENで始まりと終わりを指定しないと、
取得するデータが重複する可能性がある。