Re: BUG #16759: Estimation of the planner is wrong for hash join - Mailing list pgsql-bugs

Hello, so I've made some researches on how does this case is dealt with in Oracle and found the following document : 

https://www.doag.org/formes/pubfiles/6315126/2014-DB-Jonathan_Lewis-Calculating_Join_Selectivity-Manuskript.pdf

The issue is the number of distinct values for nd2, as we know that the number of distinct values for b.id is going to be 1 (because of filtering on attrib), not 1000.

In the document they explain the following for calculation of the number of distinct values on a table in a join.

In a query like this :

select * from t1,t2 

where T1.mod_300 = t2.mod_200

and t1.date_1000=<constant>

the selectivity is this :

t1 has 1,000,000 rows (number of rows) call this nr 

mod_300 has 300 distinct values (number of distinct) call this nd 

date_1000 = {constant} returns a sample of 1,000 rows call this s 

The expected number of distinct values for mod_300 in the sample will be: nd * (1 - power(1 - s/nr, nr/nd)) In our case, 300 * (1 - power(1 - 1000/1000000, 1000000/1000)) = 289.3156   

If we apply the same reasoning to the query I posted we would get 

SELECT * FROM T1,T2 

where T1.id = T2.parent_id

and T1.attrib='BEL'

we get : 

nr =1000

nd = 1000

s = 1

so expected number of distinct values 1000* (1 - (1-1/1000)^(1000/1000)) = 1000*(1-0,999)=1 

With nd2 corrected like this the result should be better, as the calculated selectivity is then 1*1000*(1/18)=56 far more close to the reality than before 

Hope this can help,

best regards,

Le mer. 2 déc. 2020 à 23:33, Tom Lane <tgl@sss.pgh.pa.us> a écrit :

[ please keep the list cc'd ]

Bertrand Guillaumin <bertrand.guillaumin@gmail.com> writes:
> I've managed to reproduce the bug but only in the join case not with the in
> subquery (it uses hash join semi which works) with the following test case
> :
> create table work.test_bug_hash as SELECT id, case when id <= 600 then 100
>  when id <=800 then 200  when id <=875 then 300  when id<=950 then 400
>  when id<=960 then 500  when id<=970 then 600  when id<=980 then 700  when
> id<=990 then 800 when id =991 then 900 when id=992 then 910 when id=993
> then 920 when id=994 then 930 when id=995 then 940 when id=996 then 950
> when id=997 then 960 when id =998 then 970 when id=999 then 980 else 990
> end as parent_id, null as attrib from (select generate_series(1,1000) as
> id) alias0;

> update work.test_bug_hash set attrib='BEL' where id=300;

> analyze work.test_bug_hash;

> explain select * from work.test_bug_hash a, work.test_bug_hash b where
> a.parent_id=b.id and b.attrib='BEL';

Hmm.  Trying this on HEAD, the join and IN forms both estimate rows=1,
which is no doubt because recent versions of eqjoinsel() clamp the
semijoin selectivity estimate to be not more than the plain join
selectivity estimate ... which is logically correct, but in this case
it replaces a somewhat-okay estimate with a not-very-good one.

Anyway, the estimate you're getting from the "a = (select ...)" form
is the responsibility of var_eq_non_const, which has no idea what value
might come out of the sub-select, so it falls back to this logic:

        /*
         * Search is for a value that we do not know a priori, but we will
         * assume it is not NULL.  Estimate the selectivity as non-null
         * fraction divided by number of distinct values, so that we get a
         * result averaged over all possible values whether common or
         * uncommon.  (Essentially, we are assuming that the not-yet-known
         * comparison value is equally likely to be any of the possible
         * values, regardless of their frequency in the table.  Is that a good
         * idea?)
         */

Meanwhile, in the join or semijoin cases, the issue is that
eqjoinsel_inner has an MCV list for the parent_id side, but not
for the id side (because the latter is unique so it has no MCVs).
So it falls back on this logic:

        /*
         * We do not have MCV lists for both sides.  Estimate the join
         * selectivity as MIN(1/nd1,1/nd2)*(1-nullfrac1)*(1-nullfrac2). This
         * is plausible if we assume that the join operator is strict and the
         * non-null values are about equally distributed: a given non-null
         * tuple of rel1 will join to either zero or N2*(1-nullfrac2)/nd2 rows
         * of rel2, so total join rows are at most
         * N1*(1-nullfrac1)*N2*(1-nullfrac2)/nd2 giving a join selectivity of
         * not more than (1-nullfrac1)*(1-nullfrac2)/nd2. By the same logic it
         * is not more than (1-nullfrac1)*(1-nullfrac2)/nd1, so the expression
         * with MIN() is an upper bound.  Using the MIN() means we estimate
         * from the point of view of the relation with smaller nd (since the
         * larger nd is determining the MIN).  It is reasonable to assume that
         * most tuples in this rel will have join partners, so the bound is
         * probably reasonably tight and should be taken as-is.
         *
         * XXX Can we be smarter if we have an MCV list for just one side? It
         * seems that if we assume equal distribution for the other side, we
         * end up with the same answer anyway.
         */

In the case at hand, with nd1=18, nd2=1000, we'll come out with a
selectivity of 1/1000 which results in nrows = 1.

Maybe it'd be better to do something else here, but I'm not sure what.
All of these stats-free estimates are just rules of thumb and sometimes
go wrong.  Still, the case of one side of the join being unique and
the other not has to be pretty common, so it'd be nice to make it better.

                        regards, tom lane