Supercharging H3 for Geospatial Analytics | Databricks Blogの翻訳です。
本書は抄訳であり内容の正確性を保証するものではありません。正確な内容に関しては原文を参照ください。
Databricksランタイム(DBR)におけるH3サポートの初期リリースに続き、H3によるかつてないほどのパフォーマンス改善、4つの新たなエクスプレッションのサポート、Databricks SQLでのサポートを共有できることを嬉しく思っています。本書では、新たなエクスプレッション、我々のベクトル化カラム指向実装によるパフォーマンスのベンチマーク、H3によるポイントインポリゴンの空間joinにおける複数のアプローチを学びます。
H3パフォーマンスをスーパーチャージ
DatabricksでビルトインのH3機能[AWS | ADB | GCP]を実装した際、これを最高クラスのものにすることをコミットしました。最終的にこれは有用なAPIとパフォーマンスにつながりました。我々の当初のゴールは、PhotonにおけるH3エクスプレッションの性能を少なくとも20%改善すると言うものでした。結果はさらにエキサイティングで印象的なものでした。以下の表では、機能カテゴリーでそれぞれのH3関数を分類し、(基本的にH3ライブラリをインポートする際に利用する)Java H3ライブラリ実装を用いたパフォーマンスに対して、それぞれの関数のパフォーマンスを計測しました。
H3セルIDにはBIGINT表現を用いることを強くお勧めします。BIGINT表現を用いたH3ベースのjoinでのH3セルIDは、文字列表現を用いたよりもさらにパフォーマンスが高くなります。また、入力としてBIGINTを受け取るH3エクスプレッションオーバーロードを使用することを強くお勧めします。さらに、トラバースのエクスプレッションや述語エクスプレッションなどH3ベースのjoinで通常使用されるエクスプレッションにおいては、BIGINTベースのエクスプレッションの絶対的実行時パフォーマンスは文字列ベースのものよりも数倍高速です。
Databricks SQLおよびランタイムにおいてH3エクスプレッションの何が新しいのか？
DBR 11.3移行および現行のDatabricks SQLで利用できる空間分析のためのH3の新たなエクスプレッションが4つあります。最初の二つ、h3_maxchildとh3_minchildは解像度の異なるインデックス階層をトラバースする際の効率的な手段を提供します。以下にmin/max childエクスプレッションの実践的サンプルを示します(テーブルは含めていません):
- Pointsテーブル: 解像度15におけるH3セルのカラム
h3_15を持つ。 - Polygonsテーブル: 圧縮されたH3セルのカラム(オリジナルの解像度は15)として
h3_15_c、ポリゴンIDのカラムとしてidを持つ。
以下のクエリーではそれぞれのポリゴン内のポイントの数を数えます:
SELECT COUNT(*), polygons.id
FROM points, polygons
WHERE points.h3_15
BETWEEN h3_minchild(polygons.h3_15_c, 15) AND h3_maxchild(polygons.h3_15_c, 15)
GROUP BY polygons.id
min/max childエクスプレッションによって、圧縮されたポリゴンから得られるH3セルIDを操作することができ、クエリーを高速化する可能性のあるフィルタとして動作します。
また、一般的なジオメトリフォーマット: WKT, WKB, GeoJSONですでに格納されているインデックスポイントデータのためのシンプルな関数を追加しました。h3_pointash3やh3_pointash3string関数はそれぞれBIGINTと文字列としてH3セルIDを返却します。
H3階層によるポイントインポリゴンの近似
クエリーパターン: 単一解像度のjoin
以前のブログでは、H3有り無しでのポイントインポリゴンのjoinのアプローチを紹介しました。ここでは、以下の初期クエリーに従って、同じtrip_h3とtaxi_zone_h3テーブルからスタートし、H3階層のメリットをどのように活用するのかを検討します:
SELECT /*+ SKEW('t','pickup_cell') */ *
FROM trip_h3 AS t, taxi_zone_h3
WHERE cell = pickup_cell
H3解像度12でのトリップのピックアップ(ポイント)とタクシーゾーン(ポリゴン)を持ち、パフォーマンスのためにセルでZ-orderされたH3テーブルを準備し、10台のAWS m5d.4xlargeワーカーを用いることで、1.22Bのポイントインポリゴンの近似を1.4分で達成することができました。
階層クエリーパターン: H3ペアレントマッチjoinのテスト
単一解像度クエリーパターンに続き、解像度12でのテストの前に、H3解像度8の親にマッチするトリップとタクシーゾーンをテストするためにh3_toparentを追加することで、同じクラスター構成でさらにパフォーマンスを改善することができます。h3_toparent句の追加によって、同じクエリーはたった45秒で実行することができ、40%の改善となりました！ これは、データがすでに解像度8のセルでパーティショニングされているためであり、クエリー計画の最適化の助けとなっています。詳細に関しては添付ノートブックH3 ToParent Discrete Spatial Analysisをご覧ください。これらのクエリーはDBSQLでも実行できます。
SELECT /*+ SKEW('t','pickup_cell') */ *
FROM trip_h3 AS t, taxi_zone_h3
WHERE
-- inclusion of parent check for perf gains
h3_toparent(cell, 8) = pickup_cell_8
AND cell = pickup_cell
h3_toparentの呼び出しは高速であり、オンザフライで実行することや、お使いのテーブルのカラムとして事前計算することができます。適切な親を選択する際にはいくつか目立たない検討事項があります。経験則によると、親の解像度、あるいは、セルをコンパクションする際の最小解像度を選択するというものです。 コンパクトのパターンに従っていない場合でも、H3階層を使うクエリーに指示する際にはこの情報は有用です。
階層クエリーパターン: H3コンパクトjoin
以前のクエリーパターン(コンパクトなし)のように、格納にh3_polyfillash3を用い、単一のH3解像度のポリゴンにZORDERを用いても、NYCサンプルでは全体的にベストなパフォーマンスを達成しましたが、h3_compactを用いて、特定の解像度からポリゴンセルをコンパクトにすることにもメリットがあります。このオペレーションでは、セルの親を削減できる特定の子供のセルのグループを発見するために、セルの配列を分析します。タクシーゾーンを解像度12からコンパクトにすることで、オペレーション後のセルは10倍以上少なくなります。
Newark空港を解像度12でコンパクト化(左)、コンパクト処理なしの解像度12(右)
上の図が示すように、セルのコンパクションはポリゴンあたりのセルの数を劇的に削減します。右の画像はコンパクション前のものであり、h3_uncompactを用いて解像度12に戻すことで同じ結果となります。これは、h3_uncompactはh3_compactへの入力として与えられたのと同じセルに安全に戻すことができるということを意味します。
セル削減における特筆すべき例として、以下のグラフの一番左にあるタクシーゾーンBloomfield / Emerson Hillは解像度12でコンパクションされていない状態の約63K(青で表示)はコンパクションされるとたった約2Kになっています(赤で表示)。
解像度12におけるNYCタクシーゾーンのコンパクションなしH3とコンパクションありの比較
コンパクションは単一の解像度ではなく、複数の解像度のセルを生成します。H3階層構造を取り扱う際には、以下に示すようにそれぞれの六角形の親には若干開店している7つの子供(一部のセルは6つの子供)があることを理解することが有用です。これは、とくに偶数から奇数の解像度間において、ある程度のレンダリングのギャップを引き起こしますが、論理的な包含関係は正確であることに触れることが重要です - コンパクションのように、H3は特定の解像度から派生する階層構造によって、セルに対するロスレスのインデックスです。
H3の階層構造
h3_compactの活用は、州、リージョン、国レベルデータのように、密でもあり疎でもある領域を持つポリゴンに対して大きなメリットを提供します。 適切なポリゴンIDを持ち、それらに対してコンパクションされたセルと、Z-orderingを活用することでベストなパフォーマンスを達成することができます。お使いのすべてのデータで同じ解像度(この場合は12)から常にスタートすべきであるということを注意することが重要であり、さもないと、インデックスの論理的階層包含関係の補償を損ない、結果に一貫性がなくなってしまいます:
h3_toparent(<some_cell_10_bad>, 8) vs h3_toparent(<some_cell_12_good>, 8)
言い換えると、同じ名目上のH3解像度を持つデータからスタートし、H3トラバーサル関数を用いて階層を上下し、名目上の解像度においてデータが安全かつ論理的にオリジナルのデータに対する操作と透過になるまで移動するというものです。
全体的に、コンパクションされていないタクシーゾーンは2.5Mであるのに対して、コンパクションによって合計200Kになり、セルの数を大幅に削減することができます。これは、解像度12のセルの大部分を解像度11(7xꜜ)、10(49xꜜ)、9(343xꜜ)、8(2,401xꜜ)のセルに削減することで実現されています。
コンパクション後のNYCタクシーゾーンのH3解像度の比率
解像度 < 12(コンパクトの解像度)でのアンコンパクションをトライしようとすると、以下のようなエラーを目撃することになります:
SparkIllegalArgumentException: [H3_INVALID_RESOLUTION_VALUE] H3 resolution 11 must be between 12 and 15, inclusive
H3_compactは格納するセルの数を削減したいワークロードで適用することができ、このケースではコンパクションを行わないクエリーパターンと比べて、計算の複雑性を若干増加させるというデメリットを受け入れながらもtaxi_zone_h3c_explodeに適用しています。以下のクエリーは以前のテストで使用したのと同じ10ワーカーのクラスター設定で2分以内に完了しており、同じ1.22Bの結果を得ています。 しかし、追加の句の評価は、コンパクトを行わないクエリーが45秒から1.4分で実行されていたのと比較して、約0.5xから2xのパフォーマンス低下を引き起こしていることを理解することが重要です。 つまり、トレードオフを考慮する必要があります。
SELECT /*+ MERGE(tz) SKEW('t','pickup_cell') SKEW('tz','cell_8') */ *
FROM
trip_h3 as t,
(SELECT
h3_toparent(c_cell, 8) AS cell_8, *
FROM taxi_zone_h3c_explode) AS tz
WHERE
(tz.h3_res = 8 AND t.pickup_cell_8 = tz.cell_8) OR
(t.pickup_cell_8 = tz.cell_8 AND h3_ischildof(t.pickup_cell, tz.c_cell))
テーブルtaxi_zone_h3c_explodeは、行ごとのポリゴンセルc_cellをコンパクトにしたものを格納します:
SELECT explode(h3_compact(h3_polyfillAsH3(<geom_col>, <resolution>)) as c_cell ...
このクエリーは以前の親パターンに適用され、h3_ischildofによって、ピックアップがコンパクト化されたセルの子どもなのかどうかをテストしています。レンダリングのギャップを確認できますが、依然として論理的インデックス空間にピックアップが属しているのかどうかを確認することができます。
解像度12におけるNewark空港とピックアップのコンパクト化されたセル、コンパクト化されていない結果と同じです。
階層クエリーパターン: エクスプロードしないH3コンパクトjoin
上のテーブルtaxi_zone_h3c_explodeのように行あたりそれぞれのポリゴンセルを持つjoinテーブルを格納せずに、お使いのデータ処理パイプラインに合わせてエクスプロードしていないjoinテーブルを維持するというエクスプロードしないjoinパターンに従う場合には、h3_compactが間違いなく必勝の戦略となります。
エクスプロードしないパターンにおける特に優れた利用法は、タクシーゾーンのように固定された境界ではなく、大量かつ多くの場合オーバーラップする固有のイベントに関連する311サービスリクエストを取り扱う際に顕著になります。マンハッタンのようなNYCの最も人口密度の高いエリアにあるそれぞれが低い解像度のH3セル内には、これらの数千のイベントが容易に含まれることになります。いくつかのH3セルにおける数百万のタクシーピックアップと数千の311イベントを結合したい場合には、行の結合ボリュームはすぐに、そして不必要に、数十兆に増加します！ 以下は、エクスプロードしないjoinパターンをサポートする際に様々な311イベントとタクシーピックアップテーブルを表現するUnity CatalogでのData Lineageのサンプルです。他のテーブルから派生したテーブルを確認することができ、それらがどのように派生したのかを理解するために、(表示されていない)カラムをクリックすることができます。
タクシーピックアップ(解像度12)とjoinされたコンパクト化された311イベント(最小10解像度まで)
提供されるリネージの左下の最初の3つのテーブルは、エクスプロードしていないjoinテーブルが派生するイベントポリゴンのコンパクト化を取り扱う一般的なパターンに従っています:
- 解像度10-12のセルを返却する解像度12からコンパクト化された
event_311_h3c -
event_311_h3c_explodeでは、それぞれのコンパクト化されたイベントセル(c_cell)がそれぞれの行にエクスプロードしています -
event_311_h3c_min_maxでは、311イベントのそれぞれのコンパクト化されたセルのcell_10最小解像度を特定します
ここから、最小のコンパクト化された解像度10ごとの配列にイベントIDをグルーピングするcell_unique_keysを生成します。リネージに加えて、(trip_h3からの)タクシーのピックアップの生成IDを解像度12のセルごとの配列にグルーピングするcell_tripsテーブルを生成しています。これらは最小のカラムで効果的にエクスプロードされたテーブルとなります。 これはh3_ischildofを通じてピックアップセルが(解像度10)のイベントセルの親の子どもであるかどうかをテストするシンプルなjoinです:
SELECT *
FROM
cell_trips,
cell_unique_keys
WHERE
-- handle the lat/lon 0 cell
pickup_cell_12 < 631300000000000000 and
h3_ischildof(pickup_cell_12, cell_10)
pickup_cell_12 < 631300000000000000 の句は、NYCエリアの外にあるいくつかのタクシーデータを除外します。上のクエリーによって、解像度12のピックアップのカラムと配列trip_keys、解像度10のイベント、イベントのunique_keysの配列を保持するテーブルgroup_pickup_event_311_h3cにリネージの右端の二つのテーブルがjoinされます。
解像度10の311イベントとjoinされる解像度12のエクスプロードしていないタクシーピックアップ
以下は、100Kの最もアクティブな解像度12のタクシーピックアップのセルと、311イベントの多さで色付けされた解像度の10の対応する親となります。これは、上述のテーブルからカラムpickup_cell_12、num_trip_keys、cell_10、num_unique_keys以外の2つの配列をシンプルに削除することでレンダリングすることができます。
解像度10の311イベントとjoinされた解像度12のタクシーピックアップ
Discrete Spatial Analysisテクニックを適用する際に数多くの選択肢があります。この記事および以前の記事が、皆様の要件にもっとも合致する選択肢を検討する際の助けとなればと思います。以下にハイライトすべきいくつかのテイクアウェイを示します:
- お使いのポリゴンのサイズ(領域)、複雑性(頂点の数)、h3_polyfillash3で選択した解像度に応じて、エクスプロードされていない配列によるセルの数は非常に大きなものとなります。また、配列データを取り扱う際の課題は、お使いのデータセットのポリゴンの数と比較して大きなものとなります。このため、polyfillの後にエクスプロードすることを検討しましょう。
- パフォーマンスゲインは、クエリーにh3_toparentを追加することで達成することができます。この理由は、より高い解像度のセルをテストする前に、低い解像度のセルでよりパーティションを作成するということであり、クエリー計画の最適化の助けとなります。
- エクスプロードしたセルを持つカラムに対するZORDERは効果的です。そうでない場合、様々なWHERE句で使用される他のフィールドに対してZ-ORDERを行います。
- H3の擬似階層の性質を理解し、論理的なインデックス保証を保持するために共通的な解像度からスタートすべきです。
- h3_compactの活用によって、州、リージョン、国レベルのデータのように密、疎の領域があるポリゴンに対しては多くのメリットがあります。適切なポリゴンIDをお持ちな場合、依然としてコンパクト化されたセルをエクスプロードし、それらにZ-ORDERを行うことができます。
- また、エクスプロードしないパターンに従ったとしても、コンパクションは依然として必勝の戦略となりますが、この選択によるトレードオフを認識してください。
次は？
H3はDatabricksにおける離散空間分析の基盤となっており、我々のチームは皆様のクエリーがおより効率的で、エクスプレッションがより柔軟性を持つようにするにはどうすべきかを探索し続けています。ご自身でH3で実験をしたいのであれば、入門マテリアル[AWS | ADB | GCP]をご覧ください。この記事のサンプルをより詳細に確認したいのであれば、これらのノートブックを参照してください - NB01: H3 ToParent Discrete Spatial Analysis | NB02: H3 Compact Discrete Spatial Analysis | NB03: Coincidental Event Discrete Spatial Analysis。