BUG #16558: `AND FALSE` increases planning time of query on 2 tables with 1000 partitions to more than 7 seconds

The following bug has been logged on the website:

Bug reference: 16558
Logged by: Marcin Barczyński
Email address: mba(dot)ogolny(at)gmail(dot)com
PostgreSQL version: 12.3
Operating system: Ubuntu 18.04.4 LTS
Description:

PostgreSQL server version: 12.3

Consider the following setup of empty tables partitioned first by `key1` and
then by `key2`:

DROP TABLE IF EXISTS demo1 CASCADE;
DROP TABLE IF EXISTS demo2 CASCADE;

CREATE TABLE demo1(key1 BIGINT, key2 BIGINT) PARTITION BY RANGE(key1);
CREATE TABLE demo1_positive
PARTITION OF demo1 FOR VALUES FROM (0) TO (MAXVALUE)
PARTITION BY LIST (key2);
CREATE TABLE demo1_negative
PARTITION OF demo1 FOR VALUES FROM (MINVALUE) TO (0)
PARTITION BY LIST (key2);

CREATE TABLE demo2(key1 BIGINT, key2 BIGINT) PARTITION BY RANGE(key1);
CREATE TABLE demo2_positive
PARTITION OF demo2 FOR VALUES FROM (0) TO (MAXVALUE)
PARTITION BY LIST (key2);
CREATE TABLE demo2_negative
PARTITION OF demo2 FOR VALUES FROM (MINVALUE) TO (0)
PARTITION BY LIST (key2);

ALTER TABLE demo1_positive ADD CONSTRAINT demo1_positive_pk PRIMARY KEY
(key1, key2);
ALTER TABLE demo1_negative ADD CONSTRAINT demo1_negative_pk PRIMARY KEY
(key1, key2);
ALTER TABLE demo2_positive ADD CONSTRAINT demo2_positive_pk PRIMARY KEY
(key1, key2);
ALTER TABLE demo2_negative ADD CONSTRAINT demo2_negative_pk PRIMARY KEY
(key1, key2);

DO $$
DECLARE
i BIGINT;
BEGIN
FOR i IN SELECT * FROM generate_series(0, 1024)
LOOP
EXECUTE 'CREATE TABLE demo1_positive_' || i || ' PARTITION OF
demo1_positive FOR VALUES IN (' || i || ');';
EXECUTE 'CREATE TABLE demo1_negative_' || i || ' PARTITION OF
demo1_negative FOR VALUES IN (' || i || ');';
EXECUTE 'CREATE TABLE demo2_positive_' || i || ' PARTITION OF
demo2_positive FOR VALUES IN (' || i || ');';
EXECUTE 'CREATE TABLE demo2_negative_' || i || ' PARTITION OF
demo2_negative FOR VALUES IN (' || i || ');';
END LOOP;
END$$;

ANALYZE demo1;
ANALYZE demo2;

Now, let's investigate the planning time of a query limited to a single
partition on both tables:

EXPLAIN ANALYZE
SELECT *
FROM demo1
JOIN demo2 ON demo1.key2 = demo2.key2
WHERE demo1.key2 = 123
AND demo2.key2 = 123
AND FALSE;
QUERY PLAN

-------------------------------------------------------------------------------------
Result (cost=0.00..0.00 rows=0 width=32) (actual time=0.002..0.002 rows=0
loops=1)
One-Time Filter: false
Planning Time: 7113.014 ms
Execution Time: 0.211 ms
(4 rows)

Planning time depends quadratically on the number of partitions:
- 1 partition: 0.686 ms
- 4 partitions: 0.689 ms
- 16 partitions: 1.574 ms
- 64 partitions: 15.325 ms
- 256 partitions: 213.275 ms
- 512 partitions: 1043.161 ms
- 1024 partitions: 7113.014 ms

Experimentally, I observed that removing `AND FALSE` condition vastly
increases the planning time:

EXPLAIN ANALYZE
SELECT *
FROM demo1
JOIN demo2 ON demo1.key2 = demo2.key2
WHERE demo1.key2 = 123
AND demo2.key2 = 123;
QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=13.61..72.91 rows=324 width=32) (actual
time=0.011..0.011 rows=0 loops=1)
(...)
Planning Time: 0.659 ms
Execution Time: 0.120 ms
(22 rows)

I expected that `AND FALSE` condition would not increase the planning time.