SQL Academy · レッスン

距離と最近傍探索

Q: 「距離と最近傍探索」で何を学びますか？

近くにあるものを見つけます ブラウザで直接実行するハンズオンコードでSQL Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

近くにあるものを見つけます

「距離と最近傍探索」はCoddyKit上の無料SQL Academyレッスンです。これはレッスン2/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはSQL Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 SQL Academyコースには全4レッスンが含まれています。

空間距離とは

地理空間データベースにおける距離とは、2つの地理的な位置の間隔を測定したものです。PostGISには、点、線、ポリゴン、その他のgeometry型の間の距離を計算する強力な関数が用意されています。

距離クエリを理解すると、自分の現在地から最も近いレストランはどこか、倉庫から5 km以内にいる顧客は誰かといった質問に答えられるようになります。

ST_Distance関数

ST_Distance(geom_a, geom_b)は、2つのgeometryオブジェクト間の最短距離を返します。デフォルトでは、通常のgeometry型を使用した場合、結果は座標参照系と同じ単位になります（EPSG:4326では通常、度単位です）。

意味のあるメートル単位の結果を得るには、geography型を使用するか、データを再投影してください。

SELECT ST_Distance(
  ST_MakePoint(28.9784, 41.0082)::geography,
  ST_MakePoint(29.0100, 41.0200)::geography
) AS distance_meters;

サンプルテーブルの準備

地理座標を持つ場所の簡単なテーブルを作成しましょう。geography型を使用するため、すべての距離計算が自動的にメートル単位で返され、手動で投影する必要はありません。

このテーブルには、都市内のカフェを格納します。各カフェには名前と、点として格納された位置情報があります。

CREATE TABLE cafes (
  id SERIAL PRIMARY KEY,
  name TEXT NOT NULL,
  location GEOGRAPHY(Point, 4326)
);

INSERT INTO cafes (name, location) VALUES
  ('Cafe Alpha',   ST_MakePoint(28.9784, 41.0082)::geography),
  ('Cafe Beta',    ST_MakePoint(28.9900, 41.0150)::geography),
  ('Cafe Gamma',   ST_MakePoint(29.0100, 41.0200)::geography),
  ('Cafe Delta',   ST_MakePoint(28.9650, 40.9980)::geography),
  ('Cafe Epsilon', ST_MakePoint(29.0250, 41.0350)::geography);

固定点からの距離を求める

位置データがあれば、各行から基準点までの距離を計算できます。ここでは、座標（28.9800, 41.0100）にいるユーザーから各カフェまでの距離を計算します。

geography型を使用しているため、結果はメートル単位です。

SELECT
  name,
  ROUND(
    ST_Distance(
      location,
      ST_MakePoint(28.9800, 41.0100)::geography
    )::NUMERIC
  ) AS distance_m
FROM cafes
ORDER BY distance_m;

最近傍検索の<->演算子

PostGISには、インデックスを利用できる<->演算子（KNN — K Nearest Neighbors）が用意されています。ORDER BY句でST_Distanceを使う場合とは異なり、<->はGiST空間インデックスを利用して、すべての行をスキャンせずに済みます。

最近傍を効率的に取得する必要がある場合は、ORDER BYでは常に<->を優先してください。対応するインデックスは次のように作成します。

CREATE INDEX ON cafes USING GIST (location);

SELECT
  name,
  ROUND(
    ST_Distance(
      location,
      ST_MakePoint(28.9800, 41.0100)::geography
    )::NUMERIC
  ) AS distance_m
FROM cafes
ORDER BY location <-> ST_MakePoint(28.9800, 41.0100)::geography
LIMIT 5;

距離でフィルタリングする（ST_DWithin）

ST_DWithin(geom_a, geom_b, distance)は、2つのgeometryが指定した距離以内にある場合にTRUEを返します。geography型では、距離はメートル単位です。

これは、WHERE句でST_Distance(...) < radiusを使うよりも効率的です。ST_DWithinはインデックスを利用でき、条件を満たすと早い段階で処理を停止するためです。

SELECT
  name,
  ROUND(
    ST_Distance(
      location,
      ST_MakePoint(28.9800, 41.0100)::geography
    )::NUMERIC
  ) AS distance_m
FROM cafes
WHERE ST_DWithin(
  location,
  ST_MakePoint(28.9800, 41.0100)::geography,
  2000
)
ORDER BY distance_m;

半径制限付きで上位N件の最近傍を取得する

本番環境でよく使われるパターンは、ST_DWithinを事前フィルターとして使用し、<->で並べ替える方法です。ST_DWithinのチェックで空間インデックスを使用して遠い行をすばやく除外し、残った候補を正確な距離で並べ替えます。

これにより、最大半径内にある最近傍のN個の位置を非常に効率よく取得できます。

SELECT
  name,
  ROUND(
    ST_Distance(
      location,
      ST_MakePoint(28.9800, 41.0100)::geography
    )::NUMERIC
  ) AS distance_m
FROM cafes
WHERE ST_DWithin(
  location,
  ST_MakePoint(28.9800, 41.0100)::geography,
  5000
)
ORDER BY location <-> ST_MakePoint(28.9800, 41.0100)::geography
LIMIT 3;

2つのテーブル間の距離（クロス距離）

JOINとST_Distanceを組み合わせると、異なる2つのテーブルの行同士の距離を計算できます。これは、たとえば各顧客を最寄りの倉庫に、各インシデントを最寄りの病院に対応付ける場合に便利です。

以下では、強力なPostgreSQLのパターンである行ごとのサブクエリ向けのlateral joinを使い、usersテーブルの各ユーザーに最も近いカフェを見つけます。

SELECT
  u.username,
  c.name AS nearest_cafe,
  ROUND(ST_Distance(u.location, c.location)::NUMERIC) AS distance_m
FROM (
  VALUES
    ('alice', ST_MakePoint(28.9810, 41.0095)::geography),
    ('bob',   ST_MakePoint(29.0200, 41.0300)::geography)
) AS u(username, location)
CROSS JOIN LATERAL (
  SELECT name, location
  FROM cafes
  ORDER BY location <-> u.location
  LIMIT 1
) c;

距離の出力を整形する

メートル単位の未加工の距離は読みにくいことがあります。CASE式と文字列フォーマットを使って、キロメートル単位に変換したり、人間にわかりやすいラベルを追加したりできます。次のクエリでは、短い距離はメートル単位で、長い距離はキロメートル単位で表示します。

SELECT
  name,
  CASE
    WHEN ST_Distance(location, ST_MakePoint(28.9800, 41.0100)::geography) < 1000
    THEN ROUND(ST_Distance(location, ST_MakePoint(28.9800, 41.0100)::geography)::NUMERIC)
         || ' m'
    ELSE ROUND((ST_Distance(location, ST_MakePoint(28.9800, 41.0100)::geography) / 1000.0)::NUMERIC, 2)
         || ' km'
  END AS formatted_distance
FROM cafes
ORDER BY location <-> ST_MakePoint(28.9800, 41.0100)::geography;

距離に基づいて順位を付ける

RANK()やROW_NUMBER()などのウィンドウ関数は、距離クエリと非常によく組み合わせて使えます。ユーザーから各位置までの近さに基づいて順位を付けられるため、順位付きのおすすめリストや、近い順に並べた検索結果の作成に役立ちます。

SELECT
  name,
  ROUND(
    ST_Distance(
      location,
      ST_MakePoint(28.9800, 41.0100)::geography
    )::NUMERIC
  ) AS distance_m,
  ROW_NUMBER() OVER (
    ORDER BY location <-> ST_MakePoint(28.9800, 41.0100)::geography
  ) AS proximity_rank
FROM cafes;

理解度チェック

PostGISの距離クエリと最近傍検索についての理解度を確認しましょう。

レッスンのまとめ

このレッスンでは、PostGISで空間距離と最近傍検索を扱う方法を学びました。

ST_Distanceは2つのgeometry間の正確な距離を計算します。自動的にメートル単位で取得するには、geography型を使用してください。
ST_DWithinは空間インデックスを使用して、指定した半径内の行を効率的に絞り込みます。WHERE句ではST_Distance < radiusよりもこちらを優先してください。
ORDER BYの<->演算子（KNN）はインデックスを利用でき、最近傍のN件を取得する最速の方法です。
最も効率的な半径内の上位N件クエリを実現するには、ST_DWithinを事前フィルターとして使用し、<->で並べ替えます。
CROSS JOIN LATERALを使うと、行ごとに別のテーブルから最も近い一致を見つけられます。
ROW_NUMBER()などのウィンドウ関数を使うと、距離順に並べた結果に近さの順位を付けられます。

これらのパターンは、実際のアプリケーションにおける位置情報対応機能の基盤となります。

よくある質問