BUG #4641: Wrong estimates for multi-column conditions

The following bug has been logged online:

Bug reference:      4641
Logged by:          Adrian Sandor
Email address:      aditsu@yahoo.com
PostgreSQL version: 8.3.5
Operating system:   Linux
Description:        Wrong estimates for multi-column conditions
Details:

I have two queries that should do the same thing, but have extremely
different estimates for the number of rows (and execution time):

explain select * from links where (score, created) < (0,
'2009-01-12T19:30:29.907378') ORDER BY "links"."score" DESC,
"links"."created" DESC;
                                               QUERY PLAN
----------------------------------------------------------------------------
-----------------------------
 Index Scan Backward using links_score_created_idx on links
(cost=0.00..8.31 rows=1 width=720)
   Index Cond: (ROW(score, created) < ROW(0, '2009-01-12
19:30:29.907378-08'::timestamp with time zone))
(2 rows)


explain select * from links where score < 0 or (score = 0 and created <
'2009-01-12T19:30:29.907378') ORDER BY "links"."score" DESC,
"links"."created" DESC;
                                                        QUERY PLAN
----------------------------------------------------------------------------
----------------------------------------------
 Sort  (cost=252025.64..252541.15 rows=206207 width=720)
   Sort Key: score, created
   ->  Seq Scan on links  (cost=0.00..37180.02 rows=206207 width=720)
         Filter: ((score < 0) OR ((score = 0) AND (created < '2009-01-12
19:30:29.907378-08'::timestamp with time zone)))
(4 rows)

The actual number of rows is 228614.