Comment rechercher rapidement dans une très grande liste de chaînes / enregistrements dans une base de données

32

J'ai le problème suivant: J'ai une base de données contenant plus de 2 millions d'enregistrements. Chaque enregistrement a un champ de chaîne X et je veux afficher une liste des enregistrements pour lesquels le champ X contient une certaine chaîne. Chaque enregistrement a une taille d'environ 500 octets.

Pour le rendre plus concret: dans l'interface graphique de mon application, j'ai un champ de texte où je peux entrer une chaîne. Au-dessus du champ de texte, j'ai un tableau affichant les (premiers N, par exemple 100) enregistrements qui correspondent à la chaîne dans le champ de texte. Lorsque je tape ou supprime un caractère dans le champ de texte, le contenu du tableau doit être mis à jour à la volée.

Je me demande s'il existe un moyen efficace de le faire en utilisant des structures d'index appropriées et / ou la mise en cache. Comme expliqué ci-dessus, je souhaite uniquement afficher les N premiers éléments qui correspondent à la requête. Par conséquent, pour N suffisamment petit, cela ne devrait pas être un gros problème de chargement des éléments correspondants à partir de la base de données. En outre, la mise en cache des éléments dans la mémoire principale peut accélérer la récupération.

Je pense que le principal problème est de trouver rapidement les éléments correspondants, compte tenu de la chaîne de modèle. Puis-je compter sur certaines fonctionnalités du SGBD ou dois-je créer moi-même un index en mémoire? Des idées?

MODIFIER

J'ai exécuté une première expérience. J'ai divisé les enregistrements en différents fichiers texte (au plus 200 enregistrements par fichier) et placé les fichiers dans différents répertoires (j'ai utilisé le contenu d'un champ de données pour déterminer l'arborescence des répertoires). Je me retrouve avec environ 50000 fichiers dans environ 40000 répertoires. J'ai ensuite exécuté Lucene pour indexer les fichiers. La recherche d'une chaîne avec le programme de démonstration Lucene est assez rapide. Le fractionnement et l'indexation ont pris quelques minutes: c'est tout à fait acceptable pour moi car c'est un ensemble de données statiques que je souhaite interroger.

L'étape suivante consiste à intégrer Lucene dans le programme principal et à utiliser les hits renvoyés par Lucene pour charger les enregistrements pertinents dans la mémoire principale.

database algorithms data-structures indexing Giorgio
la source
2
2 millions d'enregistrements * 500 octets = 1 Go de données. C'est beaucoup de données à rechercher, quelle que soit la manière dont vous vous y prenez - chaque valeur de X est-elle susceptible d'être unique, ou aurez-vous de nombreux enregistrements avec la même valeur de X?
1
Ce serait également beaucoup de données à essayer de stocker en mémoire en tant que cache pour une récupération rapide. Cela équivaudrait à plus de 1 Go par session utilisateur.
maple_shaft
Mon commentaire précédent suppose une application Web. S'agit-il d'une application Web?
maple_shaft
Il s'agit d'une application de bureau. Les valeurs dans les enregistrements ne sont pas nécessairement uniques. En outre, je recherche une sous-chaîne et non une correspondance exacte.
Giorgio
@maple_shaft: Je ne mettrais en cache que les enregistrements auxquels j'ai accédé récemment. Si je change la chaîne de requête et qu'un enregistrement correspond toujours, il est toujours dans le cache.
Giorgio

Réponses:

20

Au lieu de mettre vos données à l'intérieur de la base de données, vous pouvez les conserver en tant qu'ensemble de documents (fichiers texte) séparément et conserver le lien (chemin / URL, etc.) dans la base de données.

Ceci est essentiel car, par conception, la requête SQL sera très lente à la fois dans la recherche de sous-chaîne et la récupération.

Maintenant, votre problème est formulé comme: avoir à rechercher les fichiers texte qui contiennent l'ensemble de chaînes. Il y a deux possibilités ici.

  1. Correspondance de sous-chaîne Si vos taches de texte sont une seule piqûre ou un seul mot (sans espace blanc) et que vous devez rechercher une sous-chaîne arbitraire à l'intérieur. Dans de tels cas, vous devez analyser chaque fichier pour trouver les meilleurs fichiers possibles qui correspondent. On utilise des algorithmes comme l'algorithme de Boyer Moor. Voir ceci et cela pour plus de détails. Ceci est également équivalent à grep - car grep utilise des éléments similaires à l'intérieur. Mais vous pouvez toujours faire au moins 100+ grep (pire cas 2 millions) avant de revenir.

  2. Recherche indexée. Ici, vous supposez que le texte contient un ensemble de mots et que la recherche est limitée à des longueurs de mot fixes. Dans ce cas, le document est indexé sur toutes les occurrences possibles de mots. Ceci est souvent appelé «recherche de texte intégral». Il existe un certain nombre d'algorithmes pour ce faire et un certain nombre de projets open source qui peuvent être utilisés directement. Beaucoup d'entre eux prennent également en charge la recherche générique, la recherche approximative, etc. comme ci-dessous:
    a. Apache Lucene: http://lucene.apache.org/java/docs/index.html
    b. OpenFTS: http://openfts.sourceforge.net/
    c. Sphinx http://sphinxsearch.com/

Très probablement, si vous avez besoin de "mots fixes" comme requêtes, l'approche deux sera très rapide et efficace.

Dipan Mehta
la source
2
Il s'agit d'un concept intéressant, mais il semble peu probable qu'un développeur puisse facilement rechercher dans 1 Go de données textuelles plus rapidement et plus efficacement qu'un moteur de base de données. Des gens beaucoup plus intelligents que vous et moi avons travaillé sur des optimiseurs de requête pour faire exactement cela et il est un peu naïf de penser que vous pouvez le faire plus efficacement.
maple_shaft
4
@maple_shaft Les exemples que j'ai donnés ne sont pas des moteurs de base de données SGBDR. Ils ressemblent plus à des "moteurs de recherche" si vous voulez l'appeler. Il existe une énorme différence conceptuelle entre la récupération d'une liste dans un index (ou une table de hachage) et la recherche dans 1 Go de données à chaque fois qu'une requête se déclenche. Donc ce que je suggère n'est pas un petit ajustement.
Dipan Mehta
Cela semble une idée intéressante, mais je me demande comment cela fonctionnerait. J'aurais plus de 2 000 000 de fichiers, chacun d'environ un demi-kilo-octet. Ou proposez-vous d'avoir plus d'un enregistrement par fichier? Quelle serait la différence avec une base de données?
Giorgio
Je ne suis pas convaincu que cela fonctionnerait nécessairement mieux que, disons, l'index de texte intégral SQL.
Kirk Broadhurst
@Giorgio - oui, c'est ainsi que les moteurs de recherche en texte intégral fonctionneraient. La principale différence ici est une page pré-indexée par rapport à la recherche en mémoire (à nouveau à chaque fois qu'une requête arrive).
Dipan Mehta
21

La technologie que vous recherchez est l'indexation de texte intégral. La plupart des SGBDR ont une sorte de capacités intégrées qui pourraient fonctionner ici, ou vous pouvez utiliser quelque chose comme Lucene si vous voulez devenir plus sophistiqué et / ou simplement l'exécuter en mémoire.

Wyatt Barnett
la source
1
À mon avis, les options de texte intégral dans n'importe quel SGBDR sont une solution de contournement pour lui faire faire quelque chose pour lequel il n'est pas conçu: "rechercher dans une pile de données non structurées non liées". Si vous construisez un moteur de recherche, vous n'utilisez simplement pas un SGBDR. Cela peut fonctionner pour de petits ensembles de données mais lakcs toute sorte de mise à l'échelle. La recherche parmi des tas de données non structurées n'est pas un clou, alors n'utilisez pas de marteau. Utilisez le bon outil pour le travail.
Pieter B
8

Avez-vous envisagé un trie ? Fondamentalement, vous créez une arborescence en utilisant des préfixes communs, donc tous les mots qui commencent par les mêmes lettres sont des enfants du même nœud. Si vous voulez prendre en charge la correspondance sur n'importe quelle sous-chaîne, vous devrez générer une sorte d' index permuté et construire votre trie à partir de cela. Cela peut finir par faire exploser vos besoins de stockage.

RGT
la source
1
OUI! Je pensais à une structure arborescente et je me suis souvenu qu'il y avait quelque chose de similaire qui pourrait me convenir, mais je ne me souvenais pas des trios car je ne les ai jamais utilisés. Concernant l'exigence de stockage: rappelez-vous que je n'ai besoin de récupérer que les N premières entrées (par exemple N = 100) car cela n'a aucun sens de remplir une table avec 20000 hits. Ainsi, chaque nœud du trie pointerait vers au plus N entrées. De plus, j'ai oublié de mentionner que j'ai besoin d'un accès rapide mais je n'ai pas besoin d'une mise à jour rapide, car les données ne sont chargées qu'une seule fois. L'idée de trie sur un index permuté pourrait vraiment fonctionner!
Giorgio
1
Bonne réponse, mais comme vous le constatez, un trie est idéal pour faire correspondre le début de vos mots, mais deviendra rapidement complexe et très volumineux s'il correspond à une sous-chaîne ...
Kirk Broadhurst
Comme première expérience, j'ai essayé de construire l'ensemble de toutes les sous-chaînes apparaissant dans les chaînes que je dois rechercher qui, si je comprends bien, correspondent aux chemins du trie. J'ai eu une exception de mémoire insuffisante (avec 256 Mo de tas pour la JVM) à des sous-chaînes de longueur 6. Je crains donc que cette solution ne soit pas possible, sauf si je fais quelque chose de mal.
Giorgio
5

Je voudrais ajouter en plus de la réponse de Wyatt Barnett qu'une solution SGBDR avec indexation en texte intégral sur la colonne appropriée fonctionnera, mais si vous souhaitez utiliser un cache local d'enregistrements précédemment récupérés, vous devez planifier pour utiliser ces enregistrements en cache à votre avantage.

Une option consiste à collecter les identifiants uniques de ces enregistrements que vous ne souhaitez EXPLICITEMENT pas extraire de la requête et les inclure, éventuellement dans un NOT INou un NOT EXISTS.

Un mot d'avertissement cependant, l'utilisation NOT INou a NOT EXISTStendance à ne pas être bon marché et PEUT influencer négativement les performances de votre requête ou votre plan de requête en fonction du moteur de base de données que vous utilisez. Exécutez un plan d'explication sur votre requête finale pour vous assurer que tous vos index sur les colonnes affectées sont utilisés.

Cela ne fait pas de mal non plus de faire une comparaison des performances entre les deux approches pour voir laquelle est plus rapide. Vous serez peut-être surpris de découvrir que le maintien d'un cache local et le filtrage explicite de ceux de votre requête peuvent avoir de moins bonnes performances qu'une requête finement réglée qui récupère tous les enregistrements.

arbre_érable
la source
maple_shaft et @Wyatt Barnett: Merci beaucoup pour les suggestions. Je vais devoir faire quelques lectures et essayer différentes solutions. Toutes les bases de données ne prennent pas en charge l'indexation complète, MySQL (que j'utilise actuellement) le fait ( dev.mysql.com/doc/refman/5.5/en/fulltext-search.html ). Je vais essayer de faire quelques tests, puis je ferai rapport ici.
Giorgio
2

Juste au cas où vous l'auriez manqué. Si vous utilisez Lucene pour votre base de données au lieu de la recherche de texte prise en charge dans la base de données, vous devrez être extrêmement prudent lors de la modification de votre base de données. Comment vous assurez-vous que vous pouvez avoir l'atomicité lorsque vous devez apporter des modifications à la fois à la base de données et aux ressources externes (Lucene)? Oui, cela peut être fait, mais il y aura beaucoup de travail.

En bref, vous perdez le support transactionnel DB si vous mettez Lucene dans votre schéma de données.

InforméA
la source
1
Le problème, comme indiqué, ne semble de toute façon pas convenir à un SGBD.
Pieter B
1

Avez-vous pensé au Sphinx? http://sphinxsearch.com si vous pouvez utiliser un outil tiers, ce serait idéal pour ce que vous essayez de réaliser, c'est beaucoup plus efficace pour la recherche en texte intégral que n'importe quel SGBDR que j'ai personnellement utilisé.

brindille
la source
3
et le vote vers le bas est pour?
twigg
1

Il est quelque peu étrange qu'aucune des réponses ne présente le terme «indice inversé» , la technologie sous-jacente à toutes les solutions similaires à Apache Lucene et à d'autres.

L'index inversé est un mappage des mots aux documents ("index inversé au niveau de l'enregistrement") ou même des emplacements de mots précis dans le document ("index inversé au niveau du mot").

Les opérations logiques ET et OU sont triviales à implémenter. Si vous avez des emplacements de mots précis, il est possible de rechercher des mots adjacents, ce qui rend possible la recherche de phrases.

Pensez donc à un index contenant (mot, fichier, emplacement) des tuples. Lorsque vous avez par exemple ("inversé", "foo.txt", 123), vous vérifiez simplement si ("index", "foo.txt", 124) fait partie de l'index pour rechercher la phrase complète "index inversé" .

Bien que je ne vous recommande pas de réimplémenter un moteur de recherche de texte intégral à partir de zéro, il est utile de savoir comment fonctionnent des technologies telles qu'Apache Lucene.

Donc, ma recommandation est d'apprendre comment fonctionnent les index inversés et de choisir une technologie qui les utilise comme Apache Lucene. Ensuite, vous avez au moins une solide compréhension de ce qui peut être fait et de ce qui ne peut pas être fait.

juhist
la source