LINUX.ORG.RU

Эффективный алгоритм работы для посторения облака тэгов php/mysql.


0

1

Добрый день!
подскажите как сделать наиболее быстрое создание и поиск по облаку тэгов на записи.

Предположим есть большая таблица с именами (и тэги к ним).

Роман (Москва, Студент, Рыжий)
Николай (Борода, Кареглазый)
Иван (Урод, Кидалово, Гей)

Как видите тэгов может быть много и они абсолютно разные.
Нужно выполнять по базе поиск по данным тэгам.

Вынести тэги в отдельную таблицу и джоинить её некатит - слишком долгая операция.
Сделать это поле как SET тоже не катит т.к. у SET ограничение на 64 разных тэга. А это поле по сути бесконечно возможный SET
Пока выручает что тэги пишутся в проиндексированное текстовое поле и поиск ведётся так - SELECT * WHERE `tag` LIKE '%Борода%' OR `tag` LIKE '%Студент%'
возможно есть какое-то более красивое решение задачи?

★★

Преждевременная оптимизация — это корень всех бед.

anonymous ()

Вынести в отдельную таблицу и кэшировать. Не каждую секунду же теги меняются.

Viglim ()
Ответ на: комментарий от Viglim

немного не понял, что вынести.. тэги ?
и как их кешировать ? а потом надо еще поиск по ним осуществлять. т.е. тэги должны быть привязаны к записям, а если тэги в отдельной таблице, то таблица с тэгами станет еще больше чем таблица с именами и её просто так не прокешируешь.

ppy ★★ ()

Есть объекты.

Есть таблица тэгов.

Есть таблица привязок тэгов к объектам.

У таблицы тэгов есть поле счётчика привязок.

Всё делается одним запросом, никаких джойнов.

KRoN73 ★★★★★ ()
Ответ на: комментарий от KDE41user

Спасибо интерестная вещь - посмотрю.
А чем оно отличается от fulltext поиска в mysql?

ppy ★★ ()
Ответ на: комментарий от KRoN73

немного не понял про счетчик привязок.
Вы предлагаете запрос MANY TO MANY ?
не могли бы вы показать пример.

ppy ★★ ()
Ответ на: комментарий от KRoN73

Нужно выбрать все объекты с тегом А. Это простите как без джоинов одним запросом?

urxvt ★★★★★ ()

Я, конечно, не спец, но разве JOIN медленнее, чем LIKE '%Борода%' OR `tag` LIKE '%Студент%?

name_no ★★ ()
Ответ на: комментарий от urxvt

>Нужно выбрать все объекты с тегом А. Это простите как без джоинов одним запросом?

В топикстарте вопрос стоит о построении облака тэгов. Там - один запрос. SELECT tag_name, tag_count FROM tags ...

Если речь о выборке объектов, то тут или делаем текстовое с дублированием имени тэгов и выбираем одним запросом:
SELECT object_id FROM tags_index WHERE tag = 'Студент'
или, если привязок очень много (у меня есть таблицы в несколько миллионов записей) и выгоднее выбирать по целому индексу, то в два:
SELECT tag_id FROM tags WHERE tag_name = 'Студент'
SELECT object_id FROM tags_index WHERE tag_id = $tag_id

Запросов хоть и два, но будет работать несравнимо быстрее, чем при выборке по текстовому полю или при JOIN'е.

KRoN73 ★★★★★ ()
Ответ на: комментарий от name_no

При сопоставимых размерах баз и при связывании по целому ключу - JOIN, конечно, быстрее. Но лучше и без JOIN'ов, и без LIKE :)

KRoN73 ★★★★★ ()
Ответ на: комментарий от KRoN73

У вас видимо один тэг на один объект, у меня тэгов на каждый объект несколько и выбирать надо через OR .
т.е. SELECT * WHERE `tag` LIKE '%Борода%' OR `tag` LIKE '%Студент%'

ppy ★★ ()
Ответ на: комментарий от ppy

>не могли бы вы показать пример

Таблица1, скажем, tags. Это список тэгов:
int tag_id
string tag_name
int tag_usage_count

Таблица2, tags_index, список привязок тэгов к объектам:
int tag_id
int object_id

Соответственно, нужно привязать тэг к объекту:
SELECT tag_id FROM tags WHERE tag_name = '$tag_name';
INSERT INTO tag_index SET tag_id = $tag_id, object_id = $object_id
UPDATE tags SET tag_usage_count = tag_usage_count + 1 WHERE tag_name = '$tag_name';

Нужно извлечь сотню самых популярных тэгом с их количеством для облака:
SELECT tag_id, tag_name, tag_usage_count FROM tags ORDER BY tag_usage_count DESC LIMIT 100;

Нужно потом извлечь все объекты, привязанные к данному тэгу:
SELECT object_id FROM tag_index WHERE tag_id = $tag_id

...

Готового решения на ресурсах, что я могу светить нет, можно посмотреть концепт (пока не юзабельный) будущего «форума на тэгах» на http://forums.balancer.ru/tags/

Код этой страницы лежит в http://trac.balancer.ru/bors-airbase/browser/classes/bors/balancer/board/keyw...

Код вторичных страниц, типа http://forums.balancer.ru/tags/авиация/США/ лежит на http://trac.balancer.ru/bors-airbase/browser/classes/bors/balancer/board/keyw...

Код объекта «тэг» - http://trac.balancer.ru/bors-core/browser/classes/common/keyword.php

Код объекта «привязка тэга» - http://trac.balancer.ru/bors-core/browser/classes/common/keyword/bind.php

Всё пока крайне сыро, так как служит лишь для внутренних тестов.

KRoN73 ★★★★★ ()
Ответ на: комментарий от ppy

>У вас видимо один тэг на один объект

Нет, много :)

SELECT * WHERE `tag` LIKE '%Борода%' OR `tag` LIKE '%Студент%'


Это выборка списка объектов, у которых есть один из перечисленных тэгов?

SELECT object_id FROM tags_index WHERE tag_id IN ($tag_id1, $tag_id2, $tag_id3, ...);

KRoN73 ★★★★★ ()
Ответ на: комментарий от KRoN73

> В топикстарте вопрос стоит о построении облака тэгов. Там - один запрос. SELECT tag_name, tag_count FROM tags ...
Аа... Понял.

urxvt ★★★★★ ()

Если размеры не такие и страшные, да и тэгов на каждый объект не сотни, можно воспользоваться полем типа array в БД, только надо будет выбросить мускуль, и взять вместо него, например, постгрес. По массивам он вроде как индексирует.

anonymous ()
Ответ на: комментарий от KRoN73

> SELECT tag_id FROM tags WHERE tag_name = 'Студент'

SELECT object_id FROM tags_index WHERE tag_id = $tag_id

Запросов хоть и два, но будет работать несравнимо быстрее, чем при выборке по текстовому полю или при JOIN'е.

Позвольте мне ещё раз усомниться. Вы утверждаете, что

SELECT tag_id FROM tags WHERE tag_name = 'Студент';
SELECT object_id FROM tags_index WHERE tag_id = $tag_id;

будет работать быстрее, чем тот же

SELECT object_id FROM tag_index ti, tags t, WHERE ti.tag_id = t.tag_id AND tag_name = 'Студент'

А почему?

name_no ★★ ()
Ответ на: комментарий от name_no

Вдогонку ещё хочу уточнить, будет ли запрос вида SELECT object_id FROM tag_index WHERE tag_id = (SELECT tad_id FROM tags WHERE tag_name = 'Студент') медленнее, чем два раздельных запроса и тоже почем...

name_no ★★ ()
Ответ на: комментарий от name_no

>А почему?

Потому что в первом случае идёт простая выборка по индексам.

Во втором - формирование новой сущности и выборка по ней. Даже если не будут создаваться временные таблицы и не будет использоваться файловая сортировка, всё равно работа будет много медленнее.

KRoN73 ★★★★★ ()
Ответ на: комментарий от name_no

>Вдогонку ещё хочу уточнить, будет ли запрос вида SELECT object_id FROM tag_index WHERE tag_id = (SELECT tad_id FROM tags WHERE tag_name = 'Студент') медленнее, чем два раздельных запроса и тоже почем...

В теории вложенный запрос - по сути отдельный запрос. Так что разница в скорости зависит от реализации. Другое дело, что два отдельных запроса то не в вакууме, а, например, в пхп коде:) А значит будут затраты на работу с БД через пхп. В любом случае разница должна быть невелика и незаметна, по сравнению со всем остальным.

anonymous ()
Ответ на: комментарий от name_no

Фиг знает. Тут уже смотреть/проверять нужно. С одной стороны, по логике, скорость работы WHERE tag_id IN ($id1, $id2, $id3...) должна быть такой же, как и у WHERE tag_id IN (SELECT id FROM...). Но на практике я нарывался на чудовищные тормоза вторых запросов по сравнению с первыми. Разбираться и исследовать причины было обычно недосуг, так что пользовался первым вариантом.

KRoN73 ★★★★★ ()
Ответ на: комментарий от anonymous

>А значит будут затраты на работу с БД через пхп

Сегодня это уже пренебрежимо. Там оверхед чуть ли не микросекундных порядков, что на фоне миллисекундных запросов пренебрежимо.

KRoN73 ★★★★★ ()
Ответ на: комментарий от name_no

Ну да. Например, у Слоника традиционно отмечают более эффективный JOIN. Но сам не щупал.

KRoN73 ★★★★★ ()

Интересует, насколько мой алгоритм корректен, жду комментариев

> Роман (Москва, Студент, Рыжий)

Николай (Борода, Кареглазый)

Иван (Урод, Кидалово, Гей)



Таблица «Man»: man_id, man_name
# 1, Роман
# 2, Николай
# 3, Иван

Таблица «Tag»: tag_id, tag_name
# 1, Москва
# 2, Студент
# 3, Рыжий
# 4, Борода
...

Таблица «Tag_links»: man_id, tag_id
# 1, 1
# 1, 2
# 1, 3
# 2, 4
...

# рейтинг типа:
SELECT tag_id, COUNT(*) AS count
FROM Tag_links
GROUP BY tag_id
ORDER BY count DESC

leonder ()

Re: Интересует, насколько мой алгоритм корректен, жду комментариев

>SELECT tag_id, COUNT(*) AS count ... GROUP BY tag_id ORDER BY count DESC

Накладно будет, когда таких привязок будут сотни тысяч, тем паче - миллионы. От десятых долей секунды до секунд запрос может начать выполняться.

KRoN73 ★★★★★ ()
Ответ на: комментарий от KRoN73

> С одной стороны, по логике, скорость работы WHERE tag_id IN ($id1, $id2, $id3...) должна быть такой же, как и у WHERE tag_id IN (SELECT id FROM...). Но на практике я нарывался на чудовищные тормоза вторых запросов по сравнению с первыми. Разбираться и исследовать причины было обычно недосуг, так что пользовался первым вариантом.

Все просто. Оптимизатор MySQL вложенный запрос разворачивает в INNER JOIN. В результате, зачастую, происходить полное связывание двух таблиц и лишь затем выборка. А если таблицы ещё и большие, то все, нужно идти вручную убивать запрос в очереди.

Отсюда правило - не использовать вложенных запросов в MySQL. Удивительно сколько раз мне приходилось очередному сотруднику разжевывать такие элементарные вещи при работе с большими БД...

PavelR ()

Ещё небольшой совет - в качестве ключа в таблице тэгов использовать crc. Не ещё одни ключ к autoincrement, а вместо этого autoincrement. Тогда не будут нужные эти уродские выборки по строке.

PavelR ()
Ответ на: комментарий от ppy

> А чем оно отличается от fulltext поиска в mysql?

Быстрее. С определенного числа строк на выдаче MySQL начинает дохнуть. Вы просто будете стоят перед фактом - каждый запрос жрет несколько секунд и занимает ресурсы. А атрибуты? В MySQL вам придется играться с кучей многоколоночных индексов, добиваясь обработки всех комбинаций. Будут появляться неразрешимые ситуации. В sphinx об этом думать не приходиться вовсе. Его скорость сортировки и выборки на порядок превосходит MySQL. К тому же fulltext нет в InnoDB.

PavelR ()
Ответ на: комментарий от ppy

>А чем оно отличается от fulltext поиска в mysql?

Скоростью и гибкостью. Вот, можно оценить поиск по четырёхгиговой базе на два миллиона записей: http://balancer.ru/tools/search/

KRoN73 ★★★★★ ()
Ответ на: комментарий от ppy

>А чем оно отличается от fulltext поиска в mysql?

Собственно уже описали чем, добавлю, что поскольку sphinx быстрый, его используют не только для поиска - из него делают сложные выборки, чтобы не нагружать базу.

В последней версии додали real-time индексы. Цитата с оф. сайта:

with SphinxQL, RT indexes, transactions, crash recovery and other goodies Sphinx now feels almost real close to a database.

KDE41user ()
Ответ на: комментарий от KRoN73

если смотреть на мускул, то в нем быстрее будет создать временную таблицу и джойнить с ней, чем делать where id in (select...).

В постгресе с этим все гораздо веселее

OldFornit ()
Ответ на: комментарий от OldFornit

если смотреть на мускул, то в нем быстрее будет создать временную таблицу и джойнить с ней

Но ещё веселее (именно в варианте id IN ...) именно дёрнуть отдельно список ID и потом дёрнуть запрос, куда они будут подставлены. У меня это так часто встречается, что даже специальный формат записи в запросах есть. Типа:

$ids = array(1,2,5,10,25);
$topics = objects_array('topic', array('id IN' => $ids));

KRoN73 ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.