Comment mettre en œuvre un système d'étiquettes

90

Je me demandais quelle était la meilleure façon d'implémenter un système de balises, comme celui utilisé sur SO. J'y pensais mais je n'arrive pas à trouver une bonne solution évolutive.

Je pensais avoir une solution de base à 3 tables: avoir une tagstable, une articlestable et une tag_to_articlestable.

Est-ce la meilleure solution à ce problème ou existe-t-il des alternatives? En utilisant cette méthode, la table deviendrait extrêmement volumineuse dans le temps, et je suppose que la recherche n'est pas trop efficace. D'un autre côté, il n'est pas si important que la requête s'exécute rapidement.

Saif Bechan
la source

Réponses:

119

Je crois que vous trouverez intéressant ce billet de blog: Tags: Schémas de base de données

Le problème: vous voulez avoir un schéma de base de données dans lequel vous pouvez baliser un signet (ou un article de blog ou autre) avec autant de balises que vous le souhaitez. Plus tard, vous souhaitez exécuter des requêtes pour contraindre les signets à une union ou une intersection de balises. Vous souhaitez également exclure (par exemple: moins) certaines balises du résultat de la recherche.

Solution «MySQLicious»

Dans cette solution, le schéma n'a qu'une seule table, il est dénormalisé. Ce type est appelé «solution MySQLicious» car MySQLicious importe les données del.icio.us dans une table avec cette structure.

entrez la description de l'image icientrez la description de l'image ici

Requête d'intersection (AND) pour "recherche + webservice + semweb":

SELECT *
FROM `delicious`
WHERE tags LIKE "%search%"
AND tags LIKE "%webservice%"
AND tags LIKE "%semweb%"

Requête Union (OR) pour "recherche | webservice | semweb":

SELECT *
FROM `delicious`
WHERE tags LIKE "%search%"
OR tags LIKE "%webservice%"
OR tags LIKE "%semweb%"

Requête moins pour "recherche + webservice-semweb"

SELECT *
FROM `delicious`
WHERE tags LIKE "%search%"
AND tags LIKE "%webservice%"
AND tags NOT LIKE "%semweb%"

Solution «Scuttle»

Scuttle organise ses données en deux tableaux. Cette table «scCategories» est la table «tag» et a une clé étrangère vers la table «signet».

entrez la description de l'image ici

Requête d'intersection (AND) pour "bookmark + webservice + semweb":

SELECT b.*
FROM scBookmarks b, scCategories c
WHERE c.bId = b.bId
AND (c.category IN ('bookmark', 'webservice', 'semweb'))
GROUP BY b.bId
HAVING COUNT( b.bId )=3

Tout d'abord, toutes les combinaisons de signets-balises sont recherchées, où la balise est "signet", "webservice" ou "semweb" (c.category IN ("bookmark", "webservice", "semweb")), puis uniquement les ont obtenu les trois balises recherchées sont prises en compte (HAVING COUNT (b.bId) = 3).

Requête Union (OR) pour "bookmark | webservice | semweb": omettez simplement la clause HAVING et vous avez union:

SELECT b.*
FROM scBookmarks b, scCategories c
WHERE c.bId = b.bId
AND (c.category IN ('bookmark', 'webservice', 'semweb'))
GROUP BY b.bId

Moins (exclusion) Requête pour «signet + webservice-semweb», c'est-à-dire: signet ET webservice ET NON semweb.

SELECT b. *
FROM scBookmarks b, scCategories c
WHERE b.bId = c.bId
AND (c.category IN ('bookmark', 'webservice'))
AND b.bId NOT
IN (SELECT b.bId FROM scBookmarks b, scCategories c WHERE b.bId = c.bId AND c.category = 'semweb')
GROUP BY b.bId
HAVING COUNT( b.bId ) =2

Le fait d'omettre HAVING COUNT conduit à la requête "bookmark | webservice-semweb".


Solution «Toxi»

Toxi a proposé une structure à trois tables. Via le tableau «tagmap», les signets et les balises sont liés de n à m. Chaque balise peut être utilisée avec différents signets et vice versa. Ce schéma DB est également utilisé par wordpress. Les requêtes sont sensiblement les mêmes que dans la solution «scuttle».

entrez la description de l'image ici

Requête d'intersection (AND) pour "bookmark + webservice + semweb"

SELECT b.*
FROM tagmap bt, bookmark b, tag t
WHERE bt.tag_id = t.tag_id
AND (t.name IN ('bookmark', 'webservice', 'semweb'))
AND b.id = bt.bookmark_id
GROUP BY b.id
HAVING COUNT( b.id )=3

Requête Union (OR) pour "bookmark | webservice | semweb"

SELECT b.*
FROM tagmap bt, bookmark b, tag t
WHERE bt.tag_id = t.tag_id
AND (t.name IN ('bookmark', 'webservice', 'semweb'))
AND b.id = bt.bookmark_id
GROUP BY b.id

Moins (exclusion) Requête pour «signet + webservice-semweb», c'est-à-dire: signet ET webservice ET NON semweb.

SELECT b. *
FROM bookmark b, tagmap bt, tag t
WHERE b.id = bt.bookmark_id
AND bt.tag_id = t.tag_id
AND (t.name IN ('Programming', 'Algorithms'))
AND b.id NOT IN (SELECT b.id FROM bookmark b, tagmap bt, tag t WHERE b.id = bt.bookmark_id AND bt.tag_id = t.tag_id AND t.name = 'Python')
GROUP BY b.id
HAVING COUNT( b.id ) =2

Le fait d'omettre HAVING COUNT conduit à la requête "bookmark | webservice-semweb".

Nick Dandoulakis
la source
3
auteur de ce billet de blog ici. Le blog n'est plus bloqué par Chrome (vulnérabilités de wordpress stupides, déplacées vers tumblr maintenant). Félicitations pour l'avoir transformé en markdown
hansaplast
salut @Philipp. OK, j'ai édité ma réponse. BTW, merci pour l'excellent article sur les systèmes de balises de base de données.
Nick Dandoulakis le
1
Remarque: si vous souhaitez que la requête d'intersection pour la solution Toxi affiche également le signet si vous avez recherché "signet" ET "service Web", vous devrez modifier le "HAVING COUNT (b.id) = 3" de 3 à "sizeof (array ('bookmark', 'webservice'))". Juste un détail mineur si vous prévoyez de l'utiliser comme fonction de requête de balise dynamique.
toxicate20
3
des liens pour comparer les performances des différentes solutions mentionnées dans l'article?
kampta
@kampta, non, je n'ai aucun lien.
Nick Dandoulakis
8

Rien de mal avec votre solution à trois tables.

Une autre option consiste à limiter le nombre de balises pouvant être appliquées à un article (comme 5 dans SO) et à les ajouter directement à votre tableau d'articles.

La normalisation de la base de données a ses avantages et ses inconvénients, tout comme le câblage des éléments dans une seule table présente des avantages et des inconvénients.

Rien ne dit que vous ne pouvez pas faire les deux. Répéter des informations va à l'encontre des paradigmes de base de données relationnelle, mais si l'objectif est la performance, vous devrez peut-être briser les paradigmes.

John
la source
Oui, mettre les balises directement dans la table des articles serait certainement une option, bien qu'il y ait quelques inconvénients à cette méthode. Si vous stockez les 5 balises dans un champ séparé par des virgules comme (tag1,2,3,4), ce serait une méthode simple. La question est de savoir si la recherche ira plus vite. Par exemple, quelqu'un veut tout voir avec tag1, vous devez parcourir tout le tableau des articles. Ce serait moins que passer par la table tag_to_article. Mais là encore, la table tags_to_article est plus mince. Une autre chose est que vous devez exploser à chaque fois en php, je ne sais pas si cela prend du temps.
Saif Bechan
Si vous faites les deux (balises avec l'article et dans un tableau séparé), cela vous donne des performances à la fois pour les recherches post-centrées et pour les recherches centrées sur les balises. Le compromis est le fardeau de conserver les informations répétées. De plus, en limitant le nombre de balises, vous pouvez placer chacune dans sa propre colonne. Sélectionnez simplement * parmi les articles Où XXXXX et allez; pas d'explosion nécessaire.
John
6

L'implémentation de trois tables que vous proposez fonctionnera pour le balisage.

Le débordement de pile utilise cependant une implémentation différente. Ils stockent les balises dans la colonne varchar dans la table des articles en texte brut et utilisent l'indexation de texte intégral pour récupérer les articles qui correspondent aux balises. Par exemple posts.tags = "algorithm system tagging best-practices". Je suis sûr que Jeff a mentionné cela quelque part mais j'oublie où.

Juha Syrjälä
la source
4
Cela semble super inefficace. Qu'en est-il de l'ordre des étiquettes? Ou des balises liées? (comme "processus" étant similaire à "algorithme" ou quelque chose du genre)
Richard Duerr
3

La solution proposée est la meilleure - sinon la seule possible - à laquelle je puisse penser pour aborder la relation plusieurs à plusieurs entre les balises et les articles. Donc mon vote est pour "oui, c'est toujours le meilleur". Je serais cependant intéressé par toutes les alternatives.

David dit de réintégrer Monica
la source
Je suis d'accord. Ces balises et tables TagMap ont une petite taille d'enregistrement et, lorsqu'elles sont correctement indexées, ne devraient pas réduire considérablement les performances. Limiter le nombre de balises od par article pourrait également être une bonne idée.
PanJanek
2

Si votre base de données prend en charge les tableaux indexables (comme PostgreSQL, par exemple), je recommanderais une solution entièrement dénormalisée - stocker les balises sous forme de tableau de chaînes sur la même table. Sinon, une table secondaire qui mappe les objets aux balises est la meilleure solution. Si vous avez besoin de stocker des informations supplémentaires sur les balises, vous pouvez utiliser une table de balises distincte, mais il ne sert à rien d'introduire une deuxième jointure pour chaque recherche de balises.

Nick Johnson
la source
POstgreSQL ne prend en charge que les index sur des tableaux d'entiers: postgresql.org/docs/current/static/intarray.html
Mike Chamberlain
1
Nowadys, il prend également en charge le texte: postgresql.org/docs/9.6/static/arrays.html
luckydonald
2

Je voudrais suggérer MySQLicious optimisé pour de meilleures performances. Avant cela, les inconvénients de la solution Toxi (3 tableau) sont

Si vous avez des millions de questions et qu'il contient 5 balises chacune, alors il y aura 5 millions d'entrées dans le tableau tagmap. Nous devons donc d'abord filtrer 10 000 entrées de tagmap en fonction de la recherche par tag, puis à nouveau filtrer les questions correspondantes de ces 10 000. Donc, tout en filtrant si l'ID artistique est numérique simple, alors c'est ok, mais s'il s'agit d'une sorte d'UUID (32 varchar), alors le filtrage nécessite une comparaison plus large bien qu'il soit indexé.

Ma solution:

Chaque fois qu'une nouvelle balise est créée, utilisez counter ++ (base 10) et convertissez ce compteur en base64. Désormais, chaque nom de balise aura un identifiant base64. et transmettez cet identifiant à l'interface utilisateur avec le nom. De cette façon, vous aurez au maximum deux identifiants de caractères jusqu'à ce que nous ayons 4095 balises créées dans notre système. Maintenant, concaténez ces multiples balises dans chaque colonne de balises de table de questions. Ajoutez également un délimiteur et triez-le.

Donc la table ressemble à ceci

entrez la description de l'image ici

Lors de l'interrogation, interrogez sur l'id au lieu du vrai nom de la balise Puisqu'il est TRIÉ , la andcondition sur la balise sera plus efficace ( LIKE '%|a|%|c|%|f|%).

Notez qu'un seul séparateur d'espace n'est pas suffisant et que nous avons besoin d'un double délimiteur pour différencier les balises comme sqlet mysqlcar LIKE "%sql%"renverra également des mysqlrésultats. Devrait êtreLIKE "%|sql|%"

Je sais que la recherche n'est pas indexée, mais vous avez peut-être encore indexé d'autres colonnes liées à un article comme auteur / dateTime, sinon, une analyse complète de la table sera effectuée.

Enfin, avec cette solution, aucune jointure interne n'est requise où des millions d'enregistrements doivent être comparés à 5 millions d'enregistrements à condition de jointure.

Kanagavelu Sugumar
la source
Équipe, veuillez fournir votre avis sur l'inconvénient de cette solution dans les commentaires.
Kanagavelu Sugumar
@Nick Dandoulakis S'il vous plaît, aidez-moi en fournissant vos commentaires sur la solution ci-dessus fonctionnera?
Kanagavelu Sugumar
@Juha Syrjälä La solution ci-dessus convient-elle?
Kanagavelu Sugumar
0
CREATE TABLE Tags (
    tag VARHAR(...) NOT NULL,
    bid INT ... NOT NULL,
    PRIMARY KEY(tag, bid),
    INDEX(bid, tag)
)

Remarques:

  • C'est mieux que TOXI dans la mesure où il ne passe pas par un très grand nombre: plusieurs tables ce qui rend l'optimisation difficile.
  • Bien sûr, mon approche peut être légèrement plus volumineuse (que TOXI) en raison des balises redondantes, mais c'est un petit pourcentage de l' ensemble de la base de données, et les améliorations de performances peuvent être significatives.
  • Il est hautement évolutif.
  • Il n'a pas (car il n'en a pas besoin) de AUTO_INCREMENTPK de substitution . Par conséquent, c'est mieux que Scuttle.
  • MySQLicious est nul car il ne peut pas utiliser d'index ( LIKEavec un caractère générique en tête ; faux hits sur les sous-chaînes)
  • Pour MySQL, veillez à utiliser ENGINE = InnoDB afin d'obtenir des effets de «clustering».

Discussions connexes (pour MySQL):
beaucoup: beaucoup de listes ordonnées d' optimisation de table de mappage

Rick James
la source