MySQL TIPS 3 空間情報(geometry)を使って経度・緯度の検索を高速化する
以下のようなピタゴラスの定理を使った指定した経度緯度に最も近いデータを取得するSQLは結構ありがちですが、CPU負荷が高く効率も悪いのでMySQLに標準搭載となった空間情報(geometry)を使ってみることにします。
SELECT * FROM loc ORDER BY power(abs(latitude - 緯度 ), 2) + power(abs(longitude - 緯度 ), 2) LIMIT 1
MySQLの空間情報(geometry)機能はPostGIS(Postgresカスタマイズ)に比べると貧弱なので、その為の工夫を行います。例えばここのとおりのままだと逆にSQLが遅くなります。
まずは、テーブル定義から
- 通常のテーブル
CREATE TABLE IF NOT EXISTS `loc` ( `loc_id` int(11) NOT NULL auto_increment, `latitude` DECIMAL( 9, 6 ) NOT NULL DEFAULT '0', `longitude` DECIMAL( 9, 6 ) NOT NULL DEFAULT '0', PRIMARY KEY (`loc_id`), UNIQUE KEY `latitude` (`latitude`,`longitude`) ) ENGINE=MYISAM;
※ 経度・緯度にfloat型が使われていないのは、float型では計算に誤差が発生する為、MySQLで新しく追加された誤差が発生しない小数点型Decimalを使用する。(中身は文字列)。この型が追加される前は良くvarcharが使われていました。
- 空間情報を使用したテーブル
CREATE TABLE IF NOT EXISTS `loc_gis` ( `loc_id` int(11) NOT NULL auto_increment, `latlng` geometry NOT NULL, PRIMARY KEY (`loc_id`), SPATIAL KEY `spot_latlng_index` (`latlng`) ) ENGINE=MyISAM
実際のデータは国土交通省からデータを貰ってくるとして、インポートの手順を書くだけでちょっとめんどくさいので、ここは割愛。ここでは検証用にダミーデータを生成して対応する。
- 東京駅を起点としてランダムに1000万件のデータを生成
call insert_generate_series( 'loc(latitude,longitude)', 'cast(35.67832667+(RAND(?)*100) as DEC(9,6)),cast(139.77044378+(RAND()*100) as DEC(9,6))',1,10000000,1);
- loc_gisにlocからデータを流し込み
INSERT INTO `loc_gis` (`loc_id`,`latlng`) SELECT `loc_id` , GeomFromText(Concat('POINT(',longitude,' ',latitude,')')) FROM loc
両方のテーブルでのパフォーマンス比較
- 通常テーブル
SELECT SQL_NO_CACHE * FROM loc ORDER BY power(abs(latitude - 35.67832667 ), 2) + power(abs(longitude - 139.77044378 ), 2) LIMIT 1
- 1 row in set (31.37 sec)
- 空間情報を使用したテーブル
SELECT SQL_NO_CACHE loc_id,Y( `latlng` ) latitude ,X( `latlng` ) longitude FROM loc_gis ORDER BY GLength( GeomFromText( CONCAT( 'LineString(139.77044378 35.67832667,', X( `latlng` ) , ' ', Y( `latlng` ) , ')' ) ) ) LIMIT 1
- 1 row in set (1 min 50.40 sec)
あれあれ、空間情報(geometory)を使ったら逆に遅くなってしまいましたよ。explainを実行してみましょう。
id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | |
---|---|---|---|---|---|---|---|---|---|---|
1 | SIMPLE | loc_gis | ALL | NULL | NULL | NULL | NULL | 100000 | Using filesort |
....せっかくの空間インデックスが使われていませんね。これでは意味がないので、両方とも、経度・緯度共に±0.2の範囲に限定するようにWHERE句で範囲を限定してみます。空間情報(geometory)の方では矩形検索を使います。
- 通常テーブル
SELECT SQL_NO_CACHE * FROM loc WHERE latitude BETWEEN (35.67832667 - 0.2) AND (35.67832667 + 0.2) AND longitude BETWEEN (139.77044378 - 0.2) AND (139.77044378 + 0.2) ORDER BY power(abs(latitude - 35.67832667 ), 2) + power(abs(longitude - 139.77044378 ), 2) LIMIT 1
- 1 row in set (46.09 sec)
- explain
id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | |
---|---|---|---|---|---|---|---|---|---|---|
1 | SIMPLE | loc | range | latitude | latitude | 10 | NULL | 23387 | Using where; Using filesort |
- 空間情報を使用したテーブル
SELECT SQL_NO_CACHE loc_id,Y( `latlng` ) latitude ,X( `latlng` ) longitude FROM loc_gis WHERE MBRContains( GeomFromText( Concat('LineString(', 139.77044378 + 0.2 , ' ', 35.67832667 + 0.2 , ',', 139.77044378 - 0.2 , ' ', 35.67832667 - 0.2 , ')' ) ), latlng ) ORDER BY GLength( GeomFromText( CONCAT( 'LineString(139.77044378 35.67832667,', X( `latlng` ) , ' ', Y( `latlng` ) , ')' ) ) ) LIMIT 1
- 1 row in set (2.37 sec)
id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | |
---|---|---|---|---|---|---|---|---|---|---|
1 | SIMPLE | loc_gis | range | spot_latlng_index | spot_latlng_index | 34 | NULL | 28 | Using where; Using filesort |
explainしてみると今度はちゃんと空間インデックスが使われています。そして空間情報を使った方が高速になっています。
まとめ
- 空間情報(geometory)を使うときはWHERE句で矩形検索で範囲を限定する。じゃないと空間インデックスは使われないし、むしろ空間情報(geometory)を使った方が遅くなる。
- WHERE句で範囲を限定すると大幅に速度アップ!!問題点として、データが均一でない場合データが存在しない場合があり、その場合矩形の領域を拡大して再度検索する必要がある。事前にマップを作っておいた方がよい?
追記
- テストデータを1000万件に変更、これくらいのレコード数がないと比較できない程早いMySQL