💽

DynamoDBでの複合キーによる検索を考える part 1 (Geohash・Z-Order Indexing )

2025/01/21に公開

経緯

個人開発の地図型アプリケーションのメインDBとしてコストとスケーラビリティの面からDynamodbを選択しました。しかし地図情報(座標データ)を扱う場合、前提として座標による座標範囲検索には緯度、軽度の2軸での検索が必須となります。そしてさらに時間軸順でソートしたいなどの追加の条件などが発生すると、そもそも設計できないのではとなってしまいました。そんな中色々調べた結果を整理しつつ、具体例とともに書き綴っていこうと思います

例1)UserId:10の特定の座標範囲(緯度50~60, 軽度100~120)のデータを検索するケース

この場合そのまま検索しようとすると、Partition keyにはUseridを配置し、Sort keyに座標(latitude_longtitude)のような設計になるかと思います。しかし、これだとDynamodbのクエリ上Betweenやbegin_withのようなクエリしかできず、緯度か軽度でクエリをした後に、補助的にFilterでもう一方の範囲を絞るようなクエリしか実装できません。

解決策 - Solve it! -

このケースだとGeohashという座標範囲をグリッド上に区分しそれぞれ範囲をHASH値に割り当てていくというジオコードシステムをSort keyに配置することで解決できるようです。緯度経度の2軸ではなく区域によって採番され、それに対応する範囲を前方一致検索するイメージ。

Refference

このYoutubeが一番イメージつきやすいかもです
https://youtu.be/UaMzra18TD8?si=M5UTur7hEc89Qgz7
他にも参考になる記事
https://aws.amazon.com/jp/blogs/compute/implementing-geohashing-at-scale-in-serverless-web-applications/


- Geohashを知った感想 -

自分はウオォぉぉ!誰がこんなの思いついたんだっっ!となりました。
ちなみに、Google mapでもこれによって地点情報が管理されてるとかなんとか。

Geohashを使えばPoiなどの地点情報(Point)の管理は大体解決しそうです。
ただ、線データ(Line)、面データ(Polygon)データはそう簡単には行かなそうです

Geohashだけでは物足りない

ですが、自分の作りたい地図アプリではこれだけでは機能が満たせませんでした。というのもじゃあ検索範囲にあるデータが10000件あったら、それ一括で取ってくるの無理だなぁと、てことはレスポンスは、created_byなどでソートして100件ごととかに小分けでページングするしかないよなぁとなりました。

しかし検索時に使用できるSort keyはすでにGeohashで使用しているため、プラスして時系列で並べることはできません。どうしようとなりました。
そんな中ネットと色々調べてると以下の記事を見つけて、おやおや使えそうとなったので、今回の本題のZ-Order-indexingという手法の記事を見つけたので英文読むがてらに内容を書き綴っていきます

Reference

https://aws.amazon.com/jp/blogs/database/z-order-indexing-for-multifaceted-queries-in-amazon-dynamodb-part-1/

Z-Order Indexing for Multifaceted Queries in Amazon DynamoDB: Part 1 - 書き殴り解説 -

例では、気温情報を観測機関ID、緯度、経度、タイプスタンプと一緒に保存しているテーブルについて考えています。

1)まず、はじめに観測機関IDをPartition key(以降からPkeyとする)、タイムスタンプをSort key(Skey)とするテーブルデザイン

この場合、DynamoDbのPkey単一、もしくはPkeyとSkeyにより、一意性を担保しなければいけない制約上、 複数の地点のデータでタイムスタンプが被ってしまった場合にデータが損失する問題を提示しています。また、GSIを使用しなければ、座標による検索ができないのも懸念になります。

2)続いて、PkeyはそのままUseridとして、Skeyを"タイムスタンプ_緯度_経度"とするケース

この場合、同じ場所から同時にレポートを送信する 2 つのセンサーが存在することはないため、データ内で主キーの衝突が発生するリスクはなくなりました。したがって、一意性の制約は満たされました。

しかし、多面的なクエリを行おうとする場合に制約があります。


  1. クエリ制約例1 : 3 月の最後の週、ジョージア州アトランタの気温はどれくらい暖かくなりましたか?

この場合、
クエリ
観測機関ID = 1かつ、timestamp_lat_longが“1471996800”から“1472601601”(タイムスタンプ部分の前方一致検索)の間
フィルター
緯度経度の範囲
とすることで取得できます。
Filterでは、その元クエリのリソース量によりコスト計算されるため、タイムスタンプでクエリすることでかなりのデータに絞れています。また、フィルター座標もジョージア州アトランタと広範囲に及ぶため、他の地域のデータがそこまで多くない場合には無駄にコストが発生することはないかもしれません。

しかし、次の例ではどうでしょう。

  1. クエリ制約例2 : 2016 年の第 1 四半期にニューヨーク市で雪が降るほど寒い日はどのくらいありましたか?

クエリ
観測機関ID = 1かつ、timestamp_lat_longがタイムスタンプ部分の前方一致検索(1~3月)
フィルター
緯度経度の範囲 + 観測温度 < 0°

結果、timestampフィールドの境界は広範囲に及び、データの 3 か月間の範囲全体が取得されます。このため、Skeyによるインデックスは事実上役に立ちません。そのためSkeyではニューヨーク市内に絞れれば大きく検索後のデータ量を絞れることになります。

上記の通りSkeyには検索時にその範囲が大きく絞れるものでなければ、リソース量が大変になることがわかります

このようにクエリによって、絞るために有効なフィールド(attribute)が変わっていきます。では、さまざまなクエリが必要となる場合にはどのように対応していけばいいのでしょうか?

ローカルセカンダリインデックス

一つ挙げられる解決策はLSIを定義することです。
この機能を使用すると、それぞれ異なるフィールドを使用してデータを順序付ける代替インデックスのセットを作成できます。このアプローチにより、各クエリに最も役立つフィールドを使用できます。

しかし、残念ながら、幅広いクエリをカバーしたい場合、かなりの数の LSI (フィールドごとに 1 つ) を作成する必要があります。メイン テーブルでPutItem、UpdateItem、およびDeleteItem操作を実行すると、保持する各 LSI が追加の書き込み容量を消費します。また、LSI はメイン テーブルから独自のデータのコピーを保持するため、消費されるストレージの量が膨れ上がります。これらの特性は両方とも追加費用につながります。
またLSIはテーブル作成時点で指定する必要があるためアジャイル形式で、段階的に増やしていくことはできません。

そこで紹介されているのはZ-orderという次の手法です。

Z-Order

Z-Orderとは多次元データを 1 つの次元にマッピングできる手法です。
2 次元平面上の (X, Y) 座標ペアを 1 次元の線上に配置できます。重要なのは、2D 平面で近接していた値は、線上でも互いに近接しているということです。

画像にある通り、000000 -> 000001 -> 000010と辿っていくと確かに、線で結んだ時に付近に存在していることがわかります。
この線がジグザグと「Z」のように結ばれていることが名前の由来みたいですね

一旦まとめ

複数次元で検索をかけられる。
Dynamodbで実装する際には、がベー字となる計算範囲の周辺部分はスキップするようにし、該当範囲へのクエリを順次的に実行する。

該当アイテムが0だったとしても範囲に対してのクエリが続くため、その場合には前もって、単純なクエリで検索をかけるように動的に変更するのがいい。

効果的なケースはインデックスに含める属性全てで、特定の範囲を絞って検索をする場合のみ
範囲を絞れない属性をインデックスに含めてしまうと、クエリ回数が増え、逆にFIlterするよりも、リソースがかかることになる。

使い所としては座標と、時間軸を含めるとしたら、それら全てで範囲指定して、検索を行うようにしたい。

Discussion