Tìm kiếm dữ liệu chuỗi cho một kết hợp chuỗi con tùy ý có thể là một hoạt động tốn kém trong SQL Server. Các truy vấn có dạng Column LIKE '%match%' không thể sử dụng các khả năng tìm kiếm của chỉ mục b-tree, vì vậy bộ xử lý truy vấn phải áp dụng vị từ cho từng hàng riêng lẻ. Ngoài ra, mỗi bài kiểm tra phải áp dụng chính xác đầy đủ các quy tắc đối chiếu phức tạp. Kết hợp tất cả các yếu tố này với nhau, không có gì ngạc nhiên khi các loại tìm kiếm này có thể tốn nhiều tài nguyên và chậm chạp.
Tìm kiếm toàn văn bản là một công cụ mạnh mẽ để đối sánh ngôn ngữ và Tìm kiếm ngữ nghĩa thống kê mới hơn rất phù hợp để tìm kiếm các tài liệu có ý nghĩa tương tự. Nhưng đôi khi, bạn thực sự chỉ cần tìm các chuỗi có chứa một chuỗi con cụ thể - một chuỗi con thậm chí có thể không phải là một từ, bằng bất kỳ ngôn ngữ nào.
Nếu dữ liệu được tìm kiếm không lớn hoặc yêu cầu thời gian phản hồi không quan trọng, hãy sử dụng LIKE '%match%' cũng có thể là một giải pháp phù hợp. Tuy nhiên, trong trường hợp kỳ lạ khi nhu cầu tìm kiếm siêu nhanh đánh bại tất cả các cân nhắc khác (bao gồm cả không gian lưu trữ), bạn có thể xem xét một giải pháp tùy chỉnh bằng cách sử dụng n-gram. Biến thể cụ thể được khám phá trong bài viết này là một bát quái ba ký tự.
Tìm kiếm theo ký tự đại diện bằng cách sử dụng bát quái
Ý tưởng cơ bản của tìm kiếm bát quái khá đơn giản:
- Duy trì các chuỗi con ba ký tự (bát quái) của dữ liệu đích.
- Chia (các) cụm từ tìm kiếm thành bát quái.
- So khớp bát quái tìm kiếm với bát quái được lưu trữ (tìm kiếm bằng)
- Giao nhau giữa các hàng đủ điều kiện để tìm các chuỗi khớp với tất cả các bát quái
- Áp dụng bộ lọc tìm kiếm ban đầu cho giao lộ được giảm thiểu nhiều
Chúng tôi sẽ làm việc thông qua một ví dụ để xem chính xác tất cả điều này hoạt động như thế nào và sự đánh đổi là gì.
Bảng và dữ liệu mẫu
Tập lệnh bên dưới tạo một bảng mẫu và điền vào bảng đó với một triệu hàng dữ liệu chuỗi. Mỗi chuỗi dài 20 ký tự, với 10 ký tự đầu tiên là số. 10 ký tự còn lại là hỗn hợp các số và chữ cái từ A đến F, được tạo bằng NEWID() . Không có gì quá đặc biệt về dữ liệu mẫu này; kỹ thuật bát quái khá chung chung.
-- 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); Mất khoảng 3 giây để tạo và điền dữ liệu trên máy tính xách tay khiêm tốn của tôi. Dữ liệu là giả ngẫu nhiên, nhưng như một dấu hiệu, nó sẽ trông giống như sau:
Mẫu dữ liệu
Tạo ra bát quái
Hàm nội tuyến sau đây tạo ra các bát quái chữ và số riêng biệt từ một chuỗi đầu vào nhất định:
--- 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]%'; Ví dụ về việc sử dụng nó, lệnh gọi sau:
SELECT
GT.trigram
FROM dbo.GenerateTrigrams('SQLperformance.com') AS GT; Tạo ra các bát quái sau:
SQLperformance.com trigrams
Kế hoạch thực thi là một bản dịch khá trực tiếp của T-SQL trong trường hợp này:
- Tạo các hàng (kết hợp chéo của các lần quét liên tục)
- Đánh số hàng (Dự án phân đoạn và trình tự)
- Giới hạn số lượng cần thiết dựa trên độ dài của chuỗi (Trên cùng)
- Xóa bát quái có các ký tự không phải chữ và số (Bộ lọc)
- Xóa các bản sao (Sắp xếp Riêng biệt)
Kế hoạch tạo bát quái
Tải bát quái
Bước tiếp theo là duy trì bát quái cho dữ liệu ví dụ. Bát quái sẽ được giữ trong một bảng mới, được điền bằng hàm nội tuyến mà chúng tôi vừa tạo:
-- 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; Điều đó mất khoảng 20 giây để thực thi trên phiên bản máy tính xách tay SQL Server 2016 của tôi. Lần chạy cụ thể này đã tạo ra 17,937,972 hàng bát quái cho 1 triệu hàng dữ liệu thử nghiệm 20 ký tự. Kế hoạch thực thi về cơ bản hiển thị kế hoạch chức năng đang được đánh giá cho mỗi hàng của bảng Ví dụ:
Điền bảng bát quái
Vì kiểm tra này được thực hiện trên SQL Server 2016 (tải bảng heap, ở mức độ tương thích cơ sở dữ liệu 130 và với TABLOCK gợi ý), kế hoạch được hưởng lợi từ việc chèn song song. Các hàng được phân phối giữa các luồng bằng cách quét song song bảng Ví dụ và vẫn nằm trên cùng một luồng sau đó (không có trao đổi phân vùng lại).
Toán tử Sắp xếp có thể trông hơi áp đặt, nhưng các con số hiển thị tổng số hàng được sắp xếp, qua tất cả các lần lặp của phép nối vòng lặp lồng nhau. Trên thực tế, có một triệu loại riêng biệt, mỗi loại gồm 18 hàng. Ở mức độ song song của bốn (trong trường hợp của tôi là hai lõi siêu phân luồng), có tối đa bốn loại nhỏ diễn ra cùng một lúc và mỗi phiên bản sắp xếp có thể sử dụng lại bộ nhớ. Điều này giải thích tại sao mức sử dụng bộ nhớ tối đa của kế hoạch thực thi này chỉ là 136KB (mặc dù 2,152 KB đã được cấp).
Bảng bát quái chứa một hàng cho mỗi bát quái riêng biệt trong mỗi hàng của bảng nguồn (được xác định bởi id ):
Mẫu bảng Trigram
Bây giờ chúng tôi tạo một chỉ mục b-tree theo cụm để hỗ trợ tìm kiếm các kết quả phù hợp với bát quái:
-- Trigram search index
CREATE UNIQUE CLUSTERED INDEX
[CUQ dbo.ExampleTrigrams (trigram, id)]
ON dbo.ExampleTrigrams (trigram, id)
WITH (DATA_COMPRESSION = ROW); Quá trình này mất khoảng 45 giây , mặc dù một số điều đó là do sắp xếp tràn (phiên bản của tôi bị giới hạn ở bộ nhớ 4GB). Một phiên bản có nhiều bộ nhớ hơn có thể hoàn thành việc xây dựng chỉ mục song song được ghi nhật ký tối thiểu đó nhanh hơn một chút.
Kế hoạch xây dựng chỉ mục
Lưu ý rằng chỉ mục được chỉ định là duy nhất (sử dụng cả hai cột trong khóa). Chúng tôi có thể đã tạo một chỉ mục được phân cụm không phải là duy nhất chỉ trên bát quái, nhưng dù sao thì SQL Server cũng đã thêm các bộ hợp nhất 4 byte vào hầu hết tất cả các hàng. Khi chúng tôi tính đến rằng các bộ thống nhất được lưu trữ trong phần có độ dài thay đổi của hàng (với chi phí liên quan), thì việc bao gồm id sẽ có ý nghĩa hơn trong chìa khóa và được thực hiện với nó.
Nén hàng được chỉ định vì nó làm giảm kích thước của bảng bát quái từ 277MB xuống 190MB một cách hữu ích (để so sánh, bảng Ví dụ là 32MB). Nếu bạn ít nhất không sử dụng SQL Server 2016 SP1 (nơi nén dữ liệu đã có sẵn cho tất cả các phiên bản), bạn có thể bỏ qua điều khoản nén nếu cần.
Để tối ưu hóa cuối cùng, chúng tôi cũng sẽ tạo một chế độ xem được lập chỉ mục trên bảng bát quái để giúp việc tìm kiếm bát quái nào phổ biến nhất và ít phổ biến nhất trong dữ liệu một cách nhanh chóng và dễ dàng. Bước này có thể được bỏ qua, nhưng được khuyến khích để đạt được hiệu suất.
-- 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); 
Kế hoạch xây dựng chế độ xem được lập chỉ mục
Việc này chỉ mất vài giây để hoàn thành. Kích thước của chế độ xem hiện thực hóa rất nhỏ, chỉ 104KB .
Tìm kiếm bằng Trigram
Đưa ra một chuỗi tìm kiếm (ví dụ:'%find%this%' ), cách tiếp cận của chúng tôi sẽ là:
- Tạo bộ bát quái hoàn chỉnh cho chuỗi tìm kiếm
- Sử dụng chế độ xem được lập chỉ mục để tìm ba bát quái được chọn lọc nhất
- Tìm các id phù hợp với tất cả các bát quái có sẵn
- Truy xuất các chuỗi theo id
- Áp dụng bộ lọc đầy đủ cho các hàng đủ tiêu chuẩn trigram
Tìm bát quái có chọn lọc
Hai bước đầu tiên khá đơn giản. Chúng ta đã có một hàm tạo bát quái cho một chuỗi tùy ý. Có thể đạt được sự chọn lọc nhất trong số các bát quái đó bằng cách tham gia vào chế độ xem đã lập chỉ mục. Đoạn mã sau kết thúc việc triển khai cho bảng ví dụ của chúng tôi trong một hàm nội tuyến khác. Nó xoay ba bát quái chọn lọc nhất thành một hàng để dễ sử dụng sau này:
-- 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; Ví dụ:
SELECT
EGBT.trigram1,
EGBT.trigram2,
EGBT.trigram3
FROM dbo.Example_GetBestTrigrams('%1234%5678%') AS EGBT; trả về (đối với dữ liệu mẫu của tôi):
Bát quái đã chọn
Kế hoạch thực hiện là:
Kế hoạch thực thi GetBestTrigrams
Đây là kế hoạch tạo bát quái quen thuộc từ trước đó, tiếp theo là tra cứu vào chế độ xem được lập chỉ mục cho từng bát quái, sắp xếp theo số trận đấu, đánh số hàng (Dự án trình tự), giới hạn nhóm ở ba hàng (Trên cùng), sau đó xoay vòng kết quả (Tổng hợp luồng).
Tìm ID phù hợp với tất cả các bát quái
Bước tiếp theo là tìm id hàng của bảng Ví dụ phù hợp với tất cả các bát quái không rỗng được truy xuất bởi giai đoạn trước. Điều khó khăn ở đây là chúng ta có thể có sẵn số không, một, hai hoặc ba bát quái. Việc triển khai sau đây kết hợp logic cần thiết trong một hàm nhiều câu lệnh, trả về các id đủ điều kiện trong một biến bảng:
-- 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; Kế hoạch thực hiện ước tính cho chức năng này cho thấy chiến lược:
Kế hoạch id đối sánh Trigram
Nếu có sẵn một bát quái, một tìm kiếm duy nhất vào bảng bát quái sẽ được thực hiện. Nếu không, hai hoặc ba lần tìm kiếm được thực hiện và giao điểm của các id được tìm thấy bằng cách sử dụng (các) hợp nhất một-nhiều hiệu quả. Không có toán tử tiêu tốn bộ nhớ nào trong kế hoạch này, vì vậy không có khả năng xảy ra sự cố tràn băm hoặc sắp xếp.
Tiếp tục tìm kiếm ví dụ, chúng tôi có thể tìm thấy các id phù hợp với bát quái có sẵn bằng cách áp dụng chức năng mới:
SELECT EGTMID.id
FROM dbo.Example_GetBestTrigrams('%1234%5678%') AS EGBT
CROSS APPLY dbo.Example_GetTrigramMatchIDs
(EGBT.trigram1, EGBT.trigram2, EGBT.trigram3) AS EGTMID; Điều này trả về một tập hợp như sau:
ID phù hợp
Kế hoạch thực tế (sau khi thực hiện) cho hàm mới hiển thị hình dạng kế hoạch với ba đầu vào hình bát quái đang được sử dụng:
Kế hoạch đối sánh ID thực tế
Điều này cho thấy sức mạnh của sự kết hợp bát quái khá tốt. Mặc dù cả ba bát quái đều xác định được khoảng 11.000 hàng trong bảng Ví dụ, giao điểm đầu tiên giảm tập hợp này xuống 1.004 hàng và giao điểm thứ hai giảm nó xuống chỉ 7 .
Hoàn thành triển khai tìm kiếm bát quái
Bây giờ chúng ta đã có id phù hợp với bát quái, chúng ta có thể tra cứu các hàng phù hợp trong bảng Ví dụ. Chúng tôi vẫn cần áp dụng điều kiện tìm kiếm ban đầu như một lần kiểm tra cuối cùng, vì gương bát quái có thể tạo ra các kết quả dương tính giả (nhưng không phải âm tính giả). Vấn đề cuối cùng cần giải quyết là các giai đoạn trước có thể không tìm thấy bất kỳ hình bát quái nào. Ví dụ:điều này có thể là do chuỗi tìm kiếm chứa quá ít thông tin. Chuỗi tìm kiếm '%FF%' không thể sử dụng tìm kiếm bát quái vì hai ký tự không đủ để tạo ra dù chỉ là một bát quái. Để xử lý tình huống này một cách dễ dàng, tìm kiếm của chúng tôi sẽ phát hiện tình trạng này và quay trở lại tìm kiếm không phải bát quái.
Hàm nội tuyến cuối cùng sau đây thực hiện logic được yêu cầu:
-- 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;
Tính năng chính là tham chiếu bên ngoài tới GBT.trigram1 trên cả hai mặt của UNION ALL . Chúng dịch sang Bộ lọc với các biểu thức khởi động trong kế hoạch thực thi. Bộ lọc khởi động chỉ thực hiện cây con của nó nếu điều kiện của nó đánh giá là true. Kết quả thực sự là chỉ một phần của hợp nhất tất cả sẽ được thực thi, tùy thuộc vào việc chúng ta có tìm thấy một bát quái hay không. Phần có liên quan của kế hoạch thực hiện là:
Hiệu ứng bộ lọc khởi động
Example_GetTrigramMatchIDs hàm sẽ được thực thi (và kết quả được tra cứu trong Ví dụ bằng cách sử dụng tìm kiếm trên id), hoặc Ví dụ quét chỉ mục theo cụm với LIKE còn lại vị ngữ sẽ chạy, nhưng không chạy cả hai.
Hiệu suất
Đoạn mã sau kiểm tra hiệu suất của tìm kiếm trigram với LIKE tương đương :
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());
Cả hai đều tạo ra (các) hàng kết quả giống nhau nhưng LIKE truy vấn chạy trong 2100ms , trong khi tìm kiếm bát quái mất 15ms .
Thậm chí hiệu suất tốt hơn là có thể. Nói chung, hiệu suất được cải thiện khi bát quái trở nên chọn lọc hơn và số lượng ít hơn (dưới mức tối đa là ba trong cách triển khai này). Ví dụ:
SET STATISTICS XML OFF
DECLARE @S datetime2 = SYSUTCDATETIME();
SELECT ETS.string
FROM dbo.Example_TrigramSearch('%BEEF%') AS ETS;
SELECT ElapsedMS = DATEDIFF(MILLISECOND, @S, SYSUTCDATETIME());
Tìm kiếm đó trả về 111 hàng cho lưới SSMS trong 4ms . LIKE tương đương chạy trong 1950ms .
Duy trì bát quái
Nếu bảng đích là tĩnh, rõ ràng không có vấn đề gì khi giữ đồng bộ bảng cơ sở và bảng bát quái có liên quan. Tương tự như vậy, nếu kết quả tìm kiếm không bắt buộc phải luôn được cập nhật hoàn toàn, thì việc làm mới (các) bảng bát quái theo lịch trình có thể hoạt động tốt.
Nếu không, chúng tôi có thể sử dụng một số trình kích hoạt khá đơn giản để giữ cho dữ liệu tìm kiếm trigram được đồng bộ hóa với các chuỗi bên dưới. Ý tưởng chung là tạo bát quái cho các hàng đã xóa và đã chèn, sau đó thêm hoặc xóa chúng trong bảng bát quái nếu thích hợp. Trình kích hoạt chèn, cập nhật và xóa bên dưới thể hiện ý tưởng này trong thực tế:
-- 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;
Các trình kích hoạt khá hiệu quả và sẽ xử lý cả các thay đổi đơn hàng và nhiều hàng (bao gồm nhiều hành động có sẵn khi sử dụng MERGE tuyên bố). Chế độ xem được lập chỉ mục trên bảng bát quái sẽ được SQL Server tự động duy trì mà chúng tôi không cần viết bất kỳ mã kích hoạt nào.
Thao tác kích hoạt
Ví dụ:chạy một câu lệnh để xóa một hàng tùy ý khỏi bảng Ví dụ:
-- Single row delete DELETE TOP (1) dbo.Example;
Kế hoạch thực thi sau khi thực thi (thực tế) bao gồm một mục nhập cho trình kích hoạt sau khi xóa:
Xóa kế hoạch thực thi trình kích hoạt
Phần màu vàng của kế hoạch đọc các hàng từ đã xóa pesudo-table, tạo bát quái cho mỗi chuỗi Ví dụ đã xóa (sử dụng sơ đồ quen thuộc được đánh dấu màu xanh lá cây), sau đó định vị và xóa các mục nhập bảng bát quái liên quan. Phần cuối cùng của kế hoạch, được hiển thị bằng màu đỏ, được SQL Server tự động thêm vào để cập nhật chế độ xem đã lập chỉ mục.
Kế hoạch cho trình kích hoạt chèn là cực kỳ giống nhau. Cập nhật được xử lý bằng cách thực hiện xóa sau đó là chèn. Chạy tập lệnh sau để xem các kế hoạch này và xác nhận rằng các hàng mới và cập nhật có thể được định vị bằng cách sử dụng chức năng tìm kiếm bát quái:
-- 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; Ví dụ về hợp nhất
Tập lệnh tiếp theo hiển thị MERGE câu lệnh được sử dụng để chèn, xóa và cập nhật bảng Ví dụ cùng một lúc:
-- 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; Kết quả sẽ hiển thị như sau:
Đầu ra hành động
Suy nghĩ cuối cùng
Có lẽ có một số phạm vi để tăng tốc các hoạt động xóa và cập nhật lớn bằng cách tham chiếu trực tiếp id thay vì tạo bát quái. Điều này không được thực hiện ở đây vì nó sẽ yêu cầu một chỉ mục không phân nhánh mới trên bảng bát quái, tăng gấp đôi không gian lưu trữ (đã đáng kể) được sử dụng. Bảng bát quái chứa một số nguyên duy nhất và một char(3) mỗi hàng; một chỉ mục không phân biệt trên cột số nguyên sẽ nhận được char(3) ở tất cả các cấp (nhờ chỉ mục được phân nhóm và nhu cầu về các khóa chỉ mục là duy nhất ở mọi cấp). Ngoài ra còn có không gian bộ nhớ để xem xét, vì tìm kiếm bằng trigram hoạt động tốt nhất khi tất cả các lần đọc đều từ bộ nhớ cache.
Chỉ mục bổ sung sẽ làm cho tính toàn vẹn của tham chiếu xếp tầng trở thành một tùy chọn, nhưng điều đó thường gây nhiều rắc rối hơn mức đáng có.
Tìm kiếm bằng Trigram không phải là thuốc chữa bách bệnh. Các yêu cầu lưu trữ bổ sung, độ phức tạp của việc triển khai và tác động đến hiệu suất cập nhật đều đè nặng lên nó. Kỹ thuật này cũng vô dụng đối với các tìm kiếm không tạo ra bất kỳ hình bát quái nào (tối thiểu 3 ký tự). Mặc dù cách triển khai cơ bản được hiển thị ở đây có thể xử lý nhiều kiểu tìm kiếm (bắt đầu bằng, chứa, kết thúc bằng, nhiều ký tự đại diện) nhưng nó không bao gồm mọi biểu thức tìm kiếm có thể được thực hiện để hoạt động với LIKE . Nó hoạt động tốt cho các chuỗi tìm kiếm tạo ra bát quái kiểu AND; cần nhiều công việc hơn để xử lý các chuỗi tìm kiếm yêu cầu xử lý kiểu OR hoặc các tùy chọn nâng cao hơn như biểu thức chính quy.
Tất cả những gì đã nói, nếu ứng dụng của bạn thực sự phải tìm kiếm chuỗi ký tự đại diện nhanh chóng, n-gram là thứ cần nghiêm túc xem xét.
Nội dung liên quan:Một cách để chỉ mục tìm kiếm ký tự đại diện% đứng đầu của Aaron Bertrand.
