Здравствуйте! Прошу совета, ибо уже сломал голову пытаясь решить задачу.
Нужно сделать поиск по пользователям сайта.
У пользователей могут быть указаны некоторые атрибуты (число возможных атрибутов 200-300).
В основном эти атрибуты не имеют значений, а являются, по сути, просто флагами (например, "есть борода").
Но есть и атрибуты со значениями (например, "рост" - "185").
Реально каждому пользователю присваивается порядка 5-50 атрибутов.
Количество пользователей - сотни тысяч. Но нужно иметь уверенность, что это сможет быть без проблем смасштабировано еще на пару порядков.

Таким образом, вроде бы, эта задача идеально ложится на Entity-attribute-value модель.
В принципе, можно конечно иметь в таблице несколько сотен колонок со всеми этими атрибутами, но поддержка решения при этом заметно усложняется (особенно учитывая, что оно должно работать в режиме 24/7, а новые виды атрибутов появляются довольно часто). Да к тому же индексирование каждой из этих колонок тоже повлечет свои проблемы.

В общем, типовой use case - это выборка пользователей, подпадающих под заданные критерии.
Критериев может быть указано довольно много (от единиц до десятков), нужно поддерживать их сочетания для AND и OR, а также крайне желательно и NOT IN.
И трудность заключается в том, что это должно работать быстро. Для рядовых запросов - моментально, для тяжелых - в пределах 5-10 секунд (и то это уже долго).

Я пробовал моделировать это на Postgres, для 100 тыс. пользователей, для запросов по нескольким критериям работает конечно нормально. Но при увеличении количества критериев в запросе быстро умирает, даже при оптимизации по самые помидоры.
SQL Server заметно более шустрый, но все равно, большое количество критериев быстро обработать не получается.

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

miksoftЯ бы предложил использовать EAV c нормализованными attribute-value. Тогда основная табличка сокращается всего до двух числовых полей.

Сейчас в таблице есть три поля:
attribute_id int
value int
user_id int

Как это будет выглядеть в случае нормализованных attribute-value? Просто я честно говоря немного не в курсе что значит нормализованные...

Yo.!можно еще попробовать indexed view или взрослый партитионинг по юзер ид.
имхо ничего лучше реляционной субд для такой задачи не найти

Да, насчет indexed view пожалуй неплохая мысль. А в PostgreSQL или в MySQL это можно реализовать? Если нет, то подскажите плиз какие-нить бесплатные решения, очень уж не хочется на Оракл или SQL Server завязываться, т.к. лицензии стоят весьма ощутимо.
Насчет партицирования - честно говоря не очень понятно как тут это может помочь. По идее, надо наоборот стремиться все в одну кучу, на одну машину собрать, сколько бы не было записей в базе. Иначе (вроде бы) затраты времени на агрегирование информации с разных машин будут очень уж ощутимы. Да и не очень понятно, по какому признаку партицировать... Ну или поясните плиз, как Вы это видите.

pkarklinGgg_oldПоддерживаю идею с гибридным подходом. Наверняка какие-то атрибуты являются наиболее используемыми/селективными в поиске - их в колонки. Остальные атрибуты в отдельную таблицу.

+1. Решение, оправдавшее себя многолетней практикой.

Спасибо, попробую поэкспериментировать с этим.

Dimitry SibiryakovКажется, именно с проблемой выборок по большому количеству критериев призваны бороться
GIS-расширения. Всякие там R-tree индексы и т.д... Почему бы не попробовать их?..


Как-то с ходу не очень понятно как их прикрутить-то с таким прицелом...

MasterZivА типовые запросы можно увидеть ?

Просто хотя бы "поддерживать их сочетания для AND и OR" уже будет достаточно
проблематично (в смысле OR) для ЛЮБОЙ БД, не только реляционной, реляционность
тут вообще ни при чём.

А NOT IN вообще очень тяжёлая операция.


Типовой запрос с AND и OR например такой:

женщина
И
город - С.Петербург
И
не замужем
И
цель знакомства - (брак ИЛИ романтические отношения ИЛИ дружба)
И
цвет волос - блондинка
EXCLUDE
курит

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

Alexander RyndinMasterZivОни вообще мало подо что подходят. Да и вообще они не индексы.
Аргументов не будет. Так же, как и флейма на тему "Занахрена кому
нужны битмап-индексы".Мдя-я-я. Не ел, но уверен, что гадость.
MasterZivOn 10.01.2011 7:13, Васисуалий Пупкинсон wrote:

> В общем, типовой use case - это выборка пользователей, подпадающих под заданные
> критерии.
> Критериев может быть указано довольно много (от единиц до десятков), нужно
> поддерживать их сочетания для AND и OR, а также крайне желательно и NOT IN.
> И трудность заключается в том, что это должно работать быстро. Для рядовых
> запросов - моментально, для тяжелых - в пределах 5-10 секунд (и то это уже долго).

А типовые запросы можно увидеть ?

Просто хотя бы "поддерживать их сочетания для AND и OR" уже будет достаточно
проблематично (в смысле OR) для ЛЮБОЙ БД, не только реляционной, реляционность
тут вообще ни при чём.

А NOT IN вообще очень тяжёлая операция.
BITMAP-индекс как раз отлично решает эту задачу с AND и OR.
Они также специально предназначен именно для случаев, когда количество различных значений невелико. Тут подойдет даже рост, который имеет диапазон от 100 до 210.
Как применять? Строим на часто используемые поля BITMAP-индексы и все.

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

MasterZivOn 10.01.2011 20:22, Васисуалий Пупкинсон wrote:

> Типовой запрос с AND и OR например такой:
>
> женщина
> И
> город - С.Петербург
> И
> не замужем
> И
> цель знакомства - (брак ИЛИ романтические отношения ИЛИ дружба)
> И
> цвет волос - блондинка
И
> NOT курит

Что-то не видно тут OR.


Да, и правда, то что я имел в виду под OR - это не что иное как IN для значений.
Тогда правильный пример будет таким:

женщина
И
город - С.Петербург
И
не замужем
И
цель знакомства IN (брак, романтические отношения, дружба)
И
цвет волос - блондинка
И
NOT курит

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

MasterZivПодозреваю, что ключевое умение СУБД тут -- возможность при запросе использовать
несколько индексов по одной таблице, делая merge join таблицы самой с собой
(каждая отобрана по условию с использованием индекса).

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


Со способом, использующим соединение таблиц, есть проблема, если в условии поиска заданы не очень селективные атрибуты. Например, условия поиска такие:

Страна: Россия или Украина (допустим, есть 300 тыс. записей с таким атрибутом).
Пол: мужской (есть 170 тыс. записей)
Семейное положение: холост (есть 100 тыс. записей)
Цель знакомства: брак (есть 80 тыс. записей)
Цвет волос: брюнет (70 тыс. записей)
Возраст: от 25 до 45 (50 тыс. записей)

Таким образом, в лучшем случае (если планировщик выберет правильный порядок соединения) будет сделано как минимум 5 соединений по 50 тыс. записей. И хорошо еще если только 5 и только по 50 тысяч - что, в принципе, отрабатывает за приемлемое время при разогретом кеше. Но если кеш холодный, то время отклика уже не лезет ни в какие ворота (более 10 секунд). А если будет не очень селективный запрос с бОльшим числом параметров, то у пользователя определенно все зависнет.

Естественно, на выходе нужно получить всего лишь десяток записей. Но этот десяток должен быть выбран из списка, отсортированного по времени регистрации пользователей. И никуда не деться от того, чтобы не проделать прежде все эти соединения.
Вот если бы СУБД умела соединять таблицы не последовательно (сначала полностью первую пару, потом к тому что получилось, полностью третью таблицу, и т.д.), а выбирать совпадающие записи из этих таблиц (отсортированных, конечно) по одной, пока не наберется количество, указанное в опции LIMIT (или TOP). Я даже пытался сделать сам такой велосипед посредством скрипта в Postgres. Но ничего путного из этого не вышло.

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

Да, это я пробовал делать. Для каждого вида атрибута - отдельная таблица. Действительно, хорошая оптимизация. Но к сожалению, это не устраняет основного камня преткновения - ситуаций, когда нужно сделать много (5 - 10, а то и больше) связываний таблиц, где каждое связывание - по нескольку десятков тысяч записей. Естественно, такие ситуации будут встречаться не на каждом шагу. И может быть даже придется с этим смириться. Но хотелось бы прежде испробовать все возможности найти решение, которое позволило бы с приемлемой скоростью обрабатывать даже такие вот неудобные запросы.

servit Bitmap -индексы в СУБД Caché.


Почитал, хорошее дело. Вот правда, непонятно, сколько стоит лицензия. На сайте указано только
авторI love Caché! How can I purchase a license?
We offer a variety of license types – one of them is sure to be right for you. Please call us toll-free at +1.800.753.2571, or contact your local InterSystems office to discuss your needs.

Как-то мутно это... Вообще, когда вижу такой подход к делу (типа цену озвучивают только при личном общении), как-то сразу интерес снижается. Навевает что-то вроде
"Скажите, сколько стоит ваша пищевая добавка? - Это зависит от множества факторов! Для начала скажите, пожалуйста, какой марки Ваш автомобиль?".

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

pilot911Васисуалий Пупкинсон,

надеюсь, в проведенных тестах ваш запрос выглядел INNER JOIN a ON a.id=b.id AND a.have_boroda=1 AND a.have_girl=1
если так - то запрос должен выполняться очень быстро даже на миллионах записей

Да, принцип именно такой. И действительно, даже на миллионах записей выполняется очень быстро, если количество джойнов не превышает примерно 5 штук. Если больше, и при этом джойнится большое количество строк каждый раз, то вот тогда уже появляются тормоза.

pilot911я недавно оставил работу с каше, точнее с ее частью, так вот, бит индекс - не панацея в вашем варианте, поскольку позволяет искать точное совпадение, с диапазоном дат как вы битиндекс будете использовать?
и каше плохо работает на миллионах записей, я вам не советую, хотя ради интереса можете потестировать

Насчет диапазонов - на их сайте написано вот это:

авторThe SQL Engine can use bitmap indices for the following operations:
* ANDing of multiple conditions on a given table.
* ORing of multiple conditions on a given table.
* RANGE conditions on a given table.
* COUNT operations on a given table.

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

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

pilot911Васисуалий Пупкинсон,

системы госмасштаба на каше мне неизвестны, может вам известны? поделитесь

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