sql - 按值(不是列)分组后从组中选择一个随机条目？

Question

我想使用 Postgres 和 PostGIS 编写查询。我也将 Rails 与 rgeo 、 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
• int d

查询应该做什么:

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

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

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

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

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

我对这一切的问题是:我可以想象一个使用 SQL LOOP s 和大量子查询的解决方案，但是肯定有一个使用 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();

感谢 Erwin Brandstetter!

Answer 1

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

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

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

• Select first row in each GROUP BY group?

如评论中所述，这为您提供了任意选择。如果你需要随机，稍微贵一些:

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

---

第二部分更难优化。 EXISTS半连接可能是最快的选择。对于给定的表ps(p点):

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 足够接近时停止计算，并使其余的查询保持简单。

请务必使用 a matching GiST index 进行备份.

如果你有一个数组作为输入，创建一个 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 索引!)。
要获得一个行(在这里使用子选择而不是 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 毫无意义。阅读the manual at the link I provided或 this related question .