地図ヒートマップの表示を爆速にする

こんにちは。Nishikaのデータサイエンティストの髙山です。
地図ヒートマップにデータを表示する機能のDB部分の設計・開発を検証した際の知見を紹介します。

tl;dr

• PostgreSQL+PostGIS(拡張機能)が、その他アプリケーション機能の開発においても潰しが一番効きそうです
• 狭い範囲のクエリにはGiST索引、広い範囲のクエリについては集約したマテビューを用意して、緯度経度の範囲に応じてクエリを切り替えるのが吉

はじめに

今回開発した機能は以下です。画面ではズームイン・ズームアウトができ、緯度・経度の上限・下限を指定してその矩形の範囲を表示します。
ズームインして狭い範囲のデータを参照する場合は、地図の最小単位のタイルごとの値に基づいて表示され、ズームアウトして広域的なデータを参照する場合は、各タイルの値を平均で集計して値に基づいて表示されます。

今回は狭い範囲のクエリと広い範囲のクエリも高速に実現するための施策を紹介します。あくまでDB部分の設計・開発の話についてフォーカスした内容となっています。ご了承ください。

設計の検討

今回は以下の3点のポイントを踏まえて、以下の構成にしました。検証の環境としてはAWSが前提となっていたのでその中で利用できるサービスを選定しました。

• FE: CloudFront+S3として、Vite + React + TSでdeck.glを地図ヒートマップの可視化に使用する
• BE: EC2、FastAPI
• DB: Amazon RDS for PostgreSQL
  • PostGISを有効化する前提

FE,BEのフレームワークは実装者が慣れているものを選定しています。

1.ズームイン・ズームアウトの際のヒートマップに表示する値の計算をFE,BEのどちらで行うか

ズームイン・ズームアウトの際に都度BEに問い合わせてデータを取得するようにし、FEでの集約の計算は最小限にします。

数十万、数百万のレコードになるとFEで計算に必要な範囲のレコードを取得し、集約の計算を行うには負荷が非常に大きいため、BEで指定の緯度経度の範囲のデータを必要に応じて効率的に取得する。FEではなるべく軽量なデータを集計します。
倍率や範囲が変わるたびに頻繁にクエリが実行されるので1回が長いと表示が非常に遅くなります。

2. 地図ヒートマップの可視化でどのライブラリを使用するか

deck.glを採用しました。他の地図ライブラリとの連携やナレッジが豊富で商用利用可能のツールになります。

こちらは今回の本題ではないのですが、mapbox gl jsには商用利用にライセンス契約が伴うこと、maplibre GL JS, Leafletはアップデート頻度や実装のしやすさを考慮してdeck.glを採用しています。

3. データをどこに置くか

いくつか選択肢がありましたが、以下の判断軸でAmazon RDS for PostgreSQL + PostGISを選びました。

• 地図ヒートマップの表示以外の機能実装で支障がない
• 地理情報のクエリのチューニングで困らない
• コストをなるべく抑えたい

他にも検討したサービスの候補と今回採用しなかった理由を列挙しておきます

• Amazon Document DB
  NoSQLのDBでGeoJSON型のデータをスキーマレスで扱えて、参照用のDBとしては向いていますが、空間データ用のクエリの高度な機能はないところがノックアウトでした。ヒートマップ表示で使用するマルチポイントのクエリのためのインデックスが貼れないことがわかっていました。

Amazon DocumentDB を使用した地理空間データのクエリ > 制限
Amazon DocumentDB は、ポリゴン、ラインストリング、マルチポイント、マルチポリゴン、マルチラインストリング、GeometryCollection のクエリやインデックス作成をサポートしていません。

• Amazon Redshift DB
  上記の空間データ用のクエリの高度な機能というところで言うと、充足しているのですが、サポートされていない PostgreSQL 機能に記載がある通り、一般的なRDBにあるインデックスや制約などPostgreSQLにはある機能がサポートされない点があり、実装コストの増加を懸念しました
  分析用に特化するのであれば性能メリットはあると思うのですが、インフラコストもハードウェアスペックを同程度で条件を揃えた時にRDS PostgreSQLに比べ高いです。

• Amazon Aurora PostgreSQL
  PostgreSQLを使うと言う意味ではこちらも一緒なのですが、運用機能（フェイルオーバー優先順位、バックトラックなど）が充実する反面で、こちらもインフラコストもハードウェアスペックを同程度で条件を揃えた時にRDS PostgreSQLに比べ高いです。

地図ヒートマップを表示するためのSQLのチューニング

事前準備

管理者アカウントでPostGISの拡張機能を有効化します。RDSではデフォルトで有効化はされていませんが、有効化できるようになっています。
今回はPostgreSQL17.4で検証を実施しました

-- PostGIS拡張がインストールされているか確認
SELECT name, default_version, installed_version 
FROM pg_available_extensions 
WHERE name LIKE '%postgis%';
-- postgisの有効化
CREATE EXTENSION postgis;
-- 現在有効な拡張の確認
SELECT extname, extversion 
FROM pg_extension 
WHERE extname LIKE '%postgis%';

ついでにbtree_gistも有効化しておくとB-TreeとGiSTの複合列のインデックスが貼れるようになるので、必要に応じて地図ヒートマップにアクセスする際に緯度経度以外の列も使って絞り込む際に検討するのが良いと思います。
※PostgreSQLの場合、複数のインデックスを使ったアクセスが望ましい場合それに基づいてアクセスされるので、それぞれ別でインデックスを貼る形でも良いと思います。

参考：PostGIS 拡張機能を使用した空間データの管理

狭い範囲のデータ取得のSQLチューニング

地図ヒートマップを表示するために必要なデータの形式とそのSQLクエリを見ていきます

• テーブル定義のイメージ
  インデックスを作る対象の地理情報のgeog列はlongitude, latitudeをもとに、自動で生成される列にしています。

-- 各タイルの全量のデータ
CREATE TABLE heatmap_data (
    -- 座標情報
    longitude FLOAT NOT NULL,
    latitude FLOAT NOT NULL,
    longitude_idx INTEGER NOT NULL, -- 集計用経度インデックス
    latitude_idx INTEGER NOT NULL,  -- 集計用緯度インデックス
    val FLOAT NOT NULL,
    -- ヒートマップの可視化で色を決める0.0~1.0の値
    val_intensity FLOAT NOT NULL 
        CHECK (val_intensity >= 0 AND val_intensity <= 1),
    -- 地理空間カラム（計算列）
    geog GEOGRAPHY GENERATED ALWAYS AS (
        CAST(ST_SetSRID(ST_MakePoint(longitude, latitude), 4326) AS geography)
    ) STORED,
    -- 主キー
    PRIMARY KEY (longitude_idx, latitude_idx)
);

-- 地理空間インデックス
CREATE INDEX idx_log_heatmap_data_geog_cast_gist 
ON heatmap_data USING GIST ((geog::geometry));

• 狭い範囲のクエリのイメージ
  ST_MakeEnvelopeの関数で矩形の範囲の左下と右上の緯度経度を指定して、矩形の範囲にフィルタリングする

SELECT
    longitude,
    latitude,
    val,
    val_intensity
FROM
    heatmap_data
WHERE
    -- geometry型の列について、位置の矩形のbboxと重複するところを取得する
    geog::geometry && ST_MakeEnvelope(
        113.30012, 3.35,  -- 範囲の左下（最小経度, 最小緯度）
        113.35, 3.4,  -- 範囲の右上（最大経度, 最大緯度）
        4326           -- SRID（座標系）
    );

地理情報の列の宣言について

DDLの列定義のこの部分は見慣れないかと思います。

geog GEOGRAPHY GENERATED ALWAYS AS (
        CAST(ST_SetSRID(ST_MakePoint(longitude, latitude), 4326) AS geography)

• ST_MakePoint関数: 緯度・経度を元に頂点を設定する
• ST_SetSRID関数：緯度経度の地理座標系(ESPGコード4326)を設定する

ESPGコード4326はWGS84の世界測地系でGPSで使用されるものになります。0101000020E61000004298BD4E8BC5584063CF273F389B0840のようなバイナリのデータになっておりEWKB形式といい先頭から以下の構成になっているようです。

• １バイト(01)：エンディアン(01:リトルエンディアン,00: ビッグエンディアン)
• ４バイト(01000020)：ジオメトリタイプ
• ４バイト(E6100000)：SRID
• 可変長：座標データ
  • 4298BD4E8BC55840: X座標（経度）
  • 63CF273F389B0840: Y座標（緯度）

狭い範囲のクエリのアクセスパターンについて

実行計画をみると、GiSTインデックスがうまく使用されて、2.5ミリ秒程度の実行時間で高速化できていることがわかります。
heatmap_data表は160万行ほどあり、その中の約数千行(1%未満)を取得する上ではフルスキャンするのではなくインデックスを利用してアクセスした方が効率的です。

Bitmap Heap Scan on heatmap_data  (cost=490.14..19903.10 rows=6417 width=298) (actual time=0.860..2.355 rows=3500 loops=1)
"  Recheck Cond: ((geog)::geometry && '0103000020E61000000100000005000000B6F3FDD478595C40CDCCCCCCCCCC0A40B6F3FDD478595C403333333333330B409A99999999595C403333333333330B409A99999999595C40CDCCCCCCCCCC0A40B6F3FDD478595C40CDCCCCCCCCCC0A40'::geometry)"
  Heap Blocks: exact=161
  ->  Bitmap Index Scan on idx_log_heatmap_data_geog_cast_gist  (cost=0.00..488.54 rows=6417 width=0) (actual time=0.833..0.833 rows=3500 loops=1)
"        Index Cond: ((geog)::geometry && '0103000020E61000000100000005000000B6F3FDD478595C40CDCCCCCCCCCC0A40B6F3FDD478595C403333333333330B409A99999999595C403333333333330B409A99999999595C40CDCCCCCCCCCC0A40B6F3FDD478595C40CDCCCCCCCCCC0A40'::geometry)"
Planning Time: 0.126 ms
Execution Time: 2.527 ms

データアクセスの流れとしては、3つに分かれます。索引を元にheap作っていてアクセスしていて、シンプルな索引スキャンではないので少し複雑です。

• Step1: Bitmap Index ScanでGiSTインデックスのdx_log_heatmap_data_geog_cast_gist索引を走査して、BBoxが重なるR木内のリーフノード※を特定
• Step2: 特定したリーフノードの情報をもとに、アクセスする対象の行をビットマップで整理しHeapに持たせる
  イメージ
  Page1: [1,0,1,1,0,0,1,...] -- 1=該当行あり
  Page2: [0,1,1,0,0,1,0,...]
  ...
• Step3: heapのビットマップをもとに対象の行にアクセス

※リーフノードというのは以下のBBoxの集合を管理するR木の一番したのノードを指します。あくまでラフなイメージです。

Level 3 (Root)
    ┌─────────────────────┐
    │    全体を覆うBBox     │
    └───────┬─────────────┘
            │
    ┌───────┴───────┐
Level 2 (Internal)
┌──────┐        ┌──────┐
│地域A │        │地域B │
└──┬───┘        └──┬───┘
   │               │
┌──┴──┐        ┌──┴──┐
Level 1 (Leaf)
┌───┐ ┌───┐   ┌───┐ ┌───┐
│Obj│ │Obj│   │Obj│ │Obj│
└───┘ └───┘   └───┘ └───┘

GiSTインデックスの説明を参照するとデータアクセスの理解の助けになると思います。空間情報のインデックスにはRDBで主流なB-Treeを拡張したタイプもありますが、PostGISで使われているのはR-Treeの構造になっています。
参考：15.1. どのように空間インデックスが動作するか

R-Treeの説明は空間データのためのRツリーがイメージわかりやすかったです。

広い範囲のデータ取得のSQLチューニング

狭い範囲のデータ取得と同じように緯度経度の範囲を広げて、対象データが多い問い合わせを実行すると、アクセスするデータブロックが増えて、索引を使用せずフルスキャンするため時間がかかります。

Seq Scan on heatmap_data  (cost=0.00..100267.59 rows=861035 width=298) (actual time=0.016..1029.874 rows=1105652 loops=1)
"  Filter: ((geog)::geometry && '0103000020E61000000100000005000000C1CAA145B6535C406666666666660A40C1CAA145B6535C400000000000000C400000000000605C400000000000000C400000000000605C406666666666660A40C1CAA145B6535C406666666666660A40'::geometry)"
  Rows Removed by Filter: 593996
Planning Time: 0.125 ms
Execution Time: 1075.374 ms

実行時間が1秒を超えていて、改善の必要がありそうです。

SQLチューニングの基本的な考えとして、データブロックのアクセスが最小限になるようにSQLや対象のオブジェクトを設計を見直すことを考えます。
ズームアウトした時に広い範囲のデータを参照する必要があり、そこは変えられないので、事前計算済みのマテリアライズドビューを用意して、そこを参照することでデータブロックへのアクセスが最小になるように対処します。

集計したマテビューについても元の表と定義は基本同じにします。

CREATE MATERIALIZED VIEW mv_heatmap_data_summary
SELECT
    longitude_idx / 10 * 10 AS longitude_idx,
    latitude_idx / 10 * 10 AS latitude_idx,
    avg(longitude) AS longitude,
    avg(latitude) AS latitude,
    st_setsrid(st_makepoint(avg(longitude), avg(latitude)), 4326)::geography(Geometry,4326) AS geog
    avg(val) AS val,
    avg(val_intensity) AS val_intensity
FROM heatmap_data
GROUP BY
    (longitude_idx / 10 * 10),
    (latitude_idx / 10 * 10)
;

広い範囲のクエリは参照先を変える形で対応。上記の例では緯度も経度も等間隔でデータがあり、10x10の単位で平均の値を集計する表を作成するので、全データの表に比べて1/100のデータサイズになり、フルスキャンしても2万行程度なので高速に実行できます。

SELECT
    longitude,
    latitude,
    val,
    val_intensity
FROM
    mv_heatmap_data_summary
WHERE
    -- geometry型の列について、位置の矩形のbboxと重複するところを取得する
    geog::geometry && ST_MakeEnvelope(
        113.30012, 3.30,  -- 範囲の左下（最小経度, 最小緯度）
        113.4, 3.4,  -- 範囲の右上（最大経度, 最大緯度）
        4326           -- SRID（座標系）
    );

狭い範囲のSQLと広い範囲のSQLをどう切り替えるか

こちらについては画面で指定される緯度経度の範囲をもとにルールを決め、動的に切り替える必要があります。

BEの処理として切り替えてもいいですし、DBのレイヤで吸収するのであればテーブル関数を実装する形になるかと思います。
切り替えるルールとしては、緯度経度の範囲の入力を元に見積もりのタイル数をルールベースで算出して、閾値を決めて判定するくらいしか策はないかと思います。

例えばテーブル関数で実装するのであれば、以下の関数を定義して

CREATE OR REPLACE FUNCTION public.heatmap_data_grid(
    p_minlon double precision, 
    p_minlat double precision, 
    p_maxlon double precision, 
    p_maxlat double precision
)
RETURNS TABLE(
    longitude double precision, 
    latitude double precision, 
    val double precision, 
    val_intensity double precision
)
LANGUAGE plpgsql
STABLE
AS $function$
DECLARE
    cell_size   constant double precision := 0.00009;
    lon_cells   int := CEIL( (p_maxlon - p_minlon) / cell_size );
    lat_cells   int := CEIL( (p_maxlat - p_minlat) / cell_size );
    n_cells     int := GREATEST(lon_cells, 0) * GREATEST(lat_cells, 0);
    use_mv      boolean := n_cells >= 40000;
BEGIN
    IF use_mv THEN
        -- 閾値を超えた場合はマテリアライズドビュー（クエリ2）を使用
        RETURN QUERY
        SELECT
            mv.longitude,
            mv.latitude,
            mv.val,
            mv.val_intensity
        FROM mv_heatmap_data_summary AS mv
        WHERE mv.geog::geometry && ST_MakeEnvelope(
            p_minlon, p_minlat, 
            p_maxlon, p_maxlat, 
            4326
        );
    ELSE
        -- 閾値未満の場合は通常のテーブル（クエリ1）を使用
        RETURN QUERY
        SELECT
            tbl.longitude,
            tbl.latitude,
            tbl.val,
            tbl.val_intensity
        FROM heatmap_data AS tbl
        WHERE tbl.geog::geometry && ST_MakeEnvelope(
            p_minlon, p_minlat, 
            p_maxlon, p_maxlat, 
            4326
        );
    END IF;
END $function$;

表関数を以下のように呼び出す

SELECT
    longitude,
    latitude,
    val,
    val_intensity 
FROM heatmap_data_grid(
      113.3994, 3.286849, 113.494041, 3.39519934491979
)

という形になるかと思います。

まとめ

地図ヒートマップ機能のDB設計において、PostgreSQL+PostGISの組み合わせは他機能との親和性が高く、実用的な選択肢だと感じました。狭い範囲にはGiSTインデックスによる高速検索、広い範囲には事前集約したマテリアライズドビューを活用し、範囲に応じた動的な切り替えによって安定したパフォーマンスを実現できます。
地理情報系の開発を初めて行ったのもあり、座標系や空間インデックスなど初めて扱う概念も多かったですが、PostGISの豊富な機能で効率的に開発できました。

Nishikaについて

Nishikaは2019年に創業、「テクノロジーですべての人が誇りを持てる社会の実現」をビジョンに掲げ、「テクノロジーを、普段テクノロジーからは縁の遠い人にとっても当たり前の存在としていき、皆の仕事の付加価値・業務効率を向上させることに貢献したい」と考え、活動しています。
AIプロダクト事業/AIコンサルティング・開発事業/AI人材事業を手掛け、AIコンサルティング・開発事業では「生成AIを使うと何が嬉しいのか、通り一遍ではない使い方を知りたい」という段階のお客様から、伴走してご支援するアプローチを強みとしています。

https://info.nishika.com/

We're hiring!

Nishikaテックチームでは、「テクノロジーを、普段テクノロジーからは縁の遠い人にとっても当たり前の存在としていく」を目指し、音声AIプロダクトの開発・生成AIを活用した課題解決ソリューションの構築を行なっています。
興味をお持ちいただけた方は、以下リンクからご応募お待ちしています。インターンも募集しております！
https://nishika0507.notion.site/Careers-at-Nishika-25c33efd5f5f43fe99018c8a16ea4444