最近のWebサービスでは、外部APIを活用したものが非常に多くなっています。前回は外部APIのアクセス数制限を回避するためのキャッシュ、及び具体例として位置情報サービスのfoursquare APIの結果をキャッシュする仕組みを設計しました。今回は、MySQLに保存された位置情報データのキャッシュをMySQL Spatial Extensionsを使って検索する方法について説明します。

はじめに

Retty株式会社の鹿島です。前回は、最近のWebサービスでよく使われている外部のAPIおよびサービス停止に致命的な影響を与えかねないrate limitについて説明しました。またrate limitの超過を防ぐための「キャッシュ」という方法についても説明しました。

具体例として、位置情報SNSサービスであるfoursquareのAPIを取り上げ、その結果をキャッシュする仕組みの基本的な設計を説明しました。ポイントとしては、以下の通りです。

lat(=latitude=緯度)、lng(=longitude=経度)、検索キーワードの組み合わせをキャッシュのキーとする
APIから返されるJSONをそのままキャッシュする
キャッシュされたデータからlat, lngを用いて検索する際には、lat, lngにある程度の幅を持たせて検索する

今回は、MySQLで位置情報を扱うためのMySQL Spatial Extensionsについて説明した後、結果をキャッシュするためのテーブル、必要な関数の定義を行い、最後にテーブルに格納された位置情報を検索する方法について説明します。

MySQL Spatial Extensions

MySQLは、位置情報を扱うために以下のような仕組みを用意しています。

位置情報を保存するためのデータ型（POINT、GEOMETRYなど）
位置情報を扱うための関数群
位置情報の検索を効率的に行うためのインデックス（Spatialインデックス）

MySQLには位置情報を扱うためのデータ型が用意されています。「位置情報」と書きましたが、実際には位置（点）だけでなく、直線、ポリゴン及びそれらが複数集まったデータを扱う事ができます [1] 。本記事ではこれらを総称して「Spatialデータ型」と記述します。

以下、基本データ型のみ記載します。

POINT型:: 点を表現するデータ型
LINESTRING型:: 線を表現するデータ型
POLYGON型:: 平面を表現するデータ型
GEOMETRY型:: GEOMETRY型のカラムには、POINT、LINESTRING、POLYGON型の値は、どれでも入れることができます。

Spatialデータ型をサポートするストレージエンジンは、MySQL 5.0.16以降のMyISAM、InnoDB、NDB、ARCHIVEの4つです。

詳細はマニュアルの以下の項を参照して下さい。

http://dev.mysql.com/doc/refman/5.1/ja/mysql-spatial-datatypes.html

なお、MySQLのSpatialデータ型は、OpenGIS標準で定義されている「Class」に対応しています [2] 。詳細は以下のマニュアルページを参照して下さい。

http://dev.mysql.com/doc/refman/5.1/ja/opengis-geometry-model.html

[1]	本記事では、「位置情報」と書いた場合には、特に断りがない限り各種地理情報を含みます。

[2]	MySQLのSpatial ExtensionsはOpenGISに完全に準拠しているわけではありません。

位置情報を扱うための関数には、以下のようなものがあります。

Spatialデータ型の値を作成するための関数(例：緯度経度を表す文字列からPOINT型の値を作成する、等)
Spatialデータ型の各種プロパティ(次数等)を取得する関数
2つのSpatialデータの関係を調べる関数(例：平面Aと平面Bは交わっているか、等)

該当するマニュアルページは以下になります。

http://dev.mysql.com/doc/refman/5.1/ja/analysing-spatial-information.html

今回は、ある地点から半径100m以内にデータがあるかを調べたいので、3のタイプの関数、具体的には2点間の距離を計算する関数が必要になります。ただし前述の通り、MySQLはOpenGISに完全に準拠しているわけではないので、残念ながら2点間の距離を計算する関数が最初から用意されていません。そのため、このような計算をする関数を新たに定義する必要があります。これについては後ほど説明します。

位置情報の検索を効率的に行うためのインデックス（Spatialインデックス）

ご存知の通り、データベースにおけるインデックスとは本の目次のようなもので、テーブル内の目的とする情報に素早くたどりつけるよう、あらかじめ作成しておく情報です。

数値、文字列等の通常のデータ型であれば、MySQLの場合b-treeを使用しますが [3] 、Spatialデータ型のカラムにb-treeインデックスを貼っても、インデックスは使われず、検索速度は向上しません [4] 。

MySQLには、Spatialデータ型のカラムの値を効率的に検索するためにSpatialインデックスというインデックスが存在します。Spatialデータ型のカラムにSpatialインデックスを貼ることにより、位置情報を高速に検索できるようになります。

なお、現状ではSpatialインデックスが使用できるのは、ストレージがMyISAMに限られるという制約があるため、テーブル設計の際に気をつける必要があるかもしれません（トランザクション処理が必要なデータとは別テーブルにする等）。

[3]	一部のストレージエンジンの場合、ハッシュインデックスも使用可能

[4]	2点が等しいかどうかの検索の場合にはb-treeインデックスが使用されます

MySQLの定義

前節ではMySQL Spatial Extensionsについて説明しましたので、ここではそれらの機能を使って実装を進めていきます。 MySQLのSpatialデータ型の違いについて最初に説明しましたが、今回lat、lngの保存にはPOINT型を使います。

テーブル定義は以下の通りになります。

CREATE TABLE IF NOT EXISTS `cache_fs_search` (
  `cache_id` int(11) NOT NULL AUTO_INCREMENT,
  `latlng` point NOT NULL,
  `keyword` varchar(255) DEFAULT NULL,
  `result_json` mediumtext NOT NULL,
  `create_datetime` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  PRIMARY KEY (`cache_id`),
  KEY `keyword` (`keyword`),
  SPATIAL KEY `latlng` (`latlng`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8;

ポイントは以下の通りです。

latlngカラムにspatial indexが付いている
ストレージエンジンはMyISAMを使用

latlng、keywordをキーとして検索して、result_jsonカラムの結果を取得します。

今回は「ある地点から半径100m以内のデータがあるか」を調べたいので、2点間の距離を計算する関数が必要になりますが、前述の通りMySQLにはそのような関数は存在しません。そこで、以下のように2点間の距離をメートルで返すユーザー定義関数（distance_in_meter）を用意します。

DELIMITER $$
DROP FUNCTION IF EXISTS `dbname`.`distance_in_meter` $$
CREATE FUNCTION `distance_in_meter`(a POINT, b POINT) RETURNS double
DETERMINISTIC
COMMENT 'distance function'
BEGIN
RETURN round(glength(linestring(a, b)) * 111000);
END $$
DELIMITER ;

この関数の内容については、中学（あるいは高校？）で習う数学で理解できるかと思いますが、少し説明します。

111,000という数字は(地球の円周)/360です。地球は完全な球形ではありませんが、今回は正確な数値は求められていませんのでこの程度で十分です。
glength(linestring(a, b)) は図中の赤い線の部分に相当しますが、lat、lngの単位は角度ですので、2点間の中心角に相当します。a, bが離れている場合は誤差が大きくなりますが、約100m以内かどうかが分かればよいため、この程度の計算で十分です。

以上で、位置情報を検索するための準備は整いました。

位置情報の検索

実際にキャッシュを検索する際には、lat、lngに加えて「キーワード」をキーとして検索しています。しかし今回はMySQL Spatial Extensionsの説明を趣旨にしていますので、ここではキーワードなしでの検索を例に説明します。

まずテストデータをいくつか作成します。お好きなプログラム言語でlat、lngの組み合わせをランダムに作成して、以下のようなSQLを実行して下さい。lat、lngのばらつきにもよりますが、データ数は10,000レコード位あればとりあえず十分です。

INSERT INTO cache_fs_search (latlng, result_json)
VALUES (GeomFromText('POINT(35.00000 139.0000)'), 'test result')

GeomFromText関数で 'POINT(35.00000 139.0000)' という文字列をSpatialデータ型の値に変換しています。

なお、ここではX軸をlat(緯度)に、Y軸をlng(経度)に取っていますが、地図上でX軸が垂直方向でY軸が水平方向なのが気持ち悪いと思う方は逆にしても構いません。システム内部で統一されていればどちらでもいいと個人的には考えています。

前節で作成したdistance_in_meter関数を使用して、以下のようなSQLである地点（この例ではlat=35.691147、lng=139.702084）から100m以内のデータを取得できます。

SELECT cache_id, x(latlng) as lat, y(latlng) as lng, result_json,
   distance_in_meter(latlng,
                     PointFromText('POINT (35.691147 139.702084)')) d
FROM `cache_fs_search`
WHERE distance_in_meter(latlng,
                        PointFromText('POINT (35.691147 139.702084)')) < 100

実はこの方法には、latlngカラムにつけたインデックスが使用されないという問題があります。ユーザー定義関数であるdistance_in_meter関数を用いた検索にはインデックスが適用できないことが原因です。

EXPLAINステートメントの結果は以下の通りです。

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	cache_fs_search	ALL	NULL	NULL	NULL	NULL	8797	Using where

EXPLAINの結果についてまず見るべき所は「type」です。このSQLの場合、typeがALLとなっていますので、テーブル全走査が実行されることが分かります。

EXPLAINステートメントに関しての詳細は以下のマニュアルページを参照して下さい。

http://dev.mysql.com/doc/refman/5.1/ja/explain.html

Spatialインデックスが使われるように検索

ユーザー定義関数であるdistance_in_meter関数ではlatlngカラムに付けられたSpatialインデックスは使用されませんでしたが、MySQLで最初から用意されているMBRWithin関数であればインデックスが使用されます。

従って、MBRWithin関数を使って、以下の通り対処が可能です(図参照)。

検索したい位置を中心とした直径200mのバウンディングボックス内の結果を、MBRWithin関数を使用して取得
得られた結果のうち距離が100m以内のものをフィルターして使用

具体的には以下のようなSQLを使用します。

SELECT cache_id, x(latlng) as lat, y(latlng) as lng, result_json,
       distance_in_meter(latlng,
                         PointFromText('POINT (35.691147 139.702084)')) d
FROM `cache_fs_search`
WHERE MBRWithin(latlng, GeomFromText('POLYGON ((35.692047 139.701184,
                                                35.692047 139.702984,
                                                35.690247 139.702984,
                                                35.690247 139.701184,
                                                35.692047 139.701184))'))
  AND distance_in_meter(latlng,
                        PointFromText('POINT (35.691147 139.702084)')) < 100

前にも登場したGeomFromText関数により、'POLYGON ....'という文字列からSpatialデータ型の一つであるPOLYGON型の値を生成しています。

POLYGONでは、バウンディングボックスの4頂点の座標をぐるっと一周り指定します。始点と終点で同じ頂点を指定しますので、合計5つの座標を渡すことに注意して下さい。また、カッコの数も紛らわしいですが、数を間違えないようにしましょう。

WHERE句ではまずMBRWithin関数により、latlngがバウンディングボックス内にあるかが判定され、その上でdistance_in_meter関数により半径100mの円内にあるかの判定が実行されます。

このSQLのEXPLAINの結果は以下の通りです。select_typeがrange、possible_keysがlatlngとなっていますので、latlngに貼られたSpatialインデックスが使われていることが分かります。

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	cache_fs_search	range	latlng	latlng	34	NULL	1	Using where

上に挙げたSQLは、実際にはもう少しだけ簡単に書くことが出来ます。

SELECT cache_id, x(latlng) as lat, y(latlng) as lng, result_json,
       distance_in_meter(latlng,
                         PointFromText('POINT (35.691147 139.702084)')) d
FROM `cache_fs_search`
WHERE MBRWithin(latlng, GeomFromText('LINESTRING (35.692047 139.701184,
                                                  35.690247 139.702984)'))
  AND distance_in_meter(latlng,
                        PointFromText('POINT (35.691147 139.702084)')) < 100

MBRWithin関数に渡すバウンディングボックスですが、POLYGONではなく対角線を表すLINESTRINGを渡すことにより、同じ結果を得ることが出来ます。

EXPLAINの結果も同じですので、ここでは省略します。

まとめ

今回は以下の内容を説明しました。

MySQL Spatial Extensionsの機能について
Spatialデータ型を使用したテーブルの作成
MySQLに存在しない2点間の距離を算出するユーザー定義関数の作成
位置情報を検索する際に、Spatialインデックスが使用されるようなSQL

次回は引き続き「Webサービスにおける外部APIの使用」というテーマに関連して、Facebook API、そしてFacebook Query Language（FQL）について書こうと思います。

執筆者紹介
鹿島和郎
ソーシャルグルメサイト「Retty」の開発・インフラ全般を担当。過去には米企業でのオフショア開発拠点の立ち上げから国内SIerでの運用保守業務まで、広く浅く経験している何でも屋。
Rettyは、「行った」お店の投稿・共有、友達・趣味嗜好の合う人のオススメから「行きたい」お店をリスト化、スマートフォンで現在地周辺のお店をリストから検索などできるサービスで、Facebook、Twitterアカウントがあれば無料で使用可能。PC、iPhone、Androidに対応。

O'Reilly Japan Blog