LIMIT confuses the planner (again)

Hello,

I am using PostgreSQL 8.3.7 and I am experiencing an issue similar to
the one I've already described some time ago:
http://archives.postgresql.org/pgsql-performance/2009-02/msg00261.php

Again, adding a LIMIT clause to a query, which is normally executing
very fast thanks to an index, makes it perform slow, because the planner
no longer uses the "correct" index.

I have the following table:

CREATE TABLE message (
   message_sid SERIAL PRIMARY KEY,
   from_profile_sid INT NOT NULL REFERENCES profile,
   to_profile_sid INT NOT NULL REFERENCES profile,
   sender_has_deleted BOOLEAN NOT NULL DEFAULT FALSE,
   receiver_has_deleted BOOLEAN NOT NULL DEFAULT FALSE,
   body TEXT,
   datetime TIMESTAMP NOT NULL DEFAULT NOW()
);


With the following conditional index:

CREATE INDEX message_to_profile_idx ON message (to_profile_sid) WHERE
NOT receiver_has_deleted;


The query to obtain the list of received messages of a profile is simple
and executes very fast, because of the index above:

db=# EXPLAIN ANALYZE SELECT
   *
FROM
   message
WHERE
   to_profile_sid = -1
AND
   NOT receiver_has_deleted
ORDER BY
   message_sid DESC;
                                                                 QUERY PLAN

-------------------------------------------------------------------------------------------------------------------------------------------
  Sort  (cost=11857.09..11866.19 rows=3640 width=277) (actual
time=0.317..0.319 rows=15 loops=1)
    Sort Key: message_sid
    Sort Method:  quicksort  Memory: 32kB
    ->  Bitmap Heap Scan on message  (cost=106.44..11641.78 rows=3640
width=277) (actual time=0.096..0.271 rows=15 loops=1)
          Recheck Cond: ((to_profile_sid = (-1)) AND (NOT
receiver_has_deleted))
          ->  Bitmap Index Scan on message_to_profile_idx
(cost=0.00..105.53 rows=3640 width=0) (actual time=0.056..0.056 rows=21
loops=1)
                Index Cond: (to_profile_sid = (-1))
  Total runtime: 0.383 ms
(8 rows)


Adding a LIMIT clause to exactly the same query slows its execution more
than 20'000 times:

db=# EXPLAIN ANALYZE SELECT
   *
FROM
   message
WHERE
   to_profile_sid = -1
AND
   NOT receiver_has_deleted
ORDER BY
   message_sid DESC LIMIT 20;

QUERY PLAN

----------------------------------------------------------------------------------------------------------------------------------------------------
  Limit  (cost=0.00..6513.60 rows=20 width=277) (actual
time=0.617..6576.539 rows=15 loops=1)
    ->  Index Scan Backward using message_pkey on message
(cost=0.00..1185474.32 rows=3640 width=277) (actual time=0.617..6576.522
rows=15 loops=1)
          Filter: ((NOT receiver_has_deleted) AND (to_profile_sid = (-1)))
  Total runtime: 6576.572 ms
(4 rows)


Just as I was advised in my recent post, I've already increased the
statistics of both fields all the way till 1000, analyzed the table and
reindexed the index:

ALTER TABLE message ALTER COLUMN to_profile_sid SET STATISTICS 1000;
ALTER TABLE message ALTER COLUMN receiver_has_deleted SET STATISTICS 1000;
ANALYZE message;
REINDEX index message_to_profile_idx;


This time, however, the steps above didn't affect the planner in any
way, it still refuses to use the index "message_to_profile_idx" when a
LIMIT is involved (for this particular value of to_profile_sid).

Here's some statistical data:

db=# SELECT COUNT(*) FROM message;
   count
---------
  1312213
(1 row)

db=# SELECT COUNT(*) FROM message WHERE to_profile_sid = -1;
  count
-------
   5604
(1 row)

db=# SELECT COUNT(*) FROM message WHERE to_profile_sid = -1 AND NOT
receiver_has_deleted;
  count
-------
     15
(1 row)

db=# SELECT COUNT(DISTINCT to_profile_sid) FROM message;
  count
-------
   8596
(1 row)

db=# SELECT AVG(length) FROM (SELECT to_profile_sid, COUNT(*) AS length
FROM message GROUP BY to_profile_sid) AS freq;
          avg
----------------------
  152.6540251279664960
(1 row)

db=# SELECT n_distinct FROM pg_stats WHERE tablename='message' AND
attname='to_profile_sid';
  n_distinct
------------
        6277
(1 row)


Also, the value of -1 for "to_profile_sid" is second in the list of
most_common_vals in pg_stats, but still I don't understand why a simple
limit is blinding the planner for the "good" index. Any ideas?

Regards,
--
Kouber Saparev
http://kouber.saparev.com/