Pencarian String Wildcard Trigram di SQL Server

Mencari data string untuk kecocokan substring yang berubah-ubah bisa menjadi operasi yang mahal di SQL Server. Query berbentuk Column LIKE '%match%' tidak dapat menggunakan kemampuan pencarian dari indeks b-tree, sehingga pemroses kueri harus menerapkan predikat ke setiap baris satu per satu. Selain itu, setiap tes harus benar menerapkan set lengkap aturan susunan yang rumit. Menggabungkan semua faktor ini bersama-sama, tidak mengherankan bahwa jenis penelusuran ini bisa memakan banyak sumber daya dan lambat.

Pencarian Teks Lengkap adalah alat yang ampuh untuk pencocokan linguistik, dan Pencarian Semantik Statistik yang lebih baru sangat bagus untuk menemukan dokumen dengan arti yang serupa. Namun terkadang, Anda benar-benar hanya perlu menemukan string yang berisi substring tertentu – substring yang bahkan mungkin bukan kata, dalam bahasa apa pun.

Jika data yang dicari tidak besar, atau persyaratan waktu respons tidak penting, gunakan LIKE '%match%' bisa menjadi solusi yang tepat. Namun, pada kesempatan aneh di mana kebutuhan akan pencarian super cepat mengalahkan semua pertimbangan lain (termasuk ruang penyimpanan), Anda dapat mempertimbangkan solusi khusus menggunakan n-gram. Variasi spesifik yang dieksplorasi dalam artikel ini adalah trigram tiga karakter.

Pencarian karakter pengganti menggunakan trigram

Ide dasar pencarian trigram cukup sederhana:

Pertahankan substring tiga karakter (trigram) dari data target.
Pisahkan istilah penelusuran menjadi trigram.
Cocokkan trigram penelusuran dengan trigram yang disimpan (pencarian kesetaraan)
Potong baris yang memenuhi syarat untuk menemukan string yang cocok dengan semua trigram
Terapkan filter penelusuran asli ke persimpangan yang jauh lebih sedikit

Kami akan bekerja melalui sebuah contoh untuk melihat dengan tepat bagaimana semua ini bekerja, dan apa komprominya.

Contoh tabel dan data

Skrip di bawah ini membuat tabel contoh dan mengisinya dengan jutaan baris data string. Setiap string memiliki panjang 20 karakter, dengan 10 karakter pertama berupa angka. 10 karakter sisanya adalah campuran angka dan huruf dari A hingga F, dibuat menggunakan NEWID() . Tidak ada yang istimewa dari data sampel ini; teknik trigramnya cukup umum.

-- The test tableCREATE TABLE dbo.Contoh ( id integer IDENTITY NOT NULL, string char(20) NOT NULL, CONSTRAINT [PK dbo.Contoh (id)] PRIMARY KEY CLUSTERED (id));GO-- 1 juta rowsINSERT dbo.Contoh WITH (TABLOCKX) (string)SELECT TOP (1 * 1000 * 1000) -- 10 karakter numerik REPLACE(STR(RAND(CHECKSUM(NEWID())) * 1e10, 10), SPACE(1), ' 0') + -- ditambah 10 campuran numerik + [A-F] karakter KANAN(BARU(), 10)FROM master.dbo.spt_values AS SV1CROSS GABUNG master.dbo.spt_values AS SV2OPTION (MAXDOP 1);

Dibutuhkan sekitar 3 detik untuk membuat dan mengisi data di laptop sederhana saya. Datanya pseudorandom, tetapi sebagai indikasi akan terlihat seperti ini:

Contoh data

Membuat trigram

Fungsi sebaris berikut menghasilkan trigram alfanumerik yang berbeda dari string input yang diberikan:

--- Menghasilkan trigram dari stringCREATE FUNCTION dbo.GenerateTrigrams (@string varchar(255))RETURNS tableWITH SCHEMABINDINGAS 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)), -- Tabel Bilangan (256) Bilangan AS ( SELECT n =ROW_NUMBER() OVER (ORDER BY A.v) FROM N16 AS A CROSS GABUNG N16 AS B ), Trigram AS ( -- Setiap substring 3 karakter SELECT TOP (CASE WHEN WHEN(@string)> 2 THEN LEN(@string) - 2 ELSE 0 END) trigram =SUBSTRING(@string, N.n, 3) FROM Nums AS N ORDER BY N.n ) -- Hapus duplikat dan pastikan semua tiga karakter adalah alfanumerik SELECT DISTINCT T.trigram FROM Trigrams AS T WHERE -- Binary collation comparison so r anges bekerja seperti yang diharapkan T.trigram COLLATE Latin1_General_BIN2 NOT LIKE '%[^A-Z0-9a-z]%';

Sebagai contoh penggunaannya, berikut panggilannya:

PILIH GT.trigramFROM dbo.GenerateTrigrams('SQLperformance.com') AS GT;

Menghasilkan trigram berikut:

trigram SQLperformance.com

Rencana eksekusi adalah terjemahan langsung dari T-SQL dalam hal ini:

Membuat baris (gabungan silang dari Pemindaian Konstan)
Penomoran baris (Proyek Segmen dan Urutan)
Membatasi angka yang dibutuhkan berdasarkan panjang string (Atas)
Hapus trigram dengan karakter non-alfanumerik (Filter)
Hapus duplikat (Urutan Berbeda)

Rencana untuk membuat trigram

Memuat trigram

Langkah selanjutnya adalah mempertahankan trigram untuk contoh data. Trigram akan disimpan di tabel baru, diisi menggunakan fungsi sebaris yang baru saja kita buat:

-- Trigrams for Example tableCREATE TABLE dbo.ExampleTrigrams( id integer NOT NULL, trigram char(3) NOT NULL);GO-- Generate trigramsINSERT dbo.ExampleTrigrams WITH (TABLOCKX) (id, trigram)SELECT E.id, GT.trigramFROM dbo.Contoh AS ECROSS APPLY dbo.GenerateTrigrams(E.string) AS GT;

Itu membutuhkan waktu sekitar 20 detik untuk dijalankan pada instance laptop SQL Server 2016 saya. Proses khusus ini menghasilkan 17.937.972 baris trigram untuk 1 juta baris data uji 20 karakter. Rencana eksekusi pada dasarnya menunjukkan rencana fungsi yang dievaluasi untuk setiap baris tabel Contoh:

Mengisi tabel trigram

Karena pengujian ini dilakukan pada SQL Server 2016 (memuat tabel heap, di bawah tingkat kompatibilitas database 130, dan dengan TABLOCK petunjuk), rencana mendapat manfaat dari penyisipan paralel. Baris didistribusikan di antara utas dengan pemindaian paralel dari tabel Contoh, dan tetap berada di utas yang sama setelahnya (tidak ada pertukaran partisi ulang).

Operator Sort mungkin terlihat sedikit mengesankan, tetapi angka menunjukkan jumlah total baris yang diurutkan, pada semua iterasi dari gabungan loop bersarang. Faktanya, ada satu juta jenis terpisah, masing-masing terdiri dari 18 baris. Pada tingkat paralelisme empat (dua inti hyperthreaded dalam kasus saya), ada maksimum empat pengurutan kecil yang terjadi pada satu waktu, dan setiap contoh pengurutan dapat menggunakan kembali memori. Ini menjelaskan mengapa penggunaan memori maksimum dari rencana eksekusi ini hanya 136KB (meskipun 2.152 KB diberikan).

Tabel trigram berisi satu baris untuk setiap trigram yang berbeda di setiap baris tabel sumber (diidentifikasi dengan id ):

Contoh tabel trigram

Kami sekarang membuat indeks b-tree berkerumun untuk mendukung pencarian kecocokan trigram:

-- Indeks pencarian trigramCREATE UNIQUE CLUSTERED INDEX [CUQ dbo.ExampleTrigrams (trigram, id)]ON dbo.ExampleTrigrams (trigram, id)DENGAN (DATA_COMPRESSION =ROW);

Ini membutuhkan waktu sekitar 45 detik , meskipun beberapa di antaranya disebabkan oleh jenis yang tumpah (contoh saya terbatas pada memori 4GB). Instance dengan lebih banyak memori yang tersedia mungkin dapat menyelesaikan pembuatan indeks paralel dengan log minimal sedikit lebih cepat.

Rencana pembangunan indeks

Perhatikan bahwa indeks ditentukan sebagai unik (menggunakan kedua kolom di kunci). Kita bisa saja membuat indeks berkerumun non-unik pada trigram saja, tetapi SQL Server akan menambahkan uniquifiers 4-byte ke hampir semua baris. Setelah kami memperhitungkan bahwa uniquifiers disimpan di bagian panjang variabel dari baris (dengan overhead terkait), lebih masuk akal untuk memasukkan id di kunci dan selesai dengan itu.

Kompresi baris ditentukan karena berguna untuk mengurangi ukuran tabel trigram dari 277 MB menjadi 190 MB (sebagai perbandingan, tabel Contoh adalah 32MB). Jika Anda setidaknya tidak menggunakan SQL Server 2016 SP1 (di mana kompresi data tersedia untuk semua edisi), Anda dapat menghilangkan klausa kompresi jika perlu.

Sebagai pengoptimalan terakhir, kami juga akan membuat tampilan terindeks di atas tabel trigram agar cepat dan mudah menemukan trigram mana yang paling banyak dan paling tidak umum dalam data. Langkah ini dapat diabaikan, tetapi disarankan untuk performa.

-- Selektivitas setiap trigram (optimasi kinerja)CREATE VIEW dbo.ExampleTrigramCountsWITH SCHEMABINDINGASSELECT ET.trigram, cnt =COUNT_BIG(*)FROM dbo.ExampleTrigrams AS ETGROUP BY ET.trigram;GO-- Wujudkan tampilanCLUSTERED UNIQUE CUQ dbo.ExampleTrigramCounts (trigram)]ON dbo.ExampleTrigramCounts (trigram);

Rencana bangunan tampilan yang diindeks

Ini hanya membutuhkan beberapa detik untuk menyelesaikannya. Ukuran tampilan yang terwujud sangat kecil, hanya 104KB .

Penelusuran trigram

Diberikan string pencarian (mis. '%find%this%' ), pendekatan kami adalah:

Buat set lengkap trigram untuk string pencarian
Gunakan tampilan terindeks untuk menemukan tiga trigram paling selektif
Temukan id yang cocok dengan semua trigram yang tersedia
Ambil string dengan id
Terapkan filter lengkap ke baris yang memenuhi syarat trigram

Menemukan trigram selektif

Dua langkah pertama cukup mudah. Kami sudah memiliki fungsi untuk menghasilkan trigram untuk string arbitrer. Menemukan yang paling selektif dari trigram tersebut dapat dicapai dengan bergabung ke tampilan yang diindeks. Kode berikut membungkus implementasi untuk tabel contoh kita dalam fungsi sebaris lainnya. Ini memutar tiga trigram paling selektif menjadi satu baris untuk kemudahan penggunaan nanti:

-- Trigram paling selektif untuk string pencarian-- Selalu mengembalikan baris (NULL jika tidak ada trigram yang ditemukan)CREATE FUNCTION dbo.Example_GetBestTrigrams (@string varchar(255))RETURNS tableWITH SCHEMABINDING ASRETURN SELECT -- Pivot trigram1 =MAX( KASUS KETIKA BT.rn =1 MAKA BT.trigram AKHIR), trigram2 =MAX(KASUS KETIKA BT.rn =2 MAKA BT.trigram AKHIR), trigram3 =MAX(KASUS KETIKA BT.rn =3 MAKA BT.trigram AKHIR) DARI ( -- Hasilkan trigram untuk string pencarian -- dan pilih tiga yang paling selektif SELECT TOP (3) rn =ROW_NUMBER() OVER ( ORDER BY ETC.cnt ASC), GT.trigram FROM dbo.GenerateTrigrams(@string) AS GT GABUNG dbo.ExampleTrigramCounts AS DLL WITH (NOEXPAND) DI ETC.trigram =GT.trigram ORDER BY ETC.cnt ASC ) SEBAGAI BT;

Sebagai contoh:

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

pengembalian (untuk sampel data saya):

Trigram yang dipilih

Rencana eksekusi adalah:

Rencana eksekusi GetBestTrigrams

Ini adalah rencana pembuatan trigram yang sudah dikenal sebelumnya, diikuti dengan pencarian ke tampilan yang diindeks untuk setiap trigram, mengurutkan berdasarkan jumlah kecocokan, memberi nomor baris (Proyek Urutan), membatasi kumpulan menjadi tiga baris (Atas), lalu berputar hasilnya (Stream Agregat).

Menemukan ID yang cocok dengan semua trigram

Langkah selanjutnya adalah menemukan Contoh id baris tabel yang cocok dengan semua trigram non-null yang diambil oleh tahap sebelumnya. Kerutan di sini adalah bahwa kita mungkin memiliki nol, satu, dua, atau tiga trigram yang tersedia. Implementasi berikut membungkus logika yang diperlukan dalam fungsi multi-pernyataan, mengembalikan id yang memenuhi syarat dalam variabel tabel:

-- Mengembalikan Contoh id yang cocok dengan semua trigram yang disediakan (non-null)CREATE FUNCTION dbo.Example_GetTrigramMatchIDs( @Trigram1 char(3), @Trigram2 char(3), @Trigram3 char(3))RETURNS @IDs tabel (id integer PRIMARY KEY)DENGAN SCHEMABINDING ASBEGIN JIKA @Trigram1 TIDAK NULL MULAI JIKA @Trigram2 BUKAN NULL MULAI JIKA @Trigram3 TIDAK NULL BEGIN -- 3 trigram tersedia INSERT @IDs (id) SELECT ET1.id FROM dbo.ContohTrigram WHERE AS 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 JOINTION); AKHIR; ELSE BEGIN -- 2 trigram tersedia 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 =OPTION @Trigram2 GABUNG GABUNG); AKHIR; AKHIR; ELSE BEGIN -- 1 trigram tersedia INSERT @IDs (id) SELECT ET1.id FROM dbo.ExampleTrigrams AS ET1 WHERE ET1.trigram =@Trigram1; AKHIR; AKHIR; RETURN;END;

Perkiraan rencana eksekusi untuk fungsi ini menunjukkan strategi:

Rencana id pencocokan trigram

Jika ada satu trigram yang tersedia, pencarian tunggal ke dalam tabel trigram dilakukan. Jika tidak, dua atau tiga pencarian dilakukan dan persimpangan id ditemukan menggunakan penggabungan satu-ke-banyak yang efisien. Tidak ada operator yang menghabiskan memori dalam paket ini, jadi tidak ada kemungkinan tumpahan hash atau sortir.

Melanjutkan pencarian contoh, kita dapat menemukan id yang cocok dengan trigram yang tersedia dengan menerapkan fungsi baru:

PILIH EGTMID.id FROM dbo.Example_GetBestTrigrams('%1234%5678%') SEBAGAI EGBTCROSS BERLAKU dbo.Example_GetTrigramMatchIDs (EGBT.trigram1, EGBT.trigram2, EGBT.trigram3) SEBAGAI EGTMID;

Ini mengembalikan satu set seperti berikut:

ID yang Cocok

Rencana aktual (pasca-eksekusi) untuk fungsi baru menunjukkan bentuk rencana dengan tiga input trigram yang digunakan:

Paket pencocokan ID yang sebenarnya

Ini menunjukkan kekuatan pencocokan trigram dengan cukup baik. Meskipun ketiga trigram masing-masing mengidentifikasi sekitar 11.000 baris dalam tabel Contoh, persimpangan pertama mengurangi kumpulan ini menjadi 1.004 baris, dan persimpangan kedua menguranginya menjadi hanya 7 .

Selesaikan implementasi pencarian trigram

Sekarang kita memiliki id yang cocok dengan trigram, kita dapat mencari baris yang cocok di tabel Contoh. Kami masih perlu menerapkan kondisi pencarian asli sebagai pemeriksaan terakhir, karena trigram dapat menghasilkan positif palsu (tetapi tidak negatif palsu). Masalah terakhir yang harus diatasi adalah bahwa tahap sebelumnya mungkin tidak menemukan trigram. Ini mungkin, misalnya, karena string pencarian berisi terlalu sedikit informasi. String pencarian '%FF%' tidak dapat menggunakan pencarian trigram karena dua karakter tidak cukup untuk menghasilkan bahkan satu trigram. Untuk menangani skenario ini dengan baik, penelusuran kami akan mendeteksi kondisi ini dan kembali ke penelusuran non-trigram.

Fungsi inline terakhir berikut mengimplementasikan logika yang diperlukan:

-- Cari implementasiCREATE FUNCTION dbo.Example_TrigramSearch( @Search varchar(255))RETURNS tableWITH SCHEMABINDINGASRETURN SELECT Result.string FROM dbo.Example_GetBestTrigrams(@Search) SEBAGAI GBT CROSS APPLY ( -- Trigram search E.SELECT E.SELECT string DARI dbo.Example_GetTrigramMatchIDs (GBT.trigram1, GBT.trigram2, GBT.trigram3) SEBAGAI MID JOIN dbo.Contoh AS E ON E.id =MID.id WHERE -- Setidaknya satu trigram ditemukan GBT.trigram1 BUKAN NULL DAN E .string LIKE @Search UNION ALL -- Pencarian non-trigram SELECT E.id, E.string FROM dbo.Contoh AS E WHERE -- Tidak ada trigram yang ditemukan GBT.trigram1 IS NULL AND E.string LIKE @Search ) AS Result; 
 Fitur utama adalah referensi luar ke GBT.trigram1 di kedua sisi UNION ALL . Ini diterjemahkan ke Filter dengan ekspresi start-up dalam rencana eksekusi. Filter start-up hanya mengeksekusi subtree-nya jika kondisinya bernilai true. Efek bersihnya adalah hanya satu bagian dari serikat yang semuanya akan dieksekusi, tergantung pada apakah kita menemukan trigram atau tidak. Bagian yang relevan dari rencana eksekusi adalah:
  
 Efek filter awal 
 
 Baik Example_GetTrigramMatchIDs fungsi akan dieksekusi (dan hasilnya dicari dalam Contoh menggunakan pencarian pada id), atau Pemindaian Indeks Clustered dari Contoh dengan sisa LIKE predikat akan dijalankan, tetapi tidak keduanya.
 Kinerja
 
 Kode berikut menguji kinerja pencarian trigram terhadap LIKE yang setara :
 SET STATISTICS XML OFFDECLARE @S datetime2 =SYSUTCDATETIME(); PILIH F2.stringFROM dbo.Contoh SEBAGAI F2WHERE F2.string LIKE '%1234%5678%'OPTION (MAXDOP 1); SELECT ElapsedMS =DATEDIFF(MILLISECOND, @S, SYSUTCDATETIME());GOSET STATISTICS XML OFFDECLARE @S datetime2 =SYSUTCDATETIME(); PILIH ETS.stringFROM dbo.Example_TrigramSearch('%1234%5678%') SEBAGAI ETS; SELECT ElapsedMS =DATEDIFF(MILLISECOND, @S, SYSUTCDATETIME());
 
 Keduanya menghasilkan baris hasil yang sama tetapi LIKE kueri berjalan selama 2100 md , sedangkan penelusuran trigram membutuhkan waktu 15 md .
 
 Bahkan kinerja yang lebih baik adalah mungkin. Umumnya, kinerja meningkat karena trigram menjadi lebih selektif, dan jumlahnya lebih sedikit (di bawah maksimum tiga dalam implementasi ini). Misalnya:
 SET STATISTICS XML OFFDECLARE @S datetime2 =SYSUTCDATETIME(); PILIH ETS.stringFROM dbo.Example_TrigramSearch('%BEEF%') SEBAGAI ETS; SELECT ElapsedMS =DATEDIFF(MILLISECOND, @S, SYSUTCDATETIME());
 
 Penelusuran tersebut mengembalikan 111 baris ke kisi SSMS dalam 4 md . LIKE setara berjalan selama 1950 md .
 Mempertahankan trigram
 
 Jika tabel target statis, jelas tidak ada masalah menjaga tabel dasar dan tabel trigram terkait disinkronkan. Demikian juga, jika hasil pencarian tidak diharuskan untuk selalu diperbarui setiap saat, pembaruan tabel trigram yang dijadwalkan dapat bekerja dengan baik.
 
 Jika tidak, kita dapat menggunakan beberapa pemicu yang cukup sederhana untuk menjaga agar data pencarian trigram tetap sinkron dengan string yang mendasarinya. Ide umumnya adalah untuk menghasilkan trigram untuk baris yang dihapus dan disisipkan, kemudian menambahkan atau menghapusnya dalam tabel trigram yang sesuai. Pemicu penyisipan, pembaruan, dan penghapusan di bawah ini menunjukkan gagasan ini dalam praktiknya:
 -- Pertahankan trigram setelah penyisipan ContohCREATE TRIGGER MaintainTrigrams_AION dbo.ContohAFTER INSERTASBEGIN JIKA @@ROWCOUNT =0 RETURN; JIKA TRIGGER_NESTLEVEL(@@PROCID, 'AFTER', 'DML')> 1 RETURN; SET NOCOUNT AKTIF; SET ROWCOUNT 0; -- Sisipkan trigram terkait INSERT dbo.ExampleTrigrams (id, trigram) SELECT INS.id, GT.trigram FROM Inserted AS INS CROSS APPLY dbo.GenerateTrigrams(INS.string) AS GT;END;
 -- Pertahankan trigram setelah Contoh deletesCREATE TRIGGER MaintainTrigrams_ADON dbo.ContohAFTER DELETEASBEGIN JIKA @@ROWCOUNT =0 RETURN; JIKA TRIGGER_NESTLEVEL(@@PROCID, 'AFTER', 'DML')> 1 RETURN; SET NOCOUNT AKTIF; SET ROWCOUNT 0; -- Trigram terkait yang dihapus 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; SELESAI;
 -- Pertahankan trigram setelah Pembaruan ContohCREATE TRIGGER MaintainTrigrams_AUON dbo.ExampleAFTER UPDATEASBEGIN JIKA @@ROWCOUNT =0 RETURN; JIKA TRIGGER_NESTLEVEL(@@PROCID, 'AFTER', 'DML')> 1 RETURN; SET NOCOUNT AKTIF; SET ROWCOUNT 0; -- Trigram terkait yang dihapus 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; -- Sisipkan trigram terkait INSERT dbo.ExampleTrigrams (id, trigram) SELECT INS.id, GT.trigram FROM Inserted AS INS CROSS APPLY dbo.GenerateTrigrams(INS.string) AS GT;END;
 
 Pemicunya cukup efisien, dan akan menangani perubahan baris tunggal dan banyak (termasuk beberapa tindakan yang tersedia saat menggunakan MERGE penyataan). Tampilan yang diindeks pada tabel trigram akan secara otomatis dikelola oleh SQL Server tanpa kita perlu menulis kode pemicu apa pun.
 Operasi pemicu
 
 Sebagai contoh, jalankan pernyataan untuk menghapus baris arbitrer dari tabel Contoh:
 -- Baris tunggal hapusDELETE TOP (1) dbo.Contoh;
 
 Rencana eksekusi pasca-eksekusi (aktual) mencakup entri untuk pemicu setelah penghapusan:
  
 Hapus rencana eksekusi pemicu 
 
 Bagian kuning dari rencana membaca baris dari dihapus pesudo-table, menghasilkan trigram untuk setiap string Contoh yang dihapus (menggunakan rencana yang sudah dikenal yang disorot dengan warna hijau), kemudian mencari dan menghapus entri tabel trigram terkait. Bagian terakhir dari rencana, ditunjukkan dengan warna merah, secara otomatis ditambahkan oleh SQL Server untuk menjaga tampilan yang diindeks tetap mutakhir.
 
 Rencana untuk pemicu insert sangat mirip. Pembaruan ditangani dengan melakukan penghapusan diikuti dengan penyisipan. Jalankan skrip berikut untuk melihat rencana ini dan konfirmasikan bahwa baris baru dan yang diperbarui dapat ditemukan menggunakan fungsi pencarian trigram:
 -- Satu baris insertINSERT dbo.Contoh (string) VALUES ('SQLPerformance.com'); -- Temukan baris baruSELECT ETS.stringFROM dbo.Example_TrigramSearch('%perf%') AS ETS; -- Pembaruan baris tunggalUPDATE TOP (1) dbo.Contoh SET string ='12345678901234567890'; -- Multi-baris insertINSERT dbo.Contoh WITH (TABLOCKX) (string)SELECT TOP (1000) REPLACE(STR(RAND(CHECKSUM(NEWID())) * 1e10, 10), SPACE(1), '0') + KANAN(BARU(), 10)DARI master.dbo.spt_values AS SV1; -- Multi-baris updateUPDATE TOP (1000) dbo.Contoh SET string ='12345678901234567890'; -- Cari baris yang diperbaruiSELECT ETS.string FROM dbo.Example_TrigramSearch('12345678901234567890') AS ETS;
 Menggabungkan contoh
 
 Script berikutnya menunjukkan MERGE pernyataan yang digunakan untuk menyisipkan, menghapus, dan memperbarui tabel Contoh sekaligus:
 -- MERGE demoDECLARE tabel @MergeData ( id integer UNIQUE CLUSTERED NULL, operasi char(3) NOT NULL, string char(20) NULL); INSERT @MergeData (id, operasi, string)VALUES (NULL, 'INS', '11223344556677889900'), -- Sisipkan (1001, 'DEL', NULL), -- Hapus (2002, 'UPD', '00000000000000000000'); -- Perbarui tabel DECLARE @Actions ( 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.Contoh AS EUSING @MergeData AS MD PADA MD.id =E.idWHEN MATCHED DAN MD.operation ='DEL' MAKA DELETEWHEN MATCHED DAN MD.operation ='UPD' MAKA UPDATE SET E.string =MD.stringWHEN NOT MATCHED AND MD.operation ='INS' THEN INSERT (string) VALUES (MD.string)OUTPUT $action, Deleted.id, Deleted.string, Inserted.id, Inserted.stringINTO @Actions (action$, old_id, old_string, new_id, string_baru); PILIH * DARI @Actions SEBAGAI A;
 
 Outputnya akan menampilkan sesuatu seperti:
  
 Keluaran tindakan 
 Pemikiran terakhir
 
 Mungkin ada beberapa ruang untuk mempercepat operasi penghapusan dan pembaruan besar-besaran dengan merujuk id secara langsung alih-alih menghasilkan trigram. Ini tidak diterapkan di sini karena akan memerlukan indeks nonclustered baru pada tabel trigram, menggandakan ruang penyimpanan (yang sudah signifikan) yang digunakan. Tabel trigram berisi satu bilangan bulat dan char(3) per baris; indeks nonclustered pada kolom integer akan mendapatkan char(3) kolom di semua level (milik indeks berkerumun, dan perlunya kunci indeks menjadi unik di setiap level). Ada juga ruang memori yang perlu dipertimbangkan, karena pencarian trigram bekerja paling baik ketika semua pembacaan berasal dari cache.
 
 Indeks ekstra akan membuat integritas referensial berjenjang menjadi pilihan, tetapi itu sering kali lebih merepotkan daripada nilainya.
 
 Pencarian trigram bukanlah obat mujarab. Persyaratan penyimpanan ekstra, kompleksitas implementasi, dan dampak pada kinerja pembaruan semuanya sangat membebaninya. Teknik ini juga tidak berguna untuk pencarian yang tidak menghasilkan trigram (minimal 3 karakter). Meskipun implementasi dasar yang ditampilkan di sini dapat menangani banyak jenis penelusuran (dimulai dengan, berisi, diakhiri dengan, banyak karakter pengganti), hal ini tidak mencakup semua kemungkinan ekspresi penelusuran yang dapat dibuat agar berfungsi dengan LIKE . Ini bekerja dengan baik untuk string pencarian yang menghasilkan trigram tipe-AND; lebih banyak pekerjaan diperlukan untuk menangani string pencarian yang memerlukan penanganan tipe OR, atau opsi lanjutan seperti ekspresi reguler.
 
 Semua itu dikatakan, jika aplikasi Anda benar-benar harus memiliki pencarian string wildcard yang cepat, n-gram adalah sesuatu yang perlu dipertimbangkan secara serius.
 
 Konten terkait:Salah satu cara untuk mendapatkan pencarian indeks untuk %wildcard terkemuka oleh Aaron Bertrand.