Come cercare rapidamente un elenco molto grande di stringhe / record su un database

Invece di mettere i tuoi dati all'interno del DB, puoi tenerli come un insieme di documenti (file di testo) separatamente e mantenere il collegamento (percorso / url ecc.) nel DB.

Questo è essenziale perché, la query SQL per progettazione sarà molto lenta sia nella ricerca sottostringa che nel recupero.

Ora, il tuo problema è formulato come, dovendo cercare nei file di testo che contengono l'insieme di stringhe. Ci sono due possibilità qui.

1. Corrispondenza sottostringa Se i tuoi BLOB di testo sono una singola puntura o parola (senza spazi bianchi) e devi cercare una sottostringa arbitraria al suo interno. In questi casi è necessario analizzare ogni file per trovare i migliori file possibili corrispondenti. Uno utilizza algoritmi come l'algoritmo di Boyer Moor. Vedi questo e questo per i dettagli. Questo è anche equivalente a grep - perché grep usa cose simili dentro. Ma puoi ancora fare almeno 100+ grep (caso peggiore 2 milioni) prima di tornare.

2. Ricerca indicizzata. Qui si presuppone che il testo contenga un insieme di parole e la ricerca sia limitata a lunghezze di parole fisse. In questo caso, il documento viene indicizzato su tutte le possibili occorrenze di parole. Questo è spesso chiamato "ricerca a tutto testo". Ci sono un numero di algoritmi per fare questo e un numero di progetti open source che possono essere usati direttamente. Molti di essi supportano anche la ricerca con caratteri jolly, la ricerca approssimativa ecc. Come di seguito:
   un. Apache Lucene: link
   b. OpenFTS: link
   c. Sfinge link

Molto probabilmente se hai bisogno di "parole fisse" come query, l'approccio due sarà molto veloce ed efficace.

La tecnologia che stai cercando è l'indicizzazione full-text. La maggior parte degli RDBMS ha una sorta di funzionalità incorporate che potrebbero funzionare qui, oppure potresti usare qualcosa come Lucene se volessi diventare fancier e / o semplicemente eseguirlo in memoria.

Hai considerato un trie ? Fondamentalmente si costruisce un albero usando prefissi comuni, quindi tutte le parole che iniziano con le stesse lettere sono figli dello stesso nodo. Se vuoi supportare la corrispondenza su qualsiasi sottostringa, dovrai generare una sorta di indice permutato e costruire il tuo trie da quello. Ciò potrebbe tuttavia far svanire i tuoi requisiti di archiviazione.

Vorrei aggiungere la risposta di Wyatt Barnett che una soluzione RDBMS con indicizzazione full-text sulla colonna appropriata funzionerà, ma se si desidera utilizzare una cache locale di record precedentemente recuperati, è necessario un piano per utilizzare questi record nella cache a tuo vantaggio.

Un'opzione consiste nel raccogliere gli identificatori univoci di questi record che ESPLICITAMENTE non vuoi recuperare dalla query e includerli, possibilmente in NOT IN o NOT EXISTS .

Tuttavia, la cautela, usando NOT IN o NOT EXISTS tende a non essere a buon mercato e MAG può influenzare negativamente le prestazioni della query o il piano di query a seconda del motore di database che si sta utilizzando. Esegui un piano di spiegazioni sulla tua query finale per assicurarti che tutti gli indici sulle colonne interessate vengano utilizzati.

Inoltre non fa male fare un confronto delle prestazioni tra i due approcci per vedere quale è più veloce. Potresti essere sorpreso di scoprire che mantenere una cache locale e filtrare esplicitamente quelli della tua query potrebbe avere prestazioni peggiori di una query finemente sintonizzata che recupera tutti i record.

Nel caso lo avessi perso. Se si utilizza Lucene per il database anziché la ricerca di testo supportata dal DB, sarà necessario prestare estrema attenzione quando si apportano modifiche al DB. Come ti assicuri di poter avere atomicità quando devi apportare modifiche sia al DB che alle risorse esterne (Lucene)? Sì, si può fare, ma ci sarà molto lavoro.

In breve, stai perdendo il supporto transazionale DB se inserisci Lucene nello schema dati.

È piuttosto strano che nessuna delle risposte abbia presentato il termine "indice invertito" , la tecnologia alla base di tutte le soluzioni simili ad Apache Lucene e ad altri.

L'indice invertito è una mappatura da parole a documenti ("indice invertito a livello di record") o persino posizioni di parole precise all'interno del documento ("indice invertito a livello di parola").

Le operazioni logiche AND e OR sono banali da implementare. Se hai posizioni di parole precise, è possibile cercare parole adiacenti, rendendo così possibile la ricerca di frasi.

Quindi, pensa a un indice contenente tuple (parola, file, posizione). Quando hai, ad es. ("inverted", "foo.txt", 123) quindi basta controllare se ("index", "foo.txt", 124) fa parte dell'indice per cercare la frase completa "index invertito".

Anche se non ti sto raccomandando di reimplementare un motore di ricerca full-text da zero, è utile sapere come funzionano le tecnologie come Apache Lucene.

Quindi, la mia raccomandazione è di imparare come funzionano gli indici invertiti e scegliere una tecnologia che li utilizza come Apache Lucene. Allora almeno hai una solida comprensione di cosa si può fare e cosa non si può fare.

Hai considerato la Sfinge? link se puoi utilizzare uno strumento di terze parti, questo sarebbe l'ideale per ciò che stai cercando di ottenere, è molto più efficiente nella ricerca testuale di qualsiasi altro RDBMS che ho usato personalmente.