ちずぶらりHackers

オープンソースの古地図/絵地図アプリ基盤、Maplat開発してます。同種のソリューションに対する優位性は、色々ありますが一番は、あらゆる地図間で双方向1対1座標変換可能な点です。会津若松のサンプル試してみてください。=> http://bit.ly/aizumap

mysql空間拡張とGeoHash, quadkeyについて検索速度を比較してみた & quadkeyって何?の紹介

1週間程前かな?退社間際にやったSQL調整がどうしてもうまくいかず、100ms程度だった検索速度が空間検索条件を外すと爆速になったので、十分な確認もなく短絡して、Twitterで「mysqlの空間検索遅過ぎる!使えねー」と呟いてしまいました。
明日になればGeoHashとかquadkey*1のような一次元空間コード検索に変更してやるぞと。
が、翌日取り急ぎ検索条件をquadkeyに変更してやっても、特に速くならない。
あり?と思ってよくよくさらにチェックしてやると、複合検索のプロファイルの見方を間違えてて、テーブル間のリレーションキーで非空間テーブル=>空間テーブルの向きは主キーでリンクされてたけど、その逆はリレーションキーにインデックスを張ってなかったので、オプティマイザの選択が先に非空間テーブルの検索条件=>フィルタされたレコードに対し逐次空間検索、となっていたのが遅い原因でした。
非空間テーブル側のリレーションキーにインデックスを張ってやると、空間検索が優先され、空間インデックスが効いて数ms程度の速度が確保できました。

いわば空間DBの名誉を傷つけるような事を調査不十分で言ってしまったわけで、これは汚名返上のための情報提供をせんと怒られるだろうなあ、という事でやってみました。
2年間スタンドアローンに近いiPhoneアプリ作り続けて、Web開発の世界から離れていたので、2年前に似たような議論と調査があったこともすっかり忘れてしまってましたが、若干温度の違う結果も出ましたし、その頃との差はquadkeyの存在もあるので、共有します。
一応業務上も必要なこともあり、調査自体は業務中に行ったので、GeoHashは落ちてたコードを流用しましたがquadkeyは同僚と2人で新しくコードを作ったりしたものの、それらのコードの公開は差し控えます。
取り急ぎ結果のみの共有。

やってみた

実験条件は、日本の範囲に近い北緯20度〜50度、東経120度〜150度の領域に、ランダムに100万点のポイントを散りばめて、空間カラム、GeoHash、quadkeyの3値に直した形でレコード*2に持つテーブルを、MyISAMInnoDBでそれぞれ準備。
もちろん、システム非対応のためにインデックスを張れないInnoDBの空間カラム以外は、全てインデックスを張っています。
MyISAMInnoDB両方準備した理由は、空間カラムを使えない最大の理由は取り回しのしにくいMyISAMであることだと思うので、それは取りも直さずGeoHashを使うような用途ではInnoDBが使われているという事であり、それは両方を比較しないとよくないよね、という事で。

走らせた検索は、ある点を中心に半径10kmの検索。
空間検索は空間インデックス/GeoHash/quadkey問わず、いきなり円内検索はできず、まず円を内包する矩形で検索し、その後中心との距離を計算してフィルタしてやるしかないので、検索結果比較としては、

  • 事前の矩形検索時の、検索速度の比較
  • 事前の矩形検索で、本来必要な検索結果数と比較してどれくらい余分に拾ってしまったか
  • その後の円内篩いまで実行した結果の、検索速度の比較(SQL上でやってます)

を並べます。
また、GeoHash、quadkeyの初期矩形選出には、都度完全に最適な矩形を選ぶ事ももちろんできますが、そこまではせずに、中心点がメッシュ内のどこにあっても半径全体を含むのが確実なメッシュサイズに対して、近傍9メッシュを選出し検索する、という形*3を採っています。
検索速度は各々5回試行の平均、5回のうち最初2回は各sql交互に実行、3回は同じsqlを連続実行しています*4

結果は以下の通りです。

実施条件 ふるい前実行時間 ふるい前検索数 最終*5実行時間 最終検索数
空間検索*6:MyISAM 0.78ms 43 0.86ms 36
quadkey*7:MyISAM 1.96ms 269 3.22ms 36
GeoHash*8:MyISAM 1.52ms 664 7.04ms 36
quadkey:InnoDB 1.04ms 269 2.00ms 36
GeoHash:InnoDB 1.08ms 664 4.36ms 36

やっぱり、空間検索を使うと大分速いです。
つうか、100万件の日本中のランダムな点の中から、10km円内の36点を検索するのに0.86ミリ秒ってすごくないですか?
もちろん、MyISAMでしか使えないことはかなりイタいです。
頻繁に更新されるユーザの登録データなんかをMyISAMで運用したら、確かにいろいろ運用面でウザい問題は出てくると思います。
が、世の中頻繁にトランザクションしたり管理したりするデータだけではないはず。
Appleじゃないですが、自分たちで更新はせず基本的に他業者から買ってくるPOI、リードオンリーのデータであれば、MyISAMでもそこまで問題ないのでは?
もちろんコードの流用やメンテナンスの問題もありますが、これだけパフォーマンス差があるなら、GeoHashを使った情報ばかり溢れてるからなんでもGeoHash使うよ、じゃなくて、適宜空間検索も使われていいと思います。

もし空間検索でもおっつかないような規模の検索をされる場合は、最近話題のMapion本を読んで、Solrの空間検索等を試されるといいと思います。
私は別の部署にいたので経験ないんですけど。

Mapion・日本一の地図システムの作り方 (Software Design plus)

Mapion・日本一の地図システムの作り方 (Software Design plus)

quadkeyって何?

どうしてもInnoDBを使わないといけない場合は、前方一致一次元コードを使うしかないですが、その場合今はGeoHashを使う事が流行ってますけど、個人的にはquadkeyを使った方がいいんじゃないかなと思ってます。
quadkeyって何?と聞いた事もない人がいると思いますが、Microsoftが提唱している、位置情報の符号化手法です*9
特徴は、以前の記事でも採り上げた、Google Mapsが発明した画期的な地図配信手法であるタイル配信がありますが、その配信タイルの木構造そのものを、そのままコード化したものです。
言わば、当世風靡する天才会社GoogleMicrosoftのコラボで生まれたような規格といえるでしょうか。

quadkeyの特長

quadkeyは地図タイルと連動している規格のため、地図タイルが持つ特長を全て備えています。

コードメッシュの形が、実距離に置いても正しく正方形

Web地図というのはメルカトル図法が使われていて、メルカトル図法の悪名は、やれ「赤道付近と極付近で、描画の大きさが異なる」とか「日本の東は北アメリカじゃなくて南アメリカだ」とか、いろいろ聞いた事があると思います。
が、メリットもたくさんあります。
もちろん、人が住まないような極域を除くと全世界を表現できる事も一つ。
そしてもう一つは、意外に知られてない事ですが、個々の微少領域では、緯度方向と経度方向の距離が等しく保たれる事です。

Google Mapsの地図を見てみてください。
(c)Google
左下にスケールが表示されてますね。
経度方向のスケールしか表示されてないですが、緯度方向のスケールがありません。
これ、省略してるんじゃなくて、必要ないから表示してないんですね。

もちろん、メルカトル図法の特性上、緯度が異なると同じズームのタイルでも1辺の長さは異なりますし、広い範囲の緯度を含む広域図レベルになると、そりゃ話が違ってきます。
が、町中レベルの大縮尺の地図で、気にかけるような正方形の辺の長さの違いは存在しません。
世界中を表現できながら、個々のローカル微少領域では、もっとも大事な要素である「距離」が座標軸方向に依らず保たれる*10
これが、Web地図でメルカトル図法が選ばれている理由です。

その性質を受け継いでいるquadkeyも、両辺の距離が等しい正方形タイルです。
距離が等しい正方形メッシュということは、半径ある距離の円を含む9メッシュを選択するロジックにおいても、単に半径と比較して十分な辺の長さのメッシュレベルで近傍9メッシュを選べば、ほぼ最適に近い検索範囲が得られるという事です。
これは、矩形ふるいをかけた後の実距離ふるい処理コストを最小化するためには、重要な性質といえます。

これに対し、GeoHashは元々が長方形のメッシュ形状な上に、ベースとなっているのが経緯度ですから、その形状と緯度方向、経度方向の割合は場所によって全然違います。
これは、同じように9メッシュ検索を行っても、無駄に取得されるデータが多くなる、という事を示しています。

この辺の性質の違いを知りたければ、地図の図法についてまとめた私のSlideShareがありますので、こちらを見てみてください。
この中で、quadkeyはメルカトル図法、GeoHashは正距円筒図法をベースにしたメッシュコード、と理解すれば判り易いです。

メッシュ上位と下位の分割が、4分木でマイルド

quadkeyは上位メッシュを下位メッシュを4分木で結んでいるため、上位メッシュに変えてもメッシュサイズは4倍にしかならず、もし下位メッシュが9メッシュ選択に十分でなかったからと上位メッシュに変えてもたかだか4倍で、さほど無駄な検索量は増えません。

が、GeoHashは32分木という苛烈な分割のため、下位メッシュで十分なサイズでなかったからと上位メッシュに変えた場合、一気に検索サイズは32倍になり、無駄な検索量が非常に大きくなります。

もちろんその副作用として、quadkeyはGeoHashと比較してむちゃくちゃデータ量を食います。
コード化のBASE値が違うので当然の事です。
が、上述の検索実行結果を見ても、MyISAMだとデータサイズの差によって検索速度に差が出ているように感じますが、InnoDBではそれほどあるように感じません*11
予測さえつくならデータサイズ圧縮がそれほどクリティカルな時代でもないと思いますし、コードサイズ増大はさほどの欠点でもないように思います。

隣接タイルの取得ロジックが簡単

この辺は別にAPI化しちゃえばいいって話ではありますが…。
一部GeoHash APIの実装見ましたが、隣接タイルの値を求めるのに、2進値まで戻して計算するのでなければ、何通りもの境界値を管理して…というややこしい事をされていました。
quadkeyでは、基本的に

  • 東西方向の移動は、0⇔1か2⇔3のどちらか*12
  • 南北方向の移動は、0⇔2か1⇔3のどちらか*13

ですし、それもさらに簡略化すると

  • 東西方向の移動は最終桁に±1
  • 南北方向の移動は最終桁に±2
  • 計算後の最終桁が0未満又は4以上になるか、或いは計算前の最終桁と計算後の最終桁の和が3になれば、最終桁に加算する値の正負を逆にしてやると同時に桁上がり/下がり処理

とすれば、汎用的に処理できます。
この程度ならば、脳内変換も比較的容易です*14

メッシュのカバーする距離判定も簡単

この辺もAPI化してしまえば…ですが、
GeoHashは経度緯度2軸の表す距離が同じメッシュによっても異なり、またメッシュレベルによって縦長横長も違うので、複雑な距離計算が必要になると同時に2軸での比較が必要になります。

が、quadkeyでは正方形メッシュなので1軸判定で十分であり、かつ緯度によって長さが異なるのも定数値に緯度を元にしたsin値を掛けてやれば十分で、
さらに正方形4分木メッシュですから、レベル毎の比較値も計算しなくてもしきい値をテーブル持ちしてやれば十分です。

「地図の表示範囲検索」も、JavaScript地図APIと連動させてやれば楽勝かも?

これは理屈だけでまだ試した事はないのですが、半径検索ではなく地図の表示内検索も、JavaScript地図APIと連動させれば楽勝という印象を持っています。

今ユーザが表示している地図範囲のPOIを検索して表示する場合、GeoHashだとどうするでしょうか?
JavaScriptで表示範囲の矩形データを送って、それを内包するGeoHashセット(多くの場合、必要以上の広域となる)を生成して検索後、領域との比較で絞って送ってやり、表示?
画面外に出たPOIデータの消去は、マーカー毎に経緯度の表示範囲との内包を比較?

タイルと連動しているquadkeyの仕様は、ここで効いてきます。
多くのJavaScript地図APIは、ユーザがオリジナルの地図タイルを挿入してやるためのインタフェースを持っています。
例えばGoogle Maps APIならここ
ここには、以前の記事でも書いたほぼあらゆる地図サービスにおいて共通仕様のタイルセット単位で、今表示中の地図が必要になったタイル、不要になったタイルの情報が取得できるインタフェースが存在します。
このインタフェースではタイルのズームレベルとタイルX,Y座標が与えられますから、そのタイルと1対1対応するquadkeyを算出するのは容易です。
つまりこのインタフェースを使えば、今表示されている地図を充たすのに必要充分な範囲のquadkeyを得るインタフェースと、不要になれば消すインタフェースの両方が得られるわけです。

もっとも、それがうまく機能するのは同じズームでの平行移動だけで、ズーム変更処理等では同じ範囲を表す上位キーと下位キーが同時にリリースと取得されたりするので、その辺の工夫は実際にやってみてノウハウを貯める必要がありますが、うまく使えれば劇的に表示範囲内地図検索の処理を簡単化できる可能性があります。
quadkeyはこういう発展可能性があるので、個人的には一押し空間インデックス仕様です。

quadkey、GeoHashともに特許侵害の懸念も

まあ空間検索を使いたいけどMyISAMは無理です、という場合、これまでの資産もあると思うのでquadkeyかGeoHashを使うかはお好みで、というところですが、ちょっと気になる話も。
位置コード生き字引の上田さんのブログですが、

GeoHashが米国特許6,552,670(通称 BINGEO)に引っかかってるかもしれない/ロカポブログ

空間表現を緯度経度ベースで2進数化してコード化するのは、米国で特許が取られていて、請求項は多岐に渡るのでその2進コードをBASE32しました、といったからといって逃れられるわけではないかも、という話です。
quadkeyも、4進数を使ってるといってもそれは単に2進数をBASE4しただけなので、上田さんも書かれていますが微妙だそうです。
quadkeyは経緯度ではなくメルカトル座標を使ってる点も、特に座標系を指定してるわけではないからこれも微妙とか。

もっとも、特許侵害しているといっても、これだけGeoHashが有名になってあちこちで使われていて、侵害申し立てするつもりがあるならとっくに動いているだろうし、Microsoftだって優秀な知財部隊抱える中で大丈夫と判断したのでしょうから、リスクは少ないと思いますが…。
気になる情報ではあるので共有しておきます。
あと、米国特許だと米国でサービスしない限りは、日本国内だけだとOKなんですかね?

*1:Microsoftの提唱している、Google地図やBing地図で使われている地図画像のタイル配信の単位を、そのままインデックスキーの仕様にしたもの。 http://msdn.microsoft.com/en-us/library/bb259689.aspx 実際の距離と対応した正方形で、かつ表示されている地図タイルと1対1対応しているので、GeoHashより直感的に扱える。

*2:GeoHash、quadkeyとも、varcharではなくcharでサイズを指定しています

*3:多分これが一般的な手法と思っています

*4:キャッシュが効く時と効かない時の効果を平均…したかったというわけではなく単に面倒くさくなりました。やって見てた感覚ではあまり影響なさそうにも感じたので。

*5: WHERE 条件にこれを追加。 AND SQRT( POWER( ( X( `geometry` ) - 135 ) * 91187.58845252,2 ) + POWER( ( Y( `geometry` ) - 35 ) * 111319.49079327,2 ) ) < 10000

*6: WHERE MBRWithin(`geometry`, GeomFromText('LineString(134.89033595285 34.910168471588, 135.10966404715 35.089831528412)', 4326) )

*7: WHERE ( `quadkey` LIKE '13211313131%' OR `quadkey` LIKE '13300202020%' OR `quadkey` LIKE '13300202021%' OR `quadkey` LIKE '13211313133%' OR `quadkey` LIKE '13300202022%' OR `quadkey` LIKE '13300202023%' OR `quadkey` LIKE '13211313311%' OR `quadkey` LIKE '13300202200%' OR `quadkey` LIKE '13300202201%' )

*8: WHERE ( `geohash` LIKE 'wyr8%' OR `geohash` LIKE 'wyrb%' OR `geohash` LIKE 'xn20%' OR `geohash` LIKE 'wypx%' OR `geohash` LIKE 'wypz%' OR `geohash` LIKE 'xn0p%' OR `geohash` LIKE 'wypw%' OR `geohash` LIKE 'wypy%' OR `geohash` LIKE 'xn0n%' )

*9:Windows PhoneだとAPIまであるみたいですね。

*10:Think Globally, act locally みたいなw

*11:というか、有意ではないと思いますが結果的にはコードサイズの大きい方が速くなってるし。

*12:当然、桁上がり下がりの処理は必要

*13:こちらも当然、桁上がり下がりの処理は必要

*14:所詮プログラムの処理するコードでも、直感理解できるかどうかは意外と重要

© TileMapJp/歴史国土/地図タイル工法協会