Postgres - fast way to enforce AND across multiple rows I've got a 4 column table with ~25M rows:

tweetifai=&gt; \d core_tagusage;
                                 Table "public.core_tagusage"
  Column  |         Type          |                         Modifiers
----------+-----------------------+------------------------------------------------------------
 id       | integer               | not null default nextval('core_tagusage_id_seq'::regclass)
 tag      | character varying(30) | not null
 score    | double precision      | not null
 tweet_id | character varying(16) | not null
Indexes:
    "core_tagusage_pkey" PRIMARY KEY, btree (id)
    "core_tagusage_tag_3ed0f993a18dd430_uniq" UNIQUE CONSTRAINT, btree (tag, tweet_id)
    "core_tagusage_cea90699" btree (tweet_id)
    "core_tagusage_score_772bb061400905c6_uniq" btree (score)
    "core_tagusage_tag_443351eb_uniq" btree (tag)
    "core_tagusage_tweet_id_11461293c1e23f80_like" btree (tweet_id varchar_pattern_ops)
Foreign-key constraints:
    "core_tagusage_tweet_id_11461293c1e23f80_fk_core_imagetweet_id" FOREIGN KEY (tweet_id) REFERENCES core_imagetweet(id) DEFERRABLE INITIALLY DEFERRED


There is a many-to-many relationship between tweet_id and tag.

Given a few tags (eg. "dog", "grass", "frisbee") I'd like to retrieve all tweet_ids  which match all tags and sort by score. Here's my query:

SELECT *
FROM (SELECT
        COUNT(ort.tweet_id) AS numtags,
        ort.tweet_id,
        MIN(ort.score)      AS minscore
      FROM (SELECT
              tg.tweet_id AS tweet_id,
              tg.tag      AS tag,
              tg.score    AS score
            FROM core_tagusage AS tg
            WHERE tg.tag = 'dog'
                  OR tg.tag = 'grass'
                  OR tg.tag = 'frisbee'
           ) AS ort
      GROUP BY ort.tweet_id) AS ct
WHERE numtags = 3
ORDER BY minscore DESC
LIMIT 200;


Even without the ORDER BY this is remarkably slow (~10-20 seconds). Here's what I get from EXPLAIN ANALYZE:

Limit  (cost=0.56..22720.77 rows=200 width=33) (actual time=24177.117..24177.117 rows=0 loops=1)
  -&gt;  GroupAggregate  (cost=0.56..1327311.85 rows=11685 width=25) (actual time=24177.115..24177.115 rows=0 loops=1)
        Group Key: tg.tweet_id
        Filter: (count(tg.tweet_id) = 3)
        Rows Removed by Filter: 493764
        -&gt;  Index Scan using core_tagusage_cea90699 on core_tagusage tg  (cost=0.56..1321691.90 rows=547389 width=25) (actual time=0.206..23322.853 rows=501654 loops=1)
              Filter: (((tag)::text = 'dog'::text) OR ((tag)::text = 'grass'::text) OR ((tag)::text = 'frisbee'::text))
              Rows Removed by Filter: 24309855
Planning time: 0.237 ms
Execution time: 24177.166 ms


Is there a different query I could write to achieve the same results?

edit:

EXPLAIN ANALYZE SELECT
              tg.tweet_id AS tweet_id,
              tg.tag      AS tag,
              tg.score    AS score
            FROM core_tagusage AS tg
            WHERE tg.tag = 'dog'
                  OR tg.tag = 'grass'
                  OR tg.tag = 'tree';

Bitmap Heap Scan on core_tagusage tg  (cost=295.51..44454.72 rows=13794 width=32) (actual time=8.253..105.051 rows=104691 loops=1)
  Recheck Cond: (((tag)::text = 'dog'::text) OR ((tag)::text = 'grass'::text) OR ((tag)::text = 'tree'::text))
  Heap Blocks: exact=1133
  -&gt;  BitmapOr  (cost=295.51..295.51 rows=13797 width=0) (actual time=8.111..8.111 rows=0 loops=1)
        -&gt;  Bitmap Index Scan on core_tagusage_tag_443351eb_uniq  (cost=0.00..95.06 rows=4599 width=0) (actual time=3.238..3.238 rows=38385 loops=1)
              Index Cond: ((tag)::text = 'dog'::text)
        -&gt;  Bitmap Index Scan on core_tagusage_tag_443351eb_uniq  (cost=0.00..95.06 rows=4599 width=0) (actual time=2.217..2.217 rows=30477 loops=1)
              Index Cond: ((tag)::text = 'grass'::text)
        -&gt;  Bitmap Index Scan on core_tagusage_tag_443351eb_uniq  (cost=0.00..95.06 rows=4599 width=0) (actual time=2.649..2.649 rows=35864 loops=1)
              Index Cond: ((tag)::text = 'tree'::text)
Planning time: 0.093 ms
Execution time: 187.032 ms
I think you have unnecessary steps in your query, consider this:

SELECT *
FROM (SELECT
        COUNT(tag) AS numtags,
        tweet_id,
        MIN(score)      AS minscore
      FROM  core_tagusage
            WHERE tag = 'dog'
                  OR tag = 'grass'
                  OR tag = 'frisbee'
      GROUP BY tweet_id) AS ct
WHERE numtags = 3
ORDER BY minscore DESC
LIMIT 200;


and this:

SELECT
    tweet_id,
    MIN(score) AS minscore
FROM  core_tagusage
WHERE tag IN ('dog', 'grass', 'frisbee')
GROUP BY tweet_id
WHERE COUNT(*) = 3
ORDER BY minscore DESC
LIMIT 200;


I also think that running analyze on your table will help the query planner.

After playing with some fabricated data locally, I was seeing ~600K rows take ~1sec, so 10 seconds doesn't seem unreasonable (but my data was so predictable that analyze made the query planner just go for a sequential scan)