Join performance

Hello,

I'm building a kind of messaging/forum application with postgresql. There
are users which will send each others messages, send messages to forums,
etc.
I would like to put the messages in folders, so each user has several
folders (inbox, sent...), and forums are also folders.

A message will appear in the sender's "sent" folder and the receiver's
inbox, or receiving forum folder.

There are two ways I can do this :
- either by placing two folder fields (outbox_folder_id and
receiving_folder_id) in the messages table, which can both point to a
folder or be null. When a user sends a message to another user/folder,
these fields are set appropriately.
- or by having a messages table, and a link table linking messages to
folders.

I have built a test database with about 20000 messages in 2000 folders
(10 messages per folder).

Finding all the messages in a folder takes more than 600 times longer
with the link table than with the single table approach (66 ms vs. 0.12
ms).

Is this normal ? I have checked explain analyze and it uses indexes in
all cases. The query plans look right to me.