Comments 14
Простите, а почему на иллюстрирующей Nested Loops Joins гифке для каждой строки Outer Input перебираются все строки Inner Input? Разве у Inner Input таблицы нет соответствующего индекса?
Подозреваю, что для индексов нужна дополнительная память, а как сказано в статье
...SQLite чаще всего оперирует в средах с её ограниченным ресурсом. К тому же, добавление ещё одного алгоритма сильно усложнит планирование выполнения запроса.
Никто не мешает сделать это опцией, и собирать библиотеку по-разному для разных сценариев использования.
База данных без индексов - абсурд, и конечно же индексы в SQLite имеются.
Да как бы примерно всегда индексы выбираются на этапе проектирования базы, это ответственность db architect. И если тут индекса не будет – db architect будут бить, может быть, даже ногами.
Я так понял, что фильтр Блума как раз дополняет индекс, позволяя выполнить проверку наличия хоть одного элемента очень быстро (по крохотной табличке в памяти) и не ходить по индексу в случае, когда это не требуется. Просто картинка, видимо, далека от реальности.
Это стандартный nested loops join. Бывает и nested loops join с индексом для inner table - если индекс существует.
Ну вот мне, хоть убейте, непонятно, почему для случая из примера он может не существовать. Проверка "if order.id == customer.order_id" – за гранью того, что я могу понять и простить.
И, насколько я понял, чуть погуглив по теме, если там нет индекса – то и фильтра Блума не будет.
Не очень понимаю для чего при построении фильтра Блума нужен бы был индекс? Ведь чтобы его построить, надо в любом случае перебрать все записи соединяемой таблицы, есть индекс или нет.
Фильтр Блума позволяет отказаться от вхождения во вложенный цикл в случае, когда соединение записей заведомо невозможно.
Но если соединение возможно, а индекса нет, то вложенный цикл придется выполнить и при отсутствии индекса. А если индекс имеется, то во вложенном цикле надо будет всего лишь собрать все соответствующие записи.
Другое дело, что для условия соединения по совпадению ключа таблицы1 и внешнего ключа таблицы2 индекс обычно существует. Но это всего лишь частный случай соединения (хотя он и приведен в качестве иллюстрации) - соединение таблиц вполне возможно без подходящего индекса.
При построении – не нужен. По сути, фильтр Блума – это эдакий легковесный "недоиндекс", который может быть применён ровно в одном случае: когда ситуация "нет ни одной подходящей записи" достаточно частая, чтобы не искать эту запись по индексу.
Но не вижу ни единой причины строить фильтр Блума и не строить индекс. Данные для их построения нужны ровно одни и те же, и если фильтр Блума показал возможное наличие записи – всё равно придётся её искать в таблице, что лучше сделать по индексу.
Если есть индекс (B-tree), то Блум не очень то и нужен. Индекс по внешнему ключу (всегда B-tree для SQLite) не создается автоматически. Хэш-индексы в SQLite не используются. Ну и Блум занимает сильно меньше места, чем любой тип индекса.
Если человек не создал индекс для колонки, на которую ссылается – то он сам себе злобный дендромутант.
Причём даже есть он создал блум вместо индекса, но половина используемых строк есть – их всё равно придётся искать в таблице. Т.е. скорость увеличится в лучше случае вдвое – несопоставимо с эффектом от индекса (который из O(n) делает O(log n)).
Молодцы, ребята. Хорошая курсовая работа.
Судя по истории релизов версия 3.38.0 была выпущена 22 февраля 2022 года, т.е. 3 года назад.
Может кто знает есть ли вариант апнуть на последнюю версию sqlite используемую в приложении. Если конкретно Adobe lightroom использует базы sqlite для библиотеки фотографий. Так как фотографий уже накопилось очень много, библиотека подтормаживает. Думал может есть вариант заменить dll от sqlite на свежее. Но возможно есть более правильный метод.
Может быть есть вариант для sqlite собрать и пропагандировать статистику запросов как например в MS query store.
Как фильтры Блума в 10 раз ускорили SQLite