How can I optimize retrieving lowest edit distance from a large table in SQL?

Answer 1

I think your attempt differs from the code that you say works in that the working code orders by distance first, whether or not that is original or trimmed distance. Your attempt orders by original distance first, then trimmed.

I'm not sure I understand what you're trying to do entirely, but does the following do what you need?

SELECT TOP 1
    @ResultId = ID,
    @Result = [Name],
    @ResultDist = distOrig,
    @ResultTrimmed = distTrimmed
FROM (
    SELECT
        ID, [Name], 
        dbo.Levenshtein(@Source, [Name]) As distOrig,
        dbo.Levenshtein(@SourceTrimmed, [Name])) As distTrimmed,
        Frequency
    FROM MyTable
) AS T
ORDER BY
    CASE WHEN distOrig > distTrimmed THEN distOrig ELSE distTrimmed END, -- Distance
    CASE WHEN distOrig > distTrimmed THEN 1 ELSE 0 END,                  -- Trimmed
    Frequency                                                            -- Frequency