Эффективная генерация запросов для перестановок тегов

Question

Вот упрощенная версия проблемы, с которой я сталкиваюсь на работе.Детали были изменены и более обобщены, поэтому я могу объяснить их проще.

Допустим, у вас есть движок блога, который позволяет постам в блогах присваивать теги при их создании.Поэтому я мог бы написать пост под названием «Мой отпуск в Италии», и я решил добавить к нему следующие теги: has-photos, vacation, family.Как часть моего блогового движка, я могу создавать собственные действия на основе групп тегов.Поэтому я решил, прежде чем писать, что любой пост с тегами has-photos и family будет автоматически опубликован в Facebook.Когда этот пост создается впервые, я должен автоматически сопоставить все его теги со всеми действиями, которые можно выполнить с комбинациями этих тегов.

Когда сообщение "Мой отпуск в Италии"После сохранения необходимо выполнить поиск всех действий для следующих групп тегов:

• has-photos
• vacation
• family
• has-photos & vacation
• has-photos & family
• vacation & family
• has-photos & vacation & family

Генерация этого запроса тривиальна, я просто получаю все перестановки любой длины из исходного набора тегов поста.Оказывается 2^N - 1 возможностей комбинаций тегов.

Проблема, с которой я сталкиваюсь, возникает, когда вы сталкиваетесь с большими наборами данных.С чем мы имеем дело:

• 10 000 + "сообщения", поступающие ежедневно
• 20 + "теги" за "сообщение"
• 1 000 из«действия», уже существующие, когда приходят сообщения в блоге, с различными числами тегов, с которыми они запускаются

Когда приходит сообщение с 20 тегами, получается чуть более миллиона перестановок.будет генерировать запрос для.Даже если бы моя база данных позволяла мне отправлять строки запроса на него настолько большим (подсказка: это не так), запуск по-прежнему занял бы целую вечность.

Есть ли разумное решение для этого, я не думаю,из?Прямо сейчас, как я это вижу, у меня остается одна возможность:

Действия используют OR вместо AND

Я мог бы изменить его так, чтобы при создании предопределенного действия тегион действует неявно ИЛИ вместо И.Тогда количество комбинаций тегов падает с 2^N - 1 до N.К сожалению, это серьезно ограничило бы полезность функции «тег действия».

Редактировать: я не обязательно ищу ответ в SQL.Просто другой подход к решению этой проблемы, даже если это просто описание высокого уровня.

Answer 1

Это похоже на то, что управляет алгоритмами движка, как http://en.wikipedia.org/wiki/Rete_algorithm. Я полагаю, что первым шагом к этому было бы сохранение списка тысяч действий в памяти и выполнение чего-то более быстрого, чем SQL, проверяя их при сохранении нового сообщения.

Answer 2

Вы можете решить эту проблему: для всех возможных совпадений, для которых у вас есть действия (в вашем примере только has-photos and family), рассчитайте, соответствует ли сообщение этому действию.Если у вас есть только несколько действий с несколькими триггерами, это будет быстро.

Answer 3

Вы можете комбинировать GROUP BY, COUNT и HAVING: хранить количество тегов для действий в строке действия, и теперь вы можете легко получить идентификаторы соответствующих действий:

Структура базы данных:

tag
  id
  name

action
  id
  tag_count
  // = SELECT COUNT(*) FROM action_tag WHERE action_tag.action_id=action.id

action_tag
  action_id
  tag_id

Пример строки:

tag
id name
1  has-photos
2  vacation
3  family

action
id tag_count
1  1
2  3

action_tag
action_id tag_id
1         3
2         1
2         2
2         3

Выбор:

SELECT     action.id
FROM       action
INNER JOIN tag         ON tag.name IN (<tag_1>,<tag_2>,....)
INNER JOIN action_tag  ON action_tag.action_id = action.id
                      AND action_tag.tag_id = tag.id
GROUP BY action.id
HAVING COUNT( action_tag ) = action.tag_count