29. 最近傍探索¶
29.1. 最近傍探索とは?¶
しばしば要求される空間クエリに次の物があります:「<クエリ地物>への最短の<候補地物>は何か?」
距離探索と異なり、「最近傍」探索では、候補ジオメトリまでどれだけ遠そうかという計測上の制限は一切含まれません。あらゆる距離の地物を、「最も近い」ものである限り受け付けることになります。
PostgreSQLは、並べ替えた結果集合の速度向上のためにデータベースにインデックスを使用するよう誘導する "order by distance" (<->) 演算子の導入によって最近傍問題を解決しました。あるべき "order by distance" 演算子との併用で、順序の設定と、N 個の集合の結果を得るための制限とを追加することで、最近傍クエリは「N 番目の最も近い地物」を返すことができます。
"order by distance" 演算は、ジオメトリ型、ジオグラフィ型の両方で動作します。二つの型の動作の差は、返される距離値です。ジオメトリでは <-> は ST_Distance と同じで、使用している空間参照系の単位に依存します。ジオグラフィでは、ST_Distance(geography,geography) が返す精度の高い回転楕円体面上の距離でなく、球面距離値を返します。
'Broad St' 地下鉄駅に三つの最も近いストリートは次の通りです:
-- Get the geometry of Broad St
SELECT ST_AsEWKT(geom, 1)
FROM nyc_subway_stations
WHERE name = 'Broad St';
SRID=26918;POINT(583571.9 4506714.3)
-- Plug the geometry into a nearest-neighbor query
SELECT streets.gid, streets.name,
ST_Transform(streets.geom, 4326),
streets.geom <-> 'SRID=26918;POINT(583571.9 4506714.3)'::geometry AS dist
FROM
nyc_streets streets
ORDER BY
dist
LIMIT 3;
gid | name | dist
-------+-----------+--------------------
17385 | Wall St | 0.749987508809928
17390 | Broad St | 0.8836306235191059
17436 | Nassau St | 1.3368280241070414
インデックスによるクエリをどの程度確定されられるでしょうか? 最近傍クエリの "EXPLAIN" 出力を確認するのが良い考えです。正しい答えを非インデックス SQL から得ることができ、テーブルのスケールアップが無い限りインデックスの欠如が明白にはならないことがあるためです。
EXPLAIN からの出力を示しますが、インデックススキャンは ORDER BY に対して実行しています:
QUERY PLAN
---------------------------------------------------------------------------------
Limit (cost=0.28..79.58 rows=3 width=31)
-> Index Scan using nyc_streets_geom_idx on nyc_streets streets
(cost=0.28..504685.12 rows=19091 width=31)
Order By:
(geom <-> '0101000020266900000EEBD4CF27CF2141BC17D69516315141'::geometry)
29.2. 最近傍結合¶
インデックスによる ORDER BY 演算子は、演算子の一方が**単一ジオメトリリテラル**でないと動作しないという、大きな欠点があります。これはあるクエリオブジェクトに最も近いオブジェクトを探索する場合は良いのですが、候補から一つずつオブジェクトを抜き出して最近傍を検索することを目的とする空間結合には役立ちません。
幸運なことに、ループ内で繰り返し駆動されるクエリの実行が可能になる SQL 言語機能 LATERAL join があります。
地下鉄駅ごとに最も近いストリートを探索します:
SELECT subways.gid AS subway_gid,
subways.name AS subway,
streets.name AS street,
streets.gid AS street_gid,
streets.geom::geometry(MultiLinestring, 26918) AS street_geom,
streets.dist
FROM nyc_subway_stations subways
CROSS JOIN LATERAL (
SELECT streets.name, streets.geom, streets.gid, streets.geom <-> subways.geom AS dist
FROM nyc_streets AS streets
ORDER BY dist
LIMIT 1
) streets;
CROSS JOIN LATERAL が地下鉄テーブルで駆動するループ内の処理部分として動作します。地下鉄テーブルの個々のレコードは LATERAL サブクエリにどんどん送られるので、地下鉄レコードごとの最近傍の結果を得ます。
EXPLAIN は地下鉄駅のループと、求めるループ内のインデックスによる ORDER BY を表示します:
QUERY PLAN
-------------------------------------------------------------------------
Nested Loop (cost=0.28..13140.71 rows=491 width=37)
-> Seq Scan on nyc_subway_stations subways
(cost=0.00..15.91 rows=491 width=46)
-> Limit
(cost=0.28..1.71 rows=1 width=170)
-> Index Scan using nyc_streets_geom_idx on nyc_streets streets
(cost=0.28..27410.12 rows=19091 width=170)
Order By: (geom <-> subways.geom)
