PostgreSQL - Рассчитать минимальное расстояние между двумя точками - PullRequest
Новая
       23

PostgreSQL - Рассчитать минимальное расстояние между двумя точками

0 голосов
/ 02 апреля 2020

У меня довольно существенный точечный слой (чуть более 1 миллиона), и я хотел бы выбрать кратчайшее расстояние, отделяющее каждую точку от одного и того же слоя до другого (ближайшего соседа). После некоторых исследований inte rnet я обратился к условию Cross Join Lateral.

Однако запрос никогда не заканчивается (более 5 часов без завершения). Я сравнил с QGis Distance Matrix, , и там время вычислений кажется намного быстрее (около 10% каждые 5 минут). Я говорю себе, что причина может быть ie в плохо сформулированном запросе.

Вот код, который я использовал: 

with couche_points as (select * from public.centroides_batis_all)
select p.id, t.id_2, t.dist
from couche_points p cross join lateral(
select r.id as id_2, p.geom <-> r.geom as dist
from couche_points r
where p.id <> r.id
order by p.geom <-> r.geom
limit 1) as t

Однако, все выглядит хорошо для меня. Есть ли разница в производительности между PostGis и QGis?

Спасибо.

Ответы [ 3 ]

0 голосов
/ 03 апреля 2020

Как я вижу, вы строите матрицу, подобную этой, в вашем запросе: 

   p1  p2  p3  p4  ... pn
p1 --- d21 d31 d41 ... dn1
p2 d12 --- d32 d42 ... dn2
p3 d13 d23 --- d43 ... dn3
p4 d14 d24 d34 --- ... dn4
..........................
pn d1n d2n d3n d4n ... ---

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

   p1  p2  p3  p4  ... pn
p1 --- d21 d31 d41 ... dn1
p2 --- --- d32 d42 ... dn2
p3 --- --- --- d43 ... dn3
p4 --- --- --- --- ... dn4
..........................
pn --- --- --- --- ... ---

select t1.id as id, t2.id as id_2, t2.dist
from
  centroides_batis_all as t1 cross join lateral (
    select t2.id, t1.geom <-> t2.geom as dist
    from centroides_batis_all as t2 where t1.id < t2.id -- the main difference here
    order by dist limit 1) as t2;

Этот запрос вернет такие пары, как p1-p2, но не p2-p1 (с одинаковым расстоянием, конечно)

Чтобы исправить это, вы можете просто продублировать строки из предыдущего запроса с помощью поменялись местами: 

with cte as (
  select t1.id as id, t2.id as id_2, t2.dist
  from
    centroides_batis_all as t1 cross join lateral (
      select t2.id, t1.geom <-> t2.geom as dist
      from centroides_batis_all as t2 where t1.id < t2.id
      order by dist limit 1) as t2)
select
  case t.n when 1 then cte.id else cte.id_2 end as id,
  case t.n when 1 then cte.id_2 else cte.id end as id_2,
  cte.dist
from cte, (values(1), (2)) as t(n);
0 голосов
/ 03 апреля 2020

Возможно, у вас есть возможность разделить ваши точки на четыре области.

1 Матрица расстояний с 1.000.000 точек требует 1.000.000 x 1.000.000 = 1.000.000.000.000 вычислений.

4 Расстояние MAtrix с 250.000 точек требует 250.000 x 250.000 = 250.000.000.0000 вычислений.

Это всего лишь 1/4 вычислений. Конечно, вы должны показать, как справиться, где разделенные области собираются вместе, но, похоже, это происходит намного быстрее.

0 голосов
/ 03 апреля 2020

Какой смысл в манекене CTE? Все, что он делает - это игнорирует использование любого индекса в реальной таблице (что, безусловно, является достаточным объяснением медлительности) 

select p.id, t.id_2, t.dist
from centroides_batis_all p cross join lateral(
select r.id as id_2, p.geom <-> r.geom as dist
from centroides_batis_all r
where p.id <> r.id
order by p.geom <-> r.geom
limit 1) as t;
...