地理空間分析のためのH3をスーパーチャージ

[Supercharging H3 for Geospatial Analytics \| Databricks Blog](https://www.databricks.com/blog/2023/01/12/supercharging-h3-geospatial-analytics.html)の翻訳です。

:::note warn
本書は抄訳であり内容の正確性を保証するものではありません。正確な内容に関しては原文を参照ください。
:::

[Databricksランタイム(DBR)におけるH3サポート](https://www.databricks.com/blog/announcing-built-h3-expressions-geospatial-processing-and-analytics)の初期リリースに続き、H3によるかつてないほどのパフォーマンス改善、4つの新たなエクスプレッションのサポート、[Databricks SQL](https://www.databricks.com/jp/product/databricks-sql)でのサポートを共有できることを嬉しく思っています。本書では、新たなエクスプレッション、我々のベクトル化カラム指向実装によるパフォーマンスのベンチマーク、H3によるポイントインポリゴンの空間joinにおける複数のアプローチを学びます。

# H3パフォーマンスをスーパーチャージ

DatabricksでビルトインのH3機能[[AWS](https://docs.databricks.com/sql/language-manual/sql-ref-h3-geospatial-functions.html) | [ADB](https://learn.microsoft.com/en-us/azure/databricks/sql/language-manual/sql-ref-h3-geospatial-functions) | [GCP](https://docs.gcp.databricks.com/sql/language-manual/sql-ref-h3-geospatial-functions.html)]を実装した際、これを最高クラスのものにすることをコミットしました。最終的にこれは有用なAPIとパフォーマンスにつながりました。我々の当初のゴールは、[Photon](https://www.databricks.com/jp/product/photon)におけるH3エクスプレッションの性能を少なくとも20%改善すると言うものでした。結果はさらにエキサイティングで印象的なものでした。以下の表では、機能カテゴリーでそれぞれのH3関数を分類し、(基本的にH3ライブラリをインポートする際に利用する)Java H3ライブラリ実装を用いたパフォーマンスに対して、それぞれの関数のパフォーマンスを計測しました。

H3セルIDにはBIGINT表現を用いることを強くお勧めします。BIGINT表現を用いたH3ベースのjoinでのH3セルIDは、文字列表現を用いたよりもさらにパフォーマンスが高くなります。また、入力としてBIGINTを受け取るH3エクスプレッションオーバーロードを使用することを強くお勧めします。さらに、トラバースのエクスプレッションや述語エクスプレッションなどH3ベースのjoinで通常使用されるエクスプレッションにおいては、**BIGINTベースのエクスプレッションの絶対的実行時パフォーマンスは文字列ベースのものよりも数倍高速です。**

![Screenshot 2024-02-11 at 7.59.57.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1168882/202e575f-a5bb-a584-cf8b-a50a0012ebba.png)

# Databricks SQLおよびランタイムにおいてH3エクスプレッションの何が新しいのか？

DBR 11.3移行および現行のDatabricks SQLで利用できる空間分析のためのH3の新たなエクスプレッションが4つあります。最初の二つ、[h3\_maxchild](https://docs.databricks.com/sql/language-manual/functions/h3_maxchild.html)と[h3\_minchild](https://docs.databricks.com/sql/language-manual/functions/h3_minchild.html)は解像度の異なるインデックス階層をトラバースする際の効率的な手段を提供します。以下にmin/max childエクスプレッションの実践的サンプルを示します(テーブルは含めていません):

- Pointsテーブル: 解像度15におけるH3セルのカラム`h3_15`を持つ。
- Polygonsテーブル: 圧縮されたH3セルのカラム(オリジナルの解像度は15)として`h3_15_c`、ポリゴンIDのカラムとして`id`を持つ。

以下のクエリーではそれぞれのポリゴン内のポイントの数を数えます:

```sql
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](https://docs.databricks.com/sql/language-manual/functions/h3_pointash3.html)や[h3\_pointash3string](https://docs.databricks.com/sql/language-manual/functions/h3_pointash3string.html)関数はそれぞれBIGINTと文字列としてH3セルIDを返却します。

# H3階層によるポイントインポリゴンの近似

## クエリーパターン: 単一解像度のjoin

[以前のブログ](https://www.databricks.com/blog/2022/12/13/spatial-analytics-any-scale-h3-and-photon.html)では、H3有り無しでのポイントインポリゴンのjoinのアプローチを紹介しました。ここでは、以下の初期クエリーに従って、同じ`trip_h3`と`taxi_zone_h3`テーブルからスタートし、H3階層のメリットをどのように活用するのかを検討します:

```sql
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](https://docs.databricks.com/sql/language-manual/functions/h3_toparent.html)句の追加によって、同じクエリーはたった45秒で実行することができ、40%の改善となりました！** これは、データがすでに解像度8のセルでパーティショニングされているためであり、クエリー計画の最適化の助けとなっています。詳細に関しては添付ノートブック[H3 ToParent Discrete Spatial Analysis](https://www.databricks.com/wp-content/uploads/notebooks/nb01-h3-toparent-discrete-spatial-analysis.html)をご覧ください。これらのクエリーは[DBSQL](https://docs.databricks.com/ja/sql/index.html#what-is-databricks-sql)でも実行できます。

```sql
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](https://docs.databricks.com/sql/language-manual/functions/h3_polyfillash3.html)を用い、単一のH3解像度のポリゴンに[ZORDER](https://docs.databricks.com/ja/delta/data-skipping.html#data-skipping-with-z-order-indexes-for-delta-lake)を用いても、NYCサンプルでは全体的にベストなパフォーマンスを達成しましたが、[h3\_compact](https://docs.databricks.com/sql/language-manual/functions/h3_compact.html)を用いて、特定の解像度からポリゴンセルをコンパクトにすることにもメリットがあります。このオペレーションでは、セルの親を削減できる特定の子供のセルのグループを発見するために、セルの配列を分析します。**タクシーゾーンを解像度12からコンパクトにすることで、オペレーション後のセルは10倍以上少なくなります。**

![](https://cms.databricks.com/sites/default/files/inline-images/db-446-blog-img-1.png)
*Newark空港を解像度12でコンパクト化(左)、コンパクト処理なしの解像度12(右)*

上の図が示すように、セルのコンパクションはポリゴンあたりのセルの数を劇的に削減します。右の画像はコンパクション前のものであり、[h3\_uncompact](https://docs.databricks.com/sql/language-manual/functions/h3_uncompact.html)を用いて解像度12に戻すことで同じ結果となります。これは、**h3_uncompactはh3_compactへの入力として与えられたのと同じセルに*安全に*戻すことができる**ということを意味します。

セル削減における特筆すべき例として、以下のグラフの一番左にあるタクシーゾーン*Bloomfield / Emerson Hill*は解像度12でコンパクションされていない状態の約63K(青で表示)はコンパクションされるとたった約2Kになっています(赤で表示)。
![](https://cms.databricks.com/sites/default/files/inline-images/db-446-blog-img-2.png)
*解像度12におけるNYCタクシーゾーンのコンパクションなしH3とコンパクションありの比較*

コンパクションは単一の解像度ではなく、複数の解像度のセルを生成します。H3階層構造を取り扱う際には、以下に示すようにそれぞれの六角形の親には若干開店している7つの子供(一部のセルは6つの子供)があることを理解することが有用です。これは、とくに偶数から奇数の解像度間において、ある程度のレンダリングのギャップを引き起こしますが、論理的な包含関係は正確であることに触れることが重要です - コンパクションのように、**H3は特定の解像度から派生する階層構造によって、セルに対するロスレスのインデックスです。**

![](https://cms.databricks.com/sites/default/files/inline-images/db-446-blog-image-3.png)
*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ꜜ)のセルに削減することで実現されています。
![](https://cms.databricks.com/sites/default/files/inline-images/db-446-blog-image-4.png)
*コンパクション後の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のパフォーマンス低下を引き起こしていることを理解することが重要です。* つまり、トレードオフを考慮する必要があります。

```sql
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`をコンパクトにしたものを格納します:

```sql
SELECT explode(h3_compact(h3_polyfillAsH3(<geom_col>, <resolution>)) as c_cell ...
```

このクエリーは以前の親パターンに適用され、[h3\_ischildof](https://docs.databricks.com/sql/language-manual/functions/h3_ischildof.html)によって、ピックアップがコンパクト化されたセルの子どもなのかどうかをテストしています。レンダリングのギャップを確認できますが、依然として論理的インデックス空間にピックアップが属しているのかどうかを確認することができます。
![](https://cms.databricks.com/sites/default/files/inline-images/db-446-blog-img-5.png)
*解像度12におけるNewark空港とピックアップのコンパクト化されたセル、コンパクト化されていない結果と同じです。*

## 階層クエリーパターン: エクスプロードしないH3コンパクトjoin

上のテーブル`taxi_zone_h3c_explode`のように行あたりそれぞれのポリゴンセルを持つjoinテーブルを格納せずに、お使いのデータ処理パイプラインに合わせてエクスプロードしていないjoinテーブルを維持するというエクスプロードしないjoinパターンに従う場合には、`h3_compact`が間違いなく必勝の戦略となります。

エクスプロードしないパターンにおける特に優れた利用法は、タクシーゾーンのように固定された境界ではなく、大量かつ多くの場合オーバーラップする固有のイベントに関連する311サービスリクエストを取り扱う際に顕著になります。マンハッタンのようなNYCの最も人口密度の高いエリアにあるそれぞれが低い解像度のH3セル内には、これらの数千のイベントが容易に含まれることになります。**いくつかのH3セルにおける数百万のタクシーピックアップと数千の311イベントを結合したい場合には、行の結合ボリュームはすぐに、そして不必要に、数十兆に増加します！** 以下は、エクスプロードしないjoinパターンをサポートする際に様々な311イベントとタクシーピックアップテーブルを表現する[Unity Catalog](https://www.databricks.com/jp/product/unity-catalog)での[Data Lineage](https://docs.databricks.com/ja/data-governance/unity-catalog/data-lineage.html)のサンプルです。他のテーブルから派生したテーブルを確認することができ、それらがどのように派生したのかを理解するために、(表示されていない)カラムをクリックすることができます。
![](https://cms.databricks.com/sites/default/files/inline-images/db-446-blog-img-6.png)
*タクシーピックアップ(解像度12)とjoinされたコンパクト化された311イベント(最小10解像度まで)*

提供されるリネージの左下の最初の3つのテーブルは、エクスプロードしていないjoinテーブルが派生するイベントポリゴンのコンパクト化を取り扱う一般的なパターンに従っています:

1. 解像度10-12のセルを返却する解像度12からコンパクト化された`event_311_h3c`
1. `event_311_h3c_explode`では、それぞれのコンパクト化されたイベントセル(`c_cell`)がそれぞれの行にエクスプロードしています
1. `event_311_h3c_min_max`では、311イベントのそれぞれのコンパクト化されたセルの`cell_10`最小解像度を特定します

ここから、最小のコンパクト化された解像度10ごとの配列にイベントIDをグルーピングする`cell_unique_keys`を生成します。リネージに加えて、(`trip_h3`からの)タクシーのピックアップの生成IDを解像度12のセルごとの配列にグルーピングする`cell_trips`テーブルを生成しています。*これらは最小のカラムで効果的にエクスプロードされたテーブルとなります。* これは`h3_ischildof`を通じてピックアップセルが(解像度10)のイベントセルの親の子どもであるかどうかをテストするシンプルなjoinです:

```sql
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されます。
![](https://cms.databricks.com/sites/default/files/inline-images/db-446-blog-img-7.png)
*解像度10の311イベントとjoinされる解像度12のエクスプロードしていないタクシーピックアップ*

以下は、100Kの最もアクティブな解像度12のタクシーピックアップのセルと、311イベントの多さで色付けされた解像度の10の対応する親となります。これは、上述のテーブルからカラム`pickup_cell_12`、`num_trip_keys`、`cell_10`、`num_unique_keys`以外の2つの配列をシンプルに削除することでレンダリングすることができます。
![](https://cms.databricks.com/sites/default/files/inline-images/db-446-blog-img-8.jpg)
*解像度10の311イベントとjoinされた解像度12のタクシーピックアップ*

Discrete Spatial Analysisテクニックを適用する際に数多くの選択肢があります。この記事および[以前の記事](https://www.databricks.com/blog/2022/12/13/spatial-analytics-any-scale-h3-and-photon.html)が、皆様の要件にもっとも合致する選択肢を検討する際の助けとなればと思います。以下にハイライトすべきいくつかのテイクアウェイを示します:

- お使いのポリゴンのサイズ(領域)、複雑性(頂点の数)、[h3\_polyfillash3](https://docs.databricks.com/sql/language-manual/functions/h3_polyfillash3.html)で選択した解像度に応じて、エクスプロードされていない配列によるセルの数は非常に大きなものとなります。また、配列データを取り扱う際の課題は、お使いのデータセットのポリゴンの数と比較して大きなものとなります。このため、polyfillの後にエクスプロードすることを検討しましょう。
- パフォーマンスゲインは、クエリーに[h3\_toparent](https://docs.databricks.com/sql/language-manual/functions/h3_toparent.html)を追加することで達成することができます。この理由は、より高い解像度のセルをテストする前に、低い解像度のセルでよりパーティションを作成するということであり、クエリー計画の最適化の助けとなります。
- エクスプロードしたセルを持つカラムに対する[ZORDER](https://docs.databricks.com/ja/delta/data-skipping.html#data-skipping-with-z-order-indexes-for-delta-lake)は効果的です。そうでない場合、様々なWHERE句で使用される他のフィールドに対してZ-ORDERを行います。
- H3の擬似階層の性質を理解し、論理的なインデックス保証を保持するために共通的な解像度からスタートすべきです。
- [h3\_compact](https://docs.databricks.com/sql/language-manual/functions/h3_compact.html)の活用によって、州、リージョン、国レベルのデータのように密、疎の領域があるポリゴンに対しては多くのメリットがあります。適切なポリゴンIDをお持ちな場合、依然としてコンパクト化されたセルをエクスプロードし、それらにZ-ORDERを行うことができます。
- また、エクスプロードしないパターンに従ったとしても、コンパクションは依然として必勝の戦略となりますが、この選択によるトレードオフを認識してください。

# 次は？

H3はDatabricksにおける離散空間分析の基盤となっており、我々のチームは皆様のクエリーがおより効率的で、エクスプレッションがより柔軟性を持つようにするにはどうすべきかを探索し続けています。ご自身でH3で実験をしたいのであれば、入門マテリアル[[AWS](https://docs.databricks.com/sql/language-manual/sql-ref-h3-geospatial-functions.html) | [ADB](https://learn.microsoft.com/en-us/azure/databricks/sql/language-manual/sql-ref-h3-geospatial-functions) | [GCP](https://docs.gcp.databricks.com/sql/language-manual/sql-ref-h3-geospatial-functions.html)]をご覧ください。この記事のサンプルをより詳細に確認したいのであれば、これらのノートブックを参照してください - [NB01: H3 ToParent Discrete Spatial Analysis](https://www.databricks.com/wp-content/uploads/notebooks/nb01-h3-toparent-discrete-spatial-analysis.html) | [NB02: H3 Compact Discrete Spatial Analysis](https://www.databricks.com/wp-content/uploads/notebooks/nb02-h3-compact-discrete-spatial-analysis.html) | [NB03: Coincidental Event Discrete Spatial Analysis](https://www.databricks.com/wp-content/uploads/notebooks/nb03-coincidental-event-discrete-spatial-analysis.html)。

### はじめてのDatabricks

[はじめてのDatabricks](https://qiita.com/taka_yayoi/items/8dc72d083edb879a5e5d)

### Databricks無料トライアル

[Databricks無料トライアル](https://databricks.com/jp/try-databricks)