🗃️ SQLite: Past, Present, and Future
#sqlite #duckdb #bloomfilter #btree
🥼 Article https://dl.acm.org/doi/10.14778/3554821.3554842

На одном из проектов использую sqlite и решил почитать про нее.
Статья от 2022 года, поэтому надо это учитывать.

🪨 Context
SQLite это embedded база данных, которая может работать прямо из процесса приложения без client/server взаимодействия.
Она с одной стороны сильно ограничена по функциональности, но имеет все необходимое для минимальной базы данных.
В данной статье люди University of Wisconsin-Madison решили сравнить duckdb и sqlite, потому что duckdb набирает популярность и отбирает лавры embedded db для аналитических сценариев.

🧂The idea
Авторы взяли несколько бенчмарков:
* TATP для OLTP нагрузки, где sqlite чаще используется и больше предназначен. Тут конечно интересного мало, sqlite на 1-2 порядка быстрее, см. pic 1.
* SSB для OLAP нагрузки, где duckdb быстрее, но это как раз поле чтобы поискать точки роста для sqlite.

! sqlite не поддерживает in-query parallelisation, поэтому для "справедливого" сравнения, сравнивалась single-threaded версия duckdb.

В OLAP случае все наоборот, duckdb на 1-2 порядка быстрее (см. pic 2)
В sqlite все запросы компилируются в byte-code, который исполняется в реализованной VM -- VDBE (Virtual Database Engine).
Дальше по инструкциям byte-code можно понять где больше всего тратится времени и у VDBE есть возможность записывать количество CPU Cycles per instruction type.

В join-запросав большинство времени уходило на seek в B-tree, при этом на запросах было много промахов, т.е. много поисков в дереве в бенчмарке делалось впустую.
Авторы решили реализовать дополнительный BloomFilter, который динамически строят перед таким join.
Это конечно ускорило join в benchmark, но требует дополнительного full scan прохода по всей таблице. Нельзя прочесть лишь 1 столбец, это же row-oriented, прочитана будет вся таблица.

Такая оптимизация ускорила часть запросов в 4 раза (см pic 3), и это здорово, но это очень далеко от оптимизаций которые в duckdb.

Да вот и все работа и оптимизации, добавили BloomFilter перед B-tree.

🤔 My opinion
Кажется проект sqlite стал заложником своей популярности и консурциума, который хочет сохранить технологию, а не развивать.
Надо смотреть на форки вроде turso.

In the two decades following its initial release, SQLite has become the most widely deployed database engine in existence. Today, SQLite is found in nearly every smartphone, computer, web browser, television, and automobile. Several factors are likely responsible for its ubiquity, including its in-process design, standalone codebase, extensive test suite, and cross-platform file format.

However, we quickly encountered limitations surrounding changes to SQLite’s database file format. The database file format is extremely stable, cross-platform, and backwards compatible. As noted earlier, the database file format is a US Library of Congress recommended format for the preservation of digital content [1], largely due to its stability, portability, and thorough documentation. It is straightforward to imagine new data formats, such as columnoriented, that would streamline value extraction. However, we were unwilling to sacrifice the stability and portability of the database file format for the added performance.

Когда ты такой популярный, то нельзя просто так взять и поменять формат данных, слишком много всего нужно мигрировать или поломается.
Т.е. единственное что можно менять, так это процессинг уже текущего формата. Но и тут есть ограничения, реализация sqlite старается быть минимальной, без внешних зависимостей и уметь работать на разнообразных платформах. Они json/jsonb даже сами реализовали внутри.

For example, one might reasonably predict that SQLite would benefit from vectorized execution, which DuckDB uses to reduce the overhead of runtime query interpretation. However, our profiling analysis revealed that SQLite spends little time in query interpretation relative to B-tree probes and value extraction, and thus vectorization is unlikely to have an appreciable impact.