title: Postgresql - LEFT OUTER JOIN performance issue
body: <p>This is more of theoretical question regarding how postgres actually works. I have four tables, say A, B, C and D with 20k, 870k, 770k and 1.5mln records respectively. Ids are Primary Keys and joins are being made on  Foreign Keys (which are indexed by default, and don't allow nulls). Here is my query:</p>
  
  <pre><code>SELECT "A"."id" AS "a", 
    COUNT("B"."id") AS "b_count", 
     COUNT("C"."id") AS "c_count",
     COUNT("D"."id") AS "d_count" 
  FROM "A" 
  LEFT OUTER JOIN "B" ON ("A"."id" = "B"."A_id") 
  LEFT OUTER JOIN "C" ON ("B"."id" = "C"."B_id") 
  LEFT OUTER JOIN "D" ON ("C"."id" = "D"."C_id") 
  GROUP BY "A"."id"
  </code></pre>
  
  <p>Tables and the query are generated by django framework. For unknow reason it runs so long, that server breaks up. However, if I change any of these LEFT OUTER JOIN to INNER JOIN, then query runs for 4.2 seconds. I know how LEFT and INNER JOIN work in practice, but why there is so much difference in performance in this case?</p>
  
  <p>Additional info:
  EXPLAIN for query with LEFT OUTER JOIN (EXPLAIN (ANALYZE, BUFFERS) doesn't work, because query doesn't end):</p>
  
  <pre><code>"GroupAggregate  (cost=606144.91..628195.81 rows=20784 width=16)"
  "  -&gt;  Sort  (cost=606144.91..610513.52 rows=1747445 width=16)"
  "        Sort Key: A.id"
  "        -&gt;  Hash Right Join  (cost=282896.74..365231.69 rows=1747445 width=16)"
  "              Hash Cond: (D.C_id = C.id)"
  "              -&gt;  Seq Scan on D  (cost=0.00..32113.94 rows=1494094 width=8)"
  "              -&gt;  Hash  (cost=267717.03..267717.03 rows=873257 width=12)"
  "                    -&gt;  Hash Right Join  (cost=208924.92..267717.03 rows=873257 width=12)"
  "                          Hash Cond: (B.A_id = A.id)"
  "                          -&gt;  Hash Right Join  (cost=207935.28..250353.82 rows=873257 width=12)"
  "                                Hash Cond: (C.B_id = B.id)"
  "                                -&gt;  Seq Scan on C  (cost=0.00..21039.49 rows=746649 width=8)"
  "                                -&gt;  Hash  (cost=193607.57..193607.57 rows=873257 width=8)"
  "                                      -&gt;  Seq Scan on B  (cost=0.00..193607.57 rows=873257 width=8)"
  "                          -&gt;  Hash  (cost=729.84..729.84 rows=20784 width=4)"
  "                                -&gt;  Seq Scan on A  (cost=0.00..729.84 rows=20784 width=4)"
  </code></pre>
  
  <p>EXPLAIN(ANALYZE, BUFFERS) for query with one INNER JOIN instead of LEFT OUTER JOIN:</p>
  
  <pre><code>"GroupAggregate  (cost=559935.67..578819.69 rows=20784 width=16) (actual time=4565.338..5090.632 rows=19567 loops=1)"
  "  Buffers: shared hit=10625 read=205521, temp read=27640 written=27388"
  "  -&gt;  Sort  (cost=559935.67..563670.91 rows=1494094 width=16) (actual time=4565.244..4832.596 rows=1494094 loops=1)"
  "        Sort Key: A.id"
  "        Sort Method: external merge  Disk: 37992kB"
  "        Buffers: shared hit=10625 read=205521, temp read=27640 written=27388"
  "        -&gt;  Hash Join  (cost=278322.24..355638.06 rows=1494094 width=16) (actual time=2274.363..3341.921 rows=1494094 loops=1)"
  "              Hash Cond: (D.C_id = C.id)"
  "              Buffers: shared hit=10622 read=205521, temp read=13681 written=13429"
  "              -&gt;  Seq Scan on D  (cost=0.00..32113.94 rows=1494094 width=8) (actual time=0.007..270.841 rows=1494094 loops=1)"
  "                    Buffers: shared hit=3828 read=13345"
  "              -&gt;  Hash  (cost=265343.13..265343.13 rows=746649 width=12) (actual time=2271.959..2271.959 rows=746649 loops=1)"
  "                    Buckets: 4096  Batches: 64  Memory Usage: 512kB"
  "                    Buffers: shared hit=6794 read=192176, temp read=5640 written=8351"
  "                    -&gt;  Hash Join  (cost=208924.92..265343.13 rows=746649 width=12) (actual time=1107.516..2138.249 rows=746649 loops=1)"
  "                          Hash Cond: (B.A_id = A.id)"
  "                          Buffers: shared hit=6794 read=192176, temp read=5640 written=5514"
  "                          -&gt;  Hash Join  (cost=207935.28..250353.82 rows=746649 width=12) (actual time=1099.799..1784.403 rows=746649 loops=1)"
  "                                Hash Cond: (C.B_id = B.id)"
  "                                Buffers: shared hit=6272 read=192176, temp read=5640 written=5514"
  "                                -&gt;  Seq Scan on C  (cost=0.00..21039.49 rows=746649 width=8) (actual time=0.005..203.923 rows=746649 loops=1)"
  "                                      Buffers: shared hit=4600 read=8973"
  "                                -&gt;  Hash  (cost=193607.57..193607.57 rows=873257 width=8) (actual time=1095.407..1095.407 rows=873453 loops=1)"
  "                                      Buckets: 4096  Batches: 64  Memory Usage: 547kB"
  "                                      Buffers: shared hit=1672 read=183203, temp written=2907"
  "                                      -&gt;  Seq Scan on B  (cost=0.00..193607.57 rows=873257 width=8) (actual time=0.004..939.839 rows=873453 loops=1)"
  "                                            Buffers: shared hit=1672 read=183203"
  "                          -&gt;  Hash  (cost=729.84..729.84 rows=20784 width=4) (actual time=7.701..7.701 rows=20784 loops=1)"
  "                                Buckets: 4096  Batches: 1  Memory Usage: 731kB"
  "                                Buffers: shared hit=522"
  "                                -&gt;  Seq Scan on A  (cost=0.00..729.84 rows=20784 width=4) (actual time=0.004..4.661 rows=20784 loops=1)"
  "                                      Buffers: shared hit=522"
  "Total runtime: 5099.046 ms"
  </code></pre>
  
  <p>And bonus: if I use slightly modified query:</p>
  
  <pre><code>SELECT "A"."id" AS "a", 
    COUNT("B"."id") AS "b_count", 
     COUNT("C"."id") AS "c_count",
     COUNT("D"."id") AS "d_count" 
  FROM "A" 
  LEFT OUTER JOIN "B" ON ("A"."id" = "B"."A_id") 
  LEFT OUTER JOIN "C" ON ("B"."id" = "C"."B_id") 
  LEFT OUTER JOIN "D" ON ("C"."id" = "D"."D_id") 
  WHERE "D"."id" &lt; 1500000 -- this is always true
  GROUP BY "A"."id"
  </code></pre>
  
  <p>Then it also works, but a little bit longer than using at least one INNER JOIN. EXPLAIN (ANALYZE, BUFFERS) for this case:</p>
  
  <pre><code>"GroupAggregate  (cost=563670.91..582554.92 rows=20784 width=16) (actual time=6779.121..7286.640 rows=19567 loops=1)"
  "  Buffers: shared hit=10814 read=205329, temp read=27640 written=27388"
  "  -&gt;  Sort  (cost=563670.91..567406.14 rows=1494094 width=16) (actual time=6777.606..7033.885 rows=1494094 loops=1)"
  "        Sort Key: A.id"
  "        Sort Method: external merge  Disk: 37992kB"
  "        Buffers: shared hit=10814 read=205329, temp read=27640 written=27388"
  "        -&gt;  Hash Join  (cost=278322.24..359373.29 rows=1494094 width=16) (actual time=4601.432..5674.321 rows=1494094 loops=1)"
  "              Hash Cond: (D.C_id = C.id)"
  "              Buffers: shared hit=10814 read=205329, temp read=13681 written=13429"
  "              -&gt;  Seq Scan on D  (cost=0.00..35849.18 rows=1494094 width=8) (actual time=0.005..374.660 rows=1494094 loops=1)"
  "                    Filter: (id &lt; 1500000)"
  "                    Buffers: shared hit=3892 read=13281"
  "              -&gt;  Hash  (cost=265343.13..265343.13 rows=746649 width=12) (actual time=4600.782..4600.782 rows=746649 loops=1)"
  "                    Buckets: 4096  Batches: 64  Memory Usage: 512kB"
  "                    Buffers: shared hit=6922 read=192048, temp read=5640 written=8351"
  "                    -&gt;  Hash Join  (cost=208924.92..265343.13 rows=746649 width=12) (actual time=3363.352..4469.474 rows=746649 loops=1)"
  "                          Hash Cond: (B.A_id = A.id)"
  "                          Buffers: shared hit=6922 read=192048, temp read=5640 written=5514"
  "                          -&gt;  Hash Join  (cost=207935.28..250353.82 rows=746649 width=12) (actual time=3257.869..4066.067 rows=746649 loops=1)"
  "                                Hash Cond: (C.B_id = B.id)"
  "                                Buffers: shared hit=6400 read=192048, temp read=5640 written=5514"
  "                                -&gt;  Seq Scan on C  (cost=0.00..21039.49 rows=746649 width=8) (actual time=0.006..372.317 rows=746649 loops=1)"
  "                                      Buffers: shared hit=4664 read=8909"
  "                                -&gt;  Hash  (cost=193607.57..193607.57 rows=873257 width=8) (actual time=3257.327..3257.327 rows=873453 loops=1)"
  "                                      Buckets: 4096  Batches: 64  Memory Usage: 547kB"
  "                                      Buffers: shared hit=1736 read=183139, temp written=2907"
  "                                      -&gt;  Seq Scan on B  (cost=0.00..193607.57 rows=873257 width=8) (actual time=0.004..3097.367 rows=873453 loops=1)"
  "                                            Buffers: shared hit=1736 read=183139"
  "                          -&gt;  Hash  (cost=729.84..729.84 rows=20784 width=4) (actual time=105.467..105.467 rows=20784 loops=1)"
  "                                Buckets: 4096  Batches: 1  Memory Usage: 731kB"
  "                                Buffers: shared hit=522"
  "                                -&gt;  Seq Scan on A  (cost=0.00..729.84 rows=20784 width=4) (actual time=0.002..101.506 rows=20784 loops=1)"
  "                                      Buffers: shared hit=522"
  "Total runtime: 7294.388 ms"
  </code></pre>
  
  <p>Why original query breaks postgres, while other two work like a charm?</p>
  
  <p>EDIT:
  All queries behave the same even if there are no count() clauses. The problem is in JOINs only</p>