Optimization disaster - Mailing list pgsql-general

I have a web application running since one year on postgres 7.1.3
with good performance.
Now suddenly a query takes huge amounts of time: I tried to turn of
SEQ_SCAN, and it was fast again.

The following Query needs about 0,2 seconds with SEQ_SCAN set to OFF
and 150 seconds with SEQ_SCAN set to ON:

EXPLAIN
SELECT DISTINCT location_elem_id, locationseason_id, valid_from ,
valid_until, startday_exclude FROM bc_quicktravel
WHERE valid_until >= '2002-10-17' AND valid_from <= '2003-02-13' AND
attrib_id < 0
     AND location_elem_id IN (SELECT elem_id FROM bc_catalog_x_elem
         WHERE catalog_id IN

(186827,54786,186724,186829,73115,186831,186726,798429,186833,1368557,186728,186835,186837,186730,1821382,75083,297219,186732,63533,186781,75078,186736,902810,129859,1178799,186750,75281,1387815,54786,1368557,297219,1178799,936688,55706,132578,408097,132576,136852,160655,160657,160653,160665,73110,73115,1821382,1476580,1309559,1303367,1202899,1179539,1106603,1140768,950925,798429,902810,466934,334726,288050,197983,187203,186781,186783,186789,0,3011678,68214,54686,68414,68419)
         AND active_from_time < '2002-10-16 23:59:59 +0200'
         AND active_until_time > '2002-10-16 23:59:59 +0200'
         AND elem_active_and_released = 't'
         AND elem_type = 'location')
     AND (package_elem_id <= 0
         OR package_elem_id IN (SELECT elem_id FROM bc_catalog_x_elem
             WHERE catalog_id IN

(186827,54786,186724,186829,73115,186831,186726,798429,186833,1368557,186728,186835,186837,186730,1821382,75083,297219,186732,63533,186781,75078,186736,902810,129859,1178799,186750,75281,1387815,54786,1368557,297219,1178799,936688,55706,132578,408097,132576,136852,160655,160657,160653,160665,73110,73115,1821382,1476580,1309559,1303367,1202899,1179539,1106603,1140768,950925,798429,902810,466934,334726,288050,197983,187203,186781,186783,186789,0,3011678,68214,54686,68414,68419)
             AND active_from_time < '2002-10-16 23:59:59 +0200'
             AND active_until_time > '2002-10-16 23:59:59 +0200'
             AND elem_active_and_released = 't'
             AND elem_type = 'travelpack')
         )
     AND valid_until > '2002-10-16 23:59:59 +0200'
     AND package_elem_id < 0
ORDER BY location_elem_id, valid_from
;


(1) I get this with without SEQ_SCAN set to ON (150 sec):

Unique  (cost=1946377.12..1946383.16 rows=48 width=35)
   ->  Sort  (cost=1946377.12..1946377.12 rows=483 width=35)
         ->  Index Scan using quicktravel_inx011 on bc_quicktravel
(cost=0.00..1946355.60 rows=483 width=35)
               SubPlan
                 ->  Materialize  (cost=520.03..520.03 rows=24 width=4)
                       ->  Seq Scan on bc_catalog_x_elem
(cost=0.00..520.03 rows=24 width=4)
                 ->  Seq Scan on bc_catalog_x_elem  (cost=0.00..520.03
rows=455 width=4)

(2) I get this with without SEQ_SCAN set to OFF (0,2 sec):

Unique  (cost=1677.70..1677.71 rows=1 width=36)
   ->  Sort  (cost=1677.70..1677.70 rows=1 width=36)
         ->  Index Scan using quicktravel_inx011 on bc_quicktravel
(cost=0.00..1677.69 rows=1 width=36)
               SubPlan
                 ->  Materialize  (cost=837.80..837.80 rows=25 width=4)
                       ->  Index Scan using bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey on bc_catalog_x_elem
(cost=0.00..837.80 rows=25 width=4)
                 ->  Materialize  (cost=837.80..837.80 rows=371 width=4)
                       ->  Index Scan using bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey,
bc_catalog_x_elem_pkey, bc_catalog_x_elem_pkey on bc_catalog_x_elem
(cost=0.00..837.80 rows=371 width=4)

So the
                 ->  Seq Scan on bc_catalog_x_elem  (cost=0.00..520.03
rows=455 width=4)

in (1) seems to be wrong...

I do a VACUUM ANALYZE regularly.

What's wrong? I don't want to turn off SEQ_SCAN, because many other
queries will suffer.

Dietrich