Incorrect choice of Nested Loop for a skewed distribution

Hi All,

With PostgreSQL 10 and 11, the planner doesn't use the lists of most
common values to determine the selectivity of "=" for Nested Loop as it
does for a normal inner join in eqjoinsel_inner(). Incorrect choice of a
nested loops join strategy causes poor query performance.
To demonstrate it one can make the following test case:

  create table t(f integer not null,g integer not null);
  create table u(f integer not null,g integer not null);
  create sequence s cache 1000;
  insert into t select 0,s from (select nextval('s') as s) as d;
  insert into t select 0,s from (select nextval('s') as s) as d;
  insert into t select 0,s from (select nextval('s') as s from t,t t1,t
t2) as d;
  insert into t select 0,s from (select nextval('s') as s from t,t t1,t
t2,t t3) as d;
  insert into t(f,g) select g,f from t;
  insert into u select * from t;
  create index t_f on t(f);
  vacuum analyze;

The columns f and g of both tables t and u have a skewed distribution:
10010 values of 0 and 10010 unique values starting from 1.
Let's see query plan for the join of t and u:

  explain analyze select * from t,u where t.f=u.f and t.g=u.g;

                                                  QUERY PLAN
-----------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.29..7629.95 rows=25055030 width=16) (actual
time=0.042..22540.629 rows=20020 loops=1)
   ->  Seq Scan on u  (cost=0.00..289.20 rows=20020 width=8) (actual
time=0.011..3.025 rows=20020 loops=1)
   ->  Index Scan using t_f on t  (cost=0.29..0.36 rows=1 width=8)
(actual time=0.565..1.125 rows=1 loops=20020)
         Index Cond: (f = u.f)
         Filter: (u.g = g)
         Rows Removed by Filter: 5004
 Planning Time: 0.394 ms
 Execution Time: 22542.639 ms

After dropping the index
  drop index t_f;
we obtain much better query plan (without Nested Loop):

                                                   QUERY PLAN
-----------------------------------------------------------------------------------------------------------------
 Merge Join  (cost=3439.09..442052.26 rows=25055030 width=16) (actual
time=15.708..32.735 rows=20020 loops=1)
   Merge Cond: ((t.f = u.f) AND (t.g = u.g))
   ->  Sort  (cost=1719.54..1769.59 rows=20020 width=8) (actual
time=8.189..10.189 rows=20020 loops=1)
         Sort Key: t.f, t.g
         Sort Method: quicksort  Memory: 1707kB
         ->  Seq Scan on t  (cost=0.00..289.20 rows=20020 width=8)
(actual time=0.012..2.958 rows=20020 loops=1)
   ->  Sort  (cost=1719.54..1769.59 rows=20020 width=8) (actual
time=7.510..9.459 rows=20020 loops=1)
         Sort Key: u.f, u.g
         Sort Method: quicksort  Memory: 1707kB
         ->  Seq Scan on u  (cost=0.00..289.20 rows=20020 width=8)
(actual time=0.008..2.748 rows=20020 loops=1)
 Planning Time: 0.239 ms
 Execution Time: 34.585 ms

Using MCV lists in var_eq_non_const() would prevent from choosing Nested
Loop in such cases.

Regards,
Oleg Kharin