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

Откуда:
Сообщений: 456
А какие есть разумные решения для такой задачи:
1. Есть достаточно небольшое (около 10 млн.) объектов.
2. У каждого объекта около сотни параметров, некоторые параметры общие для всех объектов, некоторые - только для малой части. Всего различных параметров - около 10 000.
3. Параметры - разные (числовые, строковые, булевские), с очень разной селективностью.

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

По производительности: при нескольких десятках-сотнях запросов в секунду время одного запроса не более 10ms.

Обновления достаточно редкие, можно делать, например, пачками раз в несколько минут.
Транзакционной целостности и непротиворечивости не требуется.

Я понимаю, как это сделать "ручками", на чистой Java. И тут есть куча плюсов, типа специальных стратегий хранения для отдельных параметров. Но как-то не хочется изобретать велосипед и самому придумывать оптимизатор запросов.

Попытки использовать in-memory db (например, h2) пока не радуют, долго отрабатывает.
Платить за TimesTen или solidDB не хочется )
Задача, конечно, похожа на OLAP, но в OLAP-системах я совсем плохо разбираюсь (

Кто и что может предложить-посоветовать? Желательно бесплатное или дешевое )
31 окт 13, 17:30    [15060153]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
Dimitry Sibiryakov
Member

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

DPH3
при нескольких десятках-сотнях запросов в секунду время одного запроса не более
10ms.

Вам бы лучше определиться: один запрос должен отрабатывать за 10 миллисекунд или сто
запросов должны отработать за секунду. Второе гораздо проще, с первым вам никто не поможет.

Posted via ActualForum NNTP Server 1.5

31 окт 13, 17:44    [15060239]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
servit
Member

Откуда: г. Кишинёв, Республика Молдова
Сообщений: 3148
Блог
Dimitry Sibiryakov
с первым вам никто не поможет.
Здесь внизу страницы выводится:

Generated in 11ms. [1ms]
31 окт 13, 18:26    [15060490]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
DPH3
Member

Откуда:
Сообщений: 456
Dimitry Sibiryakov
DPH3
при нескольких десятках-сотнях запросов в секунду время одного запроса не более
10ms.

Вам бы лучше определиться: один запрос должен отрабатывать за 10 миллисекунд или сто
запросов должны отработать за секунду. Второе гораздо проще, с первым вам никто не поможет.

Увы, первое. Ну, ладно, пусть будет 20ms, хотя это уже многовато.
И почему ничего не поможет? Примитивный код на Java примерно столько и дает, а он явно не оптимален.
31 окт 13, 18:27    [15060498]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
miksoft
Member

Откуда:
Сообщений: 38920
DPH3,

я видел где-то описание такой системы, построенной на sphinx-е. Посмотрите в его сторону.
31 окт 13, 18:35    [15060548]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
ASCRUS
Member

Откуда: МО Электросталь
Сообщений: 5994
DPH3
Кто и что может предложить-посоветовать? Желательно бесплатное или дешевое )

Elastic Search. MPP сервак колонок ориентированный, который как раз заточен на такие задачи поиска объектов по множеству параметров. Рекомендую почитать.
31 окт 13, 19:50    [15060881]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
ДохтаР
Member [заблокирован]

Откуда: Новоукраинск
Сообщений: 16864
DPH3

По производительности: при нескольких десятках-сотнях запросов в секунду время одного запроса не более 10ms.



На днях меня накормили маркетинговым булшитом
на тему SAP HANA
Обещали суппер-пупер скорострельность.
1 ноя 13, 19:30    [15066974]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
Yo.!
Guest
ASCRUS
Elastic Search. MPP сервак колонок ориентированный, который как раз заточен на такие задачи поиска объектов по множеству параметров. Рекомендую почитать.

на 10 млн MPP ... сурово ...

я бы проголосовал за EAV и mysql/myisam. имхо и то и другое для подобных задач создавали.
2 ноя 13, 00:32    [15068085]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
miksoft
Member

Откуда:
Сообщений: 38920
Yo.!
я бы проголосовал за EAV и mysql/myisam. имхо и то и другое для подобных задач создавали.
Не слишком хорошая комбинация, имхо. Запросы написанные "в лоб" работают крайне медленно, приходится извращаться, чтобы работало быстро. Хотя, возможно, за последние пару лет оно поменялось в новых версиях, но я что-то сомневаюсь.
2 ноя 13, 00:38    [15068110]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
lookat
Member

Откуда:
Сообщений: 135
DPH3,

Есть интересная реализация на C#
http://velocitydb.com

Удачи
2 ноя 13, 04:08    [15068458]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
lookat
Member

Откуда:
Сообщений: 135
DPH3,

А если нужен plain old SQL, то вот:

http://www.kognitio.com/free/

Удачи
2 ноя 13, 04:13    [15068463]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709
DPH3
А какие есть разумные решения для такой задачи:
1. Есть достаточно небольшое (около 10 млн.) объектов.
2. У каждого объекта около сотни параметров, некоторые параметры общие для всех объектов, некоторые - только для малой части. Всего различных параметров - около 10 000.
3. Параметры - разные (числовые, строковые, булевские), с очень разной селективностью.

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

По производительности: при нескольких десятках-сотнях запросов в секунду время одного запроса не более 10ms.

Обновления достаточно редкие, можно делать, например, пачками раз в несколько минут.
Транзакционной целостности и непротиворечивости не требуется.

Я понимаю, как это сделать "ручками", на чистой Java. И тут есть куча плюсов, типа специальных стратегий хранения для отдельных параметров. Но как-то не хочется изобретать велосипед и самому придумывать оптимизатор запросов.

Попытки использовать in-memory db (например, h2) пока не радуют, долго отрабатывает.
Платить за TimesTen или solidDB не хочется )
Задача, конечно, похожа на OLAP, но в OLAP-системах я совсем плохо разбираюсь (

Кто и что может предложить-посоветовать? Желательно бесплатное или дешевое )


Могу посоветовать бесплатный virtuoso 7.
2 ноя 13, 07:18    [15068579]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
DPH3
Member

Откуда:
Сообщений: 456
Yo.!
я бы проголосовал за EAV и mysql/myisam. имхо и то и другое для подобных задач создавали.

Э, EAV на 1млрд. записей с тысячью индексов - и на mysql? Не смешно.
2 ноя 13, 19:32    [15069727]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
SergSuper
Member

Откуда: SPb
Сообщений: 5488
А контекстной поиск тут не может помочь? Формирует по установленным атрибутам некое текстовое поле, и ищем в тексте
(я сам с контекстом поиском дела не имел, но просто как идея - имеет она право на существование?)
2 ноя 13, 20:37    [15069972]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
Yo.!
Guest
DPH3
Э, EAV на 1млрд. записей с тысячью индексов - и на mysql? Не смешно.

"индусам" может не смешно, а так половина инета до сих пор на mysql сидит и посерьезней базы крутят. yahoo заметно серьезней поисковый индекс держали на mysql лет 15 назад. хотя если запихать весь индекс в одну таблицу или найти, где в EAV тысячу индексов повесить ...
4 ноя 13, 23:40    [15076079]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
Пилот Пиркс
Member

Откуда: Москва
Сообщений: 352
Мысль 1
По идее колоночные базы должны давать такую хорошую скорость на фильтрах по 5 параметрам, за счёт хранения колонок вместе, эффективной компрессии, и поиск х=3 and y=4 позволит базе сделать что-то вроде bitmap merge, что должно быть страшно эффективно. Попробуйте http://www.vertica.com/, на последнем Highload++ очень хвалили. До террабайта вроде как бесплатно. Единственное, что такого рода базы заточены под кластера машин и большие объёмы...


Мысль 2
Насчёт 10 ms не уверен что это вообще реально. "результат в сотни-тысячи объектов" за 10 ms надо ещё успеть с сервера выкачать...

Мысль 3
Большинство SQL баз (бесплатных, по крайней мере) плохи из-за того, что не умеют занимать все ядра на 1 запрос. Можно попробовать распилить базу на 10 бакетов по 1m записей и сделать поверх них map-reduce запрос. Ну или больше бакетов, если у вас есть больше ядер :) Hadoop stinger например умеет map-reduc-ить SQL запросы на кластер машин. ИМХО такой подход имеет больше всего шансов сработать и выжать 10 ms latency.
5 ноя 13, 00:19    [15076225]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
DPH3
Member

Откуда:
Сообщений: 456
Краткое резюме по текущим опытам.
Экспериментировал на "микробазе": 500 000 записей, 6 параметров, покрытие от 10 до 100%, количество различных значений параметров от 10 до 10000.

Вообще, выбрать из такой базы по нескольким полям с хорошей селективностью несколько сотен записей - достаточно простая задача. В более-менее разумное время (20ms, без суровой оптимизации) вписалась и H2 DB (в in-memory embedded режиме) и SOLR (запущен в отдельной JVM на той же машине).

Но вот как только требуется отдать более 1000 записей (а такие сценарии вполне возможны), как начинаются изрядные тормоза. У h2 поменьше, у SOLR побольше.

Самодельное "наколеночное" решение (java, хранение в hashmap/SortedSet, примитивнейший оптимизатор) раз в пять-десять быстрее на малых объемах отдаваемых данных. На больших объемах разница еще заметнее.

Подозреваю, что проще уже будет доделать свое собственное. Если будет время, попробую еще Vertica. Но есть подозрение, что там надо будет еще выкурить кучу мануалов для правильной оптимизации, а это по ресурсам будет дороже, чем доделать свое...
6 ноя 13, 01:02    [15082064]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
DPH3
Member

Откуда:
Сообщений: 456
Yo.!,
Я, конечно, знаю, как заставить летать такую задачу на MySQL. С разнообразными memory table, хитрым шардингом и практически ручными join-ами. Но это будет дороже, чем просто написать все свое на чистой java (так как, по сути, и сведется к созданию собственной БД).

Как выглядят большие базы данных на MySQL я тоже навидался - и вот совершенно не хочу такого делать самостоятель. К счастью, у меня нет унаследованных проблем от стадии студенческого стартапа.
6 ноя 13, 01:06    [15082084]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
DPH3
Member

Откуда:
Сообщений: 456
Пилот Пиркс
Мысль 1
По идее колоночные базы должны давать такую хорошую скорость на фильтрах по 5 параметрам, за счёт хранения колонок вместе, эффективной компрессии, и поиск х=3 and y=4 позволит базе сделать что-то вроде bitmap merge, что должно быть страшно эффективно.

По-сути, я такое у себя в памяти на java и делаю. Пока основные беды - в запросах по двум полям с плохой селективностью (типа, join по двум выборкам по 100 000 записей в каждой), тут производительность сильно падает. Тут как раз bitmap merge даст хорошую прибавку и реализовывать просто )

Мысль 2
Насчёт 10 ms не уверен что это вообще реально. "результат в сотни-тысячи объектов" за 10 ms надо ещё успеть с сервера выкачать...

Ну, в случае собственной реализации выкачивать даже не нужно, результат запроса прямо на сервере может и пожить )

Мысль 3
Большинство SQL баз (бесплатных, по крайней мере) плохи из-за того, что не умеют занимать все ядра на 1 запрос. Можно попробовать распилить базу на 10 бакетов по 1m записей и сделать поверх них map-reduce запрос. Ну или больше бакетов, если у вас есть больше ядер :) Hadoop stinger например умеет map-reduc-ить SQL запросы на кластер машин. ИМХО такой подход имеет больше всего шансов сработать и выжать 10 ms latency.

Это как-то получается уже подороже, нежели самому сделать. Хотя идея правильная, как только выйду за пределы одной машины - придется такое реализовывать в любом случае.
6 ноя 13, 01:19    [15082116]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
ASCRUS
Member

Откуда: МО Электросталь
Сообщений: 5994
DPH3
Краткое резюме по текущим опытам.
Подозреваю, что проще уже будет доделать свое собственное. Если будет время, попробую еще Vertica. Но есть подозрение, что там надо будет еще выкурить кучу мануалов для правильной оптимизации, а это по ресурсам будет дороже, чем доделать свое...

Там ничего курить не надо. Но Вертика не для этих задач заточена. Еще раз рекомендую вам посмотреть elastic search, который делает именно то, что вам требуется и заточен на такого рода задачи.
6 ноя 13, 16:11    [15085650]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
DPH3
Member

Откуда:
Сообщений: 456
ASCRUS
Там ничего курить не надо. Но Вертика не для этих задач заточена. Еще раз рекомендую вам посмотреть elastic search, который делает именно то, что вам требуется и заточен на такого рода задачи.


Я, вообще-то, уже выше писал про эксперименты с SOLR. Как раз для этого типа задач (мало данных, нет требований к real-time indexing) SOLR работает несколько быстрее. Внутри то у них обоих Lucene. Увы, требуемых результатов не получил. На маленьких выборках еще более-менее нормально, хотя и на пределе, но вот при попытке join по нескольким выборкам с плохой селективностью производительность падает категорически, похоже, внутри там все-таки loop join.

Так что все-таки elastic search/SOLR/Lucene для этой задачи не подходит.
6 ноя 13, 17:18    [15086230]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
ASCRUS
Member

Откуда: МО Электросталь
Сообщений: 5994
DPH3
Так что все-таки elastic search/SOLR/Lucene для этой задачи не подходит.

Жалко. Видел аналогичный проект, там эластик на ура вписался. Видимо или проектирование структуры по другому было или часть требований легче, чем у Вас. Можете тогда действительно попробовать Вертику, она с джойнами хорошо дружит и дополнительно потом под разные группы запросов можно проекции накатать. Для Ваших объемов никакой оптимизации сервера не потребуется, потом только пулы под группы пользователей разве что расписать, чтобы оптимизировать пиковые нагрузки. Но у Вертики в минусах для вас думаю будет то, что этот сервер изначально на большие объемы рассчитан, поэтому хоть данные ищутся очень быстро, никакого кэширования данных в памяти не предусмотрено. То есть диски работают постоянно. Здесь еще бы очень хорошо смотрелся Sybase IQ, который и колонкоориентированный и кэширует отлично. Но у него бесплатных версий нет к сожалению, нужно лицензию на ядра покупать.
7 ноя 13, 19:39    [15093497]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
DPH3
Member

Откуда:
Сообщений: 456
ASCRUS
Жалко. Видел аналогичный проект, там эластик на ура вписался.

Я сам на SOLR надеялся, благо для полнотекстового поиска все равно его используем.

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

P.S.Вообще на выбор чужого решения ушло больше времени, нежели на "написать свое" )
7 ноя 13, 23:14    [15094339]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
mayton
Member

Откуда: loopback
Сообщений: 53029
DPH3, тут скорее всего поможет некий вариант тюнинга материализоанных представлений
для однородных запросов. Например даже если у объекта 100 параметров, пользователь
обычно ищет по дате и по имени или классу объекта. Тоесть 10 млн. индексируются
или сегментируются или кластеризуются или еще бог весть как делятся но на
2 или 3 оси (DATE,NAME, CLASS).

А оставшиеся атрибуты сливаем обычным списком, текстом, XML-ем иди ДжСоном.
Они будут просто уточняющмими атрибутами. И мы будем считать что именно за счёт
сегмнентации 10 млн на 3 оси мы и получим отклик в 10 милисекунд чтобы выдать
первую страницу (page) объектов. А дальше уже обычным текстовым поиском
с Solr (Lucene) или просто вручную фильтруем.
11 ноя 13, 17:25    [15110625]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск по множеству параметров  [new]
DPH3
Member

Откуда:
Сообщений: 456
mayton
DPH3, тут скорее всего поможет некий вариант тюнинга материализоанных представлений для однородных запросов. Например даже если у объекта 100 параметров, пользователь обычно ищет по дате и по имени или классу объекта. Тоесть 10 млн. индексируются или сегментируются или кластеризуются или еще бог весть как делятся но на
2 или 3 оси (DATE,NAME, CLASS).

А оставшиеся атрибуты сливаем обычным списком, текстом, XML-ем иди ДжСоном.
Они будут просто уточняющмими атрибутами. И мы будем считать что именно за счёт
сегмнентации 10 млн на 3 оси мы и получим отклик в 10 милисекунд чтобы выдать
первую страницу (page) объектов. А дальше уже обычным текстовым поиском
с Solr (Lucene) или просто вручную фильтруем.


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

Вообще, для меня было некоторым откровением, насколько просто написать работающую in-memory (not key-value) storage под специфические требования (и только под них). Понятно, что я выплеснул 99% функциональности любой нормальной СУБД - но они мне и не нужны. А нужное оказалось сделать достаточно просто.
12 ноя 13, 13:32    [15114816]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Сравнение СУБД Ответить