最近点的 MySQL 空间连接

Question

我环顾四周，发现很多人都在寻求根据到设定点的距离来排序点表，但我很好奇如何有效地连接两个表之间的最小距离点。在我的例子中，考虑表 nodes 和 centroids。

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

我有大约 30 万个节点和 15 千个质心，我想获得离每个节点最近的质心，这样我就可以为每个节点分配一个温度。到目前为止，我已经在两个表的 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 提供有关查询的详细信息时，它说没有使用索引，也没有将任何空间索引列为可能的键。

我如何构建一个查询，以利用空间索引有效地返回我想要有效连接的数据？

Answer 1

我认为一个好的方法是将数据分区(数字上不是数据库分区)到单元格中。我不知道空间索引在这里应用得有多好，但高级逻辑是说将每个节点和质心点放入正方形区域并找到同一正方形中所有节点质心之间的匹配项，然后确保有' 在 8 个相邻的正方形中进行更接近的匹配(例如，在原始正方形中使用相同的节点)。然后可以使用最接近的匹配来计算和保存温度。所有后续查询都应​​忽略具有温度设置的节点。

仍然会有质心不在相同或 8 个相邻正方形内的节点，然后您可以扩大搜索范围，也许使用宽度和高度加倍的正方形。我可以看到这只在点的 x 和 y 坐标上使用普通索引。我不知道空间索引如何进一步改善这一点。