3

2つのテーブルがあり、どちらにも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 が述べたように、最短距離の 2 乗の行は最短距離の行にもなるため、行の組み合わせごとに平方根を計算する必要はありません。

あなたの最善の最善は、実行される計算の全体的な数を減らそうとしていると思うので、おそらく次のようなものがスピードアップします:

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 * 500k 行をチェックするのではなく、その行をもう一方のテーブルの 500k に対してチェックし、必要に応じて TABLE_C を更新できます。

于 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側面...不明。必要に応じて比較を交換してください）。
ここで 2 つのことに注意してください。

  1. これはすべて、平らなデカルト平面で操作していることを前提としています。これが地表上のポイントの場合、方程式はかなり複雑になります。ただし、見れば、それらをカバーする質問/回答がたくさんあります。
  2. 平方根の距離を取得/使用する必要があります。そうしないと、実際には距離の「外側」にあるグリッドの正方形の隅に物が隠れているためです (約 40%)。
于 2013-02-07T19:06:28.920 に答える
0

テーブルに対応する/一致する行がない場合は、JOINをまったく使用しないでください。2つの別々のクエリを使用します。それ以外の場合、出力には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を使用しています。結合とドロップを個別に追加して、違いを確認してください。すべての行を選択し、実行/経過時間を記録します。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)
/

アウタージョイン。以下のクエリは、BがテーブルAに対応する行を持っていない場合でも、Aテーブル（dept）テーブルとBからすべての行を返します。クエリを実行してdeptno = 40を参照してください。emptablrに行がなく、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 に答える