Comments 48
«с построением облака тегов очень большие проблемы. Можно решить так: обрабатываются все «тэговые» поля таблиц, анализируется частота присутствия отдельного тэга (эх, был бы доступ непосредственно к самому полнотекстовому индексу, как было бы хорошо) и на фоне этого строится облако.» я проблемы не обнаружил, например нужно облако тегов конкретного автора: отправляем запрос на получение всех материалов автора > забираем содержимое ячейки tegs(например) далее объеденям все в единый массив и анализируем его на чистоту и тд… ИМХО — описал как можно короче :)
все будет зависить от масштаба запроса + кэш + группировка данных например на определённом этапе обращаться уже не к материалам пользователя а к самому пользователю а потом к группе и тд…
На Хабре используется первый механизм.
Только второй минус компенсируется дублированием строчки тегов AS IS в таблице объектов (постов, блогов, компаний и пр). Соответственно, при выводе постов никаких JOIN-ов делать не надо.

В связях Объект->Тег используются не те теги, которые указал пользователь, а «нормализованные» в нижнем регистре и с учётом таблицы синонимов.

Поиск одному тегу или нескольким по условию «ИЛИ» происходит довольно просто. Сначала ищестся ID нормализованного тега, а, потом, в связке Объект->Тег выбираются посты по
where tag_id = ID
либо
where tag_id IN (...)


Для сортировки объектов по дате публикации в таблице Объект->Тег дополнительно хранится время публикации. В общем, денормализция рулит.

А вот поиск по тегам по условию «И», или, как в блоке «похожие статьи» по условию «как можно больше и чтобы статьи были не очень старые» всё немного сложнее. Если кто-то сталкивался с подобными задачами с интересом послушаю Ваши решения

Вместо сортировки статей по дате публикации часто достаточно просто сортировать по автоинкрементному первичному ключу. Конечно, если при этом бывает такое, что дата изменяется, или может быть не текущей, а задним числом, или на будущее (как это сделано в LiveJournal) — то такой способ не подходит. Но если дата публикации ставится исключительно автоматически, при публикации, как например тут на Хабре, то это очень даже подходит.

Еще одно, извините что немного не в тему, но тоже насчет дат… для себя я давно сделал вывод, что значения дат наиболее эффективно хранить в поле UNSIGNED SMALLINT, а значения дата-время — в UNSIGNED INT :)
Полнотекстовые поисковые системы построены на пересечении возрастающих списков идентификаторов в индексе, по которым параллельно идут несколько итераторов. Списки в индексах лежат плотно. Либо 4 байта на запись, либо меньше, если использовать дифференциальное кодирование.

В описанном случае лучше, на мой взгляд, забить на SQL. Таблицу (id-тега -> id-статьи) закешировать в памяти. При поиске по И пересекать цепочки идентификаторов, при поиске по ИЛИ — объединять. При поиске «по кворуму» объединять по ИЛИ, потом считать для для каждого id-статьи количество прошедших тегов.

Более детально — для ИЛИ имеет смысл использовать алгоритм «куча». В вершине — итератор с минимальным значением.

Для поиска по И, например, такой алгоритм. Сортируем по возрастанию длин списков id. Двигаемся от первого итератора к последнему, проверяя текущий элемент. Если меньше, то проматываем итератор, пока не станет >=. Если >, то продвигаем значение, которое нас интересует, и начинаем просматривать итераторы опять с первого. Если все стоят на одном элементе, возвращаем Ok.

При изменении базы данных (добавление, удаление тега в записи, удаление записи с тегами) можно поступать по-разному:

1) Безусловно перечитываем кеш. Частота операций записи в базу меньше, чем частота просмотров.

2) Перечитываем в случае изменений, но не чаще, чем раз в 5 минут. В отдельном потоке без блокирования поисков. В этом случае поиск по тегам может чуть-чуть отставать от актуального состояния базы, но в реальном сценарии это не страшно.

3) Делим на две группы пространство идентификаторов статей маской по id — старые / изменившиеся. Для каждой группы — отдельный instance кеша. Для изменившихся перечитываем кеш после каждого изменения. Для старых — маскируем изменившиеся id. При поиске объединяем результаты. Перечитываем кеш старых раз в час без блокирования поисков.

поиск «по кворуму», алгоритм «куча»… круто!
Будет чем вечером заняться )
Сам использую метод описаный в статье, лично мне и моему серверу он нравится больше )))
Кстати этот метод работает и с другими разделяемыми параметрами, такими как списки привязанных файлов и галереи.
Использую 2 метода одновременно. Писал тут две статьи по поводу вывода и ввода тегов. Ни каких серьезных проблем не вижу с работой с тегами.

Использую второй способ, с облаком особых проблем нет. Просто запускается по крону скриптик раз в день и строится облако которое потом кэшируется.
acts_as_taggable в Rails работает именно по такому принципу, только прозрачно для кодера.
Ну, то что теги нормализованные былть должны я просто не стал писать… :-) А так, это да. Я для нормализации использоват такую схему — tag_id + 1000, после чего в полученой цифре заменял 0=> a, 1=>b и т.д. таким образом для тега c id = 1 получался «хэш» «baab» и так далее. Но это чтоб нормально искать в полнотекстовом поиске.

Поиск одному тегу или нескольким по условию «ИЛИ» происходит довольно просто. Сначала ищестся ID нормализованного тега, а, потом, в связке Объект->Тег выбираются посты по
where tag_id = ID
либо
where tag_id IN (...)


Так все равно получается объединение 2-х огромных таблиц, или я ошибаюсь? И еще такй момент: при where tag_id IN (...) у вас индексы учитыватся? Потому что вроде могут и не учитываться. Интресно просто.

А вот поиск по тегам по условию «И», или, как в блоке «похожие статьи» по условию «как можно больше и чтобы статьи были не очень старые» всё немного сложнее. Если кто-то сталкивался с подобными задачами с интересом послушаю Ваши решения

Вот полнотекстовый поиск такие проблемы хорошо решает. :-) Я бы наверно сделал так — в таблицу статей добавил поле с полнотекстовым индексом, которое было бы приведенной копией поля с тегами — т.е. хранились бы нормализованные теги перечисленные через пробел. Ну, еще приведенные к варианту > 3 символов. Это может решить проблемы с «И», «ИЛИ» и похожих статей. Но как это отразится на производительности — сказать сложно…
UFO landed and left these words here
UFO landed and left these words here
а как тогда быть с облаком? или подсказкой при добавлении тега, где нужно искать по началу тега и сортировать по частоте употребления?
UFO landed and left these words here
вовсе не надо джойнить 3 таблицы.
Во превых (забыл рассказать) при создании поста и прилинковке тегов автоматически инкрементируются счётчики в таблице тегов, по этому выбор облака происходит так:
SELECT name, tags_count FROM tags ORDER BY tags_count DESC LIMIT N;


А при поиске по тегу 3 запроса:
1. SELECT id FROM tags where name = 'тег'
2. SELECT target_id FROM tag_to_targets WHERE tag_id = <ID> and target_type = TYPE_POST ORDER BY target_time_published DESC LIMIT <пагинация>
3. SELECT ... FROM posts where in IN (<список полученных ID-шников>)
Это вы расписали то, что нормальный оптимизатор запросов БД сделает при том джойне 3-х таблиц, о котором мы говорим.
Тоже хороший вариант, но join всё же остаётся. Хотя только один на две таблицы.
UFO landed and left these words here
Ну, это, видимо, особенность работы (точнее «не работы») оптимизатора запроса mysql. Если я ничего не путаю, то ваш запрос в MSSQL будет при выполнении будет аналогичен, что и его join версия.
UFO landed and left these words here
Интересная мысль, но возникло несколько вопросов:
— Как насчет производительности при поиске по строке во втором случае?
— Если правильно понял, то в адресах тоже используется это же написание тега? (Иначе бы не было проблемы с кодированием url). Как быть если надо переименовать тег? Не получится так, что тег называется «Миша», а там «Петя»?

Я бы предложил такой вариант: все теги заменяются на их идешники (по описанной таблице tags), а в статье в отдельном поле типа массив (такое поддерживается, например, в постгресе) записывается массив идешек. Постгря еще чем хороша: такое поле можно проиндексировать и эффективно по нему искать. Даже с использованием запросов типа таких:
— все статьи с тегом «Вася»
— все с тегами «Вася» ИЛИ «Петя»
— все с тегами «Вася» И «Петя»
— теги ТОЛЬКО «Вася» И «Петя»
и т.п.
Производительность нормальная. Не фонтан, но нормальная.
Да, часто используется то же написание тэга. С переименованием будут проблемы.
В mysql нет массивов. К сожалению. Хотя, может и к счастью. Поэтому приходится довольствоаться тем, что есть.
А как вы оценивали? На каком объеме БД?
И насколько большой вклад в общую производительность дает система тегов?
Только на глаз… :-) Меньше сотой секунды выполняется, занчит нормально.
Объем примерно 10000… Остальное сказать затрудняюсь.
Про общую производительность тоже ничего точно сказать не могу.

Ваши вопросы слишком сильно завизят от многих параметров, так что дельный ответ дать сложно.
UFO landed and left these words here
Т.к. у меня «основная» БД MS SQL я также предлагаю вариант с XML полем: т.е. тэги записывать в XML поле (что даёт нам уже хоть какую-то степень нормализации данных в плане атомарности), на которые можно натравить индексы. Также с помощью MS SQL XML операторов можно достаточно легко переименовывать тэги. Но при выполнении сложных И/ИЛИ запросов, скорее всего, будет медленнее, чем, скажем, метод с много-ко-многим.
Использую только описанный в статье первый способ, но не в лоб, то есть, не делаю этих двух JOIN-ов.
Вместо этого, если есть возможность, стараюсь параллелить запросы, и использую многоуровневое кеширование.

Попробую объяснить на пальцах. Сначала рассмотрим реализацию «в лоб», как описывает автор статьи.

Итак, есть три таблицы:

1. Таблица тегов, назовем ее tag, с двумя полями tag_id и name:
tag_id — первичный ключ, поле типа int (или bigint, по ситуации)
name — сам тег, текстовое поле, уникальный индекс (часто имеет смысл делать HASH INDEX).

2. Таблица с «тегируемой информацией», например, таблица статей article с полями article_id и остальными (для нас сейчас важно только это article_id).

3. Связующая таблица article_tag, с двумя полями article_id и tag_id.

Это — уже жизнеспособная схема, и может быть использована без всяких ухищрений, но, к сожалению, как и упомянул в автор, будет неживой на больших объемах данных.

Теперь начинаем улучшать эту схему, тут уже очень важна специфика самого проекта, и соответственно рассмотрим несколько случаев.

1. Минимизируем количество запросов к таблице tag, чтобы получить tag_id. Конечно, полностью от этого избавиться не получится, особенно если тегов очень много, но самые часто запрашиваемые теги можно и нужно кешировать.

Параллелим запросы к таблице tag. Если есть возможность использовать распределенное хранилище данных, и если это оправдано по специфике проекта, то запрос к таблице tag (чтобы получить tag_id) можно делать на другой сервер, параллельно с какими-либо другими запросами на текущем сервере. В конце концов, для больших систем можно вообще выделить отдельный сервер (или несколько серверов) с огромным кешем, который будет оптимизирован только лишь на одну операцию — отдавать tag_id для запрашиваемого тега.

2. Минимизируем количество запросов к таблице article_tag на получение списка тегов для статьи. Это достигается путем кеширования тегов, соответствующих статье. А таблицу article добавляется простое неиндексируемое текстовое поле tag_cache (или же, делается отдельная таблица article_tag_cache с первичным ключем article_id, связанным с таблицей article 1:1, и полем cache), в котором просто перечислены все теги этой статьи или через разделитель, или в уже отформатированном предназначенном для вывода виде. Когда выводится статья, при этом не делается никакого обращения к огромной таблице article_tag, и просто берется содержимое tag_cache, и выводится.

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

3. Минимизируем количество запросов к таблице article_tag на получение списка статей для тега. Тут — аналогичное пункту 3 кеширование. По ситуации, можно добавить поле в таблицу тегов article_cache, или отдельную таблицу tag_article_cache (где хранятся article_id, соответствующие этому тегу, через разделитель, и первичный ключ tag_id, связанным с таблицей tag 1:1). Если статей, соответствующих тегу, может быть очень много, то структура усложняется, тогда исключительно потребуется добавлять таблицу tag_article_cache, в которую добавляется числовое поле page, при этом первичный ключ становится составным (tag_id, page).

Запросы к этой таблице также можно параллелить, вынеся ее на другой сервер.

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

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

Не нужно бояться, что при добавлении новой статьи или нового тега (это про описанный мной пример) придется делать лишние вставки и изменения в базе данных. Это довольно быстрые операции, так как работа будет идти по неиндексируемым полям. По сути, это только хранилища кешируемой информации. Более того, если есть возможности выделять отдельные кеш-серверы, то можно по ситуации обходиться вообще без дополнительных таблиц и обращений к БД, используя, скажем, нереляционные хранилища.

— В общем, не буду дальше детально расписывать, тут очень-очень много моментов которые нужно учитывать, фокусов, уловок, использования специфик тех или иных СУБД и т.д… думаю, принцип уже понятен. Не для каждого проекта подходит такой подход, но в ряде случаев он дает потрясающие результаты.

Общие выводы:
— Стараться не использовать JOIN на огромных таблицах, вместо этого делать отдельные запросы, при этом кешируя результаты.
— Параллелить запросы, насколько это возможно по задаче.
— Денормализовать базу данных, храня при этом промежуточные результаты тяжеловетных запросов, или же использовать внешние кеши или нереляционные хранилища данных.

В общем, все… Все вышеописанное использовано на практике в больших проектах, если что, с удовольствием выслушаю конструктивную критику. Все вышеизложенное — мое глубокое IMHO, я могу быть неправ. Просто эта тема для меня очень актуальна, и я давно ее копаю, может быть кому-то то что я написал выше пригодится, или натолкнет на какие-то идеи.
Проще говоря — тотальное кэширование.
Возможно, в зависимости от обновляемости данных, вам стоит рассмотреть вариант с полным переносом основных таблиц в память — LINQ, к примеру, с такими БД в памяти очень быстро работает.
Проблема с русскими буквами в тэгах, пожалуй, решаема. Использовать вместо самого названия тэга его md5-хэш. Для ускорения поиска по md5-хэшам я использую дополнительную колонку с индексом. В ней храним, например, две первые буквы хэша (в зависимости от объёма данных). Скорость поиска возрастает в сотни раз. Имея дополнительную таблицу где перечислены все теги и их md5 можно строить облако и тд.
«статей у нас 50000, а тэгов 10000» — это как это так? И проблем с построением облака тэгов нет? Естественно нет, если при таком количестве тэгов смысла в облаке просто нет и можно делать его статическим. Надо ввести модерирование и слияние тэгов, тогда их количество сократится на порядок, и проблемы, которые так горячо обсуждаются, исчезнут.
Тут вообще 10000 можно опустить. :-) Для примера это не имеет решительно никакого значения. А я вот думаю, кто на это первый внимания обратит? :-))))

Вообще, 10000 — нормальная цифра. А облака строятся не по всем, а только по самым-самым. Видете у статьи тег «полнотекстовый поиск»? Теперь попробуйте его найти хоть в одном облаке на сайте?

Видишь суслика? И я не вижу… А он есть!
Есть ли в тэгах смысл? Смотрим более-менее любое сообщение на хабре — тэги проставлены, половина тэгов — уникальные. Зачем они нужны, только засоряют. А вот тэги, создаваемые автоматическими классификаторами, были бы более полезны.

200.000 тэгов… Теряется смысл тэга.
Мне бы ваши объемы…
Различных тегов у меня сейчас ~200 тысяч.
Протежено ~800 тысяч записей.
Фильтры — разнообразные.
Проблем — нет.
Отлично! Я очень рад за вас.

Правда, это не мешает вашему коментарию выглядеть довольно бессмысленным.
Вы бы хоть уточнили, что вы такое используйте что у вас нет проблем. :-)
Долго писал, но долбанный Хабр что-то с перебоями работает.
Повторять не буду, а в кратце скажу:
прямые руки, нормальную субд, первичные ключи и алгоритмы, предугадывающие какие теги попадут в очередные облака.
Добавьте в первый способ денормализацию по вкусу — и будет счастье
Only those users with full accounts are able to leave comments. Log in, please.