Postgresql 10 query with large(?) IN lists in filters

Question

I am working on a relatively simple query:

SELECT row.id, row.name FROM things AS row 
WHERE row.type IN ( 
'00000000-0000-0000-0000-000000031201',
...
 )
ORDER BY row.name ASC, row.id ASC 
LIMIT 2000;

The problem:

the query is fine if the list contains 25 or less UUIDs:

 Limit  (cost=21530.51..21760.51 rows=2000 width=55) (actual time=5.057..7.780 rows=806 loops=1)
   ->  Gather Merge  (cost=21530.51..36388.05 rows=129196 width=55) (actual time=5.055..6.751 rows=806 loops=1)
         Workers Planned: 1
         Workers Launched: 1
         ->  Sort  (cost=20530.50..20853.49 rows=129196 width=55) (actual time=2.273..2.546 rows=403 loops=2)
               Sort Key: name, id
               Sort Method: quicksort  Memory: 119kB
               ->  Parallel Index Only Scan using idx_things_type_name_id on things row  (cost=0.69..9562.28 rows=129196 width=55) (actual time=0.065..0.840 rows=403 loops=2)
                     Index Cond: (type = ANY ('{00000000-0000-0000-0000-000000031201,... (< 24 more)}'::text[]))
                     Heap Fetches: 0
 Planning time: 0.202 ms
 Execution time: 8.485 ms

but once the list grows larger than 25 elements a different index is used and the query execution time really goes up:

 Limit  (cost=1000.58..15740.63 rows=2000 width=55) (actual time=11.553..29789.670 rows=952 loops=1)
   ->  Gather Merge  (cost=1000.58..2400621.01 rows=325592 width=55) (actual time=11.551..29855.053 rows=952 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         ->  Parallel Index Scan using idx_things_name_id on things row  (cost=0.56..2362039.59 rows=135663 width=55) (actual time=3.570..24437.039 rows=317 loops=3)
               Filter: ((type)::text = ANY ('{00000000-0000-0000-0000-000000031201,... (> 24 more)}'::text[]))
               Rows Removed by Filter: 5478258
 Planning time: 0.209 ms
 Execution time: 29857.454 ms

Details:

The table contains 16435726 rows, 17 columns. The 3 columns relevant to the query are:

id - varchar(36), not null, unique, primary key
type - varchar(36), foreign key
name - varchar(2000)

The relevant indexes are:

create unique index idx_things_pkey on things (id);
create index idx_things_type on things (type);
create index idx_things_name_id on things (name, id);
create index idx_things_type_name_id on things (type, name, id);

there are 70 different type values of which 2 account for ~15 million rows. Those two are NOT in the IN list.

Experiments and questions:

I started by checking if this index helps:

create index idx_things_name_id_type ON things (name, id, type);

it did but slightly. 12s is not acceptable:

 Limit  (cost=1000.71..7638.73 rows=2000 width=55) (actual time=5.888..12120.907 rows=952 loops=1)
   ->  Gather Merge  (cost=1000.71..963238.21 rows=289917 width=55) (actual time=5.886..12154.580 rows=952 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         ->  Parallel Index Only Scan using idx_things_name_id_type on things row  (cost=0.69..928774.57 rows=120799 width=55) (actual time=1.024..9852.923 rows=317 loops=3)
               Filter: ((type)::text = ANY ('{00000000-0000-0000-0000-000000031201,... 37 more}'::text[]))
               Rows Removed by Filter: 5478258
               Heap Fetches: 0
 Planning time: 0.638 ms
 Execution time: 12156.817 ms

I know that large IN lists are not efficient in Postgres but I was surprised to hit this as soon as 25 elements. Or is the issue here something else?

I tried the solutions suggested in other posts (to inner join to a VALUES list, too change IN to IN VALUES, ...) but it made things even worse. Here is an example of one if the experiments:

SELECT row.id, row.name
FROM things AS row 
WHERE row.type IN (VALUES ('00000000-0000-0000-0000-000000031201'), ... )
ORDER BY row.name ASC, row.id ASC 
LIMIT 2000;

 Limit  (cost=0.56..1254.91 rows=2000 width=55) (actual time=45.718..847919.632 rows=952 loops=1)
   ->  Nested Loop Semi Join  (cost=0.56..10298994.72 rows=16421232 width=55) (actual time=45.714..847917.788 rows=952 loops=1)
         Join Filter: ((row.type)::text = "*VALUES*".column1)
         Rows Removed by Join Filter: 542360414
         ->  Index Scan using idx_things_name_id on things row  (cost=0.56..2170484.38 rows=16421232 width=92) (actual time=0.132..61387.582 rows=16435726 loops=1)
         ->  Materialize  (cost=0.00..0.58 rows=33 width=32) (actual time=0.001..0.022 rows=33 loops=16435726)
               ->  Values Scan on "*VALUES*"  (cost=0.00..0.41 rows=33 width=32) (actual time=0.004..0.030 rows=33 loops=1)
 Planning time: 1.131 ms
 Execution time: 847920.680 ms
(9 rows)

Query plan from inner join values():

 Limit  (cost=0.56..1254.91 rows=2000 width=55) (actual time=38.289..847714.160 rows=952 loops=1)
   ->  Nested Loop  (cost=0.56..10298994.72 rows=16421232 width=55) (actual time=38.287..847712.333 rows=952 loops=1)
         Join Filter: ((row.type)::text = "*VALUES*".column1)
         Rows Removed by Join Filter: 542378006
         ->  Index Scan using idx_things_name_id on things row  (cost=0.56..2170484.38 rows=16421232 width=92) (actual time=0.019..60303.676 rows=16435726 loops=1)
         ->  Materialize  (cost=0.00..0.58 rows=33 width=32) (actual time=0.001..0.022 rows=33 loops=16435726)
               ->  Values Scan on "*VALUES*"  (cost=0.00..0.41 rows=33 width=32) (actual time=0.002..0.029 rows=33 loops=1)
 Planning time: 0.247 ms
 Execution time: 847715.215 ms
(9 rows)

Am I doing something incorrectly here?

Any tips on how to handle this? If any more info is needed I will add it as you guys ask.

ps. The column/table/index names were "anonymised" to comply with the company policy so please do not point to the stupid names :)

user_13602007 · Answer

I actually figured out what is going on. Postgres planner is correct in its decision. But it makes it basing on not perfect statistical data. The key are those lines of the query plans:

Below 25 UUIDs:

->  Gather Merge  (cost=21530.51..36388.05 **rows=129196** width=55) 
(actual time=5.055..6.751 **rows=806** loops=1)

Overestimated by ~160 times

Over 25 UUIDs:

->  Gather Merge  (cost=1000.58..2400621.01 **rows=325592** width=55) 
(actual time=11.551..29855.053 **rows=952** loops=1)

overestimated by ~342(!) times

If this would indeed be 325592 than using the index on (type, id) which already is sorted as needed and filtering from it could be the most efficient. But because the overestimation Postgres needs to remove over 5M rows to fetch the full result:

**Rows Removed by Filter: 5478258**

I guess Postgres figures out that sorting 325592 rows (query > 25 UUIDs) will be so expensive that it is more beneficial to use the already sorted index vs sorting of 129196 rows (query <25 UUIDs) which it can sort in memory.

I took a peek into pg_stats and the statistics were quite unhelpful.

This is because just a few types that are not present in the query occur so often and the UUIDs that do occur fall into the histogram and are overestimated.

Increasing the statistics target for this column:

ALTER TABLE things ALTER COLUMN type SET STATISTICS 1000;

Solved the issue.

Now the query executes in 8ms also for UUIDs lists with more than 25 elements.

UPDATE: Because of claims that the :text cast visible in the query plan is the culprit I went to the test server and run:

ALTER TABLE things ALTER COLUMN type TYPE text;

no there is no cast but nothing has changed:

`Limit  (cost=1000.58..20590.31 rows=2000 width=55) (actual time=12.761..30611.878 rows=952 loops=1)
   ->  Gather Merge  (cost=1000.58..2386715.56 rows=243568 width=55) (actual time=12.759..30682.784 rows=952 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         ->  Parallel Index Scan using idx_things_name_id on things row  (cost=0.56..2357601.74 rows=101487 width=55) (actual time=3.994..24190.693 rows=317 loops=3)
               Filter: (type = ANY ('{00000000-0000-0000-0000-000000031201,... (> 24 more)}'::text[]))
               Rows Removed by Filter: 5478258
 Planning time: 0.227 ms
 Execution time: 30685.092 ms
(9 rows)`

user_12121627 · Answer

This is related with how the PostgreSQL choose to use or not the subquery JOIN.

The query optimizer is free to try to decide how he acts (if uses or not indexes) by some internal rules and statistical behaviors and try to do the cheapest costs.

But, sometimes, this decision could not be the best. You can "force" your optimizer to use joins changing the join_collapse_limit.

You can try using SET join_collapse_limit = 1 and then execute your query to "force" to use the indexes.

Remember to put this option on session, normally the query optimizer has right on decisions.

Is an option that worked for me for subqueries, maybe a try inside a IN will also helps to force your query to use the indexes.

user_905902 · Answer

there are 70 different type values of which 2 account for ~15 million rows. Those two are NOT in the IN list

And you address this domain using a 36 character key. That is 36*8 bits of space, where only 7 bits are needed.

put these 70 different types in a separate LookUpTable, containing a surrogate key
the original type field could have a UNIQUE constraint in this table
refer to this table, using its surrogate id as a Foreign Key
... and: probably similar for the other obese keys

Postgresql 10 query with large(?) IN lists in filters

3 Answers