Jak wdrożyć system tagów

Zastanawiałem się, jak najlepiej zaimplementować system tagów, taki jak używany w SO. Myślałem o tym, ale nie mogę znaleźć dobrego skalowalnego rozwiązania.

Myślałem o podstawowym rozwiązaniu z trzema stołami: o tagsstole, articlesstołach i tag_to_articlesstole.

Czy to najlepsze rozwiązanie tego problemu, czy też istnieją alternatywy? Korzystając z tej metody, tabela stałaby się bardzo duża w czasie, a wyszukiwanie to nie jest zbyt wydajne, jak zakładam. Z drugiej strony nie jest tak ważne, aby zapytanie było wykonywane szybko.

Myślę, że ten post na blogu będzie interesujący: Tagi: Schematy baz danych

Problem: Chcesz mieć schemat bazy danych, w którym możesz oznaczyć zakładkę (lub post na blogu lub cokolwiek innego) dowolną liczbą tagów. Później chcesz uruchamiać zapytania, aby ograniczyć zakładki do unii lub przecięcia znaczników. Chcesz także wykluczyć (powiedzmy: minus) niektóre tagi z wyników wyszukiwania.

Rozwiązanie „MySQLicious”

W tym rozwiązaniu schemat ma tylko jedną tabelę, jest on zdenormalizowany. Ten typ jest nazywany „rozwiązaniem MySQLicious”, ponieważ MySQLicious importuje dane del.icio.us do tabeli o takiej strukturze.

Zapytanie o skrzyżowanie (AND) dla „search + webservice + semweb”:

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

Zapytanie Union (OR) dla „search | webservice | semweb”:

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

Zapytanie minus dla „search + webservice-semweb”

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

Rozwiązanie „Scuttle”

Scuttle organizuje swoje dane w dwóch tabelach. Ta tabela „scCategories” jest tabelą „tagów” ​​i ma klucz obcy do tabeli „zakładek”.

Zapytanie o skrzyżowanie (AND) dla „zakładka + usługa internetowa + 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

Najpierw przeszukiwane są wszystkie kombinacje zakładka-znacznik, gdzie tag to „zakładka”, „usługa sieciowa” lub „semweb” (c.category IN („bookmark”, „webservice”, „semweb”)), a następnie tylko zakładki, które uwzględniono wszystkie trzy wyszukiwane tagi (HAVING COUNT (b.bId) = 3).

Zapytanie Union (OR) dla „bookmark | webservice | semweb”: Po prostu pomiń klauzulę HAVING i masz 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 (wykluczenie) Zapytanie dla „bookmark + webservice-semweb”, czyli: bookmark AND webservice AND NOT 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

Pominięcie opcji HAVING COUNT prowadzi do zapytania „bookmark | webservice-semweb”.

Rozwiązanie „Toxi”

Toxi wymyślił strukturę z trzema stołami. Za pomocą tabeli „tagmap” zakładki i znaczniki są powiązane n-to-m. Każdy tag może być używany razem z różnymi zakładkami i odwrotnie. Ten schemat DB jest również używany przez wordpress. Zapytania są takie same, jak w przypadku rozwiązania „scuttle”.

Zapytanie o skrzyżowanie (AND) dla „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

Zapytanie Union (OR) dla „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

Minus (wykluczenie) Zapytanie dla „bookmark + webservice-semweb”, czyli: bookmark AND webservice AND NOT 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

Pominięcie opcji HAVING COUNT prowadzi do zapytania „bookmark | webservice-semweb”.

Nie ma nic złego w rozwiązaniu z trzema stołami.

Inną opcją jest ograniczenie liczby tagów, które można zastosować do artykułu (np. 5 w SO) i dodanie ich bezpośrednio do tabeli artykułów.

Normalizacja bazy danych ma swoje zalety i wady, podobnie jak sztywne podłączanie rzeczy do jednej tabeli ma zalety i wady.

Nic nie mówi, że nie możesz zrobić obu. Powtarzanie informacji jest sprzeczne z relacyjnymi paradygmatami DB, ale jeśli celem jest wydajność, być może trzeba będzie złamać te paradygmaty.

Proponowana przez Ciebie implementacja trzech tabel będzie działać w przypadku tagowania.

Przepełnienie stosu używa jednak innej implementacji. Przechowują tagi w kolumnie varchar w tabeli postów w postaci zwykłego tekstu i używają indeksowania pełnotekstowego, aby pobrać posty pasujące do tagów. Na przykład posts.tags = "algorithm system tagging best-practices". Jestem pewien, że Jeff gdzieś o tym wspomniał, ale nie pamiętam gdzie.

Proponowane rozwiązanie jest najlepszym - jeśli nie jedynym wykonalnym - sposobem, w jaki przychodzi mi do głowy, aby rozwiązać relację wiele do wielu między tagami a artykułami. Więc mój głos jest za „tak, nadal jest najlepszy”. Byłbym jednak zainteresowany jakąkolwiek alternatywą.

Jeśli twoja baza danych obsługuje tablice indeksowalne (jak na przykład PostgreSQL), poleciłbym rozwiązanie całkowicie zdenormalizowane - przechowywanie znaczników jako tablicy ciągów w tej samej tabeli. Jeśli nie, najlepszym rozwiązaniem jest dodatkowa tabela mapująca obiekty na znaczniki. Jeśli chcesz przechowywać dodatkowe informacje w odniesieniu do tagów, możesz użyć oddzielnej tabeli tagów, ale nie ma sensu wprowadzać drugiego sprzężenia dla każdego wyszukiwania tagów.

Chciałbym zasugerować zoptymalizowany MySQLicious dla lepszej wydajności. Wcześniej wady rozwiązania Toxi (3 tabele) są

Jeśli masz miliony pytań i każdy ma po 5 tagów, to w tabeli tagmap będzie 5 milionów wpisów. Więc najpierw musimy odfiltrować 10 tysięcy wpisów tagmap na podstawie wyszukiwania tagów, a następnie ponownie odfiltrować pasujące pytania z tych 10 tysięcy. Więc podczas odfiltrowywania, jeśli identyfikator artykułu jest prosty numeryczny, to jest w porządku, ale jeśli jest to rodzaj UUID (32 varchar), to filtrowanie wymaga większego porównania, mimo że jest indeksowane.

Moje rozwiązanie:

Za każdym razem, gdy tworzony jest nowy tag, miej counter ++ (podstawa 10) i przekonwertuj ten licznik na base64. Teraz każda nazwa tagu będzie miała identyfikator base64. i przekaż ten identyfikator do interfejsu użytkownika wraz z nazwą. W ten sposób będziesz mieć maksymalnie dwa identyfikatory znaków, dopóki nie będziemy mieli 4095 tagów utworzonych w naszym systemie. Teraz połącz te wiele tagów w każdej kolumnie tagu tabeli pytań. Dodaj również separator i posortuj go.

A więc stół wygląda tak

Podczas odpytywania zapytaj o identyfikator zamiast prawdziwej nazwy tagu. Od kiedy jest SORTOWANY , andstan na tagu będzie bardziej wydajny ( LIKE '%|a|%|c|%|f|%).

Zauważ, że pojedynczy separator spacji nie wystarczy i potrzebujemy podwójnego separatora, aby rozróżnić tagi takie jak sqlimysql ponieważ LIKE "%sql%"również zwróci mysqlwyniki. Powinien byćLIKE "%|sql|%"

Wiem, że wyszukiwanie nie jest indeksowane, ale mimo to możesz zindeksować inne kolumny związane z artykułem, takie jak autor / data Czas w przeciwnym razie spowoduje pełne skanowanie tabeli.

Wreszcie, dzięki temu rozwiązaniu nie jest wymagane sprzężenie wewnętrzne, w przypadku gdy trzeba porównać milion rekordów z 5 milionami rekordów pod warunkiem łączenia.

CREATE TABLE Tags (
    tag VARHAR(...) NOT NULL,
    bid INT ... NOT NULL,
    PRIMARY KEY(tag, bid),
    INDEX(bid, tag)
)

Uwagi:

• Jest to lepsze niż TOXI, ponieważ nie przechodzi przez wiele dodatkowych tabel, co utrudnia optymalizację.
• Jasne, moje podejście może być nieco bardziej nieporęczne (niż TOXI) ze względu na nadmiarowe tagi, ale to niewielki procent całości bazy danych, a poprawa wydajności może być znacząca.
• Jest wysoce skalowalny.
• Nie ma (ponieważ nie potrzebuje) zastępczej AUTO_INCREMENTPK. Dlatego jest lepszy niż Scuttle.
• MySQLicious jest do bani, ponieważ nie może używać indeksu ( LIKEz rozszerzeniem wiodącym wieloznacznym; fałszywe trafienia w podciągach)
• W przypadku MySQL, upewnij się, że używasz ENGINE = InnoDB, aby uzyskać efekt „klastrowania”.

Powiązane dyskusje (dla MySQL):
wiele: wiele uporządkowanych list optymalizacji tabel mapowania