最近点上的 MySQL 空间连接

Question

我搜索了一下，发现很多人想按照到某个点的距离来排序点的表格，但我想知道如何高效地通过两点之间的最小距离将两个表格连接起来。在我的情况下，考虑表格nodes和centroids。

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

我大约有300k个节点和15k个质心，我想找到每个节点最接近的质心，以便为每个节点分配一个温度。目前为止，我已在两个表上的pt上创建了空间索引，并尝试运行以下查询：

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;

显然，这个查询并不能解决我的问题；它不会检索温度，假设最近的质心在4810内，只评估了10个节点。然而，即使有这些简化，这个查询仍然非常不优化，而且在我输入这段话时仍在运行。当我让MySQL给出有关查询的详细信息时，它说没有使用索引，并且没有将任何空间索引列为可能的键。

我该如何构建一个能够高效地利用空间索引联合返回我所需数据的查询呢？

- Benjamin Brownlee

Answer 1

我认为一个好的方法是将数据分成单元格（按数字而不是数据库分区）。我不知道空间索引在这里是否适用，但高层逻辑是将每个节点和质心点装入正方形区域中，并在同一正方形中查找所有节点-质心匹配，然后确保在8相邻正方形中没有更接近的匹配（例如使用原始正方形中的相同节点）。然后可以使用最接近的匹配来计算并保存温度。所有后续查询都应忽略已设置温度的节点。

仍然会有质心不在同一或8相邻正方形内的节点，然后您需要扩展搜索，可能使用宽度和高度加倍的正方形。我可以看到这适用于只对点的x和y坐标进行简单索引的情况。我不知道空间索引如何进一步改进这一点。

- karmakaze

---

你提到单元格时，我想到了一个主意。我知道MySQL空间索引可以快速找到在某个多边形内或周围的项目。是否可能将我的质心转换为多边形的镶嵌，并仅搜索每个多边形包含的节点？这样做比尝试计算距离要快得多吗？ - Benjamin Brownlee

听起来真的很酷，你知道多边形中的所有节点都会最接近其中一个顶点重心。所以现在问题变成了制作镶嵌图案。三角形怎么样？记住“外部”（网格的负多边形）对于那些不在内部的节点来说也是一个多边形。 - karmakaze

这些怎么样？我可以使用Python提取所有的质心并计算它们的Voronoi多边形，然后将它们推回去。在这些多边形上建立一个空间索引应该会很快。 https://zh.wikipedia.org/wiki/%E7%BB%B4%E7%BD%97%E8%AF%BA%E5%9B%BE - Benjamin Brownlee

是的，使用欧几里得距离是完美的。有趣的是，沃罗诺伊图的对偶图是德劳内三角剖分（最初的三角剖分思想与重心顶点）。 - karmakaze

是的，使用Voronoi多边形计算和将温度与这些区域中的节点配对的速度非常快。我可以在几秒钟内完成我想要的整个网络连接。感谢您的帮助，我会接受您的答案，并在我的问题的答案中解释我所做的事情。 - Benjamin Brownlee

Answer 2

有许多方法可以解决这个 least-n-per-group 问题。

其中一种方法使用了自身左连接反模式（这允许出现并列的情况）：

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

使用not exists条件可以表达相同的逻辑。

另一个选项是使用相关子查询进行过滤（这不允许出现并列）：

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
    )

最后：如果你只想要最近质心的温度，那么一个简单的子查询应该是一个不错的选择：

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

- GMB

---

感谢提供可运行的查询。它们在低限制下肯定是可运行的，但MySQL似乎仍然没有使用任何索引。100个节点大约需要2.14秒，1000个节点需要21.33秒，10000个节点需要212.94秒。因此，完整的网络（一旦我更新它，将达到500k个节点）应该需要大约3小时，这绝对是可以管理的，但如果能进一步优化就更好了。有什么想法可以实际利用mysql空间索引，或者这不是它们设计的目的吗？ - Benjamin Brownlee