Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5   вперед  Ctrl      все
 EAV с возможностью быстрой выборки по сложным условиям  [new]
Васисуалий Пупкинсон
Member

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

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

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

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

Тут, видимо, нужен какой-то принципиально другой подход нежели реляционная база, но какой выбрать - хз. Вариантов вроде бы много, но пока не сделаешь тестовый стенд, не поймешь - будет-ли быстро работать выборка по сложному условию. Поэтому обращаюсь к коллективному разуму - может кто такое уже делал.
10 янв 11, 07:13    [10047404]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Alexander Ryndin
Member

Откуда:
Сообщений: 4919
Блог
Васисуалий Пупкинсон,

В случае с Oracle я бы использовал таблицу с 200-300 атрибутами и bitmap-индексы (они отлично подходят под ваши условия). Возможно, что разделил таблицу для запросов и таблицу для добавления новых данных. Таблицу для запросов бы периодически перестраивал.
10 янв 11, 08:24    [10047427]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
miksoft
Member

Откуда:
Сообщений: 38921
Я бы предложил использовать EAV c нормализованными attribute-value. Тогда основная табличка сокращается всего до двух числовых полей.
Запросы в Оракле вполне приемлемо работают через банальные GROUP BY ... HAVING COUNT(*)=..., а вот для MySQL пришлось покумекать над оптимизацией.
10 янв 11, 14:07    [10048359]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Yo.!
Guest
можно еще попробовать indexed view или взрослый партитионинг по юзер ид.
имхо ничего лучше реляционной субд для такой задачи не найти
10 янв 11, 14:09    [10048372]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
miksoft
Member

Откуда:
Сообщений: 38921
Yo.!
взрослый партитионинг по юзер ид.
Ну если только по достаточно крупному диапазону (например, с шагом в тысячу или десять тысяч). Иначе ораклоиды не одобрят - 9963426.
10 янв 11, 14:14    [10048397]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 10.01.2011 7:13, Васисуалий Пупкинсон wrote:

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

Кто тебе мешает использовать гибрид обычной реляционной БД с EAV ?

Важные атрибуты -- в виде обычных колонок таблиц, остальные, дополнительные -- в
виде EAV.

Posted via ActualForum NNTP Server 1.4

10 янв 11, 14:26    [10048460]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 10.01.2011 8:24, Alexander Ryndin wrote:

> В случае с Oracle я бы использовал таблицу с 200-300 атрибутами и bitmap-индексы
> (они отлично подходят под ваши условия). Возможно, что разделил таблицу для

Они вообще мало подо что подходят. Да и вообще они не индексы.

Posted via ActualForum NNTP Server 1.4

10 янв 11, 14:26    [10048464]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Alexander Ryndin
Member

Откуда:
Сообщений: 4919
Блог
MasterZiv
On 10.01.2011 8:24, Alexander Ryndin wrote:

> В случае с Oracle я бы использовал таблицу с 200-300 атрибутами и bitmap-индексы
> (они отлично подходят под ваши условия). Возможно, что разделил таблицу для

Они вообще мало подо что подходят. Да и вообще они не индексы.
Аргументы?
10 янв 11, 15:15    [10048659]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Ggg_old
Member

Откуда: Одесса
Сообщений: 1342
Интересная задачка. Поддерживаю идею с гибридным подходом. Наверняка какие-то атрибуты являются наиболее используемыми/селективными в поиске - их в колонки. Остальные атрибуты в отдельную таблицу.
10 янв 11, 15:48    [10048836]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
pkarklin
Member

Откуда: Москва (Муром)
Сообщений: 74930
Ggg_old
Поддерживаю идею с гибридным подходом. Наверняка какие-то атрибуты являются наиболее используемыми/селективными в поиске - их в колонки. Остальные атрибуты в отдельную таблицу.


+1. Решение, оправдавшее себя многолетней практикой.
10 янв 11, 15:53    [10048875]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54850

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

Posted via ActualForum NNTP Server 1.4

10 янв 11, 15:59    [10048907]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 10.01.2011 15:15, Alexander Ryndin wrote:

> Они вообще мало подо что подходят. Да и вообще они не индексы.
>
> Аргументы?

Аргументов не будет. Так же, как и флейма на тему "Занахрена кому
нужны битмап-индексы".

Posted via ActualForum NNTP Server 1.4

10 янв 11, 17:12    [10049290]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 10.01.2011 7:13, Васисуалий Пупкинсон wrote:
> Критериев может быть указано довольно много (от единиц до десятков), нужно
> поддерживать их сочетания для AND и OR, а также крайне желательно и NOT IN.

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

Posted via ActualForum NNTP Server 1.4

10 янв 11, 17:17    [10049321]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 10.01.2011 7:13, Васисуалий Пупкинсон wrote:

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

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

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

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

Posted via ActualForum NNTP Server 1.4

10 янв 11, 17:20    [10049337]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6645
Васисуалий Пупкинсон,

Найли тут iv_an_ru. У него как раз подобные психованные запросы на virtuoso обрабатываются.
10 янв 11, 17:47    [10049494]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
servit
Member

Откуда: г. Кишинёв, Республика Молдова
Сообщений: 3148
Блог
Bitmap-индексы в СУБД Caché.

+ Пример
Class del.a Extends %Persistent
{
Index ia On a [ Type = bitmap ];
Index ib On b [ Type = bitmap ];
Index ic On c [ Type = bitmap ];
Index id On d [ Type = bitmap ];
Property As %Integer;
Property As %String;
Property As %Date;
Property As %Boolean;

ClassMethod Fill(As %Integer = {1e6}) As %Status
{
  
do ##class(del.a).%KillExtent()
  
set c=0
  
for i=1:1:set c=c+1,^del.aD(c)=$lb("",$r(1e5),$r(1e5),$r(1e5),$r(2))
  
^del.aD=c
  
do ##class(del.a).%BuildIndices()
  
q $$$OK
}
}

select count(*) from del.a where 
(
  a in (1,78) 
  and year(c) between year(current_date)-5 and year(current_date) 
  and d=0
) or b like '%75%'
На моих данных запрос отрабатывает <1с. (результат - 39734 записей)
Васисуалий Пупкинсон
Тут, видимо, нужен какой-то принципиально другой подход нежели реляционная база, но какой выбрать - хз. Вариантов вроде бы много, но пока не сделаешь тестовый стенд, не поймешь - будет-ли быстро работать выборка по сложному условию. Поэтому обращаюсь к коллективному разуму - может кто такое уже делал.
Если без SQL, то посмотрите здесь.
10 янв 11, 20:02    [10050086]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Васисуалий Пупкинсон
Member

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


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

Как это будет выглядеть в случае нормализованных attribute-value? Просто я честно говоря немного не в курсе что значит нормализованные...
10 янв 11, 20:03    [10050087]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Alexander Ryndin
Member

Откуда:
Сообщений: 4919
Блог
MasterZiv
Они вообще мало подо что подходят. Да и вообще они не индексы.
Аргументов не будет. Так же, как и флейма на тему "Занахрена кому
нужны битмап-индексы".
Мдя-я-я. Не ел, но уверен, что гадость.
MasterZiv
On 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-индексы и все.
10 янв 11, 20:08    [10050098]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Васисуалий Пупкинсон
Member

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


Да, насчет indexed view пожалуй неплохая мысль. А в PostgreSQL или в MySQL это можно реализовать? Если нет, то подскажите плиз какие-нить бесплатные решения, очень уж не хочется на Оракл или SQL Server завязываться, т.к. лицензии стоят весьма ощутимо.
Насчет партицирования - честно говоря не очень понятно как тут это может помочь. По идее, надо наоборот стремиться все в одну кучу, на одну машину собрать, сколько бы не было записей в базе. Иначе (вроде бы) затраты времени на агрегирование информации с разных машин будут очень уж ощутимы. Да и не очень понятно, по какому признаку партицировать... Ну или поясните плиз, как Вы это видите.
10 янв 11, 20:09    [10050100]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Васисуалий Пупкинсон
Member

Откуда: Москва
Сообщений: 23
pkarklin
Ggg_old
Поддерживаю идею с гибридным подходом. Наверняка какие-то атрибуты являются наиболее используемыми/селективными в поиске - их в колонки. Остальные атрибуты в отдельную таблицу.


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


Спасибо, попробую поэкспериментировать с этим.
10 янв 11, 20:10    [10050101]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Васисуалий Пупкинсон
Member

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


Как-то с ходу не очень понятно как их прикрутить-то с таким прицелом...
10 янв 11, 20:13    [10050112]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Васисуалий Пупкинсон
Member

Откуда: Москва
Сообщений: 23
MasterZiv
А типовые запросы можно увидеть ?

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

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


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

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

Насчет NOT IN - тут может быть несколько облегчает задачу то, что это условие можно накладывать в самом конце, на то, что уже выбрано предыдущими операторами. Т.е. в теле основного запроса этих ограничений встечаться не будет.
10 янв 11, 20:22    [10050133]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Васисуалий Пупкинсон
Member

Откуда: Москва
Сообщений: 23
Alexander Ryndin
MasterZiv
Они вообще мало подо что подходят. Да и вообще они не индексы.
Аргументов не будет. Так же, как и флейма на тему "Занахрена кому
нужны битмап-индексы".
Мдя-я-я. Не ел, но уверен, что гадость.
MasterZiv
On 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-индексы и все.


Ох, попробую конечно, если больше никаких вариантов не будет. Просто очень уж не хочется с Ораклом связываться. При всем уважении, конечно. Если бы это корпоративный софт был, за который есть кому хорошо заплатить, тогда без вопросов, но тут ситуация несколько другая... Бюджет довольно-таки ограничен, увы.
10 янв 11, 20:27    [10050150]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Yo.!
Guest
Васисуалий Пупкинсон

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


запутался в терминах - я partitioning view имел ввиду, они в стандарт эдишене есть. взрослый оракловый партитионинг как и битмап индексы вам врядле подойдут, они только в ЕЕ редакции, т.е. по $47000 за процессор.
у постгреса нет взрослого партитионинга, но есть аналог partitioning view
http://www.postgresql.org/docs/8.1/interactive/ddl-partitioning.html

партиции делать на то, что обязательно заполняют, типа пол и город аля женщина-мск, женщина-питер. правда принципиально наверно не решит ...
10 янв 11, 20:51    [10050201]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 10.01.2011 20:08, Alexander Ryndin wrote:

> BITMAP-индекс как раз отлично решает эту задачу с AND и OR.

Это-то да.

> Они также специально предназначен именно для случаев, когда количество различных
> значений невелико. Тут подойдет даже рост, который имеет диапазон от 100 до 210.

Как критерии будем объединять ?

Posted via ActualForum NNTP Server 1.4

10 янв 11, 22:24    [10050425]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5   вперед  Ctrl      все
Все форумы / Сравнение СУБД Ответить