35x Improved T-SQL LevenShtein Distance Algorithm...at a cost

At work, we noticed a considerable performance hit using a T-SQL implementation of the Levenshtein algorithm created by Michael Gilleland found here. It seems to me that his approach was to replicate the C-code algorithm found in Wikipedia in T-SQL rather than taking a step back and re-conceptualizing the algorithm from a T-SQL standpoint. Feel free to correct me, but it seems that the algorithm focues on three things to find the shortest distance between two strings (what it takes to make them the same):

1. How many character insertions are necessary
2. How many character deletions are necessary
3. How many character substitutions are necessary

These three traits are necessary to accommodate mis-aligned strings because of typos. If the algorithm is not designed with these constraints, one missing letter will result in inaccurate reporting because it throws the indexing off. The C-code example in Wikipedia uses a 2-D matrix approach, which is a natural, compact, and performant fit for C/C++, or probably any other modern programming language. However, in SQL, especially T-SQL, stuffing all these characters into one huge string and doing sub string comparisons is very costly.

More than that, a true Levenshtein function should return the numeric distance between the two strings, not a string value of this distance. Keeping this in mind, I started editing the algorithm to understand what was going on at a low level but quickly found that I would just be better off re-architecting the whole solution, not just to make it performant, but so that I would understand it completely. I followed the above 3 traits with some small additions for performance. I wanted to do the following:

1. If either string is empty, return the length of the other string
2. Find the longest string, and loop on that length.
3. Compare each character and see if they are equal
4. If they are not, then increment the difference counter
5. See if an insertion will re-align the strings; increment the right index forward if true
6. Else, see if a deletion will re-align the string; increment the left index forward if true
7. Return the number of differences

Seems pretty simple when you think about it... I now have one 'WHILE' loop with at most 4 substring() calls per character.

This new algorithm comes at a cost of not checking for insertions/deletions along the entire length of the comparison string, so we can now only handle one insertion/deletion consecutively except at the end of the comparison string. This, in effect, makes it no longer follow the Levenshtein algorithm's end capabilities, but this is an acceptable cost for our needs.

So, how much does this help my performance?
  Test Case: I was matching first and last names on a table with over 5,500 users and using Mr. Gilleland's approach with a user that was towards the end of the table, it took ~28 seconds. I optimized that call down to 14 seconds (I was using the function twice in the proc). Still, 14 seconds is a heck of a long time.


Original Query: 28 seconds
Optimized Original Query (removed a second Levenshtein function call, using lengths as a predeterminate instead): 14 seconds

My 'optimized' Levenshtein Algorithm using the Optimized Original Query: With the same table and same user with my 'improved' algorithm, I could now perform the same query in ~400 ms. That's a 35x improvement! All of these tests were run with MSSQL 2005.

Here's the code:

/****** Object: UserDefinedFunction [dbo].[LEVENSHTEIN] Script Date: 06/10/2009 09:36:44 ******/ 
SET ANSI_NULLS ON GO 
SET QUOTED_IDENTIFIER ON GO  
ALTER function [dbo].[LEVENSHTEIN]( @left varchar(100), @right varchar(100) ) 
   returns int 
as 
BEGIN 
   DECLARE @difference int, @lenRight int, @lenLeft int, @leftIndex int, @rightIndex int,   @left_char char(1), @right_char char(1), @compareLength int  
   SET @lenLeft = LEN(@left) 
   SET @lenRight = LEN(@right) 
   SET @difference = 0  
   If @lenLeft = 0 
   BEGIN 
      SET @difference = @lenRight GOTO done 
   END 
   If @lenRight = 0 
   BEGIN 
      SET @difference = @lenLeft 
      GOTO done 
   END  
   GOTO comparison  

   comparison: 
   IF (@lenLeft >= @lenRight) 
      SET @compareLength = @lenLeft 
   Else 
      SET @compareLength = @lenRight  
   SET @rightIndex = 1 
   SET @leftIndex = 1 
   WHILE @leftIndex <= @compareLength 
   BEGIN 
      SET @left_char = substring(@left, @leftIndex, 1)
      SET @right_char = substring(@right, @rightIndex, 1)
      IF @left_char <> @right_char 
      BEGIN -- Would an insertion make them re-align? 
         IF(@left_char = substring(@right, @rightIndex+1, 1))    
            SET @rightIndex = @rightIndex + 1 
         -- Would an deletion make them re-align? 
         ELSE 
            IF(substring(@left, @leftIndex+1, 1) = @right_char)
               SET @leftIndex = @leftIndex + 1
               SET @difference = @difference + 1 
      END 
      SET @leftIndex = @leftIndex + 1 
      SET @rightIndex = @rightIndex + 1 
   END  
   GOTO done  

   done: 
      RETURN @difference 
END