title: How does the optimizer decide between merge join and hash join?
body: <p>Database System Concepts introduce several ways to implement a join operation. Two of them are merge join and hash join. </p>
  
  <ol>
  <li>I was wondering when the optimizer decides to use a merge join and
  when a hash join?</li>
  <li><p>In particular, from <a href="https://stackoverflow.com/a/1114288/156458">https://stackoverflow.com/a/1114288/156458</a></p>
  
  <blockquote>
    <p>hash joins can only be used for equi-joins, but merge joins are more flexible.</p>
  </blockquote>
  
  <p>But Database System Concepts says both are used only for equi joins and
      natural joins. </p>
  
  <blockquote>
    <p>The merge-join algorithm (also called the sort-merge-join algorithm)
    can be used to compute natural joins and equi-joins.</p>
    
    <p>...</p>
    
    <p>Like the merge-join algorithm, the hash-join algorithm can be used to
    implement natural joins and equi-joins.</p>
  </blockquote></li>
  </ol>
  
  <p>Thanks.</p>
  
  <hr>
  
  <p>My question comes from PostgreSQL document, where there are two examples, and I am not sure why one uses merge join, and the other hash join:</p>
  
  <pre><code>EXPLAIN SELECT *
  FROM tenk1 t1, tenk2 t2
  WHERE t1.unique1 &lt; 100 AND t1.unique2 = t2.unique2;
                                          QUERY PLAN
  ------------------------------------------------------------------------------------------
   Hash Join  (cost=230.47..713.98 rows=101 width=488)
     Hash Cond: (t2.unique2 = t1.unique2)
     -&gt;  Seq Scan on tenk2 t2  (cost=0.00..445.00 rows=10000 width=244)
     -&gt;  Hash  (cost=229.20..229.20 rows=101 width=244)
           -&gt;  Bitmap Heap Scan on tenk1 t1  (cost=5.07..229.20 rows=101 width=244)
                 Recheck Cond: (unique1 &lt; 100)
                 -&gt;  Bitmap Index Scan on tenk1_unique1 
   (cost=0.00..5.04 rows=101 width=0)
                       Index Cond: (unique1 &lt; 100)
  </code></pre>
  
  <p>and</p>
  
  <pre><code>EXPLAIN SELECT *
  FROM tenk1 t1, onek t2
  WHERE t1.unique1 &lt; 100 AND t1.unique2 = t2.unique2;
                                          QUERY PLAN
  ------------------------------------------------------------------------------------------
   Merge Join  (cost=198.11..268.19 rows=10 width=488)
     Merge Cond: (t1.unique2 = t2.unique2)
     -&gt;  Index Scan using tenk1_unique2 on tenk1 t1  (cost=0.29..656.28 rows=101 width=244)
           Filter: (unique1 &lt; 100)
     -&gt;  Sort  (cost=197.83..200.33 rows=1000 width=244)
           Sort Key: t2.unique2
           -&gt;  Seq Scan on onek t2  (cost=0.00..148.00 rows=1000 width=244)
  </code></pre>