需要 SQL 优化（也许 DISTINCT ON 是原因？）

Question

相关的，前置问题：
按值（而非列）分组后从组中选择随机条目？

我的当前查询如下：

WITH
  points AS (
    SELECT unnest(array_of_points) AS p
  ),

 gtps AS (
   SELECT DISTINCT ON(points.p)
     points.p, m.groundtruth
   FROM measurement m, points
   WHERE st_distance(m.groundtruth, points.p) < distance
   ORDER BY points.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()

语义：

1. 有两个输入值：

   • 第4行：一个点数组 array_of_points
   • 第12行：一个双精度数：distance

2. 第一段（第1-6行）：

   • 从点数组中创建一个表，用于...

3. 第二段（第8-14行）：

   • 对于 points 表内的每个点：从 measurement 表中获取一个随机(!)的 groundtruth 点，该点距离小于 distance
   • 将这些元组保存在 gtps 表中

4. 第三段（第16-19行）：

   • 对于 gtps 表内的每个 groundtruth 值：获取所有 anchor_id 值并...
   • 如果一个 anchor_id 值不唯一：则选择一个随机的

5. 输出：id、anchor_id、groundtruth、p（来自 array_of_points 的输入值）

示例表格：

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

例子结果：

id  | anchor_id | groundtruth | p
-----------------------------------------
1   | 1         | POINT(1 4)  | POINT(1 0)
2   | 3         | POINT(1 4)  | POINT(1 0)
4   | 6         | POINT(1 4)  | POINT(1 0)
3   | 8         | POINT(1 4)  | POINT(1 0)
5   | 2         | POINT(3 2)  | POINT(2 2)
6   | 4         | POINT(3 2)  | POINT(2 2)
1   | 1         | POINT(1 4)  | POINT(4 8)
2   | 3         | POINT(1 4)  | POINT(4 8)
4   | 6         | POINT(1 4)  | POINT(4 8)
3   | 8         | POINT(1 4)  | POINT(4 8)
12  | 1         | POINT(6 2)  | POINT(7 3)
13  | 5         | POINT(6 2)  | POINT(7 3)
1   | 1         | POINT(4 3)  | POINT(9 1)
11  | 3         | POINT(4 3)  | POINT(9 1)
9   | 6         | POINT(4 3)  | POINT(9 1)
10  | 7         | POINT(4 3)  | POINT(9 1)

正如您所见：

• 每个输入值都可以有多个相等的groundtruth值。
• 如果一个输入值有多个groundtruth值，则这些值必须全部相等。
• 每个groundtruth-inputPoint元组都与该groundtruth的每个可能的anchor_id相连接。
• 两个不同的输入值可以具有相同的对应groundtruth值。
• 两个不同的groundtruth-inputPoint元组可以具有相同的anchor_id。
• 两个相同的groundtruth-inputPoint元组必须具有不同的anchor_id。

基准测试（针对两个输入值）：

• 第1-6行：16ms
• 第8-14行：48ms
• 第16-19行：600ms

EXPLAIN VERBOSE：

Unique  (cost=11119.32..11348.33 rows=18 width=72)
  Output: m.id, m.anchor_id, gtps.groundtruth, gtps.p, (random())
  CTE points
    ->  Result  (cost=0.00..0.01 rows=1 width=0)
          Output: unnest('{0101000000EE7C3F355EF24F4019390B7BDA011940:01010000003480B74082FA44402CD49AE61D173C40}'::geometry[])
  CTE gtps
    ->  Unique  (cost=7659.95..7698.12 rows=1 width=160)
          Output: points.p, m.groundtruth, (random())
          ->  Sort  (cost=7659.95..7679.04 rows=7634 width=160)
                Output: points.p, m.groundtruth, (random())
                Sort Key: points.p, (random())
                ->  Nested Loop  (cost=0.00..6565.63 rows=7634 width=160)
                      Output: points.p, m.groundtruth, random()
                      Join Filter: (st_distance(m.groundtruth, points.p) < m.distance)
                      ->  CTE Scan on points  (cost=0.00..0.02 rows=1 width=32)
                            Output: points.p
                      ->  Seq Scan on public.measurement m  (cost=0.00..535.01 rows=22901 width=132)
                            Output: m.id, m.anchor_id, m.tag_node_id, m.experiment_id, m.run_id, m.anchor_node_id, m.groundtruth, m.distance, m.distance_error, m.distance_truth, m."timestamp"
  ->  Sort  (cost=3421.18..3478.43 rows=22901 width=72)
        Output: m.id, m.anchor_id, gtps.groundtruth, gtps.p, (random())
        Sort Key: gtps.p, gtps.groundtruth, m.anchor_id, (random())
        ->  Nested Loop  (cost=0.00..821.29 rows=22901 width=72)
              Output: m.id, m.anchor_id, gtps.groundtruth, gtps.p, random()
              ->  CTE Scan on gtps  (cost=0.00..0.02 rows=1 width=64)
                    Output: gtps.p, gtps.groundtruth
              ->  Seq Scan on public.measurement m  (cost=0.00..535.01 rows=22901 width=8)
                    Output: m.id, m.anchor_id, m.tag_node_id, m.experiment_id, m.run_id, m.anchor_node_id, m.groundtruth, m.distance, m.distance_error, m.distance_truth, m."timestamp"

解释分析：

Unique  (cost=11119.32..11348.33 rows=18 width=72) (actual time=548.991..657.992 rows=36 loops=1)
  CTE points
    ->  Result  (cost=0.00..0.01 rows=1 width=0) (actual time=0.004..0.011 rows=2 loops=1)
  CTE gtps
    ->  Unique  (cost=7659.95..7698.12 rows=1 width=160) (actual time=133.416..146.745 rows=2 loops=1)
          ->  Sort  (cost=7659.95..7679.04 rows=7634 width=160) (actual time=133.415..142.255 rows=15683 loops=1)
                Sort Key: points.p, (random())
                Sort Method: external merge  Disk: 1248kB
                ->  Nested Loop  (cost=0.00..6565.63 rows=7634 width=160) (actual time=0.045..46.670 rows=15683 loops=1)
                      Join Filter: (st_distance(m.groundtruth, points.p) < m.distance)
                      ->  CTE Scan on points  (cost=0.00..0.02 rows=1 width=32) (actual time=0.007..0.020 rows=2 loops=1)
                      ->  Seq Scan on measurement m  (cost=0.00..535.01 rows=22901 width=132) (actual time=0.013..3.902 rows=22901 loops=2)
  ->  Sort  (cost=3421.18..3478.43 rows=22901 width=72) (actual time=548.989..631.323 rows=45802 loops=1)
        Sort Key: gtps.p, gtps.groundtruth, m.anchor_id, (random())"
        Sort Method: external merge  Disk: 4008kB
        ->  Nested Loop  (cost=0.00..821.29 rows=22901 width=72) (actual time=133.449..166.294 rows=45802 loops=1)
              ->  CTE Scan on gtps  (cost=0.00..0.02 rows=1 width=64) (actual time=133.420..146.753 rows=2 loops=1)
              ->  Seq Scan on measurement m  (cost=0.00..535.01 rows=22901 width=8) (actual time=0.014..4.409 rows=22901 loops=2)
Total runtime: 834.626 ms

运行时应该有大约100到1000个输入值，目前需要花费35到350秒，这太长了。

我已经尝试去除RANDOM()函数。这将运行时间（对于2个输入值）从约670毫秒减少至约530毫秒。因此，目前它不是主要影响因素。

如果更容易/更快捷的话，也可以运行2或3个单独的查询并在软件中执行一些部分（它正在运行于Ruby on Rails服务器上）。例如随机选择？！

正在进行的工作：

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, distance)
GROUP BY groundtruth, ps.p

使用这个查询非常快（15毫秒），但是有很多缺失：

• 我只需要每个 ps.p 的一个随机行。
• 这两个数组相互属于。也就是说：其中的项目顺序很重要！
• 这两个数组需要进行过滤（随机）：
  对于数组中出现多次的每个 anchor_id：保留一个随机的，并删除所有其他的。这还意味着对于每个已删除的 anchor_id，需要从 id 数组中删除相应的 id。

如果能够将 anchor_id 和 id 存储在元组数组中，那就更好了。例如：{[4,1],[6,3],[4,2],[8,5],[4,4]}（约束条件：每个元组都是唯一的，每个 id（== 示例中的第二个值）都是唯一的，anchor_id 不唯一）。该示例显示了未应用筛选器的查询。应用筛选器后，它将如下所示：{[6,3],[4,4],[8,5]}。

工作正在进行中 II：

SELECT DISTINCT ON (ps.p)
  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, distance)
GROUP BY ps.p, m.groundtruth
ORDER BY ps.p, RANDOM()

现在它提供了不错的结果，并且仍然非常快：16ms
只剩下一件事要做：

• ARRAY_AGG(m.anchor_id) 已经被随机化，但是：
• 它包含大量重复的条目，所以：
• 我想在它上面使用类似 DISTINCT 的东西，但是：
• 它必须与 ARRAY_AGG(m.id) 同步。这意味着：
  如果 DISTINCT 命令保留 anchor_id 数组的索引1、4和7，则它也必须保留 id 数组的索引1、4和7（当然还要删除所有其他的索引）。

- Benjamin M

---

请运行 explain analyze 命令以查看实际耗时情况。 - user330315

完成。输出在explain verbose下方。解释详细 - Benjamin M

始终明确指定您的连接，即使是 CROSS JOIN 也是如此 - 但是，如果您可以预先计算坐标的边界和最大距离（包括 points），则可以进行相关联。外部查询可能会以交叉连接的方式误导您 - 为什么不基于先前收集的点呢？我不确定使用 RANDOM() 对结果进行排序是否真正实现了您想要的效果，但我不确定这是否不可取... - Clockwork-Muse

关于“RANDOM()”：输出正是我想要的。引用：“外部查询可能以交叉连接的方式误导 - 为什么不基于先前收集的点呢？”你是什么意思？我只是不知道如何在一个查询中适配所有的东西，所以我决定按照我想要的顺序写下这些东西... - Benjamin M

我另起了一个问题，因为现在的问题非常具体，涉及到postgres和array_agg：https://dev59.com/questions/z27Xa4cB1Zd3GeqPvvfd - Benjamin M

Answer 1

如果把anchor_id和id存储在一个元组数组中会更好。

多维数组的聚合函数

我认为你可以创建一个二维数组。这比记录的数组更容易处理。标准的array_agg()无法聚合多维数组。但是，你很容易就能自己编写一个聚合函数：

CREATE AGGREGATE array_agg_mult (anyarray)  (
    SFUNC     = array_cat
   ,STYPE     = anyarray
   ,INITCOND  = '{}'
);

请阅读相关答案中的解释：
选择数据到Postgres数组中

对于出现多次的数组中的每个anchor_id：保留一个随机的并删除所有其他的。这也意味着要从每个已删除的anchor_id的id数组中删除相应的id。

查询

SELECT DISTINCT ON (p)
       p, groundtruth, array_agg_mult(ARRAY[ARRAY[anchor_id, id]]) AS ids
FROM (
   SELECT DISTINCT ON (ps.p, m.groundtruth, m.anchor_id)
          ps.p, m.groundtruth, m.anchor_id, m.id
   FROM  (SELECT unnest(point_array) AS p) AS ps
   JOIN   measurement m ON ST_DWithin(ps.p, m.groundtruth, distance)
   ORDER  BY ps.p, m.groundtruth, m.anchor_id, random()
   ) x
GROUP  BY p, groundtruth
ORDER  BY p, random();

• Subquery x gets distinct anchor_id per (p, groundtruth) and picks a random row if there are multiple peers. This way the connection anchor_id - id stays intact.

• The outer query aggregates a 2-dimensional array like you wished for, ordered by anchor_id. If you want to have anchor_id ordered randomly, use random once more:

  array_agg_mult(ARRAY[ARRAY[anchor_id, id]] ORDER BY random())
  

• And finally, the DISTINCT ON picks only 1 groundtruth per p, randomly again.

- Erwin Brandstetter

---

再次感谢Erwin :) 您的查询有一点问题：结果集中包含一些p两次（甚至三次）。而且每次调用时行数都在变化。 - Benjamin M

呵呵。但是答案是否定的。结果数量是正确的，但每个数组只有一个元组:( 顺便说一句: 这个查询版本非常慢: 350毫秒(相对于20毫秒)。 - Benjamin M

@BenjaminM：不幸的是，我没有安装PostGis。通常在发布之前我会进行测试，但今天我为您发布的大部分内容都是基于我的经验和知识。无论如何，我希望在我的（最后？）更新后，现在能从您的烟囱中看到白烟升起。 - Erwin Brandstetter

太好了！我认为你做到了！有4个输入值和4个输出值。p是独特的，但groundtruth不是独特的，每个元组的第一个值也是独特的，并且它只需要17毫秒。太棒了！！ :) - Benjamin M

似乎无论我输入多少个值，它都不会有所影响：对于4个值，它需要17毫秒。对于10个值，它需要34毫秒，对于25个值，它也需要34毫秒。这真是太神奇了！附言：50个输入值需要85毫秒。我认为它不能再快了 ;) 另外，我的快速解决方案（没有过滤anchor_id）对于50个值需要82毫秒。所以你做得很好！ - Benjamin M