BUG #18205: Performance regression with NOT NULL checks.

The following bug has been logged on the website:

Bug reference:      18205
Logged by:          Daniel Migowski
Email address:      dmigowski@ikoffice.de
PostgreSQL version: 15.5
Operating system:   Windows + Linux
Description:

I found out that selecting from a wide table with a single not-null where
clause leads to severe performance regression when upgrading from PostgreSQL
9.5 to PostgreSQL 15. I am doing the following queries without parallel
query enabled because in a real world case we cannot go parallel anyway. 

    select count(id) FROM testtable t WHERE t.y IS NULL;

Here are the timings of the query (three runs):

    PG 9.5: 0,33s 0,33s 0,33s
    PG 15: 0,43s 0,44s 0,43s

Please create a test table this way:

drop table if exists testtable cascade;
SELECT generate_series::int4 as id, null::int4 a, null::int4 b,
    null::int4 c, null::int4 d, null::int4 e, null::int4 f, null::int4 g,
null::int4 h, null::int4 i, null::int4 j,
    null::int4 k, null::int4 l, null::int4 m, null::int4 n, null::int4 o,
null::int4 p, null::int4 q, null::int4 r, 
    null::int4 s, null::int4 t, null::int4 u, null::int4 v, null::int4 w,
null::int4 x, null::int4 y, null::int4 z
    into testtable 
   FROM generate_series(1,6000000,1);

-- On PG15:
set max_parallel_workers = 0;
set max_parallel_workers_per_gather = 0;

I already talked to despesz about this and he timed the query on different
PG versions, which seem to be the versions from PostgreSQL's Debian
repository:

- 9.5.25 : 590.958 ms
- 9.6.24 : 607.228 ms
- 10.23 : 820.779 ms
- 11.22 : 746.122 ms
- 12.17 : 829.786 ms
- 13.13 : 804.878 ms
- 14.10 : 772.415 ms
- 15.5 : 774.749 ms
- 16.1 : 746.802 ms

Starting with PostgreSQL 10 there is a severe degration in performance. I
just cannot believe later versions of PostgreSQL being so much slower than
the original versions.