Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

We've got a customers table (Who doesn't?), containing many records that are, from a business perspective, duplicates. I've been able to create an SSIS package to perform fuzzy grouping, and report on potential duplicates.

Now, suppose I want to do this kind of analysis just as somebody is entering a new customer. The idea would be to perform a fuzzy lookup on customer name (and possibly some other basic info like postal code), and show potential duplicates prior to proceeding to the customer creation form.

The obvious problem here is that the fuzzy grouping and lookup components are part of SSIS. If I wanted to run those on-demand, I'd have to do something insane like putting the search terms in a staging table, running the SSIS package, waiting for it to complete, and fetching the results from an output table. It would be slow, painful, and have severe concurrency problems.

So, the other idea was to use full-text indexing. In experimenting with it, it looks like it won't be suitable. It can't catch subtle misspellings of customer names, or names that differ in "Company" vs. "Corporation" vs. "Co.", or "Anderson" vs. "Andersen", and other such variations.

Is there something that will allow for the flexibility of fuzzy grouping/matching from T-SQL? I can tell a fuzzy lookup to save the tokens, but it looks like I would still have to reimplement most of the matching algorithm to make use of them.

share|improve this question
    
Any chance you already looked for SOUNDEX and DIFFERENCE? Not sure if you have any other options directly in MS SQL, except for SSIS as you know already. –  Marian Feb 21 '12 at 19:58
1  
Found a similar question on StackOverflow. It appears that some form of fuzzy search can be done with Full Text Search using Freetext and Freetexttable. Also found a great DIY article on SQLServerCentral - Roll your own fuzzy search. –  Marian Feb 21 '12 at 20:07
    
Soundex was much too limited, based on my experiments. Full-text indexing was much better, but still wouldn't catch things like "Anderson" vs. "Andersen". Those Jaro-Winkler functions are pretty cool, but it looks like it will perform too slowly for quick lookups. It takes about 50 seconds to compare against our list of 37,000+ customer names. I'd like to use this for both preventing duplicates, and allowing the receptionist to do fuzzy name lookups. I'm sure I'll be able to find another use for those functions, though. –  db2 Feb 21 '12 at 21:53
    
Then I'm personally out of options :-). Have you tried an external text search service, like Lucene? –  Marian Feb 21 '12 at 22:19
1  
According to this MSDN blog article you're a bit on your own. There's nothing integrated in SQL Server (I mean in FTS either, as in the TSQL you already knew). You might give a try to some algorithms transformed from their original C/C++ version, like the Double metaphone in TSQL. –  Marian Feb 21 '12 at 22:37
add comment

1 Answer

up vote 1 down vote accepted

In the past I built a "fuzzy-search" in a .Net CLR function. This function gets called the same way a user-defined function gets called.

For example,

select id, name
from customers
where dbo.CompareStrings("newCustomerName", customers.name) > .8

would only return customers with a name that was 80% similar to the input name.

The % match is based on the number of changes needed to convert one value to another, not the number of characters that are different. We use it to compare addresses, and found this was more effective because of the numerous street abbreviations that are used.

Here's the code I used to compare strings. I did this so long ago that I can't remember how to deploy it, although a quick search will show you many articles on how to create SQL CLR functions

' Checks two strings against each other and returns a decimal between 0 (doesn't match at all) and 1 (100% match)
<Microsoft.SqlServer.Server.SqlFunction()> _
Public Shared Function CompareStrings(ByVal input1 As SqlChars, ByVal input2 As SqlChars) _
As <SqlFacet(Precision:=10, Scale:=4)> SqlDecimal

    If IsNothing(input1) And IsNothing(input2) Then
        Return New SqlDecimal(1.0)
    ElseIf IsNothing(input1) Or IsNothing(input2) Then
        Return New SqlDecimal(0.0)
    End If

    Dim s1 As String = New String(input1.Value)
    Dim s2 As String = New String(input2.Value)

    If s1.Length = 0 Or s2.Length = 0 Then
        Return New SqlDecimal(1.0)
    Else
        Dim re As New Regex("[^A-Za-z0-9 ]", RegexOptions.IgnorePatternWhitespace Xor RegexOptions.Singleline)
        s1 = re.Replace(s1, "( )\1*", "$1")
        s2 = re.Replace(s2, "( )\1*", "$1")
        s1 = UCase(re.Replace(s1, ""))
        s2 = UCase(re.Replace(s2.ToString, ""))

        Dim dif As Integer = GetStringSimilarity(s1, s2)
        Dim max As Integer = s1.Length
        If s2.Length > max Then max = s2.Length

        Return New SqlDecimal(1.0 - (dif / max))
    End If
End Function

' Compares two strings using the relationship in patterns of letters
Private Shared Function GetStringSimilarity(ByVal s1 As String, ByVal s2 As String) As Integer
    Dim n As Integer = s1.Length
    Dim m As Integer = s2.Length
    Dim distance(n + 1, m + 1) As Integer

    Dim cost As Integer = 0
    If n = 0 Then Return m
    If m = 0 Then Return n

    For i As Integer = 0 To n
        distance(i, 0) = i
    Next
    For j As Integer = 0 To m
        distance(0, j) = j
    Next

    For i As Integer = 1 To n
        For j As Integer = 1 To m
            If Mid(s2, j, 1) = Mid(s1, i, 1) Then cost = 0 Else cost = 1
            distance(i, j) = Min3(distance(i - 1, j) + 1, distance(i, j - 1) + 1, distance(i - 1, j - 1) + cost)
        Next
    Next
    Return distance(n, m)
End Function

' Returns the min of 3 values
Private Shared Function Min3(ByVal x As Integer, ByVal y As Integer, ByVal z As Integer) As Integer
    Dim min As Integer = x
    If y < min Then min = y
    If z < min Then min = z
    Return min
End Function
share|improve this answer
    
That looks rather promising. The big hurdle here is that CLR stuff barely works on this server - it's 32-bit, with 32 GB of RAM, and we get tons of VAS/memtoleave pressure if we try to use it. I'm worried that turning memtoleave much higher than it is now (448MB) is going to start hurting buffer pool AWE performance. But if there's an efficient way to replace the use of the RegEx, and the two-dimensional array, it might be convertible to pure T-SQL... –  db2 Feb 21 '12 at 21:35
    
Very cool algorithm, but when converted to pure T-SQL, it's much too slow. I'm not sure how the CLR version performance compares, but when I run it against our customer list, it can only compare a little over 6,000 names in 4 minutes. Running it on all 8 cores doesn't seem to improve it much. Bummer! –  db2 Feb 22 '12 at 14:21
1  
@db2 That's too bad. Our primary use of the script is to compare about 900 company addresses with about 3 million consumer addresses, and the process takes about 2 minutes. The script used to run on Windows 2003 (32bit) with 8GB of RAM without a problem (we've upgraded our sql server since then). Perhaps you can look into why CLR functions run so slowly on your machine? –  Rachel Feb 22 '12 at 14:37
    
Actually I forgot we filtered the result set prior to running the CLR function. The final result set is 900 x 113k records, and it takes about 30 seconds to filter the result set properly so it takes roughly 90 seconds to run. –  Rachel Feb 22 '12 at 14:43
    
That's pretty impressive. Hopefully we can migrate this old clunker to a 64-bit system soonish. –  db2 Feb 23 '12 at 0:18
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.