SQLServerでのトリグラムワイルドカード文字列検索

文字列データで任意の部分文字列の一致を検索することは、SQLServerではコストのかかる操作になる可能性があります。 Column LIKE '%match%'の形式のクエリ bツリーインデックスのシーク機能を使用できないため、クエリプロセッサは各行に個別に述語を適用する必要があります。さらに、各テストは、複雑な照合ルールの完全なセットを正しく適用する必要があります。これらすべての要素を組み合わせると、これらのタイプの検索がリソースを大量に消費し、時間がかかる可能性があるのは当然です。

全文検索は言語マッチングのための強力なツールであり、新しい統計的意味検索は同様の意味を持つドキュメントを見つけるのに最適です。ただし、特定の部分文字列を含む文字列を見つける必要がある場合もあります。どの言語でも、単語ではない可能性のある部分文字列です。

検索されたデータが大きくない場合、または応答時間の要件が重要でない場合は、LIKE '%match%'を使用します。 適切な解決策になる可能性があります。ただし、超高速検索の必要性が他のすべての考慮事項（ストレージスペースを含む）を上回るという奇妙な場合には、n-gramを使用したカスタムソリューションを検討することもできます。この記事で取り上げる特定のバリエーションは、3文字のトライグラムです。

トライグラムを使用したワイルドカード検索

トライグラム検索の基本的な考え方は非常に単純です：

1. ターゲットデータの3文字のサブストリング（トリグラム）を永続化します。
2. 検索語をトライグラムに分割します。
3. 検索トライグラムを保存されているトライグラムと照合します（等式検索）
4. 修飾された行を交差させて、すべてのトライグラムに一致する文字列を見つけます
5. 元の検索フィルターを大幅に削減された交差点に適用します

例を使用して、これがすべてどのように機能するか、およびトレードオフが何であるかを正確に確認します。

サンプルテーブルとデータ

以下のスクリプトは、サンプルテーブルを作成し、それに100万行の文字列データを入力します。各文字列の長さは20文字で、最初の10文字は数字です。残りの10文字は、NEWID()を使用して生成された、AからFまでの数字と文字の混合です。 。このサンプルデータについては、特に特別なことは何もありません。トリグラム技法は非常に一般的です。

-- The test table
CREATE TABLE dbo.Example 
(
    id integer IDENTITY NOT NULL,
    string char(20) NOT NULL,
 
    CONSTRAINT [PK dbo.Example (id)]
        PRIMARY KEY CLUSTERED (id)
);
GO
-- 1 million rows
INSERT dbo.Example WITH (TABLOCKX)
    (string)
SELECT TOP (1 * 1000 * 1000)
    -- 10 numeric characters
    REPLACE(STR(RAND(CHECKSUM(NEWID())) * 1e10, 10), SPACE(1), '0') +
    -- plus 10 mixed numeric + [A-F] characters
    RIGHT(NEWID(), 10)
FROM master.dbo.spt_values AS SV1
CROSS JOIN master.dbo.spt_values AS SV2
OPTION (MAXDOP 1);

約3秒かかります 控えめなラップトップでデータを作成してデータを入力します。データは疑似ランダムですが、目安として次のようになります。

データサンプル

トライグラムの生成

次のインライン関数は、指定された入力文字列から個別の英数字のトライグラムを生成します。

--- Generate trigrams from a string
CREATE FUNCTION dbo.GenerateTrigrams (@string varchar(255))
RETURNS table
WITH SCHEMABINDING
AS RETURN
    WITH
        N16 AS 
        (
            SELECT V.v 
            FROM 
            (
                VALUES 
                    (0),(0),(0),(0),(0),(0),(0),(0),
                    (0),(0),(0),(0),(0),(0),(0),(0)
            ) AS V (v)),
        -- Numbers table (256)
        Nums AS 
        (
            SELECT n = ROW_NUMBER() OVER (ORDER BY A.v)
            FROM N16 AS A 
            CROSS JOIN N16 AS B
        ),
        Trigrams AS
        (
            -- Every 3-character substring
            SELECT TOP (CASE WHEN LEN(@string) > 2 THEN LEN(@string) - 2 ELSE 0 END)
                trigram = SUBSTRING(@string, N.n, 3)
            FROM Nums AS N
            ORDER BY N.n
        )
    -- Remove duplicates and ensure all three characters are alphanumeric
    SELECT DISTINCT 
        T.trigram
    FROM Trigrams AS T
    WHERE
        -- Binary collation comparison so ranges work as expected
        T.trigram COLLATE Latin1_General_BIN2 NOT LIKE '%[^A-Z0-9a-z]%';

その使用例として、次の呼び出し：

SELECT
    GT.trigram
FROM dbo.GenerateTrigrams('SQLperformance.com') AS GT;

次のトライグラムを生成します：

SQLperformance.comトライグラム

この場合、実行プランはT-SQLをかなり直接変換したものです。

• 行の生成（コンスタントスキャンのクロスジョイン）
• 行の番号付け（セグメントおよびシーケンスプロジェクト）
• 文字列の長さに基づいて必要な数を制限する（上）
• 英数字以外の文字を含むトライグラムを削除する（フィルター）
• 重複を削除する（個別の並べ替え）

トライグラムの生成を計画する

トライグラムの読み込み

次のステップは、サンプルデータのトライグラムを永続化することです。トライグラムは新しいテーブルに保持され、作成したインライン関数を使用して入力されます：

-- Trigrams for Example table
CREATE TABLE dbo.ExampleTrigrams
(
    id integer NOT NULL,
    trigram char(3) NOT NULL
);
GO
-- Generate trigrams
INSERT dbo.ExampleTrigrams WITH (TABLOCKX)
    (id, trigram)
SELECT
    E.id,
    GT.trigram
FROM dbo.Example AS E
CROSS APPLY dbo.GenerateTrigrams(E.string) AS GT;

約20秒かかります SQLServer2016ラップトップインスタンスで実行します。この特定の実行により、17,937,972行が生成されました 20文字のテストデータの100万行のトライグラムの。実行プランは、基本的に、サンプルテーブルの各行に対して評価されている関数プランを示しています。

トリグラムテーブルへの入力

このテストはSQLServer2016で実行されたため（ヒープテーブルの読み込み、データベース互換性レベル130、TABLOCK ヒント）、プランは並列挿入の恩恵を受けます。行は、Exampleテーブルの並列スキャンによってスレッド間で分散され、その後は同じスレッドに残ります（再パーティション交換は行われません）。

並べ替え演算子は少し印象的なように見えるかもしれませんが、数値は、ネストされたループ結合のすべての反復にわたって、並べ替えられた行の総数を示しています。実際、それぞれ18行の100万の個別のソートがあります。 4つの並列度（私の場合は2つのコアがハイパースレッド化されています）では、一度に最大4つの小さなソートが実行され、各ソートインスタンスはメモリを再利用できます。これは、この実行プランの最大メモリ使用量が単なる 136KBである理由を説明しています。 （2,152 KBが付与されましたが）

トリグラムテーブルには、各ソーステーブル行（idで識別される）の個別のトリグラムごとに1つの行が含まれます。 ）：

トリグラムテーブルのサンプル

トリグラム一致の検索をサポートするために、クラスター化されたbツリーインデックスを作成します。

-- Trigram search index
CREATE UNIQUE CLUSTERED INDEX
    [CUQ dbo.ExampleTrigrams (trigram, id)]
ON dbo.ExampleTrigrams (trigram, id)
WITH (DATA_COMPRESSION = ROW);

これには約45秒かかります 、その一部はソートの流出によるものですが（私のインスタンスは4GBのメモリに制限されています）。より多くのメモリを使用できるインスタンスは、ログに記録されていない並列インデックスの構築をかなり速く完了する可能性があります。

インデックス作成計画

インデックスが一意として指定されていることに注意してください（キーの両方の列を使用）。トリグラムだけで一意でないクラスター化インデックスを作成することもできますが、SQL Serverは、とにかくほとんどすべての行に4バイトの一意化子を追加します。一意化子が行の可変長部分に（関連するオーバーヘッドとともに）格納されることを考慮に入れると、idを含める方が理にかなっています。 キーに入れて、それで完了します。

行圧縮が指定されているのは、トリグラムテーブルのサイズを277MBから 190MBに効果的に削減できるためです。 （比較のために、サンプルテーブルは32MBです）。少なくともSQLServer2016 SP1（すべてのエディションでデータ圧縮が利用可能になった）を使用していない場合は、必要に応じて圧縮句を省略できます。

最終的な最適化として、トライグラムテーブル上にインデックス付きビューを作成して、データ内で最も一般的で最も一般的でないトライグラムをすばやく簡単に見つけられるようにします。この手順は省略できますが、パフォーマンスのために推奨されます。

-- Selectivity of each trigram (performance optimization)
CREATE VIEW dbo.ExampleTrigramCounts
WITH SCHEMABINDING
AS
SELECT ET.trigram, cnt = COUNT_BIG(*)
FROM dbo.ExampleTrigrams AS ET
GROUP BY ET.trigram;
GO
-- Materialize the view
CREATE UNIQUE CLUSTERED INDEX
    [CUQ dbo.ExampleTrigramCounts (trigram)]
ON dbo.ExampleTrigramCounts (trigram);

インデックス付きビューの構築計画

これは、完了するのに数秒しかかかりません。マテリアライズドビューのサイズは小さく、 104KB 。

トライグラム検索

与えられた検索文字列（例：'%find%this%' ）、私たちのアプローチは次のようになります：

1. 検索文字列のトライグラムの完全なセットを生成します
2. インデックス付きビューを使用して、最も選択的な3つのトライグラムを見つけます
3. 利用可能なすべてのトライグラムに一致するIDを見つけます
4. IDで文字列を取得する
5. 完全なフィルターをトリグラム修飾行に適用します

選択的なトライグラムの検索

最初の2つのステップは非常に簡単です。任意の文字列のトライグラムを生成する関数はすでにあります。これらのトライグラムの中で最も選択的なものを見つけるには、インデックス付きビューに参加します。次のコードは、サンプルテーブルの実装を別のインライン関数にラップします。後で使いやすくするために、最も選択的な3つのトライグラムを1つの行にピボットします。

-- Most selective trigrams for a search string
-- Always returns a row (NULLs if no trigrams found)
CREATE FUNCTION dbo.Example_GetBestTrigrams (@string varchar(255))
RETURNS table
WITH SCHEMABINDING AS
RETURN
    SELECT
        -- Pivot
        trigram1 = MAX(CASE WHEN BT.rn = 1 THEN BT.trigram END),
        trigram2 = MAX(CASE WHEN BT.rn = 2 THEN BT.trigram END),
        trigram3 = MAX(CASE WHEN BT.rn = 3 THEN BT.trigram END)
    FROM 
    (
        -- Generate trigrams for the search string
        -- and choose the most selective three
        SELECT TOP (3)
            rn = ROW_NUMBER() OVER (
                ORDER BY ETC.cnt ASC),
            GT.trigram
        FROM dbo.GenerateTrigrams(@string) AS GT
        JOIN dbo.ExampleTrigramCounts AS ETC
            WITH (NOEXPAND)
            ON ETC.trigram = GT.trigram
        ORDER BY
            ETC.cnt ASC
    ) AS BT;

例として：

SELECT
    EGBT.trigram1,
    EGBT.trigram2,
    EGBT.trigram3 
FROM dbo.Example_GetBestTrigrams('%1234%5678%') AS EGBT;

戻り値（私のサンプルデータの場合）：

選択したトライグラム

実行計画は次のとおりです。

GetBestTrigrams実行プラン

これは、以前からおなじみのトリグラム生成計画であり、各トリグラムのインデックス付きビューを検索し、一致数で並べ替え、行に番号を付け（シーケンスプロジェクト）、セットを3行に制限し（上）、ピボットします。結果（Stream Aggregate）。

すべてのトライグラムに一致するIDを見つける

次のステップは、前のステージで取得されたnull以外のすべてのトライグラムに一致するサンプルテーブルの行IDを見つけることです。ここでのしわは、0、1、2、または3つのトライグラムが利用できる可能性があることです。次の実装は、必要なロジックをマルチステートメント関数でラップし、テーブル変数で修飾IDを返します。

-- Returns Example ids matching all provided (non-null) trigrams
CREATE FUNCTION dbo.Example_GetTrigramMatchIDs
(
    @Trigram1 char(3),
    @Trigram2 char(3),
    @Trigram3 char(3)
)
RETURNS @IDs table (id integer PRIMARY KEY)
WITH SCHEMABINDING AS
BEGIN
    IF  @Trigram1 IS NOT NULL
    BEGIN
        IF @Trigram2 IS NOT NULL
        BEGIN
            IF @Trigram3 IS NOT NULL
            BEGIN
                -- 3 trigrams available
                INSERT @IDs (id)
                SELECT ET1.id
                FROM dbo.ExampleTrigrams AS ET1 
                WHERE ET1.trigram = @Trigram1
                INTERSECT
                SELECT ET2.id
                FROM dbo.ExampleTrigrams AS ET2
                WHERE ET2.trigram = @Trigram2
                INTERSECT
                SELECT ET3.id
                FROM dbo.ExampleTrigrams AS ET3
                WHERE ET3.trigram = @Trigram3
                OPTION (MERGE JOIN);
            END;
            ELSE
            BEGIN
                -- 2 trigrams available
                INSERT @IDs (id)
                SELECT ET1.id
                FROM dbo.ExampleTrigrams AS ET1 
                WHERE ET1.trigram = @Trigram1
                INTERSECT
                SELECT ET2.id
                FROM dbo.ExampleTrigrams AS ET2
                WHERE ET2.trigram = @Trigram2
                OPTION (MERGE JOIN);
            END;
        END;
        ELSE
        BEGIN
            -- 1 trigram available
            INSERT @IDs (id)
            SELECT ET1.id
            FROM dbo.ExampleTrigrams AS ET1 
            WHERE ET1.trigram = @Trigram1;
        END;
    END;
 
    RETURN;
END;

この機能の推定実行計画は、戦略を示しています。

トリグラム一致IDプラン

使用可能なトリグラムが1つある場合は、トリグラムテーブルへの1回のシークが実行されます。それ以外の場合は、2つまたは3つのシークが実行され、効率的な1対多のマージを使用してIDの共通部分が検出されます。このプランにはメモリを消費する演算子がないため、ハッシュやソートが流出する可能性はありません。

検索例を続けると、新しい関数を適用することで、使用可能なトライグラムに一致するIDを見つけることができます。

SELECT EGTMID.id 
FROM dbo.Example_GetBestTrigrams('%1234%5678%') AS EGBT
CROSS APPLY dbo.Example_GetTrigramMatchIDs
    (EGBT.trigram1, EGBT.trigram2, EGBT.trigram3) AS EGTMID;

これにより、次のようなセットが返されます。

マッチングID

新しい関数の実際の（実行後の）計画は、3つのトリグラム入力が使用されている計画の形状を示しています。

実際のIDマッチングプラン

これは、トライグラムマッチングの力を非常によく示しています。 3つのトライグラムはすべて例の表でそれぞれ約11,000行を識別しますが、最初の交差はこのセットを1,004行に減らし、2番目の交差はわずか7に減らします。 。

完全なトライグラム検索の実装

トライグラムに一致するIDができたので、Exampleテーブルで一致する行を検索できます。トライグラムは誤検知を生成する可能性があるため（ただし、誤検知は生成されないため）、最終チェックとして元の検索条件を適用する必要があります。対処すべき最後の問題は、前の段階でトライグラムが見つからなかった可能性があることです。これは、たとえば、検索文字列に含まれる情報が少なすぎることが原因である可能性があります。 '%FF%'の検索文字列 トリグラムを1つでも生成するには、2文字では不十分なため、トリグラム検索を使用できません。このシナリオを適切に処理するために、検索ではこの状態を検出し、トライグラム以外の検索にフォールバックします。

次の最後のインライン関数は、必要なロジックを実装します。

-- Search implementation
CREATE FUNCTION dbo.Example_TrigramSearch
(
    @Search varchar(255)
)
RETURNS table
WITH SCHEMABINDING
AS
RETURN
    SELECT
        Result.string
    FROM dbo.Example_GetBestTrigrams(@Search) AS GBT
    CROSS APPLY
    (
        -- Trigram search
        SELECT
            E.id,
            E.string
        FROM dbo.Example_GetTrigramMatchIDs
            (GBT.trigram1, GBT.trigram2, GBT.trigram3) AS MID
        JOIN dbo.Example AS E
            ON E.id = MID.id
        WHERE
            -- At least one trigram found 
            GBT.trigram1 IS NOT NULL
            AND E.string LIKE @Search
 
        UNION ALL
 
        -- Non-trigram search
        SELECT
            E.id,
            E.string
        FROM dbo.Example AS E
        WHERE
            -- No trigram found 
            GBT.trigram1 IS NULL
            AND E.string LIKE @Search
    ) AS Result;

重要な機能は、GBT.trigram1への外部参照です。 UNION ALLの両側にあります 。これらは、実行プランに起動式を含むフィルターに変換されます。スタートアップフィルターは、条件がtrueと評価された場合にのみサブツリーを実行します。正味の効果は、トリグラムが見つかったかどうかに応じて、すべてのユニオンの一部のみが実行されることです。実行計画の関連部分は次のとおりです。

起動フィルター効果

Example_GetTrigramMatchIDsのいずれか 関数が実行されるか（およびIDのシークを使用して例で結果が検索されます）、または残りのLIKEを使用した例のクラスター化インデックススキャン 述語は実行されますが、両方は実行されません。

パフォーマンス

次のコードは、同等のLIKEに対してトライグラム検索のパフォーマンスをテストします。 ：

SET STATISTICS XML OFF
DECLARE @S datetime2 = SYSUTCDATETIME();
 
SELECT F2.string
FROM dbo.Example AS F2
WHERE
    F2.string LIKE '%1234%5678%'
OPTION (MAXDOP 1);
 
SELECT ElapsedMS = DATEDIFF(MILLISECOND, @S, SYSUTCDATETIME());
GO
SET STATISTICS XML OFF
DECLARE @S datetime2 = SYSUTCDATETIME();
 
SELECT ETS.string
FROM dbo.Example_TrigramSearch('%1234%5678%') AS ETS;
 
SELECT ElapsedMS = DATEDIFF(MILLISECOND, @S, SYSUTCDATETIME());

これらは両方とも同じ結果行を生成しますが、LIKE クエリは2100ms実行されます 、トライグラム検索には15msかかります 。

さらに優れたパフォーマンスが可能です。一般に、トライグラムの選択性が高くなり、数が少なくなると（この実装では最大3つ未満）、パフォーマンスが向上します。例：

SET STATISTICS XML OFF
DECLARE @S datetime2 = SYSUTCDATETIME();
 
SELECT ETS.string
FROM dbo.Example_TrigramSearch('%BEEF%') AS ETS;
 
SELECT ElapsedMS = DATEDIFF(MILLISECOND, @S, SYSUTCDATETIME());

この検索で​​は、 4msで111行がSSMSグリッドに返されました。 。 LIKE 同等のものが1950ms実行されました 。

トライグラムの保守

ターゲットテーブルが静的である場合、ベーステーブルと関連するトリグラムテーブルの同期を維持することに問題はありません。同様に、検索結果を常に完全に最新のものにする必要がない場合は、トリグラムテーブルのスケジュールされた更新が適切に機能する可能性があります。

それ以外の場合は、かなり単純なトリガーを使用して、トライグラム検索データを基になる文字列と同期させておくことができます。一般的な考え方は、削除された行と挿入された行のトリグラムを生成し、必要に応じてそれらをトリグラムテーブルに追加または削除することです。以下の挿入、更新、および削除のトリガーは、実際のこのアイデアを示しています。

-- Maintain trigrams after Example inserts
CREATE TRIGGER MaintainTrigrams_AI
ON dbo.Example
AFTER INSERT
AS
BEGIN
    IF @@ROWCOUNT = 0 RETURN;
    IF TRIGGER_NESTLEVEL(@@PROCID, 'AFTER', 'DML') > 1 RETURN;
    SET NOCOUNT ON;
    SET ROWCOUNT 0;
 
    -- Insert related trigrams
    INSERT dbo.ExampleTrigrams
        (id, trigram)
    SELECT
        INS.id, GT.trigram
    FROM Inserted AS INS
    CROSS APPLY dbo.GenerateTrigrams(INS.string) AS GT;
END;

-- Maintain trigrams after Example deletes
CREATE TRIGGER MaintainTrigrams_AD
ON dbo.Example
AFTER DELETE
AS
BEGIN
    IF @@ROWCOUNT = 0 RETURN;
    IF TRIGGER_NESTLEVEL(@@PROCID, 'AFTER', 'DML') > 1 RETURN;
    SET NOCOUNT ON;
    SET ROWCOUNT 0;
 
    -- Deleted related trigrams
    DELETE ET
        WITH (SERIALIZABLE)
    FROM Deleted AS DEL
    CROSS APPLY dbo.GenerateTrigrams(DEL.string) AS GT
    JOIN dbo.ExampleTrigrams AS ET
        ON ET.trigram = GT.trigram
        AND ET.id = DEL.id;
END;

-- Maintain trigrams after Example updates
CREATE TRIGGER MaintainTrigrams_AU
ON dbo.Example
AFTER UPDATE
AS
BEGIN
    IF @@ROWCOUNT = 0 RETURN;
    IF TRIGGER_NESTLEVEL(@@PROCID, 'AFTER', 'DML') > 1 RETURN;
    SET NOCOUNT ON;
    SET ROWCOUNT 0;
 
    -- Deleted related trigrams
    DELETE ET
        WITH (SERIALIZABLE)
    FROM Deleted AS DEL
    CROSS APPLY dbo.GenerateTrigrams(DEL.string) AS GT
    JOIN dbo.ExampleTrigrams AS ET
        ON ET.trigram = GT.trigram
        AND ET.id = DEL.id;
 
    -- Insert related trigrams
    INSERT dbo.ExampleTrigrams
        (id, trigram)
    SELECT
        INS.id, GT.trigram
    FROM Inserted AS INS
    CROSS APPLY dbo.GenerateTrigrams(INS.string) AS GT;
END;

トリガーは非常に効率的で、単一行と複数行の両方の変更を処理します（MERGEを使用するときに使用できる複数のアクションを含む） 声明）。トライグラムテーブルのインデックス付きビューは、トリガーコードを記述しなくても、SQLServerによって自動的に維持されます。

トリガー操作

例として、ステートメントを実行して、Exampleテーブルから任意の行を削除します。

-- Single row delete
DELETE TOP (1) dbo.Example;

実行後（実際の）実行プランには、削除後トリガーのエントリが含まれています：

トリガー実行プランを削除する

プランの黄色のセクションは、削除されたから行を読み取ります pesudo-tableは、削除されたサンプル文字列ごとにトリグラムを生成し（緑色で強調表示されているおなじみのプランを使用）、関連するトリグラムテーブルエントリを見つけて削除します。赤で示されているプラ​​ンの最後のセクションは、SQL Serverによって自動的に追加され、インデックス付きのビューを最新の状態に保ちます。

挿入トリガーの計画は非常に似ています。更新は、削除に続いて挿入を実行することによって処理されます。次のスクリプトを実行してこれらの計画を確認し、トライグラム検索機能を使用して新しい行と更新された行を見つけることができることを確認します。

-- Single row insert
INSERT dbo.Example (string) 
VALUES ('SQLPerformance.com');
 
-- Find the new row
SELECT ETS.string
FROM dbo.Example_TrigramSearch('%perf%') AS ETS;
 
-- Single row update
UPDATE TOP (1) dbo.Example 
SET string = '12345678901234567890';
 
-- Multi-row insert
INSERT dbo.Example WITH (TABLOCKX)
    (string)
SELECT TOP (1000)
    REPLACE(STR(RAND(CHECKSUM(NEWID())) * 1e10, 10), SPACE(1), '0') +
    RIGHT(NEWID(), 10)
FROM master.dbo.spt_values AS SV1;
 
-- Multi-row update
UPDATE TOP (1000) dbo.Example 
SET string = '12345678901234567890';
 
-- Search for the updated rows
SELECT ETS.string 
FROM dbo.Example_TrigramSearch('12345678901234567890') AS ETS;

マージの例

次のスクリプトは、MERGEを示しています Exampleテーブルを一度に挿入、削除、および更新するために使用されるステートメント：

-- MERGE demo
DECLARE @MergeData table 
(
    id integer UNIQUE CLUSTERED NULL,
    operation char(3) NOT NULL,
    string char(20) NULL
);
 
INSERT @MergeData 
    (id, operation, string)
VALUES 
    (NULL, 'INS', '11223344556677889900'),  -- Insert
    (1001, 'DEL', NULL),                    -- Delete
    (2002, 'UPD', '00000000000000000000');  -- Update
 
DECLARE @Actions table 
(
    action$ nvarchar(10) NOT NULL, 
    old_id integer NULL, 
    old_string char(20) NULL, 
    new_id integer NULL, 
    new_string char(20) NULL
);
 
MERGE dbo.Example AS E
USING @MergeData AS MD
    ON MD.id = E.id
WHEN MATCHED AND MD.operation = 'DEL' 
    THEN DELETE
WHEN MATCHED AND MD.operation = 'UPD' 
    THEN UPDATE SET E.string = MD.string
WHEN NOT MATCHED AND MD.operation = 'INS'
    THEN INSERT (string) VALUES (MD.string)
OUTPUT $action, Deleted.id, Deleted.string, Inserted.id, Inserted.string
INTO @Actions (action$, old_id, old_string, new_id, new_string);
 
SELECT * FROM @Actions AS A;

出力は次のようになります：

アクション出力

最終的な考え

トライグラムを生成する代わりにIDを直接参照することで、大規模な削除および更新操作を高速化する余地があるかもしれません。これは、トライグラムテーブルに新しい非クラスター化インデックスが必要になり、使用される（すでに重要な）ストレージスペースが2倍になるため、ここでは実装されていません。トライグラムテーブルには、単一の整数とchar(3)が含まれています 行ごと;整数列の非クラスター化インデックスは、char(3)を取得します すべてのレベルの列（クラスター化されたインデックスの提供、およびすべてのレベルで一意であるインデックスキーの必要性）。トリグラム検索はすべての読み取りがキャッシュからのものである場合に最適に機能するため、考慮すべきメモリスペースもあります。

追加のインデックスにより、カスケード参照整合性がオプションになりますが、それは多くの場合、価値があるよりも厄介です。

トライグラム検索は万能薬ではありません。追加のストレージ要件、実装の複雑さ、および更新パフォーマンスへの影響はすべて、それに大きく影響します。この手法は、トライグラムを生成しない検索（最小3文字）にも役立ちません。ここに示す基本的な実装は、多くの種類の検索（複数のワイルドカードで始まる、含む、終わる、複数のワイルドカード）を処理できますが、LIKEで機能する可能性のあるすべての検索式を網羅しているわけではありません。 。 ANDタイプのトライグラムを生成する検索文字列に適しています。 ORタイプの処理を必要とする検索文字列、または正規表現などのより高度なオプションを処理するには、さらに多くの作業が必要です。

とはいえ、アプリケーションが本当に必要の場合は、 ワイルドカード文字列の検索が高速であるため、n-gramは真剣に検討する必要があります。

関連コンテンツ：Aaron Bertrandによる主要な％ワイルドカードのインデックスシークを取得する1つの方法。