title: Optimizing PostgreSQL query with multiple joins, order by and small limit
body: <p>I need some tips for optimizing queries fetching from large tables.</p>
  
  <p>In this example I have 5 tables:</p>
  
  <pre><code>Brands
  - id_brand
  - b_name
  
  Products
  - id_product
  - p_name
  - ean
  ...
  - fk_brand
  
  Prod_attributes
  - id_prod_att
  - size_basic
  ...
  - fk_product
  
  Stores
  - id_store
  - s_name
  ...
  
  Stocks
  - id_stock
  - stock_amount
  - fk_prod_att
  - fk_store
  </code></pre>
  
  <p>I need a query with ordered list of stocks, limited, so this is the general approach I used:</p>
  
  <pre><code>SELECT stores.s_name, stocks.stock_amount, prod_attributes.size_basic, 
  products.p_name, products.ean, brands.b_name 
  
  FROM (stocks 
      INNER JOIN stores 
      ON stocks.fk_store = stores.id_store) 
      INNER JOIN (prod_attributes 
          INNER JOIN (products 
              INNER JOIN brands 
              ON products.fk_brand = brands.id_brand) 
          ON prod_attributes.fk_product = products.id_product) 
      ON stocks.fk_prod_att = prod_attributes.id_prod_att 
  
  ORDER BY s_name, p_name, size_basic 
  
  LIMIT 25 OFFSET 0
  </code></pre>
  
  <p>This works fast on small tables, but when the tables grow the query gets very expensive. With 3,5M rows in Stocks, 300K in Prod_attributes, 25K Products it executes in over 8800ms, which is not acceptable for me.</p>
  
  <p>All forgein keys have indexes and DB has been vacuum-analyzed recently.</p>
  
  <p>I know that the issue lies in the ORDER BY part, because of it the query does not use indexes and does sequential scans. If I remove the ordering then the query is very fast.</p>
  
  <p>For solving this I know the I can remove ORDER BY, but it's not feasible option for me. De-normalization of the DB or materialized view could help here also - again I would like to avoid this if possible.</p>
  
  <p>What else I can do to speed this query up?</p>
  
  <p>EXPLAIN ANALYZE:<br>
  - slow with order by: <a href="http://explain.depesz.com/s/AHO" rel="noreferrer">http://explain.depesz.com/s/AHO</a><br>
  - fast without order by: <a href="http://explain.depesz.com/s/NRxr" rel="noreferrer">http://explain.depesz.com/s/NRxr</a></p>