What is the correct/fastest way to negate @> in Postgres?
I don't think there is any highly effective way to index generic versions of that expression.  If you find a way to do so, I think you will be famous (well, famous within database circles, anyway).

If it is always exactly NOT column @&gt; array['thing'] where 'thing' does not change, you could build special-purpose indexes, like

create index on foo (("column" @&gt; array['thing']));


(or a partial index version of that)

Once 9.6 is released, you will be able to do the seq scan in parallel, and so get a boost that way.