Stability of planner estimates given multiple redundant clauses - Mailing list pgsql-hackers

I've been looking into Paolo Tavalazzi's recent report of discrepancies
in the planner's estimates and resulting plan choices when the order of
FROM-clause entries is changed.  Here is a boiled-down example:

paolo=# explain select * from seat, spettacoli, tran
paolo-# where tran.id = 42 and spettacoli.system = tran.system and
paolo-# tran.system = seat.system;                                               QUERY PLAN
-----------------------------------------------------------------------------------------------------------Hash Join
(cost=2220.72..231242.86rows=9735500 width=408)  Hash Cond: ("outer".system = "inner".system)  ->  Seq Scan on seat
(cost=0.00..11028.46rows=362446 width=117)  ->  Hash  (cost=2149.46..2149.46 rows=1703 width=291)        ->  Nested
Loop (cost=0.00..2149.46 rows=1703 width=291)              ->  Index Scan using tran_id2_idx on tran  (cost=0.00..10.00
rows=2width=183)                    Index Cond: (id = 42)              ->  Index Scan using spet_system_idx on
spettacoli (cost=0.00..1065.98 rows=300 width=108)                    Index Cond: (spettacoli.system = "outer".system)
 
(9 rows)

paolo=# explain select * from seat, tran, spettacoli
paolo-# where tran.id = 42 and spettacoli.system = tran.system and
paolo-# tran.system = seat.system;                                            QUERY PLAN
----------------------------------------------------------------------------------------------------Merge Join
(cost=25710.35..255604.83rows=14794210 width=408)  Merge Cond: ("outer".system = "inner".system)  ->  Sort
(cost=16883.32..16926.76rows=17375 width=300)        Sort Key: tran.system        ->  Hash Join  (cost=10.00..13930.56
rows=17375width=300)              Hash Cond: ("outer".system = "inner".system)              ->  Seq Scan on seat
(cost=0.00..11028.46rows=362446 width=117)              ->  Hash  (cost=10.00..10.00 rows=2 width=183)
 ->  Index Scan using tran_id2_idx on tran  (cost=0.00..10.00 rows=2 width=183)                          Index Cond:
(id= 42)  ->  Sort  (cost=8827.02..8967.22 rows=56079 width=108)        Sort Key: spettacoli.system        ->  Seq Scan
onspettacoli  (cost=0.00..1734.79 rows=56079 width=108)
 
(13 rows)

The reason for the difference in row-count estimates turns out to be the
redundant clause "spettacoli.system = seat.system" that is generated by
implied equality deduction.  We generate this clause so that we can
investigate the alternative of joining spettacoli to seat first.
However, when we come to estimate the size of the three-way join
relation, we will have two redundant clauses associated with the join.
For example if the join path being considered is {{seat, tran}, spettacoli}
then both spettacoli.system = tran.system and spettacoli.system =
seat.system will be available join clauses.  The planner understands
that the two clauses are redundant and shouldn't both be counted in
estimating the selectivity of the join.  However, its choice of which
one it *should* count is arbitrary.  It turns out to depend on
processing order and thereby on the order of the FROM items.  In Paolo's
example, the estimates derived from the two clauses are different and so
the row counts and plan come out different.

It's not clear that this is a bug, exactly; it could be seen as the
inevitable consequence of planning uncertainties.  But it's annoying.

As of CVS tip there is already some code in
remove_redundant_join_clauses() that chooses which of two redundant
clauses to eliminate on the basis of which one is cheaper to evaluate.
This doesn't affect most simple cases because all simple comparisons are
costed alike (one cpu_operator_cost).  I am toying with the idea of
adding a further test to prefer the clause with smaller estimated
selectivity, if they are different.  This might seem pretty ad hoc
but it's not completely out of the blue.  I can prove mathematically
that the smaller selectivity is an upper bound for the correct value in
some restricted cases (eg, when keys are evenly distributed in each
table).  I don't have a general proof, but hand-waving: the join of the
first two tables could only remove rows from their Cartesian product,
and estimating the selectivity of the 3-way join on the basis of either
individual join clause is like assuming that the first join is
Cartesian, so it's an upper bound for the correct value.

Comments?  Anyone see any fatal problems, or have a better idea what to
do?
        regards, tom lane