To: pgsql-hackers@postgreSQL.org
Subject: eqjoinsel_semi still sucks ...
Date: Wed, 02 May 2012 12:34:15 -0400
Message-ID: <13290.1335976455@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

I looked into Maxim Boguk's complaint of bad estimation of antijoin size:
http://archives.postgresql.org/pgsql-general/2012-05/msg00033.php

I can reproduce what I think the problem is in the regression database.
We do okay with this:

regression=# explain analyze select * from tenk1 a where not exists(select 1 from tenk1 b where a.thousand = b.unique2);
                                                                    QUERY PLAN                                                                     
---------------------------------------------------------------------------------------------------------------------------------------------------
 Hash Anti Join  (cost=395.26..1003.26 rows=1 width=244) (actual time=264.324..264.324 rows=0 loops=1)
   Hash Cond: (a.thousand = b.unique2)
   ->  Seq Scan on tenk1 a  (cost=0.00..458.00 rows=10000 width=244) (actual time=0.050..47.798 rows=10000 loops=1)
   ->  Hash  (cost=270.26..270.26 rows=10000 width=4) (actual time=129.420..129.420 rows=10000 loops=1)
         Buckets: 1024  Batches: 1  Memory Usage: 274kB
         ->  Index Only Scan using tenk1_unique2 on tenk1 b  (cost=0.00..270.26 rows=10000 width=4) (actual time=0.422..65.480 rows=10000 loops=1)
               Heap Fetches: 0
 Total runtime: 267.732 ms
(8 rows)

but not so okay when a filter condition is added inside the sub-select:

regression=# explain analyze select * from tenk1 a where not exists(select 1 from tenk1 b where a.thousand = b.unique2 and b.two = 0);
                                                      QUERY PLAN                                                      
----------------------------------------------------------------------------------------------------------------------
 Hash Anti Join  (cost=545.50..1091.00 rows=1 width=244) (actual time=123.713..265.185 rows=5090 loops=1)
   Hash Cond: (a.thousand = b.unique2)
   ->  Seq Scan on tenk1 a  (cost=0.00..458.00 rows=10000 width=244) (actual time=0.048..46.685 rows=10000 loops=1)
   ->  Hash  (cost=483.00..483.00 rows=5000 width=4) (actual time=123.483..123.483 rows=5000 loops=1)
         Buckets: 1024  Batches: 1  Memory Usage: 137kB
         ->  Seq Scan on tenk1 b  (cost=0.00..483.00 rows=5000 width=4) (actual time=0.059..91.405 rows=5000 loops=1)
               Filter: (two = 0)
               Rows Removed by Filter: 5000
 Total runtime: 284.889 ms
(9 rows)

Now, eqjoinsel_semi is correctly estimating that the condition
a.thousand = b.unique2 is unselective in itself: all values of
a.thousand will have join partners in the first case.  The problem comes
in trying to account for the additional filter condition.  The heuristic
we're currently using is to reduce the number of distinct values assumed
for the inner variable according to the selectivity of the additional
conditions.  In this case, though, that results in reducing ndistinct
for b.unique2 from 10000 to 5000, which is still more than ndistinct for
a.thousand (i.e., 1000), so the final selectivity estimate doesn't
change at all.  Oops.

On reflection I think that the idea of clamping ndistinct beforehand is
just wrong, and what we ought to do instead is apply a multiplier to the
selectivity estimate afterwards.  In the case of a base rel we could
just multiply by the selectivity of its baserestrictinfo list.  For join
rels it's a bit harder to guess how much a given input relation might
have been decimated, but if the join's estimated size is smaller than
the output size of the base rel the correlation var came from, we could
multiply by that ratio (on top of whatever correction came from the base
rel's restriction clauses).

Thoughts?

			regards, tom lane