Проблема ближайшего соседа в Postgis 2.0 с использованием индекса GIST (функция <->)

25

Я пытаюсь использовать новую функцию Postgis 2.0 <-> (Geroidry Distance Centroid), чтобы вычислить для каждой строки моей таблицы (cosn1) расстояние до ближайшего многоугольника того же класса.

Я пытался использовать следующий код:

WITH index_query AS (
  SELECT g1.gid As ref_gid, ST_Distance(g1.the_geom,g2.the_geom) As ENN    
    FROM "cosn1" As g1, "cosn1" As g2   
    WHERE g1.gid <> g2.gid AND g1.class = g2.class
    ORDER BY g1.gid, g1.the_geom <-> g2.the_geom) 
SELECT DISTINCT ON (ref_gid) ref_gid, ENN 
    FROM index_query
ORDER BY ref_gid, ENN;

Но потом я понимаю предупреждение:

Примечание. Индекс включается только в том случае, если одна из геометрий является константой (не в подзапросе / cte). например, 'SRID = 3005; POINT (1011102 450541)' :: геометрия вместо a.geom

Это означает, что индекс не будет использоваться вообще, и запрос будет занимать почти то же время, что и перед использованием:

SELECT DISTINCT ON(g1.gid)  g1.gid As ref_gid, ST_Distance(g1.the_geom,g2.the_geom) As ENN    
    FROM "cosn1" As g1, "cosn1" As g2   
    WHERE g1.gid <> g2.gid AND g1.class = g2.class
    ORDER BY g1.gid, ST_Distance(g1.the_geom,g2.the_geom)

Может кто-нибудь указать мне обходной путь, который позволяет мне улучшить производительность моего запроса?

Большое спасибо.

nearest-neighbor postgis-2.0 Александр Нето
источник
Поскольку ответов пока нет, вы можете задать это в списке рассылки PostGIS.
ГИС-Джонатан
Я уже сделал, но и без каких-либо ответов.
Александр Нето
3
Вы можете использовать g1.gid> g2.gid в предложении where, что уменьшит количество вычислений расстояния, которые вам нужно сделать. К сожалению, до тех пор, пока оператор <-> не работает без констант, мы не увидим значительного улучшения скорости в запросах такого типа.
Джон Пауэлл
Джон, мне нужно сохранить все гиды, даже те, которые повторяются, так как мне нужно обновить EEN для каждого из многоугольников в моей таблице «cosn1». Но то, что ты сказал, дало мне идею. Я мог бы сделать, как вы говорите, используя g1.gid> g2.gis, чтобы уменьшить вычисления расстояний, но сохранив g1.gid и g2.gid в результате. После этого я мог объединить два его подзапроса (один с g1.gis в качестве gid, а другой с g2.gid). Спасибо
Александр Нето
Я обнаружил, что возможное решение для обхода постоянной проблемы - использовать <-> внутри функции SQL, используя the_geom в качестве параметра. Я сделал несколько тестов, а в некоторых случаях это намного быстрее (). Но в моем случае, поскольку расстояния находятся внутри одной и той же таблицы, многие вычисления расстояний повторяются во время процесса, что делает его медленнее, чем при использовании прямого запроса.
Александр Нето

Ответы:

2

Хум, проводящий некоторые тесты на моей машине, звучал так, как будто этот оператор <-> не работает должным образом. Я не уверен, что это ошибка, но он сообщил о нулевом расстоянии на неперекрывающихся геометриях. Интригует нет?

А как насчет справедливых традиционных оптимизаций SQL-запросов? Поскольку эти неожиданные результаты с оператором <->, я заменяю его на st_centroid. Получил намного лучшие результаты в скорости.

Надеюсь, что семантика с st_overlaps останется прежней. По крайней мере, это я понял из документации о <->

Из документов по Postigs <->

Для других типов геометрии возвращается расстояние между центроидами ограничивающего прямоугольника с плавающей точкой.

В моих тестовых данных с ~ 5,5 тыс. Полигонов скорость возросла с ~ 1000 до ~ 5 секунд без пространственной индексации.

В любом случае, зачем использовать DISTINCT ON для группировки? Я вижу, что некоторые люди используют его, но не существует группа, которая существует для устранения дубликатов?

Ваш запрос со стандартными оптимизациями SQL без введенной ошибки st_centroid

select g1.gid, min( st_distance( g1.the_geom, g2.the_geom ) ) AS enn
FROM 
  "cosn1" AS g1, "cosn1" AS g2
WHERE
  g1.gid <> g2.gid
  AND g1.class = g2.class
  AND g1.the_geom && g2.the_geom
GROUP BY
  g1.gid

Счастливого Рождества!

cavila
источник
Извините, но ваш ответ не решает проблему. На самом деле это намного быстрее, но результаты не точны, поскольку окончательный результат рассчитывается с использованием центроидов многоугольников, а не их реальной геометрии. Цель <-> - оптимизировать поиск кандидатов до ближайшего соседа, но в конце следует использовать реальные геометрические параметры для расчета расстояния до лучших кандидатов. Я также попытался использовать MIN \ GROUP BY вместо DISTINCT ON \ ORDER BY, и это, кажется, медленнее.
Александр Нето
Но в руководстве postgis для оператора <-> говорится, что он использует центроид для неточечных геометрий. Таким образом, мое решение даст вам аналогичные результаты. Это должно дать вам те же результаты, что и ваш главный запрос. Пожалуйста, проверьте правильность результатов с оператором <->. Он сообщил мне о геометрии нулевой длины в моих тестовых данных, чтобы результаты могли быть нарушены, и это решение предоставило более точные данные. Если вам удастся опубликовать несколько примеров записей с ошибками на каком-нибудь сайте pastie, мы можем обнаружить недостатки в решении.
cavila
Если вы проверите мой запрос, оператор <-> будет использоваться только для упорядочения кандидатов, окончательный результат рассчитывается с использованием фактической геометрии. В любом случае, как я уже говорил, повышение производительности <-> работает только с фиксированными точками. Это был мой оригинальный вопрос.
Александр Нето
Итак, вы согласны, что верхний запрос не эквивалентен нижнему запросу? Так как порядок будет меняться, потому что оператор <-> будет ORDER BY st_centroid, а st_distance даст вам другое значение? Другой порядок может привести к другому запросу в качестве первой строки, чтобы передать предложение DISTINCT ON? Действительный запрос будет нижним, который нуждается в улучшении скорости?
кавила
Да, первый запрос предназначен для повышения скорости в нижнем. И да, это может дать немного другой результат, так как g1.geom <-> g2.geom использует центроиды, и это означает, что первая строка может быть не ближе. Я думаю, что для того, чтобы это работало, мне нужно было бы установить ограничение на порядок, скажем, ограничение 10, а затем извлечь реальные значения расстояния. Можно даже использовать вместо этого <#>, который использует ограничительные рамки вместо центроидов.
Александр Нето