planner regression in 8.4 (from 8.1)

I have a query which performs much better on 8.1.19 than on 8.4.2, unless I=
 add "offset 0" to the subqueries. I believe this is due to miscalculating =
the expected row count of nest loop joins. I cannot give you my data, but I=
 can give you the query and the plans. Let me know if anything else would b=
e helpful.

The query as I used it on 8.1:

SELECT SUM(machines.quota_purchased), license_type_id FROM sm_pro_keys, mac=
hines=20
WHERE NOT deleted AND sm_pro_keys.machine_id =3D machines.id AND=20
machines.quota_purchased > 0 AND machines.user_id IN=20
( SELECT id FROM users WHERE NOT deleted AND user_group_id IN=20
( SELECT id FROM user_groups WHERE pro_partner_id IN=20
( SELECT id FROM pro_partners WHERE tree_sortkey BETWEEN=20
'000000000000000110000000000000001111010011011010' AND=20
tree_right('000000000000000110000000000000001111010011011010') )
 ) ) GROUP BY license_type_id;

The modified query (the difference is the last line):

SELECT SUM(machines.quota_purchased), license_type_id FROM sm_pro_keys, mac=
hines=20
WHERE NOT deleted AND sm_pro_keys.machine_id =3D machines.id AND=20
machines.quota_purchased > 0 AND machines.user_id IN=20
( SELECT id FROM users WHERE NOT deleted AND user_group_id IN=20
( SELECT id FROM user_groups WHERE pro_partner_id IN=20
( SELECT id FROM pro_partners WHERE tree_sortkey BETWEEN=20
'000000000000000110000000000000001111010011011010' AND=20
tree_right('000000000000000110000000000000001111010011011010') )
  ) offset 0) GROUP BY license_type_id;


On 8.1, the plan looks like this:

 HashAggregate  (cost=3D23040.78..23040.79 rows=3D1 width=3D12) (actual tim=
e=3D36.642..36.643 rows=3D1 loops=3D1)
   ->  Nested Loop  (cost=3D20911.79..23040.77 rows=3D1 width=3D12) (actual=
 time=3D36.615..36.629 rows=3D1 loops=3D1)
         ->  Nested Loop  (cost=3D20911.79..23036.81 rows=3D1 width=3D12) (=
actual time=3D36.272..36.285 rows=3D1 loops=3D1)
               ->  HashAggregate  (cost=3D20911.79..20911.91 rows=3D12 widt=
h=3D4) (actual time=3D36.227..36.227 rows=3D1 loops=3D1)
                     ->  Nested Loop  (cost=3D10.44..20911.76 rows=3D12 wid=
th=3D4) (actual time=3D36.221..36.222 rows=3D1 loops=3D1)
                           ->  HashAggregate  (cost=3D10.44..10.45 rows=3D1=
 width=3D4) (actual time=3D36.073..36.073 rows=3D1 loops=3D1)
                                 ->  Nested Loop  (cost=3D4.21..10.44 rows=
=3D1 width=3D4) (actual time=3D36.058..36.065 rows=3D1 loops=3D1)
                                       ->  HashAggregate  (cost=3D4.21..4.2=
2 rows=3D1 width=3D4) (actual time=3D0.141..0.142 rows=3D1 loops=3D1)
                                             ->  Index Scan using pro_partn=
ers_tree_sortkey_idx on pro_partners  (cost=3D0.00..4.20 rows=3D1 width=3D4=
) (actual time=3D0.132..0.133 rows=3D1 loops=3D1)
                                                   Index Cond: ((tree_sortk=
ey >=3D B'000000000000000110000000000000001111010011011010'::bit varying) A=
ND (tree_sortkey <=3D B'000000000000000110000000000000001111010011011010111=
11111111111111111111111111111'::bit varying))
                                       ->  Index Scan using user_groups_pro=
_partner_id_idx on user_groups  (cost=3D0.00..6.19 rows=3D3 width=3D8) (act=
ual time=3D35.913..35.916 rows=3D1 loops=3D1)
                                             Index Cond: (user_groups.pro_p=
artner_id =3D "outer".id)
                           ->  Index Scan using users_user_groups_idx on us=
ers  (cost=3D0.00..20800.07 rows=3D8099 width=3D8) (actual time=3D0.142..0.=
143 rows=3D1 loops=3D1)
                                 Index Cond: (users.user_group_id =3D "oute=
r".id)
                                 Filter: (NOT deleted)
               ->  Index Scan using machines_sid_un on machines  (cost=3D0.=
00..177.01 rows=3D5 width=3D16) (actual time=3D0.042..0.055 rows=3D1 loops=
=3D1)
                     Index Cond: (machines.user_id =3D "outer".id)
                     Filter: (quota_purchased > 0)
         ->  Index Scan using sm_pro_keys_machine_id_idx on sm_pro_keys  (c=
ost=3D0.00..3.95 rows=3D1 width=3D8) (actual time=3D0.339..0.340 rows=3D1 l=
oops=3D1)
               Index Cond: (sm_pro_keys.machine_id =3D "outer".id)
 Total runtime: 36.794 ms
(21 rows)
On 8.4, the unmodified query looks like this:

 HashAggregate  (cost=3D193503.37..193503.82 rows=3D36 width=3D12) (actual =
time=3D3389.899..3389.900 rows=3D1 loops=3D1)
   ->  Hash Semi Join  (cost=3D178202.84..193475.12 rows=3D5649 width=3D12)=
 (actual time=3D1612.034..3389.861 rows=3D1 loops=3D1)
         Hash Cond: (machines.user_id =3D users.id)
         ->  Merge Join  (cost=3D142309.11..148916.54 rows=3D5649 width=3D1=
6) (actual time=3D1466.097..3317.794 rows=3D168536 loops=3D1)
               Merge Cond: (sm_pro_keys.machine_id =3D machines.id)
               ->  Index Scan using sm_pro_keys_machine_id_idx on sm_pro_ke=
ys  (cost=3D0.00..97619.86 rows=3D3086901 width=3D8) (actual time=3D0.059..=
1359.843 rows=3D3004929 loops=3D1)
               ->  Sort  (cost=3D142290.93..142535.59 rows=3D97866 width=3D=
16) (actual time=3D1466.024..1502.852 rows=3D168970 loops=3D1)
                     Sort Key: machines.id
                     Sort Method:  quicksort  Memory: 14062kB
                     ->  Seq Scan on machines  (cost=3D0.00..134178.56 rows=
=3D97866 width=3D16) (actual time=3D0.058..1354.628 rows=3D168911 loops=3D1)
                           Filter: ((NOT deleted) AND (quota_purchased > 0))
         ->  Hash  (cost=3D153.63..153.63 rows=3D2178408 width=3D4) (actual=
 time=3D0.207..0.207 rows=3D1 loops=3D1)
               ->  Nested Loop  (cost=3D4.58..153.63 rows=3D2178408 width=
=3D4) (actual time=3D0.203..0.204 rows=3D1 loops=3D1)
                     ->  HashAggregate  (cost=3D4.58..4.59 rows=3D1 width=
=3D4) (actual time=3D0.145..0.146 rows=3D1 loops=3D1)
                           ->  Nested Loop  (cost=3D2.28..4.57 rows=3D1 wid=
th=3D4) (actual time=3D0.142..0.143 rows=3D1 loops=3D1)
                                 ->  HashAggregate  (cost=3D2.28..2.29 rows=
=3D1 width=3D4) (actual time=3D0.093..0.093 rows=3D1 loops=3D1)
                                       ->  Index Scan using pro_partners_tr=
ee_sortkey_idx on pro_partners  (cost=3D0.00..2.28 rows=3D1 width=3D4) (act=
ual time=3D0.076..0.076 rows=3D1 loops=3D1)
                                             Index Cond: ((tree_sortkey >=
=3D B'000000000000000110000000000000001111010011011010'::bit varying) AND (=
tree_sortkey <=3D B'0000000000000001100000000000000011110100110110101111111=
1111111111111111111111111'::bit varying))
                                 ->  Index Scan using user_groups_pro_partn=
er_id_idx on user_groups  (cost=3D0.00..2.27 rows=3D1 width=3D8) (actual ti=
me=3D0.046..0.047 rows=3D1 loops=3D1)
                                       Index Cond: (user_groups.pro_partner=
_id =3D pro_partners.id)
                     ->  Index Scan using users_user_groups_idx on users  (=
cost=3D0.00..147.14 rows=3D152 width=3D8) (actual time=3D0.057..0.057 rows=
=3D1 loops=3D1)
                           Index Cond: (users.user_group_id =3D user_groups=
.id)
                           Filter: (NOT users.deleted)
 Total runtime: 3391.269 ms
(24 rows)


Note the nested loop with 2 million expected rows, though its inner nodes a=
re only expected to have 1 and 152 each.=20

The plan with the offset 0 clause looks like this:

 HashAggregate  (cost=3D28011.35..28011.50 rows=3D12 width=3D12) (actual ti=
me=3D0.158..0.158 rows=3D1 loops=3D1)
   ->  Nested Loop  (cost=3D27741.68..28011.29 rows=3D12 width=3D12) (actua=
l time=3D0.145..0.146 rows=3D1 loops=3D1)
         ->  Nested Loop  (cost=3D27741.68..27837.74 rows=3D200 width=3D12)=
 (actual time=3D0.129..0.130 rows=3D1 loops=3D1)
               ->  HashAggregate  (cost=3D27741.68..27743.68 rows=3D200 wid=
th=3D4) (actual time=3D0.071..0.071 rows=3D1 loops=3D1)
                     ->  Limit  (cost=3D4.58..153.67 rows=3D2207041 width=
=3D4) (actual time=3D0.068..0.069 rows=3D1 loops=3D1)
                           ->  Nested Loop  (cost=3D4.58..153.67 rows=3D220=
7041 width=3D4) (actual time=3D0.068..0.069 rows=3D1 loops=3D1)
                                 ->  HashAggregate  (cost=3D4.58..4.59 rows=
=3D1 width=3D4) (actual time=3D0.051..0.051 rows=3D1 loops=3D1)
                                       ->  Nested Loop  (cost=3D2.28..4.57 =
rows=3D1 width=3D4) (actual time=3D0.048..0.049 rows=3D1 loops=3D1)
                                             ->  HashAggregate  (cost=3D2.2=
8..2.29 rows=3D1 width=3D4) (actual time=3D0.033..0.033 rows=3D1 loops=3D1)
                                                   ->  Index Scan using pro=
_partners_tree_sortkey_idx on pro_partners  (cost=3D0.00..2.28 rows=3D1 wid=
th=3D4) (actual time=3D0.018..0.018 rows=3D1 loops=3D1)
                                                         Index Cond: ((tree=
_sortkey >=3D B'000000000000000110000000000000001111010011011010'::bit vary=
ing) AND (tree_sortkey <=3D B'000000000000000110000000000000001111010011011=
01011111111111111111111111111111111'::bit varying))
                                             ->  Index Scan using user_grou=
ps_pro_partner_id_idx on user_groups  (cost=3D0.00..2.27 rows=3D1 width=3D8=
) (actual time=3D0.014..0.014 rows=3D1 loops=3D1)
                                                   Index Cond: (user_groups=
.pro_partner_id =3D pro_partners.id)
                                 ->  Index Scan using users_user_groups_idx=
 on users  (cost=3D0.00..147.18 rows=3D152 width=3D8) (actual time=3D0.015.=
.0.015 rows=3D1 loops=3D1)
                                       Index Cond: (users.user_group_id =3D=
 user_groups.id)
                                       Filter: (NOT users.deleted)
               ->  Index Scan using machines_user_idx on machines  (cost=3D=
0.00..0.46 rows=3D1 width=3D16) (actual time=3D0.057..0.058 rows=3D1 loops=
=3D1)
                     Index Cond: (machines.user_id =3D users.id)
                     Filter: ((NOT machines.deleted) AND (machines.quota_pu=
rchased > 0))
         ->  Index Scan using sm_pro_keys_machine_id_idx on sm_pro_keys  (c=
ost=3D0.00..0.86 rows=3D1 width=3D8) (actual time=3D0.014..0.014 rows=3D1 l=
oops=3D1)
               Index Cond: (sm_pro_keys.machine_id =3D machines.id)
 Total runtime: 0.353 ms
(22 rows)


FWIW, I can get a similar execution speed in 8.4.2 by turning off hashjoins=
 and mergejoins. The estimate for the nested loop is still way off, but at =
least the offset 0 is keeping the plan better.

Anyway, we have our workaround, but I just wanted to make sure this would g=
et on a to-fix list. If I can provide anything else (you know, short of the=
 data to actually make a helpful test case), let me know.=