Slow query when adding additional where clause

Question

Here's my setup (Postgres 9.3)

Posts

• project_id

Messages

• post_id
• kind
• updated_at

I'm trying to get the most recently updated 100 messages that belong to posts (on a specific project) that are a specific kind. My query looks like:

SELECT "messages".* FROM "messages" 
INNER JOIN "posts" ON "posts"."id" = "messages"."post_id" 
WHERE "posts"."project_id" = '418fdd03-ab90-4efd-b04d-5d5563d58972' AND "messages"."kind" IN (10, 11, 12) 
ORDER BY updated_at DESC LIMIT 100 OFFSET 0;

Limit  (cost=0.17..2372.06 rows=100 width=648) (actual time=17.731..308.603 rows=100 loops=1)
 ->  Nested Loop  (cost=0.17..44164.77 rows=1862 width=648) (actual time=17.730..308.559 rows=100 loops=1)
       ->  Index Scan Backward using index_messages_on_updated_at on messages  (cost=0.08..20924.10 rows=151337 width=648) (actual time=0.034..93.817 rows=83481 loops=1)
             Filter: (kind = ANY ('{10,11,12}'::integer[]))
             Rows Removed by Filter: 130238
       ->  Index Scan using posts_pkey on posts  (cost=0.08..0.15 rows=1 width=16) (actual time=0.002..0.002 rows=0 loops=83481)
             Index Cond: (id = messages.post_id)
             Filter: (project_id = '418fdd03-ab90-4efd-b04d-5d5563d58972'::uuid)
             Rows Removed by Filter: 1
Total runtime: 308.660 ms

If I run without the kind clause:

SELECT "messages".* FROM "messages" 
INNER JOIN "posts" ON "posts"."id" = "messages"."post_id" 
WHERE "posts"."project_id" = '418fdd03-ab90-4efd-b04d-5d5563d58972' 
ORDER BY updated_at DESC LIMIT 100 OFFSET 0;

Limit  (cost=0.17..1320.02 rows=100 width=648) (actual time=0.501..23.613 rows=100 loops=1)
 ->  Nested Loop  (cost=0.17..69371.34 rows=5256 width=648) (actual time=0.500..23.583 rows=100 loops=1)
       ->  Index Scan Backward using index_messages_on_updated_at on messages  (cost=0.08..20603.62 rows=427305 width=648) (actual time=0.010..3.256 rows=7893 loops=1)
       ->  Index Scan using posts_pkey on posts  (cost=0.08..0.11 rows=1 width=16) (actual time=0.002..0.002 rows=0 loops=7893)
             Index Cond: (id = messages.post_id)
             Filter: (project_id = '418fdd03-ab90-4efd-b04d-5d5563d58972'::uuid)
             Rows Removed by Filter: 1
Total runtime: 23.667 ms

I think the main slowdown is that the majority of the rows are not of the kind I'm looking for. I tried adding a partial index on kind, but that didn't have any effect.

CREATE INDEX index_messages_on_kind ON messages USING btree (kind) WHERE (kind = ANY (ARRAY[10, 11, 12]));

Any ideas to speed this query up?

Edit:

Indexes that currently exist:

Posts

• index on project_id and updated_at

Messages

• indexes on post_id, updated_at and partial index on kind IN (10, 11, 12)

Answer 1

@Joishi already provided an explanation for what you saw.

Here is a solution to make it fast.

Your query (unchanged) after trimming some noise:

SELECT m.*
FROM   posts    p
JOIN   messages m ON m.post_id = p.id
WHERE  p.project_id = '418fdd03-ab90-4efd-b04d-5d5563d58972'
AND    m.kind = ANY ('{10,11,12}')
ORDER  BY m.updated_at DESC
LIMIT  100
OFFSET 0;

1. Multicolumn index on posts

This is only a minor improvement and not strictly necessary. Should give you an Index Only Scan instead of an Index Scan. Saves the lookup on the heap (the table)

 CREATE UNIQUE INDEX index_posts ON posts (project_id, id);

UNIQUE is also not necessary, but it better documents that the index is, in fact, unique.

2. Partial multicolumn index on messages done right

This is the major part.

• Use the same predicate in the partial index and in the query. Postgres only applies very rudimentary tests to determine whether an partial index is applicable. Else, the cost would get out of hand quickly.
  _{Since kind IN (10, 11, 12) is rewritten to kind = ANY ('{10,11,12}'::integer[]) internally, it should still work in this case, but it's better to be clear.}

• It would be useless to make kind the indexed column here. It's only relevant in the predicate, not as column to retrieve from the index. You need an equality check on post_id (so it comes first) and a range check on updated_at (so it comes after that). Details:

  • Multicolumn index and performance

  DESC is not strictly necessary, but still better here.

-- DROP INDEX index_messages_on_kind;
CREATE INDEX index_messages_on_kind ON messages (post_id, updated_at DESC)
WHERE kind = ANY ('{10,11,12}');

Then run ANALYZE on both tables and try EXPLAIN ANALYZE again. Are we fast, yet?

Answer 2

TL;DR - Try removing the LIMIT and see which one performs better.

Based off what you have pasted ... It appears that, because you are using a LIMIT on each .. the second query will run faster because it only has to apply one filter (project_id = '') while the second has to apply two filters (project_id = '' and kind = '').

As a result of using limit, it takes less TIME to just spit out the first 100 results where the kind doesn't matter .... it takes more TIME to spit out 100 results where the kind DOES matter..

If you remove the LIMIT, I'm sure you'll see that, ignoring time for the query to run, the query with two filters will most likely return less rows (which, I'm guessing, will cause it to take less time overall ... but that really depends on what indexes exist. Based off of your pasted explains, though, it looks like you have appropriate indexes).

If you remove the LIMIT, I -believe- you'll still see two index scans for the two-filter query .. but one index scan and one sequential scan on the query with only one filter.

Answer 3

For anyone curious, here is the updated query plan incorporating the changes suggested by Erwin

   Limit  (cost=131.47..131.48 rows=15 width=648) (actual time=2.816..2.880 rows=100 loops=1)
     ->  Sort  (cost=131.47..131.48 rows=15 width=648) (actual time=2.815..2.835 rows=100 loops=1)
           Sort Key: messages.updated_at
           Sort Method: quicksort  Memory: 99kB
           ->  Nested Loop  (cost=2.17..131.41 rows=15 width=648) (actual time=0.122..2.591 rows=144 loops=1)
                 ->  Index Scan using index_posts_on_project_id on posts  (cost=0.08..34.14 rows=16 width=16) (actual time=0.050..0.083 rows=35 loops=1)
                       Index Cond: (project_id = '418fdd03-ab90-4efd-b04d-5d5563d58972'::uuid)
                 ->  Bitmap Heap Scan on messages  (cost=2.09..6.07 rows=2 width=648) (actual time=0.063..0.067 rows=4 loops=35)
                       Recheck Cond: ((post_id = posts.id) AND (kind = ANY ('{10,11,12}'::integer[])))
                       ->  Bitmap Index Scan on index_messages_on_post_id_and_updated_at  (cost=0.00..2.09 rows=2 width=0) (actual time=0.061..0.061 rows=4 loops=35)
                             Index Cond: (post_id = posts.id)
   Total runtime: 2.980 ms