Query Performance

Hello List,

I have a query which use to run very fast now has turn into show stopper .

PostgreSQL:8.2

explain analyze select user_name,A.user_id, dnd_window_start, dnd_window_stop, B.subs as subs, B.city_id as city_id, B.source_type as source_type from
users A left join user_subscriptions B on (A.user_id=B.user_id)
where A.user_id in (select user_id from subs_feed where feed_id=1411 and f_sms='t')
;

Nested Loop Left Join (cost=986325.88..1094601.47 rows=11148 width=55) (actual time=132635.994..1590487.280 rows=609070 loops=1)
-> Nested Loop (cost=986325.88..1062280.53 rows=11148 width=26) (actual time=132630.057..1398299.117 rows=609070 loops=1)
-> HashAggregate (cost=986325.88..986437.36 rows=11148 width=4) (actual time=132591.648..133386.651 rows=609070 loops=1)
-> Bitmap Heap Scan on subs_feed (cost=16316.71..985194.44 rows=452576 width=4) (actual time=20199.571..131566.494 rows=609070 loops=1)
Recheck Cond: (feed_id = 1411)
Filter: f_sms
-> Bitmap Index Scan on feed_user_id (cost=0.00..16203.57 rows=681933 width=0) (actual time=19919.512..19919.512 rows=616900 loops=1)
Index Cond: (feed_id = 1411)
-> Index Scan using users_pkey on users a (cost=0.00..6.79 rows=1 width=26) (actual time=2.073..2.074 rows=1 loops=609070)
Index Cond: (a.user_id = subs_feed.user_id)
-> Index Scan using user_subscriptions_user_id_pk on user_subscriptions b (cost=0.00..2.89 rows=1 width=33) (actual time=0.312..0.313 rows=1 loops=609070)
Index Cond: (a.user_id = b.user_id)
Total runtime: 1590755.918 ms
(13 rows)

This query runs almost half an hour. It is evident that nested loop is taking most of the time (approx 27 minutes).

Any tips would be very useful.

Also these table have below count:

select relname,reltuples from pg_class where relname in ('users','user_subscriptions','subs_feed');
relname | reltuples
--------------------+-------------
user_subscriptions | 3758304
users | 1.95481e+07
subs_feed | 2.96492e+07

select n_tup_ins,n_tup_upd,n_tup_del,last_vacuum,last_analyze from pg_stat_user_tables where relname='user_subscriptions';
n_tup_ins | n_tup_upd | n_tup_del | last_vacuum | last_analyze
-----------+-----------+-----------+----------------------------------+----------------------------------
86371397 | 25865942 | 0 | 2009-12-06 23:00:36.355251+05:30 | 2009-12-06 23:00:36.355251+05:30

Thanks in advance for help ...