60_Fuzzy_String_Matching.sql

/**************************************************************
 * SQL Server 2025 Fuzzy String Matching Tutorial
 * Description: This script demonstrates Fuzzy String Matching
 *              introduced in SQL Server 2025 (17.x). It covers:
 *              - EDIT_DISTANCE function for Levenshtein distance
 *              - EDIT_DISTANCE_SIMILARITY for similarity scoring
 *              - Practical use cases for approximate matching
 *              - Performance considerations and indexing strategies
 *              - Comparison with traditional string matching methods
 *              - Real-world applications in data quality and deduplication
 **************************************************************/

-------------------------------------------------
-- Region: 1. Introduction and Setup
-------------------------------------------------
USE master;
GO

/*
  Create a test database for fuzzy string matching examples.
*/
IF DB_ID('FuzzyMatchDemo') IS NOT NULL
BEGIN
    ALTER DATABASE FuzzyMatchDemo SET SINGLE_USER WITH ROLLBACK IMMEDIATE;
    DROP DATABASE FuzzyMatchDemo;
END
GO

CREATE DATABASE FuzzyMatchDemo;
GO

USE FuzzyMatchDemo;
GO

-- Set compatibility level for SQL Server 2025 (17.x)
ALTER DATABASE FuzzyMatchDemo SET COMPATIBILITY_LEVEL = 170;
GO

-- Enable preview features (required for fuzzy matching in SQL Server 2025)
ALTER DATABASE SCOPED CONFIGURATION SET PREVIEW_FEATURES = ON;
GO

-------------------------------------------------
-- Region: 2. Understanding EDIT_DISTANCE
-------------------------------------------------
/*
  EDIT_DISTANCE calculates the number of single-character edits needed
  to transform one string into another (Levenshtein distance).
  
  Edit operations include:
  - Insertion: Add a character
  - Deletion: Remove a character
  - Substitution: Replace a character
  - Transposition: Swap adjacent characters
  
  Lower edit distance = more similar strings
*/

-- 2.1 Basic EDIT_DISTANCE examples
SELECT 
    'kitten' AS String1,
    'sitting' AS String2,
    EDIT_DISTANCE('kitten', 'sitting') AS EditDistance;
GO

SELECT 
    'SQL Server' AS String1,
    'SQL Serve' AS String2,
    EDIT_DISTANCE('SQL Server', 'SQL Serve') AS EditDistance;
GO

SELECT 
    'database' AS String1,
    'databse' AS String2,
    EDIT_DISTANCE('database', 'databse') AS EditDistance; -- Transposition
GO

-- 2.2 Case sensitivity
SELECT 
    'Hello' AS String1,
    'hello' AS String2,
    EDIT_DISTANCE('Hello', 'hello') AS EditDistance_CaseSensitive,
    EDIT_DISTANCE(LOWER('Hello'), LOWER('hello')) AS EditDistance_CaseInsensitive;
GO

-- 2.3 Empty and NULL strings
SELECT 
    '' AS String1,
    'test' AS String2,
    EDIT_DISTANCE('', 'test') AS EditDistance_Empty,
    EDIT_DISTANCE(NULL, 'test') AS EditDistance_Null;
GO

-------------------------------------------------
-- Region: 3. Understanding EDIT_DISTANCE_SIMILARITY
-------------------------------------------------
/*
  EDIT_DISTANCE_SIMILARITY calculates a similarity score from 0 to 100.
  - 0: No similarity (completely different)
  - 100: Exact match (identical strings)
  
  This is often more intuitive than raw edit distance.
*/

-- 3.1 Basic similarity examples
SELECT 
    'SQL Server' AS String1,
    'Sequel Server' AS String2,
    EDIT_DISTANCE_SIMILARITY('SQL Server', 'Sequel Server') AS SimilarityScore;
GO

SELECT 
    'Microsoft' AS String1,
    'Microsft' AS String2,
    EDIT_DISTANCE_SIMILARITY('Microsoft', 'Microsft') AS SimilarityScore;
GO

-- 3.2 Similarity spectrum
SELECT 
    String1,
    String2,
    EDIT_DISTANCE_SIMILARITY(String1, String2) AS SimilarityScore
FROM (VALUES
    ('Identical', 'Identical'),
    ('Similar', 'Similer'),
    ('Different', 'Completely'),
    ('Test', 'Testing'),
    ('ABC', 'XYZ')
) AS T(String1, String2)
ORDER BY SimilarityScore DESC;
GO

-------------------------------------------------
-- Region: 4. Data Quality and Deduplication
-------------------------------------------------
/*
  Use fuzzy matching to identify duplicate or similar records.
*/

-- 4.1 Create a customer table with potential duplicates
CREATE TABLE dbo.Customers
(
    CustomerID INT IDENTITY(1,1) PRIMARY KEY,
    FirstName NVARCHAR(50),
    LastName NVARCHAR(50),
    Email NVARCHAR(100),
    Phone NVARCHAR(20),
    City NVARCHAR(50)
);
GO

-- Insert sample data with intentional variations
INSERT INTO dbo.Customers (FirstName, LastName, Email, Phone, City)
VALUES 
    ('John', 'Smith', 'john.smith@email.com', '555-1234', 'New York'),
    ('Jon', 'Smith', 'jon.smith@email.com', '555-1234', 'New York'),
    ('John', 'Smyth', 'j.smith@email.com', '(555) 123-4567', 'NY'),
    ('Jane', 'Doe', 'jane.doe@email.com', '555-5678', 'Boston'),
    ('Jane', 'Dow', 'jane.dow@email.com', '555-5678', 'Boston'),
    ('Michael', 'Johnson', 'mjohnson@email.com', '555-9876', 'Chicago'),
    ('Mike', 'Johnson', 'mike.j@email.com', '555-9876', 'Chicago'),
    ('Sarah', 'Williams', 'sarah.w@email.com', '555-4321', 'Seattle');
GO

-- 4.2 Find potential duplicate customers based on name similarity
SELECT 
    C1.CustomerID AS Customer1_ID,
    C1.FirstName + ' ' + C1.LastName AS Customer1_Name,
    C2.CustomerID AS Customer2_ID,
    C2.FirstName + ' ' + C2.LastName AS Customer2_Name,
    EDIT_DISTANCE_SIMILARITY(
        C1.FirstName + ' ' + C1.LastName,
        C2.FirstName + ' ' + C2.LastName
    ) AS NameSimilarity
FROM dbo.Customers C1
INNER JOIN dbo.Customers C2 
    ON C1.CustomerID < C2.CustomerID
WHERE EDIT_DISTANCE_SIMILARITY(
    C1.FirstName + ' ' + C1.LastName,
    C2.FirstName + ' ' + C2.LastName
) >= 75 -- 75% similar or more
ORDER BY NameSimilarity DESC;
GO

-- 4.3 Multi-field similarity check
WITH CustomerPairs AS
(
    SELECT 
        C1.CustomerID AS Customer1_ID,
        C1.FirstName + ' ' + C1.LastName AS Customer1_Name,
        C1.Email AS Customer1_Email,
        C2.CustomerID AS Customer2_ID,
        C2.FirstName + ' ' + C2.LastName AS Customer2_Name,
        C2.Email AS Customer2_Email,
        EDIT_DISTANCE_SIMILARITY(C1.FirstName + ' ' + C1.LastName, C2.FirstName + ' ' + C2.LastName) AS NameSim,
        EDIT_DISTANCE_SIMILARITY(C1.Email, C2.Email) AS EmailSim,
        EDIT_DISTANCE_SIMILARITY(C1.City, C2.City) AS CitySim
    FROM dbo.Customers C1
    INNER JOIN dbo.Customers C2 ON C1.CustomerID < C2.CustomerID
)
SELECT 
    Customer1_ID,
    Customer1_Name,
    Customer2_ID,
    Customer2_Name,
    NameSim,
    EmailSim,
    CitySim,
    (NameSim + EmailSim + CitySim) / 3.0 AS OverallSimilarity
FROM CustomerPairs
WHERE (NameSim + EmailSim + CitySim) / 3.0 >= 70
ORDER BY OverallSimilarity DESC;
GO

-------------------------------------------------
-- Region: 5. Search and Autocomplete
-------------------------------------------------
/*
  Use fuzzy matching for search functionality with typo tolerance.
*/

-- 5.1 Create a product catalog
CREATE TABLE dbo.Products
(
    ProductID INT IDENTITY(1,1) PRIMARY KEY,
    ProductName NVARCHAR(100),
    Category NVARCHAR(50),
    Price DECIMAL(10,2)
);
GO

INSERT INTO dbo.Products (ProductName, Category, Price)
VALUES 
    ('Laptop Computer', 'Electronics', 999.99),
    ('Desktop Computer', 'Electronics', 799.99),
    ('Wireless Mouse', 'Accessories', 29.99),
    ('Mechanical Keyboard', 'Accessories', 89.99),
    ('Monitor 27 inch', 'Electronics', 299.99),
    ('USB Cable', 'Accessories', 9.99),
    ('Webcam HD', 'Electronics', 79.99),
    ('Headphones Wireless', 'Audio', 149.99);
GO

-- 5.2 Search with typo tolerance
DECLARE @searchTerm NVARCHAR(100) = 'Compter'; -- Typo for "Computer"

SELECT 
    ProductID,
    ProductName,
    Category,
    Price,
    EDIT_DISTANCE_SIMILARITY(@searchTerm, ProductName) AS RelevanceScore
FROM dbo.Products
WHERE EDIT_DISTANCE_SIMILARITY(@searchTerm, ProductName) >= 40
ORDER BY RelevanceScore DESC;
GO

-- 5.3 Autocomplete suggestions
DECLARE @partialInput NVARCHAR(100) = 'Keybo'; -- Partial input

SELECT TOP 5
    ProductName,
    EDIT_DISTANCE_SIMILARITY(@partialInput, LEFT(ProductName, LEN(@partialInput))) AS MatchScore
FROM dbo.Products
WHERE ProductName LIKE @partialInput + '%'
   OR EDIT_DISTANCE_SIMILARITY(@partialInput, LEFT(ProductName, LEN(@partialInput))) >= 60
ORDER BY MatchScore DESC;
GO

-------------------------------------------------
-- Region: 6. Address Matching and Normalization
-------------------------------------------------
/*
  Match addresses despite variations in format and spelling.
*/

-- 6.1 Create an address table
CREATE TABLE dbo.Addresses
(
    AddressID INT IDENTITY(1,1) PRIMARY KEY,
    StreetAddress NVARCHAR(200),
    City NVARCHAR(50),
    State NVARCHAR(2),
    ZipCode NVARCHAR(10)
);
GO

INSERT INTO dbo.Addresses (StreetAddress, City, State, ZipCode)
VALUES 
    ('123 Main Street', 'New York', 'NY', '10001'),
    ('123 Main St', 'NY', 'NY', '10001'),
    ('123 Maine Street', 'New York', 'NY', '10001'),
    ('456 Oak Avenue', 'Boston', 'MA', '02101'),
    ('456 Oak Ave', 'Boston', 'MA', '02101');
GO

-- 6.2 Find similar addresses
SELECT 
    A1.AddressID AS Address1_ID,
    A1.StreetAddress AS Address1,
    A2.AddressID AS Address2_ID,
    A2.StreetAddress AS Address2,
    EDIT_DISTANCE_SIMILARITY(A1.StreetAddress, A2.StreetAddress) AS StreetSimilarity
FROM dbo.Addresses A1
INNER JOIN dbo.Addresses A2 ON A1.AddressID < A2.AddressID
WHERE A1.ZipCode = A2.ZipCode
  AND EDIT_DISTANCE_SIMILARITY(A1.StreetAddress, A2.StreetAddress) >= 70
ORDER BY StreetSimilarity DESC;
GO

-------------------------------------------------
-- Region: 7. Name Matching for Person Identification
-------------------------------------------------
/*
  Match person names despite variations, nicknames, and typos.
*/

-- 7.1 Create a names reference table
CREATE TABLE dbo.PersonNames
(
    PersonID INT IDENTITY(1,1) PRIMARY KEY,
    FullName NVARCHAR(100),
    Source NVARCHAR(50)
);
GO

INSERT INTO dbo.PersonNames (FullName, Source)
VALUES 
    ('Robert Johnson', 'System A'),
    ('Bob Johnson', 'System B'),
    ('Rob Johnson', 'System C'),
    ('Robert Jonson', 'System D'),
    ('Christopher Smith', 'System A'),
    ('Chris Smith', 'System B'),
    ('Catherine Williams', 'System A'),
    ('Cathy Williams', 'System B'),
    ('Katherine Williams', 'System C');
GO

-- 7.2 Find matching names across systems
SELECT 
    P1.PersonID AS Person1_ID,
    P1.FullName AS Name1,
    P1.Source AS Source1,
    P2.PersonID AS Person2_ID,
    P2.FullName AS Name2,
    P2.Source AS Source2,
    EDIT_DISTANCE_SIMILARITY(P1.FullName, P2.FullName) AS NameMatchScore
FROM dbo.PersonNames P1
INNER JOIN dbo.PersonNames P2 
    ON P1.PersonID < P2.PersonID 
    AND P1.Source <> P2.Source
WHERE EDIT_DISTANCE_SIMILARITY(P1.FullName, P2.FullName) >= 65
ORDER BY NameMatchScore DESC;
GO

-------------------------------------------------
-- Region: 8. Performance Optimization
-------------------------------------------------
/*
  Fuzzy matching can be computationally expensive.
  Use these strategies to optimize performance.
*/

-- 8.1 Pre-filter with traditional methods
-- First filter with LIKE or exact matches, then apply fuzzy matching
DECLARE @search NVARCHAR(100) = 'Johnson';

SELECT 
    PersonID,
    FullName,
    EDIT_DISTANCE_SIMILARITY(@search, FullName) AS MatchScore
FROM dbo.PersonNames
WHERE FullName LIKE '%' + @search + '%' -- Pre-filter
   OR EDIT_DISTANCE(FullName, @search) <= 3 -- Allow up to 3 edits
ORDER BY MatchScore DESC;
GO

-- 8.2 Use computed persisted columns for common searches
ALTER TABLE dbo.Products
ADD ProductNameNormalized AS LOWER(REPLACE(ProductName, ' ', '')) PERSISTED;
GO

CREATE NONCLUSTERED INDEX IX_Products_Normalized
ON dbo.Products (ProductNameNormalized);
GO

-- 8.3 Limit comparison scope with indexes
-- Create an index on first letter for quick filtering
ALTER TABLE dbo.Customers
ADD FirstLetterLastName AS LEFT(LastName, 1) PERSISTED;
GO

CREATE NONCLUSTERED INDEX IX_Customers_FirstLetter
ON dbo.Customers (FirstLetterLastName);
GO

-- Only compare customers with same first letter
SELECT 
    C1.CustomerID,
    C1.LastName,
    C2.CustomerID,
    C2.LastName,
    EDIT_DISTANCE_SIMILARITY(C1.LastName, C2.LastName) AS Similarity
FROM dbo.Customers C1
INNER JOIN dbo.Customers C2 
    ON C1.FirstLetterLastName = C2.FirstLetterLastName
    AND C1.CustomerID < C2.CustomerID
WHERE EDIT_DISTANCE_SIMILARITY(C1.LastName, C2.LastName) >= 80;
GO

-------------------------------------------------
-- Region: 9. Combining with Other String Functions
-------------------------------------------------
/*
  Combine fuzzy matching with traditional string functions.
*/

-- 9.1 Soundex + Edit Distance
SELECT 
    P1.FullName AS Name1,
    P2.FullName AS Name2,
    SOUNDEX(P1.FullName) AS Soundex1,
    SOUNDEX(P2.FullName) AS Soundex2,
    EDIT_DISTANCE_SIMILARITY(P1.FullName, P2.FullName) AS FuzzySimilarity
FROM dbo.PersonNames P1
CROSS JOIN dbo.PersonNames P2
WHERE P1.PersonID < P2.PersonID
  AND (SOUNDEX(P1.FullName) = SOUNDEX(P2.FullName) -- Phonetically similar
       OR EDIT_DISTANCE_SIMILARITY(P1.FullName, P2.FullName) >= 75)
ORDER BY FuzzySimilarity DESC;
GO

-- 9.2 Normalize before comparison
CREATE FUNCTION dbo.NormalizeString(@input NVARCHAR(MAX))
RETURNS NVARCHAR(MAX)
AS
BEGIN
    RETURN LOWER(LTRIM(RTRIM(@input)));
END
GO

SELECT 
    ProductName,
    EDIT_DISTANCE_SIMILARITY(
        dbo.NormalizeString('wireless mouse'),
        dbo.NormalizeString(ProductName)
    ) AS NormalizedSimilarity
FROM dbo.Products
ORDER BY NormalizedSimilarity DESC;
GO

-------------------------------------------------
-- Region: 10. Practical Applications
-------------------------------------------------
/*
  Real-world use cases for fuzzy string matching.
*/

-- 10.1 Data Import Validation
CREATE TABLE dbo.ImportedCustomers
(
    ImportID INT IDENTITY(1,1) PRIMARY KEY,
    ImportedName NVARCHAR(100),
    MatchedCustomerID INT NULL,
    MatchConfidence DECIMAL(5,2) NULL,
    RequiresReview BIT DEFAULT 0
);
GO

INSERT INTO dbo.ImportedCustomers (ImportedName)
VALUES ('Jon Smythe'), ('Jane Do'), ('Micheal Jonson');
GO

-- Match imported names to existing customers
UPDATE IC
SET 
    MatchedCustomerID = BestMatch.CustomerID,
    MatchConfidence = BestMatch.BestScore,
    RequiresReview = CASE WHEN BestMatch.BestScore < 90 THEN 1 ELSE 0 END
FROM dbo.ImportedCustomers IC
CROSS APPLY (
    SELECT TOP 1
        C.CustomerID,
        EDIT_DISTANCE_SIMILARITY(IC.ImportedName, C.FirstName + ' ' + C.LastName) AS BestScore
    FROM dbo.Customers C
    ORDER BY EDIT_DISTANCE_SIMILARITY(IC.ImportedName, C.FirstName + ' ' + C.LastName) DESC
) BestMatch
WHERE BestMatch.BestScore >= 60;
GO

SELECT * FROM dbo.ImportedCustomers;
GO

-- 10.2 Spell Check Suggestions
CREATE TABLE dbo.Dictionary
(
    Word NVARCHAR(100) PRIMARY KEY
);
GO

INSERT INTO dbo.Dictionary (Word)
VALUES ('database'), ('table'), ('query'), ('index'), ('column'), ('constraint');
GO

-- Suggest corrections for misspelled word
DECLARE @misspelled NVARCHAR(100) = 'datbase'; -- Missing 'a'

SELECT TOP 3
    Word AS Suggestion,
    EDIT_DISTANCE(@misspelled, Word) AS EditDistance,
    EDIT_DISTANCE_SIMILARITY(@misspelled, Word) AS Confidence
FROM dbo.Dictionary
WHERE EDIT_DISTANCE(@misspelled, Word) <= 2 -- Within 2 edits
ORDER BY EditDistance;
GO

-------------------------------------------------
-- Region: 11. Cleanup
-------------------------------------------------
/*
  Optional: Clean up the demo database.
*/
-- USE master;
-- GO
-- DROP DATABASE IF EXISTS FuzzyMatchDemo;
-- GO