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

notion image
 
こんにちは、令和トラベルでバックエンドエンジニアをしている木村です。
MySQLにはSpatial index(R-tree index)という交差や包含など空間的な基準に基づいたインデックスが存在します。本ブログ記事では、このインデックスを使った地理的検索のパフォーマンス検証についてご紹介します。

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

マップ検索機能について

この機能は、地図からホテルをマップ検索できるものです。地図上にホテル価格が表示され、自分の行きたい場所の価格相場の把握にも便利です。
参考:https://prtimes.jp/main/html/rd/p/000000087.000077082.html
参考: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
  • ホテルのテーブル構造 ※関係のないカラムは除外しています
※1. ホテルの緯度経度は外部サーバに問い合わせた結果を格納しています。APIリクエストで取得しており、String型で受け取ったものをそのままDBに登録してしまっています(おそらく言語差分によって精度が損なわれないようにAPIではString型になっています)。今回はこのカラムをそのまま流用しますが、本来はDECIMAL型が適切であり検索パフォーマンスもVARCHAR型より上だった可能性があります。

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

ホテルは緯度と経度を持っているため、これを使って絞り込みを行います。アプローチは二つ考えられます。
  • アプリ画面に表示しているマップの左上P₁(x₁, y₁),と右下 P₂(x₂,y₂)からなる矩形の内側に存在するホテルを取得する
  • アプリ画面に表示しているマップの中心から半径zkmの円の内側に存在しているホテルを取得する
notion image
UIとしてはアプリの画面をフルに使った長方形であるため、今回は前者を採用しています。

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

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

B-tree インデックス

まずは一般的に使われるB-treeインデックスから検証します。
ホテルを取得するクエリは以下となります。 ソウル近辺のホテル取得するクエリとなります。
実行した結果、処理時間は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が使用されました)

実行計画

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

R-tree インデックス

それでは次にR-tree インデックスで検証します。 Spatial index(R-tree index)はnullを許容しないため、このインデックスを作成するにはいくつかのステップが必要です。
矩形内のホテルを取得するクエリは以下です。
実行した結果、処理時間は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インデックスは優れたパフォーマンスを発揮します。

参考資料

最後に

令和トラベルでは、このような技術的な知識や知見・成果を共有するLT会を毎月実施しています。発表テーマや令和トラベルに興味をお持ちいただいた方は誰でも気軽に参加いただけます。
2月はVoicyさん、タイミーさんと合同開催になります!各社の異なる技術スタックについてお話しするので、ぜひご参加ください!
 
また、この記事を読んで会社やプロダクトについて興味を持ってくれた方は、ぜひご連絡お待ちしています!
フランクに話だけでも聞きたいという方は、カジュアル面談も実施できますので、お気軽にお声がけください。
 
それでは次回のブログもお楽しみに!Have a nice trip!!

# backend