Técnicas de apoyo a la indexación tradicional. SQL Server

Cuando los problemas de rendimiento empiezan a surgir uno de los primeros pensamientos que solemos tener está relacionado con la indexación. En SQL Server disponemos de diversos tipos de índices, pero existen circunstancias donde no son especialmente eficientes para el tipo de búsqueda requerido.

En este tipo de situaciones el ingenio entra en juego y podemos plantearnos alternativas que se ajusten mejor a nuestras necesidades. Por comentar algunas, podemos implementar mapas de bits, digrams/trigrams, checksums/hashes, materializaciones de funciones, etc.

Técnicas de apoyo a la indexación tradicional

Vamos a ver un par de ejemplos donde podemos utilizar alguna de estas técnicas para mejorar el rendimiento de una forma que no podríamos hacerlo únicamente con un índice tradicional.

El primero de ellos corresponde a aquellos casos donde tenemos cruces de tablas por campos de texto de longitud elevada. Crearemos una base de datos y utilizaremos como textos las definiciones de los módulos de máster, que contienen cadenas con longitud de varios miles de caracteres:

CREATE DATABASE test_texto
GO
USE test_texto
GO
-- Longitud de textos 
SELECT LEN(definition) FROM master.sys.all_sql_modules
ORDER BY LEN(definition ) DESC
GO

Crearemos un par de tablas, una con 100000 registros y otra con un millón de registros:

SELECT TOP 100000 IDENTITY(INT,1,1) id, s1.definition 
INTO text1
FROM master.sys.all_sql_modules s1,master.sys.all_sql_modules s2, master.sys.all_sql_modules s3

GO

SELECT TOP 1000000 IDENTITY(INT,1,1) id, s1.definition 
INTO text2
FROM master.sys.all_sql_modules s1,master.sys.all_sql_modules s2, master.sys.all_sql_modules s3

El tamaño de estas tablas es de aproximadamente 900 MB y 8.59 GB respectivamente:

Cuando realizamos un conteo del join de estas tablas por la columna definition nos encontramos un muy elevado consumo de CPU (416 segundos) y un alta duración (148 segundos):

SET STATISTICS time ON
SELECT COUNT(*) FROM text1 INNER JOIN text2 ON text1.definition=text2.definition
GO
-- SQL Server Execution Times:
--   CPU time = 416609 ms,  elapsed time = 148303 ms.

Si intentamos crear un índice por la columna de texto obtendremos un error por el tipo de datos de texto largo empleado:

-- Error índice normal
CREATE INDEX ix_definition ON text1 (definition)

Msg 1919, Level 16, State 1, Line 31
Column ‘definition’ in table ‘text1’ is of a type that is invalid for use as a key column in an index.

Podríamos pensar que quizás los índices columnares, más modernos, nos permitirán crear un índice sobre este tipo de columnas de texto pero no es así:

-- Con columnar?
CREATE CLUSTERED COLUMNSTORE INDEX ix_clu ON text1 (id)

Msg 35343, Level 16, State 1, Line 52
The statement failed. Column ‘definition’ has a data type that cannot participate in a columnstore index. Omit column ‘definition’.

Como solución a este problema podemos optar por la creación de columas de tipo checksum calculados sobre el texto. Estas columnas se mantendrán persistidas y se actualizarán automáticamente si se realiza algún cambio sobre el texto:

-- Añadir checksums
ALTER TABLE text1 ADD CHECKSUM AS CHECKSUM(DEFINITION) PERSISTED
ALTER TABLE text2 ADD CHECKSUM AS CHECKSUM(DEFINITION) PERSISTED

Si ejecutamos la consulta anterior utilizando las nuevas columnas podemos ver que bajamos el consumo de CPU a 1 segundo y la duración no llega a 2 segundos. El plan en sí es muy parecido, la única diferencia importante es el tipo de datos utilizado en el cruce:

SELECT COUNT(*) FROM text1 INNER JOIN text2 ON text1.checksum=text2.checksum
--  SQL Server Execution Times:
-- CPU time = 1077 ms,  elapsed time = 1866 ms.

Además, el tipo de datos checksum es un entero por lo que podríamos ya indexar por ejemplo la tabla de mayor tamaño:

CREATE INDEX ix_definition ON text2 (CHECKSUM)
GO

Tras este cambio bajamos el consumo de CPU a unos meros 172 milisegundos y la duración también a solamente 60 milisegundos:

SELECT COUNT(*) FROM text1 INNER JOIN text2 ON text1.checksum=text2.checksum
-- CPU time = 172 ms,  elapsed time = 60 ms.

Ahora imaginemos que tenemos varios flags independientes que calcularemos a partir de los textos. Por ejemplo un bit por cada caracter de la A a la Z según si está,o no, contenido en la definición del texto. Para calcularlo crearemos las columnas calculadas en base al resultado de la expresión LIKE ‘%A%’ hasta LIKE ‘%Z%’:

ALTER TABLE text2 ADD A AS (CONVERT(BIT,CASE WHEN definition LIKE '%A%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  B AS (CONVERT(BIT,CASE WHEN definition LIKE '%B%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  C AS (CONVERT(BIT,CASE WHEN definition LIKE '%C%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  D AS (CONVERT(BIT,CASE WHEN definition LIKE '%D%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  E AS (CONVERT(BIT,CASE WHEN definition LIKE '%E%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  F AS (CONVERT(BIT,CASE WHEN definition LIKE '%F%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  G AS (CONVERT(BIT,CASE WHEN definition LIKE '%G%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  H AS (CONVERT(BIT,CASE WHEN definition LIKE '%H%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  I AS (CONVERT(BIT,CASE WHEN definition LIKE '%I%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  J AS (CONVERT(BIT,CASE WHEN definition LIKE '%J%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  K AS (CONVERT(BIT,CASE WHEN definition LIKE '%K%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  L AS (CONVERT(BIT,CASE WHEN definition LIKE '%L%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  M AS (CONVERT(BIT,CASE WHEN definition LIKE '%M%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  N AS (CONVERT(BIT,CASE WHEN definition LIKE '%N%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  Ñ AS (CONVERT(BIT,CASE WHEN definition LIKE '%Ñ%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  O AS (CONVERT(BIT,CASE WHEN definition LIKE '%O%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  P AS (CONVERT(BIT,CASE WHEN definition LIKE '%P%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  Q AS (CONVERT(BIT,CASE WHEN definition LIKE '%Q%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  R AS (CONVERT(BIT,CASE WHEN definition LIKE '%R%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  S AS (CONVERT(BIT,CASE WHEN definition LIKE '%S%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  T AS (CONVERT(BIT,CASE WHEN definition LIKE '%T%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  U AS (CONVERT(BIT,CASE WHEN definition LIKE '%U%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  V AS (CONVERT(BIT,CASE WHEN definition LIKE '%V%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  W AS (CONVERT(BIT,CASE WHEN definition LIKE '%W%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  X AS (CONVERT(BIT,CASE WHEN definition LIKE '%X%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  Y AS (CONVERT(BIT,CASE WHEN definition LIKE '%Y%' THEN 1 ELSE 0 end)) PERSISTED
ALTER TABLE text2 ADD  Z AS (CONVERT(BIT,CASE WHEN definition LIKE '%Z%' THEN 1 ELSE 0 end)) PERSISTED

Esto nos genera una especie de bitmap:

SELECT DISTINCT A,B,C,D,E,F,G,H,I,J,K,L,M,N,Ñ,O,P,Q,R,S,T,U,V,W,X,Y,Z FROM text2

Si intentamos buscar unos registros que cumplan ciertos valores para estos bits vemos que el rendimiento no es muy bueno y tenemos que escanear toda la tabla:

SET STATISTICS TIME on
SELECT * FROM text2 WHERE 
A=1 AND B=1 AND C=1 AND D=1 AND E=1 AND F=1 AND G=1 AND H=0 AND I=1 AND 
J=0 AND K=1 AND L=1 AND M=1 AND N=1 AND Ñ=0 AND N=1 AND O=1 AND P=1 AND 
Q=0 AND R=1 AND S=1 AND T=1 AND U=0 AND V=1 AND W=1 AND X=0 AND Y=1 AND 
Z=0

-- SQL Server Execution Times:
--   CPU time = 844 ms,  elapsed time = 500 ms.

Una posibilidad de optimización es crear un índice por todas estas columnas:

CREATE INDEX ix_bit ON text2 (A,B,C,D,E,F,G,H,I,J,K,L,M,N,Ñ,O,P,Q,R,S,T,U,V,W,X,Y,Z)

Una vez creado el índice si repetimos la búsqueda veremos que mejora muy sustancialmente el consumo de CPU gracias al índice:

SELECT * FROM text2 WHERE 
A=1 AND B=1 AND C=1 AND D=1 AND E=1 AND F=1 AND G=1 AND H=0 AND I=1 AND 
J=0 AND K=1 AND L=1 AND M=1 AND N=1 AND Ñ=0 AND N=1 AND O=1 AND P=1 AND 
Q=0 AND R=1 AND S=1 AND T=1 AND U=0 AND V=1 AND W=1 AND X=0 AND Y=1 AND 
Z=0

-- SQL Server Execution Times:
--   CPU time = 31 ms,  elapsed time = 415 ms.

A continuación vamos a plantear un escenario bastante habitual que consiste en una búsqueda pero que filtra por varios grupos de bits y no solo por un único grupo:

SET STATISTICS TIME on
SELECT * FROM text2 WHERE 
A=1 AND B=1 AND C=1 AND D=1 AND E=1 AND F=1 AND G=1 AND H=0 AND I=1 AND 
J=0 AND K=1 AND L=1 AND M=1 AND N=1 AND Ñ=0 AND N=1 AND O=1 AND P=1 AND 
Q=0 AND R=1 AND S=1 AND T=1 AND U=0 AND V=1 AND W=1 AND X=0 AND Y=1 AND 
Z=0
OR 
A=0 AND B=1 AND C=1 AND D=1 AND E=1 AND F=1 AND G=1 AND H=0 AND I=1 AND 
J=0 AND K=1 AND L=1 AND M=1 AND N=1 AND Ñ=0 AND N=1 AND O=1 AND P=1 AND 
Q=0 AND R=1 AND S=1 AND T=1 AND U=0 AND V=1 AND W=1 AND X=0 AND Y=1 AND 
Z=0
OR
A=1 AND B=0 AND C=1 AND D=1 AND E=1 AND F=1 AND G=1 AND H=0 AND I=1 AND 
J=0 AND K=1 AND L=1 AND M=1 AND N=1 AND Ñ=0 AND N=1 AND O=1 AND P=1 AND 
Q=0 AND R=1 AND S=1 AND T=1 AND U=0 AND V=1 AND W=1 AND X=0 AND Y=1 AND 
Z=0
OR 
A=0 AND B=0 AND C=1 AND D=1 AND E=1 AND F=1 AND G=1 AND H=0 AND I=1 AND 
J=0 AND K=1 AND L=1 AND M=1 AND N=1 AND Ñ=0 AND N=1 AND O=1 AND P=1 AND 
Q=0 AND R=1 AND S=1 AND T=1 AND U=0 AND V=1 AND W=1 AND X=0 AND Y=1 AND 
Z=0
 
--SQL Server Execution Times:
--   CPU time = 325 ms,  elapsed time = 388 ms.

Aunque podemos ver que se hace uso del índice:

Podemos ver como el uso del índice no es eficiente ya que los predicados de búsqueda únicamente utilizan los dos primeros filtrados (A=0 & B=0, A=0 & B=1, A=1 & B=0 y A=1 & B=1):

Por tanto si necesitamos filtrar por varios grupos de bits esta indexación no es eficiente. Como alternativa podemos crear una columna que represente estos bits de forma compacta y la rellenaremos multiplicando cada bit por su peso. Por último añadiremos un índice por esta columna bitmap:

ALTER TABLE text2 ADD bitmap BIGINT

UPDATE dbo.text2
SET bitmap= 
A*1 + B*2 + C*4 + D*8 + E*16 + F*32 + G*64+ H*128 +
I*256 + J*512 + K*1024 + L*2048 + M*4096 + N *8192 +
Ñ*16384 + O*32768 + P*65536 + Q*131072 + R*262144 + 
S*524288 + T*1048576 + U*2097152 + V*4194304 + 
W*8388608 + X*16777216 + Y*33554432 + Z*67108864

CREATE INDEX ix_bitmap ON text2 (bitmap)

Con esta alternativa podremos hacer búsquedas eficientes en base a un único filtro de mapa de bits:

SET STATISTICS TIME on
SELECT * FROM text2 WHERE 
bitmap=48086399

--SQL Server Execution Times:
--   CPU time = 0 ms,  elapsed time = 295 ms.

Pero también funcionará de forma correcta con varios valores. Podemos ver como se utiliza el índice y se realiza una búsqueda por cada uno de los cuatro valores:

SELECT * FROM text2 WHERE 
bitmap=48086399
OR
bitmap=48086398
OR
bitmap=48086397
OR
bitmap=48086396

-- SQL Server Execution Times:
--   CPU time = 16 ms,  elapsed time = 329 ms.

En conclusión, ante problemas de búsqueda o de cruce de datos menos habituales necesitamos pensar en soluciones alternativas. En un mundo ideal el motor de SQL Server tendría una mayor cantidad de estrategias y recursos para optimizar este tipo de situaciones. Por ejemplo para cadenas de texto podría incorporar automáticamente en el tipo de datos un checksum oculto y utilizarlo de forma transparente en este tipo de comparaciones entre cadenas. También podría permitir empaquetar de forma automática estos mapas de bits mediante un tipo de dato nativo que nos permita acceder a los flags/bits de forma individual y a la vez que nos permitiera indexar el mapa completo de bits de forma sencilla.