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

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

2 голосов
/ 26 апреля 2019

У меня есть огромная таблица (около 40 миллионов строк), называемая near_spot, представляющая строки (в формате строк) и ближайшую к ним точку (около 1500 различных точек хранятся в другой таблице). Таблица next_spot выглядит следующим образом: 

 data_id || spot_id || spot_name || link_geom

Где data_id первичный ключ, spot_id - это внешний ключ первичного ключа таблицы спотов, spot_name - имя спота (я знаю, избыточность не очень хорошая, но я не могу изменять базу данных) и link_geom - это координаты линии.

База данных находится в PostgreSQL 10.6, PostGIS 2.5, для столбца link_geom имеется индекс гистограммы, а VACUUM ANALYZE уже выполнен в таблице ближайших_спотов.

Моя цель - как можно быстрее найти ближайшего соседа (в этой таблице) к точке в записи данных.

Я уже знаю, как найти ближайшего соседа, моя проблема в том, сколько времени нужно, чтобы найти его. Я довольно новичок в PostgreSQL и PostGIS, и я читал их документацию, просматривая множество тем об оптимизации KNN, я искал наиболее эффективный ответ, и все же я не могу получить результат менее чем за 5 минут. (и иногда до 30 минут), даже при поиске только одной строки. Различные запросы, которые я пробовал, следующие: 

SELECT *
FROM( SELECT A.position, B.spot_id
      FROM data A, nearest_spot B
      WHERE A.id = 1
      AND ST_DWithin(A.position,B.link_geom,20)
      ORDER BY A.position <-> B.link_geom
      LIMIT 10;)
ORDER BY ST_Distance(A.position,B.link_geom)
LIMIT 1;

SELECT *
FROM( SELECT A.position, B.spot_id
      FROM data A, nearest_spot B
      WHERE A.id = 1
      AND ST_Buffer(A.position,20) && B.link_geom
      ORDER BY A.position <-> B.link_geom
      LIMIT 10;)
ORDER BY ST_Distance(A.position,B.link_geom)
LIMIT 1;

SELECT *
FROM( SELECT A.position, B.spot_id
      FROM data A, nearest_spot B
      WHERE A.id = 1
      AND ST_Intersects(ST_Buffer(A.position,20), B.link_geom)
      ORDER BY A.position <-> B.link_geom
      LIMIT 10;)
ORDER BY ST_Distance(A.position,B.link_geom)
LIMIT 1;

Причина, по которой я ЗАКАЗЫВАЮ сначала с <->, затем с ST_Distance, заключается в том, что согласно этой документации от PostGIS, <-> быстрее, но менее точно (для ограничивающих рамок), тогда как ST_Distance более точна но медленнее.

Я также использовал документацию о пространственном индексировании и one об операторе <->, оба из PostGIS.

РЕДАКТИРОВАТЬ: Я понял, что все мои координаты хранятся в виде геометрии (SRID 4326), поэтому вызов ST_DWithin, имея хороший синтаксис, возвращал все строки не в пределах 20 метров, как предполагалось, но все строки в пределах 20 градусов (от земли), так что на самом деле мой ST_DWithin не делал результирующий набор меньшим, и это может быть одной из главных причин, почему он занимал так много времени, и то же самое относится и к ST_Buffer. Я попытаюсь привести все координаты как географию (с ::geography), прежде чем использовать их с метрами, и, надеюсь, я увижу улучшение

Ответы [ 2 ]

0 голосов
/ 03 мая 2019

Похоже, в таблице было огромное количество дубликатов (каждый ряд повторялся около 1800 раз), и человек, который дал его мне, вообще не знал об этом.У меня больше нет проблем со временем запроса после удаления дубликатов

0 голосов
/ 27 апреля 2019

Нужна ли база данных?Я думаю, что самый быстрый способ - это загрузить 1500 точек в пространственный индекс, такой как KD-Tree, Quadtree или R-Tree.Затем выполните итерацию по 40M точкам и найдите ближайшего соседа в индексе.

Без особых усилий вы сможете выполнять от 100 000 до 500 000 NN-запросов в секунду, поэтому 40M NN-поисков должны занимать примерно от 2 до5 минут.

...