Geohash で特定範囲内の地点を取得する時は、以下のような戦略をとるといいみたいです。
東京タワーの周りを探す場合は、「xn76gg」だけを検索するのではなく、’xn76gu’,'xn76gf’,'xn76u5′ ,’xn76ge’,'xn76gs’,'xn76uh’,'xn76u4′,’xn76gd’,'xn76gg’も同時に検索することで、おおよそ 2km*3kmの範囲で検索が可能です。
実際にやってみました。以下の赤い領域に10万個の地点を設置し、緑枠内に含まれる地点(今回は127件)を検索します。緑枠は、(35.727353, 139.716654)〜(35.827353, 139.816654)の範囲です。
下準備
MySQLに以下のようなInnoDBのテーブルを作りました。
CREATE TABLE location ( id INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY, geohash VARCHAR(10) NOT NULL, KEY (geohash) ) ENGINE=InnoDB;
でもって、次のようにデータ投入。
my $sth = $dbh->prepare('INSERT INTO location(geohash) VALUES (?)') or die $dbh->errstr; my $gh = Geo::Hash::XS->new; for (1 .. 100000) { my $lat = rand(37 - 34) + 34; my $lng = rand(141 - 138) + 138; $sth->execute($gh->encode($lat, $lng, 10)) or die $sth->errstr; }
範囲をGeohashに直す
location テーブルには Geohash しか入っていないため、緯度経度のままでは検索ができません。そこで、検索したい範囲をまんべんなくカバーできるような Geohash のリストを作る必要があります。これを以下のように実装しました。
sub geohash_cover($$;$){ my ($lat_range, $lng_range, $precision) = @_; my ($lat_max, $lat_min) = @$lat_range; my ($lng_max, $lng_min) = @$lng_range; my @covers; my $gh = Geo::Hash::XS->new; my $hash_sw = $gh->encode($lat_min, $lng_min, $precision); # South West my $hash_se = $gh->encode($lat_min, $lng_max, $precision); my $hash_nw = $gh->encode($lat_max, $lng_min, $precision); my $hash_ne = $gh->encode($lat_max, $lng_max, $precision); my $h = $hash_sw; my $width = 0; while () { push @covers, $h; $width++; last if $h eq $hash_se; $h = $gh->adjacent($h, ADJ_RIGHT); } $h = $hash_sw; while ($h ne $hash_nw) { $h = $gh->adjacent($h, ADJ_TOP); my $h_col = $h; for( 1 .. $width ){ push @covers, $h_col; $h_col = $gh->adjacent($h_col, ADJ_RIGHT); } } die unless $covers[-1] eq $hash_ne; return @covers; }
ロジックは馬鹿みたいに単純で、まず領域の四隅のGeohashを求めてから、上下左右に地道に移動して中身のGeohash を求めています。なお、Geo-Hash-0.02では隣にあるGeohashを求める adjacent メソッドが実装されていませんので、Geo::Hash::XSを使うとよいです。
MySQLにて検索する
算出された Geohash のリストに基づいて、検索をします。ここで注意しなければいけないのは、きちんとインデックスが利用されるように検索される必要があるということです。MySQLの場合 substr + in による検索ではインデックスが使われないようなので、 like(前方一致) + or にて検索をします*1。
sub search_points($) { my $precision = shift; my @pieces = geohash_cover( [35.827353, 35.727353], [139.816654, 139.716654], $precision ); my $like_sql = join ' OR ', map {"geohash LIKE '$_\%'"} @pieces; my $sth = $dbh->prepare("SELECT id, geohash FROM location WHERE $like_sql") or die $dbh->errstr; $sth->execute or die $sth->errstr; my $gh = Geo::Hash::XS->new; my @ret; while (my $ref = $sth->fetch) { my ($lat, $lng) = $gh->decode($ref->[1]); next unless 35.727353 <= $lat and $lat <= 35.827353 and 139.716654 <= $lng and $lng <= 139.816654; push @ret, $ref; } return @ret; }
なお、Geohash によって検索された結果にはそのままだと求めたい領域よりも外の値も含んでいるため、それらを捨てるためにdecodeして範囲を確認しています。
適切な precision を選択する
precision とは Geohash の長さであり、長ければ長いほど升目は細かくなります。検索の際にはこの値を適切に選ぶ必要があります。Geohashが細か過ぎると、領域を覆うのに必要なGeohashの枚数が多くなり過ぎて、検索に支障が出てしまいます。逆にGeohashが荒過ぎると、領域からはみ出してしまう範囲が大きくなり過ぎて無駄なレコードが大量に引っかかってしまいます。
今回の例においては、precisionと領域を覆うのに必要なGeohashの枚数、そしてGeohashを元に検索した場合に引っかかる地点数の関係は以下のようになりました。なお、「127件」が実際に検索したい地点の個数です。
| precision | Geohash数 | 検索された地点数 |
|---|---|---|
| 1 | 1 | 100000 |
| 2 | 1 | 100000 |
| 3 | 1 | 21852 |
| 4 | 1 | 687 |
| 5 | 12 | 287 |
| 6 | 200 | 147 |
| 7 | 5476 | 125 |
| 8 | 170528 | 未測定 |
この表から、precision が 2以下の場合は、赤枠内の全件が引っかかってしまっており、全てPerl側で条件判定する羽目になることがわかります。また、precisionが7以上になると領域を覆うのに必要なGeohashの数が急速に増加し、DBにて前方一致検索するのが難しくなります。
【8/24 追記】id:kazuhookuさんのエントリにあるように、ベンチマークの取り方が間違えてました。ごめんなさい＞＜ → 改めてベンチマークとりました。
さらに、precisionごとに領域内の127地点の算出にかかった総合時間を測定すると、以下のようになりました。
《10回の試行》
Rate p=1 p=2 p=3 p=7 p=4 p=6 p=5
p=1 3.03/s -- -0% -78% -93% -99% -100% -100%
p=2 3.04/s 0% -- -78% -93% -99% -100% -100%
p=3 13.7/s 352% 351% -- -67% -97% -99% -99%
p=7 41.7/s 1275% 1271% 204% -- -92% -96% -96%
p=4 500/s 16400% 16350% 3550% 1100% -- -50% -50%
p=6 1000/s 32900% 32800% 7200% 2300% 100% -- -0%
p=5 1000/s 32900% 32800% 7200% 2300% 100% 0% --とりあえず、precisionが4〜6の間にないとお話にならないということがわかりました。さらにprecision=4, 5, 6に絞って比較すると以下のようになりました。
《1,000回の試行》
Rate p=4 p=6 p=5
p=4 350/s -- -31% -46%
p=6 510/s 46% -- -21%
p=5 649/s 86% 27% --今回一番高速だったのは、precision=5で領域を12個に分割した場合でした。precision=6の方が無駄なレコードを引かずに済むのですが、SQL側で何度もインデックスを使う負荷の方が大きかったという結果でしょう。
まとめ
Geohash の格納されたDBから特定の領域内の地点を検索する場合は、領域を複数のGeohashで覆って前方一致にて検索すると求まります。その際、DBのインデックスを生かせるように気を配る必要があります。
この方法のパフォーマンスはGeohashの粒度に大きく左右されますので、適切なprecisionを選ぶのが大切*2です。今回の例を見る限りでは、領域を十数個〜数百個程度に分割できるような粒度が適切だと考えられます。
*1:explainにて実行計画を見て判断するといいです。後、7.5.3. How MySQL Uses Indexesにどんなときにインデックスが利用されるか書いています。
*2:実際は、地図の縮尺(zoom)に対してprecisionを決めておくのが適切と思われます。Google Maps の場合はzoomが0から20まであるので、それぞれの値に対して予め適切なprecisionを決めておけば楽です。
