I have a pretty simple table
CREATE TABLE approved_posts (
project_id INTEGER,
feed_id INTEGER,
post_id INTEGER,
approved_time TIMESTAMP NOT NULL,
post_time TIMESTAMP NOT NULL,
PRIMARY KEY (project_id, feed_id, post_id)
)
And I'm trying to optimize this query:
SELECT *
FROM approved_posts
WHERE feed_id IN (?, ?, ?)
AND project_id = ?
ORDER BY approved_time DESC, post_time DESC
LIMIT 1;
The query optimizer is fetching every single approved_post
that matches the predicate, sorting all 100k results, and returning the top one it finds.
I do have an index on project_id, feed_id, approved_time, post_time
, which it will use if I either:
A. remove the sort by post_time
, or
B. replace the IN (?, ?, ?)
with a single = ?
.
Then it simply does a reverse index scan to get the first result and its blazingly fast.
Option A:
Limit (cost=0.43..6.57 rows=1 width=24) (actual time=0.101..0.101 rows=1 loops=1)
-> Index Scan Backward using approved_posts_approved_time_idx on approved_posts p (cost=0.43..840483.02 rows=136940 width=24) (actual time=0.100..0.100 rows=1 loops=1)
Filter: (feed_id = ANY ('{73321,73771,73772,73773,73774}'::integer[]))
Rows Removed by Filter: 37
Total runtime: 0.129 ms
Option B:
Limit (cost=0.43..3.31 rows=1 width=24) (actual time=0.065..0.065 rows=1 loops=1)
-> Index Scan Backward using approved_posts_full_pagination_index on approved_posts p (cost=0.43..126884.70 rows=44049 width=24) (actual time=0.063..0.063 rows=1 loops=1)
Index Cond: ((project_id = 148772) AND (feed_id = 73321))
Total runtime: 0.092 ms
But without these tweaks it is not so performant ...
Limit (cost=169792.16..169792.17 rows=1 width=24) (actual time=510.225..510.225 rows=1 loops=1)
-> Sort (cost=169792.16..170118.06 rows=130357 width=24) (actual time=510.224..510.224 rows=1 loops=1)
Sort Key: approved_time, post_time
Sort Method: top-N heapsort Memory: 25kB
-> Bitmap Heap Scan on approved_posts p (cost=12324.41..169140.38 rows=130357 width=24) (actual time=362.210..469.387 rows=126260 loops=1)
Recheck Cond: (feed_id = ANY ('{73321,73771,73772,73773,73774}'::integer[]))
-> Bitmap Index Scan on approved_posts_feed_id_idx (cost=0.00..12291.82 rows=130357 width=0) (actual time=354.496..354.496 rows=126260 loops=1)
Index Cond: (feed_id = ANY ('{73321,73771,73772,73773,73774}'::integer[]))
Total runtime: 510.265 ms
I can even add a conditional index on these 5 feed ids and it will once again do the right thing.
My current best solution is to put every feed_id
in its own query and do a massive UNION
between them all. But this doesn't scale very well as I might want to select the top 500 from 30 feeds, pulling in 15k rows and sorting them for no good reason. Also managing offsets with this strategy is somewhat complex.
Does anybody know how I can do this IN
clause with two sorts on my well-indexed data and get Postgres to do the right thing?
I'm using Postgres 9.3.3. Here are my indexes:
"approved_posts_project_id_feed_id_post_id_key" UNIQUE CONSTRAINT, btree (project_id, feed_id, post_id)
"approved_posts_approved_time_idx" btree (approved_time)
"approved_posts_feed_id_idx" btree (feed_id)
"approved_posts_full_pagination_index" btree (project_id, feed_id, approved_time, post_time)
"approved_posts_post_id_idx" btree (post_id)
"approved_posts_post_time_idx" btree (post_time)
"approved_posts_project_id_idx" btree (project_id)
None of the columns are nullable.
This table has 2m rows, split among 200 feed IDs and 19 project IDs.
These are the most common feed IDs:
feed_id | count
---------+--------
73607 | 558860
73837 | 354018
73832 | 220285
73836 | 172664
73321 | 118695
73819 | 95999
73821 | 75871
73056 | 65779
73070 | 54655
73827 | 43710
73079 | 36700
73574 | 36111
73055 | 25682
73072 | 22596
73589 | 19856
73953 | 15286
73159 | 13059
73839 | 8925
In terms of min/max/avg cardinality per feedid
/projectid
pairing, we have:
min | max | avg
-----+--------+-----------------------
1 | 559021 | 9427.9140271493212670
With a list of possible values for
feed_id
, Postgres has a hard time to find the best query plan. Eachfeed_id
could be associated with 1 - 559021 rows (according to your numbers). Postgres is not currently smart enough to see the potential optimization for the special case ofLIMIT 1
on its own. AUNION ALL
(not justUNION
) of several queries with onefeed_id
andLIMIT 1
each, plus another outerLIMIT 1
(like you seem to have tried) demonstrates the potential, but requires sophisticated query concatenation for a variable number of input values.There is another way to convince the query planner it can use index scans to pick the first row from the index for each
feed_id
: rewrite your query with aLATERAL
join:Or, more convenient for a variable number of values for
feed_id
:Pass an integer array for the variable, like
'{123, 234, 345}'::int[]
. This could also be implemented elegantly with a function using aVARIADIC
parameter. Then you can pass a list ofinteger
values:Your index on
(project_id, feed_id, approved_time, post_time)
works for this since Postgres can scan indexes backwards almost as fast as forwards, but(project_id, feed_id, approved_time DESC, post_time DESC)
would be even better. See:If you don't need to return all columns of the table, even index-only scans might be an option.
Your columns
approved_time
,post_time
are definedNOT NULL
. Else, you have to do more:Related answer detailing the
LATERAL
join technique:Why did your option A work?
A closer look reveals two things:
Bold emphasis mine.
(approved_time)
is used.feed_id
(which would not be possible in this case), but a Filter.Postgres chooses a completely different strategy: it reads rows from this index bottom-up (
Index Scan Backward
) until it finds a row matching one of your given values forfeed_id
. Since you only have very few projects and feeds (200 feed IDs and 19 project IDs
), chances are it won't have to discard too many rows before the first match - which is the result. This actually gets faster with more values forfeed_id
, because the "latest" row is found earlier - unlike my first approach which is faster for fewer values.A promising alternative strategy! Depending on data distribution and the feeds in your query it may be faster than my first solution - enable it with this index:
It may pay to selectively increase the statistics targets for the columns
project_id
andfeed_id
so the tipping point between both strategies can be estimated more accurately.Since you have projects with only old rows (as per comment), you might improve this query with a hint as to the maximum
approved_time
(andpost_time
, but that's probably not adding much) - if you know the maximumapproved_time
per project (and / or perfeed_id
), or at least an upper bound.