Uber社で使われている地理的インデックスシステム(H3)をPostgreSQLで利用できるh3-pg拡張機能を試してみました。

これを使ってあなたも世界を六角形で埋めましょう

#Amazon RDS

#AWS

#RDS for PostgreSQL

#PostgreSQL

じゅんや

2023.08.16

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

初めに

先日Amazon RDS for PostgreSQL 16のbeta3がリリースされました。

上記リページには含まれていなかったのですがリリースノート(英語版)側を確認したところh3-pgというなにやら見かけない拡張機能の追加情報が含まれておりました。

調べてみたところUber社が開発しており現在オープンソースとなっているH3と呼ばれる地理的インデックスシステムをPostgreSQLの拡張機能として利用できるようにしたもののようです。

PostgreSQLだけではなく現時点ではC,Python,Java,JavaScript向けにAPIが提供されているためこちらを利用することも可能です。

私自身地理情報システム(GIS)に関してはあまり詳しくないのですが気になるので触りだけでもやってみようと思います。

RDS for PostgreSQL 16 beta 3ではまだ使えない？

今回せっかくRDS for PostgreSQLで対応しているとのことなので試してみようと思いましたがどうやらまだ使えない？（何か設置すればいける？）感じでした。

拡張機能としては実際に存在しているようでしたが有効化してみようとすると共有ライブラリ不足でエラーとなりました。

$ SELECT * FROM pg_available_extensions WHERE name LIKE '%h3%';
    name    | default_version | installed_version |          comment
------------+-----------------+-------------------+----------------------------
 h3_postgis | 4.1.3           |                   | H3 PostGIS integration
 h3         | 4.1.3           |                   | H3 bindings for PostgreSQL
(2 rows)
postgres=> create extension h3;
ERROR:  could not load library "/rdsdbbin/postgres-16.20230807.R1/lib/h3.so": libpq.so.5: cannot open shared object file: No such file or directory

いつものshared_preload_librariesと思ったのですがこちらの場合はそもそも違うエラーなので何か別の原因かと思いますが、beta版というところもあるので不完全な関係か自分の設定のところか切り分けができていません。

$ CREATE EXTENSION plrust;
ERROR:  plrust must be loaded via shared_preload_libraries

betaが抜けた頃には対応するかと思うのでとりあえず今回は一旦置いて別の環境で試してみようと覆います。

RDS for PostgreSQLでも対応していることを確認しました(2023/08/25追記)

本日公開されたマイナーバージョンでh3-pgが正式対応していました。

ドキュメントの方では英語版を含めまだ16-beta3以外に対応している拡張機能として記載がなかったのですが、15.4では実行まで動作を確認しております。

 % psql -h xxxxx.xxxxx.ap-northeast-1.rds.amazonaws.com -U postgres
...
SELECT version();
                                                 version
---------------------------------------------------------------------------------------------------------
 PostgreSQL 15.4 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 7.3.1 20180712 (Red Hat 7.3.1-12), 64-bit
(1 row)
postgres=> create extension h3;
CREATE EXTENSION
postgres=> SELECT h3_cell_to_lat_lng('872f5aadeffffff');
          h3_cell_to_lat_lng
---------------------------------------
 (139.7586016409392,35.66916813197301)
(1 row)
-- h3_postgisがないとできないは未確認
postgres=> create extension h3_postgis cascade;
NOTICE:  installing required extension "postgis"
NOTICE:  installing required extension "postgis_raster"
CREATE EXTENSION

H3とは

どういったものかは以下のUber社のブログにて語られています。
当記事における記載はこちらの記事を読んだ上での自分の理解を一部抜粋したものとなり正確なものではない可能性があるため詳細はUber社のブログをご参照ください。

本当にざっくり概念としては地球上を正六面体のグリッドで埋めそのグリッドを活用することで測量に関する分析を平滑化するための手法のようです。

目的としては前述の通りUberの配送の最適化のためとなりますが、これを行うために地球上を正二十面体として取り扱い、さらにそれをそのまま展開するだけではなくその上にグリッドをを配置するグローバルで離散的な測量システムのようです。

正十二面体での各面はさらに分割され正六角形のグリッドが配置されることで構築されていますが(跨ぎ有)。ただし完全にこれでマッピングすることは無理であったため正二十面体の各面の頂点部分には五角形のグリッドを含めることで対応しているようです。
(五角形グリッドについては作業影響が少なくなるように水面上に配置しているとのこと)

六角形という形を採用した理由としては、グリッドの中心から隣接するグリッドの中心に対しての距離を計算する場合に三角形や四角形では１つにならないが六角形の場合はこれが1つになるというメリットがあり選択がされています。

例えば正方形のグリッドの場合、隣接するグリッドの中央に対する距離の計算には以下の２種類の距離が必要であり分析に対して必要な処理がその分複雑となってしまいます。

正方形の一片の距離
- 面で接する隣接する正方形グリッドへの距離
正方形の対角線の距離
- 点(角)で隣接する正方形のグリッドへの距離)

正六角形の場合隣接するグリッドとは全て面で接しているため、隣接するグリッドへの距離はどの方向であっても常に一意となるため解析の実行時の平滑化のコストを大きく下げることができます。

※　部分的に補助線を入れてるので少しわかりづらいですが全て辺で接してるので一辺の√3倍が2つの中心の距離です

またH3では正六角形の中にはさらに7つの正六角形が、さらにその中にもという形で階層化されており、１６段階の解像度が用意されています。

ただし１つ上のサイズ(大きい側)の六角形を綺麗に7つの正六角形に分割できることは不可能なため、１段階細かな正六角形グリッド群は元のグリッドと綺麗に一致しているわけではなく多少のはみ出し等(歪み)はあるとのことです。

グリッドは一定の形にマッピングされいるためグリッド単体による分割が必ずしもその地域の事情とマッチしているとは限りません。

なので実際にはこのシステムはクラスタリング等の分析を効率的に行うための要素とするためのもののようです。

使ってみる

Amazon Linux 2023(以降AL2023)上にpostgreSQLサーバを立ち上げて試してみます

インストール

バージョンの依存等々の関係でAL2023デフォルトのリポジトリにあるPostgreSQL 15を使うのは手順がややこしくなりそうだったので、fedora 36のリポジトリからPostgreSQL 14やpostgisをインストールする方法をとっています。

$ yum install -y cmake gcc pip
$ yum install -y postgresql{,-server,-server-devel} postgis --enablerepo=fedora36
# initdbだけpostgresユーザで実行
$ initdb
$ service postgresql start
# h3の依存の関係でpostgisが必要なので有効化する
$ psql -U postgres -c "CREATE EXTENSION postgis"
$ psql -U postgres -c "CREATE EXTENSION postgis_raster"
$ pip install pgxnclient
$ pgxn install h3
$ pgxn load h3 -U postgres

fedora36は以前fedora34で試したのと同じような感じでfedora 36の標準リポジトリを参照できるように設定しています。

これで導入は完了です。

実行

docs/api.mdの情報をもとに幾つか処理を実行してみます。

h3_lat_lng_to_cell()に対して地点情報(緯度経度)と解像度を指定することでそのセル(グリッド)を取得できるようなのでこれでクラスメソッド本社のある日比谷フォートタワーの緯度経度を入れて取得してみましょう。

Google Map等からコピペすると(緯度, 経度)で取得されますがPOINTの指定は(経度(x座標), 緯度(y座標))なので注意しましょう。

-- 解像度は16段階(0~15)あるので中間ほどの7を指定してみる
$ SELECT h3_lat_lng_to_cell(POINT('139.75297111216622, 35.670172852452204'), 7);
 h3_lat_lng_to_cell
--------------------
 872f5aadeffffff
(1 row)

返却値はH3Indexというものでドキュメントを読む限りこれが各グリッドの情報となるようです。

h3_cell_to_lat_lng()にh3index情報を指定することでセルの中心、h3_cell_to_boundary()にh3index情報を指定することでそのセルのエッジ（頂点情報)が得られます。

$ SELECT h3_cell_to_lat_lng('872f5aadeffffff');
          h3_cell_to_lat_lng
---------------------------------------
 (139.7586016409392,35.66916813197301)
(1 row)
$ SELECT h3_cell_to_boundary('872f5aadeffffff');
                                                                                                             h3_cell_to_boundary

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------
 ((139.77249490111734,35.66585631052455),(139.7685388815989,35.67813460513031),(139.75464385114776,35.68144488899651),(139.74470957311203,35.672477798907686),(139.74866802714678,35.660
20210153104),(139.76255832579878,35.656890897112085))
(1 row)

上記のポイントを地図上に書き起こしてみます。

赤マーカーが日比谷フォートタワー、青マーカーがセルの中心、緑マーカーがエッジです。

大阪オフィスまでの距離を見てみましょう

-- 大阪オフィスのh3index情報を取得
$ SELECT h3_lat_lng_to_cell(POINT('135.4964737597688, 34.69036403934684'), 7);
 h3_lat_lng_to_cell
--------------------
 872e61051ffffff
(1 row)

-- h3_grid_distance()でs3index間の距離を取ることができる。単位はセル数
$ SELECT h3_grid_distance('872f5aadeffffff','872e61051ffffff');
 h3_grid_distance
------------------
              188
(1 row)

-- h3_get_hexagon_edge_length_avg()でその解像度におけるグリッドの１辺の大体の長さが取れます
$ SELECT h3_get_hexagon_edge_length_avg(7);
 h3_get_hexagon_edge_length_avg
--------------------------------
                    1.220629759
(1 row)

間に188個のグリッドがあるので距離的にはグリッド189個分一辺あたりが約1.2km、先に記載したとおり隣接2つの六角形の中心距離は一辺の√3倍ですので、
２点間の距離は大体399.36km、Google Mapで見る限りも直線距離は概ね400kmですのでグリッドによる丸めや小数点等計算等を考えれば大体そんなものでしょう。