SQL交叉连接去重优化：求平面最短距离坐标集的更优解法

你的问题核心是cross join生成了重复的镜像点对，事后去重属于“补救式”处理，更高效优雅的思路是在关联阶段就避免生成冗余数据，具体可以通过以下两种经典方案实现：

方案一：利用唯一标识过滤自连接（推荐） #

如果坐标表有天然的唯一标识（比如id列），可以在自连接时添加t1.id < t2.id的条件，这样每个点对只会生成一次（比如只会出现(A,B)，不会出现(B,A)），同时自动排除点自身配对的无效情况。

完整代码示例 #

假设坐标表名为points，结构为id, x, y：

WITH point_pairs AS (
    -- 生成无冗余的有效点对，并计算距离
    SELECT 
        t1.x AS x1, t1.y AS y1,
        t2.x AS x2, t2.y AS y2,
        SQRT(POWER(t1.x - t2.x, 2) + POWER(t1.y - t2.y, 2)) AS dist
    FROM points t1
    JOIN points t2 ON t1.id < t2.id -- 核心：避免镜像对和自身配对
),
min_dist_info AS (
    -- 计算全局最短距离
    SELECT MIN(dist) AS global_min FROM point_pairs
)
-- 筛选出所有距离等于最短距离的点对
SELECT x1, y1, x2, y2, dist
FROM point_pairs, min_dist_info
WHERE point_pairs.dist = min_dist_info.global_min;

方案二：无天然标识时生成临时唯一ID #

如果坐标表没有id这类唯一标识，可以用ROW_NUMBER()生成临时序号，再套用方案一的逻辑：

WITH numbered_points AS (
    -- 给每个坐标生成临时唯一ID
    SELECT x, y, ROW_NUMBER() OVER () AS id
    FROM points
),
point_pairs AS (
    SELECT 
        t1.x AS x1, t1.y AS y1,
        t2.x AS x2, t2.y AS y2,
        SQRT(POWER(t1.x - t2.x, 2) + POWER(t1.y - t2.y, 2)) AS dist
    FROM numbered_points t1
    JOIN numbered_points t2 ON t1.id < t2.id
),
min_dist_info AS (
    SELECT MIN(dist) AS global_min FROM point_pairs
)
SELECT x1, y1, x2, y2, dist
FROM point_pairs, min_dist_info
WHERE point_pairs.dist = min_dist_info.global_min;

额外性能优化：用平方距离替代实际距离 #

因为平方根函数是单调递增的，最小平方距离对应的就是最短实际距离，可以用平方距离进行比较，避免浮点运算带来的性能损耗和精度问题：

WITH numbered_points AS (
    SELECT x, y, ROW_NUMBER() OVER () AS id
    FROM points
),
point_pairs AS (
    SELECT 
        t1.x AS x1, t1.y AS y1,
        t2.x AS x2, t2.y AS y2,
        POWER(t1.x - t2.x, 2) + POWER(t1.y - t2.y, 2) AS squared_dist
    FROM numbered_points t1
    JOIN numbered_points t2 ON t1.id < t2.id
),
min_sq_dist AS (
    SELECT MIN(squared_dist) AS min_sq FROM point_pairs
)
SELECT 
    x1, y1, x2, y2,
    SQRT(squared_dist) AS dist -- 最后按需计算实际距离
FROM point_pairs, min_sq_dist
WHERE point_pairs.squared_dist = min_sq_dist.min_sq;

方案优势对比 #

• 你的原方法：先生成所有镜像对，再通过least/greatest+distinct去重，属于事后清理，数据量越大性能损耗越明显
• 上述优化方案：从关联阶段就避免冗余数据生成，中间结果集大小直接减半，逻辑更清晰，性能更优

内容的提问来源于stack exchange，提问作者user1844086