Branch 492361 is a recent branch of lp available on qastaging;

Running just the  first CTE against it (with an old date - but this is what long running merge proposals will do, so its not unreasonable to assess its performance):

explain analyze SELECT min(Revision.id) AS id
  FROM Revision JOIN BranchRevision ON BranchRevision.revision = Revision.id
  WHERE BranchRevision.branch = 492361 AND Revision.revision_date >= '2009-08-10 21:56:30.623339+00:00';

                                                                                    QUERY PLAN                                                                                    
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=176644.63..176644.64 rows=1 width=4) (actual time=109560.941..109560.942 rows=1 loops=1)
   ->  Nested Loop  (cost=0.00..176591.63 rows=21199 width=4) (actual time=4732.780..109534.701 rows=40649 loops=1)
         ->  Index Scan using revisionnumber_branch_sequence_unique on branchrevision  (cost=0.00..29518.34 rows=21199 width=4) (actual time=60.252..995.287 rows=105756 loops=1)
               Index Cond: (branch = 492361)
         ->  Index Scan using changeset_pkey on revision  (cost=0.00..6.93 rows=1 width=4) (actual time=1.024..1.025 rows=0 loops=105756)
               Index Cond: (revision.id = branchrevision.revision)
               Filter: (revision.revision_date >= '2009-08-10 21:56:30.623339'::timestamp without time zone)
 Total runtime: 109561.079 ms

-> nearly 2 minutes.

Branch revision cannot filter on date; and revision cannot be selective on branch, which is why the db is (sensibly) picking the most selective thing it has (branchrevision.branch=branch) and working from there.

Hot, this is much faster:

explain analyze SELECT min(Revision.id) AS id
  FROM Revision JOIN BranchRevision ON BranchRevision.revision = Revision.id
  WHERE BranchRevision.branch = 492361 AND Revision.revision_date >= '2009-08-10 21:56:30.623339+00:00';
                                                                                   QUERY PLAN                                                                                   
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=176644.63..176644.64 rows=1 width=4) (actual time=849.188..849.189 rows=1 loops=1)
   ->  Nested Loop  (cost=0.00..176591.63 rows=21199 width=4) (actual time=100.800..840.951 rows=40649 loops=1)
         ->  Index Scan using revisionnumber_branch_sequence_unique on branchrevision  (cost=0.00..29518.34 rows=21199 width=4) (actual time=0.147..72.145 rows=105756 loops=1)
               Index Cond: (branch = 492361)
         ->  Index Scan using changeset_pkey on revision  (cost=0.00..6.93 rows=1 width=4) (actual time=0.007..0.007 rows=0 loops=105756)
               Index Cond: (revision.id = branchrevision.revision)
               Filter: (revision.revision_date >= '2009-08-10 21:56:30.623339'::timestamp without time zone)
 Total runtime: 849.288 ms

(We'll use that to compare with a different formulation in a minute.