H3を使用した BigQueryでの空間クラスタリングについて検証してみた

こんにちは、タイミーのデータエンジニアリング部データサイエンス（以下DS）グループ所属の菊地です。

今回は、H3を使用したBigQueryでの空間クラスタリングについて検証した内容を紹介したいと思います！

BigQueryでの空間クラスタリングとは

BigQueryにはクラスタリングという機能があり、うまく活用すると、クエリのパフォーマンスを向上させ、クエリ費用を削減できます。

クラスタリングは空間データにも適用でき、BigQuery がデフォルトで使用するS2インデックスシステムを使用して、空間クラスタリングを行うことができます。

また、H3やGeohashなどの他の空間インデックスに対しても空間クラスタリングを行うことができ、今回はタイミーでも良く使用しているH3を使用して、空間クラスタリングを行う方法を検証してみました。

BigQueryでのクラスタリング及び空間クラスタリングについては、下記の記事が参考になるかと思います。

cloud.google.com cloud.google.com

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

上記の参考記事でも挙げましたが、基本的にこちら記事の内容に沿いつつ、一部具体の実装が記載されていない箇所を補完しながら検証を行いました。 cloud.google.com

1. 検証用のテーブル作成

検証用のテーブルとして、経度と緯度のランダムポイントを、H3セルID（解像度13）に変換したテーブルを作成します。

DECLARE H3_INDEX_RESOLUTION INT64 DEFAULT 13;

-- 連番を格納しておくためだけのテーブル
-- CTEだと後続のテーブル作成が遅かったので実テーブルにしてます
CREATE OR REPLACE TABLE `tmp.tmprows` as
SELECT x FROM UNNEST(GENERATE_ARRAY(1, 10000)) AS x;

-- 経度と緯度のランダムポイントを、H3セルID（解像度13）に変換したテーブル
DROP TABLE IF EXISTS `tmp.h3_points`;
CREATE OR REPLACE TABLE `tmp.h3_points`
CLUSTER BY h3_index
AS 
WITH points AS (
  SELECT 
    `carto-os`.carto.H3_FROMLONGLAT(RAND() * 360 - 180, RAND() * 180 - 90, H3_INDEX_RESOLUTION) AS h3_index
    -- 後の検証のために追加
    , RAND() AS amount
  FROM 
    `tmp.tmprows` AS _a
    CROSS JOIN `tmp.tmprows` AS _b
)
select 
  h3_index
  , amount
FROM points

テーブルのストレージ情報と内容は以下のようになります。

2. クラスタリングによる絞り込みが効かないクエリ例

次に、参考記事で紹介されているように、親セルID（今回は解像度7）をWHERE句で指定してクエリを実行してみましたが、このクエリはテーブルをフルスキャンしてしまいます。

DECLARE PARENT_CELL_ID STRING DEFAULT '870000000ffffff'; -- H3解像度7のセルID

SELECT
    ROUND(SUM(amount), 6) AS sum_amount
FROM 
    `tmp.h3_points`
WHERE `carto-os`.carto.H3_TOPARENT(h3_index, 7) = PARENT_CELL_ID

ジョブ情報と結果

H3インデックスでクラスタリングを行っているにもかかわらず、テーブルをフルスキャンしてしまう理由としては、

H3_ToParentにはビット演算が関係し、複雑すぎて BigQuery のクエリアナライザが、クエリの結果がクラスタ境界にどのように関連しているかを把握できないために発生します。

と参考記事では言及されています。

3. クラスタリングによる絞り込みが効くクエリ例

次に、クラスタリングによる絞り込みが適用されるクエリを検証してみます。

「2. クラスタリングによる絞り込みが効かないクエリ例」との違いとしては、低解像度の親セルに含まれる、高解像度セルの開始IDと終了IDを取得し、WHERE句で指定していることです。

DECLARE H3_PARENT_ID STRING DEFAULT '870000000ffffff';  -- H3解像度7のセルID
DECLARE H3_INDEX_RESOLUTION INT64 DEFAULT 13;

DECLARE RANGE_START STRING;
DECLARE RANGE_END STRING;

-- 低解像度の親セルに含まれる、高解像度セルの開始IDと終了IDを取得しセットする
SET (RANGE_START, RANGE_END) = (
  SELECT AS STRUCT
    `carto-os`.carto.H3_TOCHILDREN(H3_PARENT_ID, H3_INDEX_RESOLUTION)[0],
    ARRAY_REVERSE(`carto-os`.carto.H3_TOCHILDREN(H3_PARENT_ID, H3_INDEX_RESOLUTION))[0]
);

SELECT
  ROUND(SUM(amount), 6) AS sum_amount
FROM
  `tmp.h3_points`
WHERE 
  h3_index BETWEEN RANGE_START AND RANGE_END

ジョブ情報と結果は以下のようになっており、スキャン量が削減され、クエリのパフォーマンスも向上しています。クエリ結果も「2. クラスタリングによる絞り込みが効かないクエリ例」の結果と合致しています。

ジョブ情報と結果

まとめ

H3を使用した BigQueryでの空間クラスタリングについて検証してきました。

タイミーでは位置情報を活用した分析を行うシーンが多く、うまく活用することで機械学習時の特徴量生成や、BIツールからのクエリ最適化に繋げることができる可能性があるので、今後のデータ分析に活かしていきたいと思います。

We’re Hiring!

タイミーのデータエンジニアリング部・データアナリティクス部では、ともに働くメンバーを募集しています！！

現在募集中のポジションはこちらです！

「話を聞きたい」と思われた方は、是非一度カジュアル面談でお話ししましょう！

Timee Product Team Blog

タイミー開発者ブログ