はじめに
こんにちは。株式会社ナウキャストのデータエンジニア、徳山です。現在所属しているData Holder Unit（DHU）では、データ整備などを担当しています。株式会社ナウキャストの商業用不動産・店舗ビジネス向けDataLens店舗開発において、物件情報を活用する検証の一環として、駅周辺に存在する物件のリストアップ検索を高速化するためにH3インデックスを作成しました。本日は、H3 Indexを用いた検索の高速化についてご紹介させていただきます。
H3 Indexのおさらい
H3はUberが開発した大小様々な六角形（五角形も存在します）をグリッドとする新しいインデックスシステム（座標システム）です。UberはH3をオープンソース化して、JavaScript, Pythonなどのライブラリも存在します。
インデックスシステムの特徴として、地上のエリアに固有のインデックスを付与することが挙げられます。インデックスを活用することで、緯度・経度を用いたジオメトリ計算と比較して、様々なメリットが得られます。
- H3をインデックスとして利用することで、近接検索、空間分析、クラスタリングなどの処理を高速に実行できます。緯度・経度を用いた計算と比較すると、パフォーマンスの面で優位性があります。
- H3インデックスは大きさを調整できるため、要件などに柔軟に対応できる分析・可視化を作成することが可能です。
H3は他のインデックスシステム（Geohash（四角形）、S2）と比べて以下の利点があります。
- 隣接するグリッドとの距離がGeohashなどの四角形グリッドに比べて均等です。
- 隣接するグリッドがほぼ必ず6個存在します（六角形の代わりに五角形を使用するエリアがあります）。
- 各六角形にはユニークなインデックスがあり、迅速な空間検索やクエリが可能です。
- StringおよびIntegerのインデックスをサポートしています。
- Integerのインデックスを使用することで、JOINなどのパフォーマンスを向上させることができます。
Map of San Francisco Bay with hexagonal tiling acquired using Uber 's H3 library plotted on top of it by Isaac Brodsky – Licensed under the Apache License 2.0 (http://www.apache.org/licenses/LICENSE-2.0)
H3 Resolution
H3にはResolution（解像度）が存在し、Resolutionの値が大きくなるほどH3 Indexがカバーする面積は小さくなります。H3の公式サイトには、Resolutionごとの平均面積、最小面積、最大面積、およびエッジ長が記載されています。
H3 Indexを用いた検索の高速化
Snowflake上でH3 Indexを座標から取得するためには以下のfunctionを使用できます。
-
h3_point_to_cell_string
- 座標が位置するH3 Indexを計算
- varchar型を返す
-
h3_grid_disk
- 座標が位置するH3 Indexと周辺のH3 Indexを計算
- array型を返す
H3 Indexを利用した検索高速化の検証
全てのクエリはSnowflakeのsmallウェアハウスを使用して「渋谷駅周辺1km以内の物件を取得する」のテーマで実行時間を計算しています。
物件データ・渋谷駅のデータを取得するためのクエリ
以下のクエリを用いて、物件名、物件の座標、および渋谷駅の座標を取得しています。h3_point_to_cellのresolutionは、検証時には4に設定していますが、ご自由に変更可能です。
create or replace temp table properties as
select distinct
t1.property_name property_name,
st_makepoint(longitude, latitude) as point,
h3_point_to_cell_string(st_makepoint(longitude, latitude), 4) h3_index,
from
all_properties t1 -- 物件が保存されているテーブル
inner join
address_for_properties t2
using (property_number) -- 物件に位置情報を付与
where t2.address is not null
;
create or replace temp table shibuya_station as
select
station_name,
st_makepoint(lon, lat) as point,
h3_point_to_cell_string(st_makepoint(lon, lat), 4) h3_index,
h3_grid_disk(
h3_point_to_cell_string(st_makepoint(lon, lat), 4), 1
) as h3_grid_disk_str, -- Array型で保存されます
from
station_data -- 日本全国の駅データが保存されているテーブル
where e_status = 0 and station_name = '渋谷' and line_code = '11302'
;
サンプルデータ
properties
| property_name | point | h3_index |
|---|---|---|
| 〇〇建設ビル | {"coordinates": [1.359181480000000e+02,3.499806700000000e+01],"type": "Point"} | 842e615ffffffff |
| 〇〇ビル | {"coordinates"": [1.363272630000000e+02,3.601317700000000e+01],"type": "Point"} | 842e623ffffffff |
| ... | ... | ... |
shibuya_station
| station_name | point | h3_index | h3_grid_disk_str |
|---|---|---|---|
| 渋谷 | {"coordinates": [1.397012380000000e+02,3.565887100000000e+01],"type": "Point"} | 842f5a3ffffffff | ["842f5a3ffffffff","842f5a1ffffffff","842f5a7ffffffff","842e749ffffffff","842f5b5ffffffff","842f5bdffffffff","842f5abffffffff"] |
H3 Indexを使用しない場合の検索
select
t1.property_name,
t1.address
from
properties as t1
inner join shibuya_station t2
-- 渋谷駅周辺1km以内の店舗を取得
on st_distance(t1.point, t2.point) <= 1000
;
h3_point_to_cell_stringを用いた検索の高速化
select
t1.property_name,
t1.address
from
properties as t1
inner join shibuya_station as t2
using (h3_index)
where
-- 渋谷駅周辺1km以内の店舗を取得
st_distance(t1.point, t2.point) <= 1000
;
h3_grid_diskを用いた検索の高速化
with h3_grid as (
select
station_name,
point,
h3_grid_disk_str.value h3_grid_disk_index
from
shibuya_station as t1,
-- 複合値を複数の行にフラット化（展開）
lateral flatten(input => h3_grid_disk_str) as h3_grid_disk_str
)
select
t1.property_name,
t1.address
from
properties t1
inner join h3_grid t2
on t1.h3_index = t2.h3_grid_disk_index
where
-- 渋谷駅周辺1km以内の店舗を取得
st_distance(t1.point, t2.point) <= 1000
;
実行時間の比較
| クエリのパターン | 実行時間 |
|---|---|
| H3 Indexを使用しない | 2.5s |
h3_point_to_cell_stringを使用 |
820ms |
h3_grid_diskを使用 |
2.3s |
上記の結果から、H3 Indexを使用することで、H3 Indexを使用しない場合と比較して検索が高速化されることがわかります。h3_grid_diskを使用した場合、配列型を展開する追加の処理が必要になるにもかかわらず、H3 Indexを使用しないケースよりも高速です。
近接エリアの検索にh3_point_to_cell_stringをおすすめする理由
h3_grid_diskはIndexの作成、グループ化、可視化の作成などに便利です。逆に h3_point_to_cell_stringは近接エリアの検索、空間分析などの使用に便利です。
h3_grid_diskを使用した近接エリアも可能なのですが、一つ問題点があります。座標がH3 Indexの端付近にある場合、中心点から半径Nkmなどによって生成されるポリゴンが隣接するH3 Indexと被ることがあります。このとき、中心点が存在するインデックスに基づいて物件をフィルタリングすると、隣接するH3 Indexに位置する物件は計算対象から除外されてしまいます。
h3_point_to_cell_stringを使用することで、上記の問題を回避できます。H3の公式サイトから、Resolutionごとの最小面積と最大面積を取得することで、六角形の最短辺長と最長辺長を算出できます。この情報を利用して、「中心点から半径N km」などのポリゴンを全て含む適切なResolutionを特定できます。「駅周辺N kmの物件を取得する」といった計算を行う場合、h3_grid_diskはh3_point_to_cell_stringと比較して計算量は多くなりますが、「周辺N km」をより正確に取得できます。
Discussion