# Get N closest relations by distance

Suppose I have the products table:

``````create table products (
id integer primary key,
name varchar(200)
);
``````

And the dealers table:

``````create table dealers (
id integer primary key,
coords geography, -- longitude and latitude
name varchar(100)
);
create index dealer_coords_index on dealers using gist (coords);
``````

Many dealers have many products:

``````create table dealer_products (
dealer_id integer,
product_id integer,
constraint foreign key (dealer_id) references dealers (id),
constraint foreign key (product_id) references products (id)
);
create index on dealer_products (product_id);
create index on dealer_products (dealer_id);
create unique index on dealer_products (dealer_id, product_id);
``````

I can find 10 closest "offers" (product-dealer pairs) efficiently using the coordinates index:

``````explain analyze
select p.id, d.id
from products p
join dealer_products dp on dp.product_id = p.id
join dealers d on d.id = dp.dealer_id
order by coords <-> st_point(18.070449829102, 59.327235165987)
limit 10

Limit  (cost=1.00..28.47 rows=10 width=12) (actual time=1.949..2.018 rows=10 loops=1)
->  Nested Loop  (cost=1.00..5988021.55 rows=2179773 width=12) (actual time=1.947..2.014 rows=10 loops=1)
->  Nested Loop  (cost=0.71..5289066.19 rows=2179773 width=36) (actual time=1.927..1.931 rows=10 loops=1)
->  Index Scan using dealer_coords_index on dealers d (cost=0.28..8848.27 rows=20571 width=36) (actual time=0.291..1.250 rows=134 loops=1)
Order By: (coords <-> '01010000007B00000009123240F50188D7E2A94D40'::geometry)
->  Index Only Scan using dealer_products_dealer_id_product_id_unique on dealer_products dp  (cost=0.43..163.92 rows=9276 width=8) (actual time=0.004..0.004 rows=0 loops=134)
Index Cond: (dealer_id = d.id)
Heap Fetches: 0
->  Index Only Scan using products_pkey on products p  (cost=0.29..0.31 rows=1 width=4) (actual time=0.004..0.004 rows=1 loops=10)
Index Cond: (id = dp.product_id)
Heap Fetches: 0
Planning time: 1.100 ms
Execution time: 2.140 ms
``````

But if I need 10 unique "closest products", it's not efficient anymore:

``````explain analyze
select p.id
from products p
join dealer_products dp on dp.product_id = p.id
join dealers d on d.id = dp.dealer_id
group by p.id
order by min(d.coords <-> st_point(18.070449829102, 59.327235165987))
limit 10

Limit  (cost=473651.54..473651.57 rows=10 width=12) (actual time=4712.858..4712.859 rows=10 loops=1)
->  Sort  (cost=473651.54..473807.51 rows=62388 width=12) (actual time=4712.857..4712.857 rows=10 loops=1)
Sort Key: (min((d.coords <-> '01010000007B00000009123240F50188D7E2A94D40'::geometry)))
Sort Method: top-N heapsort  Memory: 25kB
->  GroupAggregate  (cost=414665.48..472303.36 rows=62388 width=12) (actual time=2125.861..4702.631 rows=53183 loops=1)
Group Key: p.id
->  Merge Join  (cost=414665.48..455331.18 rows=2179773 width=36) (actual time=2125.728..3271.556 rows=2179773 loops=1)
Merge Cond: (p.id = ps.product_id)
->  Index Only Scan using products_pkey on products p  (cost=0.29..2364.11 rows=62388 width=4) (actual time=0.012..11.103 rows=62388 loops=1)
Heap Fetches: 0
->  Materialize  (cost=414665.19..425564.06 rows=2179773 width=36) (actual time=2125.709..2883.522 rows=2179773 loops=1)
->  Sort  (cost=414665.19..420114.63 rows=2179773 width=36) (actual time=2125.705..2694.712 rows=2179773 loops=1)
Sort Key: dp.product_id
Sort Method: external merge  Disk: 91576kB
->  Hash Join  (cost=2418.85..65971.46 rows=2179773 width=36) (actual time=24.993..748.693 rows=2179773 loops=1)
Hash Cond: (dp.dealer_id = d.id)
->  Seq Scan on dealer_products dp  (cost=0.00..33580.73 rows=2179773 width=8) (actual time=0.020..191.193 rows=2179773 loops=1)
->  Hash  (cost=2161.71..2161.71 rows=20571 width=36) (actual time=24.830..24.830 rows=20571 loops=1)
Buckets: 32768  Batches: 1  Memory Usage: 1622kB
->  Seq Scan on dealers d  (cost=0.00..2161.71 rows=20571 width=36) (actual time=0.015..17.278 rows=20571 loops=1)
Planning time: 1.099 ms
Execution time: 4722.017 ms
``````

How to get 10 closest unique products efficiently?

I don't think there is any way to do this that is both tidy and efficient. An efficient way would be to select a limited number of points, then aggregate those points and select from the aggregate with another limit. You just have to hope that the inner limit selects enough points they find at least enough aggregated rows to satisfy the outer limit. (Or, if there is a shortfall, you could raise the inner limit and try again)

Also, you don't need to join to `product` at all, because the only field you fetch from it is product.id, but that can just be fetched from dp.product_id instead.

``````select id, min(dist)
from
(select
product_id as id,
d.coords <-> st_point(18.070449829102, 59.327235165987) as dist
from
dealer_products dp
join dealers d on d.id = dp.dealer_id
order by 2 limit 50
) pp
group by id
order by min(dist)
limit 10
``````

The ratio of inner limit to outer limit that suffices would depend on how much product_ids get repeated

• What if the number of product_id repetitions ranges wildly from 1 to 100k depending on the reference coordinates? – Gas Welder Sep 30 '17 at 15:27
• Then you have a famously tough problem on your hands. Is there a small handful of products that have the potential to be extremely popular, or can any product become extremely popular in certain areas? You can do some kind of partitioning of the data, or have the query coded multiple ways and have software use heuristics to choose which one to run. – jjanes Sep 30 '17 at 17:52