问题:按值(不是列)分组后从组中选择一个随机条目?

我想使用 Postgres 和 PostGIS 编写查询。我也在使用带有rgeo、rgeo-activerecord和activerecord-postgis-adapter的 Rails,但 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

• 你是d

查询应该做什么:

1. 查询从点p中查找具有distance < d的所有groundtruth点

SQL 非常简单:WHERE st_distance(groundtruth, p) < d

2. 现在我们有一个groundtruth点列表及其anchor_ids。正如您在上表中看到的,可能有多个相同的 groundtruth-anchor_id 元组。例如:anchor_id=3和groundtruth=POINT(1 4)。

3. 接下来我想通过随机选择其中一个来消除相同的元组(!)。为什么不直接拿第一呢?因为data列不同。

在 SQL 中选择随机行:SELECT ... ORDER BY RANDOM() LIMIT 1

我对所有这一切的问题是:我可以想象一个使用 SQLLOOPs 和大量子查询的解决方案,但是肯定有一个使用GROUP BY或其他一些方法的解决方案可以使其更快。

完整版:

与上述基本相同,不同之处在于:输入参数变化:

• 点数p1...p312456345

• 还是一个d

如果简单查询有效,可以使用 SQL 中的LOOP来完成。但也许有更好(更快)的解决方案,因为数据库真的很大!

---

解决方案

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();

感谢欧文·布兰德施泰特!

解答

为了消除重复,这可能是 PostgreSQL 中最有效的查询:

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

有关此查询样式的更多信息:

• 在每个 GROUP BY 组中选择第一行?

正如评论中提到的,这给了你一个_arbitrary_的选择。如果您需要随机,则要贵一些:

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

---

第二部分更难优化。EXISTSsemi-join 可能是最快的选择。对于给定的表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足够接近,它就可以停止评估,并且它使查询的其余部分保持简单。

请务必使用匹配的 GiST 索引](http://blog.opengeo.org/2011/09/28/indexed-nearest-neighbour-search-in-postgis/)来支持它。

如果您有一个数组作为输入,请即时创建一个CTE和unnest():

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

根据评论更新

如果您只需要一个单行作为答案,您可以简化:

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 索引!)可能更有效。

要获得 one 行(在此处使用子选择而不是 CTE):

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

要在距离d内为每个点p** 获得 **一行:

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()将使这个查询_更昂贵_。如果没有random(),Postgres 只能从 GiST 索引中选择_第一个_匹配行。否则_所有_可能的匹配必须随机检索和排序。

---

顺便说一句,EXISTS里面的LIMIT 1是没有意义的。在我提供的链接中阅读手册或这个相关问题。