title: Extremely slow PostgreSQL query with ORDER and LIMIT clauses
body: <p>I have a table, let's call it "foos", with almost 6 million records in it. I am running the following query:</p>
  
  <pre><code>SELECT "foos".*
  FROM "foos"
  INNER JOIN "bars" ON "foos".bar_id = "bars".id
  WHERE (("bars".baz_id = 13266))
  ORDER BY "foos"."id" DESC
  LIMIT 5 OFFSET 0;
  </code></pre>
  
  <p>This query takes a very long time to run (Rails times out while running it). There is an index on all IDs in question. The curious part is, if I remove either the <code>ORDER BY</code> clause or the <code>LIMIT</code> clause, it runs almost instantaneously.</p>
  
  <p>I'm assuming that the presence of both <code>ORDER BY</code> and <code>LIMIT</code> are making PostgreSQL make some bad choices in query planning. Anyone have any ideas on how to fix this?</p>
  
  <p>In case it helps, here is the <code>EXPLAIN</code> for all 3 cases:</p>
  
  <pre><code>//////// Both ORDER and LIMIT
  SELECT "foos".*
  FROM "foos"
  INNER JOIN "bars" ON "foos".bar_id = "bars".id
  WHERE (("bars".baz_id = 13266))
  ORDER BY "foos"."id" DESC
  LIMIT 5 OFFSET 0;
                                                       QUERY PLAN                                                     
  --------------------------------------------------------------------------------------------------------------------
   Limit  (cost=0.00..16663.44 rows=5 width=663)
     -&gt;  Nested Loop  (cost=0.00..25355084.05 rows=7608 width=663)
           Join Filter: (foos.bar_id = bars.id)
           -&gt;  Index Scan Backward using foos_pkey on foos  (cost=0.00..11804133.33 rows=4963477 width=663)
                 Filter: (((NOT privacy_protected) OR (user_id = 67962)) AND ((status)::text = 'DONE'::text))
           -&gt;  Materialize  (cost=0.00..658.96 rows=182 width=4)
                 -&gt;  Index Scan using index_bars_on_baz_id on bars  (cost=0.00..658.05 rows=182 width=4)
                       Index Cond: (baz_id = 13266)
  (8 rows)
  
  //////// Just LIMIT
  SELECT "foos".*
  FROM "foos"
  INNER JOIN "bars" ON "foos".bar_id = "bars".id
  WHERE (("bars".baz_id = 13266))
  LIMIT 5 OFFSET 0;
                                                                QUERY PLAN                                                               
  ---------------------------------------------------------------------------------------------------------------------------------------
   Limit  (cost=0.00..22.21 rows=5 width=663)
     -&gt;  Nested Loop  (cost=0.00..33788.21 rows=7608 width=663)
           -&gt;  Index Scan using index_bars_on_baz_id on bars  (cost=0.00..658.05 rows=182 width=4)
                 Index Cond: (baz_id = 13266)
           -&gt;  Index Scan using index_foos_on_bar_id on foos  (cost=0.00..181.51 rows=42 width=663)
                 Index Cond: (foos.bar_id = bars.id)
                 Filter: (((NOT foos.privacy_protected) OR (foos.user_id = 67962)) AND ((foos.status)::text = 'DONE'::text))
  (7 rows)
  
  //////// Just ORDER
  SELECT "foos".*
  FROM "foos"
  INNER JOIN "bars" ON "foos".bar_id = "bars".id
  WHERE (("bars".baz_id = 13266))
  ORDER BY "foos"."id" DESC;
                                                                QUERY PLAN                                                               
  ---------------------------------------------------------------------------------------------------------------------------------------
   Sort  (cost=36515.17..36534.19 rows=7608 width=663)
     Sort Key: foos.id
     -&gt;  Nested Loop  (cost=0.00..33788.21 rows=7608 width=663)
           -&gt;  Index Scan using index_bars_on_baz_id on bars  (cost=0.00..658.05 rows=182 width=4)
                 Index Cond: (baz_id = 13266)
           -&gt;  Index Scan using index_foos_on_bar_id on foos  (cost=0.00..181.51 rows=42 width=663)
                 Index Cond: (foos.bar_id = bars.id)
                 Filter: (((NOT foos.privacy_protected) OR (foos.user_id = 67962)) AND ((foos.status)::text = 'DONE'::text))
  (8 rows)
  </code></pre>