SQLite на примере машины для приготовления сэндвичей.
SQLite. SQL — это довольно странная концепция. Вы пишете свое приложение на одном языке, скажем, JavaScript, а затем отправляете в базу данных команды на совершенно другом языке, называемом SQL. Затем база данных компилирует и оптимизирует эту команду SQL, выполняет ее и возвращает ваши данные. Это кажется ужасно неэффективным, и все же ваше приложение может делать это сотни раз в секунду. Это безумие!
Но все еще более странно.
SQL изначально был разработан для нетехнических пользователей для взаимодействия с базой данных, однако сейчас он используется почти исключительно разработчиками программного обеспечения, которые используют его во всех своих приложениях.
Почему этот язык, созданный для «деловых людей», стал отраслевым стандартом для создания приложений?
Одно из ключевых преимуществ SQL заключается в том, что он является декларативным. Это означает, что вы говорите базе данных, что вы хотите, но не как это сделать. Ваша база данных знает о ваших данных НАМНОГО больше, чем вы, поэтому она должна быть способна принимать лучшие решения о том, как их получать и обновлять. Это позволяет вам улучшить уровень данных, добавляя индексы или даже реструктурируя таблицы с минимальным влиянием на код приложения.
SQLite уникален среди встроенных баз данных тем, что он не только имеет транзакционный уровень хранения данных в виде двух деревьев, но и включает в себя надежный механизм выполнения SQL-запросов. Сегодня мы рассмотрим, как SQLite анализирует, оптимизирует и выполняет ваши SQL-запросы.
Машина для приготовления бутербродов
Если вы читали наши предыдущие статьи в блоге SQLite на тему бутербродов, посвященные формату файлов SQLite, журналу откатов и WAL, то, вероятно, вы уже проголодались. Вы также, вероятно, устали от утомительного процесса приготовления бутербродов вручную, поэтому в этой статье мы будем использовать в качестве аналогии машину для приготовления бутербродов.
Эта машина будет выполнять несколько задач:
- Принимать заказ на бутерброды.
- Определять наиболее эффективный способ приготовления сэндвичей.
- Готовить бутерброды и передавать их вам.
Процесс создания и выполнения SQL-запросов похож на процесс приготовления бутербродов, хотя и менее вкусный. Давайте погрузимся в него.
Обучение нашей машины чтению
Первый шаг — дать нашей машине заказ. Мы передаем ей листок с заказом, на котором написано:
Make 3 BLT sandwiches hold the mayo, 1 grilled cheese
Для нашего компьютера этот порядок — просто строка отдельных символов: M, a, k, e, и т.д… Если мы хотим разобраться в этом, нам сначала нужно сгруппировать эти буквы в слова, или, точнее, «лексемы». Этот процесс называется «токенизацией» или «лексизацией».
После токенизации мы видим такой список лексем:
"MAKE", "3", "BLT", "SANDWICHES", "HOLD", "THE", "MAYO", ",", "1", "GRILLED", "CHEESE"
После этого начинается этап синтаксического анализа. Синтаксический анализатор получает поток лексем и пытается структурировать его таким образом, чтобы он был понятен компьютеру. Эта структура называется абстрактным синтаксическим деревом, или AST.
AST для нашей команды sandwich может выглядеть следующим образом:
{
"command": "MAKE",
"sandwiches": [
{
"type":"BLT",
"count": 3,
"remove": ["MAYO"]
},
{
"type": "GRILLED CHEESE",
"count": 1
}
]
}
Отсюда мы можем начать понимать, как мы можем взять это определение и начать строить из него сэндвичи. Мы добавили структуру к бесструктурному блоку текста.
Лексический и синтаксический разбор SQL
SQLite выполняет тот же процесс, когда читает SQL-запросы. Сначала он группирует символы в лексемы, такие как SELECT или FROM. Затем синтаксический анализатор создает структуру для их представления.
В документации по SQLite есть полезные «диаграммы железной дороги», представляющие пути, по которым может двигаться синтаксический анализатор, потребляя поток лексем. Определение SELECT показывает, как он может начать с ключевого слова WITH (для CTE), а затем перейти к пунктам SELECT, FROM, и WHERE.
Когда парсер завершает работу, он выводит структуру с подходящим названием Select struct. Если бы у вас был SQL-запрос следующего вида:
SELECT name, age FROM persons WHERE favorite_color = 'lime green'
В итоге у вас получится AST, который выглядит примерно так:
{
"ExprList": ["name", "age"],
"Src": "persons",
"Where": {
"Left": "favorite_color",
"Right: "lime_green",
"Op": "eq"
}
}
Определение наилучшего варианта действий
Итак, теперь, когда мы заказали сэндвич в AST, у нас есть план, как сделать наш сэндвич, верно? Не совсем.
AST(Абстрактное синтаксическое дерево) представляет то, что вы хотите — пару бутербродов. Он не говорит нам, как сделать бутерброды. Но прежде чем мы перейдем к плану, нам нужно определить оптимальный способ приготовления бутербродов.
Наша машина для приготовления сэндвичей может приготовить множество различных сэндвичей, поэтому мы запаслись всеми видами ингредиентов. Если бы мы делали гигантский сэндвич с большинством имеющихся начинок, то машине имело бы смысл посетить местоположение каждого ингредиента, используя или не используя его в соответствии с AST.
Но для нашего BLT нам нужны только бекон, салат и помидор. Это будет намного быстрее, если мы заставим машину искать местоположение только этих трех начинок в индексе и переходить непосредственно между ними.
SQLite принимает аналогичное решение, когда планирует, как выполнить запрос. Для этого он использует статистику о содержимом своих таблиц.
Использование статистики для ускорения запросов
Когда SQLite просматривает AST, могут существовать сотни способов доступа к данным для выполнения запроса. Наивным подходом было бы просто прочитать всю таблицу и проверить каждую строку на соответствие. Это то, что мы в работе называем полным сканированием таблицы, и это мучительно медленно, если вам нужно всего несколько строк из большой таблицы.
Другой вариант — использовать индекс для быстрого перехода к нужным строкам. Индекс — это список идентификаторов строк, отсортированных по одному или нескольким столбцам, поэтому если у нас есть индекс, например:
CREATE INDEX favorite_color_idx ON persons (favorite_color);
Затем все идентификаторы строк для людей, которые любят «сиреневый», группируются вместе в нашем индексе. Использование индекса для нашего запроса означает, что мы должны сначала считать из индекса, а затем перейти к строке в таблице. В этом случае увеличивается объем затрат на одну строку, поскольку требуется два поиска, однако почти никто не любит сиреневый цвет, поэтому у нас не так много совпадающих строк.
Но что произойдет, если вы будете искать популярный цвет, например «синий»? Поиск сначала в индексе, а затем переход к нашей таблице для такого количества строк будет медленнее, чем если бы мы просто искали во всей таблице.
Поэтому SQLite проводит некоторый статистический анализ наших данных и использует эту информацию для выбора (вероятно) оптимального рецепта для каждого запроса.
Статистика SQLite хранится в нескольких таблицах «sqlite_stat». Эти таблицы развивались на протяжении многих лет, поэтому существует 4 различных версии статистики, но только две из них все еще используются в последних версиях SQLite: sqlite_stat1 и sqlite_stat4.
Таблица sqlite_stat1 имеет простой формат. В ней хранится приблизительное количество строк для каждого индекса и количество дубликатов значений для столбцов индекса. Эти грубые статистические данные эквивалентны отслеживанию основных средних значений для набора данных — они не являются сверхточными, но их быстро рассчитать и обновить.
Таблица sqlite_stat4 является немного более усовершенствованной. В ней хранится несколько десятков образцов значений, распределенных по индексу. Эти более тонкие выборки означают, что SQLite может понять, насколько уникальны различные значения в пространстве ключей.
Выполнение нашего плана
Как только у нас есть оптимизированный план по созданию сэндвича, мы должны попросить машину записать его. Таким образом, если в будущем мы снова получим тот же заказ, мы сможем просто повторно использовать план, а не разбирать и оптимизировать заказ каждый раз.
Итак, как выглядит этот план создания сэндвича?
План будет записан в виде списка команд, которые машина может выполнить, чтобы в будущем снова сделать BLT. Нам не нужна команда для каждого типа сэндвича, так как у нас может быть много разных типов. Лучше иметь набор общих команд, которые можно повторно использовать для составления любого плана бутерброда.
Например, у нас могут быть следующие команды:
FIND_INGREDIENT_BIN(ingredient_name)— поиск позиции ингредиента в корзине.FETCH_INGREDIENT(bin)— захват ингредиента роботизированной рукой машины из заданного номера корзины ингредиента.APPLY_INGREDIENT— помещает ингредиент из манипулятора робота на сэндвич.GRILL— поджаривает текущий сэндвич.
У нас есть еще одно требование, которое не сразу бросается в глаза. У нас есть немного места для хранения готовых сэндвичей, поэтому нам нужно делать по одному сэндвичу за раз, и чтобы клиент брал его, прежде чем делать следующий сэндвич. Таким образом, мы сможем обрабатывать любое количество сэндвичей в заказе.
Этот процесс передачи называется уступкой, поэтому у нас будет команда YIELD, когда мы будем ждать, пока клиент возьмет сэндвич.
Нам также понадобится некоторый поток управления, чтобы мы могли сделать несколько сэндвичей одного вида, поэтому мы добавим команду FOREACH.
Таким образом, если собрать наши команды вместе, наш план может выглядеть следующим образом:
// Make our BLT sandwiches
FOREACH 1...3
bin = FETCH_INGREDIENT_BIN("bacon")
FETCH_INGREDIENT(bin)
APPLY_INGREDIENT
bin = FETCH_INGREDIENT_BIN("lettuce")
FETCH_INGREDIENT(bin)
APPLY_INGREDIENT
bin = FETCH_INGREDIENT_BIN("tomato")
FETCH_INGREDIENT(bin)
APPLY_INGREDIENT
YIELD
END
// Make our grilled cheese
bin = FETCH_INGREDIENT_BIN("cheese")
FETCH_INGREDIENT(bin)
APPLY_INGREDIENT
GRILL
YIELD
Этот набор команд, специфичных для конкретной области, и механизм их выполнения называется виртуальной машиной. Она дает нам уровень абстракции, соответствующий задаче, которую мы пытаемся решить (например, приготовление бутерброда), и позволяет нам по-разному конфигурировать команды для разных бутербродов.
Проверка виртуальной машины SQLite
Виртуальная машина SQLite устроена аналогичным образом. Она содержит набор команд, связанных с базой данных, которые могут выполнять действия, необходимые для получения результатов запроса.
Например, давайте начнем с таблицы людей с несколькими добавленными строками:
CREATE TABLE persons (
id INTEGER PRIMARY KEY AUTOINCREMENT,
name TEXT,
favorite_color TEXT
);
INSERT INTO persons
(name, favorite_color)
VALUES
('Vicki', 'black'),
('Luther', 'mauve'),
('Loren', 'blue');
Мы можем проверить это с помощью двух различных команд SQLite. Первая команда называетсяEXPLAIN QUERY PLAN и предоставляет план запроса на очень высоком уровне. Если мы выполним его для простого SELECT с условием, то увидим, что он выполняет сканирование таблицыpersons:
sqlite> EXPLAIN QUERY PLAN SELECT * FROM persons WHERE favorite_color = 'blue'; QUERY PLAN `--SCAN persons
Эта команда может дать больше информации при выполнении более сложных запросов. Теперь давайте рассмотрим другую команду для дальнейшей проверки плана.
Смущает то, что она называется командой EXPLAIN . Просто отбросьте часть «QUERY PLAN» первой команды, и она покажет гораздо более подробный план:
sqlite> EXPLAIN SELECT * FROM persons WHERE favorite_color = 'blue'; addr opcode p1 p2 p3 p4 p5 comment ---- ------------- ---- ---- ---- ------------- -- ------------- 0 Init 0 11 0 0 Start at 11 1 OpenRead 0 2 0 3 0 root=2 iDb=0; persons 2 Rewind 0 10 0 0 3 Column 0 2 1 0 r[1]=persons.favorite_color 4 Ne 2 9 1 BINARY-8 82 if r[1]!=r[2] goto 9 5 Rowid 0 3 0 0 r[3]=rowid 6 Column 0 1 4 0 r[4]=persons.name 7 Column 0 2 5 0 r[5]=persons.favorite_color 8 ResultRow 3 3 0 0 output=r[3..5] 9 Next 0 3 0 1 10 Halt 0 0 0 0 11 Transaction 0 0 1 0 1 usesStmtJournal=0 12 String8 0 2 0 blue 0 r[2]='blue' 13 Goto 0 1 0 0
Это «простое английское» представление байт-кода, в который скомпилирован ваш запрос. Это может показаться запутанным, но мы можем пройтись по нему шаг за шагом, чтобы разложить его по полочкам.
Набор инструкций виртуальной машины SQLite
Подобно тому, как в компьютере есть низкоуровневые операции процессора, такие как MOV и JMP, SQLite имеет аналогичный набор команд, но только на более высоком уровне. На момент написания этой статьи существует 186 команд, или опкодов, которые может понимать виртуальная машина SQLite. Полную спецификацию можно найти на сайте SQLite, но мы рассмотрим здесь лишь некоторые из них.
Первый опкод — это Init, который инициализирует наше выполнение, а затем переходит к другой инструкции в нашей программе. Параметры для опкодов перечислены с p1 по p5, и их определение специфично для каждой команды. Для опкода Init он переходит к команде, указанной в параметре p2, который равен 11.
По адресу 11 мы получаем опкод Transaction, который начинает нашу транзакцию. Для большинства опкодов ВМ переходит на следующий адрес после выполнения инструкции, поэтому мы переходим по адресу 12. Этот опкод String8 сохраняет значение строки «blue» в регистр r[2]. Регистры действуют как набор адресов памяти и используются для хранения значений во время выполнения. Позже мы будем использовать это значение для сравнения равенства.
Далее мы переходим по адресу 13, который является инструкцией Goto, заставляющей нас перейти к инструкции, указанной в ее параметре p2, который является адресом 1.
Теперь мы переходим к обработке строк. Инструкция OpenRead открывает курсор на таблице persons. Курсор — это объект для итерации или перемещения по таблице. Следующая инструкция, Rewind, перемещает курсор к первой записи базы данных, чтобы начать сканирование таблицы.
Инструкция Column считывает столбец favorite_color в регистр r[1], а инструкция Ne сравнивает его со значением «blue» в регистре r[2]. Если значения не совпадают, то мы переходим к инструкции Next по адресу 9. Если они совпадают, мы заполним регистры r[3] , r[4] и r[5] с id, name, и favorite_color для строки.
Наконец, мы доходим до того, что можем вернуть результат вызывающему приложению с помощью инструкции ResultRow. Это позволит вызывающему приложению скопировать значения в регистры r[3…5]. Когда вызывающее приложение вызовет sqlite3_step(), программа продолжит работу с того места, на котором остановилась, вызвав Next и перейдя к повторному выполнению обработки строки по инструкции 3.
Когда Next больше не будет выдавать строки, программа перейдет к инструкции Halt, и программа завершит работу.
Завершение работы нашего механизма обработки сэндвичей
Сторона выполнения запросов в SQLite следует этому простому плану «разобрать-оптимизировать-исполнить» для каждого запроса, поступающего в базу данных. Мы можем использовать эти знания для повышения производительности нашего приложения. Используя параметры привязки в SQL-операторах (они же ?), мы можем подготовить оператор один раз и пропустить фазы разбора и оптимизации при каждом повторном использовании.
SQLite использует подход виртуальной машины для выполнения запросов, но это не единственный доступный подход. Postgres, например, использует план выполнения на основе узлов, который структурирован совершенно по-другому.
Теперь, когда вы понимаете основы работы плана обработки, попробуйте запустить EXPLAIN на одном из ваших более сложных запросов и посмотрите, сможете ли вы понять пошаговое выполнение того, как ваш запрос материализуется в набор результатов для вашего приложения.
#виртуальная машина SQLite
