BigQuery での空間クラスタリング - ベスト プラクティス

※この投稿は米国時間 2022 年 8 月 27 日に、Google Cloud blog に投稿されたものの抄訳です。

ほとんどのデータ アナリストは、データをクラスタに編成するというコンセプトに熟知しているため、より高速かつ低コストでクエリを実行できます。ユーザーの動作によって、データをどのようにクラスタ化するかが決まります。たとえば、ユーザーが地理空間データ（位置情報）を分析または可視化しようとする場合、地理空間列でクラスタ化するのが最も効率的です。この手法は、空間クラスタリングとして知られており、このブログでは、BigQuery で空間クラスタリングを実装するためのベスト プラクティスをご紹介します（ヒント - BigQuery がこの処理を行います）。

BigQuery は、ペタバイト規模のデータ ウェアハウスで、地理空間の機能と関数を多数備えています。以降のセクションでは、BigQuery が S2 インデックス システムを使用して、空間クラスタリングをすぐに行う方法について説明します。また、H3 や Geohash などの他の空間インデックスの使用方法にも触れ、さまざまなアプローチでのコスト削減を比較します。

BigQuery が内部で空間クラスタリングを行う方法

クラスタリングにより、同じような値のデータブロックが、ストレージの同じ場所に配置されるようになります。つまり、クエリ時にデータを簡単に取得できます。また、データブロックを並べ替えることで必要なブロックのみスキャンでき、コストの削減と処理時間の短縮になります。地理空間用語において、これは特定のリージョンをクエリしているときに、地球全体ではなく、そのリージョン内またはそのリージョンに近い行のみがスキャンされることを意味します。

GEOGRAPHY 列でテーブルをクラスタリングする場合、上記の最適化はすべて BigQuery で自動的に行われます。テーブルを作成する際の CLUSTER BY [GEOGRAPHY] を入力するぐらい簡単です。ST_DISJOINT を除いて、述語関数（ST_Intersects や ST_DWithin など）のみが、クラスタリングを利用します。また、BigQuery は、さまざまなフィールドでパーティショニングとクラスタリングをサポートしていますが、地理空間フィールドでは、クラスタリングのみがサポートされていることにも注意が必要です。これは、BigQuery がどのようにスペースをパーティショニングするかにかかわらず、ジオメトリが大きくなり、複数のパーティションにまたがる可能性があるためです。最終的に、クラスタのサイズは 100 MB から 1 GB の範囲になるため、100 MB 未満のテーブルでのクラスタリングには、メリットがありません。

GEOGRAPHY によってクラスタ化されたテーブルに書き込む場合、BigQuery はデータを空間的にコンパクトなブロックにシャーディングします。ブロックごとに、BigQuery は、内部に含まれるデータの空間領域を含む S2 カバーと呼ばれるメタデータの一部を計算します。空間述語を使用して地理的にクラスタ化されたテーブルをクエリする場合、BigQuery はそのカバーを読み取り、特定のカバーがフィルタを満たすことができるかどうかを評価します。次に、BigQuery は、フィルタを満たすことができないブロックをプルーニングします。ユーザーは、残りのブロックのデータに対してのみ課金されます。データを重複しないリージョンに分割できないことがよくあるため、S2 カバーは重複する可能性があることにご注意ください。

基本的に、BigQuery は S2 インデックスを使用して、ジオメトリを 64 ビットの整数にマッピングします。それから、既存の整数ベースのクラスタリング メカニズムを使用して、その整数にクラスタリングします。これまで、お客様は手動で BigQuery に S2 インデックス システムを実装していました。これは、BigQuery が S2 を介した空間クラスタリングをネイティブでサポートする前に行われていました。BigQuery のネイティブ クラスタリングを使用することで、パフォーマンスが大幅に向上しました。また、固有の S2 インデックスを管理する必要がないという簡易性が増したことは言うまでもありません。

代替空間インデックス

空間クラスタリングでは、空間インデックス システムまたは階層を利用して、格納されたデータを編成します。すべての空間インデックスの目的は、Earth と呼ばれるこの地球を数値で表すことです。これにより、ロケーションを点、多角形、線などの幾何学的オブジェクトとして定義できるようになります。数十もの空間インデックスがあり、ほとんどのデータベースは独自の方法で空間インデックスを実装しています。BigQuery はクラスタリングに S2 セルをネイティブに使用しますが、H3、Geohash、quadKey などの他のインデックスを手動で実装できます。以下の例には、次の空間インデックスが含まれます。

• S2:  S2 システムは、地理空間データを 3 次元球体上のセルとして表します。Google マップで使用されます。

• 六角形よりも効率的な四角形を使用

• H3 やジオハッシングよりも精度が高い

• H3:  H3 システムは、重複する六角形のグリッド上の地理空間データを表します。

• 六角形は、視覚的により魅力がある

• 畳み込みと平滑化アルゴリズムは、S2 よりも効率的

• Geohash - Geohash は, 曲線グリッド上の地理空間データを表すパブリック ドメイン システムです。  

• Geohash id の長さによって、空間精度が決まる

• 空間的局所性がかなり低いため、クラスタリングは機能しない

BQ での空間クラスタリング - S2 と Geohash の比較

分析のほとんどのケースで、BigQuery の組み込みの空間クラスタリングにより、最小限の労力で最高のパフォーマンスがもたらされます。ただし、Geohash ボックスなど、他の属性に従ってデータをクエリする場合は、カスタム インデックスが必要です。次の例に示すように、空間インデックスをクエリする方法は、パフォーマンスに影響を与えます。

例

まず、経度と緯度のランダム ポイントでテーブルを作成します。BigQuery 関数 st_geohash を使用して、各ポイントの Geohash ID を生成します。

st_geogpoint 関数を使用して、緯度と経度を、S2 セルをインデックスとして使用する GEOGRAPHY（BigQuery のネイティブ地理空間型）に変換します。約 3,000 ポイントのコレクションを選択します。これには、約 25 MB が必要です。クラスタ化されていないテーブルで同じクエリを実行すると、5.77 GB（テーブル全体のサイズ）が必要です。

ここで、Geohash ID でクエリを実行します。BigQuery が空間クラスタリングを活用できるかどうかは、BQ SAT ソルバーが、データのクラスタをプルーニングできることを証明できるかどうかによります。以下のクエリは、どちらも地理空間クラスタリングを利用しており、必要となるのは、わずか 340 MB です。テーブルを「gh」フィールド（Geohash ID など）でクラスタ化した場合、上記と同じで、クエリに約 25 MB が必要になることにご注意ください。

以下のクエリは、かなり効率が悪く、テーブルのフルスキャンに 5.77 GB が必要です。BigQuery は、クラスタの最小値と最大値に基づいて、この条件が失敗したことを証明できないため、テーブル全体をスキャンする必要があります。

例が示すように、最も低コストのクエリ オプションは、クエリメソッドと一致するインデックスを使用することです。たとえば、GEOGRAPHY によるクエリの場合は、ネイティブ S2 インデックス、Geohash によるクエリの場合は、文字列インデックスです。Geohash を使用する場合は、BigQuery がテーブル全体をスキャンするようになるため、left() 関数、または right() 関数の使用を避けてください。

H3 を使用した BQ での空間クラスタリング

H3 を BigQuery の空間インデックスとして使用する必要がある状況になる場合もあります。クラスタリングのパフォーマンス上のメリットを活かすことは、引き続き可能ですが、Geohash の場合と同様に、特定のパターンを避けることが重要です。

レベル 15 の H3 セル ID によってインデックスに登録された地理ポイントの巨大なテーブルがあり、これを H3_index でクラスタ化したとします（注: このような関数は、BigQuery 向けの Carto Spatial Extension でサポートされています）。レベル 7 など、解像度の低いセルに属するすべてのポイントを検索する場合、次のようなクエリを記述できます。

ここで、H3_ToParent は、より高い解像度のインデックスから親セル ID を計算するカスタム関数です。H3 インデックスでクラスタ化したため、低コストを期待するかもしれませんが、このクエリはテーブル全体をスキャンします。これは、H3_ToParent にはビット演算が関係し、複雑すぎて BigQuery のクエリ アナライザが、クエリの結果がクラスタ境界にどのように関連しているかを把握できないために発生します。代わりに必要なことは、次の例のように、地域がインデックス化されているレベルで H3 セル ID の範囲を BigQuery に提供することです。

ここで、H3_CellRangeStart と H3_CellRangeEnd は、低解像度の親 ID を高解像度のセルの適切な開始 ID と終了 ID にマッピングするカスタム関数です。これで、BigQuery は関連するクラスタを特定できるようになり、コストが削減され、クエリのパフォーマンスも向上します。

次のステップ

空間クラスタリングは複雑なトピックであり、実装には専門知識が必要です。BiqQuery のネイティブ空間クラスタリングを使用することで、ほとんどの作業が不要になります。BigQuery の地理空間データを使用すると、大規模なデータセットであっても、天文データのクエリなどの驚くような空間分析が可能になります。BigQuery を地理空間アプリケーションのバックエンドとして使用することもできます。これには、お客様がアセットの気候リスクを確認できるようにするアプリケーションなどがあります。空間クラスタリングを使用し、クラスタを正しくクエリすることで、最低限コストで最高のパフォーマンスを実現できます。

^{謝辞: この投稿に協力してくれた Eric Engle と Travis Webb に感謝します。}