Buscando texto eficientemente dentro de un string grande

1 comentario

Cuando necesitamos buscar un texto dentro de un string podemos usar LIKE ‘%TextoBuscado%’ o también podemos usar CONTAINING. Ambos funcionarán muy bien, pero tienen un problema: si la cantidad de filas es muy grande o la columna donde puede encontrarse el texto que buscamos tiene muchos caracteres, puede ser muy lento, a veces inclusive extremadamente lento.

La idea para este artículo la obtuve de aquí:

https://blog.cincura.net/233577-poor-mans-full-text-using-psql-only-on-firebird/

Listado 1.

SELECT
   *
FROM
   MiTabla
WHERE
   MiColumna LIKE '%Asunción%'

Listado 2.

SELECT
   *
FROM
   MiTabla
WHERE
   MiColumna CONTAINING 'Asunción'

Tanto el SELECT del Listado 1. como el SELECT del Listado 2. harán bien su trabajo, pero como ya dijimos antes, si la cantidad de filas de MiTabla es muy grande o la cantidad de caracteres en MiColumna es muy grande, pueden ser muy lentos. ¿Por qué? Porque el Firebird nunca usará un índice en esos casos y por lo tanto deberá buscar secuencialmente en cada columna de cada fila la palabra que deseamos encontrar.

Si necesitamos gran velocidad en la búsqueda entonces debemos emplear otro aprovechamiento: usar un diccionario de palabras.

La idea es la siguiente: cada palabra que aparece en la columna MiColumna la guardamos en otra tabla, junto con su correspondiente Identificador. A esa columna le definiremos un índice y de esa manera las búsquedas serán rapidísimas.

Desde luego que hacer eso solamente se justificará si las búsquedas realizadas mediante el Listado 1. o el Listado 2. son lentas, en otro caso no vale la pena tomarse la molestia de hacerlo.

Para que nuestra técnica sea más inteligente también debemos tener en cuenta que a veces los usuarios se equivocan al escribir las palabras que están buscando. Por ejemplo, quieren buscar ‘Asunción’ pero escribieron ‘Asuncion’; o sea, sin el acento sobre la letra ‘o’. O escribieron ‘ASUNCION’, o sea todo en mayúsculas; o escribieron ‘Asumción’, o sea que en lugar de la letra ‘n’ pusieron la letra ‘m’.

Entonces lo que haremos será lo siguiente:

  1. Crear un dominio que acepte tanto mayúsculas como mínusculas (case insensitive) y que acepte tanto palabras acentuadas como no acentuadas (accent insensitive)
  2. Crear una tabla donde se guardarán las palabras y en la cual usaremos el dominio creado
  3. Crear un índice normal que usaremos para buscar palabras normales
  4. Crear un índice inverso que usaremos para buscar palabras invertidas
  5. Crear un stored procedure seleccionable que servirá para extraer todas las palabras de un texto
  6. Crear un trigger que ejecutará al stored procedure seleccionable y luego guardará cada palabra distinta en la tabla, junto con el Identificador de la fila donde se encuentra

Paso 1. Crear un dominio

Listado 3.

CREATE DOMAIN D_PALABRAS_CI_AI 
AS VARCHAR(40) 
CHARACTER SET ISO8859_1
COLLATE ES_ES_CI_AI;

Definimos este dominio como VARCHAR(40) porque suponemos que ninguna de las palabras tendrá más de 40 caracteres, si eso pudiera ocurrir entonces tendrías que aumentar el tamaño.

Paso 2. Crear la tabla donde se guardarán las palabras

palabras01

Captura 1. Si haces clic en la imagen la verás más grande

Nuestra tabla (bastante apropiadamente) se llama DICCIONARIO porque contendrá una lista de palabras.

En la columna DIC_TABLAX se guardará el nombre de la tabla que contiene las palabras que podríamos buscar. Eso porque podríamos tener varias tablas en las cuales sería útil realizar esta búsqueda.

En la columna DIC_COLUMN se guardará el nombre de la columna que contiene las palabras que podríamos buscar. Eso porque dentro de una misma tabla podríamos tener varias columnas que nos interesan.

En la columna DIC_IDECAB se guardará el Identificador de la fila que corresponde a la tabla DIC_TABLAX. De esa manera podremos saber en cual fila de la tabla DIC_TABLAX se encuentra la palabra buscada.

En la columna DIC_PALABR se guardará la palabra que puede ser buscada.

Paso 3. Crear un índice normal

Listado 4.

CREATE INDEX IDX_DICCIONARIO ON DICCIONARIO COMPUTED BY (DIC_TABLAX || DIC_COLUMN || UPPER(DIC_PALABR)
);

Paso 4. Crear un índice inverso

Listado 5.

CREATE INDEX IDX_DICCIONARIO1 ON DICCIONARIO COMPUTED BY (DIC_TABLAX || DIC_COLUMN || REVERSE(UPPER(DIC_PALABR))
);

Paso 5. Crear un stored procedure seleccionable

Listado 6.

CREATE PROCEDURE SPG_HALLAR_PALABRAS(
   ftcTexto VARCHAR(32765))
RETURNS(
   ftcPalabra TYPE OF D_NOMBRE40)
AS
   DECLARE VARIABLE lnI        SMALLINT;
   DECLARE VARIABLE lnInicio   SMALLINT;
   DECLARE VARIABLE lnLongitud SMALLINT;
BEGIN

   lnI        = 1;
   lnInicio   = 1;
   ftcTexto   = ftcTexto || ' ';
   lnLongitud = CHARACTER_LENGTH(ftcTexto);

   WHILE (lnI <= lnLongitud) DO BEGIN
      IF(CAST(SUBSTRING(ftcTexto FROM lnI FOR 1) AS D_PALABRAS_CI_AI) NOT SIMILAR TO '[[:ALNUM:]]' AND POSITION(SUBSTRING(ftcTexto FROM lnI FOR 1) IN 'áéíóúñÁÉÍÓÚÑ') = 0) THEN BEGIN
         IF(lnI > lnInicio) THEN BEGIN
            ftcPalabra = SUBSTRING(ftcTexto FROM lnInicio FOR lnI - lnInicio);
            SUSPEND;
         END
         lnInicio = lnI + 1;
      END
      lnI = lnI + 1;
   END
END;

El stored procedure SPG_HALLAR_PALABRAS hallará cada una de las palabras contenidas en el texto que se le envíe como parámetro de entrada. Veamos algunos ejemplos:

Listado 7.

SELECT
   *
FROM
   SPG_HALLAR_PALABRAS('Hoy es un día lluvioso')

Listado 8.

SELECT
   *
FROM
   SPG_HALLAR_PALABRAS('        Hoy es un día lluvioso')

Listado 9.

SELECT
   *
FROM
   SPG_HALLAR_PALABRAS('       Hoy         es         un día lluvioso')

Listado 10.

SELECT
   *
FROM
   SPG_HALLAR_PALABRAS('   Hoy es un        día lluvioso            ')

Tanto si ejecutamos el Listado 7., como el Listado 8., como el Listado 9., como el Listado 10., siempre obtendremos el mismo resultado, aún cuando a la frase original se le hayan agregado espacios en blanco al principio, en el medio, y al final del texto:

palabras02

Captura 2. Si haces clic en la imagen la verás más grande

Paso 6. Crear un trigger 

Listado 11.

CREATE TRIGGER PRODUCTOS_BIUD FOR PRODUCTOS
   ACTIVE BEFORE INSERT OR UPDATE OR DELETE
   POSITION 1
AS
BEGIN

   -- Se borran las filas que se habían insertado correspondientes a este Producto

   IF (UPDATING OR DELETING) THEN
      DELETE FROM
         DICCIONARIO
      WHERE
         DIC_TABLAX = 'PRODUCTOS' AND
         DIC_COLUMN = 'PRD_NOMBRE' AND
         DIC_IDECAB = OLD.PRD_IDENTI;

   -- Se insertan las nuevas filas, una fila por cada palabra de la columna PRD_NOMBRE

   IF (INSERTING OR UPDATING) THEN BEGIN
      INSERT INTO DICCIONARIO (DIC_TABLAX, DIC_COLUMN, DIC_IDECAB, DIC_PALABR)
         SELECT 'PRODUCTOS', 'PRD_NOMBRE', NEW.PRD_IDENTI, ftcPALABRA FROM SPG_HALLAR_PALABRAS(NEW.PRD_NOMBRE);

   END

END;

Para cada tabla que nos interese deberemos crear un trigger similar al mostrado en el Listado 11., de esa manera cada vez que se realice un INSERT, un UPDATE, o un DELETE a alguna fila de esa tabla que nos interesa, se actualizará también la tabla DICCIONARIO.

En el Listado 11. la tabla que nos interesa se llama PRODUCTOS, y dentro de esa tabla la columna que nos interesa se llama PRD_NOMBRE.

Eso significa que cada una de las palabras que coloquemos en la columna PRD_NOMBRE se insertará en la tabla DICCIONARIO para que podamos buscarla muy rápidamente.

Agregando filas a la tabla DICCIONARIO

Para verificar que todo funciona bien le agregaremos algunas filas a la tabla PRODUCTOS y al hacerlo también le estaremos agregando filas a la tabla DICCIONARIO.

Listado 12.

INSERT INTO PRODUCTOS (PRD_CODIGO, PRD_NOMBRE) VALUES('CC267', 'COCA COLA DE 1 LITRO RETORNABLE');
INSERT INTO PRODUCTOS (PRD_CODIGO, PRD_NOMBRE) VALUES('CP389', 'CERVEZA PILSEN DE 750 C.C.');
INSERT INTO PRODUCTOS (PRD_CODIGO, PRD_NOMBRE) VALUES('LT224', 'Leche Trébol de 1 litro descremada');
INSERT INTO PRODUCTOS (PRD_CODIGO, PRD_NOMBRE) VALUES('CB357', 'Cerveza BUDWEISER 66 DE 1 ÑITRO');

Al insertar esas filas a la tabla PRODUCTOS nuestra tabla DICCIONARIO quedó así:

palabras03

Captura 3. Si haces clic en la imagen la verás más grande

Verificando que funciona

Ahora que tenemos todo listo lo único que nos falta comprobar es que funcione bien.

Mirando la Captura 3. podemos ver que la palabra “LITRO” está escrita en mayúsculas, en minúsculas, y también mal escrita (en la fila 24 dice “ÑITRO” en lugar de “LITRO”).

Entonces, ¿cómo podemos obtener rápidamente las 3 filas donde se encuentra la palabra ‘LITRO’?

Listado 13.

SELECT
   *
FROM
   DICCIONARIO
WHERE
   DIC_TABLAX || DIC_COLUMN || UPPER(DIC_PALABR) STARTING WITH 'PRODUCTOS' || 'PRD_NOMBRE' || 'LITRO' OR
   DIC_TABLAX || DIC_COLUMN || REVERSE(UPPER(DIC_PALABR)) STARTING WITH 'PRODUCTOS' || 'PRD_NOMBRE' || REVERSE('ITRO') OR
   DIC_TABLAX || DIC_COLUMN || REVERSE(UPPER(DIC_PALABR)) STARTING WITH 'PRODUCTOS' || 'PRD_NOMBRE' || REVERSE('TRO') OR
   DIC_TABLAX || DIC_COLUMN || REVERSE(UPPER(DIC_PALABR)) STARTING WITH 'PRODUCTOS' || 'PRD_NOMBRE' || REVERSE('RO')

Si ejecutamos el Listado 13., obtendremos:

palabras04

Captura 4. Si haces clic en la imagen la verás más grande

O sea, que tenemos todas las apariciones de la palabra ‘LITRO’ aún aquella que está mal escrita. Justamente para eso sirven las 3 últimas condiciones puestas en la cláusula WHERE, aquellas que usan la función REVERSE(). En el primer caso escribimos ‘ITRO’, eso significa que la primera letra puede estar mal escrita. En el segundo caso escribimos ‘TRO’, eso significa que las primeras dos letras pueden estar mal escritas. En el tercer caso escribimos ‘RO’, eso significa que las primeras tres letras pueden estar mal escritas.

¿Y qué tan eficiente es nuestro SELECT?

Veamos el PLAN que ejecutó el Firebird para saberlo.

palabras05

Captura 5. Si haces clic en la imagen la verás más grande

Como se puede ver en la Captura 5. para la primera línea de la cláusula WHERE usará el índice IDX_DICCIONARIO, y para la segunda, la tercera, y la cuarta líneas, usará el índice IDX_DICCIONARIO1.

O sea, exactamente lo que queríamos conseguir.

Veamos ahora la eficiencia del Listado 13. en forma gráfica.

palabras06

Captura 6. Si haces clic en la imagen la verás más grande

Está perfecto. Hay 3 filas que cumplen con la condición impuesta en la cláusula WHERE y hay 3 filas extraídas usando los índices.

Conclusión:

Normalmente podemos usar LIKE ‘%MiTextoBuscado%’ o CONTAINING ‘MiTextoBuscado’ cuando queremos obtener las filas que tienen a ‘MiTextoBuscado’ en ellas. Sin embargo, hay ocasiones en que usar dichas sub-cláusulas puede ser extremadamente lento: funciona bien, pero son muy lentas.

Para esos casos lo conveniente es tener un diccionario de palabras, que servirá para indicarnos en cuales filas está el texto que buscamos.

En este artículo hemos visto un método que podemos utilizar para conseguir nuestro objetivo: búsquedas muy rápidas del texto, aunque la tabla tenga muchísimas filas o aunque tenga columnas que contienen muchísimas palabras.

Artículos relacionados:

https://blog.cincura.net/233577-poor-mans-full-text-using-psql-only-on-firebird/

La función REVERSE()

El índice del blog Firebird21

El foro del blog Firebird21

 

 

Los predicados de comparación

2 comentarios

Una de las principales utilidades del comando SELECT es realizar búsquedas en las tablas, así podremos saber si algún dato existe o no existe en ellas. Cuando necesitamos realizar búsquedas podemos emplear varios predicados de comparación, ellos son:

  • BETWEEN … AND …
  • CONTAINING
  • IN
  • LIKE
  • STARTING WITH
  • SIMILAR TO

BETWEEN … AND …

El predicado de comparación BETWEEN … AND … debe recibir dos argumentos (que sean de tipos compatibles) y devuelve como resultado las filas que contienen esos valores o cualquier valor incluido entre ellos. Ejemplo:

SELECT
   CLI_NOMBRE
FROM
   CLIENTES
WHERE
   CLI_CODIGO BETWEEN 1 AND 100

Este SELECT devolverá los nombres de todos los clientes cuyos códigos se encuentren entre 1 y 100, inclusives.

CONTAINING

El predicado de comparación CONTAINING busca dentro de una columna alfanumérica los caracteres pedidos. Importante: no distingue entre mayúsculas y minúsculas. Ejemplo:

SELECT
   CLI_NOMBRE
FROM
   CLIENTES
WHERE
   CLI_NOMBRE CONTAINING 'MAR'

 Este SELECT devolverá los nombres de todos los clientes que tengan los caracteres ‘MAR’ en la columna CLI_NOMBRE. Así, podríamos tener a: MARÍA TERESA, CLAUDIA MARCELA, ROSEMARY, María Estela, Ana María, Tamara, etc.

IN

El predicado de comparación IN es una forma simplificada de escribir el operador de comparación OR, los resultados obtenidos serán los mismos pero se escribe menos.

SELECT
   CLI_NOMBRE
FROM
   CLIENTES
WHERE
   CLI_CODIGO IN (15, 21, 45)

Este SELECT nos devolverá los nombres de los clientes cuyos códigos sean 15, 21, ó 45. Podríamos haberlo escrito así:

SELECT
   CLI_NOMBRE
FROM
   CLIENTES
WHERE
   CLI_CODIGO = 15 OR
   CLI_CODIGO = 21 OR
   CLI_CODIGO = 45

Como puedes ver, al usar el predicado de comparación IN se escribe mucho menos. Y cuanto mayor sea la cantidad de valores a evaluar mayor será lo que se ahorrará. Por lo tanto, si todos los valores serán comparados contra una misma columna (como en los dos ejemplos anteriores) entonces lo más conveniente siempre es usar el predicado IN y no el operador OR. Imagínate todo lo que te ahorrarás de escribir si los valores a comparar no fueran 3 como en estos ejemplos sino 20.

LIKE

El predicado de comparación LIKE tiene cuatro características muy importantes:

  1. Distingue entre mayúsculas y minúsculas
  2. Utiliza patrones de caracteres
  3. Solamente usa índices cuando no empieza con un comodín
  4. Si alguno de los valores es NULL, entonces devuelve NULL

Dentro de los patrones de caracteres podemos usar “comodines”. Ellos son:

‘%’      equivale a cualquier string, de cualquier longitud

‘_’      equivale a un solo caracter

También puede usar un caracter de escape. ¿Qué es un caracter de escape? Un caracter que le dice al Firebird que busque también al caracter que se encuentra a continuación, y lo usaríamos cuando en nuestra búsqueda queremos hallar también a los comodines % y _. Si no existiera el caracter de escape entonces no habría forma de buscar a esos dos caracteres. Ejemplos:

CLI_NOMBRE LIKE 'MAR%'                  -- Devolverá los nombres de todos los clientes que empiecen con MAR
CLI_NOMBRE LIKE 'JULI_'                 -- Devolverá los nombres de todos los clientes que tengan 5 caracteres y los cuatro primeros sean JULI
CLI_NOMBRE LIKE '%MAR%'                 -- Devolverá los nombres de todos los clientes que tengan MAR dentro suyo
PRD_NOMBRE LIKE '%A\_B%' ESCAPE '\'     -- Devolverá todos los nombres de productos que contienen A_B
PRD_NOMBRE LIKE '%\_%' ESCAPE '\'       -- Devolverá todos los nombres de productos que tienen un guión bajo

En el primer y en el segundo casos se usará un índice (si hay uno disponible, por supuesto) porque el patrón de caracteres no empieza con un comodín. En los restantes casos, nunca se usará un índice, porque empiezan con un comodín.

STARTING WITH

El predicado de comparación STARTING WITH es muy parecido a LIKE y se lo puede utilizar cuando se conocen los primeros caracteres del string buscado.

SELECT
   CLI_NOMBRE
FROM
   CLIENTES
WHERE
   CLI_NOMBRE STARTING WITH 'MAR'

Este SELECT nos traerá a MARIA TERESA, MARTHA, MARCELA, MARLENE, etc. O sea, todos los nombres que empiezan con MAR.

SIMILAR TO

El predicado de comparación SIMILAR TO también es parecido a LIKE pero nos permite escribir condiciones más complejas.

SELECT
   CLI_NOMBRE
FROM
   CLIENTES
WHERE
   CLI_NOMBRE SIMILAR TO '[CS]%'

Este SELECT nos devolverá los nombres de todos los clientes que empiecen con C o con S.

SELECT
   CLI_NOMBRE
FROM
   CLIENTES
WHERE
   CLI_NOMBRE SIMILAR TO '[CS]%a'

Este SELECT nos devolverá los nombres de todos los clientes que empiecen con C o con S y que terminen con a.

Artículos relacionados:

Los predicados existenciales

El índice del blog Firebird21

 

Eligiendo entre LIKE y CONTAINING en los SELECT

5 comentarios

Cuando en una consulta la condición de búsqueda es alfanumérica podemos usar (entre otras posibilidades)  a LIKE y a CONTAINING.

¿Cuál es preferible?

LIKE distingue entre mayúsculas y minúsculas, en cambio CONTAINING no las distingue.

Ejemplo:

Tenemos una tabla llamada BANCOS con estas filas:

LIKE1

Captura 1. Si haces clic en la imagen la verás más grande

SELECT
   *
FROM
   BANCOS
WHERE
   BAN_CODSUC >= 0 AND
   BAN_NOMBRE LIKE '%BAN%'

LIKE2

Captura 2. Si haces clic en la imagen la verás más grande

En la Captura 2 podemos ver cuales son las filas que obtuvimos al usar LIKE.

SELECT
   *
FROM
   BANCOS
WHERE
   BAN_CODSUC >= 0 AND
   BAN_NOMBRE CONTAINING 'BAN'

LIKE3

Captura 3. Si haces clic en la imagen la verás más grande

Y en la Captura 3 las filas que obtenemos al usar CONTAINING.

Como puedes ver, con CONTAINING obtuvimos más filas porque nos muestra las que están en mayúsculas y también las que están en minúsculas. Por eso en general, cuando los nombres no están estandarizados es preferible usar CONTAINING.

Esto sucede a menudo cuando son varias las personas encargadas de registrar los datos en una tabla. Algunos escriben todo en mayúsculas y algunos mezclan mayúsculas con minúsculas. Entonces, para asegurarnos que encontremos todos los datos buscados, sea que los hayan escrito en mayúsculas o en minúsculas debemos usar CONTAINING.

Artículo relacionado:

El índice del blog Firebird21