如何优化从 SQL 中的大表检索最低编辑距离？

Question

我在优化我正在进行的编辑距离计算时遇到了麻烦。我需要执行以下操作：

1. 获取源字符串的最小距离的记录以及源字符串的修剪版本

2. 选择距离最小的记录
3. 如果最小距离相等（原始与修剪过的），则选择距离最小的修剪过的记录
4. 如果仍有多个记录属于上述两类，则选择出现频率最高的一条

这是我的工作版本：

DECLARE @Results TABLE
(
    ID int,
    [Name] nvarchar(200), 
    Distance int, 
    Frequency int, 
    Trimmed bit
)


INSERT INTO @Results
    SELECT ID, 
           [Name], 
           (dbo.Levenshtein(@Source, [Name])) As Distance,
           Frequency, 
           'False' As Trimmed
    FROM
           MyTable

INSERT INTO @Results
    SELECT ID, 
           [Name], 
           (dbo.Levenshtein(@SourceTrimmed, [Name])) As Distance,
           Frequency, 
           'True' As Trimmed
    FROM
           MyTable

SET @ResultID = (SELECT TOP 1 ID FROM @Results ORDER BY Distance, Trimmed, Frequency)
SET @Result = (SELECT TOP 1 [Name] FROM @Results ORDER BY Distance, Trimmed, Frequency)
SET @ResultDist = (SELECT TOP 1 Distance FROM @Results ORDER BY Distance, Trimmed, Frequency)
SET @ResultTrimmed = (SELECT TOP 1 Trimmed FROM @Results ORDER BY Distance, Trimmed, Frequency)

我相信我在这里需要做的是..

1. 不要将结果哑化到临时表中
2. 仅从“MyTable”中进行 1 个选择
3. 从初始 select 语句中将结果设置为正确。 （因为 select 将设置变量，并且您可以在一个 select 语句中设置多个变量）

我知道必须有一个很好的实现，但我无法弄清楚......这是我所得到的：

SELECT top 1 @ResultID = ID, 
             @Result = [Name], 
            (dbo.Levenshtein(@Source, [Name])) As distOrig,
             (dbo.Levenshtein(@SourceTrimmed, [Name])) As distTrimmed,
             Frequency
FROM
    MyTable
WHERE /* ... yeah I'm lost */
ORDER BY distOrig, distTrimmed, Frequency 

有什么想法吗？

Answer 1

我认为您的尝试与您所说的工作代码不同，因为工作代码首先按距离排序，无论是原始距离还是修剪后的距离。您的尝试首先按原始距离排序，然后进行修剪。

我不确定我完全理解您想要做什么，但是以下内容是否满足您的需要？

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