How to optimally do Postgres `IN (...set...)` query with a large set of values

Question

I have a table with millions of rows, and I want to find all rows that have any one of a supplied list of a few thousand values in a specific column. Bascially I want to run an IN(...set...) query, which is internally rewritten to an = ANY(...array...) construct, with an array size of thousands, against an indexed column with millions of rows.

My questions are:

1. Is there a limit to the size of a set or an array in this query type?
2. How does this query type scale? I assume the array is not indexed, so presumably each array value hits the index, giving scaling of O(n log N), for n array values, and N table rows?
3. How much of a hit on query throughput would it be to submit these sorts of large queries, among a stream of simpler queries? In other words, would it be good to break this down to a few dozen separate queries, with say 100 array values in each, in order to allow the work of this query to be interleaved with other queries?

Answer 1

I made a small benchmark.

Source code on pastebin

Test table: 10M rows with (id INT PRIMARY KEY, s TEXT).

Results:

   0.055ms      1 rows Correlated SELECT * FROM test_array WHERE id =ANY(A
   0.042ms      1 rows Correlated SELECT * FROM test_array WHERE id IN (1)
   0.070ms      1 rows Correlated SELECT * FROM unnest(ARRAY[1]) id JOIN t
   0.045ms      1 rows     Random SELECT * FROM test_array WHERE id =ANY(A
   0.042ms      1 rows     Random SELECT * FROM test_array WHERE id IN (31
   0.070ms      1 rows     Random SELECT * FROM unnest(ARRAY[3146607]) id
   0.058ms     10 rows Correlated SELECT * FROM test_array WHERE id =ANY(A
   0.059ms     10 rows Correlated SELECT * FROM test_array WHERE id IN (1,
   0.085ms     10 rows Correlated SELECT * FROM unnest(ARRAY[1,2,3,4,5,6,7
   0.065ms     10 rows     Random SELECT * FROM test_array WHERE id =ANY(A
   0.062ms     10 rows     Random SELECT * FROM test_array WHERE id IN (66
   0.088ms     10 rows     Random SELECT * FROM unnest(ARRAY[6629054,48357
   0.184ms    100 rows Correlated SELECT * FROM test_array WHERE id =ANY(A
   0.183ms    100 rows Correlated SELECT * FROM test_array WHERE id IN (1,
   0.222ms    100 rows Correlated SELECT * FROM unnest(ARRAY[1,2,3,4,5,6,7
   0.247ms    100 rows     Random SELECT * FROM test_array WHERE id =ANY(A
   0.237ms    100 rows     Random SELECT * FROM test_array WHERE id IN (15
   0.258ms    100 rows     Random SELECT * FROM unnest(ARRAY[153046,957664
   1.442ms   1000 rows Correlated SELECT * FROM test_array WHERE id =ANY(A
   1.458ms   1000 rows Correlated SELECT * FROM test_array WHERE id IN (1,
   1.558ms   1000 rows Correlated SELECT * FROM unnest(ARRAY[1,2,3,4,5,6,7
   2.076ms   1000 rows     Random SELECT * FROM test_array WHERE id =ANY(A
   2.019ms   1000 rows     Random SELECT * FROM test_array WHERE id IN (90
   2.070ms   1000 rows     Random SELECT * FROM unnest(ARRAY[9047600,58146
  15.233ms  10000 rows Correlated SELECT * FROM test_array WHERE id =ANY(A
  14.536ms  10000 rows Correlated SELECT * FROM test_array WHERE id IN (1,
  15.389ms  10000 rows Correlated SELECT * FROM unnest(ARRAY[1,2,3,4,5,6,7
  62.936ms   9995 rows     Random SELECT * FROM test_array WHERE id =ANY(A
  47.661ms   9995 rows     Random SELECT * FROM test_array WHERE id IN (31
  36.861ms  10000 rows     Random SELECT * FROM unnest(ARRAY[3109119,87658
 421.528ms 100000 rows Correlated SELECT * FROM test_array WHERE id =ANY(A
 413.692ms 100000 rows Correlated SELECT * FROM test_array WHERE id IN (1,
  95.054ms 100000 rows Correlated SELECT * FROM unnest(ARRAY[1,2,3,4,5,6,7
 413.768ms  99482 rows     Random SELECT * FROM test_array WHERE id =ANY(A
 411.587ms  99482 rows     Random SELECT * FROM test_array WHERE id IN (33
 508.202ms 100000 rows     Random SELECT * FROM unnest(ARRAY[3364043,10450

Interpretation:

There is no difference between "WHERE id IN (...)" and "WHERE id =ANY(...)".

How does this query type scale? I assume the array is not indexed, so presumably each array value hits the index, giving scaling of O(n.N), for n array values, and N table rows?

Assuming the column being searched is indexed, it does one index lookup for each value in the array, at a cost of O(log N). With n array values, that's a total cost of O(n log N). As expected, there is a small fixed cost to run a query, then it scales pretty much linearly with the number of rows returned.

I have included two cases: "Correlated" where ids for retrieved rows are consecutive, and "Random" where they are randomized over the whole table. As expected, the various caches (from CPU L1 to OS disk cache) do their job, so it's faster to retrieve data with higher locality of reference.

Anyway, at 2 microseconds per row, database CPU load is pretty low.

However, this runs on a SSD and the table is cached in RAM. In a more "real world" situation, where parts of the table would not be cached, if you retrieve random rows you can expect one random access per row. This may be quite slow, depending on your hardware, but... that has nothing to do with postgres itself. That depends entirely on your IO system and how well your data is cached. If you use spinning disks and data isn't cached, and you don't particularly care about this query being as fast as possible then maybe slicing it into smaller lists of rows would reduce disk trashing.

I also included a third test case:

SELECT * FROM unnest(ARRAY[%s]) id JOIN test_array USING (id)

When the length of the array is very large, the other queries simply do a parallel seq scan. This is very fast, because the "Filter where id=ANY(...)" isn't dumb, it uses some kind of fast search like hashing or bisect, it doesn't compare every row with every value of the array.

This last query is interesting because it's a join, so postgres optimizes it as a join, which may be faster... or slower... in some cases.

Answer 2

The limits appendix will inform you that the maximum number of query parameters is 65535, and if memory serves, the limit for a message (query) is half a GB.

Naturally, performance will gradually worsen as the list gets longer. I would recommend sending a single array parameter rather than thousands of individual values. An alternative approach is to COPY the values into a temporary table and join with that. For normal list sizes, I have seen no advantage from that, but it avoids the limits and may be beneficial for huge lists.

In the end, you'll have to benchmark that yourself. If you need huge lists like that, you may want to reassess your design choices.

Answer 3

I would like to complete the above answer that states that:

When the length of the array is very large, the other queries simply do a parallel seq scan. This is very fast, because the "Filter where id=ANY(...)" isn't dumb, it uses some kind of fast search like hashing or bisect, it doesn't compare every row with every value of the array.

While this seems to be the case for const arrays, including = ANY($1) where $1 is an array expression since Postgres 14 (50e17ad), = ANY(array) will do O(n²) bitmap heap scans with recheck if the array is not of Const size.

This includes the following cases:

• = ANY(ARRAY(subquery)): only const are supported. Also, the planner currently does not propagate information of subquery estimated size to array estimated size. You should generally prefer writing = ANY(subquery) or IN(subquery).
• array_value IN(a1, a2) where a1 and a2 are both arrays. Normally when doing x IN (a,b,c), this gets optimized to x = ANY(ARRAY[a,b,c]), which in turn can use hashing. However if x is actually an array that we're trying to lookup, because there's no such thing as ARRAY[ARRAY[...]] in Postgres (2d arrays are a different thing), you can't write it as = ANY($1) and array_value IN(arr1, arr2, ) instead just gets expanded as array_value = arr1 OR array_value = arr2 OR ..., which will also be checked linearly, resulting in O(n²) total.