Привет коллеги.

Илья. Белая Сова. Дима-Т. Саша-Меркурий. Лётчик Петрав. Изопропил.
Petalvik. Softwarer. Володя двухтысячный. Сидоров. Блажкович. Док. Зяма. Жук-Ботан и прочие почитателю скруля.

Начинаем мозговой штурм. Мы оптимизируем поиск по EAV.

В продолжение моего занудства по поводу EAV-модели и поиска товаров. Дима уже вкурсе.
Для всех остальных - вводная:

Дано:

интернет магазин на базе классического стека LAMP (Здесь MySQL можно
заменить на произвольную реляционную DBMS не важно какую. Главное - реляционную).

Список товаров на более чем 10 000 позиций.

Товары побиты на категории (например Холодильники, Плазмы, Печи e.t.c)

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

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

На уровне ТЗ предполагается что база использует модель EAV
как наиболее дешевый и доступный способ реализовать список расширенных
характеристик.

Интернет-магазин находится под постоянной нагрузкой. Поисковые
операции по товарам осуществляются каждую секунду.

Клиенты магазина - люди нетерпеливые и желают очень
быстро получать результаты своих поисков.

Владелец магазина - борется за клиентов и желает создать
самые комфортные условия для быстрой работы.

UI магазина спроектирован таким образом что клиент
ничего не вводит с клавиатуры а только отмечает checkboxes.
Все вещественные характеристики товаров
перед поиском разбиты на группы. Например диагональ плазмы.
Пример:




Что-бы я здесь хотел обсудить. Возможные алгоритмы и структуры данных
которые помогут ускорить поиск по модели EAV.
Можно - доработки к PG и MySQL. Можно - различные варианты кешей.
Можно - использование С/C++ в стеке LAMP. Текстовый поиск,
деревья, JSON, и все что может быть полезно - приветствуется.
На консистентность кеша и БД можно пока забить. Скорость важнее.

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

Мы будем обсуждать инженерный и творческий подход

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

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

Итак начинаем brainstorm!

С уважением
mayton

P.S. Поиск должен быть ультра-быстрым (с) :)

Привет коллеги.

Отвечу всем чуть позже когда доберусь до нормальной клавиатуры.

Всем спосибо за активность

Ого тут текста. Ну ладно. Попробую ответить.

fixxerГулить по словам Faceted index/Faceted search. Вкратце - набор индексов по значениям категорий или отрезкам значений + оптимальное применение набора таких индексов. Умеет любой промышленный индекс сервер, бери любой на вкус, Solr, ElasticSearch, Sphinx, SearchTank.
Добрый день. Большое спасибо за терминологию. Ну... если фасетный - то пускай будет фасетный поиск.
Я не против.

По поводу промышленных индекс-серверов. Solr - это КМК платный продукт на базе технологий Apache Lucene
и возможно еще кое-чего. C Apache Lucene я работал. Это full-text search. Достаточно сложный и избыточный
механизм который созавался для various text и поиска релевантных документов в соответствии с Search Query.
Использовать в данной задаче FTS я считаю немного избыточным т.к. стек у настоящего FTS очень длинный
(есть фаза очистки оригинального текста и приведения его к каноническим формам) а у нас задача более
простая. Найти товар по набору признаков.

ElasticSearch - это ЕМНИП бесплатный вариант Solr (впрочем здесь я могу ошибаться пускай меня поправят).

С продуктами Shinx, SearchTank я не сталкивался и незняю что это такое. Опять-же опираясь на свой тезис
о простом стеке LAML я не хотел-бы переводить обсуждение этой задачи в обсуждение применения конкретного
коробочного продукта.

Akina mayton , давай посчитаем...

Список на 10к товаров. У каждого товара есть несколько характеристик (если посмотреть на том же яндекс-маркете, то в среднем у категории товара их там 20-30, редко более полусотни). К тому же крайне редко попадается характеристика с очень уж обширным диапазоном значений, лично я не видал ни одной, в которой количество значений превосходило бы 64 (или хотя бы приближалось к нему). Но если брать по максимуму... пусть 20к товаров по 50 характеристик, кодирование которых требует 64 битов, это получится порядка сотни мегабайт. Не самый большой объём. А с учётом того, что таблица строго RO - грузим копию таблицы в память, и вот тебе уже минус дисковая подсистема и прирост скорости.
Несколько дополнений. Действительно у товара обычно не более полусотни уникальных характеристик.
Но ваше предположение о том что в целой категории товаров (телевизоры, холодильники) 50 характеристик - неверно.
Технологии меняются каждые 2-3 года и новые характеристики добавляются к новым товарам (SmartTv=true),
а старые постепенно уходят (VGA разъем=true).

Далее. Стопудово у тебя уже есть статистики. Нас интересуют две. Первая - это частота использования той или иной характеристики для фильтрации. Вторая - это селективность характеристики. Это я к чему? к тому, что индексировать по всем возможным совокупностям характеристик - занятие совершенно безнадёжное, но вот выделить основные группы, индексация которых даст значительный эффект (частая применимость и высокая селективность) нужно. Очень желательно, если данных хватит, выделить пары, а то и тройки, самых востребованных групп характеристик для составных индексов. Индекс из совокупности более чем 3 полей, мне кажется, будет маловостребован, и будет работать исключительно префиксом из 2-3 полей - а тогда нафига козе баян?
Я согласен насчет селективности. Но такую характеристику как частота использования мы никак не можем
детектировать. Собственно... это маркетинговая информация которая у нас появится уже в фазе эксплуатации
магазина. Поэтому сейчас мы не можем ее использовать как 100% надежного актора. Хотя заложить в поисковой
механизм популярные checkbox мы можем.

Далее. Индекс из более чем 3х полей - важен и нужен. Это я вам говорю как регулярный клиент магазинов электроники.
И поскольку мы не можем на данном этапе определить маркетинговые свойсвта (или преимущеста) одного атрибута
над другим то я все-таки предлагаю индексировать все.

AkinaЧто имеем в итоге. Работа чисто в памяти, индексный отбор достаточно высокой селективности, и всё это на сравнительно небольшом объёме данных. Не думаю, что скорость работы будет такова, что у посетителей будут поводы для недовольства, даже если использовать "младшие" СУБД (во всяком случае MySQL из лампы должен летать, хотя я бы рекомендовал собирать систему самостоятельно, а не ставить готовый комплекс, начальная настройка делается один раз), просто сервер БД нужно будет настроить должным образом, чтобы он не испытывал проблем ни с памятью под Memory-таблицы, кэш индексов и буферы сортировки, ни с количетсвом процессорного времени. А если претензии по скорости будут - то это будут претензии не к СУБД, а к другим компонентам системы.

Я не знаю - что значит собирать систему самостоятельно. Это - покупка VPS ? И установка вручную PHP, Apache, MySQL?

Dima TЕсли честно не вижу тормозов с классической реляционной структурой.
Накидал по-быстрому

ТаблицаОписаниеCategoryСправочник категорийValueЗначения внутри категорииTovarСправочник товаровAttributeПривязка товаров к значениям
Для ускорения выборок небольшая денормализация: продублировал cat_id из Value в Attribute

Хм... моя модель вышла более скромной. 3 таблицы. Где-то я просчитался?

Dima TА дальше выбираем таким запросом


Не думаю что с твоими объемами будет дольше 10 мс выборка идти. Тем более что запрос отлично параллелится.

Хм... из личного опыта. Запросы с group by ... having всегда работали тяжело и не в OLTP-стиле.

По поводу параллелизма. Для обыкновенных DBMS он остаётся мифом. Практически очень мало
запросов могут в explain plan выдать признаки параллелизма. Только Oracle при условии что
таблицы были создани о опцией partitioning или с хинтом +parallel могут генерировать запуск
map-reduce процессов для генерации выборки. Для других dbms - я не вкурсе но у меня
есть предположения что параллелизм остаёся несбыточной мечтой.

Dima TПро размер:
Предположим в среднем 50 атрибутов на товар, тогда по размеру Attribute получится примерно 500 000 записей, 16 байт на запись итого 8 Мб.

Можно затестить, надо только генератор данных сделать
Разрази меня гром. Я не понимаю как ты посчитал про 8 мегабайт. Здесь оценки можно уверенно дать
только после моделирования. Опции хранения - это самая загадочная часть dbms и здесь я-бы не стал
делать прогнозы.

По поводу генерации данных. Это больной вопрос. Забегая вперед я даже скажу что он на 60%-80% определяет
саму постановку. Тоесть эффективность решения нашей задачи не столько зависит от формул или технологий
сколько от гистограммы наших данных и характера нагрузки.

По сабжу я пока решил сделать так. Я нагуглил штук 10 магазинов стройматериалов и скачал их прайсы в виде
xls, и думаю что если их обработать и загрузить то будет вполне себе нормальный набор для тестов.

Dima TДавай прикинем: допустим очень дотошный пользователь натыкает фильтр по 10 категориям, под одну 80% товаров, под другую 20% и т.д. Думаю в среднем 30-50% товаров на категорию, тогда 10*50%=500% товаров в конечной выборке, или 10000*500% = 50 000 записей. Как-то ни разу не дофига.
В данной задаче я надеюсь что мы придем к мысли что нужен custom-алгоритм и структура данных для кеша
характеристик товаров. Но перед тем как мы к этому придем нужно сначала взять MySQL/PG и выжать ее как лимон.
Тоесть понять на какие цифры можно расчитывать. Для простоты будем считать что данные даже лежат в буферном
кеше блоков.

Тоесть даже дисковый IO мы уберем из нашей формулы.

Dimitry SibiryakovЭто очень упрощает задачу. Главная таблица связи товаров с их характеристиками упрощается, поскольку значение характеристики представлено одним полем-ссылкой на справочник групп. Критерии в поисковом запросе сводятся к "Тип_характеристики=? and Группа_значения=?", что покрывается индексом. Отсутствие having в запросе позволяет нечёткий поиск по релевантности.
Хм... мне не очень нравится постановка нечеткого поиска. Я как клиент интернет магазинов
желаю точный поиск. К примеру я указал что я ищу зеркальный фотик где производитель никон
и матрица в 24 мегапиксела и я хочу получить список именно из этих позиций товара без всяких
посторонних похожих.

MasterZivDima TMasterZiv, внимательнее на структуру посмотри, там все уже есть и дополнительно ничего не надо.
Все решается тем запросом, который я написал. Запрос строится динамически.



А, так это у тебя не классическая схема, а наоборот.
Я прочитал "классическая", и дальше не глядел даже :-)
Коллеги!

Я предлагаю не спекулировать термином классического или не классического .

Есть LAMP. И есть база с товарами. Надо извлекать товары как можно быстрее.

Dima TAkinaпропущено...
Планировщик - он один на инстанс сервера, и работает в одном потоке. При большом потоке запросов он запросто может стать узким местом.
Можно конкретики: где именно он однопоточный? О каком сервере речь? Я честно сознаюсь что в эту тему никогда не вникал, но не вижу проблем сделать его многопоточным. Тут нет ничего требующего однопоточности. План строится на статистиках, а они не очень меняются, да даже если и меняются и план будет построен на предыдущей статистике, то это просто проблема одного конкретного запроса.
Здесь я - пас. Я не знаю какие планировщики в LAMP.

Если вы смоделируете узкое место в optimizer - буду рад.

AkinaDima Tв ТЗ было по другомуНу тогда берём любую СУБД с олапкой - самая для него задача.
Хм... ну попробуйте найти такую любую.

Насколько мне известно OLAP бывает разных под-типов. И тот который (R)OLAP (реляционный OLAP) по сути
является программной надстройкой над обычной DBMS и я сильно сомневаюсь что эта надстройка
будет эффективнее чем наш поиск по EAV.

А коробочные решения OLAP - обычно дороги и требуют большой сноровки в изначальной конфигурации.

Может кто-либо из вас похвастаться что он конфигурил OLAP-системы под ключ?

SashaMercuryПрошу прощения за оффтоп. Дмитрий, не первый раз встречаю что атрибуты отношений имеют префикс относящийся к имени отношения, но никогда не понимал зачем это. Когда я спрашивал, мне говорили о том, что ребятам элементарно join ить удобно, однако разве кто-то используется JOIN без псевдонимов. В том случае, если один из атрибутов отношения является foreign key то я согласен с тем, что желательно добавить префикс указывающий на имя таблицы, в противном случае, мне до сих пор не понятно, зачем это нужно, видимо в силу малого опыта в области баз данных. Объясни пожалуйста для большинство все так делают, ибо это вопрос уже несколько лет лежит у меня в голове фоном))) Надеюсь что это холивар, если так, то удаляйте сразу мое сообщение, а то основная тема загнется
Это действительно холивар и оффтоп. И лучше эту тему поднять отдельным топиком.

Dima TНе уверен что так происходит, но тут после выборок подзапросов серверу можно снимать блокировки с рабочей таблицы, сливать результат union во временную таблицу и group by делать по ней. Про тяжесть уже писал, group by по 50к записей это не много.

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

По поводу 50k записей я погорячился. Может их будет даже меньше. Но в любом случае
желательно убрать из стека такие операции как write temporary table при формировании
курсора.

Dima TВсе просто: таблица Attribute это привязка товара к галочке. Т.е. чтобы товар "ТВ Gnusmas 40" FullHD" найти галочками, то надо этот товар привязать к двум Value, т.е. 39"-43" и FullHD. Это две записи в таблицу Attribute.
Ты написал что товаров 10000, Akina 20009771 предположил что привязок не более 50 на товар, вот я и прикинул 50*10000.

А ну ОК.

Выделение характеристик и привязку к ним кто будет делать? Жопа в этом, написания в прайсах не нормализованы, я про ИИ потому и писал что сложная это работа выделять характеристики и привязывать к ним.
Да это сложная работа. И я думаю она пойдет отдельным топиком. Подключу энтузиастов к парсингу.
А кто распарсит быстрее всех - пополню телефончик.

Dima TСибиряков прав: если сначала выдать то что совпадает по всем трем характеристикам (count(*) = 3), затем по двум, то никому хуже не будет. Покупатель в начале увидит то что просил, но дальше вполне может оказаться близкое, но то что не просил. Возможно оно больше его устроит по каким-то пятым свойствам не упомянутым в фильтре.
Я приму это как доп-фичу. Но основной business-req. должен звучать именно как точный поиск по
атрибутам товара.

Вот модель, которую я накрапал в четверг. Она отражена в скриншоте с Modeller.

Дима. К тебе просьба оценить разницу между твоей и моей моделью. Может я чего-то недосказал
или наоборот ты глубже сделал нормализацию.

Вобщем хотелось бы прояснить почему у нас число таблиц разное.