sql - 数组重叠运算符的 GIN 索引具有 O(N^2) 复杂度？

Question

我在我的 GIN 索引上使用 && 数组运算符时遇到了问题。基本上我有一个看起来像这样的查询：

SELECT *
FROM example
WHERE keys && ARRAY[1,2,3,...]

这对于数组字面量中的少量数组元素 (N) 工作得很好，但是随着 N 变得越来越大，看起来 O(N^2) 的复杂度变得非常慢。

但是，通过研究文档中描述的 GIN 数据结构，似乎其性能可能是 O(N)。实际上，可以将查询计划器强制转换为 O(N) 计划，如下所示：

SELECT DISTINCT ON (example.id) *
FROM unnest(ARRAY[1,2,3,...]) key
JOIN example ON keys && ARRAY[key]

为了更好地说明这一点，我创建了一个填充示例表的 jupyter 笔记本，显示两个查询的查询计划，最重要的是对它们进行基准测试并绘制时间与数组大小 (N) 的关系图。

https://github.com/felixge/pg-slow-gin/blob/master/pg-slow-gin.ipynb

请帮助我了解导致查询 1 的 O(N^2) 性能的原因以及查询 2 是否是解决此问题的最佳方法。

谢谢费利克斯·盖森多弗

PS：我使用的是 Postgres 10，但也验证了 Postgres 11 存在这个问题。

我也在postgres 性能邮件列表上发布了这个问题，但不幸的是没有得到任何答案。

标签： sqlpostgresqlindexing

Answer 1

你需要三样东西：

create extension intarray;

然后使用运算符 gist__int_opts 创建 gist 索引

CREATE INDEX fgfe
   ON public.arrtest USING gist (keys2 gist__int_ops );

删除旧索引（如果有）。

瞧——您的查询现在使用位图索引扫描：

explain SELECT *
FROM arrtest
WHERE  ARRAY[1,2,3,4] && keys2

结果：

Bitmap Heap Scan on arrtest  (cost=4.24..14.92 rows=12 width=104)
  Recheck Cond: ('{1,2,3,4}'::integer[] && keys2)
  ->  Bitmap Index Scan on fgfe  (cost=0.00..4.23 rows=12 width=0)
        Index Cond: ('{1,2,3,4}'::integer[] && keys2)

文档