29. Närmaste granne-sökning¶
29.1. Vad är en Nearest Neighbour-sökning?¶
En ofta ställd spatial fråga är: ”Vad är det närmaste <candidate feature> till <query feature>?”
Till skillnad från en avståndssökning innehåller sökningen efter ”närmaste granne” inte något mått som begränsar hur långt bort kandidatgeometrierna kan befinna sig. Funktioner på vilket avstånd som helst accepteras, så länge de är de närmaste.
PostgreSQL löser det närmaste grannproblemet genom att införa en ”order by distance” (<->) operatör som inducerar databasen att använda ett index för att påskynda en sorterad returuppsättning. Med en ”order by distance” -operatör på plats kan en närmaste grannfråga returnera ”N närmaste funktioner” bara genom att lägga till en beställning och begränsa resultatuppsättningen till N-poster.
Operatorn ”order by distance” fungerar för både geometri- och geograftyper. Den enda skillnaden mellan hur de fungerar mellan de två typerna är det avståndsvärde som returneras. För geometri <-> returneras samma svar som ST_Distance som är beroende av enheterna i det spatiala referenssystem som används. För geografi är avståndsvärdet som returneras sfäravståndet, istället för det mer exakta sfäroidala avståndet som ST_Distance(geography,geography) returnerar.
Här är de tre närmaste gatorna till ”Broad St” tunnelbanestation:
-- 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
Hur kan vi vara säkra på att vi får en indexassisterad fråga? Det är en bra idé att kontrollera EXPLAIN-utdata för en närmaste granne-fråga, eftersom det är möjligt att få korrekta svar från icke-indexerad SQL och avsaknaden av ett index kanske inte är uppenbart förrän storleken på tabellerna skalas upp.
Det här är utdata från EXPLAIN, notera indexskanningen över 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. Närmaste granne Join¶
Den indexassisterade order by-operatorn har en stor nackdel: den fungerar bara med en enkel geometrilitteral på ena sidan av operatorn. Detta är bra för att hitta de objekt som ligger närmast ett frågeobjekt, men hjälper inte för en spatial join, där målet är att hitta den närmaste grannen för var och en av en fullständig uppsättning kandidater.
Lyckligtvis finns det en funktion i SQL-språket som gör att vi kan köra en fråga upprepade gånger i en slinga: LATERAL join.
Här hittar vi den närmaste gatan till varje tunnelbanestation:
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;
Observera hur CROSS JOIN LATERAL fungerar som den inre delen av en slinga som drivs av tunnelbanetabellen. Varje post i tunnelbanetabellen matas in i den laterala underfrågan, en i taget, så att du får ett närmaste resultat för varje tunnelbanepost.
Förklaringen visar slingan på tunnelbanestationerna och den indexassisterade beställningen genom att lägga in slingan där vi vill ha den:
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)
