Как битмап-индексы помогают быстро искать по каталогам. Денис Колпаков, Авито

Это рассказ о том, как как мы решили продуктовую задачу по быстрой фильтрации модификаций в каталогах: начиная от сбора требований до финального решения на продакшене. В процессе расскажу о контексте и проблематике с которой столкнулись, функциональных и нефункциональных требованиях к ручкам фильтрации. Также какие решения и алгоритмы мы рассматривали, их эволюцию от MVP до production ready (как решение «в лоб» эволюционировало в достаточно эффективный алгоритм основанный на битмап индексах). В конце поделюсь тем, каких результатов нам удалось добиться, какие есть плюсы и минусы у выбранного подхода, а также о дальнейших шагах в поддержке данного решения.