Discussion :

[trucmuche2005]

Bonjour !

J'ai une liste formée par des "mots" qui sont des juxtapositions de lettres/chiffres (300 caractères au maximum dans un mot mais la plupart sont plutôt faits de 3 à 12 caractères). Cette liste contient probablement 200.000 ou 300.000 mots et est complétée peu à peu...

J'aimerais créer une table pour pouvoir faire des recherches dans cette liste de mots rapidement. La table n'aurait donc qu'une colonne (le mot), a priori.
Seulement, je n'ai aucune idée du temps nécessaire pour que MySQL fasse des recherches dans une base de données de cette taille. Et pour bien faire, il ne faudrait pas que cela prenne une seconde à chaque fois qu'on lance une recherche... Pensez-vous que cela puisse poser un problème ?

Le type de recherches que je souhaite faire dans cette table sont par exemple :

• trouver tous les mots de X caractères ;
• trouver tous les mots qui ont un caractère donné à une place donnée (avec le _)
• trouver tous les mots qui commencent/finissent par un/des caractère(s) donné(s) (avec le %).

Qu'en dites-vous ? Je fonce ou je devrais penser à quelque chose en particulier ?

La question est peut-être mal posée, trop vague, naïve... veuillez m'en excuser, je débute et je commence les réflexions... :-)

Trucmuche

[aieeeuuuuu]

Bonjour,

Un petit exemple de données aiderait à bien cerner le problème.
Vous donnez des "exemples" de recherche... est-ce que vous serez amené à d'autres types de recherches ?

Est-ce que le choix de MySQL est déjà définitif ? vous vous privez de certaines fonctionnalités qui pourraient vous être très utiles dans ce contexte, notamment les index sur des colonnes calculées ou sur des vues.

[trucmuche2005]

Bonjour ! et grand merci pour votre première réponse :-)

Les mots en question n'ont pas grand chose de régulier ni de compréhensible... C'est des juxtapositions de lettres et de chiffres, dans le désordre... Il n'y a pas de structure particulière... C'est donc des trucs du genre : "AABD", "AC4F5", "AFBGGF", "TGHZR5S", "4SFGT4X9", ...

Je n'ai donné que quelques exemples de recherches, mais je pense que les recherches les plus compliquées seraient par exemple de trouver tous les mots possédant entre 3 et 10 caractères avec un "A" à la 4e place, un "5" à la 6e place et se terminant/commençant par "GT".

Le choix de MySQL est relativement déterminé, je pense, car je vais être obligé d'utiliser ce qui est déjà installé sur mon serveur...

Merci encore pour votre aide !

[CinePhil]

Comme l'a dit aieeeuuuuu, avec MySQL, le seul index possible pour une chaîne de caractères est l'ordre alphabétique donc vos recherches portant sur le début du mot pourraient utiliser l'index mais pas les autres.

Une autre solution à étudier consisterait à découper chaque mot, via 3 tables.

mot -1,n----posseder(position)----0,n- lettre

te_mot_mot (mot_id, mot_mot)
te_lettre_let (let_id, let_lettre) => y compris les chiffres et éventuels autres caractères
tj_mot_posseder_let_mpl (mpl_lettre_id, mpl_position, mpl_mot_id)

trouver tous les mots possédant entre 3 et 10 caractères avec un "A" à la 4e place, un "5" à la 6e place et se terminant/commençant par "GT"

La requête pourrait être celle-ci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
SELECT DISTINCT m.mot
FROM te_mot_mot m
INNER JOIN tj_mot_posseder_let_mpl j1 ON j1.mpl_mot_id = m.mot_id
	INNER JOIN te_lettre_let l1 ON l1.let_id = j1.mpl_let_id
INNER JOIN tj_mot_posseder_let_mpl j2 ON j2.mpl_mot_id = m.mot_id
	INNER JOIN te_lettre_let l2 ON l2.let_id = j2.mpl_let_id
WHERE LENGTH(m.mot_mot) BETWEEN 3 AND 10
	AND m.mot_mot LIKE 'GT%'
	AND j1.mpl_position = 4
	AND l1.let_lettre = 'A'
	AND j2.mpl_position = 6
	AND l2.let_lettre = '5'

[trucmuche2005]

Salut à vous !

Grand merci pour vos conseils ! Bon... J'ai quelques difficultés à comprendre mais je vais m'y attacher... J'ai peu d'expérience en bases de données et les seules que j'ai manipulées étaient des simples tables MySQL avec quelques colonnes et des requêtes SELECT élémentaires...
Donc là, j'ai un peu de mal à comprendre ce que vous proposez comme stockage en 3 tables (mot -1,n----posseder(position)----0,n- lettre ??) : comment un mot donné doit être stocké dans chacune de ces tables, et vos trois notations te_mot_mot, te_lettre_let, tj_mot_posseder_let_mpl...

La requète, je ne vais pas m'y atteler tout de suite mais pour commencer, j'aimerais comprendre la structure des tables que vous proposez et le stockage des mots dans ces tables... Ensuite, j'y verrai sans doute beaucoup plus clair...

Est-ce que vous accepteriez de donner encore un peu de votre temps à m'expliquer ce que vous imaginez ? Ce serait vraiment super gentil... Ce problème m'intéresse beaucoup et je vais faire ce qu'il faut pour m'autonomiser un max... mais en attendant, j'ai besoin d'aide :-)

Grand merci encore !

[CinePhil]

mot -1,n----posseder(position)----0,n- lettre

Il s'agit d'un morceau de modèle conceptuel de données (MCD) de la méthode Merise.
Cela traduit la règle de gestion suivante :
- Un mot possède de 1 à plusieurs lettres et une lettre peut être possédée par plusieurs mots.

comment un mot donné doit être stocké dans chacune de ces tables

Pour mémoire, je redonne ici les trois tables proposées :

te_mot_mot (mot_id, mot_mot)
te_lettre_let (let_id, let_lettre) => y compris les chiffres et éventuels autres caractères
tj_mot_posseder_let_mpl (mpl_lettre_id, mpl_position, mpl_mot_id)

Dans la première, on stockera les mots, chacun étant associé à un identifiant unique de type entier. Pour reprendre vos exemples, on y trouvera les données suivantes :

mot_id, mot_mot
1, 'AABD'
2, 'AC4F5'
3, 'AFBGGF'
4, 'TGHZR5S'
5, '4SFGT4X9'

Dans la deuxième table, on trouvera toutes les lettres, chiffres et éventuels autre signes qui peuvent compsoer les mots de la première table :

let_id, let_lettre
1, 'A'
2, 'B'
3, 'C'
4, 'D'
...

Dans la troisième, on trouvera la composition des mots. Par exemple, pour le premier mot, 'AABD', il y aura les lignes suivantes :

mpl_lettre_id, mpl_position, mpl_mot_id
1, 1, 1 => Lettre n° 1 (A) en première position dans le premier mot
1, 2, 1 => Lettre n° 1 (A) en deuxième position dans le premier mot
2, 3, 1 => Lettre n° 2 (B) en troisième position dans le premier mot
4, 4, 1 => Lettre n° 4 (D) en quatrième position dans le premier mot

et vos trois notations te_mot_mot, te_lettre_let, tj_mot_posseder_let_mpl

C'est un standard de nommage, dérivé de celui proposé par SQLPro, que j'ai adopté. Vous pouvez avoir votre propore convention de nommage mais ce qu'il faut retenir est que les objets de la BDD (tables, colonnes) ne doivent pas avoir un nom faisant parti des mots réservés du langage SQL.

[trucmuche2005]

Wouw ! Super :-) J'ai compris et tout devient très clair :-) Génial !! Grand grand merci !!

Point de vue type de données,

• mot_id sera un 'unsigned int', auto incrémenté,
• mot_mot un 'vartext' L=255 ou un 'text' (je verrai si je dois obligatoirement dépasser les 255 caractères),
• let_lettre est un 'char', auto incrémenté,
• mpl_lettre_id, mpl_position, mpl_mot_id sont des 'unsigned int'

Mais au point de vue indexation, quelles colonnes dois-je indexer ? Je serais tenté d'indexer uniquement mpl_lettre_id, mpl_position et mpl_mot_id mais fais-je bien ?

Encore un tout tout grand merci !!

[CinePhil]

mot_mot un 'vartext' L=255 ou un 'text' (je verrai si je dois obligatoirement dépasser les 255 caractères),

Si possible, préférer le VARCHAR. L'indexation sur les colonnes TEXT est moins performante car obligatoirement limitée sur un nombre de caractères.
Voir la doc MySQL à ce sujet.

let_lettre est un 'char', auto incrémenté,

Non. Seule une colonne de type INTEGER peut être auto-incrémentée.

Mais au point de vue indexation, quelles colonnes dois-je indexer ?

Les clés primaires, bien sûr, c'est à dire les colonnes "mot_id", "let_id" et l'ensemble de colonnes {mpl_lettre_id, mpl_position, mpl_mot_id}. Cette indexation sera faite automatiquement par la déclaration de la clé primaire.
Les clés étrangères "mpl_position" et "mpl_mot_id" individuellement. La clé étrangère "mpl_lettre_id" n'a en principe pas besoin d'être indexée individuellement puisque c'est la première colonne de la clé primaire mais elle sera peut-être indexée automatiquement lors de la déclaration de la clé étrangère.
Les colonnes sur lesquelles se feront les recherches, c'est à dire :
- la colonne "let_lettre" mais comme la table sera petite, il est probable que cet index soit inutilisé par le SGBD. Il faudra examiner le plan d'exécution des requêtes pour s'en rendre compte et déterminer si on peut supprimer cet index ;
- la colonne "mot_mot" puisque vous aurez des recherches sur le début du mot.

D'une manière générale, vous trouverez chez SQLPro la réponse à la question, "Quoi indexer ?"

Comme je l'ai dit dans un précédent message, le manque de performance pourra se faire sentir lorsqu'il y aura une recherche sur la fin du mot.
2 solutions :
- ajouter une colonne mot_mot_inverse dans laquelle on stocke, comme son nom l'indique, le mot avec l'ordre des lettres inversées, ce qui permet de l'indexer mais cette fois sur la fin du mot ;
- utiliser la table associative en cherchant les lettres en dernières positions, la dernière position étant la longueur du mot (LENGTH).

[trucmuche2005]

Ah oui oui bien sûr pour le char non incrémenté : c'était une erreur de copier-coller :-)
Je vais me mettre maintenant au travail et je risque de revenir un jour vers vous si j'ai un problème, pratique, cette fois... :-)
Merci pour tous vos conseils et vos suggestions précieuses !!