PostgreSQL NOT IN array slow query
I have solved thanks to Jeff Janes on the pgsql-performance mailing list:

The GIN index was not used by PostgreSQL for the "NOT" operation. Creating a Btree index on the whole array solved the problem, allowing an index only scan. Now the query takes only a few milliseconds instead of minutes.