O que é um substituto adequado para o SQL como operador para aumentar o desempenho?

Question

Estou trabalhando em um aplicativo que é executado no Windows Mobile 6 que precisa recuperar todos os itens de uma tabela de itens que contêm uma determinada string (fornecida pelo usuário final) no campo Descrição do item. O problema é que existem aproximadamente 170.000 itens na tabela. Como preciso devolver todos os itens que contêm a string em qualquer lugar da descrição, sou forçado a usar uma string like %, o que elimina qualquer chance de usar o índice. Os dados e a estrutura da tabela são originalmente baseados em um banco de dados de progresso, que possui um operador maravilhoso contém em qualquer campo indexado por palavras. Este não é o caso em nosso aplicativo móvel, pois usa o SQL Server Compact 3.5.

Basicamente, meu DAL executa a consulta e recupera um SQLCedatarader e depois usa um itemFactory para criar um objeto de lista que contém apenas os itens correspondentes. Obviamente, isso nos permite manter nossos objetos de domínio/negócios separados da camada de acesso a dados.

Fine e Dandy, exceto os 8 e 42s necessários para recuperar itens quando procuro todos os itens que contêm algo como "golfe" na descrição. Obviamente, esse não é um período aceitável para o usuário final.

Minha primeira tentativa foi recuperar todos os itens de volta do banco de dados usando selecionar * do item "(com uma cláusula de ordem por um dos principais campos indexados). Nesse ponto, eu corri um índice de cheque enquanto corri pelo SQLCedataReader e tive O ItemFactory adiciona apenas itens ao objeto da lista se eles continham o texto de descrição solicitado. Isso melhorou a velocidade até 1m 46s. Não é muito ruim, mas ainda muito lento.

Tentei então outra abordagem que mostrou promessa ... quase ... enquanto o aplicativo inicia, tentei criar uma lista que continha todos os objetos do item no banco de dados (leva cerca de 2 minutos para executar a consulta e preencher a lista inteira, mas Pelo menos é apenas uma vez quando o aplicativo está inicializando ... ainda ... ugh). Depois que a lista estiver concluída, posso facilmente executar consultas nessa lista fazendo coisas como as seguintes (espero que minha sintaxe esteja certa ... Não estou no trabalho agora e não tenho Visual Studio no PC I estou sentado em):

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

Essa abordagem chegou a 21 anos. Muito bom (ainda lento no grande esquema das coisas). No entanto, o problema é que o uso da memória é muito grande se eu carregar todos os itens do banco de dados. Eu tive que realmente cortar os últimos 20.000 itens (para que o prazo dos 21s provavelmente teria sido mais como 25s) durante a carga inicial, porque uma parte do outOfMemoryException estava sendo jogada. De acordo com o gerente de memória no emulador, eu ainda tinha cerca de 20 MB de RAM livre, mas ouvi dizer que um processo só pode ter 32 MB ou RAM associado a ele (não tenho certeza se isso é verdade para o WM 6, mas parece assim).

Para ter certeza de que não era porque eu estava usando um objeto de lista para manter todos os itens (que eu estava instantando com a capacidade necessária em seu construtor para evitar redimensionamentos dinâmicos), o que eu também li pode causar uso extra de memória quando ele As chamadas de implicação são de segurança, tentei usar uma matriz de item [] (dimensionada com antecedência). Isso ainda tinha o problema da memória e a diferença de tamanho era insignificante.

Ok o suficiente divagando. Eu sei que provavelmente vou ter para que limite os registros retornados do banco de dados pelo DataReader (através de alguma pesquisa indexada em um tipo diferente de campo) e, em seguida, provavelmente usará o indexOF nesse subconjunto menor de itens para obter o máximo desempenho (pulando assim o operador semelhante todos juntos). Isso fará com que o usuário final tenha que inserir mais do que apenas uma pesquisa de descrição (talvez informações de hierarquia de itens para limitar qual tipo de itens a serem pesquisados).

Alguma ideia? Estou fazendo isso da maneira errada?

Obrigado por ouvir (desculpe, este post é longo, estou meio que pensando em voz alta).

Oh, eu deveria acrescentar (apenas em resumo) o que estou usando:

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

ATUALIZAÇÃO: Embora a abordagem do filtro Bloom mencionada abaixo pareça interessante, não pude atender a um requisito (que eu realmente não especifiquei acima). Eu realmente não posso combinar as palavras que estão contidas em outras palavras (por exemplo, "Club" não retornaria "clubes"). Devido a isso, fui forçado a usar uma abordagem completamente diferente (Kent Fredric ... obrigado por apontar isso). Marquei a resposta de Kent como a correta, já que a abordagem dele foi a que preencheu mais requisitos (Mitch, o seu tem um problema semelhante ao filtro Bloom sugerido por Jaunder). No entanto, fui uma abordagem diferente (por enquanto ...) do que o seu caminho também.

O que eu fiz foi puxado todos os objetos de itens na memória, com apenas números e descrições de itens (que o mantém sob as limitações da memória, no entanto, ainda causa uma inicialização mais longa do que eu gosto ... multithreading e carregando essas informações nos bastidores Enquanto o aplicativo está em execução pode cuidar disso, eu acho). Para realizar as pesquisas que escrevi, a minha contém rotina. A rotina é escrita em código C# não gerenciado que usa dois ponteiros e alguns loops para percorrer a descrição e o texto correspondente necessário. Se encontrar uma correspondência em qualquer lugar da descrição, adicionará o número do item a uma matriz. Depois que todos os itens forem pesquisados, uma nova consulta remonta ao banco de dados e agarra apenas os números de itens correspondentes (o que é muito rápido devido ao índice em um campo inteiro). Em seguida, esses itens são criados em uma lista com todas as informações (não apenas o número e a descrição do item). Toda a operação leva aproximadamente 5 a 10 segundos (dependendo da descrição), o que é bom o suficiente por enquanto.

Ainda vou otimizar ainda mais isso (pode ser capaz de rastrear quantos caracteres o termo de pesquisa é ... se houver menos caracteres restantes na descrição do item do que o texto necessário, o loop poderá continuar diretamente para o próximo item) .

Quaisquer sugestões ainda são bem -vindas. Por enquanto, marquei a resposta de Kent como "a mais correta" para minha pergunta.

Adereços para Dolch por me ajudar a escrever a rotina contém.

Answer 1

Eu votei em Mitch Wheat's Responder, mas existem alguns truques que eu também testaria para a eficácia.

Minha grande preocupação em ter uma mesa cheia de [char], [int] é que você ainda pode estar executando grandes volumes de comparações inúteis de string, especialmente se você usar % do Word % nesta nova tabela. (Entradas duplicadas, mas não correspondentes à pesquisa).

Eu provavelmente optaria por experimentar

Words
-----
chars  | word_id 

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

E veja se a sobrecarga do banco de dados é uma mitigação digna desse possível problema (não posso testar, desculpe)

Answer 2

Que tal o pré-processamento (uma vez) a tabela de itens (e cada nova entrada adicionada a ela precisaria ser processada), para criar uma tabela de ocorrência de palavras tendo

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

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

Itera sobre todos os seus itens, divida em palavras separadas e adicione entradas à tabela de ocasião conforme elas são encontradas.

Criar um índice em cluster no [Word] e entrar na tabela de itens no itemID deve ser rápido.

Answer 3

Você pode tentar usar um filtro Bloom.

1. Wikipedia
2. Usando filtros Bloom