Indexing foreign keys

Due to reasons that everyone can probably intuit, we are porting a large
server application from IBM Informix to PG. However, things that take
milliseconds in IFX are taking HOURS (not joking) in PG. I *think* I
may have come across some reasons why, but I would like to see if anyone
else has an opinion. I could not find anything relevant in docs (but if
it is there, please point me to it).

Let me give an example of one of the problems...

I have a table that utilizes 2 foreign keys. It has 400000 records of
approximately 512 bytes each (mostly text, except for the keys). When I
run a specific query on it, it takes 8000ms to complete, and it always
does a full scan.

I "assumed" that since I did not have to create an index on those
foreign key fields in IFX, that I did not have to in PG. However, just
for kicks, I created an index on those 2 fields, and my query time
(after the first, longer attempt, which I presume is from loading an
index) went from 8000ms to 100ms.

So, do we ALWAYS have to create indexes for foreign key fields in PG?
Do the docs say this? (I couldn't find the info.)

I will create other threads for my other issues.

Thanks!

--
Matt Mello