unpredictable cost in explain

Hello !

Please help me, I tried to make request run faster

1st request (original):
  SELECT dy.*,  sat.dton as satdton
  FROM dyBilling dy, saType sat
  WHERE dy.dt>='20-12-2004' AND dy.dt<='20-12-2004' AND
       dy.servid=sat.servid AND dy.dt BETWEEN sat.dton AND sat.dtoff

it have execution time 4174,514 ms  and
following query plan:
 Nested Loop  (cost=0.00..11.57 rows=1 width=41)
   ->  Index Scan using dybilling_dt_servid_sid on dybilling dy
(cost=0.00..5.69 rows=1 width=37)
         Index Cond: ((dt >= '20-12-2004'::date) AND (dt <=
'20-12-2004'::date))
   ->  Index Scan using satype_dton_dtoff_servid on satype sat
(cost=0.00..5.86 rows=1 width=12)
         Index Cond: (("outer".dt >= sat.dton) AND ("outer".dt <=
sat.dtoff) AND ("outer".servid = sat.servid))


2nd request:
  SELECT dy.*,  sat.dton as satdton
  FROM dyBilling dy, saType sat
  WHERE dy.dt='20-12-2004' AND   --  <- diff only here
       dy.servid=sat.servid AND dy.dt BETWEEN sat.dton AND sat.dtoff

it have execution time 106,340 ms  and
following query plan:
 Merge Join  (cost=3973.95..4037.21 rows=195 width=41)
   Merge Cond: ("outer".servid = "inner".servid)
   Join Filter: (("outer".dt >= "inner".dton) AND ("outer".dt <=
"inner".dtoff))
   ->  Sort  (cost=3451.52..3453.99 rows=989 width=37)
         Sort Key: dy.servid
         ->  Index Scan using dybilling_dt_servid_sid on dybilling dy
(cost=0.00..3402.32 rows=989 width=37)
               Index Cond: (dt = '20-12-2004'::date)
   ->  Sort  (cost=522.43..538.58 rows=6460 width=12)
         Sort Key: sat.servid
         ->  Seq Scan on satype sat  (cost=0.00..113.60 rows=6460 width=12)

So,
                    Estimated Cost          Real Execution Time, ms
     1st request    0.00..11.57             4174,514
     2ns request    3973.95..4037.21        106,340

Why?  Is this EXPLAIN's behaviour correct ?
Results reproducable any number of times, no any caching effects etc.

Some maybe useful info:
isbs=# select count(*) from dyBilling;
---------
 1144078

isbs=# select count(*) from saType;
-------
  6472

isbs=# select version();
---------------------------------------------------------------------
 PostgreSQL 7.4.1 on i386-unknown-freebsd4.7, compiled by GCC 2.95.4


Thanks.


--
 best regards,
Ruslan A Dautkhanov  rusland@scn.ru