Запрос K-ближайшего соседа в PostGIS

Несколько мыслей о вашей проблеме:

st_distance, а также st_area не могут использовать индексы. Это потому, что обе функции нельзя свести к вопросам типа «Находится ли а внутри b?» или «Перекрываются ли a и b?». Более конкретно: GIST-индексы могут работать только с ограничивающими рамками двух объектов.

Дополнительную информацию об этом вы можете найти в руководстве по postgis, в котором приводится пример с st_distance и как можно улучшить запрос, чтобы он работал лучше.

Однако это не решает вашу проблему k-ближайшего-соседа. Для этого прямо сейчас я не знаю, как улучшить производительность запроса. Единственный шанс, который я вижу, - это предположить, что k ближайших соседей всегда находятся на расстоянии менее x метров. Тогда вы можете использовать тот же подход, что и в руководстве postgis.

Ваш второй запрос можно немного ускорить. В настоящее время вы вычисляете площадь для каждого объекта в таблице 1 так часто, как в таблице есть строки - стратегия состоит в том, чтобы сначала объединить данные, а затем выбрать их на основе этой функции. Вы можете значительно сократить количество вычислений площади, предварительно вычислив площадь:

WITH polygonareas AS (
    SELECT gid, the_geom, st_area(the_geom) AS area
    FROM polygons
)
SELECT g1.gid, g2.gid
FROM polygonareas as g1 , polygonareas as g2 
WHERE g1.area > g2.area;

Третий запрос можно значительно оптимизировать с помощью ограничивающих рамок: когда ограничивающие прямоугольники двух объектов не перекрываются, объекты не могут пересекаться. Это позволяет использовать заданный индекс и, таким образом, значительно повысить производительность.

Начиная с конца сентября 2011 г., PostGIS поддерживает индексированные запросы ближайшего соседа с помощью специального оператора (ов), используемого в предложении ORDER BY:

SELECT name, gid
FROM geonames
ORDER BY geom <-> st_setsrid(st_makepoint(-90,40),4326)
LIMIT 10;

... вернет 10 объектов, geom которых является ближайшим к -90,40 масштабируемым способом. Еще несколько деталей (варианты и предостережения) находятся в этом объявлении post и использование ‹-> и ‹#> операторы теперь также документированы в официальной версии PostGIS 2.0. ссылка. (Основное различие между ними заключается в том, что <-> сравнивает центроиды формы, а <#> сравнивает их границы - нет разницы для точек, другие формы выбирают то, что подходит для ваших запросов.)

Вы можете сделать это с помощью индекса KNN и бокового соединения.

SELECT v.gid, v2.gid,st_distance(v.the_geom, v2.the_geom)
  FROM geonames v, 
       lateral(select * 
                 from geonames v2
                where v2.id<>v.id
                ORDER BY v.the_geom <-> v2.the_geom LIMIT 10) v2
where v.gid in (...) - or other filtering condition

Что вам может понадобиться, так это индекс KNN, который, надеюсь, скоро будет доступен в PostGIS 2.x и PostgreSQL 9.1: см. http://blog.opengeo.org/tag/knn/

Предполагая, что у вас есть многоугольники p point и g, ваш исходный запрос:

SELECT g1.gid, g2.gid FROM points as g1, polygons g2   
WHERE g1.gid <> g2.gid
ORDER BY g1.gid, ST_Distance(g1.the_geom,g2.the_geom)
LIMIT k;

Возвращает k ближайших соседей в наборе p x g. Запрос может использовать индексы, но он все равно должен упорядочить весь набор p x g, чтобы найти k строк с наименьшим расстоянием. Вместо этого вам нужно следующее:

SELECT g1.gid, 
      (SELECT g2.gid FROM polygons g2   
       --prevents you from finding every nearest neighbour twice
       WHERE g1.gid < g2.gid 
       --ORDER BY gid is erroneous if you want to limit by the distance
       ORDER BY ST_Distance(g1.the_geom,g2.the_geom)
       LIMIT k)
FROM points as g1;