Pesquisa de string curinga do Trigram no SQL Server

Pesquisa de curingas usando trigramas

1. Persista substrings de três caracteres (trigramas) dos dados de destino.
2. Divida os termos de pesquisa em trigramas.
3. Combinar trigramas de pesquisa com os trigramas armazenados (pesquisa de igualdade)
4. Faça a interseção das linhas qualificadas para encontrar strings que correspondam a todos os trigramas
5. Aplicar o filtro de pesquisa original à interseção muito reduzida

Tabela de amostra e dados

-- A tabela de testeCREATE TABLE dbo.Example ( id integer IDENTITY NOT NULL, string char(20) NOT NULL, CONSTRAINT [PK dbo.Example (id)] PRIMARY KEY CLUSTERED (id));GO-- 1 milhão rowsINSERT dbo.Example WITH (TABLOCKX) (string)SELECT TOP (1 * 1000 * 1000) -- 10 caracteres numéricos REPLACE(STR(RAND(CHECKSUM(NEWID()))) * 1e10, 10), SPACE(1), ' 0') + -- mais 10 caracteres numéricos mistos + [A-F] RIGHT(NEWID(), 10)FROM master.dbo.spt_values ​​AS SV1CROSS JOIN master.dbo.spt_values ​​AS SV2OPTION (MAXDOP 1);

Gerando trigramas

--- Gerar trigramas de uma 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)), -- Tabela de números (256) Nums AS ( SELECT n =ROW_NUMBER() OVER (ORDER BY A.v) FROM N16 AS A CROSS JOIN N16 AS B ), Trigramas AS ( -- Cada substring de 3 caracteres SELECT TOP (CASE WHEN LEN(@string)> 2 THEN LEN(@string) - 2 ELSE 0 END) trigrama =SUBSTRING(@string, N.n, 3) FROM Nums AS N ORDER BY N.n ) -- Remova duplicatas e certifique-se de que todas três caracteres são alfanuméricos SELECT DISTINCT T.trigram FROM Trigrams AS T WHERE -- Comparação de agrupamento binário so r os anges funcionam como esperado T.trigram COLLATE Latin1_General_BIN2 NOT LIKE '%[^A-Z0-9a-z]%';

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

• Gerando linhas (junção cruzada de verificações constantes)
• Numeração de linhas (Projeto de segmento e sequência)
• Limitando os números necessários com base no comprimento da string (Top)
• Remover trigramas com caracteres não alfanuméricos (Filtro)
• Remover duplicatas (classificação distinta)

Carregando os trigramas

-- Trigramas para Exemplo tableCREATE TABLE dbo.ExampleTrigrams( id integer NOT NULL, trigram char(3) NOT NULL);GO-- Gerar trigramsINSERT dbo.ExampleTrigrams WITH (TABLOCKX) (id, trigram)SELECT E.id, GT.trigramFROM dbo.Example AS ECROSS APPLY dbo.GenerateTrigrams(E.string) AS GT;

-- Índice de pesquisa de trigramaCREATE UNIQUE CLUSTERED INDEX [CUQ dbo.ExampleTrigrams (trigram, id)]ON dbo.ExampleTrigrams (trigram, id)WITH (DATA_COMPRESSION =ROW);

-- Seletividade de cada trigrama (otimização de desempenho)CREATE VIEW dbo.ExampleTrigramCountsWITH SCHEMABINDINGASSELECT ET.trigram, cnt =COUNT_BIG(*)FROM dbo.ExampleTrigrams AS ETGROUP BY ET.trigram;GO-- Materialize a viewCREATE UNIQUE CLUSTERED INDEX [ CUQ dbo.ExampleTrigramCounts (trigram)]ON dbo.ExampleTrigramCounts (trigram);

Pesquisa de trigramas

1. Gere o conjunto completo de trigramas para a string de pesquisa
2. Use a visualização indexada para encontrar os três trigramas mais seletivos
3. Encontre os IDs correspondentes a todos os trigramas disponíveis
4. Recuperar as strings por id
5. Aplicar o filtro completo às linhas qualificadas para trigramas

Encontrando trigramas seletivos

-- Trigramas mais seletivos para uma string de pesquisa-- Sempre retorna uma linha (NULLs se nenhum trigrama for encontrado)CREATE FUNCTION dbo.Example_GetBestTrigrams (@string varchar(255))RETURNS tableWITH SCHEMABINDING ASRETURN SELECT -- Pivot trigram1 =MAX( CASE WHEN BT.rn =1 THEN BT.trigram END), trigrama2 =MAX(CASE WHEN WHEN BT.rn =2 THEN BT.trigram END), trigram3 =MAX(CASE WHEN WHEN BT.rn =3 THEN BT.trigram END) FROM ( -- Gerar trigramas para a string de pesquisa -- e escolher os três mais seletivos 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;

Encontrando IDs correspondentes a todos os trigramas

-- Retorna exemplos de ids que correspondem a todos os trigrams fornecidos (não nulos)CREATE FUNCTION dbo.Example_GetTrigramMatchIDs( @Trigram1 char(3), @Trigram2 char(3), @Trigram3 char(3))RETURNS @IDs table (id integer CHAVE PRIMÁRIA) COM SCHEMABINDING ASBEGIN IF @Trigram1 NÃO É NULL BEGIN IF @Trigram2 NÃO É NULL BEGIN IF @Trigram3 NÃO É NULL BEGIN -- 3 trigramas disponíveis 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); FIM; ELSE BEGIN -- 2 trigramas disponíveis 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); FIM; FIM; ELSE BEGIN -- 1 trigrama disponível INSERT @IDs (id) SELECT ET1.id FROM dbo.ExampleTrigrams AS ET1 WHERE ET1.trigram =@Trigram1; FIM; FIM; RETURN;END;

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

Implementação completa da pesquisa de trigramas

-- Implementação de pesquisaCREATE FUNCTION dbo.Example_TrigramSearch( @Search varchar(255))RETURNS tableWITH SCHEMABINDINGASRETURN SELECT Result.string FROM dbo.Example_GetBestTrigrams(@Search) AS GBT CROSS APPLY ( -- Pesquisa de Trigrama 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 -- Pelo menos um trigrama encontrado GBT.trigram1 IS NOT NULL AND E .string LIKE @Search UNION ALL -- Pesquisa sem trigrama SELECT E.id, E.string FROM dbo.Example AS E WHERE -- Nenhum trigrama encontrado GBT.trigram1 IS NULL AND E.string LIKE @Search ) AS Result; 
 O recurso principal é a referência externa a GBT.trigram1 em ambos os lados do UNION ALL . Eles se traduzem em Filtros com expressões de inicialização no plano de execução. Um filtro de inicialização só executa sua subárvore se sua condição for verdadeira. O efeito líquido é que apenas uma parte da união será executada, dependendo se encontramos um trigrama ou não. A parte relevante do plano de execução é:
  
 Efeito de filtro de inicialização 
 
 Ou os Example_GetTrigramMatchIDs será executada (e os resultados pesquisados ​​no Exemplo usando uma busca no id), ou a Varredura de Índice Agrupado do Exemplo com um LIKE residual predicado será executado, mas não ambos. 
 
Desempenho
 
 O código a seguir testa o desempenho da pesquisa de trigramas em relação ao equivalente LIKE :
 
SET STATISTICS XML OFFDECLARE @S datetime2 =SYSUTCDATETIME(); SELECT F2.stringFROM dbo.Example AS F2WHERE F2.string LIKE '%1234%5678%'OPTION (MAXDOP 1); SELECT ElapsedMS =DATEDIFF(MILLISEGOND, @S, SYSUTCDATETIME());GOSET STATISTICS XML OFFDECLARE @S datetime2 =SYSUTCDATETIME(); SELECT ETS.stringFROM dbo.Example_TrigramSearch('%1234%5678%') AS ETS; SELECT ElapsedMS =DATEDIFF(MILISECOND, @S, SYSUTCDATETIME());
 
 Ambos produzem a(s) mesma(s) linha(s) de resultado, mas o LIKE a consulta é executada por 2100ms , enquanto a pesquisa de trigramas leva 15 ms . 
 
 Um desempenho ainda melhor é possível. Geralmente, o desempenho melhora à medida que os trigramas se tornam mais seletivos e em menor número (abaixo do máximo de três nesta implementação). Por exemplo:
 
SET STATISTICS XML OFFDECLARE @S datetime2 =SYSUTCDATETIME(); SELECT ETS.stringFROM dbo.Example_TrigramSearch('%BEEF%') AS ETS; SELECT ElapsedMS =DATEDIFF(MILISECOND, @S, SYSUTCDATETIME());
 
 Essa pesquisa retornou 111 linhas para a grade do SSMS em 4 ms . O LIKE equivalente executado por 1950ms . 
 
Manutenção dos trigramas
 
 Se a tabela de destino for estática, obviamente não há problema em manter a tabela base e a tabela de trigramas relacionada sincronizadas. Da mesma forma, se os resultados da pesquisa não precisarem estar completamente atualizados o tempo todo, uma atualização programada da(s) tabela(s) de trigramas pode funcionar bem. 
 
 Caso contrário, podemos usar alguns gatilhos bastante simples para manter os dados de pesquisa de trigramas sincronizados com as strings subjacentes. A ideia geral é gerar trigramas para linhas excluídas e inseridas e, em seguida, adicioná-las ou excluí-las na tabela de trigramas conforme apropriado. Os gatilhos de inserção, atualização e exclusão abaixo mostram essa ideia na prática:
 
-- Mantém trigramas após exemplo insertsCREATE TRIGGER ManutençãoTrigrams_AION dbo.ExampleAFTER INSERTASBEGIN IF @@ROWCOUNT =0 RETURN; IF TRIGGER_NESTLEVEL(@@PROCID, 'APÓS', 'DML')> 1 RETORNO; DEFINIR NOCOUNT ON; SET CONTAGEM DE LINHA 0; -- Inserir trigramas relacionados INSERT dbo.ExampleTrigrams (id, trigram) SELECT INS.id, GT.trigram FROM inserido AS INS CROSS APPLY dbo.GenerateTrigrams(INS.string) AS GT;END;
 
-- Mantém trigramas após Exemplo deletesCREATE TRIGGER ManterTrigramas_ADON dbo.ExampleAFTER DELETEASBEGIN IF @@ROWCOUNT =0 RETURN; IF TRIGGER_NESTLEVEL(@@PROCID, 'APÓS', 'DML')> 1 RETORNO; DEFINIR NOCOUNT ON; SET CONTAGEM DE LINHA 0; -- Excluídos trigramas relacionados DELETE ET WITH (SERIALIZABLE) DE Excluído 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; FIM;
 
-- Mantém os trigramas após as atualizações de exemploCREATE TRIGGER ManterTrigramas_AUON dbo.ExampleAFTER UPDATEASBEGIN IF @@ROWCOUNT =0 RETURN; IF TRIGGER_NESTLEVEL(@@PROCID, 'APÓS', 'DML')> 1 RETORNO; DEFINIR NOCOUNT ON; SET CONTAGEM DE LINHA 0; -- Excluídos trigramas relacionados DELETE ET WITH (SERIALIZABLE) DE Excluído 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; -- Inserir trigramas relacionados INSERT dbo.ExampleTrigrams (id, trigram) SELECT INS.id, GT.trigram FROM inserido AS INS CROSS APPLY dbo.GenerateTrigrams(INS.string) AS GT;END;
 
 Os gatilhos são bastante eficientes e lidam com alterações de linha única e de várias linhas (incluindo as várias ações disponíveis ao usar um MERGE demonstração). A exibição indexada sobre a tabela de trigramas será mantida automaticamente pelo SQL Server sem que precisemos escrever nenhum código de gatilho. 
 
Operação do gatilho
 
 Como exemplo, execute uma instrução para excluir uma linha arbitrária da tabela Example:
 
-- Linha única deleteDELETE TOP (1) dbo.Example;
 
 O plano de execução pós-execução (real) inclui uma entrada para o gatilho após a exclusão:
  
 Excluir plano de execução do gatilho 
 
 A seção amarela do plano lê as linhas do excluído pesudo-table, gera trigramas para cada string de exemplo excluída (usando o plano familiar destacado em verde) e, em seguida, localiza e exclui as entradas da tabela de trigramas associadas. A seção final do plano, mostrada em vermelho, é adicionada automaticamente pelo SQL Server para manter a exibição indexada atualizada. 
 
 O plano para o gatilho de inserção é extremamente semelhante. As atualizações são tratadas executando uma exclusão seguida de uma inserção. Execute o script a seguir para ver esses planos e confirmar se as linhas novas e atualizadas podem ser localizadas usando a função de pesquisa de trigramas:
 
-- Uma única linha insertINSERT dbo.Example (string) VALUES ('SQLPerformance.com'); -- Localiza a nova linhaSELECT ETS.stringFROM dbo.Example_TrigramSearch('%perf%') AS ETS; -- Atualização de linha únicaUPDATE TOP (1) dbo.Example SET string ='12345678901234567890'; -- Inserção de várias linhasINSERT dbo.Exemplo 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; -- Atualização de várias linhasUPDATE TOP (1000) dbo.Example SET string ='12345678901234567890'; -- Procure as linhas atualizadasSELECT ETS.string FROM dbo.Example_TrigramSearch('12345678901234567890') AS ETS;
 
Exemplo de mesclagem
 
 O próximo script mostra um MERGE instrução usada para inserir, excluir e atualizar a tabela de exemplo de uma só vez:
 
-- MERGE demoDECLARE @MergeData table ( id integer UNIQUE CLUSTERED NULL, operação char(3) NOT NULL, string char(20) NULL); INSERT @MergeData (id, operação, string)VALUES (NULL, 'INS', '11223344556677889900'), -- Insert (1001, 'DEL', NULL), -- Delete (2002, 'UPD', '00000000000000000000'); -- Atualizar a tabela 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.Example AS EUSING @MergeData AS MD ON MD.id =E.idWHEN MATCHED AND MD.operation ='DEL' THEN DELETEWHEN MATCHED AND MD.operation ='UPD' THEN 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, nova_string); SELECT * FROM @Actions AS A;
 
 A saída mostrará algo como:
  
 Resultado da ação 
 
Considerações finais
 
 Talvez haja algum escopo para acelerar grandes operações de exclusão e atualização referenciando ids diretamente em vez de gerar trigramas. Isso não é implementado aqui porque exigiria um novo índice não clusterizado na tabela de trigramas, dobrando o espaço de armazenamento (já significativo) usado. A tabela de trigramas contém um único inteiro e um char(3) por linha; um índice não clusterizado na coluna inteira ganharia o char(3) coluna em todos os níveis (cortesia do índice clusterizado e a necessidade de chaves de índice serem exclusivas em todos os níveis). Também há espaço de memória a ser considerado, pois as pesquisas de trigramas funcionam melhor quando todas as leituras são do cache. 
 
 O índice extra tornaria a integridade referencial em cascata uma opção, mas isso geralmente é mais problemático do que vale a pena. 
 
 A busca de trigramas não é uma panacéia. Os requisitos de armazenamento extra, a complexidade da implementação e o impacto no desempenho da atualização pesam muito contra isso. A técnica também é inútil para pesquisas que não geram trigramas (mínimo de 3 caracteres). Embora a implementação básica mostrada aqui possa lidar com muitos tipos de pesquisa (começa com, contém, termina com vários curingas), ela não cobre todas as expressões de pesquisa possíveis que podem ser feitas para funcionar com LIKE . Funciona bem para strings de pesquisa que geram trigramas do tipo AND; mais trabalho é necessário para lidar com strings de pesquisa que exigem manipulação do tipo OR ou opções mais avançadas, como expressões regulares. 
 
 Tudo isso dito, se seu aplicativo realmente precisa tem buscas rápidas de caracteres curinga, n-grams são algo a considerar seriamente. 
 
 Conteúdo relacionado:Uma maneira de obter um índice busca por um %wildcard líder por Aaron Bertrand.