title: Slow query ordering by a column in a joined table
body: <p>Introducing an ORDER BY clause in a query increases the total time due the extra work that the db have to do in order to sort the result set:</p>
  
  <ul>
  <li>copy the resulting tuples in some temporary memory</li>
  <li>sorting them (hopefully in memory, otherwise using the disk)</li>
  <li>stream the result to the client</li>
  </ul>
  
  <p>What I miss is why just adding a column from a joined table produces a so different performance.</p>
  
  <h3>Query1</h3>
  
  <pre class="lang-sql prettyprint-override"><code>EXPLAIN ANALYZE
  SELECT p.*
  FROM product_product p
  JOIN django_site d ON (p.site_id = d.id)
  WHERE (p.active = true  AND p.site_id = 1 )
  ORDER BY d.domain, p.ordering, p.name
  </code></pre>
  
  <h3>Query plan</h3>
  
  <pre><code>Sort  (cost=3909.83..3952.21 rows=16954 width=1086) (actual time=1120.618..1143.922 rows=16946 loops=1)
     Sort Key: django_site.domain, product_product.ordering, product_product.name
     Sort Method:  quicksort  Memory: 25517kB
     -&gt;  Nested Loop  (cost=0.00..2718.86 rows=16954 width=1086) (actual time=0.053..87.396 rows=16946 loops=1)
           -&gt;  Seq Scan on django_site  (cost=0.00..1.01 rows=1 width=24) (actual time=0.010..0.012 rows=1 loops=1)
                 Filter: (id = 1)
           -&gt;  Seq Scan on product_product  (cost=0.00..2548.31 rows=16954 width=1066) (actual time=0.036..44.138 rows=16946 loops=1)
                 Filter: (product_product.active AND (product_product.site_id = 1))
   Total runtime: 1182.515 ms
  </code></pre>
  
  <h3>Query 2</h3>
  
  <p>Same as the above but not sorting by <code>django_site.domain</code></p>
  
  <h3>Query plan</h3>
  
  <pre><code> Sort  (cost=3909.83..3952.21 rows=16954 width=1066) (actual time=257.094..278.905 rows=16946 loops=1)
     Sort Key: product_product.ordering, product_product.name
     Sort Method:  quicksort  Memory: 25161kB
     -&gt;  Nested Loop  (cost=0.00..2718.86 rows=16954 width=1066) (actual time=0.075..86.120 rows=16946 loops=1)
           -&gt;  Seq Scan on django_site  (cost=0.00..1.01 rows=1 width=4) (actual time=0.015..0.017 rows=1 loops=1)
                 Filter: (id = 1)
           -&gt;  Seq Scan on product_product  (cost=0.00..2548.31 rows=16954 width=1066) (actual time=0.052..44.024 rows=16946 loops=1)
                 Filter: (product_product.active AND (product_product.site_id = 1))
   Total runtime: 305.392 ms
  </code></pre>
  
  <p><a href="https://stackoverflow.com/questions/7261900/postgres-order-by-foreign-key-performance">This question</a> could be related.</p>
  
  <h2>Edit: More details added</h2>
  
  <pre><code>           Table "public.product_product"
   Column       |          Type          |  
   -------------+------------------------+---------
   id                | integer                | not null default nextval('product_product_id_seq'::regclass)
   site_id           | integer                | not null
   name              | character varying(255) | not null
   slug              | character varying(255) | not null
   sku               | character varying(255) | 
   ordering          | integer                | not null
   [snip some columns ]
  
   Indexes:
      "product_product_pkey" PRIMARY KEY, btree (id)
      "product_product_site_id_key" UNIQUE, btree (site_id, sku)
      "product_product_site_id_key1" UNIQUE, btree (site_id, slug)
      "product_product_site_id" btree (site_id)
      "product_product_slug" btree (slug)
      "product_product_slug_like" btree (slug varchar_pattern_ops)
  
  
                    Table "public.django_site"
   Column |          Type          | 
  --------+------------------------+----------
   id     | integer                | not null default nextval('django_site_id_seq'::regclass)
   domain | character varying(100) | not null
   name   | character varying(50)  | not null
  Indexes:
      "django_site_pkey" PRIMARY KEY, btree (id)
  </code></pre>
  
  <p>The Postgres version is <strong>8.4</strong></p>
  
  <h1>some table stats:</h1>
  
  <pre><code># select count(*) from django_site;
   count 
  -------
       1
  
  # select count(*) from product_product;
   count 
  -------
   17540
  
  # select active, count(*) from product_product group by active;
   active | count 
  --------+-------
   f      |   591
   t      | 16949
  
  # select site_id, count(*) from product_product group by site_id;
   site_id | count 
  ---------+-------
         1 | 17540
  </code></pre>