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
