PostgreSQL NOT IN array slow query

Question

I have a large table with millions of rows. Each row has an array field tags. I also have the proper GIN index on tags.

Counting the rows that have a tag is fast (~7s):

SELECT COUNT(*) FROM "subscriptions" WHERE (tags @> ARRAY['t1']::varchar[]);

However counting the rows that don't have a tag is extremely slow (~70s):

SELECT COUNT(*) FROM "subscriptions" WHERE NOT (tags @> ARRAY['t1']::varchar[]);

I have also tried other variants, but with the same results (~70s):

SELECT COUNT(*) FROM "subscriptions" WHERE NOT ('t1' = ANY (tags));

How can I make the "not in array" operation fast?

Answer 1

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.

Answer 2

If 't1' is a rare tag, counting rows that don't have a tag results in counting most of your "millions of rows". And even if 't1' is very common, counting more than a few percent of rows from the index is no improvement over a sequential scan. Either way, this is never going to be very fast. Indexes are not going to help.

If you have to do several counts excluding rare tags - and the the total number of rows does not change in the meantime (or the minimal change does not matter), a possible optimization would be to get the total row count once (slow) and subtract the (small) count of rows with the tag (fast with matching index) ...

Depending on exact requirements and your complete use case, there may be other shortcuts. See:

• Fast way to discover the row count of a table in PostgreSQL

Bottom line, indexes can typically only help with identifying a relatively small percentage of table rows. BTW, IN, = ANY() and the containment operators @> are related tools, but with subtle differences. GIN indexes typically only support proper array operators. See:

• Can PostgreSQL index array columns?

You may get something out of using integer arrays in combination with operators and an index based on an operator class provided by the additional intarray module. Highly optimized, but it cannot defy above principals.

You can then also combine any mixture of tags that the row must have or must not have like you commented in a query_int expression.

Answer 3

You've already had a good answer, so here's a bit more to file under food for thought. First, your question reminded me of an interesting-sounding technique:

https://heap.io/blog/engineering/running-10-million-postgresql-indexes-in-production

I'd be interested in comments from those who have tried such a strategy.

As another thought, another option is to maintain your own frequency tables for tags and their occurrence. That can give you information to guide your own code generator. The idea here is that the generic query planner/optimizer can't ever know as much about your specific data as you do. With frequency counts, even reasonably good approximate counts, you can build different queries to submit to Postgres for different cases.

Fleshing out that frequency count idea

Elaborating a bit here as my original shorthand answer wasn't clear. The notion here is that you can maintain a table of frequency counts, like tag_count with unique tags and a count. That small data gives you the ability to test how common tags within a query are before generating the actual query for Postgres. This "simple" plan depends on several things, any number of which may not be true in your case:

• You've got code that's composing the queries that can be modified to do this pre-processing step to figure out how best to compose the query.

• You can find ways to use the frequency counts to help the planner do a better job.

• There's some way for you to run the frequency count update code.

• There's some way to maintain the counts with adequate fidelity and without bogging the system down.

That last point is huge topic, obviously. The simplest way (conceptually) is a trigger for add/mod/delete that finds the old and new tags, and adjusts counts accordingly. Not the most performant solution, and a potential bottleneck. There are many, many alternative designs. (A statement-level trigger with a post-and-reconcile queue table would be an alternate design that's not a bottleneck.) Honestly, I don't yet know the best performing strategies for incremental updates in Postgres. I sketched out ~10 strategies for myself a few months back, but haven't circled back to testing and comparing solutions. Other folks on this forum have been using Postgres for ages and are super smart and helpful. So, if this kind of solution is what you're after, it's worth asking again.