BUG #16383: Query planner has (potentially very) wrong predicted row count for some group bys

The following bug has been logged on the website:

Bug reference: 16383
Logged by: Alex Kaiser
Email address: alextkaiser(at)gmail(dot)com
PostgreSQL version: 12.2
Operating system: macOS 10.14.6
Description:

Hello,

The query planner is a big complicated black box to me so I don't know if
the following is just not possible or if it's actually a bug, but it did
cause large problems for us.

Suppose you have a simple table to track user logins like this:

create table user_logins (
user_id bigint,
login_date timestamptz,
info varchar(10)
);
create index find_login on user_logins (user_id, login_date);

And lets assume you have at least 1000 users and they have all logged in 50
times, so you have 50,000 rows. And then you issue the following query:

explain analyze
SELECT user_id, max(login_date) as max_login_date FROM user_logins WHERE
user_id = 0 GROUP BY user_id;

QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------
GroupAggregate (cost=0.29..90.41 rows=49 width=16) (actual
time=0.068..0.069 rows=1 loops=1)
Group Key: user_id
-> Index Only Scan using find_login on user_logins (cost=0.29..89.67
rows=50 width=16) (actual time=0.038..0.054 rows=50 loops=1)
Index Cond: (user_id = 0)
Heap Fetches: 50
Planning Time: 0.283 ms
Execution Time: 0.119 ms

The query planner estimates that there will be 49 rows in the result,
however looking at the query it should be easy to see that there will always
be a max of 1 row because we are grouping by user_id and also have an
equality limiting the number of user_ids.

The above case shows the actual issue but doesn't cause any tangible
problems as for that query the query planner will still always choose the
right plan, it will just be off in the estimated cost. The real problem is
when the above group by is an inner query in a larger query. For example
suppose we wanted to find the 'info' column for the latest login for X
random users (This is a common "find the whole data for the row with some
max value in a column per some group identifier" see
https://stackoverflow.com/questions/7745609/sql-select-only-rows-with-max-value-on-a-column).
A query to solve this might be:

explain analyze SELECT user_logins_1.user_id, user_logins_1.info
FROM user_logins user_logins_1 inner join
(SELECT user_id, max(login_date) as max_login_date
FROM user_logins
WHERE user_id in (0, 1, 2, 3, 4)
GROUP BY user_id) user_logins_2
ON user_logins_1.user_id = user_logins_2.user_id
AND user_logins_1.login_date = user_logins_2.max_login_date;
QUERY
PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------
Hash Join (cost=363.16..1484.66 rows=1 width=16) (actual
time=0.141..11.432 rows=5 loops=1)
Hash Cond: ((user_logins_1.user_id = user_logins.user_id) AND
(user_logins_1.login_date = (max(user_logins.login_date))))
-> Seq Scan on user_logins user_logins_1 (cost=0.00..859.00 rows=50000
width=24) (actual time=0.011..4.607 rows=50000 loops=1)
-> Hash (cost=359.83..359.83 rows=222 width=16) (actual
time=0.122..0.122 rows=5 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 9kB
-> GroupAggregate (cost=0.29..357.61 rows=222 width=16) (actual
time=0.040..0.117 rows=5 loops=1)
Group Key: user_logins.user_id
-> Index Only Scan using find_login on user_logins
(cost=0.29..354.14 rows=250 width=16) (actual time=0.014..0.089 rows=250
loops=1)
Index Cond: (user_id = ANY ('{0,1,2,3,4}'::bigint[]))
Heap Fetches: 250
Planning Time: 0.178 ms
Execution Time: 11.469 ms

However if you turn off sequential scans by running "set enable_seqscan =
off;" you then get:
QUERY
PLAN
------------------------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.58..1678.87 rows=1 width=16) (actual time=0.073..0.205
rows=5 loops=1)
-> GroupAggregate (cost=0.29..357.61 rows=222 width=16) (actual
time=0.064..0.180 rows=5 loops=1)
Group Key: user_logins.user_id
-> Index Only Scan using find_login on user_logins
(cost=0.29..354.14 rows=250 width=16) (actual time=0.023..0.140 rows=250
loops=1)
Index Cond: (user_id = ANY ('{0,1,2,3,4}'::bigint[]))
Heap Fetches: 250
-> Index Scan using find_login on user_logins user_logins_1
(cost=0.29..5.93 rows=1 width=24) (actual time=0.003..0.003 rows=1
loops=5)
Index Cond: ((user_id = user_logins.user_id) AND (login_date =
(max(user_logins.login_date))))
Planning Time: 0.248 ms
Execution Time: 0.244 ms

The second plan runs a lot faster. This is just a small example, but we ran
into this problem with a 200 GB table where when trying to look up logins
for ~100 users it started to do full table scans when the efficient plan
would have run in < 10 ms.

Here is a link to a sql file to set up the schema, insert the 50,000 rows,
and then run the problem query:
https://gist.github.com/atkaiser/1d240b33315ba75fc8cfbe206822ad8d

Thanks,
Alex