¿Qué 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 necesita para poder recuperar todos los elementos de una tabla de elementos que contienen una cadena determinada (proporcionada por el usuario final) en el campo de descripción del elemento. El problema es que hay aproximadamente 170,000 artículos en la tabla. Como necesito devolver todos los elementos que contienen la cadena en cualquier lugar de la descripción, me veo obligado a utilizar un LIKE% string%, que elimina cualquier posibilidad de utilizar el índice. La estructura de datos y tablas se basa originalmente en una base de datos Progress, que tiene un maravilloso operador contains en cualquier campo indexado por palabras. Este no es el caso en nuestra aplicación móvil, ya que usa SQL Server Compact 3.5.

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

Fino y elegante, a excepción de los 8m y 42s que se necesitan para recuperar elementos cuando busco todos los artículos que contienen algo así 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 utilizando SELECT * FROM Item "(con una cláusula order by en uno de los principales campos indexados). En este punto ejecuté una comprobación de IndexOf mientras corría SqlCeDataReader e ítemsFactory solo agregaron elementos al objeto List si contenían el texto de la descripción solicitada. Esto mejoró la velocidad a 1m 46s. No muy raído, pero aún demasiado lento.

Luego probé con otro enfoque que mostraba promesa ... casi ... Mientras la aplicación se inicia, traté de crear una lista que contuviera todos los objetos de los elementos dentro de la base de datos (toma aproximadamente 2 minutos ejecutar la consulta y completar la lista completa, pero al menos solo una vez como el la aplicación se está inicializando ... aún ... ugh). Una vez que la lista es completa ete, puedo ejecutar fácilmente consultas en esa lista haciendo cosas como las siguientes (espero que mi sintaxis sea correcta ... No estoy trabajando ahora y no tengo Visual Studio en la PC en la que estoy sentado):

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

Este enfoque lo bajó a 21s. Muy agradable (aún lento en el gran esquema de las cosas). Sin embargo, el problema es que el uso de memoria es demasiado grande si cargué todos los elementos de la base de datos. De hecho, tuve que cortar los últimos 20,000 elementos (por lo que el marco de tiempo 21 probablemente habría sido más como 25s) durante la carga inicial, porque se estaba lanzando 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 oído que un proceso solo puede tener 32 MB o RAM asociados (no estoy seguro de si eso es cierto para WM 6, pero parece que asi que).

Para asegurarse de que no era porque estaba utilizando un objeto List para contener todos los elementos (que estaba creando instancias con la capacidad necesaria en su constructor para evitar el cambio de tamaño dinámico), que también he leído puede causar extra uso de memoria cuando su implicidad llama a EnsureCapacity, traté de usar una matriz Item [] (dimensionada antes de tiempo). Esto todavía tenía el problema de memoria y la diferencia de tamaño era insignificante.

Ok, deambulando. Sé que es probable que tenga que limitar de algún modo los registros devueltos de la base de datos por el lector de datos (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 (tal vez información de jerarquía de elementos para limitar qué tipo de elementos buscar dentro).

¿Alguna idea? ¿Voy por esto de la manera incorrecta?

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

Oh debo añadir (al igual que en resumen) lo que estoy usando:

• Windows Mobile 6
• SQL Server Compact Edition 3.5
• C# 3,5

ACTUALIZACIÓN: Mientras el enfoque de Bloom Filter mencionado a continuación me pareció interesante, no pude cumplir con un requisito (que realmente no especifiqué más arriba). Realmente no puedo relacionar las palabras que están contenidas dentro de otras palabras (por ejemplo, "club" no devolvería "clubes"). Debido a esto, me vi obligado a utilizar un enfoque diferente por completo (Kent Fredric ... gracias por señalar esto). Marqué la respuesta de Kent como la correcta, ya que su enfoque fue el que cumplió con la mayoría de los requisitos (Mitch, tu problema es similar al que sugiere el filtro Bloom sugerido por Jaunder). Sin embargo, he adoptado un enfoque diferente (por ahora ...) que su manera también.

Lo que he hecho es extraer todos los objetos de elementos en la memoria, con solo números de elementos y descripciones (lo cual mantiene las limitaciones de memoria, pero aún así causa una inicialización más larga que la que me gusta ... multithreading y cargando la información detrás de la escena mientras la aplicación se está ejecutando puede ocuparse de eso, supongo). Para realizar las búsquedas que he escrito, el mío contiene la rutina. La rutina está escrita en código C# no administrado que usa dos punteros y un par de bucles para recorrer la descripción y el texto correspondiente. Si encuentra una coincidencia en cualquier parte de la descripción, agrega el número de elemento a una matriz. Una vez que se han buscado todos los elementos, una nueva consulta regresa a la base de datos y toma solo los números de elementos coincidentes (lo cual es muy rápido debido al índice en un campo entero). Luego, esos elementos se crean en una lista con toda la información (no solo el número de artículo y la descripción). Toda la operación demora aproximadamente de 5 a 10 segundos (según la descripción), lo cual es suficiente por ahora.

Seguiré buscando optimizar aún más esto (podría ser capaz de rastrear cuántos caracteres es el término de búsqueda ... si quedan menos caracteres en la descripción del artículo que el texto requerido, el ciclo podría continuar directamente 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.

Apoyos a Dolch por ayudarme a escribir la rutina contains.

Answer 1

He votado por Mitch Wheat's respuesta, pero hay algunos trucos que también probaría para comprobar su efectividad.

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

probablemente optar por experimeting con

Words 
----- 
chars | word_id 

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

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

Answer 2

¿Qué hay de pre-procesamiento (una vez) la tabla de artículos (y cada nueva entrada agregado a él tendría que ser procesado), para crear una tabla de palabras ocurrencia tener

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

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

iterar sobre todos sus artículos, dividir en palabras separadas y agregar entradas a la tabla de eventos a medida que se encuentran.

Crear un índice agrupado en [Word] y unirse a la tabla Item en ItemId debe ser rápido.

Answer 3

Usted podría tratar de usar un filtro de floración .

1. wikipedia
2. using bloom filters