ロコガイド テックブログ

「地域のくらしを、かしこく、たのしく」する、株式会社ロコガイドの技術部ブログです。主にトクバイ・ロコナビのサービス開発について発信しています。

「地域のくらしを、かしこく、たのしく」する、株式会社ロコガイドの技術部ブログです。
主にトクバイ・ロコナビのサービス開発について発信しています。

既存の位置情報ログに対する空間データ検索のパフォーマンス改善

 技術部の根岸(@negipo)です。「ポケモンおぼえたい」と二週間くらい前に奥さんが言いだしたのでスッとReact Nativeでポケモンがおぼえられるアプリを作ったのですが、できたそれを奥さんが一日四時間くらい触っていて心配です。すでに800匹以上覚えたそうです。よかったね……。

 三密、避けていますか。もちろんできることなら避けたいです。しかし、ウィズコロナの生活においても毎日の買い物を続けなければぼくたちは生きていけないので、ときに三密が起きている可能性のあるお店へと足を運ばなければなりません。でもお店がどれくらい混んでいるのかって、基本的には現地に行かなければわからないし、怖いですよね。

 さて、これをお読みのあなたが開発しているサービスでは位置情報ログを取得しているでしょうか。ロコガイドが提供しているモバイルアプリは、おトクな買い物情報を配信するというサービスの特徴上位置情報ログを取得しています。まだ今ほど暑くなかったころ、この位置情報ログを分析して店舗が混雑する時間帯がわかる機能としてユーザー向けにリリースしようということが決まりました。分析そのものは、簡単に言えば位置情報ログと店舗の位置情報の突き合わせによって達成されます。SQLが書けるディレクターによっておこなわれた限られた店舗に対する検証によって、ある程度価値のある機能になりそうだとのことがわかったようでした。超すごいです。三密、避けられます。ぼくはよろこび勇んでサービス導入のためのパフォーマンス改善に手を上げました。

f:id:korn_freak:20200706154125p:plain

 データの内容を確認してみましょう。

  • 位置情報ログも店舗データもAmazon Redshift上に置かれているが、double precisionとしての位置情報しか持っていないため、距離の算出は三平方の定理を使って sqrt(power((latitude1 - latitude2) / 0.0111, 2) + power((longitude1 - longitude2) / 0.0091, 2)) みたいなプリミティブな計算でおこなうことになる
  • 探索対象の店舗数は10万件程度
  • 探索対象の位置情報ログは100億行オーダー
  • 総当りで検索すると1000兆回以上の空間データ検索をおこなう必要がある

 ええー……という感じです。この状態では、パフォーマンスが大きなボトルネックになるのはあきらかです。しかしもちろんリリースはしたい。やっていきです。

計算量削減手法の列挙

 大量データ解析において重要なのは計算量を減らすことです。一般的には、それは対象のログを事前計算された何らかの機構を用いて効率的に絞り込むことで達成されます。通常、パフォーマンス改善は分析機構に備わっているインデックスなどを用いて行ないます。Redshiftにおいても分散キーやソートキーなど、インデックスに相当する機構を用いてクエリパフォーマンスを改善するよう、ドキュメントのなかで繰り返し述べられています(1,2,3)。

 まず、Redshiftで位置情報を取り扱う専用の方法がないかどうか調べました。専用の方法があれば、Redshiftの機構にまかせれば計算量が勝手に減る公算が大きくなります。そしてGEOMETRY型という位置情報を取り扱う型を見つけ、我々が利用しているRedshiftクラスターがその型をカバーしているバージョンであることを確認しました。

 次に、そういった空間検索の刈り込みを手動で行う手法がないか調べました。一般的には空間自体を矩形などで区切る『メッシュ』と呼ばれる手法で行なわれ、いくつかの具体的な仕様があることを確認しました。

  • ジオハッシュ
    • 緯度経度の組から矩形の同じセルに入る位置情報に対し、u4pruydqqvjなどの文字列を割当て、その前方一致で同じセルかどうかを判定するメッシュ
    • メッシュの実装としては最も一般的
  • メッシュコード
    • 総務省統計局が標準化した、主に国内の統計でよく使われるメッシュ
    • 計算が非常に簡単

 ここまで理解したところで、まずRedshiftの型を適用して十分実用的な時間内に計算可能か調査しました。

RedshiftのGEOMETRY型を利用する

 ドキュメントを見ながらPOINTという形式で空間上の一点を指定するカラムを持った中間テーブルを作成し、st_distancesphereという命令で空間の距離をメートル単位で計算できることまではわかりました。距離の計算式はビルトイン関数を用いてst_distancesphere(point1, point2)となり、なんだか簡単そうです。これで計算量削減のために位置情報カラムに対して分散キーかソートキーを指定すれば……というところでGEOMETRY型にはいずれの指定もできないという事実に気づきました。一縷の望みをかけて実際に検索を行ってみましたが、とても実用的なスピードは出ていなさそうでした。

 というわけで、Redshiftにビルトインされた機構をもちいずに、手動でなんらかの手法を適用する以外の選択肢がなくなってしまいました。

手動でメッシュを作成し、空間データ検索の枝刈りを行う

 先程述べたとおり、メッシュの実装としてはジオハッシュが一般的でありファーストチョイスです。しかし、ジオハッシュの計算はまあまあ難しいためにSQLでの表現が難しく、Redshiftにはユーザー定義関数のサポートがあるためPythonの実装をつっこめば稼働はしそうなものの、一旦タイムアップで諦めました。余談ですが、調査中にBigQueryにはジオハッシュのビルトイン関数を見つけてしまいかなりかなしかったです……。

 そのため、今回の計算ではメッシュコードを採用しました。セルの大きさはそれなりに自由に設定でき、たとえば1km四方程度の大きさであれば以下のようになります(参考)。

cast(cast(floor(latitude * 60 / 40) as integer) as varchar) ||
cast(cast(floor(longitude - 100) as integer) as varchar) ||
cast(cast(floor((latitude * 60)::integer % 40 / 5) as integer) as varchar) ||
cast(cast(floor((longitude - floor(longitude)) * 60 / 7.5) as integer) as varchar) ||
cast(cast(floor(((latitude * 60)::integer % 40)::integer % 5 * 60 / 30) as integer) as varchar) ||
cast(cast(floor(((longitude - floor(longitude)) * 60)::integer % 7.5 * 60 / 45) as integer) as varchar) as meshcode

 無事にメッシュコードをSQLで表現できました。上記のメッシュコードの表現において、同じメッシュコードを持つ位置情報データは1km四方程度の大きさの同じ矩形の中にいることになるので、ソートキーにメッシュコードを指定した中間テーブルを作成し、位置情報ログと店舗を結合時にまずそれぞれメッシュコードで突き合わせてから距離検索をするという手法で高いパフォーマンスを得ることができました。たとえば、ある店舗を訪れたユニークユーザーを曜日ごとに出すクエリは以下のような実装になります。

select
  shops.id
  , date_part(dayofweek, logs.time) "day_of_week"
  , count(distinct logs.unique_id) uu
from
  shops
inner join
  logs
  on shops.meshcode = logs.meshcode
    and st_distancesphere(shops.point, logs.point) <= 15
group by 1, 2

 ※ この実装はサンプルで、設定されている閾値などは実際のサービスで利用されているものではありません。

 単純かつ、実用的な方法で解析を行うことができるようになりました。

Redshiftでユーザー定義関数をもちいてジオハッシュを使う

 後日、メッシュコードの実装をジオハッシュで代替できないか検討しました。

 Redshiftのユーザー定義関数ではPython 2.7のライブラリを動作させることができます。このドキュメントで詳述されているzip形式でアーカイブしたファイルはPythonパッケージのwheelファイルで代替できます。今回は下記のワークフローでジオハッシュのエンコードを行うユーザー定義関数を定義しました。

  1. ジオハッシュのPythonライブラリ をclone
  2. python setup.py bdist_wheel して dist ディレクトリにパッケージファイルを生成
  3. S3にパッケージファイルを配置
  4. S3の読み出し権限を持ったIAMを用意し、該当するクレデンシャルでRedshift上で下記のSQLを個別に実行
create or replace library py_geohash_any
language plpythonu
from 's3://{bucket}/Geohash-1.0-py3-none-any.whl'
credentials 'aws_access_key_id={aws_key};aws_secret_access_key={aws_secret}'
create or replace function f_geohash_encode (latitude double precision, longitude double precision, chars integer)
  returns varchar(max)
stable
as $$
  import Geohash
  return Geohash.encode(latitude, longitude, precision=chars)
$$ language plpythonu

 さて、導入してはみたものの、結論としてはやはりメッシュコードと同等のパフォーマンスは出ないため、さらに何らかの対応が必要と判断しました。メッシュコードとほぼ同等の仕様を達成するためにおおよそ600m四方の矩形で区切られる6桁のジオハッシュを出力するように指定し、1000万行の位置情報を変換するクエリを実行したところ、メッシュコードの実装は30秒程度で完了したのに対し、今回定義した関数は12分かかってしまいました。店舗情報などに対しては実用上十分と言えますが、100億行オーダーの位置情報ログなどに対しては十分な性能ではないでしょう。たとえばなんらかの中間テーブルを利用するか、あるいはクライアント側で事前にジオハッシュを計算しログ送信時に付加するなどが有益と考えています。

おわりに

 膨大な位置情報ログと店舗レコードの突き合わせを短期間で実用可能にしました。利用したメッシュコードというメッシュはあまり空間データ検索の実装としては一般的ではありませんでしたが、とにもかくにも三密を避けることができる機能をリリースすることができました。世の中にはやっていかなければならない瞬間が必ず存在します。いつでもやっていけるように勇気を磨いておきたいですね。