Поиск данных с учетом большого числа критериев

Question

[VBart]

Вот сразу вспомнилось, примерно похоже на мою задачу:
Яндекс.Маркет подбор мобилок

Взгляните на панель справа, дофига всяких критериев выбрать можно и работает очень быстро. Как делаются подобные штуки? Какие подходы используются, устройство базы данных? В идеале нужен некий универсальный механизм, который мог бы искать по любому произвольному очень большому набору критериев, по огромному количеству объектов (>100 000) с разным набором полей, делать это максимально быстро, по возможности обходясь без over 9000 серверов.

Comments

[meettya]

" В идеале нужен некий универсальный механизм" — сферический конь в вакууме.
Задача-то какая, среда, условия? Делать выборку из небольшого объема объектов (не говорите никогда бд-кам, что > 100 к объектов — это много ) по набору параметров проблемы-то нет, в идеале-то :)

[VBart]

Задача похожая на яндекс маркет. Будет база товаров (несколько сотен тысяч и расти), каждый товар может содержать произвольный набор данных, нужно делать выборку на запросы с произвольным набором параметров. Таких запросов будет сыпаться по нескольку тысяч в секунду. Главное выборка, запросов на изменение будет значительно меньше и их время выполнения не очень критично.

[meettya]

ИМХО — на такой частоте подобных запросов вам ПРИДЕТСЯ продумывать индексы или материализацию заранее, в чистой динамике эта задача «в лоб» вряд ли решаема.

[VBart]

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

Алгоритмически все действо я представляю себе так. У нас есть b-tree «значение — id-товара» на каждое поле доступное для выборки (причем их можно разнести по разным серверам и вообще неплохо масштабировать), из них легко брать срезы. Поступает запрос, по каждому параметру присутствующему в запросе берется срез, так, что в итоге у нас получается набор сортированных массивов содержащих id-товаров. Остается найти между ними пересечение, начать можно с самого маленького массива, не такая уж затратная операция. В итоге, получаем набор id-товаров, по котором уже надо выбрать набор соответствующих объектов из базы.

В общем, с помощью чего это можно провернуть быстро, масштабируемый и чтобы не писать своих велосипедов?

[VBart]

Смотрите, b-tree из 100000 наборов «значение_поля — id_товара» с большой вероятностью вполне неплохо будет помещаться целиком в ОЗУ. И выборка среза по нему это очень быстрая операция. Результаты выборок по одному из полей, довольно часто будут помещаться даже целиком в процессорный кэш, после поочередного нахождения пересечений между подобными выборками, количество оставшихся id будет стремительно уменьшаться. Все эти операции весьма быстрые, и не представляют существенных проблем для современных серверов, да и легко параллелятся, не вижу что бы мешало делать их тысячами в секунду на десятке, может быть нескольку десятков среднестатистических машинок.

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

Answer 1

[KLUBS]

Посмотрите в сторону Entity-attribute-value model.

Также хороший ответ на StackOverflow в теме Product table, many kinds of product, each product has many parameters

Comments

[VBart]

Хм, думаете EAV в RDBMS наилучший способ решения данной задачи? Мне вообще всегда казалось, что EAV это костыль для запихивания объектов в реляционную модель, когда нет других вариантов, или я ошибаюсь? и это весьма производительное решение?

[KLUBS]

Костыль не костыль. Есть второй вариант — Для каждого типа товара своя таблица… Но сколько типов товаров и сколько таблиц? Это тоже костыль. Для реляционных БД нет нормального решения. Мне нравится EAV (след. сайт как раз буду делать с ним)

На StackOverflow как раз написаны "+" и "-". И ниже еще обсуждение

[VBart]

Я и не спрашиваю решения конкретно для «реляционных БД». Если кто-нибудь скажет, о, слушай, да с твоей задачей прекрасно и быстро справится такая-то БД, но она на графах, смотри… <cut> — вот как оно с этим справляется. Я скажу — о, круто, спасибо, попробую! На RDBMS свет клином не сошелся.

Answer 2

[asm0dey]

В Java это очень удобно помогает делать Spring Roo с использованием finder'ов. Хотя, вероятно, он не является идеальным инструментом для решения данной задачи.

А в какой среде эту задачу решаете Вы?

Ставлю себе RSS на эту тему — мне тоже очень интересно.

Comments

[VBart]

Что вы понимаете под средой? Я вот и пытаюсь выяснить, с помощью чего данную задачу лучше решать.

«Spring Roo с использованием finder'ов»
Это кажется что-то вроде ORM? О нет, только этого еще не хватало, всяких замедляющих прослоек.

[asm0dey]

Хм. Ну я не считаю, что ORM замедляет Вашу работу, при условии, что сервер приложений и сервер базы данных — разные машины.
ORM транслирует простые и понятные простому человеку запросы в оптимизированный SQL. При этом база данных не теряет в скорости работы.
А finder'ы d roo — просто удобный способ генерации необходимых запросов.
Бейте меня ногами, но существуют гигантские кучи хэви-продакшн проектов, которые работают с ORM.
И да, 100 к объектов — это немного. Вот 100 кк…

Answer 3

[meettya]

«Будет база товаров (несколько сотен тысяч и расти), каждый товар может содержать произвольный набор данных, нужно делать выборку на запросы с произвольным набором параметров»
ИМХО — жесткая типизация параметров в отдельные справочники даст возможность быстрого выбора и сравнения, но расплачиваться будете скоростью заполнения справочника.
А по архитектуре — многоуровневый кеш и хорошое продумываение структуры базы. Если не боитесь — noSQL базы с map/reduce или колоночные БД. Будет зоопарк, зато (по идее) быстрее работать. Или хранить свойства в классической реляционной и хитрая материализация на чем-то типа Redis — поиск по параметрам — классический хеш, если я правильно понимаю задачу.

Comments

[VBart]

Я вообще не считаю, что «каждый товар может содержать произвольный набор данных» как-то хорошо вписывается в RDBMS. Я нигде не писал, что речь идет об SQL.

«noSQL базы с map/reduce»
Какую? CouchDB — отсутствуют динамические запросы, map/reduce нужно продумывать заранее, и все запросы характерны выборкам по b-tree, т. е. максимум срез от сих до сих, а пересечения уже самим искать. Либо, если только Lucene прикручивать, либо я что-то про нее не знаю еще.

MongoDB — ограничения на количества индексов и коллекций, как-то пугают. А индексов нужно судя по всему великое множество.

RIAK — пока не очень понимаю, как оно применимо для моей задачи.

Answer 4

[xdenser]

Нормально задача решается на RDBMS. Просто нужно описывать не модель хранения продуктов, а модель модели хранения продуктов. Т.е. набор метаданных и автоматического создания скриптов на основе их.
Все равно продукты (точнее новые типы продуктов) добавляться у вас будут реже, чем искаться ( я так понимаю). Так что можно время от времени подстраивать внутреннюю модель автоматом.
В таких системах, кстати, не поиск самое сложное и главное. Там все оптимизируется понятными методами.
Намного сложнее саму базу содержать в актуальном и полном виде. Как этот вопрос решается?