How to speed up single-column date range query in Postgres?

Question

How would you speed up a Postgres query that's trying to filter on a date column between a start and end date?

I'm running a query like:

SELECT * FROM record WHERE tag_id IN (1,2,3) AND person_id = 1 AND created >= '2022-1-1' AND created < '2022-6-1'
ORDER BY priority DESC LIMIT 100;

on a table with millions of rows. However, only a few thousand rows should apply to my query, and I have a couple indexes that should cover the criteria exactly, like:

CREATE INDEX record_tag_priority_person_index
ON public.record USING btree
(tag_id ASC NULLS LAST, priority DESC NULLS LAST, person_id ASC NULLS LAST)
WHERE (tag_id = ANY (ARRAY[1, 2, 3])) AND person_id = 1;

CREATE INDEX record_created_index
ON public.record USING btree
(created ASC NULLS LAST);

Yet even with these indexes the query still takes ~18 minutes to run.

If I run an EXPLAIN on my query, it shows:

"Limit  (cost=155990.12..155990.37 rows=100 width=165) (actual time=1104683.783..1104683.799 rows=100 loops=1)"
"  ->  Sort  (cost=155990.12..156078.05 rows=35170 width=165) (actual time=1104683.782..1104683.789 rows=100 loops=1)"
"        Sort Key: priority DESC"
"        Sort Method: top-N heapsort  Memory: 58kB"
"        ->  Bitmap Heap Scan on record  (cost=27359.52..154645.95 rows=35170 width=165) (actual time=556.641..1104569.771 rows=32804 loops=1)"
"              Recheck Cond: ((created >= '2022-01-01 04:00:00+00'::timestamp with time zone) AND (created < '2022-6-1 04:00:00+00'::timestamp with time zone) AND (tag_id = ANY ('{1,2,3}'::integer[])) AND (person_id = 1))"
"              Rows Removed by Index Recheck: 1103447"
"              Heap Blocks: exact=35800 lossy=99400"
"              ->  BitmapAnd  (cost=27359.47..27359.47 rows=35170 width=0) (actual time=547.819..547.821 rows=0 loops=1)"
"                    ->  Bitmap Index Scan on record_created_index  (cost=0.00..8666.93 rows=409449 width=0) (actual time=244.146..244.146 rows=309261 loops=1)"
"                          Index Cond: ((created >= '2022-01-01 04:00:00+00'::timestamp with time zone) AND (created < '2022-6-1 04:00:00+00'::timestamp with time zone))"
"                    ->  Bitmap Index Scan on record_tag_priority_person_index  (cost=0.00..18674.71 rows=2043655 width=0) (actual time=293.201..293.202 rows=2029783 loops=1)"
"Planning Time: 118.456 ms"
"Execution Time: 1104683.854 ms"

So it's using both of my indexes, but it's still taking forever to find the first 100 results.

How do I speed this up? Are my indexes inefficient?

I tried combining the two indexes into one partial index like:

CREATE INDEX record_tag_priority_person_created_index
ON public.record USING btree
(tag_id ASC NULLS LAST, priority DESC NULLS LAST, person_id ASC NULLS LAST, created DESC)
WHERE (tag_id = ANY (ARRAY[1, 2, 3])) AND person_id = 1;

but the planner doesn't pick it up and continues to use the two separate indexes.

Answer 1

Generally, filtering by one column, sorting by another, combined with a small LIMIT is a tough nut to crack.

The run time still seems excessive, even for your poorly fitting indexes.

More work_mem

One issue is revealed by this:

Heap Blocks: exact=35800 lossy=99400"

Meaning, Postgres did not have enough work_mem to store row identifiers for identified data pages. Your query would benefit a lot from more work_mem. See:

• "Recheck Cond:" line in query plans with a bitmap index scan

Better index

Depending on how selective this filter is:

AND created >= '2022-1-1' AND created < '2022-6-1'

If it's not very selective, i.e. a large percentage of indexed rows (of those passing the index filter) qualify, then this should serve well:

CREATE INDEX record_priority_part_idx ON public.record (priority DESC)
WHERE tag_id = ANY ('{1,2,3}'::int[]) AND person_id = 1;

Postgres can walk the index in sort order in a plain index scan and filter the (relatively few) non-matches until the small LIMIT 100 is satisfied.

Using priority DESC to match your query. If you really want priority DESC NULLS LAST use that in both query and index.

Else:

CREATE INDEX record_created_part_idx ON public.record (created)
WHERE tag_id = ANY ('{1,2,3}'::int[]) AND person_id = 1;

The point is to have the remaining filter column created as leading index expression.

If very few rows match the filter, it may be faster to run an index scan, then sort the few qualifying rows. This small index on just (created) will be fast for this.

Be sure to run ANALYZE after creating either index. Postgres will gather statistics for the partial index.

With the tighter fitting index, and updated statistics, you may not have to increase work_mem for this query.

With more sophistication you can do even better. Especially if the timestamptz filter falls in between (neither very selective, nor hardly selective). See:

• Can spatial index help a "range - order by - limit" query

Aside

The query plan also reveals that created is type timestamptz. So this is not a safe way to provide bounds:

AND created >= '2022-1-1' AND created < '2022-6-1'

The current time zone setting is assumed. Seems to be UTC in your case. Running the same query with a different timezone setting can return different results. Provide unambiguous timestamptz constants (with time offset or an explicit time zone) to be safe.

Answer 2

Based on your EXPLAIN PLAN, the bitmap must have found at least 35800+99400 rows in the index, but when it got to the table there were only 32804 visible rows meeting the criteria. The only way I can think of that would make this happen in this scenario is if your indexes are bloated with dead rows. Try vacuuming the table to take care of that. Btree indexes have a feature called "killed tuples" or "microvacuuming" where using the index will cause it to mark dead tuples in the table as also dead in the index, but bitmap scans do not implement this feature (but do benefit from other queries having done it). (Also, hot-standbys ignore those markings and so can't benefit from this feature at all.) If your indexes are only used for bitmap scans, they will get bloated more easily than ones also occasionally used for plain index scans.

Your partial index won't work the way you apparently think it will. First, your ordering decoration on "priority" is wrong, you define it DESC NULLS LAST, but your query is DESC NULLS FIRST (the NULLS FIRST being understand as implicit for DESC). The planner could plausibly do a better job of dealing with such mismatches, but it doesn't. It just won't use that part of that index for ordering.

Even if it weren't for that mismatch, it still wouldn't use it for ordering, because an IN-list on a preceding column makes it not use a following column for ordering. (The exception is if the planner realizes the IN-list can only have one value, and so converts to simple equality). Again, it is plausible PostgreSQL could do a better job here (using something like multiple index scans with a "merge append" between them) but no one has implemented that. Since the entire benefit of tag_id has already been had in the WHERE clause, there is only downside in including that column in the index (for this particular query)

And even if not for those two things, it still might not use it for ordering, as bitmap scans inherently don't preserve order. So it has to choose, use "priority" for ordering with an ordinary btree scan and need to filter on "created", or use the "created" index and forgo ordering on "priority".

Finally, your hardware doesn't seem very good. It looks like you are getting about 8ms per buffer (assuming none of them were in cache), which is what you would expect from a single low-end hard drive. Faster storage, or more RAM for caching disk pages in memory, could both give you big improvements.