Что нового в SQLite (2013)?

В последнем обновлении SQLite планировщик запросов претерпел серьезные изменения и отныне зовется Планировщик Запросов Следующего Поколения. Мы решили сделать небольшой обзор нового планировщика и некоторых других значительных обновлений SQLite в текущем году. Новый функционал может оказаться полезным разработчикам.

Планировщик Запросов Следующего Поколения (NGQP, с версии 3.8.0)

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

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

Запросы, соединяющие несколько таблиц, SQLite исполняет с помощью вложенных циклов, по одному на каждую из таблиц (плюс дополнительные циклы, если в условии есть OR или IN). Цикл может использовать один или несколько индексов или делать полный обход таблицы. Таким образом, планирование состоит из двух задач:

1) выбрать порядок вложения циклов;
2) подобрать индекс под каждый цикл;

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

Планировщик запросов SQLite «стабилен», то есть выбирает один и тот же план при условии, что:

1) схема БД не изменилась в части индексов;
2) не был перевыполнен ANALYZE;
3) не установлена опция SQLITE_ENABLE_STAT3;
4) версия SQLite не изменилась.

Это означает, что, если при тестировании запросы работают «хорошо», то они будут «хорошо» работать и в боевой системе на той же версии SQLite. «Большие» БД, как правило, такой гарантии не дают поскольку все время обновляют статистику индексов.

Версии SQLite до 3.8.0 плохо работали со сложными запросами. Пример такого «сложного случая»: «TPC-H Q8» от Transaction Processing Performance Council. В этом запросе соединяются 8 таблиц:

На этой диаграмме кружок означает таблицу из FROM запроса. На дуге, соединяющей кружки, написана примерная «стоимость» исполнения каждого цикла, исходя из предположения, что цикл, откуда дуга исходит, является внешним для данного. Например, если вложить цикл S в цикл L, то стоимость составит 2.30. А если вложить цикл L в S, то стоимость составит 9.17.

«Стоимости» являются логарифмическими и при вкладывании циклов их стоимости перемножаются, а не складываются. Преимущество в 6.87 от вложения цикла S в L означает, что запрос выполняется в 963 раза быстрее, если S вложен в L, чем если L вложен в S.

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

Это описание задачи является упрощением, поскольку в реальности оценки стоимости всегда приблизительны и представлены не одной цифрой, а несколькими «весами» разных вариантов поведения. Например, «стартовый» вес, в который заложено время построения автоматического индекса. Не все запросы представимы в виде подобного графа. Если запрос включает ORDER BY, то будет полезно использовать индекс, чтобы избежать дополнительной сортировки. И так далее. Но для рассмотрения случая TPC-H Q8 все эти сложности будут исключены для понимания сути.

До версии 3.8.0 SQLite использовал эвристику «Ближайший Сосед», «БС». В этом случае делается единственный обход графа по дуге наименьшей стоимости. Как ни странно, это неплохо работает во многих случаях. И работает быстро. Но, увы, для «TPC-H Q8» этот метод выбирает маршрут R-N1-N2-S-C-O-L-P стоимостью 36.92. Эта запись означает, что R — внешний цикл, в него вложен N1 и пр. В реальности наилучший маршрут здесь P-L-O-C-N1-R-S-N2. Его стоимость 27.38, разница вроде незначительна, но не стоит забывать, что это — логарифмические стоимости. Так что оптимальное исполнение работает быстрее в 750 раз. Решение может заключаться в полном переборе всех маршрутов, но время работы такого перебора пропорционально факториалу от количества циклов.

Новый Планировщик использует новую эвристику для поиска маршрута в графе: «N Ближайших Соседей». Алгоритм ведет N путей вместо выбора единственного соседа с минимальной стоимостью. Предположим, что N = 4. Тогда на графе TPC-H Q8 отбираются следующие лучшие маршруты:

R (cost: 3.56)
N1 (cost: 5.52)
N2 (cost: 5.52)
P (cost: 7.71)

Далее, для каждого маршрута выбираем следующей шаг с минимальной стоимостью:

R-N1 (cost: 7.03)
R-N2 (cost: 9.08)
N2-N1 (cost: 11.04)
R-P (cost: 11.27)

Третий шаг:

R-N1-N2 (cost: 12.55)
R-N1-C (cost: 13.43)
R-N1-P (cost: 14.74)
R-N2-S (cost: 15.08)

И т.д. Всего возможны 8 шагов по числу таблиц. В общем случае для K циклов, вычислительное время есть O(K*N), что далеко не O(2^K).

Но какое значение N стоит использовать? Может N = K?

В реальности «N Ближайших Соседей» находит оптимальный вариант исполнения TPC-H Q8 при N = 10. И в настоящее время в SQLite вшиты следующие константы: N = 1 для простых запросов, N = 5 для запросов из двух циклов и N = 10 для всех запросов, в которых более двух циклов. Возможно, эти константы поменяются в будущем.

При переходе на SQLite 3.8.0 некоторые запросы могут начать работать медленно.

Выполните ANALYZE!

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

Частичные индексы (partial indexes, с версии 3.8.0)

Частичные индексы позволяют указать условие, чтобы исключить часть записей из индекса. «Классический» способ использования:

 CREATE INDEX po_parent ON purchaseorder(parent_po)   WHERE parent_po IS NOT NULL; 

В индекс po_parent будут включены только записи, у которых не пустой parent_po. Если в таблице много записей с пустыми parent_po, то достигается существенная экономия ресурсов, поскольку эти записи индекс вообще не содержит.

Более хитрый способ использования. Предположим, люди разбиты по командам (team). У каждой команды есть лидер, входящий в команду. Например:

 CREATE TABLE person(    person_id       INTEGER PRIMARY KEY,    team_id           INTEGER REFERENCES team,    is_team_leader  BOOLEAN,    -- другие поля опущены ); 

Как гарантировать, что у команды будет не больше одного лидера? Просто сделать уникальный индекс по (team_id, is_team_leader), разумеется, нельзя. Поскольку он не позволит включить в команду несколько «нелидеров». Решение — создать частичный индекс:

CREATE UNIQUE INDEX team_leader ON person(team_id) WHERE is_team_leader; 

Этот индекс поможет быстро найти лидера команды:

SELECT person_id FROM person WHERE is_team_leader AND team_id=?1; 

И одновременно не позволит добавить второго лидера в команду.

Ввод/вывод с использованием отображения в память (memory-mapped I/O, с версии 3.7.17)

SQLite работает в «виртуальном окружении». Он использует специальную таблицу вызовов, за который скрывается «внешний мир» операционной системы с ее чтением файлов, блокировками и пр. До версии 3.7.17 чтение и запись данных использовали вызовы xRead() и xWrite() окружения. Эти вызовы обычно транслируются в вызовы API «чтение из файла» и «запись в файл» операционной системы. С версии 3.7.17 SQLite может вместо обычного ввода/вывода использовать отображаемый в память ввод/вывод (новые вызовы: xFetch() и xUnfetch()).

При обычном чтении данных SQLte выделяет буфер и просит систему прочитать в него данные постранично. При этом всегда происходит копирование данных в памяти. При использовании отображения в память SQLite получает указатель места в памяти. Если файл уже был ранее загружен, то копирования не происходит и это приводит к повышению производительности (до 146 200%). Также достигается экономия памяти за счет разделения ее между системой и SQLite.

Однако есть и недостатки. Ошибки переполнения буфера сразу испортят базу, так как синхронизация памяти с диском будет мгновенно выполнена системой. Однако не это самое печальное. Плохо то, что ошибка ввода/вывода по новой схеме «не ловится» SQLite. Вместо этого приложение получает сигнал на терминирование (поведение на Windows системах мне неизвестно — может кто-то отпишет в комментариях).

Также на определенных схемах работы возможна и деградация производительности.

Чтобы включить отображаемый в память ввод/вывод используется команда:

PRAGMA mmap_size=268435456; 

Значение задает максимальный размер буфера памяти на одну базу данных. Отключить:

PRAGMA mmap_size=0; 

Вот и все новости. Надеемся, обзор окажется полезным. Здесь можно посмотреть подробную историю релизов SQLite.