Como pesquisar rapidamente em uma lista muito grande de strings / registros em um banco de dados

Eu tenho o seguinte problema: Eu tenho um banco de dados contendo mais de 2 milhões de registros. Cada registro possui um campo de string X e quero exibir uma lista de registros para os quais o campo X contém uma determinada string. Cada registro tem aproximadamente 500 bytes de tamanho.

Para torná-lo mais concreto: na GUI do meu aplicativo, tenho um campo de texto onde posso inserir uma string. Acima do campo de texto, tenho uma tabela exibindo os registros (primeiro N, por exemplo, 100) que correspondem à string no campo de texto. Quando digito ou excluo um caractere no campo de texto, o conteúdo da tabela deve ser atualizado rapidamente.

Gostaria de saber se existe uma maneira eficiente de fazer isso usando estruturas de índice apropriadas e / ou cache. Como explicado acima, só quero exibir os primeiros N itens que correspondem à consulta. Portanto, para N pequeno o suficiente, não deve ser um grande problema carregar os itens correspondentes do banco de dados. Além disso, o armazenamento em cache de itens na memória principal pode acelerar a recuperação.

Penso que o principal problema é encontrar rapidamente os itens correspondentes, dada a sequência de padrões. Posso confiar em alguns recursos do DBMS ou preciso criar algum índice na memória? Alguma ideia?

EDITAR

Eu fiz uma primeira experiência. Dividi os registros em diferentes arquivos de texto (no máximo 200 registros por arquivo) e os coloquei em diretórios diferentes (usei o conteúdo de um campo de dados para determinar a árvore de diretórios). Acabo com cerca de 50000 arquivos em cerca de 40000 diretórios. Em seguida, executei o Lucene para indexar os arquivos. Procurar uma string com o programa de demonstração Lucene é bastante rápido. A divisão e a indexação levaram alguns minutos: isso é totalmente aceitável para mim, porque é um conjunto de dados estático que eu quero consultar.

O próximo passo é integrar o Lucene no programa principal e usar os hits retornados pelo Lucene para carregar os registros relevantes na memória principal.

Em vez de colocar seus dados dentro do banco de dados, você pode mantê-los como um conjunto de documentos (arquivos de texto) separadamente e manter o link (caminho / URL, etc.) no banco de dados.

Isso é essencial porque, a consulta SQL por design será muito lenta, tanto na pesquisa por sub-string quanto na recuperação.

Agora, seu problema é formulado como, tendo que pesquisar os arquivos de texto que contêm o conjunto de seqüências de caracteres. Existem duas possibilidades aqui.

1. Correspondência de sub-string Se o seu texto blobs for uma única picada ou palavra (sem nenhum espaço em branco) e você precisar pesquisar uma sub-string arbitrária dentro dela. Nesses casos, você precisa analisar todos os arquivos para encontrar os melhores arquivos possíveis que correspondam. Um usa algoritmos como o algoritmo Boyer Moor. Veja isto e isto para detalhes. Isso também é equivalente ao grep - porque o grep usa coisas semelhantes por dentro. Mas você ainda pode fazer pelo menos mais de 100 grep (pior caso, 2 milhões) antes de retornar.

2. Pesquisa indexada. Aqui você assume que o texto contém um conjunto de palavras e a pesquisa é limitada a comprimentos fixos de palavras. Nesse caso, o documento é indexado em todas as ocorrências possíveis de palavras. Isso geralmente é chamado de "pesquisa de texto completo". Há um número de algoritmos para fazer isso e um número de projetos de código aberto que podem ser usados ​​diretamente. Muitos deles também suportam pesquisa de curingas, pesquisa aproximada etc. como abaixo:
   a. Apache Lucene: http://lucene.apache.org/java/docs/index.html
   b. OpenFTS: http://openfts.sourceforge.net/
   c. Sphinx http://sphinxsearch.com/

Provavelmente, se você precisar de "palavras fixas" como consultas, a abordagem dois será muito rápida e eficaz.

A tecnologia que você está procurando é a indexação de texto completo. A maioria dos RDBMS possui algum tipo de recursos internos que podem funcionar aqui, ou você pode usar algo como Lucene se quiser ficar mais sofisticado e / ou simplesmente executá-lo na memória.

Você já pensou em tentar ? Basicamente, você constrói uma árvore usando prefixos comuns, portanto, todas as palavras que começam com as mesmas letras são filhos do mesmo nó. Se você for dar suporte à correspondência em qualquer substring, precisará gerar algum tipo de índice permutado e criar sua tentativa a partir disso. No entanto, isso pode acabar expondo os requisitos de armazenamento.

Gostaria de acrescentar, além da resposta de Wyatt Barnett, que uma solução RDBMS com indexação de texto completo na coluna apropriada funcionará, mas se você desejar utilizar um cache local de registros buscados anteriormente, precisará de um plano para utilizar esses registros em cache para sua vantagem.

Uma opção é coletar os identificadores exclusivos desses registros que você EXPLICITAMENTE não deseja recuperar da consulta e incluí-los, possivelmente em um NOT INou em um NOT EXISTS.

Palavra de cautela, porém, usar NOT INou NOT EXISTStende a não ser barato e PODE influenciar negativamente o desempenho ou o plano de consultas, dependendo do mecanismo de banco de dados que você está utilizando. Execute um plano de explicação em sua consulta final para garantir que todos os seus índices nas colunas afetadas estejam sendo utilizados.

Também não custa fazer uma comparação de desempenho entre as duas abordagens para ver qual é mais rápida. Você pode se surpreender ao descobrir que manter um cache local e filtrar explicitamente os da sua consulta pode ter um desempenho pior do que uma consulta refinada que busca todos os registros.

Apenas no caso de você ter perdido. Se você usar o Lucene para o seu banco de dados, em vez da pesquisa de texto suportada no banco de dados, precisará ser extremamente cuidadoso ao fazer modificações no seu banco de dados. Como você se certifica de que pode ter atomicidade quando precisa fazer alterações nos recursos de banco de dados e externos (Lucene)? Sim, isso pode ser feito, mas haverá muito trabalho.

Em resumo, você está perdendo o suporte transacional do banco de dados se colocar o Lucene em seu esquema de dados.

Você já considerou Sphinx? http://sphinxsearch.com, se você puder usar uma ferramenta de terceiros, isso seria ideal para o que você está tentando alcançar, é muito mais eficiente na pesquisa de texto completo do que qualquer RDBMS que eu tenha usado pessoalmente.

É um tanto estranho que nenhuma das respostas tenha apresentado o termo "índice invertido" , a tecnologia subjacente a todas as soluções semelhantes ao Apache Lucene e outras.

O índice invertido é um mapeamento de palavras para documentos ("índice invertido no nível do registro") ou até locais de palavras precisos no documento ("índice invertido no nível da palavra").

As operações lógicas AND e OR são triviais para implementar. Se você tiver localizações precisas de palavras, é possível procurar por palavras adjacentes, possibilitando a pesquisa de frases.

Portanto, pense em um índice contendo (palavra, arquivo, local) tuplas. Quando você tem, por exemplo, ("invertido", "foo.txt", 123), basta verificar se ("índice", "foo.txt", 124) faz parte do índice para pesquisar a frase completa "índice invertido" .

Embora eu não esteja recomendando a reimplementação de um mecanismo de pesquisa de texto completo do zero, é útil saber como tecnologias como o Apache Lucene funcionam.

Portanto, minha recomendação é aprender como os índices invertidos funcionam e escolher uma tecnologia que os utilize como o Apache Lucene. Então você tem pelo menos uma sólida compreensão do que pode ser feito e do que não pode ser feito.