2

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?

2

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.

  • That's fantastic! Thanks for digging in on the question until you brought back a real solution. – Morris de Oryx Nov 13 at 21:33
1

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:

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:

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.

  • I have simplified my question, however I have to filter the tables based on arbitrary data and arbitrary tags. The query can any mixture of tags that the row must have or must not have. Also I cannot make assumptions on data since it is a SaaS. The estimates don't work well, I have already tried them and the bias is too high :( – collimarco Nov 12 at 18:16
  • I have already tried the && (0verlap) operator for string array and I have already have the gin index, but the results are the same (~70s) – collimarco Nov 13 at 9:29
1

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.

  • The problem is that I don't have any idea about data or tags, because it is a SaaS and our customers can enter arbitrary tags in the database and then execute arbitrary queries on tags (e.g. it has tag 't1' and not tag 't2', etc.) – collimarco Nov 13 at 9:24
  • I've expanded my answer which, honestly, may or may not be a good match for you. – Morris de Oryx Nov 13 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.