Interesting performance behaviour - Mailing list pgsql-performance

#postgresql on Freenode recommended I post this here.

I'm seeing some odd behaviour with LIMIT. The query plans are included
here, as are the applicable table and index definitions. All table,
index, and query information can be found in a standard dbmail 1.2.6
install, if anyone wants to try setting up an exactly similar system.

Version: PostgreSQL 7.4.3 on i386-pc-linux-gnu, compiled by GCC
i386-linux-gcc (GCC) 3.3.4 (Debian 1:3.3.4-3)
OS: Debian Linux, "unstable" tree

Some settings that I was told to include (as far as I am aware, these
are debian default values):
shared_buffers = 1000
sort_mem = 1024
effective_cache_size = 1000


Table/index definitions:

                                       Table "public.messages"
    Column     |              Type              |                     Modifiers
---------------+--------------------------------+----------------------------------------------------
 message_idnr  | bigint                         | not null default
nextval('message_idnr_seq'::text)
 mailbox_idnr  | bigint                         | not null default 0
 messagesize   | bigint                         | not null default 0
 seen_flag     | smallint                       | not null default 0
 answered_flag | smallint                       | not null default 0
 deleted_flag  | smallint                       | not null default 0
 flagged_flag  | smallint                       | not null default 0
 recent_flag   | smallint                       | not null default 0
 draft_flag    | smallint                       | not null default 0
 unique_id     | character varying(70)          | not null
 internal_date | timestamp(6) without time zone |
 status        | smallint                       | not null default 0
 rfcsize       | bigint                         | not null default 0
 queue_id      | character varying(40)          | not null default
''::character varying
Indexes:
    "messages_pkey" primary key, btree (message_idnr)
    "idx_mailbox_idnr_queue_id" btree (mailbox_idnr, queue_id)
Foreign-key constraints:
    "ref141" FOREIGN KEY (mailbox_idnr) REFERENCES
mailboxes(mailbox_idnr) ON UPDATE CASCADE ON DELETE CASCADE




EXPLAIN ANALYZE results:


 EXPLAIN ANALYZE SELECT message_idnr FROM messages WHERE mailbox_idnr
= 1746::bigint AND status<2::smallint AND seen_flag = 0 AND unique_id
!= '' ORDER BY message_idnr ASC LIMIT 1;
                                                                QUERY PLAN

-------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..848.36 rows=1 width=8) (actual
time=1173.949..1173.953 rows=1 loops=1)
   ->  Index Scan using messages_pkey on messages
(cost=0.00..367338.15 rows=433 width=8) (actual
time=1173.939..1173.939 rows=1 loops=1)
         Filter: ((mailbox_idnr = 1746::bigint) AND (status <
2::smallint) AND (seen_flag = 0) AND ((unique_id)::text <> ''::text))
 Total runtime: 1174.012 ms


EXPLAIN ANALYZE SELECT message_idnr FROM messages WHERE mailbox_idnr =
1746::bigint AND status<2::smallint AND seen_flag = 0 AND unique_id !=
'' ORDER BY message_idnr ASC ;
                                                                   QUERY PLAN

------------------------------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=2975.42..2976.50 rows=433 width=8) (actual
time=2.357..2.545 rows=56 loops=1)
   Sort Key: message_idnr
   ->  Index Scan using idx_mailbox_idnr_queue_id on messages
(cost=0.00..2956.46 rows=433 width=8) (actual time=0.212..2.124
rows=56 loops=1)
         Index Cond: (mailbox_idnr = 1746::bigint)
         Filter: ((status < 2::smallint) AND (seen_flag = 0) AND
((unique_id)::text <> ''::text))
 Total runtime: 2.798 ms


I see a similar speedup (and change in query plan) using "LIMIT 1
OFFSET <anything besides 0>".