0

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.

3
  • 1
    Have you tried putting Priority as your first column in Index and others in the same sequence? You are using Priority in order by clause and that seems to be challenging. Try both ways - meaning, try the query without order by, just take limit 100 or create index as mentioned above and try with order by. Nov 2, 2022 at 5:18
  • You know the drill: please always disclose the Postgres version in use. Table definition, and data distribution for crucial columns would help, too. Nov 2, 2022 at 5:52
  • Including tag_id in the index is counterproductive here, especially as the first column. The WHERE clause already filtered out the non-qualifying tag_id. There is no need to filter them out again, and including it there makes the index less efficient for use on other columns.
    – jjanes
    Nov 2, 2022 at 14:15

2 Answers 2

3

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:

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:

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.

3
  • While increasing work_mem is a good idea, I very much doubt it is the main issue. I am assuming the main bottleneck here is reading the table pages from disk, and even if all of those lossy pages were converted to exact pages, they still all need to be read from disk.
    – jjanes
    Nov 2, 2022 at 14:35
  • @jjanes: I agree, not the main issue. Nov 2, 2022 at 14:42
  • 1
    Thank you. Your first "better index" suggestion, the partial index keyed on priority, completely fixed the issue.
    – Cerin
    Nov 2, 2022 at 14:48
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.