Натолкнулся в разделе QA на интересный вопрос. Ответ на него заставил написать эту статью как бОлее полный ответ на вопрос «как организовать поиск по множеству параметров, как в Яндекс-маркете, например».
Я знаю, что на Хабре, да и вообще есть много сторонников noSQL решений (сам не без греха), но все же я сторонник сначала подумать, а уже потом выбирать решение.
Итак, что имеем в «ДАНО»
Истерика наступала от понимания, что надо обрабатывать более 100 запросов в секунду, а для этого придется продать «трешку» с видом на Кремль и купить еще железа.
Итак, начинаем думать, как сэкономить кучу денег и часть положить в свой карман в виде премии.
Хочу сразу заметить, мы не задаемся целью СРАЗУ получить список нужных строк из базы. Нам нужно сделать префильтрацию для ускорения процесса поиска и фильтрации.
Для начала все наши чекбоксы, которые имеют всего 2 варианта значения, мы преобразуем в биты и сгруппируем в одно «число». В нашем случае данное число будет 120 битным (128 битным для ровного счета). Это будет наш первый «индекс». По нему мы всегда сможем отфильтровать те товары, которые соответствуют нашим условиям. На практике, в среднем, таких товаров не более 10 тыс на всю базу. Остальные параметры можно смотреть уже только в этих 10 тыс товарах, а не «лопатить» всю базу.
Любой диапазон (рост, вес, талия, объем бюста) можно разбить на интервалы и пронумеровать их. Поделим на 256 частей. Цифра взята «с потолка». В любом случае мы для диапазона 100$ — 1200$ мы получим 2 числа. Если взять на 1 — 100$ при максимуме в 25500$, то наш диапазон мы можем записать как 2|12 — по факту это 16 битное число. Таких чисел у нас будет по числу возможных диапазонов. Если их менее нескольких, то на этом мы остановимся, если их 100-10000, то все сложнее. Мы не можем адекватно быстро искать по 200-20000 битному ключу. Да и не станем, мы просто высчитаем его md5, а для ускорения процесса еще и преобразуем все в 128 битное число (каких то жалких 16 байт). В сочетании с множеством «чекбоксов» мы получим еще более точную выборку.
Алгоритм поиска данных значений с доп. параметром «не важно» почти похож на вариант с чекбоксами, за исключением того, что мы в 1 индекс записываем только да/нет (и 0, при выборе «не важно»). Во второй индекс будем ставить 0 при варианте «не важно» и 1 при любом другом.
Итого получаем 2 индекса:
1 индекс: 01010000001010101010001
2 индекс: 01111101110111101110111
Домашним заданием будет построить через Xor|And|Or запрос в котором мы обнулим все незначащие биты по индекс2 и сравним с индекс1.
Итак, мы из 12 млн записей нашли 0-100-500 подходящих по условиям. Именно эти записи уже стоит проверять целиком (120 битное поле чекбоксов, диапазон и множество «Да/нет/не важно»). Согласитесь, что полная проверка среди пары сотен строк — это намного быстрее, чем полноценный поиск.
Вариант с преобразованием длинного ключа в короткий, путем, допустим, шифрования, достаточно удобен для проведение префильтрации данных. При этом, если мы работаем с SQL, то выборку префильтра можно для ускорения хранить в MemTable и уже с этими данными проводить полноценную фильтрацию.
Подобный алгоритм Используется нами и в фильтре текстов по шинглам, когда из контрольной суммы получаем 32 битное число, которые сравнивать быстрее, чем 128 битные.
Подобная методика работает и в одной специализированной системе хранения документов, что позволяет в микросекунды найти в 2.2Gb базе текстов ссылки на документы, где находится искомое слово или фраза. Но, об этом чуть подробнее в другой статье.
Я знаю, что на Хабре, да и вообще есть много сторонников noSQL решений (сам не без греха), но все же я сторонник сначала подумать, а уже потом выбирать решение.
Итак, что имеем в «ДАНО»
- Имеем 120 чекбоксов — вариант 1/0
- Имеем 30 «радио» с выбором «да/нет/не важно»
- Имеем 2-3 слайдера для указания диапазона цен/размера чего нить
- Имеем самое главное: 12 млн записей в БД.
- Имеем Select * From tovar Where (wifi=true) and (led=false) and (type=3) and ….остальные параметры …; со временем выполнения близкому к истерике клиента.
Истерика наступала от понимания, что надо обрабатывать более 100 запросов в секунду, а для этого придется продать «трешку» с видом на Кремль и купить еще железа.
Итак, начинаем думать, как сэкономить кучу денег и часть положить в свой карман в виде премии.
Хочу сразу заметить, мы не задаемся целью СРАЗУ получить список нужных строк из базы. Нам нужно сделать префильтрацию для ускорения процесса поиска и фильтрации.
Чекбоксы
Для начала все наши чекбоксы, которые имеют всего 2 варианта значения, мы преобразуем в биты и сгруппируем в одно «число». В нашем случае данное число будет 120 битным (128 битным для ровного счета). Это будет наш первый «индекс». По нему мы всегда сможем отфильтровать те товары, которые соответствуют нашим условиям. На практике, в среднем, таких товаров не более 10 тыс на всю базу. Остальные параметры можно смотреть уже только в этих 10 тыс товарах, а не «лопатить» всю базу.
Диапазоны
Любой диапазон (рост, вес, талия, объем бюста) можно разбить на интервалы и пронумеровать их. Поделим на 256 частей. Цифра взята «с потолка». В любом случае мы для диапазона 100$ — 1200$ мы получим 2 числа. Если взять на 1 — 100$ при максимуме в 25500$, то наш диапазон мы можем записать как 2|12 — по факту это 16 битное число. Таких чисел у нас будет по числу возможных диапазонов. Если их менее нескольких, то на этом мы остановимся, если их 100-10000, то все сложнее. Мы не можем адекватно быстро искать по 200-20000 битному ключу. Да и не станем, мы просто высчитаем его md5, а для ускорения процесса еще и преобразуем все в 128 битное число (каких то жалких 16 байт). В сочетании с множеством «чекбоксов» мы получим еще более точную выборку.
Да/нет/не важно
Алгоритм поиска данных значений с доп. параметром «не важно» почти похож на вариант с чекбоксами, за исключением того, что мы в 1 индекс записываем только да/нет (и 0, при выборе «не важно»). Во второй индекс будем ставить 0 при варианте «не важно» и 1 при любом другом.
Итого получаем 2 индекса:
1 индекс: 01010000001010101010001
2 индекс: 01111101110111101110111
Домашним заданием будет построить через Xor|And|Or запрос в котором мы обнулим все незначащие биты по индекс2 и сравним с индекс1.
Итак, мы из 12 млн записей нашли 0-100-500 подходящих по условиям. Именно эти записи уже стоит проверять целиком (120 битное поле чекбоксов, диапазон и множество «Да/нет/не важно»). Согласитесь, что полная проверка среди пары сотен строк — это намного быстрее, чем полноценный поиск.
….
Profit!!!
Вариант с преобразованием длинного ключа в короткий, путем, допустим, шифрования, достаточно удобен для проведение префильтрации данных. При этом, если мы работаем с SQL, то выборку префильтра можно для ускорения хранить в MemTable и уже с этими данными проводить полноценную фильтрацию.
Подобный алгоритм Используется нами и в фильтре текстов по шинглам, когда из контрольной суммы получаем 32 битное число, которые сравнивать быстрее, чем 128 битные.
Подобная методика работает и в одной специализированной системе хранения документов, что позволяет в микросекунды найти в 2.2Gb базе текстов ссылки на документы, где находится искомое слово или фраза. Но, об этом чуть подробнее в другой статье.
