PostgreSQL – Optimize Query to Find Top N Users Who Commented on a Post

greatest-n-per-groupoptimizationperformancepostgresqlpostgresql-performance

Problem

Trying to find the most efficient query to retrieve the top N (5 in the examples) users who have commented on a post, where a user is considered 'top' if they have the most followers. The query optimizer does not seem to be choosing the correct path.

Tables (Postgres v9.4.4)

user_account (40k records)

CREATE TABLE user_account (
  user_id TEXT PRIMARY KEY,
  name TEXT
);

following (13k records)

CREATE TABLE following (
  follower_user_id TEXT,
  followed_user_id TEXT,
  PRIMARY KEY (followed_user_id, follower_user_id)
);

follower_count_mv (10.5k records with only 5 users having > 1 follower)

CREATE MATERIALIZED VIEW follower_count_mv AS
SELECT followed_user_id AS user_id, COUNT(*)::int AS follower_count
FROM following
WHERE deleted_at IS NULL
GROUP BY user_id;

CREATE UNIQUE INDEX follower_count_mv_user_id_idx ON follower_count_mv (user_id);
CREATE INDEX follower_count_mv_follower_count_idx ON follower_count_mv (follower_count);

user_post_comment (13.4k records but the majority are on 3 posts)

CREATE TABLE user_post_comment (
  comment_id TEXT PRIMARY KEY,
  user_id TEXT,
  post_id TEXT
)
CREATE INDEX user_post_comment_user_id_idx ON user_post_comment (user_id);
CREATE INDEX user_post_comment_post_id_idx ON user_post_comment (post_id);

Queries I've tried

1) The most natural choice: join the tables and sort

SELECT user_account.*
FROM user_account
JOIN follower_count_mv ON (user_account.user_id = follower_count_mv.user_id)
JOIN user_post_comment ON (user_account.user_id = user_post_comment.user_id)
WHERE user_post_comment.post_id = '26c72242-7e3b-4982-92c5-021b622d7ecd'
ORDER BY follower_count DESC LIMIT 5;

This is what I originally had, but the query optimizer seems to have a hard time figuring out the best way to execute this. Something to do with the data distribution perhaps?

Limit  (cost=0.99..117.00 rows=5 width=580) (actual time=0.082..148.688 rows=2 loops=1)
  ->  Nested Loop  (cost=0.99..12136.14 rows=523 width=580) (actual time=0.081..148.687 rows=2 loops=1)
        ->  Nested Loop  (cost=0.57..6875.61 rows=1570 width=78) (actual time=0.049..148.624 rows=2 loops=1)
              ->  Index Scan Backward using follower_count_mv_follower_count_idx on follower_count_mv  (cost=0.29..383.25 rows=10483 width=41) (actual time=0.011..1.904 rows=10483 loops=1)
              ->  Index Scan using user_post_comment_user_id_idx on user_post_comment  (cost=0.29..0.61 rows=1 width=37) (actual time=0.014..0.014 rows=0 loops=10483)
                    Index Cond: ((user_id)::text = (follower_count_mv.user_id)::text)
                    Filter: ((post_id)::text = '26c72242-7e3b-4982-92c5-021b622d7ecd'::text)
                    Rows Removed by Filter: 0
        ->  Index Scan using user_account_pkey on user_account  (cost=0.41..3.34 rows=1 width=576) (actual time=0.029..0.030 rows=1 loops=2)
              Index Cond: ((user_id)::text = (follower_count_mv.user_id)::text)
Planning time: 4.172 ms
Execution time: 148.763 ms

It appears to loop 10483 times … why?

2) #1 without specifying a limit (apparently makes it faster…)

Sort  (cost=6406.46..6407.76 rows=523 width=580) (actual time=14.574..14.574 rows=2 loops=1)
  Sort Key: follower_count_mv.follower_count
  Sort Method: quicksort  Memory: 26kB
  ->  Nested Loop  (cost=799.36..6382.84 rows=523 width=580) (actual time=11.633..14.545 rows=2 loops=1)
        ->  Hash Join  (cost=798.95..1122.31 rows=1570 width=78) (actual time=11.590..14.469 rows=2 loops=1)
              Hash Cond: ((follower_count_mv.user_id)::text = (user_post_comment.user_id)::text)
              ->  Seq Scan on follower_count_mv  (cost=0.00..202.83 rows=10483 width=41) (actual time=0.005..1.168 rows=10483 loops=1)
              ->  Hash  (cost=773.89..773.89 rows=2005 width=37) (actual time=11.448..11.448 rows=2005 loops=1)
                    Buckets: 1024  Batches: 1  Memory Usage: 136kB
                    ->  Bitmap Heap Scan on user_post_comment  (cost=87.82..773.89 rows=2005 width=37) (actual time=1.211..11.040 rows=2005 loops=1)
                          Recheck Cond: ((post_id)::text = '26c72242-7e3b-4982-92c5-021b622d7ecd'::text)
                          Heap Blocks: exact=105
                          ->  Bitmap Index Scan on user_post_comment_post_id_idx  (cost=0.00..87.32 rows=2005 width=0) (actual time=1.196..1.196 rows=2005 loops=1)
                                Index Cond: ((post_id)::text = '26c72242-7e3b-4982-92c5-021b622d7ecd'::text)
        ->  Index Scan using user_account_pkey on user_account  (cost=0.41..3.34 rows=1 width=576) (actual time=0.034..0.035 rows=1 loops=2)
              Index Cond: ((user_id)::text = (follower_count_mv.user_id)::text)
Planning time: 1.935 ms
Execution time: 14.719 ms

3) The optimal (but messy) way (that I've been able to find)

SELECT user_account.*
FROM user_account
JOIN follower_count_mv ON (user_account.user_id = follower_count_mv.user_id)
JOIN user_post_comment ON (user_account.user_id = user_post_comment.user_id)
WHERE user_post_comment.post_id = '26c72242-7e3b-4982-92c5-021b622d7ecd'
AND user_account.user_id IN (SELECT user_id FROM follower_count_mv ORDER BY follower_count DESC LIMIT 5)
ORDER BY follower_count DESC LIMIT 5;

Using a subquery to calculate the top N user IDs first seems to force the optimizer to do a more efficient calculation.

Limit  (cost=44.87..44.88 rows=1 width=580) (actual time=0.588..0.588 rows=2 loops=1)
   ->  Sort  (cost=44.87..44.88 rows=1 width=580) (actual time=0.587..0.587 rows=2 loops=1)
         Sort Key: follower_count_mv.follower_count
         Sort Method: quicksort  Memory: 26kB
         ->  Nested Loop  (cost=1.52..44.86 rows=1 width=580) (actual time=0.358..0.571 rows=2 loops=1)
               ->  Nested Loop  (cost=1.23..44.47 rows=1 width=654) (actual time=0.116..0.405 rows=5 loops=1)
                     ->  Nested Loop  (cost=0.95..42.81 rows=5 width=613) (actual time=0.081..0.243 rows=5 loops=1)
                           ->  HashAggregate  (cost=0.53..0.58 rows=5 width=37) (actual time=0.028..0.030 rows=5 loops=1)
                                 Group Key: ("ANY_subquery".user_id)::text
                                 ->  Subquery Scan on "ANY_subquery"  (cost=0.29..0.52 rows=5 width=37) (actual time=0.014..0.019 rows=5 loops=1)
                                       ->  Limit  (cost=0.29..0.47 rows=5 width=41) (actual time=0.013..0.018 rows=5 loops=1)
                                             ->  Index Scan Backward using follower_count_mv_follower_count_idx on follower_count_mv follower_count_mv_1  (cost=0.29..383.25 rows=10483 width=41) (actual time=0.013..0.018 rows=5 loops=1)
                           ->  Index Scan using user_account_pkey on user_account  (cost=0.41..8.43 rows=1 width=576) (actual time=0.041..0.041 rows=1 loops=5)
                                 Index Cond: ((user_id)::text = ("ANY_subquery".user_id)::text)
                     ->  Index Scan using follower_count_mv_user_id_idx on follower_count_mv  (cost=0.29..0.32 rows=1 width=41) (actual time=0.030..0.030 rows=1 loops=5)
                           Index Cond: ((user_id)::text = (user_account.user_id)::text)
               ->  Index Scan using user_post_comment_idx on user_post_comment  (cost=0.29..0.39 rows=1 width=37) (actual time=0.031..0.032 rows=0 loops=5)
                     Index Cond: ((user_id)::text = (user_account.user_id)::text)
                     Filter: ((post_id)::text = '26c72242-7e3b-4982-92c5-021b622d7ecd'::text)
                     Rows Removed by Filter: 1
 Planning time: 2.035 ms
 Execution time: 0.785 ms

4) Add composite indexes and use subquery to get top 5 before joining

CREATE INDEX user_post_comment_post_id_user_id_idx ON user_post_comment (post_id, user_id);
CREATE INDEX follower_count_mv_user_id_follower_count_idx ON follower_count_mv (user_id, follower_count);

SELECT ua.*
FROM (
  SELECT user_id
  FROM user_post_comment pc
  JOIN follower_count_mv fc ON (pc.user_id = fc.user_id)
  WHERE post_id = '26c72242-7e3b-4982-92c5-021b622d7ecd'
  ORDER BY fc.follower_count DESC LIMIT 5
) sub
JOIN user_account ua ON (sub.user_id = ua.user_id)
JOIN follower_count_mv fc ON (sub.user_id = fc.user_id)
ORDER BY follower_count DESC LIMIT 5;

Limit  (cost=57.36..57.38 rows=5 width=579) (actual time=329.718..329.720 rows=2 loops=1)
  ->  Sort  (cost=57.36..57.38 rows=5 width=579) (actual time=329.717..329.717 rows=2 loops=1)
        Sort Key: fc.follower_count
        Sort Method: quicksort  Memory: 26kB
        ->  Nested Loop  (cost=1.40..57.31 rows=5 width=579) (actual time=0.118..329.709 rows=2 loops=1)
              Join Filter: ((pc.user_id)::text = (ua.user_id)::text)
              ->  Nested Loop  (cost=0.98..40.54 rows=5 width=78) (actual time=0.089..329.657 rows=2 loops=1)
                    ->  Limit  (cost=0.70..18.92 rows=5 width=41) (actual time=0.067..329.618 rows=2 loops=1)
                          ->  Nested Loop  (cost=0.70..5721.98 rows=1570 width=41) (actual time=0.067..329.617 rows=2 loops=1)
                                ->  Index Scan Backward using follower_count_mv_follower_count_idx on follower_count_mv fc_1  (cost=0.29..383.25 rows=10483 width=41) (actual time=0.015..1.872 rows=10483 loops=1)
                                ->  Index Only Scan using user_post_comment_post_id_user_id_idx on user_post_comment pc  (cost=0.41..0.50 rows=1 width=37) (actual time=0.031..0.031 rows=0 loops=10483)
                                      Index Cond: ((post_id = '26c72242-7e3b-4982-92c5-021b622d7ecd'::text) AND (user_id = (fc_1.user_id)::text))
                                      Heap Fetches: 0
                    ->  Index Only Scan using follower_count_mv_user_id_follower_count_idx on follower_count_mv fc  (cost=0.29..4.31 rows=1 width=41) (actual time=0.019..0.019 rows=1 loops=2)
                          Index Cond: (user_id = (pc.user_id)::text)
                          Heap Fetches: 0
              ->  Index Scan using user_account_pkey on user_account ua  (cost=0.41..3.34 rows=1 width=575) (actual time=0.023..0.024 rows=1 loops=2)
                    Index Cond: ((user_id)::text = (fc.user_id)::text)
Planning time: 3.007 ms
Execution time: 331.744 ms

The estimated time goes down, but the execution time doubled. I don't understand the reason for this…

Outstanding Questions

Why does #1 loop through the entire follower_count_mv table?
Why does removing LIMIT from #1 make the query optimizer choose a different query plan, where the estimated cost is higher, but the actual execution time is much much lower than #1?
Why is the query optimizer not smart enough to figure out it should do what query #3 does for query #1? Is the data distribution tripping it up?
If the database has a more normalized distribution of data, will query #1 perform the best? It's still not clear to me how the distribution affects the query plan.
What is the optimal query to use in this scenario, if not #3? #3 seems hacky to me; is there a way to make the query optimizer use the same plan as #2 for #1's query?

Best Answer

Better data types

text is a sub-optimal data type for key columns. It would be more efficient to use integer. Related:

Indexes: integer vs string performance if the number of nodes in the index is the same

'26c72242-7e3b-4982-92c5-021b622d7ecd' in your example looks like a UUID. If you need to use UUIDs, still don't store them as text. The appropriate data type would be uuid - much more efficient. Details:

Would index lookup be noticeably faster with char vs varchar when all values are 36 chars

Indexes

You only use single-column indexes. Since you need to optimize read performance for your query, add these two multicolumn indexes:

CREATE INDEX fc_mv_user_id_follower_count_idx ON follower_count_mv (user_id, follower_count DESC);
CREATE INDEX upc_post_id_user_id_idx ON user_post_comment (post_id, user_id);

@Ziggy already mentioned the second.
The order of index columns is important:

Is a composite index also good for queries on the first field?

Btree indexes can be scanned backwards at practically the same cost. But it's even slightly faster to use matching descending sort order. (There's a corner case with NULL values.)

Query

For a single post like in your examples it won't get faster than this:

SELECT ua.*
FROM  (
   SELECT user_id, fc.follower_count 
   FROM  (
      SELECT DISTINCT user_id
      FROM   user_post_comment
      WHERE  post_id = '26c72242-7e3b-4982-92c5-021b622d7ecd'
      ) pc
   JOIN   follower_count_mv fc USING (user_id)
   ORDER  BY fc.follower_count DESC
   LIMIT  5
   ) sub
JOIN   user_account ua USING (user_id)
ORDER  BY sub.follower_count DESC;

This is assuming that the same user can comment on the same post multiple times. It's cheapest to fold duplicates before joining to follower_count_mv.

And join to follower_count_mv directly. It's expensive and useless to use user_account as stepping stone.

Only join to user_account after reducing to the top 5.

You did not specify, but your queries have an outer ORDER BY follower_count DESC. I only include follower_count in the subquery for the outer sort.

If (post_id, user_id) is unique (users can only comment once on each post), simplify to:

SELECT ua.*
FROM  (
   SELECT user_id, fc.follower_count
   FROM   user_post_comment pc
   JOIN   follower_count_mv fc USING (user_id)
   WHERE  pc.post_id = '26c72242-7e3b-4982-92c5-021b622d7ecd'
   ORDER  BY fc.follower_count DESC
   LIMIT  5
   ) sub
JOIN   user_account ua USING (user_id)
ORDER  BY sub.follower_count DESC;

Getting the top N for multiple posts at once is a bit more complex. Detailed explanation in chapter 2a of this related answer:

Optimize GROUP BY query to retrieve latest record per user