在不同表中查找对象之间的最小距离

Question

我可以帮您翻译成中文。以下是需要翻译的内容：

我有两个表格，它们都包含具有XY坐标的对象：

表A：

ID_A | X    | Y
-----|------|------
100  | 32.2 | 25.6
101  | 36.2 | 22.1
102  | 31.7 | 39.2
103  | 42.7 | 15.6
104  | 24.5 | 29.9

表B：

ID_B | X    | Y
-----|------|------
200  | 55.3 | 25.1
201  | 21.5 | 54.2
202  | 67.3 | 66.6
203  | 23.5 | 55.4
204  | 41.1 | 24.5
205  | 42.4 | 62.6
206  | 26.8 | 23.6
207  | 63.2 | 25.6
208  | 35.6 | 11.1
209  | 74.2 | 22.2
210  | 12.2 | 33.3
211  | 15.7 | 44.4

对于表 A 中的每个对象，我想要找到表 B 中最近的对象（对象之间的距离最小）。 因此结果应该像这样（这里的距离是随机的……）：

ID_A | ID_B | DISTANCE
-----|------|---------
100  | 203  | 12.5
101  | 203  | 11.1
102  | 211  | 16.5
103  | 205  | 14.2
104  | 209  | 17.7

物体之间的距离：

SQRT( (A.X-B.X)*(A.X-B.X) + (A.Y-B.Y)*(A.Y-B.Y) )

所以我做了这个查询：

SELECT DISTINCT A.ID_A
     , FIRST_VALUE (B.ID_B) OVER (PARTITION BY A.ID_A ORDER BY SQRT((A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y)) ASC) AS ID_B
     , FIRST_VALUE (SQRT((A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y))) OVER (PARTITION BY A.ID_A ORDER BY SQRT((A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y)) ASC) AS DISTANCE
FROM TableA A, TableB B

这个功能是正常工作的，但问题在于两个表格都有大量数据行（超过500K），因此该查询速度较慢（可能非常低效）。

如何优化此查询？（我正在使用Oracle SQL） 提前感谢。

- user2051102

---

找到最短距离的平方就等同于找到最短距离，因此您可以在“partition”和“order by”子句中安全地省略“SQRT”。这应该会稍微加快计算速度。 - Sergey Kalinichenko

谢谢。它确实加快了事情的进展 - 一点点 ;) - user2051102

Answer 1

如dasblinkenlight所述，由于平方距离最短的行也是距离最短的行，因此您不需要为每个行组合计算平方根。

我认为您最好尝试减少执行的总计算次数，因此可能会加快速度：

SELECT ID_A,ID_B,SQRT(DISTANCE_SQUARED) DISTANCE FROM (
  SELECT ID_A,ID_B,DISTANCE_SQUARED,MIN(DISTANCE_SQUARED) OVER (PARTITION BY ID_A) MIN_DS FROM (
    SELECT A.ID_A,B.ID_B,
    POWER(A.X-B.X,2)+POWER(A.Y-B.Y,2) DISTANCE_SQUARED
    FROM
    TABLE_A A,
    TABLE_B B
  )
)
WHERE DISTANCE_SQUARED=MIN_DS

这可能会返回多个匹配项（如果TABLE_B中有多行与TABLE_A中的某一行的距离相同）……不确定是否可接受。

如果这些表很少被写入，而您需要频繁运行此查询，则最好预先计算此信息并将其存储在另一个表TABLE_C中。当/如果向任一表添加或编辑一行时，您可以将该行与另一个表中的500k行进行比较，并在必要时更新TABLE_C，而无需每次运行查询时检查500k * 500k行。

- Mike

---

这并没有改变速度，但是这段代码看起来更加优美。在单独的表中存储结果也是一个好主意。 - user2051102

Answer 2

嗯，我认为我更喜欢在CTE中“预计算”距离。我知道优化器应该能够缓存某些值，但我不确定它可能做得有多好。此外，基于“距离”进行维护也更容易。不幸的是，您没有“最大距离”来最初排除某些值，这意味着这将始终略慢。

WITH Distances (id_a, id_b, distance_squared, index) as 
                   (SELECT a.id_a, b.id_b, 
                           POWER((a.x - b.x), 2) + POWER((a.y - b.y), 2) d,
                           ROW_NUMBER() OVER(PARTITION BY a.id_a, ORDER BY d ASC)
                    FROM TableA a
                    CROSS JOIN TableB b)
SELECT id_a, id_b,
       SQRT(distance_squared)
FROM Distances
WHERE index = 1

使用 FIRST_VALUE() 导致“最小”的值重复 - 如果删除它们，则不需要使用 DISTINCT，这可能会有所帮助。

---

编辑：

如果您有“最大距离”，请尝试以下操作：

WITH Distances (id_a, id_b, distance_squared, index) as 
                   (SELECT a.id_a, b.id_b, 
                           POWER((a.x - b.x), 2) + POWER((a.y - b.y), 2) d,
                           ROW_NUMBER() OVER(PARTITION BY a.id_a, ORDER BY d ASC)
                    FROM TableA a
                    JOIN TableB b
                      ON (b.x > a.x - @distance AND b.x < a.x + @distance)
                         AND (b.y > a.y - @distance AND b.y < a.y + @distance)
                    WHERE d < POWER(@distance, 2))
SELECT id_a, id_b,
       SQRT(distance_squared) as distance
FROM Distances
WHERE index = 1

这可能可以利用坐标值的索引，尽管我不确定（可能是在TableB一侧，也可能是在TableA一侧...如果需要的话，请交换比较）。请注意以下两点：

1. 所有这些都是基于在平面笛卡尔坐标系上进行操作。如果这是针对地球表面上的点，则方程会更加复杂；但是，如果您查看一下，这里有许多问题/答案来涵盖它们。
2. 仍然必须获取/使用平方根距离，否则您将在网格方格的角落中隐藏一些内容，实际上这些内容“超出”了距离（约为40%）。

- Clockwork-Muse

---

这并没有在速度上有太大的改变，但代码更加优美。假设我有一个最大距离，我应该在CROSS JOIN之后使用WHERE子句吗？此外，实际数字类似于545632.04536，我使用了TRUNC将它们裁剪到545632，但速度的变化很小。 - user2051102

Answer 3

如果您的表没有相应/匹配的行，请根本不要使用JOIN。使用两个单独的查询。否则，您的输出将包含500K * 500K行。在我的示例中，我假设您的表是相关的，我所做的一切只是为了帮助。

请参见下面的Outer Join。

除非您在将最终查询示例复制到帖子中时出错，否则您的查询运行时间很长，因为您忘记连接表a和b而使结果加倍。您得到的是笛卡尔积：

SELECT DISTINCT A.ID_A
 , FIRST_VALUE (B.ID_B) OVER (PARTITION BY A.ID_A ORDER BY SQRT((A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y)) ASC) AS ID_B
 , FIRST_VALUE (SQRT((A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y))) OVER (PARTITION BY A.ID_A ORDER BY SQRT((A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y)) ASC) AS DISTANCE
 FROM TableA A, TableB B
WHERE a.id = b.id -- You missed this
/

此外，您正在使用DISTINCT。尝试添加JOIN并删除DISTINCT，看看差异。选择所有行并注意执行/经过时间。避免基于emp表的distinct的一般示例：

-- Distinct - runs longer --
SELECT DISTINCT d.deptno, dname FROM scott.dept D, scott.emp E WHERE D.deptno = E.deptno
/  
-- Same as Distinct - faster --
SELECT deptno, dname FROM scott.dept D 
 WHERE EXISTS (SELECT 'X' FROM scott.emp E WHERE E.deptno = D.deptno)
/

外连接。下面的查询将返回 A 表（dept）和 B 表中的所有行，即使 B 表中没有与 A 表对应的行也是如此。运行查询并查看 deptno = 40。它在 emp 表中没有行，并显示 empname 的空值。在我的示例中，您的表 A（scott.dept）似乎比 B（emp）少一些行。因此，我认为外连接是答案：

SELECT d.deptno, e.ename
  FROM scott.dept d LEFT OUTER JOIN scott.emp e
    ON d.deptno = e.deptno
ORDER BY d.deptno
/

- Art

---

嗯，鉴于 TableA.id != TableB.id，连接条件根本没有帮助。实际上，他需要笛卡尔积，因为他正在获取不同点之间的最短距离 - 他没有其他可以将它们连接起来的东西！现在，DISTINCT 可能只需删除，因为给定的元组应该是唯一的 _regardless_，这应该有所帮助。但我怀疑这不是全部故事... - Clockwork-Muse

@Clockwork- 这完全取决于用户。只有用户知道完整的故事。外连接可能是答案... - Art

没错，笛卡尔积正是我所需要的。如果我不使用DISTINCT，就会得到多个相同的条目。你能详细阐述一下关于外连接的想法吗？ - user2051102

@user2051102 - 抱歉，我误解了FIRST_VALUE()实际上的作用，在回顾时很明显。 - Clockwork-Muse

@Clockwork - 看，我们不要在这里变得荒谬。如果表中没有匹配的行，则用户犯了错误。应该只有两个单独的查询。否则，500K的输出将乘以另外的500K。这是SQL基础知识。 - Art