Re: Reducing planning time of large IN queries on primary key / unique columns - Mailing list pgsql-hackers

At ServiceNow, we frequently encounter queries with very large IN lists where the number of elements in the IN list range from a 

few hundred to several thousand. For a significant fraction of the queries, the IN clauses are constructed on primary key columns. 

While planning these queries, Postgres query planner loops over every element in the IN clause, computing the selectivity of each 

element and then uses that as an input to compute the total selectivity of the IN clause. For IN clauses on primary key or unique 

columns, it is easy to see that the selectivity of the IN predicate is given by (number of elements in the IN clause / table cardinality)

and is independent of the selectivity of the individual elements. We use this observation to avoid computing the selectivities of the

individual elements. This results in an improvement in the planning time especially when the number of elements in the IN clause 

is relatively large. 

The table below demonstrates the improvement in planning time (averaged over 3 runs) for IN queries of the form 

SELECT COUNT(*) FROM table_a WHERE sys_id IN ('000356e61b568510eabcca2b234bcb08', '00035846db2f24101ad7f256b9961925', ...). 

Here sys_id is the primary key column of type VARCHAR(32) and the table cardinality of table_a is around 10M.

Number of IN list elements | Planning time w/o optimization (in ms) | Planning time w/ optimization (in ms) | Speedup

------------------------------------|---------------------------------------------------  | --------------------------------------------------|--------------

500                                     | 0.371                                                     | 0.236                                                   | 1.57

5000                                   | 2.019                                                     | 0.874                                                   | 2.31

50000                                 | 19.886                                                   | 8.273                                                   | 2.40

Similar to IN clauses, the selectivity of NOT IN clauses on a primary key or unique column can be computed by not computing the 

selectivities of individual elements. The query used is of the form SELECT COUNT(*) FROM table_a WHERE sys_id NOT IN 

('000356e61b568510eabcca2b234bcb08', '00035846db2f24101ad7f256b9961925', ...).

Number of NOT IN list elements | Planning time w/o optimization (in ms) | Planning time w/ optimization (in ms) | Speedup

-------------------------------------------|---------------------------------------------------  | --------------------------------------------------|--------------

500                                              | 0.380                                                     | 0.248                                                   | 1.53

5000                                            | 2.534                                                     | 0.854                                                   | 2.97

50000                                          | 21.316                                                   | 9.009                                                   | 2.36

We also obtain planning time of queries on a primary key column of type INTEGER with 10M elements for both IN and NOT in queries.

Number of IN list elements | Planning time w/o optimization (in ms) | Planning time w/ optimization (in ms) | Speedup

------------------------------------|---------------------------------------------------  | --------------------------------------------------|--------------

500                                     | 0.370                                                     | 0.208                                                   | 1.78

5000                                   | 1.998                                                     | 0.816                                                   | 2.45

50000                                 | 18.073                                                   | 6.750                                                   | 2.67

Number of NOT IN list elements | Planning time w/o optimization (in ms) | Planning time w/ optimization (in ms) | Speedup

-------------------------------------------|---------------------------------------------------  | --------------------------------------------------|--------------

500                                              | 0.342                                                     | 0.203                                                   | 1.68

5000                                            | 2.073                                                     | 0.822                                                   | 3.29

50000                                          |19.551                                                   | 6.738                                                   | 2.90

We see that the planning time of queries on unique columns are identical to that we observed for primary key columns. 

The resulting patch file for the changes above is small and we are happy to polish it up and share.

Best,

Souvik Bhattacherjee

(ServiceNow)