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.ogolny@gmail.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.