Hatena::ブログ(Diary)

イノベートな非日常 Twitter

2010-07-23

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

なまええなまええ 2012/09/29 02:44 MBRContainsの範囲が、日付変更線(180度)をまたぐ場合と赤道をまたぐ場合に正しく動作しないみたい。
MySQL 5.5

投稿したコメントは管理者が承認するまで公開されません。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証