Discussion :

[lvr]

Bonjour,

J'ai besoin de vos lumières pour me conseiller sur l'algoritme suivant que j'ai écrit.
Je développe une petite application personnelle pour indexer des samples musicaux sur mon PC. Ces samples sont indexés par des tags. Et j'aimerais pouvoir rechercher sur les tags et donner un pourcentage de correspondance. J'ai aussi installé un système de "similarité", exemple: "tuba" est similaire à "trompette" à 90%.

Le principe de base est la construction d'une hash qui représente les tags d'un sample. Cette hash est une String où je concatène les id des tags sur trois positions (voir ci-dessous). C'est pas optimal et pourra être peaufiné plus tard.

Je travaille sur deux temps:

- une partie statique: quand je modifie les tags d'un sample, je re-calcule toutes les combinaisons possibles de ces tags et en calcule les hash. Et je stocke ces hash.

- une partie dynamique:
1) quand l'utilisateur indique les tags sur lesquels il veut chercher, je re-calcule toutes les combinaisons de ces tags en y ajoutant les tags similaires et j'associe un pourcentage de correspondance par rapport aux tags demandés. Je mets tout ça dans une table temporaire.
Ex: si la recherche est sur "stéréo+trompette", "stéréo" seul correspond à 50% à la recherche,"stéréo+trompette" correspond à 100%, "stéréo+tuba" correspond à 95%.
2) je fais un query entre les hash des samples et mes hash de recherche en ne gardant pour chaque sample trouvé que le max du pourcentage.

Cet algorithme fonctionne. Je l'ai testé sur une petite db, mais je demande si à votre avis il est viable sur une plus grosse db et quelles précuations je dois prendre dans mon query, dans mes index.

Une grosse db c'est 500 samples avec une moyenne de 10 tags. La table des sampleshash avoisinerait les 500.000 entrées.
Une recherche normale c'est 3 tags, avec chacun deux similarités. Donc 9 tags. La table temporaire des searchhash avoisine les 180 entrées.

Le query est:

Code :

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

1
2
3
select sample.id, sample.name, sample.duration, sample.path, max(searchhash.pourcentage) from sample, samplehash, searchhash
where (sample.id=samplehash.sampleid) and (samplehash.hash=searchhash.hash)
group by sample.id

Là où je vois où ça peut ne pas être efficace:
- un join entre les samplehash et les searchhash sur les hash qui sont des varchars.
- le groupby sampleid avec un max(pourcentage)

J'utilise comme db H2.

Voilà, vous pensez quoi de tout ceci ? Quels sont les index que je dois prévoir ?

[CinePhil]

Ta requête, réécrite ci-dessous avec la syntaxe normalisée depuis 1992 pour les jointures, ne semble pas très complexe.
J'y ai aussi ajouté dans le GROUP BY toutes les colonnes du SELECT ne faisant pas l'objet d'une fonction de calcul.

Code :

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

1
2
3
4
5
6
SELECT sample.id, sample.name, sample.duration, sample.path, 
  MAX(searchhash.pourcentage) AS pourcentage_max
FROM sample
INNER JOIN samplehash ON sample.id=samplehash.sampleid
INNER JOIN searchhash ON samplehash.hash=searchhash.hash
GROUP BY sample.id, sample.name, sample.duration, sample.path

Là où je vois où ça peut ne pas être efficace:
- un join entre les samplehash et les searchhash sur les hash qui sont des varchars.
- le groupby sampleid avec un max(pourcentage)

Effectivement, une jointure sur des VARCHAR sera moins performante que sur des entiers mais avec 500 000 lignes, ce n'est pas encore catastrophique en performances je pense.

Le GROUP BY est nécessaire du fait de la fonction MAX. Je ne pense pas que tu puisses y échapper.

Quels sont les index que je dois prévoir ?

Au moins sur toutes les colonnes qui sont dans les conditions de jointure.

[lvr]

Merci. Les dernières fois que j'avais écris des joins c'était sous Oracle 8 => j'adapte.

Au moins sur toutes les colonnes qui sont dans les conditions de jointure.

Je souhaite encore ajouter un champ dans le join: un indicateur du type combinaison : 0: générale, 1: exclusivement des tags décrivant la source du son, 2: exclusivement des tags décrivant la perception du son

Code :

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

1
2
3
4
5
6
SELECT sample.id, sample.name, sample.duration, sample.path, 
  MAX(searchhash.pourcentage) AS pourcentage_max
FROM sample
INNER JOIN samplehash ON (sample.id=samplehash.sampleid and samplehash.combinaison=1)
INNER JOIN searchhash ON samplehash.hash=searchhash.hash
GROUP BY sample.id, sample.name, sample.duration, sample.path

que je peux écrire aussi

Code :

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

1
2
3
4
5
6
SELECT sample.id, sample.name, sample.duration, sample.path, 
  MAX(searchhash.pourcentage) AS pourcentage_max
FROM sample
INNER JOIN samplehash ON sample.id=samplehash.sampleid 
INNER JOIN searchhash ON (samplehash.hash=searchhash.hash and samplehash.combinaison=1)
GROUP BY sample.id, sample.name, sample.duration, sample.path

Quelle des deux formes est préférable ?

Sachant que je peux faire le query avec ou sans la restriction sur la combinaison:
avec la forme 1,
Je dois donc avoir des index pour samplehash
1°) sampleid + combinaison (ou combinaison+sampleid ?)
2°) hash

Avec la forme 2
Je dois donc avoir des index pour samplehash
1°) sampleid
2°) hash + combinaison (ou combinaison+hash ?)

Effectivement, une jointure sur des VARCHAR sera moins performante que sur des entiers mais avec 500 000 lignes, ce n'est pas encore catastrophique en performances je pense.

En à l'origine je souhaitais avoir une vraie hash numérique, mais je n'ai pas trouvé de bon algorithme pour hasher une String en nombre !

[CinePhil]

Je souhaite encore ajouter un champ dans le join: un indicateur du type combinaison : 0: générale, 1: exclusivement des tags décrivant la source du son, 2: exclusivement des tags décrivant la perception du son

Quelle des deux formes est préférable ?

Comme il s'agit cette fois d'une condition de restriction sur les données et non pas d'une condition de jointure, il est préférable de la mettre dans la clause de restriction, c'est à dire dans le WHERE :

Code :

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

1
2
3
4
5
6
7
SELECT sample.id, sample.name, sample.duration, sample.path, 
  MAX(searchhash.pourcentage) AS pourcentage_max
FROM sample
INNER JOIN samplehash ON sample.id = samplehash.sampleid
  INNER JOIN searchhash ON samplehash.hash = searchhash.hash
WHERE samplehash.combinaison=1
GROUP BY sample.id, sample.name, sample.duration, sample.path

[lvr]

Comme il s'agit cette fois d'une condition de restriction sur les données et non pas d'une condition de jointure, il est préférable de la mettre dans la clause de restriction, c'est à dire dans le WHERE

A vouloir trop en faire...
Comme cette valeur divise ma table en 4 (moitié des rows pour combinaison=0, un quart pour 1 et un quart pour 2) mais qu'il n'y a que 3 valeurs possibles, est-ce qu'un index est nécessaire/utile ? Je me souviens que sur DB2 un index sur champ avec aussi peu de valeurs possibles n'était pas utilisé.
Si utile, quel(s) est(sont)-ils ?
1°) sampleid + combinaison
2°) combinaison+sampleid
3°) hash + combinaison
4°) combinaison+hash
Est-ce qu'il est possible de voir comment la db résout le select pour adapter les index en conséquence ?

[CinePhil]

N'ayant jamais testé les performances des index autrement que pas d'index = escargot / index = formule1 , je préfère te reporter vers les articles de SQLPro sur l'indexation :
http://sqlpro.developpez.com/cours/quoi-indexer/
http://blog.developpez.com/sqlpro/p7...d-index-ni-de/
http://sqlpro.developpez.com/optimis...ntenanceIndex/

[lvr]

Merci CinePhil.
J'ai revu les index en fonctions des guidelines que tu m'as pointés. Pour le moment ça marche, je verrai bien lorsque je montrai en charge.