3

PostgresとPostGISを使ってクエリを書きたいです。rgeoRailsも、、、rgeo-activerecordで使用していますactiverecord-postgis-adapterが、Railsのものはそれほど重要ではありません。

テーブル構造：

measurement
 - int id
 - int anchor_id
 - Point groundtruth
 - data (not important for the query)

データ例：

id | anchor_id | groundtruth | data
-----------------------------------
1  | 1         | POINT(1 4)  | ...
2  | 3         | POINT(1 4)  | ...
3  | 2         | POINT(1 4)  | ...
4  | 3         | POINT(1 4)  | ...
-----------------------------------
5  | 2         | POINT(3 2)  | ...
6  | 4         | POINT(3 2)  | ...
-----------------------------------
7  | 1         | POINT(4 3)  | ...
8  | 1         | POINT(4 3)  | ...
9  | 1         | POINT(4 3)  | ...
10 | 5         | POINT(4 3)  | ...
11 | 3         | POINT(4 3)  | ...

このテーブルは、view（数百万行の）ルックアップを高速化するために手動で作成されたものです。そうしないと、8つのテーブルを結合する必要があり、さらに遅くなります。しかし、それは問題の一部ではありません。

シンプルバージョン：

パラメーター：

  • 点p
  • intd

クエリが行うべきこと：

1.クエリはfromポイントgroundtruthを持つすべてのポイントを探しますdistance < dp

そのためのSQLは非常に簡単です。WHERE st_distance(groundtruth, p) < d

2.groundtruthこれで、ポイントとそのポイントのリストができましたanchor_id。上の表からわかるように、複数の同一のgroundtruth-anchor_idタプルを持つことができます。例：anchor_id=3およびgroundtruth=POINT(1 4)。

3.次に、同じタプルの1つをランダムに選択して、同じタプルを削除します（！）。単純に最初のものを取りませんか？data列が違うからです。

SQLでランダムな行を選択する：SELECT ... ORDER BY RANDOM() LIMIT 1

これらすべてに関する私の問題は次のとおりです。SQLLOOPと多数のサブクエリを使用した解決策を想像できますがGROUP BY、それを高速化する他の方法を使用した解決策は確かにあります。

完全版：

基本的に上記と同じですが、1つの違いがあります。入力パラメータが変更されます。

  • たくさんのポイントp1..。p312456345
  • まだ1つd

LOOP単純なクエリが機能している場合、これはSQLでを使用して実行できます。しかし、データベースは本当に巨大なので、おそらくより良い（そしてより速い）解決策があるでしょう！

解決

WITH ps AS (SELECT unnest(p_array) AS p)
SELECT DISTINCT ON (anchor_id, groundtruth)
    *
FROM measurement m, ps
WHERE EXISTS (
    SELECT 1
    FROM ps
    WHERE st_distance(m.groundtruth, ps.p) < d
)
ORDER BY anchor_id, groundtruth, random();

Erwin Brandstetterに感謝します！

4

2 に答える 2

1

重複を排除するには、これがPostgreSQLで最も効率的なクエリである可能性があります。

SELECT DISTINCT ON (anchor_id, groundtruth) *
FROM   measurement
WHERE  st_distance(p, groundtruth) < d

このクエリスタイルの詳細：

コメントで述べたように、これはあなたに任意の選択を与えます。ランダムが必要な場合は、やや高価です。

SELECT DISTINCT ON (anchor_id, groundtruth) *
FROM   measurement
WHERE  st_distance(p, groundtruth) < d
ORDER  BY anchor_id, groundtruth, random()

2番目の部分は最適化が困難です。EXISTSセミジョインがおそらく最速の選択でしょう。特定のテーブルの場合ps (p point)：

SELECT DISTINCT ON (anchor_id, groundtruth) *
FROM   measurement m
WHERE  EXISTS (
   SELECT 1
   FROM   ps
   WHERE  st_distance(ps.p, m.groundtruth) < d
   )
ORDER  BY anchor_id, groundtruth, random();

pこれにより、1つが十分に近づくとすぐに評価を停止でき、残りのクエリが単純になります。

一致するGiSTインデックスを使用してバックアップしてください。

入力として配列がある場合は、オンザフライでCTEを作成します。unnest()

WITH ps AS (SELECT unnest(p_array) AS p)
SELECT ...

コメントに従って更新

答えとして1行だけが必要な場合は、次のように簡略化できます。

WITH ps AS (SELECT unnest(p_array) AS p)
SELECT *
FROM   measurement m
WHERE  EXISTS (
   SELECT 1
   FROM   ps
   WHERE  st_distance(ps.p, m.groundtruth) < d
   )
LIMIT  1;

より速くST_DWithin()

ST_DWithin()関数（および一致するGiSTインデックス！）を使用すると、おそらくより効率的です。1つの
行 を取得するには（ここではCTEの代わりに副選択を使用）：

SELECT *
FROM   measurement m
JOIN  (SELECT unnest(p_array) AS p) ps ON ST_DWithin(ps.p, m.groundtruth, d)
LIMIT  1;

距離内のすべてのポイントに対して1つの行pを取得するにはd：

SELECT DISTINCT ON (ps.p) *
FROM   measurement m
JOIN  (SELECT unnest(p_array) AS p) ps ON ST_DWithin(ps.p, m.groundtruth, d)

追加ORDER BY random()すると、このクエリのコストが高くなります。がない場合、PostgresはGiSTインデックスから最初にrandom()一致する行を選択するだけです。それ以外の場合は、可能なすべての一致をランダムに取得して並べ替える必要があります。

ところで、LIMIT 1中EXISTSは無意味です。私が提供したリンクまたはこの関連する質問でマニュアルを読んでください。

于 2013-02-26T14:25:22.623 に答える
0

私は今それをクラックしました、しかしクエリはかなり遅いです...

WITH
  ps AS (
    SELECT unnest(p_array)
    ) AS p
  ),

  gtps AS (
    SELECT DISTINCT ON(ps.p)
      ps.p, m.groundtruth
    FROM measurement m, ps
    WHERE st_distance(m.groundtruth, ps.p) < d
    ORDER BY ps.p, RANDOM()
  )

SELECT DISTINCT ON(gtps.p, gtps.groundtruth, m.anchor_id)
  m.id, m.anchor_id, gtps.groundtruth, gtps.p
FROM measurement m, gtps
ORDER BY gtps.p, gtps.groundtruth, m.anchor_id, RANDOM()

私のテストデータベースには22000行が含まれており、2つの入力値を指定しましたが、約700ミリ秒かかります。最後に、何百もの入力値が存在する可能性があります：-/

結果は次のようになります。

id  | anchor_id | groundtruth | p
-----------------------------------------
20  | 1         | POINT(0 2)  | POINT(1 0)
14  | 3         | POINT(0 2)  | POINT(1 0)
5   | 8         | POINT(0 2)  | POINT(1 0)
42  | 2         | POINT(4 1)  | POINT(2 2)
11  | 3         | POINT(4 8)  | POINT(4 8)
4   | 6         | POINT(4 8)  | POINT(4 8)
1   | 1         | POINT(6 2)  | POINT(7 3)
9   | 5         | POINT(6 2)  | POINT(7 3)
25  | 3         | POINT(6 2)  | POINT(9 1)
13  | 6         | POINT(6 2)  | POINT(9 1)
18  | 7         | POINT(6 2)  | POINT(9 1)

新着：

SELECT
  m.groundtruth, ps.p, ARRAY_AGG(m.anchor_id), ARRAY_AGG(m.id)
FROM
  measurement m
JOIN
  (SELECT unnest(point_array) AS p) AS ps
  ON ST_DWithin(ps.p, m.groundtruth, 0.5)
GROUP BY groundtruth, ps.p

実結果：

p           | groundtruth | anchor_arr | id_arr
--------------------------------------------------
P1          | G1          | {1,3,2,..} | {9,8,11,..}
P1          | G2          | {4,3,5,..} | {1,8,23,..}
P1          | G3          | {6,8,9,..} | {12,7,6,..}
P2          | G1          | {6,6,2,..} | {15,2,10,..}
P2          | G4          | {7,9,1,..} | {5,4,3,..}
...         | ...         | ...        | ...

だから私が得る瞬間：

  • すべての個別のinputValue-groundtruth-tuple
  • for every tuple I get an array with all anchor_id corresponding the groundtruth part of the tuple
  • and an array of all ids corresponding the groundtruth-anchor_id relation

Remember:

  • two input values can 'select' the same groundtruth
  • a single groundtruth value can have multiple identical anchor_ids
  • each groundtruth-anchor_id-tuple has a distinct id

So what's missing for completion?:

  • I just need a random row for each ps.p
  • The two arrays belong to each other. Means: the order of the items inside is important!
  • Those two arrays need to get filtered (randomly):
    • For each anchor_id in the array that appears more than once: keep a random one and delete all other. This also means to remove the corresponding id from the id-array for every deleted anchor_id
于 2013-02-26T17:04:23.070 に答える