Con bastante frecuencia nos encontramos que nuestros clientes sufren problemas de rendimiento debido a filtros sobre campos de texto. Es bastante habitual que se quiera permitir filtrados “libres” sobre textos, descripciones, documentos, etc. pero no se tenga en cuenta que, en función del patrón de búsqueda, esto puede ser bastante pesado para SQL Server.
En este tipo de situaciones de lentitud normalmente se intenta aliviarlas mediante indexación extra. En el caso de búsquedas de texto bien mediante índices más estrechos (que solo incluyan la columna de texto y/o particionados en base a algún otro criterio de filtrado como la fecha) o bien mediante con diccionarios Full-Text Search.
Sin embargo, hay casos donde la búsqueda tiene unos requerimientos que hacen que no encaje con ninguna de las alternativas anteriores. Por ejemplo, si tenemos que permitir búsquedas libres en base a un mínimo de cuatro caracteres donde no buscamos ni palabras completas, ni prefijos y tampoco sufijos (que sería lo que nos soportaría Full-Text Search, incluyendo también una columna reverse del texto y buscando por el reverse del sufijo).
En estos casos necesitamos utilizar estrategias de indexación alternativas, adaptadas a las necesidades específicas de cada caso. En enero hablamos de este tipo de estrategias aquí (Técnicas de apoyo a la indexación tradicional) y vamos a mostrar una implementación particular para este caso. Lo que vamos a mostrar es cómo utilizar N-grams (trigrams en este caso) junto a Full-Text Search para acelerar la búsqueda.
La idea base es sencilla, ya que Full-Text no nos permite realizar búsquedas del tipo “text like ‘%abcd%’” vamos a descomponer en cadenas de cuatro caracteres (quadgrams) el texto y realizaremos búsquedas de palabras completas sobre dicha descomposición con Full-Text. Comenzaremos creando una tabla con textos de cierto tamaño donde marcaremos 10 filas con cuatro caracteres poco frecuentes (zzzz):
create database [trigrams&fulltext] go use [trigrams&fulltext] go create table test (id int identity(1,1) primary key, texto varchar(8000), ngrams varchar(8000)) go insert into test (texto) select top (10000000) s.name +' '+ s2.name + ' ' + s3.name + ' ' + s4.name texto from sys.objects s, sys.objects s2, sys.objects s3, sys.objects s4 -- Marcamos 10 filas con unos caracteres poco frecuentes update t set texto=texto+'zzzz' from (select top 10 texto from test) t
El siguiente paso será probar qué rendimiento nos da con un filtro de búsqueda like tradicional en distintos casos, desde muy poco selectivos, donde muchas filas son devueltas, al caso más selectivo del zzzz:
-- test búsqueda set statistics io on set statistics time on -- Poco selectiva select count(*) from test where texto like '%sysr%' -- 3322972 filas -- SQL Server Execution Times: -- CPU time = 15030 ms, elapsed time = 2175 ms. -- Más selectiva select count(*) from test where texto like '%ryNO%' -- 297010 -- SQL Server Execution Times: -- CPU time = 14624 ms, elapsed time = 2479 ms. -- Muy selectiva select count(*) from test where texto like '%zzzz%' -- 10 -- SQL Server Execution Times: -- CPU time = 15221 ms, elapsed time = 2493 ms.
Podemos ver que en este caso los tiempos de ejecución son similares, ya que en todos los casos tenemos que escanear toda la tabla para localizar las filas afectadas.
Una curiosidad en este caso particular es que la primera consulta, la que devuelve más filas, es la más rápida. La razón es cómo realiza SQL Server la busqueda dentro de una cadena (de izquierda a derecha) por lo que en función de lo “pronto” en la cadena que encuentre un “match” el tiempo total será mayor o menor. En el caso de “sysr” en muchas cadenas es el prefijo, lo cual hace que sea más rápido evaluar el match de la fila.
Una vez tenemos esta “linea base” vamos a crear una función para particionar en ngrams (original de Alan Burstein):
- Función generadora de N-Grams
-- De Alan Burstein (http://www.sqlservercentral.com/articles/Tally+Table/142316/)
CREATE FUNCTION dbo.NGrams8k
(
@string varchar(8000), -- Input string
@N int -- requested token size
)
/****************************************************************************************
Purpose:
A character-level N-Grams function that outputs a contiguous stream of @N-sized tokens
based on an input string (@string). Accepts strings up to 8000 varchar characters long.
For more information about N-Grams see: http://en.wikipedia.org/wiki/N-gram.
Compatibility:
SQL Server 2008+, Azure SQL Database
Syntax:
--===== Autonomous
SELECT position, token FROM dbo.NGrams8k(@string,@N);
--===== Against a table using APPLY
SELECT s.SomeID, ng.position, ng.token
FROM dbo.SomeTable s
CROSS APPLY dbo.NGrams8K(s.SomeValue,@N) ng;
Parameters:
@string = The input string to split into tokens.
@N = The size of each token returned.
Returns:
Position = bigint; the position of the token in the input string
token = varchar(8000); a @N-sized character-level N-Gram token
Developer Notes:
1. NGrams8k is not case sensitive
2. Many functions that use NGrams8k will see a huge performance gain when the optimizer
creates a parallel execution plan. One way to get a parallel query plan (if the
optimizer does not choose one) is to use make_parallel by Adam Machanic which can be
found here:
sqlblog.com/blogs/adam_machanic/archive/2013/07/11/next-level-parallel-plan-porcing.aspx
3. When @N is less than 1 or greater than the datalength of the input string then no
tokens (rows) are returned. If either @string or @N are NULL no rows are returned.
This is a debatable topic but the thinking behind this decision is that: because you
can't split 'xxx' into 4-grams, you can't split a NULL value into unigrams and you
can't turn anything into NULL-grams, no rows should be returned.
For people who would prefer that a NULL input forces the function to return a single
NULL output you could add this code to the end of the function:
UNION ALL
SELECT 1, NULL
WHERE NOT(@N > 0 AND @N <= DATALENGTH(@string)) OR (@N IS NULL OR @string IS NULL)
4. NGrams8k can also be used as a Tally Table with the position column being your "N"
row. To do so use REPLICATE to create an imaginary string, then use NGrams8k to split
it into unigrams then only return the position column. NGrams8k will get you up to
8000 numbers. There will be no performance penalty for sorting by position in
ascending order but there is for sorting in descending order. To get the numbers in
descending order without forcing a sort in the query plan use the following formula:
N = <highest number>-position+1.
Pseudo Tally Table Examples:
--===== (1) Get the numbers 1 to 100 in ascending order:
SELECT N = position
FROM dbo.NGrams8k(REPLICATE(0,100),1);
--===== (2) Get the numbers 1 to 100 in descending order:
DECLARE @maxN int = 100;
SELECT N = @maxN-position+1
FROM dbo.NGrams8k(REPLICATE(0,@maxN),1)
ORDER BY position;
5. NGrams8k is deterministic. For more about deterministic functions see:
https://msdn.microsoft.com/en-us/library/ms178091.aspx
Usage Examples:
--===== Turn the string, 'abcd' into unigrams, bigrams and trigrams
SELECT position, token FROM dbo.NGrams8k('abcd',1); -- unigrams (@N=1)
SELECT position, token FROM dbo.NGrams8k('abcd',2); -- bigrams (@N=2)
SELECT position, token FROM dbo.NGrams8k('abcd',3); -- trigrams (@N=3)
--===== How many times the substring "AB" appears in each record
DECLARE @table TABLE(stringID int identity primary key, string varchar(100));
INSERT @table(string) VALUES ('AB123AB'),('123ABABAB'),('!AB!AB!'),('AB-AB-AB-AB-AB');
SELECT string, occurances = COUNT(*)
FROM @table t
CROSS APPLY dbo.NGrams8k(t.string,2) ng
WHERE ng.token = 'AB'
GROUP BY string;
----------------------------------------------------------------------------------------
Revision History:
Rev 00 - 20140310 - Initial Development - Alan Burstein
Rev 01 - 20150522 - Removed DQS N-Grams functionality, improved iTally logic. Also Added
conversion to bigint in the TOP logic to remove implicit conversion
to bigint - Alan Burstein
Rev 03 - 20150909 - Added logic to only return values if @N is greater than 0 and less
than the length of @string. Updated comment section. - Alan Burstein
Rev 04 - 20151029 - Added ISNULL logic to the TOP clause for the @string and @N
parameters to prevent a NULL string or NULL @N from causing "an
improper value" being passed to the TOP clause. - Alan Burstein
****************************************************************************************/
RETURNS TABLE WITH SCHEMABINDING AS RETURN
WITH
L1(N) AS
(
SELECT 1
FROM (VALUES -- 90 NULL values used to create the CTE Tally Table
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL)
) t(N)
),
iTally(N) AS -- my cte Tally Table
(
SELECT TOP(ABS(CONVERT(BIGINT,(DATALENGTH(ISNULL(@string,''))-(ISNULL(@N,1)-1)),0)))
ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) -- Order by a constant to avoid a sort
FROM L1 a CROSS JOIN L1 b -- cartesian product for 8100 rows (90^2)
)
SELECT
position = N, -- position of the token in the string(s)
token = SUBSTRING(@string,CAST(N AS int),@N) -- the @N-Sized token
FROM iTally
WHERE @N > 0 AND @N <= DATALENGTH(@string); -- Protection against bad parameter values
GO
Crearemos otra función que, utilizando la anterior, nos concatenará el resultado de la descomposición en ngrams en una cadena separada por comas:
create function dbo.NGrams8k_agg (@cadena varchar(8000)) returns varchar(8000) as begin declare @concat varchar(8000) set @concat=(select STRING_AGG(token,',') from dbo.NGrams8k(@cadena,4)) return @concat end go
Una vez tenemos esta función, actualizaremos la columna ngrams de nuestra tabla:
-- Calculamos los ngrams y los cargamos en la columna sobre la que crearemos el full text update test set ngrams=dbo.NGrams8k_agg(texto)
El último paso consistirá en crear nuestro índice fulltext:
-- Creamos el fulltext CREATE FULLTEXT CATALOG ft AS DEFAULT; CREATE FULLTEXT INDEX ON test(ngrams) KEY INDEX PK__test__3213E83F8FE37964 WITH STOPLIST = SYSTEM;
Realizaremos una primera prueba con el patrón que es muy selectivo y veremos cómo se utiliza el índice fulltext para localizar los valores de la PK que cumplen y luego el índice cluster para recuperar el resto de datos:
-- Buscamos con fulltext con 4 caracteres declare @patron varchar(200) = 'zzzz' select * from test where contains(ngrams,@patron)
Vamos a testear las búsquedas anteriores pero utilizando fulltext sobre la columna con ngrams:
-- Comparamos tiempos -- Poco selectiva, no mejoramos nada, incluso empeoramos un poco declare @patron varchar(200) = 'sysr' select count(*) from test where contains(ngrams,@patron) -- 3322972 filas -- SQL Server Execution Times: -- CPU time = 15282 ms, elapsed time = 2423 ms. -- VS -- CPU time = 15030 ms, elapsed time = 2175 ms. -- Más selectiva, mejoramos mucho, un 80% menos CPU y un 80% menos duración declare @patron varchar(200) = 'ryNO' select count(*) from test where contains(ngrams,@patron) -- 297010 -- SQL Server Execution Times: -- CPU time = 2968 ms, elapsed time = 471 ms -- VS -- CPU time = 14624 ms, elapsed time = 2479 ms. -- Muy selectiva, mejoramos muchísimo, un 99% menos de CPU y un 98% menos de duración declare @patron varchar(200) = 'zzzz' select count(*) from test where contains(ngrams,@patron) -- 10 -- SQL Server Execution Times: -- CPU time = 0 ms, elapsed time = 54 ms. -- VS -- CPU time = 15221 ms, elapsed time = 2493 ms.
Podemos ver como en este caso la selectividad del filtro nos afecta mucho. Si nuestra búsqueda va a devolver muchos resultados, no es una solución eficiente. Sin embargo, suele ser habitual que al limitar a 4 caracteres ya la búsqueda se acote bastante por lo que los escenarios de selectividad media-alta suelen ser mucho más representativos. En estos casos esta alternativa nos da un rendimiento muy superior.
Para el caso de búsquedas de más de 4 caracteres lo que debemos hacer es hacer una búsqueda por la intersección de todas aquellas filas que contengan alguno de los quadgrams que podamos generar con nuestra cadena de búsqueda. Para ello una posibilidad es generar código dinámico que compruebe esto, con la precaución de filtrar/validar que de los resultados solo devolvemos los que cumplan un like ‘%patron%’. Esto es necesario ya que si buscamos por abcde tendríamos dos quadgrams, abcd y bcde, pero podríamos tener un falso positivo con cadenas como por ejemplo ‘abcd otras cosas bcde’ que contienen ambos quadgrams pero no consecutivos.
-- Si tenemos más de 4, sobre la descomposición en 4 en 4 y obtenemos la intersección de los resultados declare @patron varchar(200) = 'sysrscolszzzz' declare @ngrams table (token varchar(200)) insert into @ngrams select token from dbo.NGrams8K(@patron,4) -- generar código dinámico concatenando múltiples contains con un string_agg (token,') and contains(t.ngrams,' declare @sql varchar(max) print @sql set @sql = (select 'select * from test t where contains(t.ngrams,''' + string_agg (token,''') and contains(t.ngrams,''') + ''') and t.texto like ''%'+@patron+'%''' from @ngrams) exec (@sql)
Esta sería la consulta dinámica que se generaría para este ejemplo:
SELECT *
FROM test t
WHERE CONTAINS(t.ngrams, 'sysr')
AND CONTAINS(t.ngrams, 'ysrs')
AND CONTAINS(t.ngrams, 'srsc')
AND CONTAINS(t.ngrams, 'rsco')
AND CONTAINS(t.ngrams, 'scol')
AND CONTAINS(t.ngrams, 'cols')
AND CONTAINS(t.ngrams, 'olsz')
AND CONTAINS(t.ngrams, 'lszz')
AND CONTAINS(t.ngrams, 'szzz')
AND CONTAINS(t.ngrams, 'zzzz')
AND t.texto LIKE '%sysrscolszzzz%'
En este post hemos analizado una estrategia combinada entre ngrams y fulltext para acelerar búsquedas libres en textos. Esta no es la única posibilidad, ya que podríamos guardar por ejemplo la relación entre las filas de la tabla principal con los N grams con una tabla con una relación 1:N y realizar este filtrado utilizando esta estructura. En otras ocasiones cuando las palabras claves a buscar están limitadas es posible utilizar mapas de bits para indicar si una fila cumple 1 o N de dichas palabras claves y realizar búsquedas sobre dichos mapas de bits. En resumen, cuando tenemos problemas de rendimiento debemos analizar la razón de este problema de rendimiento para comprender por donde podemos atacarlo. Si queremos optimizar escenarios más complejos debemos estar abiertos a estrategias alternativas, que normalmente requieren más trabajo, son más laboriosas de mantener, etc. pero que pueden dar rendimientos no alcanzables con otras técnicas.
