読者です 読者をやめる 読者になる 読者になる

Google APP Engineで複数のプロパティにまたがる範囲検索

Google App Egine

理由は解りませんが、残念ながらデプロイ環境では動作しないようです。

 Google APP Engineでは、従来のシステムのRDBMSに相当する(実際はKVSですが)データストアをデータの保存、検索に使用します。
 このデータストアにはいくつかの制限があるのですが、その中でも大きいのが範囲検索です。イコールで無いクエリは、一つのプロパティ(RDBMSにおけるカラム)に対してしかかけられません。
 しかし、緯度経度や時刻のようにとりうる値の上限と下限がわかっている場合においては、複数のプロパティにまたがる範囲検索が可能です。


方法

 まず対象となるプロパティの値について以下の正規化を施します。

  1. 数値は文字列に変換し、桁をそろえる。
    1. とりうる最小の値が負の数の場合は、その絶対値を足してとりうる最小の値が0になるように
      1. 例えば緯度ならばとりうる最小の値は-90度なので90を足す。
    2. 小数点以下の桁数は一定にし、とりうる最大の値分だけ0埋めでパディング
      1. 例:とりうる最大の値が10000ならば9は00009
  2. 正規化した値を文字列変換し、プロパティごとにユニークな接頭辞をつける 

 この正規化を施した上で、ListPropertyというリストをそのまま格納できるプロパティを設定してその中に保存します。 
 検索する時は検索条件に対して同様の正規化を施した上で、先ほどの値を格納したプロパティに対して全てを論理積(and)でつないだ範囲検索として投げれば複数プロパティにまたがる範囲検索が可能です。

原理

 原理としては非常に単純で、文字列の大小比較においては左側が優先されるというルールを利用しているだけです。
 このルールにより、接頭辞を共有する複数の文字列のグループが一つのプロパティに存在する場合は以下の性質が現れます。

  1. ある接頭辞をもつ文字列は、他の接頭辞を共有するグループの全ての文字列に対して大きいか小さい
  2. 同じ接頭辞を持つグループ内では、文字数が同じであり、少数点のようなデリミタ(区切り文字)の位置が等しい限りは数値と同じ比較が成り立つ

 1番目の性質により範囲検索においては上限か下限のいずれかにおいて接頭辞が異なる文字列は偽となり排除されるので、一つのプロパティの中に他の複数のプロパティの値が格納されていても互いに影響することはありません。なので、複数のプロパティのうちの一部の組み合わせに対して範囲検索するようなことも可能です。
 そして2番目の性質により、文字数が一定になるように正規化を施せば通常の数値範囲の検索と同様の検索が可能になります。ただし文字列比較においては+より-の方がunicode順に見て大きいので、0以上になるように正規化する必要があります。
 逆に言うと、この場合において複数のプロパティに対して大小比較のみの検索を行う場合は、取りうる最大また最小の値との範囲検索に変換する必要が生じます。
 なお、デリミタは文字列上の位置が一定である限りはいくつあってもいいので、数値以外にも日時のような一定のフォーマットで表現可能なパラメーターにも同様な応用が可能になります

サンプルコード

 緯度経度の場合、以下のようになります。(Pythonの場合)

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from google.appengine.ext import db

class Squere(db.Model):
    lat=db.FloatProperty()
    lon=db.FloatProperty()
    geo=db.StringListProperty()

testdata=[{"lat":35.664694,"lon":139.700016},
         {"lat":36.564854,"lon":138.899456},
          {"lat":-35.664694,"lon":35.664694},
         {"lat":37.564854,"lon":121.987546}
          ]
for data in testdata:
    e=Squere(lat=data["lat"],lon=data["lon"])
    e.geo=geo_normalization(data["lat"],data["lon"])#インデックスとなるデータを入れる
    e.put()

#検索範囲を正規化
nw_lat,nw_lon=geo_normalization(35.789425,139.717587)
se_lat,se_lon=geo_normalization(35.576616,139.600056)

#クエリオブジェクト取得
q=Squere.all()

#北東(nw_lat,nw_lon)が上限
q.filter("geo <",nw_lat)
q.filter("geo <",nw_lon)

#南西(se_lat,se_lon)が下限
q.filter("geo >",se_lat)
q.filter("geo >",se_lon)

for r in q:

    print str(r.lat)+str(",")+str(r.lon)#35.664694,139.700016

def geo_normalization(lat,lon,decimal_length=6):
    """
    緯度経度を正規化

    """
    lat=normalization(prefix="lat ",
                      value=lat,
                      over_decimal_length=3,
                      min_limit=-90,
                      decimal_length=decimal_length)
    lon=normalization(prefix="lon ",
                      value=lon,
                      over_decimal_length=3,
                      min_limit=-180,
                      decimal_length=decimal_length
                      )
    return [lat,lon]


def normalization(prefix,value,over_decimal_length=0,decimal_length=0,min_limit=0):
    """
        正規化
        over_decimal_length 小数点以上のケタ数。文字列(フォーマットされた日付など)の場合は省略可
        decimal_length 小数点以下のケタ数。文字列(フォーマットされた日付など)の場合は省略可
        min_limit 最小値。0以上または文字列(フォーマットされた日付など)の場合は省略可
    """

    if not isinstance(min,basestring) and min_limit <0:
        value=value+-1*min_limit
    value=unicode(value)
    if over_decimal_length >=0:

        temp=value.split(".")
        ud=None
        od=temp[0]
        if len(temp)==2:
            ud=temp[1]

        pattern="%0"+over_decimal+"d"
        od=pattern % od
        if decimal_length <= 0:
            value=od

        if decimal_length>0 :
            if not ud<2:
                pattern="%0"+str(decimal_length)+"d"
                zero=pattern % "0"
                value=od+"."+zero
            else:

                if len(ud)>decimal_length:
                    ud=ud[:decimal_length]
                elif len(ud)< decimal_length:
                    pattern="%0"+str(decimal_length-len(ud))+"d"
                    zero=pattern % "0"
                    ud=ud+zero
                value=od+"."+ud
    return prefix+value