На просторах интернета легко можно найти материалы по реализации нечёткого поиска, в которых предполагается поиск одной строки в множестве строк M. Но что если возникнет необходимость реализовать нечёткое сравнение множества M₁ с множеством M₂? При классическом подходе нам придется выполнить сравнений - при линейном росте этих множеств, сложность задачи будет расти экспоненциально, в плане производительности это решение никуда не годиться!

Предложенное ниже решение для БД SQL реализовано с помощью хэширования строк по сигнатуре. Оно максимально эффективно выполняет данный поиск в пределах одной ошибки (по расстоянию Левенштейна), но его можно адаптировать и под поиск в пределах какого угодно количества ошибок, но увеличение допуска экспоненциально усложняет алгоритм.

Размер строк также не ограничен, но нечёткий поиск очень большого текста в пределах одной, двух, трёх ошибок можно сравнить со "сферический конём в вакууме" (не могу вообразить, зачем это может понадобится), в этом случае гораздо эффективнее воспользоваться другими методами хэширования - например, SimHash(SimilarityHash)^[1][2][3], MinHash^[1][2]. Поэтому предложенный алгоритм наиболее уместен для поиска средних, малых строк - ФИ, ФИО, VIN, маркировка, спецификация техники, серийные номера, штрихкоды, хэшсуммы и т.д.

Цели:

1. Ознакомить с концепцией

2. Дать конкретный пример интеграции в БД SQL(MSSQL)

3. Ознакомить с возможностями на базе практической реализации

Основная концепция

Хэш по сигнатуре

В целях упрощения восприятия, здесь и далее будем разбираться на примере 32-битного хэша, хотя его размер может быть любым. Кратко описываю алгоритм получения хэша(в практической реализации я буду делать так же):

Правило 2-ух ошибок

Среди всех нечётких хэшей он обладает уникальной особенностью, на которой будет строиться вся дальнейшая работа - он подчиняется "правилу 2-ух ошибок"(для удобства изложения пришлось придумать название самостоятельно, в статье Бойцова Л.М. это свойство описано, но названия не получило). Формулировка: Если расстояние Левенштейна между строками А и B = 1, то расстояние Хэмминга между хэшами от А и Б меньше или равно 2, если это была замена, либо меньше или равно 1, если это была вставка/удаление

Иными словами:

Например, получим сигнатурные хэши от 2-ух одинаковых строк с одной ошибкой:

В строке A была вводная м, которая, очевидно, включала бит №19
В строке B пропала вводная м, и появилась вводная б, которая, очевидно, включила бит №16

Правило 2-ух ошибок позволяет сделать поиск детерменированным - мы можем быть уверены, что точно не пропустим строки с заданным количеством ошибок. Например, очень популярный и действительно неплохо работающий даже на таких небольших строках, как ФИО, SimHash все равно остается вероятностным - 1 ошибка скорее всего поменяет мáлую часть хэша, но всегда остается вероятность того, что хэш изменится кардинально. MinHash тоже вероятностный. Они лучше подходят для больших текстов, например, при сравнении на антиплагиат - особенно, если предварительно обработать их, исключив связующие предлоги, союзы, артикли и т.д.

HEngine

HEngine^[1][2] является алгоритмом ускорения поиска запрашиваемой бинарной строки в множестве таких строк в пределах заданного расстояния Хэмминга. Сейчас попробуем применить этот алгоритм для поиска в пределах 2-ух ошибок на нашем примере, попутно раскрывая его суть:

Если разделить 32-битные хэши A и B на 4 равные части(chunk'и) по 8 бит с сохранением информации об их порядковом номере, то как минимум по двум из них A и B совпадут:

То есть необязательно проверять сплошняком каждый бит. Если мы ищем похожие на А строки в множестве М, мы можем таким же образом дробить хэши на 4, 8, 16 частей и искать match'и соответственно по 2/4, 6/8, 14/16, 30/32(собственно расстояние Хэмминга). Постоянно сужая выборку на текущем этапе "предрасчёта" расстояния Хэмминга, мы будем компенсировать возрастающую стоимость поиска match'ей на следующем этапе (очевидно, что проверить 2/4 легче, чем 30/32).

Более того, если мы ищем строки из M₁, похожие на строки M₂ с расстоянием Левенштейна = 1, после первого самого дешевого этапа (2/4), мы уже получаем не просто сокращенные множества от M₁ и M₂, а суженный набор пар M₁.id-M₂.id, которые теоретически могут быть искомыми. Таким образом уже после первого этапа предрасчёта расстояния Хэмминга перед нами стоит задача не экспоненциальной сложности, а линейной.

Специфика SQL

Вот и весь алгоритм - хэшируем по сигнатуре множества M₁, M₂ и ищем совпадения по HEngine (перебирая 2 массива вложенными циклами). Теоретической новизны в проекте практически нет. Осталось написать пару примеров реализации, и на этом можно было бы и закончить, если бы мы программировали на обычном императивном C-подобном языке программирования. Но, как правило, на практике для хранения/выборки данных используются БД SQL. Внедрение этого поиска в SQL оказалось достаточно сложной задачей, в ходе которой сам алгоритм претерпел много изменений, хотя в сущности концепция осталась прежней.

Предоставление конкретной реализации нечёткого поиска является одной из целей этой статьи. Реализовано на примере MSSQL. Подобное решение можно портировать на любую СУБД, имеющую возможность интеграции стороннего кода(SQLCLR, PL/Java, PL/Python, MySQL Connector/C++ и др.), без каких-либо ограничений.

Необходимость интеграции стороннего кода

Следующие функции очень проблематично реализовать силами процедурного SQL (T-SQL) - производительность будет на плачевном уровне. Поэтому они реализованы через интеграцию стороннего кода (C# SQLCLR)

В SQL нельзя эффективно реализовать алгоритм HEngine полностью

После первого самого дешёвого этапа 2/4, перед нами будет множество пар из M₁.id-M₂.id. Если мы начнем дальше "копать" согласно этому алгоритму (проходить этапы 6/8, 14/16), то в каждой итерации на каждую пару, нужно будет вызывать дважды(на M₁.id и M₂.id) функцию разбивки хэша SplitSignatureHash(), затем полученные множества придется join'ить. Операционная стоимость даже одной SplitSignatureHash() в любом случае больше, чем одной HammingDistanceX32(), потому что она примитивна и работает через битовый XOR. Очевидно, что проходить этапы 6/8, 14/16 в SQL для дальнейшего сужения выборки бессмысленно - эффективнее сразу вызывать HammingDistanceX32().

Базово описываем алгоритм:

Ускорение с помощью k-комбинаций chunk'ов.

При классическом исполнении алгоритма HEngine, БД тратит огромный ресурс на сложное агрегирование данных(3 этап). Эта операция настолько затратна, что оптимизатор запросов SQLServer'а предпочитает сначала выполнять 4-ый этап, производя много лишних запусков HammingDistanceX32() на несгруппированном множестве, но сокращая множество комбинаций, а затем - 3-ий, потому что так дешевле!

Вернемся к нашему примеру. Если A находится в множестве M₁, а B - в M₂. То на 2-ом этапе с комбинации А-Б в множестве комбинаций M₁.id-M₂.id мы получили 2 строки по 2-ум совпадающим парам chunk'ов по индексам 1 и 4. Но помимо интересной нам комбинации, в полученном несгруппированном множестве находятся как интересные нам комбинаций, которые заjoin'ились более чем по 2-ум chunk'ам, так и НЕинтересные, которые заjoin'ились только лишь по 1-му chunk'у - вот поэтому нам необходим 3-ий этап.

Для избежания затратного агрегирования введем функцию стороннего кода SplitSignatureHashKComb() - возвращает все возможные k-комбинации 2/4 chunk'ов по 8 бит:

Во-первых, будем возвращать не 2 поля (i, chunk), а сконкатенированное 2-байтовое (i_chunk). Да, для диапазона значений 0-3 достаточно 2 бит, но байт(8 бит) – это минимальная ячейка адресации. На примере A-B это будет выглядеть следующим образом.

А теперь будем возвращать все возможные k-комбинации i_chunk'ов:

-: Увеличение веса и количества возвращаемых строк. Раньше на каждый хэш приходилось по байт, теперь байт.
+: Не нужно агрегировать комбинации, это дает несопоставимо бóльший выигрыш в производительности

Описываем ускоренный окончательный алгоритм, которым будем пользоваться (теперь можно оценить, как далеко мы ушли от первоначального HEngine):

Стоит отметить, что:

1. На практике оптимизатор запросов SQLServer'а всё равно предпочитает менять 4-ый и - 3-ий этап местами, но сама агрегация гораздо дешевле

2. До 5-го этапа алгоритм обладает свойством резистивности к перестановке слов в строке - порядок в строках не важен(ФИО!=ИФО). Чтобы сохранить это свойство, нам придётся разбивать 5-ый шаг на несколько однотипных расчётов расстояния Левенштейна для каждой комбинации слов в шаблоне(в случае ФИО - это факториал ). Учитывая, что к 5-му этапу выборка уже максимально сужена, это не несёт слишком больших затрат, хотя, конечно, количество слов в шаблоне усложняет 5-ый этап экспоненциально.

DDL vs расчёт на месте

Расчёт на месте

SQLServer на этапе 2/4 сортирует chunk'и и использует MERGE JOIN, т.е. план адекватный

DDL

1. фактически экономим время на расчет хэшей и сортировку(индексацию)

2. меньше дергаем tempDB(больше свободной ОЗУ)

3. Более предсказуемый план выполнения, т.к. оптимизатор SQLServer'а неадекватно оценивает стоимость SQLCLR-функций - они для него словно "закрытый ящик". Например, более дешёвый HammingDistanceX32() имеет бóльший Estimated Operator Cost, чем у LevenshteinDistanceBytes(), потому что имеет больше параметров, несмотря на то, что он примитивнее:

SELECT *
FROM       (SELECT * FROM dbo.employees WHERE dbo.HammingDistanceX32      (id, 25, 32) <= 2) AS t1
INNER JOIN (SELECT * FROM dbo.employees WHERE dbo.LevenshteinDistanceBytes(id, 25)     <= 2) AS t2 ON t1.id = t2.id

Специфика SQL(необязательно к прочтению)

SELECT COUNT(*) FROM SplitSignatureHashKComb(123456, 8, 2)
SELECT COUNT(*) FROM SplitSignatureHashKComb(123456, 4, 6)
SELECT COUNT(*) FROM SplitSignatureHashKComb(123456, 2, 14)

DECLARE @start int = 0
DECLARE @end   int = 2000
DECLARE @step  int = 1

;WITH x AS
(
   SELECT n FROM (VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) v(n)
),
series AS
(
    SELECT TOP (ROUND((@end- @start) / @step, 0) + 1)
           @start - @step + ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) * @step AS n
    FROM
       x as x1, --1           - 10
       x as x2, --11          - 100
       x as x3, --101         - 1000
       x as x4, --1001        - 10 000
       x as x5, --10 001      - 100 000
       x as x6, --100 001     - 1 000 000
       x as x7, --1 000 001   - 10 000 000
       x as x8, --10 000 001  - 100 000 000
       x as x9  --100 000 001 - 1 000 000 000
)
SELECT *
FROM       series s1
CROSS JOIN series s2
WHERE --ABS(s1.n*s2.n - 305)  = 4056/*random int*/
      dbo.xor32(s1.n, s2.n) = 4056/*random int*/

Соление

В этом разделе возможно есть немного теоретической новизны(по крайней мере для русскоязычного интернета). При классическом хэшировании по сигнатуре, если строки разные, но имеют одинаковый набор уникальных букв, случится коллизия.

Хэш должен быть качественным - обладать свойствами устойчивости к коллизиям, которые гарантируются нормальным распределением битов в битовой маске. Иначе на этапе 2/4 будет много лишних join'ов, что негативно скажется на производительности. Чтобы повысить его качество были предприняты попытки его дополнительно посолить(добавить в хэш больше уникальной информации о строке). Пробовались следующие соли, которые применялись к каждой вводной(букве) хэша:

Нарушающие правило 2-ух ошибок

Количество повторений буквы во всей строке

Замена повторяющейся буквы не может изменить хэш более чем на 4 ошибки

Количество повторений буквы в слове

Замена повторяющейся буквы в пределах слова, если нет такой же буквы с таким же кол-вом повторений в другом слове(нет такой же вводной) не может изменить хэш более чем на 4 ошибки

N-gramm'ы

Замена повторяющейся буквы не может изменить хэш более чем на ошибки.

Вывод:

Эти соли усиливают селективность хэша, но увеличение предела допустимых ошибок в хэше экспоненциально негативно влияет на производительность:

          SELECT '1' AS lev_dist,'2/4' AS stage, COUNT(*) AS cnt, MAX(LEN(iChunkKComb)) AS kComb_size, COUNT(*) * MAX(LEN(iChunkKComb)) AS row_size FROM dbo.SplitSignatureHashKComb(123456, 8, 2)  
UNION ALL SELECT '1',            '6/8',          COUNT(*),        MAX(LEN(iChunkKComb)),               COUNT(*) * MAX(LEN(iChunkKComb))             FROM dbo.SplitSignatureHashKComb(123456, 4, 6)  
UNION ALL SELECT '1',            '14/16',        COUNT(*),        MAX(LEN(iChunkKComb)),               COUNT(*) * MAX(LEN(iChunkKComb))             FROM dbo.SplitSignatureHashKComb(123456, 2, 14) 
UNION ALL SELECT '2',            '4/8',          COUNT(*),        MAX(LEN(iChunkKComb)),               COUNT(*) * MAX(LEN(iChunkKComb))             FROM dbo.SplitSignatureHashKComb(123456, 4, 4)  
UNION ALL SELECT '2',            '12/16',        COUNT(*),        MAX(LEN(iChunkKComb)),               COUNT(*) * MAX(LEN(iChunkKComb))             FROM dbo.SplitSignatureHashKComb(123456, 2, 12) 
UNION ALL SELECT '3',            '2/8',          COUNT(*),        MAX(LEN(iChunkKComb)),               COUNT(*) * MAX(LEN(iChunkKComb))             FROM dbo.SplitSignatureHashKComb(123456, 4, 2)  
UNION ALL SELECT '3',            '10/16',        COUNT(*),        MAX(LEN(iChunkKComb)),               COUNT(*) * MAX(LEN(iChunkKComb))             FROM dbo.SplitSignatureHashKComb(123456, 2, 10) 

Но, тем не менее, они могут пригодиться, если мы хотим осуществить "поверхностный/быстрый" поиск. Эти соли значительно ускоряют алгоритм, но становится возможным пропуск искомых совпадений. Появляется уязвимость - можно целенаправленно изменить строку так, чтобы получить ложноотрицательный результат совпадения.

Сохраняющие правило 2-ух ошибок

Отбирать буквы определенного количества повторений.

Замена повторяющейся буквы не может изменить хэш более чем на 2 ошибки, но теряет информацию.

Есть идея использовать как двойной хэш, например, хэш от букв с кол-вом 1 + хэш от букв с кол-вом 2. Они вместе дают неплохую селективность, но затраты на поиск по двойному хэшу тоже значительны - придётся выборку от хэша №1 intersect'ить с выборкой от хэша №2.

Индекс слова

Замена повторяющейся буквы не может изменить хэш более чем на 2 ошибки, но теряется свойство резистивности к перестановке слов в строке.

Вывод: Если нам НЕ нужна резистивность к перестановке слов в строке, то соль по индексу слова считаю наиболее перспективной.

Погружение в код

Как вы уже поняли из всего вышеизложенного материала, я достаточно много "игрался" с размером хэша, k-комбинаций, солями. Объём DDL, который мне пришлось бы писать вручную параллельно дорабатывая "шаблон" создания индекса изначально меня насторожил. Поэтому я сразу прибег к динамическому SQL, который в конечном счёте получился достаточно громоздким, страшным, но работающим. В конце концов, для меня главное - дать пример реализации и представление о производительности интегрированного в SQL алгоритма.
Шаблон не умеет реализовывать:

1. резистивность к перестановке слов в строке - это перегрузило бы и без того перегруженный шаблонизатор DDL'а, это можно дописать вручную при необходимости на готовый шаблон. Все нижележащие тесты проводятся без реализации этого свойства, но это не помешает сравнительному анализу хэшей.

2. двойной/тройной хэш - это перегрузило бы и без того перегруженный шаблонизатор DDL'а, это можно дописать вручную при необходимости на готовый шаблон. Вручную дописанный в тестах показал себя неудачно.

Шаблон умеет:

1. создавать индекс с несколькими однотипными солями:

• classic - без соли

• salt_cnt - количество повторений буквы во всей строке

• salt_cnt_per_word - количество повторений буквы в слове

• salt_i_word - индекс слова

2. создавать индекс с несколькими хэшами с разными фильтрами вводных - для соли с отбором букв определенного количества повторений

Я не буду здесь объяснять, как именно работает инструмент - не вижу смысла лезть в дебри генератора SQL'а - я базово опишу, что он делает и покажу как им пользоваться:

Допустим, нам нужно осуществить нечёткий поиск между двумя однотипными таблицами customers и employees по шаблону first_name + '%' + patronomyc_name + '%' + last_name

CREATE TABLE dbo.customers
(
    id              int IDENTITY(1, 1) PRIMARY KEY,
    first_name      nvarchar(100),
    patronomyc_name nvarchar(100),
    last_name       nvarchar(100),
    gender          nchar(1)
)
CREATE TABLE dbo.employees
(
    id              int IDENTITY(1, 1) PRIMARY KEY,
    first_name      nvarchar(100),
    patronomyc_name nvarchar(100),
    last_name       nvarchar(100),
    gender          nchar(1)
)

Для этого нам понадобятся 2 процедуры - create_SH_fuzzy_search_index и create_SH_fuzzy_search_join

create_SH_fuzzy_search_index

Предназначена для создания индекса на конкретную таблицу. На примере customers 1-граммный 32-битный индекс этапа 2/4 (8-битные chunk'и) без солей(classic) состоит из:

1. Таблицы для хэша с внешним ключом на customers

CREATE TABLE [ix].[customers_full_name_H_1gram_x32]
(
     [row_num] int NOT NULL
    ,[classic] varbinary(4)
    ,CONSTRAINT [PK_customers_full_name_H_1gram_x32]                      PRIMARY KEY ([row_num])
    ,CONSTRAINT [FK_customers_full_name_H_1gram_x32.row_num-customers.id] FOREIGN KEY ([row_num]) REFERENCES [dbo].[customers]([id]) ON DELETE CASCADE
)

2. Таблицы для k-комбинаций chunk'ов от хэша с внешним ключом на таблицу для хэша и индексами - это основная таблица, по которой будет идти первичный поиск этапа 2/4

CREATE TABLE [ix].[customers_full_name_H_1gram_x32_C_x8_K_2/4]
(
     [row_num] int NOT NULL
    ,[classic] varbinary(4)
    ,CONSTRAINT [FK_customers_full_name_H_1gram_x32_C_x8_K_2/4.row_num-customers_full_name_H_1gram_x32.row_num] FOREIGN KEY ([row_num]) REFERENCES [ix].[customers_full_name_H_1gram_x32]([row_num]) ON DELETE CASCADE
)
CREATE CLUSTERED INDEX [customers_full_name_H_1gram_x32_C_x8_K_2/4.row_num] ON [ix].[customers_full_name_H_1gram_x32_C_x8_K_2/4] ([row_num])
CREATE INDEX [customers_full_name_H_1gram_x32_C_x8_K_2/4.classic] ON [ix].[customers_full_name_H_1gram_x32_C_x8_K_2/4] ([classic])

3.Триггер на customers для заполнения таблицы для хэша. Стоит отметить, что он достаточно умный:

• не триггериться на строки, у которых template не изменился, чтобы не замедлять update'ы в таблице, если они не меняют template

• не включает в индекс строки, у которых пустой template - множество таких строк замедляет работу алгоритма, т.к. хэши от таких template'ов одинаковы -> появляются неуникальные значения -> селективность падает

-- generated in dbo.p_create_SH_fuzzy_search_index
ALTER TRIGGER [dbo].[TR_customers_full_name_H_1gram_x32]
   ON [dbo].[customers]
   AFTER INSERT, UPDATE
AS
BEGIN
    SET NOCOUNT ON;

    DELETE FROM [ix].[customers_full_name_H_1gram_x32]
    WHERE row_num IN
    (
    SELECT I.id
    FROM      (SELECT id, ISNULL(first_name, '') + '%' + ISNULL(patronomyc_name, '') + '%' + ISNULL(last_name, '') AS template FROM Inserted) I
    LEFT JOIN (SELECT id, ISNULL(first_name, '') + '%' + ISNULL(patronomyc_name, '') + '%' + ISNULL(last_name, '') AS template FROM Deleted)  D ON D.id        = I.id
                                                                                                                                               AND D.template <> I.template
    WHERE D.id IS NOT NULL -- changed rows
    )

    INSERT INTO [ix].[customers_full_name_H_1gram_x32] ([row_num], [classic])
    SELECT I.id
          ,dbo.GetSignatureHash(I.template, 1, '%', 65001, 0/*classic*/, 0, 32)
    FROM      (SELECT id, ISNULL(first_name, '') + '%' + ISNULL(patronomyc_name, '') + '%' + ISNULL(last_name, '') AS template FROM Inserted) AS I
    LEFT JOIN (SELECT id, ISNULL(first_name, '') + '%' + ISNULL(patronomyc_name, '') + '%' + ISNULL(last_name, '') AS template FROM Deleted)  AS D ON D.id        = I.id
                                                                                                                                                  AND D.template <> I.template
    LEFT JOIN [ix].[customers_full_name_H_1gram_x32]                                                                                          AS H ON H.row_num   = I.id
    WHERE (   D.id       IS NOT NULL  -- changed rows
           OR H.row_num  IS     NULL) -- haven't been inserted yet
      AND REPLACE(I.template, '%', '') <> ''
END

4.Триггер на таблицу для хэша для заполнения таблицы k-комбинаций хэша

-- generated in dbo.p_create_SH_fuzzy_search_index
ALTER TRIGGER [ix].[TR_customers_full_name_H_1gram_x32_C_x8_K_2/4]
   ON [ix].[customers_full_name_H_1gram_x32]
   AFTER INSERT, UPDATE
AS
BEGIN
    SET NOCOUNT ON;

    DELETE FROM [ix].[customers_full_name_H_1gram_x32_C_x8_K_2/4] WHERE row_num IN (SELECT row_num FROM Inserted)

    INSERT INTO [ix].[customers_full_name_H_1gram_x32_C_x8_K_2/4] ([row_num], [classic])
    SELECT [row_num], [classic].iChunkKComb
    FROM Inserted
    CROSS APPLY dbo.SplitSignatureHashKComb([classic], 8, 2) AS [classic] WHERE  [classic].i = [classic].i 
END

После всех манипуляций нам остается лишь "дёрнуть" за любое поле customers следующим образом UPDATE dbo.customers SET Gender = Gender WHERE 1 = 1 и индекс заполнится по цепочке:
1.UPDATE
2.Триггер на customers заполнит таблицу для хэша
3.Триггер таблицы для хэша заполнит таблицу k-комбинаций хэша

То же самое динамическим SQL:

EXEC dbo.create_SH_fuzzy_search_index
    @schema_name            = 'dbo',
    @table_name             = 'customers', @table_id_field_name = 'id',
    --@table_name             = 'employees', @table_id_field_name = 'id',
    @table_mock_field_name  = 'Gender',
    @postfix                = 'full_name',
    @template               = 'ISNULL(first_name, '''') + ''%'' + ISNULL(patronomyc_name, '''') + ''%'' + ISNULL(last_name, '''')',
    @delimiter              = '%',
                            
    @h_table                = '',
    @hc_name                = '',
    @hc_table               = '',
    @h_table_join           = '',
    @hc_table_join          = '',
    @hc_table_case_col      = '',
    @hc_table_case_col_name = '',
    @row_size               = NULL,
                            
    @h_schema_name          = 'ix',
    @codepage               = '65001',
    @n                      = '1',
    @hashSize               = '32',
    @hashChunkSize          = '8',
    @kCombCount             = '2',
    @nGramHashModes         = '0',
    @salt_filter            = '0',
                            
    @is_del                 = 1,
    @top                    = 999999,
    @DEBUG                  = 0

create_SH_fuzzy_search_join

Создаёт полноценный связочный индекс между двумя таблицами и процедуры, функции для работы с ним. Возвращаясь к нашей задаче:

1. Запускает create_SH_fuzzy_search_index для customers

2. Запускает create_SH_fuzzy_search_index для employees

3. Создаёт основную TVF, в которой хранится весь алгоритм поиска

/*
Generated in create_SH_fuzzy_search_join
-- usage
SELECT * FROM [ix].[customers_full_name-employees_full_name_H_1gram_x32_C_x8_K_2/4](1, 1) AS SH_search
*/
ALTER FUNCTION [ix].[customers_full_name-employees_full_name_H_1gram_x32_C_x8_K_2/4]
(
    @col_num    int = 1,
    @only_fuzzy int = 1
)
RETURNS table AS RETURN
(
 	--DECLARE @col_num int = 1, @only_fuzzy int = 1
    WITH
    residual_chunks AS
    (
        SELECT hc1.row_num AS rn1,
               hc2.row_num AS rn2
        FROM       [ix].[customers_full_name_H_1gram_x32_C_x8_K_2/4] AS hc1
        INNER JOIN [ix].[employees_full_name_H_1gram_x32_C_x8_K_2/4] AS hc2 ON (@col_num = 1 AND hc1.classic = hc2.classic)
    ),
    residual_ham_dist AS
    (
        SELECT DISTINCT
               rn1, rn2
        FROM             residual_chunks AS residual
        INNER JOIN [ix].[customers_full_name_H_1gram_x32] AS h1 ON residual.rn1 = h1.row_num
        INNER JOIN [ix].[employees_full_name_H_1gram_x32] AS h2 ON residual.rn2 = h2.row_num
        WHERE (@col_num = 1 AND dbo.HammingDistanceX32(h1.classic, h2.classic, 2) <= 2)
    ),
    residual_lev_dist AS -- query optimizer leaves this CTE for last, because it's necessary to JOIN the templates, which is what we want
    (
        SELECT residual.rn1, residual.rn2, t1.templ1, t2.templ2
        FROM       residual_ham_dist AS residual
        INNER JOIN (SELECT id AS rn1, ISNULL(first_name, '') + '%' + ISNULL(patronomyc_name, '') + '%' + ISNULL(last_name, '') AS templ1 FROM dbo.customers) AS t1 ON t1.rn1 = residual.rn1
        INNER JOIN (SELECT id AS rn2, ISNULL(first_name, '') + '%' + ISNULL(patronomyc_name, '') + '%' + ISNULL(last_name, '') AS templ2 FROM dbo.employees) AS t2 ON t2.rn2 = residual.rn2
        WHERE (@only_fuzzy = 0 AND dbo.LevenshteinDistanceString(t1.templ1, t2.templ2) <= 1)
           OR (@only_fuzzy = 1 AND dbo.LevenshteinDistanceString(t1.templ1, t2.templ2)  = 1)
    )
    SELECT * FROM residual_lev_dist
)

4. Создаёт вспомогательную процедуру [ix].[customers_full_name-employees_full_name_H_1gram_x32_C_x8_K_2/4(filter)] для удобной работы с индексом, позволяет join'ить другие таблицы и навешивать предикаты

5. Создаёт вспомогательную процедуру [ix].[customers_full_name-employees_full_name_H_1gram_x32_C_x8_K_2/4(index_size)] для анализа размера индекса

6. Создаёт вспомогательную процедуру [ix].[customers_full_name-employees_full_name_H_1gram_x32_C_x8_K_2/4(stat) для анализа селективности и заполненности хэша

То же самое динамическим SQL

EXEC dbo.create_SH_fuzzy_search_join
    @schema_name_1           = 'dbo',
    @table_name_1            = 'customers', 
    @table_id_field_name_1   = 'id',
    @table_mock_field_name_1 = 'Gender',
    @postfix_1               = 'full_name',
    @template_1              = 'ISNULL(first_name, '''') + ''%'' + ISNULL(patronomyc_name, '''') + ''%'' + ISNULL(last_name, '''')',
    @delimiter_1             = '%',

    @schema_name_2           = 'dbo',
    @table_name_2            = 'employees', 
    @table_id_field_name_2   = 'id',
    @table_mock_field_name_2 = 'Gender',
    @postfix_2               = 'full_name',
    @template_2              = 'ISNULL(first_name, '''') + ''%'' + ISNULL(patronomyc_name, '''') + ''%'' + ISNULL(last_name, '''')',
    @delimiter_2             = '%',

    @h_schema_name           = 'ix',
    @codepage                = '65001',
    @n                       = '1',
    @hashSize                = '32',
    @hashChunkSize           = '8',
    @kCombCount              = '2',
    @nGramHashModes          = '0',
    @salt_filter             = '0',
    @lev_dist                = '1',
                 
    @is_del                  = 0,
    @top                     = 999999,
    @DEBUG                   = 0

Тестирование

Как пройти по моим стопам описано в github.com/VGoren/SHFuzzySearch/README.md. На моей машине с Intel Core i3 7gen Windows 11 x64 все тесты отрабатывают примерно за 1 час. Если у вас железо помощнее, то можно увеличить переменные @top_stat(для анализа индекса) и @top_srch(для замера производительности индекса). @top_stat меньше, т.к. вспомогательная аналитическая процедура (с постфиксом stat) достаточно затратная(не использует многопоток), в то же время данные однородны - увеличение выборки не влияет на аналитические показатели индекса.

Итак, если всё сделали верно, то получите следующий результат:

Проанализируем результаты на примере выборки 5000 customers с 5000 employees:

1. Если требуется реализовать нечёткий поиск БЕЗ резистивности к перестановке слов, то:

• salt_i_word - показывал себя наилучшим образом

• 2gram + salt_i_word несплошной(2/4) - можно использовать в качестве беглого поиска

2. Если требуется реализовать нечёткий поиск С резистивностью к перестановке слов, то salt_i_word использовать нельзя, поэтому практически все соли могут найти своё применение:

• salt_cnt_per_word - беглый поиск

• salt_cnt - более беглый поиск

• 2gram несплошной(2/4) - наиболее беглый поиск

• 2gram сплошной(4/8) - отрабатывает лучше classic'а, но весит больше

3. Двойной хэш classic_1_2 везде проигрывает в производительности, хотя его селективность(residual_chunks_%) слегка выше, чем у classic'а. Он теряет информацию о буквах с 3, 4, 5... повторениями. Поиск по тройному, четверному... хэшу потребует дополнительных intersect'ов, что повлечёт за собой увеличение операционной стоимости.

4. У беглых поисков уменьшение селективности(residual_chunks_%) - не всегда обозначает снижение истинной селективности, это может быть связано с уменьшением уязвимости к ложноотрицательным результатам - просто поиск становится более тщательным.
   

   

5. На малых размерах индекса (размер хэша/количество строк в исходной таблице) прослеживается, что предельное увеличение размера хэша(hash_size) меньше предельного увеличения размера данных индексных таблиц(data(KB)) - SQLServer резервирует минимальное место под хранение метаданных, таких как информация о таблицах, столбцах, индексах и ограничениях
   

   

6. Расчётный размер данных индексных таблиц data_calculated(KB) меньше, чем data(KB) - SQLServer оставляет свободные "страницы" с определённым fill-factor'ом таблицы (не путать с fill-factor'ом индекса) в файле данных для оптимизации операций с таблицей.

6. График зависимости размера хэша(hash_size) от фактического времени поиска(time_srch) представляет из себя кривую параболического типа, на неё с двух сторон влияют следующие основные негативные факторы:

При уменьшении размера хэша:

• Поиск по переполненному хэшу сопровождается множеством коллизионных join'ов переполненных chunk'ов

• Вероятность коллизии разных вводных внутри хэша - 1/hash_size(одна и та же буква может занять один и тот же бит). Чем сильнее селекивность(residual_chunks_%) хэша, тем губительнее для него этот фактор, поэтому максимальная скорость classic'а раскрывается на x512, а salt_i_word'а - на x1024.

При увеличении размера хэша:

• Увеличение размера хэша, очевидно, увеличивает операционную стоимость join'ов. На слишком малых размерах хэшей проявляется слабо, потому что как SQLServer в частности, так и .NET в целом "под капотом" зачастую приводят значения к бóльшему типу данных - в конце концов, в современной 64-битной ОС процессор обрабатывает 64 бита за один такт.

• Поиск по слишком недозаполненному хэшу сопровождается множеством коллизионных join'ов вообще пустых chunk'ов. Проявляется на слишком недозаполненных хэшах.

7. Кривая смещена по горизонтали влево. Влияние негативных факторов при уменьшении размера хэша усиливается сильнее, чем у негативных факторов при увеличении размера хэша - недозаполненный хэш лучше переполненного.

8. Помимо основных факторов, на графике не отображены, но продолжают воздействовать дополнительные факторы: величина шаблона, уникальность данных, лингвистический аспект, количество букв в алфавите, рандом и др. Поэтому не стоит удивляться, что хэш x128 выбивается из общего ряда в худшую сторону. Возможно, на другом наборе данных он отработал бы лучше.

9. Тестирование изменения размера текста не проводилось, но очевидно, что с его увеличением при заполнении сигнатурного хэша, мы неизбежно упрёмся в количество уникальных символов в алфавите, а при использовании солей - в статистическое сглаживание. В этом случае остается лишь одно - за вводные брать большие n-граммы, но они пропорционально увеличивают допуск ошибок в хэше. Для очень больших текстов этот поиск - не лучший выбор

Итого, увеличивать размера хэша(hash_size) стоит до тех пор, пока:

1. Вас устраивает размер индекса

2. Не перестанет увеличиваться селективность(уменьшаться residual_chunks_%)

3. Не перестанет уменьшаться фактическое время поиска(time_srch)

Да, инструмент узкоспециализированный... Надеюсь, кому-то пригодится. Спасибо за внимание!