title: Efficient way to join by levenshtein in Hive or Impala
body: <p>I have two tables one includes about 17K (<code>NLIST</code>) records while the other 57K (<code>FNAMES</code>).</p>
  
  <p>I would like to join the both by comparing the records using levenshtein formula.</p>
  
  <p>Here is the example for the content of tables:</p>
  
  <p>Table <code>NLIST</code>:</p>
  
  <pre><code>+------+-------------+
  | ID   |   S_NAME    |
  +------+-------------+
  |  1   |   Avi       |
  |  2   |   Moshe     |
  |  3   |   David     |
  ....
  </code></pre>
  
  <p>Table <code>FNAMES</code>:</p>
  
  <pre><code>+------+-------------+
  | ID   |   NICKNAMES |
  +------+-------------+
  |  1   |  Avile      |
  |  2   |  Dudi       |
  |  3   |  Moshiko    |
  |  4   |  Avi        |
  |  5   |  DAVE       |
  ....
  </code></pre>
  
  <p>The above tables are just examples. In the real case the names column can include more than one word.</p>
  
  <p>The required result should be:</p>
  
  <pre><code>+------+-------------+--------+
  | ID   |   NICKNAMES | S_NAME |
  +------+-------------+--------+
  |  1   |  Avile      | Avi    |
  |  2   |  Dudi       | David  |
  |  3   |  Moshiko    | Moshe  |
  |  4   |  Avi        | Avi    |
  |  5   |  DAVE       | David  |
  ...
  </code></pre>
  
  <p>Here is the code I use:</p>
  
  <pre><code>select FNAMES.NICKNAMES, NLIST.S_NAME  
  from NICKNAMES
  LEFT OUTER JOIN NLIST
  ON(true)  
  WHERE levenshtein (FNAMES.NICKNAMES, NLIST.S_NAME) &lt;=4
  </code></pre>
  
  <p>The above code runs for a very long time and I stopped its running.</p>
  
  <p>How can I make it run in a reasonable time?</p>
  
  <p>In addition, I think the <code>levenshtein</code> distance depends on the length of the words. How can I find the optimal value for the distance (in this case I chose 4 arbitrarily)?</p>