Поиск по произвольным параметрам

Иногда (часто) во время разработки веб-сайта возникает необходимость реализовать поиск с фильтрацией, и отсортировать результаты по какому-то фиксированному полю: например, поиск товаров в интернет-магазине, поиск туров в турагентстве, показ логов с фильтрацией по содержимому, и т.д. Очень часто бывает так, что фильтрация должна осуществляться чуть ли не по любому полю (а полей десятки), а записей тысячи или даже миллионы. Если данных много, или же нужно их часто обновлять, то индекс на каждое поле не создать, ибо много места будут занимать, или же будут создавать слишком большую нагрузку на диск при записи, и приходится что-то придумывать. Давайте что-нибудь придумаем.

Тривиальный случай

Давайте сначала рассмотрим ситуацию, когда данных мало, запросов на чтение и запись тоже мало, требований по скорости тоже особых нет. В таком случае можно просто использовать базу данных (MySQL, Postgres, SQLite, не важно) и осуществлять фильтрацию и сортировку простыми WHERE и ORDER BY. Индексы можно даже не создавать, ну или создать индекс только для того поля, по которому будет осуществляться сортировка (далее это поле будем называть timestamp для простоты, ибо зачастую сортировка нужна именно по времени).

Много чтения, мало записи, время отклика не очень важно

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

SELECT * FROM products
WHERE
  name LIKE '%пылесось%' AND
  (price BETWEEN 1 AND 200) AND
  brand NOT IN ('рога', 'копыта') -- индекс тут не создать
ORDER BY timestamp DESC
LIMIT 100

По сути, поиск всегда будет идти сверху вниз по индексу timestamp и просматривать каждую строчку, пока не наберется 100 записей, которые удовлетворяют критериям поиска. Проблема такого наивного подхода заключается в том, что строки в базе данных не будут физически упорядочены по timestamp, а будут, вероятнее всего, расположены в порядке их вставки в базу данных, поэтому такой запрос в худшем случае будет осуществлять случайное чтение с файловой системы на каждую строчку, что весьма неэффективно (например, в моих бенчмарках SQLite способен читать лишь около 500 000 строк в секунду таким способом, на одно ядро процессора). Вторая проблема будет поджидать Вас, если вдруг таблица products вытеснится из кеша и придется читать каждую строчку случайным чтением с диска: даже SSD вряд ли выдаст вам больше пары сотен тысяч случайных чтений в секунду, а скорее всего меньше, особенно если ваш диск — сетевой, как это часто бывает в облаках. Про HDD и упоминать не хочется: тут больше пары сотен случайных чтений с диска ожидать не приходится.

Кластерный индекс

Многие СУБД поддерживают так называемые кластерные индексы, когда данные хранятся вместе с первичным ключом в виде B-дерева. Если создать составной кластерный индекс, который будет содержать в себе достаточно полей, чтобы быть уникальным, и первым полем будет timestamp, то данные будут кластеризованы по timestamp, и чтение из таблицы при запросах вида ORDER BY timestamp будет идти очень эффективно (20 млн строк в секунду на ядро в случае SQLite), и будет при этом идти в порядке возрастания (или убывания), что позволяет прекратить поиск сразу как только нужное количество записей найдено. В случае, если таблица не в кеше, то чтение с диска будет идти относительно крупными блоками, что намного эффективнее чтения по одной строке.

В MySQL первичный ключ движка InnoDB всегда представляет из себя кластерный индекс, а в SQLite кластерный индекс можно создать, используя опцию WITHOUT ROWID. Ваш хваленый PostgreSQL, кстати говоря, кластерные индексы из коробки не поддерживает.

Недостатки кластерного индекса

Помимо очевидного недостатка, что набор полей кластерного индекса должен быть уникален (т.е. AUTO_INCREMENT использовать не выйдет), есть и менее очевидный: скорость вставки. Поскольку данные всегда поддерживаются в полу-отсортированном состоянии в B-дереве, то вставка неотсортированных данных будет вести к необходимости перезаписи большого количества блоков на диске (а не небольших блоков только для изменившийся колонки). Кластерный индекс не будет позволять вставлять много строк в секунду, если данные не находятся в порядке возрастания первичного ключа (а это гарантировать можно не всегда).

Много чтения, мало записи, время отклика минимальное

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

Для такого случая подходит так называемый bitmap index. При использовании bitmap index вы создаете массив в памяти, уже отсортированный по нужному нам полю (в данном случае timestamp desc), и этот массив состоит из наборов бит. Значение каждого бита соответствует какому-то возможному значению фильтра, и выставляется в 1, если товар попадает под фильтр, и 0, если не попадает.

Пример:

0001110010101101101 <- первый элемент массива
0001001001100101111 <- второй элемент массива
...

   ^ четвертый бит равен 1, если "диагональ экрана от 15'' до 23''"
     ^ шестой бит равен 1, если "средний рейтинг товара выше 4.0"
      ^ седьмой бит равен 1, если "средний рейтинг товара выше 4.5"

Поиск по такому массиву в памяти осуществляется созданием маски поиска (например, если мы хотим найти товары с рейтингом выше 4.5 и диагональю от 15'' до 23'', то мы создадим маску 00010010 — четвертый и седьмой биты выставлены), и с помощью обычного логического "И" (оператор &) отсеем значения, которые не равны маске после применения "И":

mask = 0x12;
for (...) {
    if ((bitmap[i] & mask) != mask) continue;
    ...
}

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

Недостатки bitmap индекса

Bitmap индекс хорош только тогда, когда возможных вариантов фильтра относительно немного. Также, достаточно очевидно, что такой индекс не будет работать в случае необходимости фильтрации по строке. Поскольку данные в массиве должны уже быть отсортированы, индекс нужно периодически перестраивать, чтобы получить наиболее свежие результаты при поиске.

Много чтения, много записи, быстрое время отклика

Вы ждали этого момента, не так ли :)? Используйте ClickHouse с первичным ключом по timestamp. В ClickHouse первичный ключ лишь задает порядок сортировки, поэтому уникальность обеспечивать не нужно. ClickHouse очень быстр и на чтение и на вставку, и заодно хорошо сжимает данные. Сделайте по (материализованной) колонке на каждое поле, по которому вам нужно осуществлять поиск, и будет вам счастье.