# Re: [HACKERS] <> join selectivity estimate question

```On Sat, Mar 18, 2017 at 6:14 AM, Tom Lane <t...@sss.pgh.pa.us> wrote:
> After a bit more thought, it seems like the bug here is that "the
> fraction of the LHS that has a non-matching row" is not one minus
> "the fraction of the LHS that has a matching row".  In fact, in
> this example, *all* LHS rows have both matching and non-matching
> RHS rows.  So the problem is that neqjoinsel is doing something
> that's entirely insane for semijoin cases.
>
> It would not be too hard to convince me that neqjoinsel should
> simply return 1.0 for any semijoin/antijoin case, perhaps with
> some kind of discount for nullfrac.  Whether or not there's an
> equal row, there's almost always going to be non-equal row(s).
> Maybe we can think of a better implementation but that seems
> like the zero-order approximation.```
```
Right.  If I temporarily hack neqjoinsel() thus:

result = 1.0 - result;
+
+       if (jointype == JOIN_SEMI)
+               result = 1.0;
+
PG_RETURN_FLOAT8(result);
}

... then I obtain sensible row estimates and the following speedups
for TPCH Q21:

8 workers = 8.3s -> 7.8s
7 workers = 8.2s -> 7.9s
6 workers = 8.5s -> 8.2s
5 workers = 8.9s -> 8.5s
4 workers = 9.5s -> 9.1s
3 workers = 39.7s -> 9.9s
2 workers = 36.9s -> 11.7s
1 worker  = 38.2s -> 15.0s
0 workers = 47.9s -> 24.7s

The plan is similar to the good plan from before even at lower worker
counts, but slightly better because the aggregation has been pushed
under the Gather node.  See attached.

--
Thomas Munro
http://www.enterprisedb.com
```
```
QUERY PLAN

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit  (cost=2201513.85..2201514.10 rows=100 width=34) (actual
time=9063.236..9063.250 rows=100 loops=1)
->  Sort  (cost=2201513.85..2201538.56 rows=9882 width=34) (actual
time=9063.234..9063.242 rows=100 loops=1)
Sort Key: (count(*)) DESC, supplier.s_name
Sort Method: top-N heapsort  Memory: 38kB
->  Finalize GroupAggregate  (cost=2199767.92..2201136.17 rows=9882
width=34) (actual time=9041.788..9061.662 rows=3945 loops=1)
Group Key: supplier.s_name
->  Gather Merge  (cost=2199767.92..2200987.95 rows=9880
width=34) (actual time=9041.743..9059.098 rows=17026 loops=1)
Workers Planned: 4
Workers Launched: 4
->  Partial GroupAggregate  (cost=2198767.86..2198811.09
rows=2470 width=34) (actual time=9026.843..9029.020 rows=3405 loops=5)
Group Key: supplier.s_name
->  Sort  (cost=2198767.86..2198774.04 rows=2470
width=26) (actual time=9026.835..9027.507 rows=7781 loops=5)
Sort Key: supplier.s_name
Sort Method: quicksort  Memory: 1067kB
->  Nested Loop Anti Join
(cost=558157.24..2198628.67 rows=2470 width=26) (actual time=4200.001..8975.908
rows=7781 loops=5)
->  Hash Join
(cost=558156.67..2143996.29 rows=2470 width=42) (actual time=4198.642..8624.528
rows=139326 loops=5)
Hash Cond: (l1.l_orderkey =
orders.o_orderkey)
->  Nested Loop Semi Join
(cost=2586.15..1585196.80 rows=199953 width=50) (actual time=14.685..4251.092
rows=288319 loops=5)
->  Hash Join
(cost=2585.58..1425767.03 rows=199953 width=42) (actual time=14.635..3160.867
rows=298981 loops=5)
Hash Cond:
(l1.l_suppkey = supplier.s_suppkey)
->  Parallel Seq Scan
on lineitem l1  (cost=0.00..1402436.29 rows=4998834 width=16) (actual
time=0.056..2355.120 rows=7585870 loops=5)
Filter:
(l_receiptdate > l_commitdate)
Rows Removed by
Filter: 4411341
->  Hash
(cost=2535.58..2535.58 rows=4000 width=30) (actual time=14.470..14.470
rows=3945 loops=5)
Buckets: 4096
Batches: 1  Memory Usage: 279kB
->  Nested Loop
(cost=79.29..2535.58 rows=4000 width=30) (actual time=1.807..13.024 rows=3945
loops=5)
->  Seq
Scan on nation  (cost=0.00..1.31 rows=1 width=4) (actual time=0.024..0.031
rows=1 loops=5)

Filter: (n_name = 'ETHIOPIA'::bpchar)
Rows
Removed by Filter: 24
->  Bitmap
Heap Scan on supplier  (cost=79.29..2494.27 rows=4000 width=38) (actual
time=1.776..11.984 rows=3945 loops=5)

Recheck Cond: (s_nationkey = nation.n_nationkey)
Heap
Blocks: exact=1898
->
Bitmap Index Scan on idx_supplier_nation_key  (cost=0.00..78.29 rows=4000
width=0) (actual time=1.260..1.260 rows=3945 loops=5)

Index Cond: (s_nationkey = nation.n_nationkey)
->  Index Scan using
idx_lineitem_orderkey on lineitem l2  (cost=0.56..21.18 rows=159 width=16)
(actual time=0.003..0.003 rows=1 loops=1494906)
Index Cond:
(l_orderkey = l1.l_orderkey)
Filter: (l_suppkey <>
l1.l_suppkey)
Rows Removed by
Filter: 0
->  Hash
(cost=463721.01..463721.01 rows=7347961 width=4) (actual
time=4140.371..4140.371 rows=7309184 loops=5)
Buckets: 8388608  Batches: 1
Memory Usage: 322500kB
->  Seq Scan on orders
(cost=0.00..463721.01 rows=7347961 width=4) (actual time=0.035..2674.999
rows=7309184 loops=5)
Filter: (o_orderstatus
= 'F'::bpchar)
Rows Removed by
Filter: 7690816
->  Index Scan using
idx_lineitem_orderkey on lineitem l3  (cost=0.56..21.58 rows=53 width=16)
(actual time=0.002..0.002 rows=1 loops=696628)
Index Cond: (l_orderkey =
l1.l_orderkey)
Filter: ((l_receiptdate >
l_commitdate) AND (l_suppkey <> l1.l_suppkey))
Rows Removed by Filter: 1
Planning time: 4.914 ms
Execution time: 9162.742 ms
```
```--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
```
• Re: [HACKERS] <> join selectivity estimate question Thomas Munro