CODEWITHSUNDEEP
mysqlsqlspatial
Benjamin Brownlee
Benjamin Brownlee

Reputation: 43

MySQL Spatial Join on Closest Point

I've looked around a bit and found quite a few people seeking to order a table of points by distance to a set point, but I'm curious how one would go about efficiently joining two tables on the minimum distance between two points. In my case, consider the table nodes and centroids.

CREATE TABLE nodes (
    node_id VARCHAR(255),
    pt POINT
);
CREATE TABLE centroids (
    centroid_id MEDIUMINT UNSIGNED,
    temperature FLOAT,
    pt POINT
);

I have approximately 300k nodes and 15k centroids, and I want to get the closest centroid to each node so I can assign each node a temperature. So far I have created spatial indexes on pt on both tables and tried running the following query:

SELECT
    nodes.node_id,
    MIN(ST_DISTANCE(nodes.pt, centroids.pt))
FROM nodes
INNER JOIN centroids
ON ST_DISTANCE(nodes.pt, centroids.pt) <= 4810
GROUP BY
    nodes.node_id
LIMIT 10;

Clearly, this query is not going to solve my problem; it does not retrieve temperature, assumes that the closest centroid is within 4810, and only evaluates 10 nodes. However, even with these simplifications, this query is very poorly optimized, and is still running as I type this. When I have MySQL give details about the query, it says no indexes are being used and none of the spatial indexes are listed as possible keys.

How could I build a query that can actually return the data I want joined efficiently utilizing spatial indexes?

Upvotes: 3

Views: 1460

Answers (2)

GMB
GMB

Reputation: 222432

There are many ways to solve this least-n-per-group problem.

One method uses a self-left-join antipattern (this allows ties):

select 
    n.node_id,
    c.centroid_id,
    st_distance(n.pt, c.pt) dist,
    c.temperature
from nodes n
cross join centroids c
left join centroids c1 
    on c1.centroid_id <> c.centroid_id
    and st_distance(n.pt, c1.pt) < st_distance(n.pt, c.pt)
where c1.centroid_id is null

The same logic can be expressed with a not exists condition.

Another option is to use a correlated subquery for filtering (this does not allow ties):

select 
    n.node_id,
    n.node_id,
    c.centroid_id,
    st_distance(n.pt, c.pt) dist,
    c.temperature
from nodes n
inner join centroids c
    on c.centroid_id = (
        select c1.centroid_id
        from centroids c1
        order by st_distance(n.pt, c1.pt) 
        limit 1
    )

Finally: if all you want is the temperature of the closest centroid, then a simple subquery should be a good choice:

select 
    n.node_id,
    (
        select c1.temperature
        from centroids c1
        order by st_distance(n.pt, c1.pt) 
        limit 1
    ) temperature 
from nodes n

Upvotes: 1

karmakaze
karmakaze

Reputation: 36134

I think a good approach would be partitioning (numerically not db partitioning) the data into cells. I don't know how well spatial indexes applies here, but the high-level logic is to say bin each node and centroid point into square regions and find matches between all the node-centroid in the same square, then make sure that there isn't a closer match in an 8-adjacent square (e.g. using the same nodes in original square). The closest matches can then be used to compute and save the temperature. All subsequent queries should ignore nodes with the temperature set.

There will still be nodes with centroids that aren't within the same or 8-adjacent squares, you would then expand the search, perhaps use squares with double the width and height. I can see this working with plain indexes on just the x and y coordinate of the points. I don't know how spatial indexes can further improve this.

Upvotes: 2

Related Questions