Как фильтры Блума в 10 раз ускорили SQLite

Это интригующая история о том, как исследователи с помощью грамотного использования фильтров Блума смогли в 10 раз ускорить аналитические запросы в SQLite. Ниже я приведу свой краткий обзор работы «SQLite: Past, Present, and Future (2022) ^[1]», и объясню некоторые внутренние особенности баз данных, включая механизм реализации соединений.

▍ Введение

База данных SQLite представляет собой хранящееся на диске B-дерево, состоящее из строк. Для выполнения запросов в этой БД используется виртуальная машина VDBE ^[2]. Она кроссплатформенная, однопоточная и работает почти на всём.

SQLite относится к БД общего назначения, но преимущественно выигрывает в задачах транзакционной обработки данных (OLTP). Однако в 2015 году исследователи из Университета Буффало выяснили, что большинство запросов в ней — это простые поиски пар ключ-значение и сложные задачи оперативной аналитической обработки (OLAP). Впоследствии другие исследователи, уже из Висконсинского университета в Мэдисоне, захотели ускорить этот её аспект аналитической обработки, так как он становится всё более актуальным. В качестве экспериментальной основы они использовали DuckDB, которую оценивали с помощью общепринятого бенчмарка Star Schema Benchmark (SSB).

SSB включает множество аналитических запросов, называемых Star Queries, в которых используется большая таблица fact и множество меньших таблиц dimension. Например, fact может содержать заказы клиентов, а dimension — информацию о клиенте, поставщике, партнёрах и так далее.

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

Как и ожидалось, исследователи выяснили, что DuckDB в 30-50х быстрее SQLite. Причём DuckDB они использовали в однопоточном режиме.

▍ Причина

Надо разобраться, почему SQLite оказалась столь медленной, тогда мы сможем понять, как её ускорить. У этой БД есть опция этапа компиляции, VDBE_PROFILE, которая измеряет количество тактов процессора, затраченных на выполнение VDBE каждой инструкции. Повторно прогнав бенчмарк, исследователи выявили два основных опкода:

Что эти операции делают?

• SeekRowID — получает rowId и сканирует соответствующую строку в B-дереве.
• Column — извлекает из указанной записи столбец.

Поскольку аналитические запросы состоят преимущественно из операций соединения, нужно разобрать, как эти операции реализованы.

▍ Соединение в базе данных

Вот несколько способов реализации JOIN:

• Соединение вложенными циклами.
• Соединение хэшированием.
• Соединение сортировкой/слиянием.

SQLite выполняет простейший из этих видов — соединение вложенными циклами. Вот анимация ^[3], которая показывает его в действии:

А вот образец псевдокода в стиле Python:

orders: {id, data} = [(1, obj...), (7, ...), (21, ...)] # Таблица fact
customers: {order_id, data} = [(2, obj...), (7, ...), (14, ...)] # Таблица dimension

selected = []
for order in orders:
    for customer in customers:
        # Отбрасывает данные, если id customer равен 2 или 14
        if order.id == customer.order_id:
            selected.append(customer)

Предположим, у вас есть две таблицы: заказы (orders) и клиенты (customers). Приведённый код производит соединение этих таблиц на основе столбца order_id. Внешний цикл перебирает каждый элемент в таблице customers и также перебором сопоставляет с ним все элементы таблицы orders.

В случае совпадения id он добавляет соответствующие записи в список результатов. Такие операции с циклами сопряжены с весьма затратным обращением к B-дереву.

Наша же цель — уменьшить число таких обращений. Задумайтесь, чем плох описанный механизм? Есть идеи, как реализовать его наиболее эффективно?

▍ Порядок соединения

Порядок таблиц в процессе соединения тоже важен. Вот простой пример:

• Перебираем каждый элемент во внешней таблице (внешний цикл).
• Сопоставляем с ним каждый элемент внутренней таблицы (внутренний цикл).
• Orders: 10 000, Clients: 100, Dates: 200
  • Совпадений: Clients: 20, Dates: 10
• Операций поиска по дереву:
  • O, C, D: 10 000*20*200=4M
  • O, D, C: 10 000*10*100=1M
• Оптимизация соединения является NP-трудной задачей.

Представим, что у нас три таблицы: Orders, Customers и Date. Наш запрос совпадает с 20 элементами в Customers и с 10 в Date. При каждом совпадении строки мы выполняем поиск по B-дереву.

• O, C, D: 10000 * 20 * 200 = 4M.
• O, D, C: 10000 * 10 * 100 = 1M.

Одна только перестановка таблиц местами уже сократила процесс до 1М операций. Но оптимизированный план выполнения запроса придумать очень сложно, поэтому здесь мы имеем NP задачу.

▍ Оптимизация

Как оптимизировать соединение? Два других упомянутых выше алгоритма справляются лучше, чем вложенные циклы. Но авторы исследования утверждают, что соединение хэшированием требует много памяти, а SQLite чаще всего оперирует в средах с её ограниченным ресурсом. К тому же, добавление ещё одного алгоритма сильно усложнит планирование выполнения запроса.

orders = [(1, obj...), (7, ...), (21, ...)]
customers = [(2, obj...), (7, ...), (14, ...)]

selected = []
cache = {2: True, 7: True, 14: True}
for order in orders:
    if order.id in cache:
        # Проверяем таблицу customers только при обнаружении соответствия в кэше.
        for customer in customers:
            if order.id == customer.order_id:
                selected.append(customer)

Вот возможное решение: прежде чем выполнять оба цикла, сначала создаём кэш данных из customers. Затем во внутреннем цикле первым делом проверяется этот кэш, и только в случае обнаружения совпадения выполняется перебор циклом.

Так и поступили исследователи. Они использовали фильтр Блума, который очень экономичен по ресурсам, вмещается в кэш-строку процессора и легко реализуется.

Они добавили два опкода: Filter и FilterAdd. Соединение начинается с перебора всех строк таблицы dimensions и установки в фильтре тех битов, которые соответствуют условию запроса. Это операция FilterAdd.

В ходе этого процесса мы на каждой стадии сначала проверяем, присутствует ли строка в фильтре Блума. Если да, выполняем поиск по B-дереву. Это операция Filter.

▍ Результаты

Вот оптимизированный план выполнения запроса.

А вот анализ количества тактов процессора после оптимизации — синие столбцы почти исчезли!

И каков результат? SQLite ускорилась в 7-10 раз!

Результаты исследования уже были внедрены в SQLite v3.38.0.

Почему фильтры Блума так хорошо себя показали? Потому что минимально нагружают память, прекрасно сочетаются с простой реализацией SQLite и использовались в имеющемся механизме обработки запросов.