¿Cuál es un reemplazo adecuado para el operador SQL Like para aumentar el rendimiento?

Question

Estoy trabajando en una aplicación que se ejecuta en Windows Mobile 6 que debe poder recuperar todos los elementos de una tabla de elementos que contienen una cadena dada (proporcionada por el usuario final) dentro del campo de descripción del elemento. El problema es que hay aproximadamente 170,000 artículos en la tabla. Dado que debo devolver todos los elementos que contienen la cadena en cualquier lugar dentro de la descripción, me veo obligado a usar una cadena% LIKE, lo que elimina cualquier posibilidad de usar el índice. Los datos y la estructura de la tabla se basan originalmente en una base de datos de Progress, que tiene un maravilloso operador de contenidos en cualquier campo indexado por palabra. Este no es el caso de nuestra aplicación móvil, ya que utiliza SQL Server Compact 3.5.

Básicamente, mi DAL ejecuta la consulta y recupera un SqlCeDataReader y luego usa un ItemFactory para crear un objeto de lista que contiene solo los elementos coincidentes. Obviamente, esto nos permite mantener nuestros objetos de dominio / negocio separados de la capa de acceso a datos.

Fino y elegante, excepto los 8m y 42s que se necesitan para recuperar elementos cuando busco todos los elementos que contienen algo como " golf " en la descripción. Obviamente, este no es un marco de tiempo aceptable para el usuario final.

Mi primer intento fue recuperar todos los elementos de la base de datos usando SELECT * FROM Item " (con una cláusula orden por en uno de los principales campos indexados). En este punto ejecuté una comprobación IndexOf mientras corría a través del SqlCeDataReader y el ItemFactory solo agregaba elementos al objeto de la Lista si contenían el texto de la descripción solicitada. Esto mejoró la velocidad hasta 1m 46s. No está mal, pero sigue siendo demasiado lento.

Luego probé otro enfoque que parecía prometedor ... casi ... Mientras se inicia la aplicación, intenté crear una Lista que contenía todos los objetos del elemento dentro de la base de datos (toma aproximadamente 2 minutos ejecutar la consulta y rellenar todo el lista, pero al menos es solo una vez ya que la aplicación se está inicializando ... todavía ... ugh). Una vez que la lista está completa, puedo realizar consultas fácilmente en esa lista haciendo cosas como las siguientes (espero que mi sintaxis sea la correcta ... No estoy trabajando ahora y no tengo Visual Studio en la computadora). estoy sentado en):

List<Item> specificItems = 
    AllItems.FindAll(i => i.Description.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >= 0);

Este enfoque lo derribó a 21s. Muy bonito (aunque lento en el gran esquema de las cosas). Sin embargo, el problema es que el uso de la memoria es demasiado grande si carga todos los elementos de la base de datos. En realidad, tuve que cortar los últimos 20,000 elementos (por lo que el marco de tiempo de los 21 probablemente habría sido más como 25) durante la carga inicial, porque se emitió una excepción OutOfMemoryException. De acuerdo con el administrador de memoria en el emulador, todavía tenía unos 20 MB de RAM libre, pero he escuchado que un proceso solo puede tener 32 MB o RAM asociados (no estoy seguro si eso es cierto para WM 6, pero parece que así).

Para asegurarme de que no fuera porque estaba usando un objeto de Lista para contener todos los elementos (que estaba creando una instancia con la capacidad necesaria en su constructor para evitar el cambio de tamaño dinámico), que también he leído puede causar memoria adicional uso cuando implícitamente llama a VerifyCapacity, intenté usar una matriz Item [] (dimensionada antes de tiempo). Esto todavía tenía el problema de la memoria y la diferencia de tamaño era insignificante.

Muy bien divagando. Sé que es probable que tenga que limitar de alguna manera los registros devueltos por el datareader (a través de una búsqueda indexada en un tipo diferente de campo) y luego usaré IndexOf en ese subconjunto más pequeño de elementos para obtener el máximo rendimiento. (omitiendo así el operador Like todos juntos). Esto hará que el usuario final tenga que ingresar más que solo una búsqueda de descripción (aunque quizás la información de la jerarquía de elementos limite el tipo de elementos para buscar).

¿Alguna idea? ¿Estoy yendo por esto de manera incorrecta?

Gracias por escuchar (lo siento, esta publicación es larga, estoy pensando en voz alta).

Oh, debo agregar (solo en resumen) lo que estoy usando:

• Windows Mobile 6
• Sql Server Compact Edition 3.5
• C # 3.5

ACTUALIZACIÓN: Si bien el enfoque de Bloom Filter mencionado a continuación parecía interesante, no pude cumplir un requisito (que no especifiqué anteriormente). Realmente no puedo hacer coincidir las palabras que están contenidas dentro de otras palabras (por ejemplo, " club " no devolvería " clubs "). Debido a esto, me vi obligado a utilizar un enfoque completamente diferente (Kent Fredric ... gracias por señalarlo). He marcado la respuesta de Kent como la correcta, ya que su enfoque fue el que llenó la mayoría de los requisitos (Mitch, usted tuvo un problema similar al del filtro Bloom sugerido por Jaunder). Sin embargo, también he seguido un enfoque diferente (por ahora ...) que él.

Lo que he hecho es sacar todos los objetos de los elementos en la memoria, con solo los números de los elementos y las descripciones (lo cual lo mantiene bajo las limitaciones de la memoria, sin embargo, todavía causa una inicialización más larga de lo que me gusta ... multihilo y carga esa información detrás de las escenas mientras la aplicación se está ejecutando puede hacerse cargo de eso, supongo). Para realizar las búsquedas que he escrito mi propia rutina contiene. La rutina está escrita en código c # no administrado que utiliza dos punteros y un par de bucles para ejecutar la descripción y el texto coincidente requerido. Si encuentra una coincidencia en cualquier lugar de la descripción, agrega el número de artículo a una matriz. Una vez que se han buscado todos los elementos, una nueva consulta regresa a la base de datos y captura solo los números de elementos coincidentes (lo cual es muy rápido debido al índice en un campo entero). Luego, esos artículos se crean en una Lista con toda la información (no solo el número y la descripción del artículo). Toda la operación toma aproximadamente de 5 a 10 segundos (según la descripción), lo que es suficiente por ahora.

Seguiré analizando la optimización de esto (podría rastrear cuántos caracteres contiene el término de búsqueda ... si quedan menos caracteres en la descripción del elemento que el texto requerido, el bucle podría continuar hasta el siguiente artículo).

Cualquier sugerencia es bienvenida. Por ahora, he marcado la respuesta de Kent como " la más correcta " para mi pregunta.

Props to Dolch por ayudarme a escribir la rutina de contenidos.

Answer 1

He votado por Respuesta de Mitch Wheat , pero hay algunos trucos que también probaría para determinar su efectividad.

Mi gran preocupación acerca de tener una tabla llena de [char], [int] es que aún puede ejecutar grandes volúmenes de comparaciones de cadenas sin sentido, especialmente si usa% word% en esta nueva tabla. (Entradas duplicadas pero que no coinciden con nuestra búsqueda).

Probablemente optaría por experimentar con

Words
-----
chars  | word_id 

WordsToEntry
------------
word_id | entry_id 

y vea si la sobrecarga de la base de datos es una mitigación digna de este posible problema (no puedo realizar la prueba, lo siento)

Answer 2

¿Qué hay de preprocesar (una vez) la tabla de elementos (y cada nueva entrada agregada a ella tendría que procesarse), para crear una tabla de ocurrencia de palabras que tenga

CREATE TABLE WordItemOccurance
(
    [Word] varchar(50) not null,

    ItemId int not null
        constraint FK_Items references ItemTable(ID)
)

Iterice sobre todos sus elementos, divida en palabras separadas y agregue entradas a la tabla de ocurrencias a medida que se encuentren.

La creación de un índice agrupado en [Word] y la unión a la tabla de elementos en ItemId debería ser rápida.

Answer 3

Puedes intentar usar un filtro de floración.

1. wikipedia
2. utilizando bloom filtros