GIN Index has O(N^2) complexity for array overlap operator?

Question

I ran into an issue with using the && array operator on a GIN index of mine. Basically I have a query that looks like this:

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

This works fine for a small number of array elements (N) in the array literal, but gets really slow as N gets bigger in what appears to be O(N^2) complexity.

However, from studying the GIN data structure as described by the docs, it seems that the performance for this could be O(N). In fact, it's possible to coerce the query planner into an O(N) plan like this:

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

In order to illustrate this better, I've created a jupyter notebook that populates an example table, show the query plans for both queries, and most importantly benchmarks them and plots a time vs array size (N) graph.

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

Please help me understand what causes the O(N^2) performance for query 1 and if query 2 is the best way to work around this issue.

Thanks Felix Geisendörfer

PS: I'm using Postgres 10, but also verified that this problem exists with Postgres 11.

I've also posted this question on the postgres performance mailing list, but unfortunately didn't get any answer.

Answer 1

you need three things:

create extension intarray;

then create gist index with operator gist__int_opts

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

drop old index if any.

and voila - your query now uses bitmap index scan:

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

result:

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)

Documentation