Backend

MySQLのSpatial index(R-tree index)を使った地理的検索のパフォーマンス検証

2024/01/23

| yuta kimura

マップ検索機能と前提条件

マップ検索機能について

この機能は、地図からホテルをマップ検索できるものです。地図上にホテル価格が表示され、自分の行きたい場所の価格相場の把握にも便利です。

参考：https://prtimes.jp/main/html/rd/p/000000087.000077082.html

この機能実現のために、APIの仕様としては以下二つの担保が必要となります。

アプリ上に表示されているマップのエリア内に含まれるホテルを返すこと

マップの移動や拡大・縮小に伴う操作でホテルを再取得する必要があり、そういった操作に耐えうるレスポンス速度であること

前提条件

ホテルのデータは70万軒以上

検証環境

MacBookPro(Apple M1 Pro, 2021)
localのDocker環境で実行

Docker

CPU: 4core
Memory: 8GB
Storage: 256GB

Database

MySQL v8.0.33

ホテルのテーブル構造　※関係のないカラムは除外しています


CREATE TABLE `hotel` (
  `id` int NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `map_lat` varchar(255) NOT NULL, -- ※1
  `map_lng` varchar(255) NOT NULL, -- ※1
  `rank` int DEFAULT NULL, -- ソートで使用
  PRIMARY KEY (`id`),
)

※1. ホテルの緯度経度は外部サーバに問い合わせた結果を格納しています。APIリクエストで取得しており、String型で受け取ったものをそのままDBに登録してしまっています(おそらく言語差分によって精度が損なわれないようにAPIではString型になっています)。今回はこのカラムをそのまま流用しますが、本来はDECIMAL型が適切であり検索パフォーマンスもVARCHAR型より上だった可能性があります。

地理的検索クエリについて

ホテルは緯度と経度を持っているため、これを使って絞り込みを行います。アプローチは二つ考えられます。

アプリ画面に表示しているマップの左上P₁(x₁, y₁),と右下 P₂(x₂,y₂)からなる矩形の内側に存在するホテルを取得する

アプリ画面に表示しているマップの中心から半径zkmの円の内側に存在しているホテルを取得する

UIとしてはアプリの画面をフルに使った長方形であるため、今回は前者を採用しています。

B-tree インデックス vs R-tree インデックス

それでは実際に二つのインデックスを作成し、処理時間を比較していきます。

B-tree インデックス

まずは一般的に使われるB-treeインデックスから検証します。


CREATE INDEX idx_map_lat_lng ON hotel(map_lat, map_lng);

ホテルを取得するクエリは以下となります。ソウル近辺のホテル取得するクエリとなります。


SET @x1 = 37.498405, @y1 = 126.895084, @x2 = 37.601046, @y2 = 127.038838;
SELECT * FROM hotel WHERE map_lat BETWEEN x1 AND x2 AND map_lng BETWEEN y1 AND y2 ORDER BY `rank` LIMIT 50;

実行した結果、処理時間は4.71sでした。実行計画を確認したところ、適切にindexはされましたが、結果の取得時間はアプリの仕様を考慮すると物足りません。また、他にもNEWTで人気のあるエリアでいくつか実行しましたが、処理時間はまちまちで安定しませんでした。

実行結果まとめ

ソウル

(37.601046, 126.895084), (37.498405, 127.038838)
4.71 sec

ホノルル

(21.404024, -157.944242), (21.265405, -157.786248)
0.90 sec

パリ

(48.898167, 2.249380), (48.824151, 2.410848)
7.91 sec

マドリード

(40.546225, -3.805035), (40.362755, -3.529107)
9.02 sec

北京

(40.007245, 116.207906), (39.836776, 116.514156)
55.28 sec　（実行計画によるとソートで仕様しているrankのindexが使用されました）

実行計画

想定通りのインデックスが使われたもの


+----+-------------+-------+------------+-------+-----------------+-----------------+---------+------+------+----------+---------------------------------------+
| id | select_type | table | partitions | type  | possible_keys   | key             | key_len | ref  | rows | filtered | Extra                                 |
+----+-------------+---------------+------------+-------+-----------------+-----------------+---------+------+------+----------+-------------------------------+
|  1 | SIMPLE      | hotel | NULL       | range | idx_map_lat_lng | idx_map_lat_lng | 2044    | NULL | 3416 |    11.11 | Using index condition; Using filesort |
+----+-------------+-------+------------+-------+-----------------+-----------------+---------+------+------+----------+---------------------------------------+

ソートのインデックスが使われたもの


+----+-------------+-------+------------+-------+-----------------+----------------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type  | possible_keys   | key            | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+-------+-----------------+----------------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | hotel | NULL       | index | idx_map_lat_lng | idx_hotel_rank | 5       | NULL | 1537 |     0.36 | Using where |
+----+-------------+-------+------------+-------+-----------------+----------------+---------+------+------+----------+-------------+

R-tree インデックス

それでは次にR-tree インデックスで検証します。 Spatial index(R-tree index)はnullを許容しないため、このインデックスを作成するにはいくつかのステップが必要です。


-- nullableなカラムを追加
ALTER TABLE hotel ADD COLUMN geom GEOMETRY NULL SRID 4326;
-- 座標を登録
UPDATE hotel
SET geom = ST_GeometryFromText(CONCAT('POINT(', map_lng, ' ', map_lat, ')'), 4326);

-- non nullableなカラムに変更
ALTER TABLE hotel MODIFY COLUMN geom GEOMETRY NOT NULL SRID 4326;

-- Spatial indexの作成
ALTER TABLE hotel ADD SPATIAL INDEX(geom);

矩形内のホテルを取得するクエリは以下です。


SET @x1 = 37.498405, @y1 = 126.895084, @x2 = 37.601046, @y2 = 127.038838;
-- 矩形データを作成します
SET @rec = ST_PolygonFromText(CONCAT('POLYGON((',
  x1, ' ', y1, ',',
  x1, ' ', y2, ',',
  x2, ' ', y2, ',',
  x2, ' ', y1, ',',
  x1, ' ', y1,
  '))'));
-- ホテル取得クエリ
SELECT
  *
FROM
  hotel
WHERE MBRWithin(
  geom,
  @rec
)
ORDER BY `rank` LIMIT 50;

実行した結果、処理時間は4.71sでした。極端に狭いエリア極端に広いエリアでも検証しましたが、処理時間は安定しました。

実行結果まとめ

ソウル

(37.601046, 126.895084), (37.498405, 127.038838)
0.67 sec

ホノルル

(21.404024, -157.944242), (21.265405, -157.786248)
0.35 sec

パリ

(48.898167, 2.249380), (48.824151, 2.410848)
0.81 sec

マドリード

(40.546225, -3.805035), (40.362755, -3.529107)
0.31 sec

北京

(40.007245, 116.207906), (39.836776, 116.514156)
0.31 s

結論

このブログでは、MySQLにおける地理的検索クエリのパフォーマンスチューニングに焦点を当てました。具体的には、二次元の地理データ（緯度と経度）を持つホテル情報に基づき、B-treeインデックスとR-treeインデックスのパフォーマンスを比較しました。

B-treeインデックスの限界

B-treeインデックスは一次元データに適していますが、地理的な範囲検索や複合的な空間クエリには不向きです。複合インデックスを使用しても、二次元データにおいてはデータの空間的な隣接性を捉えることができず、検索効率が低下します。

R-treeインデックスの優位性

一方、R-treeインデックスは、地理的なデータの空間的な配置と隣接性を考慮に入れた設計に基づいています。これにより、地理的に近いオブジェクトがデータベース内で物理的にも近い位置に格納されるため、空間的なクエリの処理が高速化されます。特に、地理的範囲検索や近接検索において、R-treeインデックスは優れたパフォーマンスを発揮します。