3

我有两个表，都包含具有 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）提前致谢。

4

3 回答 3

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 中的多于 1 行与 TABLE_A 中的一行具有相同的距离）......不确定这是否可以接受。

如果不经常写入表并且您需要经常运行此查询，则最好预先计算此信息并将其存储在另一个表中，例如 TABLE_C。当/如果将一行添加或编辑到任一表时，您可以根据另一个表中的 500k 检查该行并在必要时更新 TABLE_C，而不是每次运行查询时都需要检查 500k * 500k 行。

于 2013-02-07T18:56:09.530 回答
1

嗯，我想我更喜欢在 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%）。
于 2013-02-07T19:06:28.920 回答
0

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

请参阅下面的外部连接。

除非您在将最终查询示例复制到您的帖子中时出错，否则您的查询会运行很长时间，因为您将结果加倍而忘记连接表 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 和 drop distinct 并查看差异。选择所有行并注意执行/经过的时间。基于 emp 表避免不同的一般示例：

-- 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 tablr 中没有行，并且 empname 显示为 null。您的表 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
/
于 2013-02-07T18:17:01.550 回答