Hi,
Planning a query of the form
SELECT * FROM t WHERE c = 1 AND (a, b) IN ((...), (...), ...)
on a table with an index on (c, a, b) takes time that grows with the square
of the number of entries in the IN list. With 2000 entries the planner needs
about one second on each of 15.19, 16.15, 17.11, 18.6 and 19beta4. With 4000
entries, measured on 18.6 and 19beta4, it needs about four seconds. I found
no earlier report of this behaviour in the archives of pgsql-hackers,
pgsql-bugs and pgsql-performance.
I first observed the behaviour on 15.2, in a batch job whose prepared
statements each contain an (a, b) IN (...) list of 448 entries that all
share the same b. Planning one such statement took 104 to 187 ms, against
5 to 9 ms with enable_bitmapscan = off. Since version 18 that form plans in
a few milliseconds, while the form above stays quadratic.
I have two questions for the list. Is the first suggestion below, testing
the arm at the same position before the others, an acceptable change to
predtest.c? And is someone who knows that file willing to write it? I cannot
write the patch myself. If the change is back-patched to 15, 16 or 17, I
will test it with the statements of that batch job.
Reproduction
Each attached script runs with psql -X -f <file> against an empty database.
The attached repro_short.sql creates a table of 500000 generated rows and
runs EXPLAIN (SUMMARY ON) only, so none of the measured queries is executed.
Its core:
create table orproof_t (c int not null, a text not null,
b timestamp not null, d int);
insert into orproof_t
select i % 5, 'K' || lpad(i::text, 7, '0'),
timestamp '2026-01-01' + (i % 10) * interval '1 day', i
from generate_series(1, 500000) i;
create index orproof_t_c_a_b on orproof_t (c, a, b);
vacuum analyze orproof_t;
explain (summary on)
select * from orproof_t
where c = 1 and (a, b) in (('K0000006', '2026-01-07'),
('K0000011', '2026-01-02'), ...);
It prints the top plan node and the planning time for 250 to 4000 entries,
with and without enable_bitmapscan. For 4000 entries it printed 3871 ms on
18.6 and 3930 ms on 19beta4.
Measurements
All figures are the planning time in ms that EXPLAIN (SUMMARY ON) reports,
as the median of three runs. The servers are the official Docker images with
their default configuration, on a laptop under WSL2. The attached repro2.sql
produces these figures.
Literal values, default settings; the top plan node is a Bitmap Heap Scan
over a BitmapOr with one Bitmap Index Scan per entry of the list:
entries 15.19 16.15 17.11 18.6 19beta4
250 19.2 16.8 14.4 25.2 15.5
500 68.4 64.6 60.7 95.6 66.1
1000 253.3 233.9 243.1 381.8 268.5
2000 939.2 1410.8 1046.8 1209.8 1053.6
With enable_bitmapscan = off the same statement with 2000 entries plans in
6 to 8 ms on all five versions, as a Gather over a Parallel Seq Scan.
Prepared statement with parameters, plan_cache_mode = force_generic_plan;
Bitmap Heap Scan:
entries 15.19 16.15 17.11 18.6 19beta4
250 4.6 4.5 4.0 6.4 3.7
500 19.4 16.3 15.7 26.2 13.4
1000 58.8 56.5 54.1 70.3 58.7
2000 253.0 245.2 223.2 220.4 243.0
As a workaround, the same lookup written as a join against
unnest(array[...]::text[], array[...]::timestamp[]) plans in 0.3 to 0.4 ms
for 2000 entries on all five versions.
Two related query forms show which queries are affected (attached
repro.sql; index on (a, b), no condition on c):
1. (a, b) IN (...) where b varies across the entries of the list: planning
stays below 17 ms for 2000 entries on all five versions.
2. (a, b) IN (...) where every entry of the list has the same b: planning
is quadratic on 15.19, 16.15 and 17.11 (762, 890 and 975 ms for 2000
entries) and stays below 8 ms on 18.6 and 19beta4. The plan on 18.6 and
19beta4 is an Index Scan.
Source reading
The following is my reading of master as of 2026-10-04. It is consistent
with every measurement above, yet I have not profiled the planner, so the
attribution to these functions is an inference.
transformAExprIn() turns the row-value IN list into one OR with one AND arm
per entry. In the reproduction the scan clauses are therefore
c = 1
(a = a1 AND b = b1) OR (a = a2 AND b = b2) OR ...
generate_bitmap_or_paths() builds one index path per arm and adds c = 1 to
each of them, so create_bitmap_subplan() returns as indexquals a single OR
whose arms have three conditions (createplan.c, the make_orclause() call for
subindexquals):
(c = 1 AND a = a1 AND b = b1) OR (c = 1 AND a = a2 AND b = b2) OR ...
EXPLAIN shows both shapes: the three-condition arms as Recheck Cond and
Index Cond of the bitmap plan, the two-condition arms as Filter of the
sequential plan.
create_bitmap_scan_plan() then decides for each scan clause whether it has
to stay in qpqual:
if (list_member(indexquals, clause))
continue; /* simple duplicate */
...
if (!contain_mutable_functions(clause) &&
predicate_implied_by(list_make1(clause), indexquals, false))
continue; /* provably implied by indexquals */
list_member() fails, because the arms differ in shape.
predicate_implied_by()
reaches the OR-versus-OR case of predicate_implied_by_recurse()
(predtest.c),
/*
* OR-clause => OR-clause if each of A's items implies any
* of B's items. Messy but can't do it any more simply.
*/
which compares arm i of the indexquals with the arms 1 to i of the scan
clause until the proof succeeds at arm i. For N entries that amounts to
about N^2/2 attempts. Each failing attempt compares a = ai with a = aj in
operator_predicate_proof(), which builds a test expression from the two
constants and evaluates it in the executor.
This reading explains the other measurements as follows:
- With enable_bitmapscan = off the planner still generates the bitmap
paths. Since it picks the sequential scan, create_bitmap_scan_plan() does
not run.
- With parameters instead of constants operator_predicate_proof() returns
before it builds the test expression, so each of the N^2/2 attempts is
cheaper, while the growth stays quadratic.
- In related form 1 the scan clause and the indexquals are equal(), so
list_member() succeeds and the proof does not run.
- In related form 2 the common condition on b is factored out of the OR
(process_duplicate_ors() in prepqual.c), which leaves b = X and an OR
over
a alone. The shapes of the scan clause and the indexquals therefore
differ
again. Since version 18 the OR over a is matched to the index as
a = ANY(...) (commit d4378c0, "Transform OR-clauses to SAOP's during
index
matching"), so no BitmapOr is built. group_similar_or_args() accepts only
arms that are a single two-argument operator clause, so the AND arms of
the reproduction keep the BitmapOr on 18 and 19.
predtest.c already limits proofs of this kind for ScalarArrayOpExpr:
/*
* Proof attempts involving large arrays in ScalarArrayOpExpr nodes are
* likely to require O(N^2) time, and more often than not fail anyway.
* So we set an arbitrary limit on the number of array elements that
* we will allow to be treated as an AND or OR clause.
*/
#define MAX_SAOP_ARRAY_SIZE 100
Explicit AND and OR trees have no such limit.
Suggestions
1. Try the arm at the same position first. In the OR-versus-OR case, test
arm i of the clause against arm i of the predicate before scanning the
other arms. In the plans of the reproduction the BitmapOr arms appear in
the same order as the OR arms, so the proof in create_bitmap_scan_plan()
then succeeds after N attempts. The result of the proof is unchanged,
since the full scan remains as the fallback.
2. Limit the number of arms, as MAX_SAOP_ARRAY_SIZE does for arrays, either
in predicate_classify() for all callers or only in
create_bitmap_scan_plan(). A proof that is skipped there keeps the OR
clause in qpqual, so the executor evaluates an N-arm filter for every
heap row the bitmap returns. A limit therefore moves part of the cost
from planning to execution. In predicate_classify() it also changes
proofs for partial indexes and constraint exclusion.
Suggestion 1 keeps the current plans, which is why I prefer it.
Regards,
Stefan Guha
-- Planning time of a row-value IN list against a two-column index.
-- Self-contained: creates its own table, runs EXPLAIN (SUMMARY ON) only,
executes none of the measured queries.
-- usage: psql -X -f repro.sql
\set ON_ERROR_STOP on
\pset pager off
\timing off
select version();
drop table if exists orproof_t;
create table orproof_t (a text not null, b timestamp not null, c int);
insert into orproof_t
select 'K' || lpad(i::text, 7, '0'), timestamp '2026-01-01' + (i % 10) *
interval '1 day', i
from generate_series(1, 500000) i;
create index orproof_t_a_b on orproof_t (a, b);
vacuum analyze orproof_t;
-- Returns the top plan node, whether any node carries a Filter, and the
planning time of one EXPLAIN.
create or replace function orproof_plan(q text, out plan text, out has_filter
boolean, out planning_ms numeric)
language plpgsql as $$
declare
l text;
first boolean := true;
begin
has_filter := false;
for l in execute 'explain (summary on) ' || q loop
if first then
plan := split_part(l, ' (', 1);
first := false;
end if;
if l ~ '^\s*Filter:' then
has_filter := true;
end if;
if l like 'Planning Time:%' then
planning_ms := substring(l from '([0-9.]+) ms')::numeric;
end if;
end loop;
end $$;
create temp table orproof_result (
form text, setting text, n int, run int, plan text, has_filter boolean,
planning_ms numeric);
do $$
declare
n int;
step int;
form text;
tuples text;
params text;
args text;
a_list text;
b_list text;
q text;
run int;
r record;
begin
foreach n in array array[250, 500, 1000, 2000] loop
-- step 1: b varies across the tuples; step 10: all tuples share one value
of b
foreach step in array array[1, 10] loop
form := case step when 1 then 'row IN, b varies' else 'row IN, b shared'
end;
select string_agg(format('(%L,%L)', a, b), ',' order by k),
string_agg(format('($%s,$%s)', 2 * k - 1, 2 * k), ',' order by k),
string_agg(format('%L,%L', a, b), ',' order by k),
string_agg(format('%L', a), ',' order by k),
string_agg(format('%L', b), ',' order by k)
into tuples, params, args, a_list, b_list
from (select k,
'K' || lpad((k * step)::text, 7, '0') as a,
(timestamp '2026-01-01' + ((k * step) % 10) * interval '1
day')::text as b
from generate_series(1, n) k) s;
q := 'select * from orproof_t where (a, b) in (' || tuples || ')';
execute 'prepare orproof_p as select * from orproof_t where (a, b) in ('
|| params || ')';
for run in 1..3 loop
perform set_config('enable_bitmapscan', 'on', false);
select * into r from orproof_plan(q);
insert into orproof_result values (form, 'literals', n, run, r.plan,
r.has_filter, r.planning_ms);
perform set_config('enable_bitmapscan', 'off', false);
select * into r from orproof_plan(q);
insert into orproof_result values (form, 'literals, enable_bitmapscan =
off', n, run, r.plan, r.has_filter, r.planning_ms);
perform set_config('enable_bitmapscan', 'on', false);
perform set_config('plan_cache_mode', 'force_custom_plan', false);
select * into r from orproof_plan('execute orproof_p(' || args || ')');
insert into orproof_result values (form, 'prepared, custom plan', n,
run, r.plan, r.has_filter, r.planning_ms);
end loop;
-- A generic plan is cached after the first EXECUTE, so each run needs a
fresh PREPARE.
execute 'deallocate orproof_p';
perform set_config('plan_cache_mode', 'force_generic_plan', false);
for run in 1..3 loop
execute 'prepare orproof_p as select * from orproof_t where (a, b) in
(' || params || ')';
select * into r from orproof_plan('execute orproof_p(' || args || ')');
insert into orproof_result values (form, 'prepared, generic plan', n,
run, r.plan, r.has_filter, r.planning_ms);
execute 'deallocate orproof_p';
end loop;
perform set_config('plan_cache_mode', 'auto', false);
for run in 1..3 loop
select * into r from orproof_plan(
'select t.* from orproof_t t join unnest(array[' || a_list ||
']::text[], array[' || b_list
|| ']::timestamp[]) u(a, b) on t.a = u.a and t.b = u.b');
insert into orproof_result values (replace(form, 'row IN', 'join
unnest'), 'literals', n, run, r.plan, r.has_filter, r.planning_ms);
end loop;
end loop;
for run in 1..3 loop
select * into r from orproof_plan('select * from orproof_t where a in ('
|| a_list || ')');
insert into orproof_result values ('single-column IN', 'literals', n,
run, r.plan, r.has_filter, r.planning_ms);
end loop;
end loop;
end $$;
select form, setting, n,
min(plan) as top_plan_node,
bool_or(has_filter) as filter,
min(planning_ms) as min_ms,
(array_agg(planning_ms order by planning_ms))[2] as median_ms,
max(planning_ms) as max_ms
from orproof_result
group by form, setting, n
order by form, setting, n;
drop table orproof_t;
drop function orproof_plan(text);
-- Short reproduction for the mail body. usage: psql -X -f repro_short.sql
\set ON_ERROR_STOP on
\pset pager off
select version();
drop table if exists orproof_t;
create table orproof_t (c int not null, a text not null, b timestamp not null,
d int);
insert into orproof_t
select i % 5, 'K' || lpad(i::text, 7, '0'), timestamp '2026-01-01' + (i % 10) *
interval '1 day', i
from generate_series(1, 500000) i;
create index orproof_t_c_a_b on orproof_t (c, a, b);
vacuum analyze orproof_t;
-- Builds "c = 1 AND (a, b) IN (<n entries>)"; every entry of the list exists
in the table with c = 1.
create or replace function orproof_q(n int) returns text language sql as $$
select 'explain (costs off, summary on) select * from orproof_t where c = 1
and (a, b) in ('
|| string_agg(format('(%L,%L)', 'K' || lpad((5 * k + 1)::text, 7, '0'),
timestamp '2026-01-01' + ((5 * k + 1) % 10) *
interval '1 day'), ',')
|| ')'
from generate_series(1, n) k
$$;
-- Prints only the top plan node and the planning time.
create or replace function orproof_plan(n int) returns setof text language
plpgsql as $$
declare
l text;
first boolean := true;
begin
for l in execute orproof_q(n) loop
if first or l like 'Planning Time:%' then
return next format('n = %s: %s', n, l);
end if;
first := false;
end loop;
end $$;
select orproof_plan(n) from unnest(array[250, 500, 1000, 2000, 4000]) n;
set enable_bitmapscan = off;
select orproof_plan(n) from unnest(array[250, 500, 1000, 2000, 4000]) n;
reset enable_bitmapscan;
drop function orproof_plan(int);
drop function orproof_q(int);
drop table orproof_t;
-- Planning time of "c = X AND (a, b) IN (...)" against an index on (c, a, b).
-- The arms of the OR stay two-column ANDs, so the OR-to-SAOP transformation of
PostgreSQL 18 does not apply.
-- Self-contained: creates its own table, runs EXPLAIN (SUMMARY ON) only,
executes none of the measured queries.
-- usage: psql -X -f repro2.sql
\set ON_ERROR_STOP on
\pset pager off
\timing off
select version();
drop table if exists orproof_t;
create table orproof_t (c int not null, a text not null, b timestamp not null,
d int);
insert into orproof_t
select i % 5, 'K' || lpad(i::text, 7, '0'), timestamp '2026-01-01' + (i % 10) *
interval '1 day', i
from generate_series(1, 500000) i;
create index orproof_t_c_a_b on orproof_t (c, a, b);
vacuum analyze orproof_t;
create or replace function orproof_plan(q text, out plan text, out has_filter
boolean, out planning_ms numeric)
language plpgsql as $$
declare
l text;
first boolean := true;
begin
has_filter := false;
for l in execute 'explain (summary on) ' || q loop
if first then
plan := split_part(l, ' (', 1);
first := false;
end if;
if l ~ '^\s*Filter:' then
has_filter := true;
end if;
if l like 'Planning Time:%' then
planning_ms := substring(l from '([0-9.]+) ms')::numeric;
end if;
end loop;
end $$;
create temp table orproof_result (
form text, setting text, n int, run int, plan text, has_filter boolean,
planning_ms numeric);
do $$
declare
n int;
tuples text;
params text;
args text;
a_list text;
b_list text;
q text;
run int;
r record;
begin
foreach n in array array[250, 500, 1000, 2000] loop
-- rows with i = 5k + 1 all have c = 1, and b varies across them
select string_agg(format('(%L,%L)', a, b), ',' order by k),
string_agg(format('($%s,$%s)', 2 * k - 1, 2 * k), ',' order by k),
string_agg(format('%L,%L', a, b), ',' order by k),
string_agg(format('%L', a), ',' order by k),
string_agg(format('%L', b), ',' order by k)
into tuples, params, args, a_list, b_list
from (select k,
'K' || lpad((5 * k + 1)::text, 7, '0') as a,
(timestamp '2026-01-01' + ((5 * k + 1) % 10) * interval '1
day')::text as b
from generate_series(1, n) k) s;
q := 'select * from orproof_t where c = 1 and (a, b) in (' || tuples || ')';
for run in 1..3 loop
perform set_config('enable_bitmapscan', 'on', false);
select * into r from orproof_plan(q);
insert into orproof_result values ('c = 1 and (a, b) IN', 'literals', n,
run, r.plan, r.has_filter, r.planning_ms);
perform set_config('enable_bitmapscan', 'off', false);
select * into r from orproof_plan(q);
insert into orproof_result values ('c = 1 and (a, b) IN', 'literals,
enable_bitmapscan = off', n, run, r.plan, r.has_filter, r.planning_ms);
perform set_config('enable_bitmapscan', 'on', false);
end loop;
-- A generic plan is cached after the first EXECUTE, so each run needs a
fresh PREPARE.
perform set_config('plan_cache_mode', 'force_generic_plan', false);
for run in 1..3 loop
execute 'prepare orproof_p as select * from orproof_t where c = 1 and (a,
b) in (' || params || ')';
select * into r from orproof_plan('execute orproof_p(' || args || ')');
insert into orproof_result values ('c = 1 and (a, b) IN', 'prepared,
generic plan', n, run, r.plan, r.has_filter, r.planning_ms);
execute 'deallocate orproof_p';
end loop;
perform set_config('plan_cache_mode', 'auto', false);
for run in 1..3 loop
select * into r from orproof_plan(
'select t.* from orproof_t t join unnest(array[' || a_list ||
']::text[], array[' || b_list
|| ']::timestamp[]) u(a, b) on t.a = u.a and t.b = u.b where t.c = 1');
insert into orproof_result values ('c = 1 and join unnest', 'literals',
n, run, r.plan, r.has_filter, r.planning_ms);
end loop;
end loop;
end $$;
select form, setting, n,
min(plan) as top_plan_node,
bool_or(has_filter) as filter,
min(planning_ms) as min_ms,
(array_agg(planning_ms order by planning_ms))[2] as median_ms,
max(planning_ms) as max_ms
from orproof_result
group by form, setting, n
order by form, setting, n;
drop table orproof_t;
drop function orproof_plan(text);
