Uma maneira de obter uma busca de índice para um %curinga principal

... WHERE SomeColumn LIKE N'%SomePortion%';

1. gato
2. em
3. t

Uma tabela de fragmentos separada

SELECT CustomerID, DeliveryAddressLine2
  FROM Sales.Customers
  WHERE DeliveryAddressLine2 LIKE N'%Hudecova%';
 
/* This returns two rows:
 
    CustomerID  DeliveryAddressLine2
    ----------  ----------------------
    61          1695 Hudecova Avenue
    181         1846 Hudecova Crescent
*/

CREATE TABLE Sales.CustomersCopy
(
  CustomerID int IDENTITY(1,1) CONSTRAINT PK_CustomersCopy PRIMARY KEY,
  CustomerName         nvarchar(100) NOT NULL,
  DeliveryAddressLine1 nvarchar(60) NOT NULL,
  DeliveryAddressLine2 nvarchar(60)
);
GO
 
INSERT Sales.CustomersCopy
(
  CustomerName,
  DeliveryAddressLine1,
  DeliveryAddressLine2
)
SELECT 
  CustomerName,
  DeliveryAddressLine1,
  DeliveryAddressLine2
FROM Sales.Customers
WHERE DeliveryAddressLine2 LIKE N'%Hudecova%';

• 1846 Hudecova Crescent
• 846 Hudecova Crescent
• 46 Hudecova Crescent
• 6 Hudecova Crescent
• Hudecova Crescent
• Hudecova Crescent
• udecova crescente
• decova crescente
• ecova crescente
• Cova Crescente
• Ova Crescente
• vai crescente
• um crescente
• Crescente
• Crescente
• rescente
• escente
• cheiro
• centavos
• ent
• n
• t

CREATE FUNCTION dbo.CreateStringFragments( @input nvarchar(60) )
RETURNS TABLE WITH SCHEMABINDING
AS
  RETURN 
  (
    WITH x(x) AS 
    (
      SELECT 1 UNION ALL SELECT x+1 FROM x WHERE x < (LEN(@input))
    )
    SELECT Fragment = SUBSTRING(@input, x, LEN(@input)) FROM x
  );
GO
 
SELECT Fragment FROM dbo.CreateStringFragments(N'1846 Hudecova Crescent');
-- same output as above bulleted list

CREATE TABLE Sales.CustomerAddressFragments
(
  CustomerID  int          NOT NULL,
  Fragment    nvarchar(60) NOT NULL,
  CONSTRAINT FK_Customers FOREIGN KEY(CustomerID) REFERENCES Sales.CustomersCopy(CustomerID)
);
 
CREATE CLUSTERED INDEX s_cat ON Sales.CustomerAddressFragments(Fragment, CustomerID);

INSERT Sales.CustomerAddressFragments(CustomerID, Fragment)
SELECT c.CustomerID, f.Fragment
  FROM Sales.CustomersCopy AS c
  CROSS APPLY dbo.CreateStringFragments(c.DeliveryAddressLine2) AS f;

SELECT c.CustomerID, c.DeliveryAddressLine2
  FROM Sales.CustomersCopy AS c
  INNER JOIN Sales.CustomerAddressFragments AS f
    ON  f.CustomerID = c.CustomerID
    AND f.Fragment LIKE N'Hudecova%';

SELECT c.CustomerID, c.DeliveryAddressLine2
  FROM Sales.CustomersCopy AS c
  WHERE EXISTS
  (
    SELECT 1 FROM Sales.CustomerAddressFragments
    WHERE CustomerID = c.CustomerID
      AND Fragment LIKE N'Hudecova%'
  );

TRUNCATE TABLE Sales.CustomerAddressFragments;
DELETE Sales.CustomersCopy;
DBCC FREEPROCCACHE WITH NO_INFOMSGS;
 
INSERT Sales.CustomersCopy WITH (TABLOCKX) (CustomerName, DeliveryAddressLine1, DeliveryAddressLine2)
SELECT TOP (400000) c1.CustomerName, c1.DeliveryAddressLine1, c2.DeliveryAddressLine2
  FROM Sales.Customers c1 CROSS JOIN Sales.Customers c2
  ORDER BY NEWID(); -- fun for distribution
 
-- this will take a bit longer - on my system, ~4 minutes
-- probably because I didn't bother to pre-expand files
INSERT Sales.CustomerAddressFragments WITH (TABLOCKX) (CustomerID, Fragment)
SELECT c.CustomerID, f.Fragment
  FROM Sales.CustomersCopy AS c
  CROSS APPLY dbo.CreateStringFragments(c.DeliveryAddressLine2) AS f;
 
-- repeated for compressed version of the table
-- 7.25 million rows, 278MB (79MB compressed; saving those tests for another day)

Hudecova%


Para esse padrão, a varredura ainda era a mesma para a condição LIKE; no entanto, com mais dados, o custo é muito maior. As buscas na tabela de fragmentos realmente compensam nessa contagem de linhas (1.206), mesmo com estimativas muito baixas. O plano EXISTS adiciona uma classificação distinta, que você esperaria adicionar ao custo, embora neste caso acabe fazendo menos leituras:


Planeje o JOIN para a tabela de fragmentos Planejar o EXISTS em relação à tabela de fragmentos

cova%


À medida que retiramos algumas letras do nosso predicado, vemos as leituras na verdade um pouco mais altas do que com a varredura de índice clusterizado original, e agora sobre -estimar as linhas. Mesmo assim, nossa duração permanece significativamente menor com ambas as consultas de fragmento; a diferença desta vez é mais sutil - ambos têm tipos (apenas EXISTS é distinto):


Planejar o JOIN para a tabela de fragmentos Planejar o EXISTS em relação à tabela de fragmentos

% de óvulos


Tirar uma letra adicional não mudou muito; embora valha a pena notar o quanto as linhas estimadas e reais saltam aqui – o que significa que isso pode ser um padrão de substring comum. A consulta LIKE original ainda é um pouco mais lenta que as consultas de fragmento.


Planeje o JOIN para a tabela de fragmentos Planejar o EXISTS em relação à tabela de fragmentos

va%


Com duas letras, isso introduz nossa primeira discrepância. Observe que o JOIN produz mais linhas do que a consulta original ou EXISTS. Por que seria isso?


Planeje o JOIN para a tabela de fragmentos Planeje o EXISTS em relação à tabela de fragmentos Não precisamos procurar muito. Lembre-se de que há um fragmento começando de cada caractere sucessivo no endereço original, o que significa algo como 899 Valentova Road terá duas linhas na tabela de fragmentos que começam com va (diferenciação de maiúsculas e minúsculas à parte). Então você vai combinar em ambos Fragment = N'Valentova Road' e Fragment = N'va Road' . Vou poupar a pesquisa e fornecer um único exemplo de muitos:


SELECT TOP (2) c.CustomerID, c.DeliveryAddressLine2, f.Fragment
FROM Sales.CustomersCopy AS c
INNER JOIN Sales.CustomerAddressFragments AS f
ON c.CustomerID = f.CustomerID
WHERE f.Fragment LIKE N'va%'
AND c.DeliveryAddressLine2 = N'899 Valentova Road'
AND f.CustomerID = 351;
 
/*
CustomerID  DeliveryAddressLine2  Fragment
----------  --------------------  --------------
351         899 Valentova Road    va Road
351         899 Valentova Road    Valentova Road
*/


Isso explica prontamente por que o JOIN produz mais linhas; se você quiser corresponder à saída da consulta LIKE original, você deve usar EXISTS. O fato de que os resultados corretos geralmente também podem ser obtidos de maneira menos intensiva em recursos é apenas um bônus. (Eu ficaria nervoso se as pessoas escolhessem o JOIN se essa fosse a opção repetidamente mais eficiente – você deve sempre favorecer os resultados corretos em vez de se preocupar com o desempenho.)

Resumo

Advertências

• Você precisará manter a tabela de fragmentos sincronizada com a tabela base usando gatilhos – o mais simples seria para inserções e atualizações, excluir todas as linhas para esses clientes e reinseri-las, e para exclusões, obviamente, remover as linhas dos fragmentos tabela.
• Como mencionado, esta solução funcionou melhor para esse tamanho de dados específico e pode não funcionar tão bem para outros comprimentos de string. Isso justificaria mais testes para garantir que seja apropriado para o tamanho da coluna, o comprimento médio do valor e o comprimento típico do parâmetro de pesquisa.
• Como teremos muitas cópias de fragmentos como "Crescent" e "Street" (não importa todos os nomes de ruas e números de casas iguais ou semelhantes), poderíamos normalizá-lo ainda mais armazenando cada fragmento único em uma tabela de fragmentos, e, em seguida, outra tabela que atua como uma tabela de junção muitos-para-muitos. Isso seria muito mais complicado de configurar, e não tenho certeza se haveria muito a ganhar.
• Ainda não investiguei completamente a compactação de página, parece que – pelo menos em teoria – isso poderia trazer algum benefício. Também tenho a sensação de que uma implementação de columnstore também pode ser benéfica em alguns casos.