So implementieren Sie ein Tag-System

89

Ich habe mich gefragt, wie man am besten ein Tag-System implementiert, wie es auf SO verwendet wird. Ich habe darüber nachgedacht, aber ich kann keine gute skalierbare Lösung finden.

Ich dachte an eine grundlegende 3-Tisch-Lösung: einen tagsTisch, articleseinen tag_to_articlesTisch und einen Tisch.

Ist dies die beste Lösung für dieses Problem oder gibt es Alternativen? Mit dieser Methode würde die Tabelle mit der Zeit extrem groß werden, und für die Suche ist dies vermutlich nicht zu effizient. Andererseits ist es nicht so wichtig, dass die Abfrage schnell ausgeführt wird.

Saif Bechan
quelle

Antworten:

118

Ich glaube, Sie werden diesen Blog-Beitrag interessant finden: Tags: Datenbankschemata

Das Problem: Sie möchten ein Datenbankschema haben, in dem Sie ein Lesezeichen (oder einen Blog-Beitrag oder was auch immer) mit so vielen Tags versehen können, wie Sie möchten. Später möchten Sie Abfragen ausführen, um die Lesezeichen auf eine Vereinigung oder einen Schnittpunkt von Tags zu beschränken. Sie möchten auch einige Tags aus dem Suchergebnis ausschließen (z. B. minus).

"MySQLicious" -Lösung

In dieser Lösung hat das Schema nur eine Tabelle, es wird denormalisiert. Dieser Typ wird als "MySQLicious-Lösung" bezeichnet, da MySQLicious del.icio.us-Daten in eine Tabelle mit dieser Struktur importiert.

Geben Sie hier die Bildbeschreibung einGeben Sie hier die Bildbeschreibung ein

Schnittpunktabfrage (UND) für "Suche + Webservice + Semweb":

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

Union (OR) Abfrage nach "search | webservice | semweb":

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

Minus-Abfrage für "Suche + Webservice-Semweb"

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

"Scuttle" -Lösung

Scuttle organisiert seine Daten in zwei Tabellen. Diese Tabelle "scCategories" ist die "Tag" -Tabelle und hat einen Fremdschlüssel für die "Lesezeichen" -Tabelle.

Geben Sie hier die Bildbeschreibung ein

Schnittpunktabfrage (UND) für "Lesezeichen + 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

Zuerst werden alle Lesezeichen-Tag-Kombinationen durchsucht, wobei das Tag "Lesezeichen", "Webservice" oder "Semweb" ist (c.Kategorie IN ("Lesezeichen", "Webservice", "Semweb")), dann nur die Lesezeichen, die Alle drei Tags, nach denen gesucht wurde, werden berücksichtigt (HAVING COUNT (b.bId) = 3).

Union (OR) Abfrage für "bookmark | webservice | semweb": Lassen Sie einfach die HAVING-Klausel weg und Sie haben union:

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

Minus (Ausschluss) Abfrage für "Lesezeichen + Webservice-Semweb", dh: Lesezeichen UND Webservice UND NICHT 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

Das Weglassen des HAVING COUNT führt zur Abfrage für "bookmark | webservice-semweb".


"Toxi" -Lösung

Toxi entwickelte eine Struktur mit drei Tischen. Über die Tabelle "Tagmap" sind die Lesezeichen und die Tags n-zu-m-bezogen. Jedes Tag kann zusammen mit verschiedenen Lesezeichen verwendet werden und umgekehrt. Dieses DB-Schema wird auch von WordPress verwendet. Die Abfragen sind die gleichen wie bei der "scuttle" -Lösung.

Geben Sie hier die Bildbeschreibung ein

Schnittpunktabfrage (UND) für "Lesezeichen + 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

Union (OR) Abfrage für "Lesezeichen | 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

Minus (Ausschluss) Abfrage für "Lesezeichen + Webservice-Semweb", dh: Lesezeichen UND Webservice UND NICHT 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

Das Weglassen des HAVING COUNT führt zur Abfrage für "bookmark | webservice-semweb".

Nick Dandoulakis
quelle
3
Autor dieses Blogposts hier. Der Blog wird nicht mehr von Chrome blockiert (dumme WordPress-Schwachstellen, jetzt auf Tumblr verschoben). Ein
großes Lob
hi @Philipp. OK, habe meine Antwort bearbeitet. Übrigens, danke für den tollen Beitrag zu Datenbank-Tag-Systemen.
Nick Dandoulakis
1
Nur als Hinweis: Wenn Sie möchten, dass in der Schnittpunktabfrage für die Toxi-Lösung auch das Lesezeichen angezeigt wird, wenn Sie nach "Lesezeichen" UND "Webservice" gesucht haben, müssen Sie "HAVING COUNT (b.id) = 3" von ändern 3 bis "sizeof (array ('bookmark', 'webservice'))". Nur ein kleines Detail, wenn Sie dies als dynamische Tag-Abfragefunktion verwenden möchten.
Toxicate20
3
Gibt es Links zum Leistungsvergleich für verschiedene im Beitrag erwähnte Lösungen?
Kampta
@kampta, nein, ich habe keine Links.
Nick Dandoulakis
8

An Ihrer Drei-Tabellen-Lösung ist nichts auszusetzen.

Eine andere Möglichkeit besteht darin, die Anzahl der Tags zu begrenzen, die auf einen Artikel angewendet werden können (z. B. 5 in SO), und diese direkt zu Ihrer Artikeltabelle hinzuzufügen.

Das Normalisieren der Datenbank hat Vor- und Nachteile, genau wie das Festverdrahten von Dingen in einer Tabelle Vor- und Nachteile hat.

Nichts sagt, dass Sie nicht beides können. Es widerspricht relationalen DB-Paradigmen, Informationen zu wiederholen, aber wenn das Ziel Leistung ist, müssen Sie möglicherweise die Paradigmen brechen.

John
quelle
Ja, das direkte Einfügen der Tags in die Artikeltabelle wäre sicherlich eine Option, obwohl diese Methode einige Nachteile aufweist. Wenn Sie die 5 Tags in einem durch Kommas getrennten Feld wie (tag1,2,3,4) speichern, ist dies eine einfache Methode. Die Frage ist, ob die Suche schneller geht. Zum Beispiel möchte jemand alles mit tag1 sehen, man muss die gesamte Artikeltabelle durchgehen. Dies wäre weniger, als durch die tag_to_article-Tabelle zu gehen. Andererseits ist die Tabelle tags_to_article schlanker. Eine andere Sache ist, dass Sie jedes Mal in PHP explodieren müssen, ich weiß nicht, ob dies Zeit braucht.
Saif Bechan
Wenn Sie beides tun (Tags mit dem Artikel und in einer separaten Tabelle), erhalten Sie Leistung sowohl für postzentrierte Suchvorgänge als auch für tagzentrierte Suchvorgänge. Der Kompromiss ist die Last der Aufrechterhaltung der wiederholten Informationen. Indem Sie die Anzahl der Tags begrenzen, können Sie jedes in eine eigene Spalte einfügen. Wählen Sie einfach * aus den Artikeln Wo XXXXX und gehen Sie; Keine Explosion notwendig.
John
6

Ihre vorgeschlagene Implementierung mit drei Tabellen funktioniert für das Tagging.

Der Stapelüberlauf verwendet jedoch eine andere Implementierung. Sie speichern Tags in der varchar-Spalte in der Posts-Tabelle im Klartext und verwenden die Volltextindizierung, um Posts abzurufen, die mit den Tags übereinstimmen. Zum Beispiel posts.tags = "algorithm system tagging best-practices". Ich bin sicher, dass Jeff dies irgendwo erwähnt hat, aber ich vergesse wo.

Juha Syrjälä
quelle
4
Das scheint super ineffizient zu sein. Was ist mit der Tag-Bestellung? Oder verwandte Tags? (wie "Prozess" ähnlich wie "Algorithmus" oder ähnliches)
Richard Duerr
3

Die vorgeschlagene Lösung ist die beste - wenn nicht die einzig praktikable - Möglichkeit, die viele-zu-viele-Beziehung zwischen Tags und Artikeln anzugehen. Ich stimme also für "Ja, es ist immer noch das Beste". Ich würde mich allerdings für Alternativen interessieren.

David sagt, Monica wieder einsetzen
quelle
Genau. Diese Tags und TagMap-Tabellen haben eine geringe Datensatzgröße und sollten bei ordnungsgemäßer Indizierung die Leistung nicht drastisch verringern. Es könnte auch eine gute Idee sein, die Anzahl der Tags pro Artikel zu begrenzen.
PanJanek
2

Wenn Ihre Datenbank indizierbare Arrays unterstützt (wie z. B. PostgreSQL), würde ich eine vollständig denormalisierte Lösung empfehlen: Speichern Sie Tags als Array von Zeichenfolgen in derselben Tabelle. Wenn nicht, ist eine sekundäre Tabelle, die Objekte Tags zuordnet, die beste Lösung. Wenn Sie zusätzliche Informationen für Tags speichern müssen, können Sie eine separate Tags-Tabelle verwenden. Es macht jedoch keinen Sinn, für jede Tag-Suche einen zweiten Join einzuführen.

Nick Johnson
quelle
POstgreSQL unterstützt nur Indizes für ganzzahlige Arrays: postgresql.org/docs/current/static/intarray.html
Mike Chamberlain
1
Heutzutage unterstützt es auch Text: postgresql.org/docs/9.6/static/arrays.html
Luckydonald
2

Ich möchte optimiertes MySQLicious für eine bessere Leistung vorschlagen. Davor sind die Nachteile der Toxi-Lösung (3 Tabellen)

Wenn Sie Millionen von Fragen haben und jeweils 5 Tags enthalten, enthält die Tagmap-Tabelle 5 Millionen Einträge. Also müssen wir zuerst 10 Tausend Tagmap-Einträge basierend auf der Tag-Suche herausfiltern und dann wieder übereinstimmende Fragen dieser 10 Tausend herausfiltern. Wenn Sie also herausfiltern, ob die künstliche ID einfach numerisch ist, ist dies in Ordnung. Wenn es sich jedoch um eine Art UUID (32 varchar) handelt, muss herausgefiltert werden, obwohl sie indiziert ist.

Meine Lösung:

Wenn ein neues Tag erstellt wird, haben Sie den Zähler ++ (Basis 10) und konvertieren Sie diesen Zähler in base64. Jetzt hat jeder Tag-Name die Base64-ID. und übergeben Sie diese ID zusammen mit dem Namen an die Benutzeroberfläche. Auf diese Weise haben Sie maximal zwei Zeichen, bis 4095 Tags in unserem System erstellt wurden. Verketten Sie nun diese mehreren Tags in jede Fragetabellen-Tag-Spalte. Fügen Sie auch ein Trennzeichen hinzu und sortieren Sie es.

Der Tisch sieht also so aus

Geben Sie hier die Bildbeschreibung ein

Fragen Sie beim Abfragen die ID anstelle des echten Tag-Namens ab. Da es SORTIERT ist , ist die andBedingung auf dem Tag effizienter (LIKE '%|a|%|c|%|f|% ).

Beachten Sie, dass Leerzeichen Trennzeichen ist nicht genug , und wir brauchen doppelte Trennzeichen zu unterscheiden Tags wie sqlund mysqlda LIKE "%sql%"kehrtmysql Ergebnisse als gut. Sollte seinLIKE "%|sql|%"

Ich weiß, dass die Suche nicht indiziert ist, aber Sie haben möglicherweise andere Spalten indiziert, die sich auf Artikel wie author / dateTime beziehen. Andernfalls führt dies zu einem vollständigen Tabellenscan.

Schließlich ist bei dieser Lösung kein innerer Join erforderlich, bei dem Millionen Datensätze mit 5 Millionen Datensätzen unter Join-Bedingungen verglichen werden müssen.

Kanagavelu Sugumar
quelle
Team, Bitte geben Sie in den Kommentaren Ihren Beitrag zum Nachteil dieser Lösung an.
Kanagavelu Sugumar
@ Nick Dandoulakis Bitte helfen Sie mir, indem Sie Ihre Kommentare zu der oben genannten Lösung abgeben. Funktioniert das?
Kanagavelu Sugumar
@ Juha Syrjälä Ist die obige Lösung in Ordnung?
Kanagavelu Sugumar
0
CREATE TABLE Tags (
    tag VARHAR(...) NOT NULL,
    bid INT ... NOT NULL,
    PRIMARY KEY(tag, bid),
    INDEX(bid, tag)
)

Anmerkungen:

  • Dies ist insofern besser als TOXI, als es nicht viele zusätzliche: viele Tabellen durchläuft, was die Optimierung schwierig macht.
  • Sicher, mein Ansatz ist aufgrund der redundanten Tags möglicherweise etwas sperriger (als TOXI), aber das ist ein kleiner Prozentsatz des Ganzen Datenbank, und die Leistungsverbesserungen können erheblich sein.
  • Es ist hoch skalierbar.
  • Es hat keine Ersatz- AUTO_INCREMENTPK (weil es keine benötigt) . Daher ist es besser als Scuttle.
  • MySQLicious ist zum Kotzen, weil es keinen Index verwenden kann ( LIKEmit führendem Platzhalter ; falsche Treffer auf Teilzeichenfolgen)
  • Verwenden Sie für MySQL unbedingt ENGINE = InnoDB, um Clustering-Effekte zu erzielen.

Verwandte Diskussionen (für MySQL):
viele: viele geordnete Listen zur Optimierung der Zuordnungstabelle

Rick James
quelle