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是否是解决此问题的最佳方法。

感谢FelixGeisendörfer

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

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

Answer 1

你需要三件事：

create extension intarray;

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

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)

文档