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(at)yahoo(dot)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.