1

我有一张1.5 MM记录表。每条记录在数组中的元素之间都有一个row number和一个。我正在尝试查找作为较大数组子集的所有数组。array1 and 1,000

当我使用下面的代码时，我得到 ERROR: statement requires more resources than resource queue allowed (可能是因为有超过一万亿种可能的组合)：

select
   a.array as dup
from
   table a
left join
    table  b
on
  b.array @> a.array 
  and a.row_number <> b.row_number

是否有更有效的方法来识别哪些数组是其他数组的子集并将它们标记为除使用之外的删除@>？

4

2 回答 2

0

您的示例代码表明您只对查找作为表格另一行中任何其他数组的子集的数组感兴趣。

但是，带有 a 的查询JOIN会返回所有组合，可能会成倍增加结果。

尝试使用EXISTS半连接，只返回一次符合条件的行：

SELECT a.array as dup
FROM   table a
WHERE  EXISTS (
   SELECT 1
   FROM   table b
   WHERE  a.array <@ b.array
   AND    a.row_number <> b.row_number
   );

使用这种形式，Postgres 可以在找到第一个匹配项后立即停止迭代行。如果这也不会通过，请尝试对查询进行分区。添加一个像

AND table_id BETWEEN 0 AND 10000

并遍历表。对于这种情况应该是有效的。

顺便说一句：很遗憾，您的派生（Greenplum）似乎不支持 GIN 索引，这将使此操作更快。（不过，索引本身会很大）

于 2014-02-05T16:33:38.643 回答
0

好吧，如果没有索引的适当支持，我看不出如何在单个声明性 SQL 语句中有效地执行此操作。我不知道这对 GIN 索引的效果如何，但使用 GIN 索引肯定会避免需要比较每一对可能的行。

我要做的第一件事是仔细调查您可以使用的索引类型，并尝试根据需要创建一个。

如果这不起作用，从程序上讲，我首先想到的是对所有数组进行排序，然后将行排序为数组上的分级字典顺序。然后从最短的数组开始，向上工作如下：例如，对于 [1,4,9]，检查所有长度 <= 3 的数组，如果它们是子集，则以 1 开头，然后检查所有长度 <= 的数组2 以 4 开头，然后检查所有长度 <= 1 且以 9 开​​头的数组，同时删除任何找到的子集，这样您就不会一遍又一遍地重新检查相同的行。

我相信你可以稍微调整一下这个算法，尤其是根据所涉及数据的特定性质。如果有更好的算法，我不会感到惊讶。这只是我想到的第一件事。您可能可以从该算法向后工作到您想要的 SQL，或者您可能必须转储表以进行客户端处理，或者它们的某种混合。

于 2014-02-05T16:28:54.040 回答