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(at)scn(dot)ru