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

文系プログラマによるTIPSブログ

文系プログラマ脳の私が開発現場で学んだ事やプログラミングのTIPSをまとめています。

offsetの罠:その3:もっと対策

mysql

懲りずにmysqlのoffsetの遅さに立ち向かいます。
今回は少し実践っぽくするため、以下の住所データを使用して、offsetを使ったクエリの高速化を目指します。
住所データTSV

まず、以下のようにcreate tableをします。

drop table if exists address;
create table address (
    address_cd char(9) not null comment "住所CD"
    ,pref_cd char(2) not null comment "都道府県CD"
    ,city_cd char(5) not null comment "市区町村CD"
    ,town_cd char(9) not null comment "町域CD"
    ,zip_cd char(8) not null comment "郵便番号"
    ,office_flg bool not null comment "事業所フラグ"
    ,disabled_flg bool not null comment "廃止フラグ"
    ,pref_name varchar(4) not null comment "都道府県"
    ,pref_name_kana varchar(10) comment "都道府県カナ"
    ,city_name varchar(50) comment "市区町村"
    ,city_name_kana varchar(50) comment "市区町村カナ"
    ,town_name varchar(50) comment "町域"
    ,town_name_kana varchar(50) comment "町域カナ"
    ,town_name_extra varchar(100) comment "町域補足"
    ,kyoto_popular_name varchar(100) comment "京都通り名"
    ,street_name varchar(50) comment "字丁目"
    ,street_name_kana varchar(50) comment "字丁目カナ"
    ,extra varchar(191) comment "補足"
    ,office_name varchar(100) comment "事業所名"
    ,office_name_kana varchar(100) comment "事業所名カナ"
    ,office_address varchar(191) comment "事業所住所"
    ,new_address_cd char(9) comment "新住所CD"
    ,primary key (address_cd)
) engine=innodb character set=utf8mb4;

primary keyは住所CDです。

offsetを使ったクエリですが、一般的には以下のようなクエリを書いてしまいがちです。

select address_cd,pref_name,city_name,town_name
from address
where pref_cd in (1, 3, 5, 7, 9) and disabled_flg = false
order by pref_cd, city_cd, town_cd
limit 15000, 1000;

しかし、これはダメな例。explain結果は以下の通りです。

+----+-------------+---------+------+---------------+------+---------+------+--------+-----------------------------+
| id | select_type | table   | type | possible_keys | key  | key_len | ref  | rows   | Extra                       |
+----+-------------+---------+------+---------------+------+---------+------+--------+-----------------------------+
|  1 | SIMPLE      | address | ALL  | idx1          | NULL | NULL    | NULL | 201250 | Using where; Using filesort |
+----+-------------+---------+------+---------------+------+---------+------+--------+-----------------------------+

思いっきりフルスキャンして、且つoffsetしてます。内部的には以下のような動作になります。
全件取得→where句で不要レコードをフィルタ→offset位置まで移動→offset位置から100件取得
インデックスを追加

alter table address add key idx1 (pref_cd, city_cd, town_cd, disabled_flg);
+----+-------------+---------+------+---------------+------+---------+------+--------+-----------------------------+
| id | select_type | table   | type | possible_keys | key  | key_len | ref  | rows   | Extra                       |
+----+-------------+---------+------+---------------+------+---------+------+--------+-----------------------------+
|  1 | SIMPLE      | address | ALL  | idx1          | NULL | NULL    | NULL | 201250 | Using where; Using filesort |
+----+-------------+---------+------+---------------+------+---------+------+--------+-----------------------------+

あれ?idx1がキーの候補に挙がってるのに、ALL(フルスキャン)ですね。ちなみにクエリに要した時間は以下の通り。
1000 rows in set, 1 warning (0.27 sec)

MySQL で ORDER BY の解決にインデックスを使用できない場合は以下のとおりです(この場合も MySQL は WHERE 節の条件に一致するレコードの検索にインデックスを使用します)。
複数のキーに対して ORDER BY を実行する場合。
SELECT * FROM t1 ORDER BY key1,key2

http://dev.mysql.com/doc/refman/4.1/ja/order-by-optimisation.html

カバリングインデックスを使う。
これが本トピックの本題。カバリングインデックス(インデックスカバークエリ)を使います。

alter table address add key idx1 (address_cd, pref_cd, disabled_flg);
select a.address_cd,a.pref_name,a.city_name,a.town_name
from address a inner join (
    select tmp.address_cd
    from address tmp
    where tmp.pref_cd in (1, 3, 5, 7, 9) and tmp.disabled_flg = false
) cover using (address_cd)
order by pref_cd, city_cd, town_cd
limit 15000, 1000;

explainしてみる。

+----+-------------+------------+--------+---------------+---------+---------+------------------+-------+---------------------------------+
| id | select_type | table      | type   | possible_keys | key     | key_len | ref              | rows  | Extra                           |
+----+-------------+------------+--------+---------------+---------+---------+------------------+-------+---------------------------------+
|  1 | PRIMARY     | <derived2> | ALL    | NULL          | NULL    | NULL    | NULL             | 21190 | Using temporary; Using filesort |
|  1 | PRIMARY     | a          | eq_ref | PRIMARY,idx1  | PRIMARY | 36      | cover.address_cd |     1 |                                 |
|  2 | DERIVED     | tmp        | index  | NULL          | idx1    | 45      | NULL             | 82970 | Using where; Using index        |
+----+-------------+------------+--------+---------------+---------+---------+------------------+-------+---------------------------------+

1000 rows in set, 1 warning (0.19 sec)
おや、rowsも減り、インデックスが使われていて、尚且つ実行時間が短縮されてますね。
このクエリでは、以下のような動作になります。
1,サブクエリが先に処理される。サブクエリ内で使っている項目が全てインデックスに存在するので、
  完全にディスクアクセスの無いオンメモリの検索(インデックスカバークエリ)をしている。
  PKのaddress_cdしかselectしていないのがポイント。
2,addressを自己結合(inner join)して、件数を絞った後で、order byとlimit offsetを実行
  サブクエリでPKであるaddress_cdを取得しているので、簡単・最速で自己結合が可能となる。
  前述のようにorder byのインデックスが効かないので、最初からorder byのインデックス利用は諦める。
  但し、件数を絞ってからそれらを行えば、フルスキャンであっても速いのです。件数少ないから。

ポイントは以下の2点です。
1、1でカバリングインデックスで完全オンメモリでPKのみを検索している事。
2,事前にレコード数をwhere句で減らしてから、ソートとlimit offsetを実行している事。
この例では14万件しかないので大した実行時間の差が無いですが、レコード数が億単位になるとはっきり差がでるかと思います。
ちなみに、where句が多い場合、サブクエリ内のwhere句をインデックスが張れそうな項目のみにして、
残りのwhere句は外側のwhere句に書くとよいです。件数減らしてからのwhereなら、結構速いので。