Планировщик запросов нового поколения

Задача «планировщика запросов» — определить оптимальный алгоритм, или «план выполнения запроса», для выполнения инструкции SQL. Начиная с версии 3.8.0 SQLite (2013-08-26), компонент планировщика запросов был переписан, чтобы работать быстрее и формировать более эффективные планы. Эта переработка называется «планировщиком запросов нового поколения», или «NGQP».

В этой статье рассматривается важность планирования запросов, описываются некоторые присущие ему проблемы и объясняется, как NGQP решает эти проблемы.

NGQP почти всегда лучше прежнего планировщика запросов. Однако могут существовать старые приложения, которые, сами того не зная, зависят от неопределённого и/или неоптимального поведения прежнего планировщика запросов. Переход таких приложений на NGQP может привести к снижению производительности. Этот риск рассматривается в статье, а также приводится контрольный список для его уменьшения и устранения возникающих проблем.

Этот документ посвящён NGQP. Более общий обзор планировщика запросов SQLite, охватывающий всю историю SQLite, см. в документах «Обзор оптимизатора SQLite» и «Как работают индексы».

2. Предыстория

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

Именно планировщики запросов делают движки баз данных SQL настолько невероятно полезными и мощными. (Это относится ко всем движкам баз данных SQL, а не только к SQLite.) Планировщик запросов избавляет программиста от необходимости выбирать конкретный план выполнения запроса и тем самым позволяет ему направить больше умственных усилий на вопросы более высокого уровня, связанные с приложением, и на то, чтобы приносить больше пользы конечному пользователю. Для простых запросов, где выбор плана выполнения очевиден, это удобно, но не так уж важно. Однако по мере усложнения приложений, схем и запросов эффективный планировщик запросов может значительно ускорить и упростить разработку приложений. Возможность сообщить движку базы данных, какие данные нужны, а затем позволить ему самому определить наилучший способ их извлечения — это поразительная возможность.

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

2.1. Планирование запросов в SQLite

SQLite вычисляет соединения с помощью вложенных циклов — по одному циклу для каждой таблицы в соединении. (Для операторов IN и OR в предложении WHERE могут добавляться дополнительные циклы. SQLite учитывает и их, но для простоты мы не будем рассматривать их в этой статье.) В каждом цикле может использоваться один или несколько индексов для ускорения поиска либо цикл может выполнять «полное сканирование таблицы», считывая каждую её строку. Таким образом, планирование запросов сводится к двум подзадачам:

Выбор порядка вложенности различных циклов
Выбор подходящих индексов для каждого цикла

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

2.2. Гарантия стабильности планировщика запросов SQLite

Если включена гарантия стабильности планировщика запросов (QPSG), SQLite всегда будет выбирать один и тот же план выполнения для заданной инструкции SQL при условии, что:

схема базы данных не меняется существенным образом, например при добавлении или удалении индексов;
команда ANALYZE не запускается повторно;
используется одна и та же версия SQLite.

По умолчанию QPSG отключена. Её можно включить во время компиляции с помощью параметра компиляции SQLITE_ENABLE_QPSG или во время выполнения, вызвав sqlite3_db_config(db,SQLITE_DBCONFIG_ENABLE_QPSG,1,0).

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

Движки клиент-серверных баз данных SQL обычно не дают такой гарантии. В таких движках сервер отслеживает статистику о размерах таблиц и качестве индексов, а планировщик запросов использует эту статистику, чтобы помочь выбрать оптимальные планы. По мере добавления, удаления или изменения данных в базе статистика меняется, что может привести к тому, что планировщик запросов начнёт использовать другой план для определённого запроса. Обычно новый план лучше подходит к изменившейся структуре данных. Но иногда новый план запроса снижает производительность. В клиент-серверных движках баз данных обычно есть администратор базы данных (DBA), который может решать такие редкие проблемы по мере их возникновения. Но встраиваемой базой данных, такой как SQLite, DBA не управляет, поэтому SQLite принимает меры, чтобы планы не менялись неожиданно после развёртывания.

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

См. также:

3. Сложный случай

«TPC-H Q8» — тестовый запрос из набора Совета по оценке производительности транзакционной обработки. Планировщики запросов в версиях SQLite 3.7.17 и более ранних не выбирают эффективные планы для TPC-H Q8. Кроме того, было установлено, что никакая настройка прежнего планировщика запросов не поможет исправить ситуацию. Чтобы найти хорошее решение для запроса TPC-H Q8 и продолжить улучшать качество планировщика запросов SQLite, потребовалось перепроектировать его. В этом разделе объясняется, почему такая переработка была необходима, чем NGQP отличается от прежнего планировщика и как он решает проблему TPC-H Q8.

3.1. Подробности запроса

TPC-H Q8 — это соединение восьми таблиц. Как отмечалось выше, главная задача планировщика запросов — определить оптимальный порядок вложенности восьми циклов, чтобы свести к минимуму объём работы, необходимой для выполнения соединения. Упрощённая модель этой задачи для TPC-H Q8 показана на следующей диаграмме:

На диаграмме каждая из 8 таблиц в предложении FROM запроса обозначена большим кругом с меткой соответствующего элемента предложения FROM: N2, S, L, P, O, C, N1 и R. Дуги графа показывают предполагаемую стоимость вычисления каждого элемента при условии, что начало дуги находится во внешнем цикле. Например, стоимость выполнения цикла S как внутреннего цикла для L равна 2.30, тогда как стоимость выполнения цикла S как внешнего цикла для L равна 9.17.

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

Стрелки от маленьких кругов с меткой «*» показывают стоимость выполнения каждого цикла без зависимостей. Для самого внешнего цикла должна использоваться стоимость со «*». Для внутренних циклов можно использовать стоимость со «*» либо стоимость, рассчитанную при условии, что один из других элементов находится во внешнем цикле, — выбирается вариант с лучшим результатом. Стоимости со «*» можно считать сокращённой записью нескольких дуг: по одной от каждого другого узла графа. Таким образом, граф является «полным»: между каждой парой узлов есть дуги в обоих направлениях (часть из них показана явно, а часть подразумевается).

Задача поиска оптимального плана выполнения запроса эквивалентна поиску пути минимальной стоимости через граф, который проходит через каждый узел ровно один раз.

(Примечание: оценки стоимости на графе TPC-H Q8 выше вычислены планировщиком запросов в SQLite 3.7.16 и преобразованы с помощью натурального логарифма.)

3.2. Осложнения

Приведённое выше описание задачи планировщика запросов упрощено. Стоимости являются оценками. Мы не можем узнать истинную стоимость выполнения цикла, пока не выполним его. SQLite оценивает стоимость выполнения цикла, основываясь на наличии индексов и ограничений, указанных в предложении WHERE. Обычно эти оценки довольно точны, но иногда могут быть ошибочными. Команда ANALYZE, собирающая дополнительную статистическую информацию о базе данных, иногда позволяет SQLite точнее оценить стоимость.

Стоимость состоит из нескольких чисел, а не из одного, как показано на графе. SQLite вычисляет для каждого цикла несколько различных оценок стоимости, применимых в разное время. Например, есть стоимость «настройки», которая учитывается только один раз при запуске запроса. Это стоимость вычисления индекса, создаваемого во время выполнения запроса для таблицы, у которой ещё нет индекса. Затем учитывается стоимость каждого шага цикла. Наконец, оценивается количество строк, создаваемых циклом, — эта информация нужна для оценки стоимости внутренних циклов. Если в запросе есть предложение ORDER BY, может учитываться стоимость сортировки.

В общем случае зависимости могут охватывать не один цикл, поэтому матрицу зависимостей не всегда можно представить графом. Например, одно из ограничений предложения WHERE может иметь вид S.a=L.b+P.c, что означает, что цикл S должен быть внутренним циклом и для L, и для P. Такие зависимости невозможно изобразить графом, поскольку дуга не может начинаться сразу в двух или более узлах.

Если запрос содержит предложение ORDER BY или GROUP BY либо использует ключевое слово DISTINCT, выгодно выбрать путь через граф, при котором строки естественным образом появляются в отсортированном порядке, чтобы не требовался отдельный этап сортировки. Автоматическое устранение предложений ORDER BY может существенно повлиять на производительность, поэтому при полноценной реализации необходимо учитывать и этот фактор.

В запросе TPC-H Q8 все затраты на настройку пренебрежимо малы, все зависимости связывают отдельные узлы, а предложения ORDER BY, GROUP BY и DISTINCT отсутствуют. Поэтому для TPC-H Q8 приведённый выше граф достаточно хорошо представляет задачу. Общий случай значительно сложнее, но для ясности в оставшейся части этой статьи эти дополнительные сложности не рассматриваются.

3.3. Поиск оптимального плана выполнения запроса

До версии 3.8.0 (2013-08-26) SQLite всегда использовала эвристику «ближайшего соседа», или «NN», при поиске оптимального плана выполнения запроса. Эвристика NN выполняет один обход графа, на каждом шаге выбирая дугу с наименьшей стоимостью. В большинстве случаев эвристика NN работает на удивление хорошо. Кроме того, NN работает быстро, поэтому SQLite может оперативно находить эффективные планы даже для больших соединений из 64 таблиц. В отличие от неё, другие движки баз данных SQL, выполняющие более полный поиск, обычно начинают работать медленно, когда число таблиц в соединении превышает 10 или 15.

К сожалению, план выполнения запроса, вычисленный NN для TPC-H Q8, не является оптимальным. План, вычисленный NN, — R-N1-N2-S-C-O-L-P, его стоимость равна 36.92. Эта запись означает, что таблица R обрабатывается во внешнем цикле, N1 — в следующем внутреннем цикле, N2 — в третьем цикле и так далее, вплоть до P, которая находится во внутреннем цикле самого нижнего уровня. Кратчайший путь через граф (найденный полным перебором) — P-L-O-C-N1-R-S-N2, его стоимость равна 27.38. Разница может показаться небольшой, но помните, что значения стоимости логарифмические, поэтому кратчайший путь почти в 750 раз быстрее пути, найденного эвристикой NN.

Один из способов решить эту проблему — изменить SQLite так, чтобы она выполняла полный перебор в поисках оптимального пути. Но полный перебор требует времени, пропорционального K! (где K — число таблиц в соединении), поэтому при соединении более чем из 10 таблиц время выполнения sqlite3_prepare() становится очень большим.

3.4. N ближайших соседей, или алгоритм «N3»

В NGQP для поиска оптимального пути через граф используется новый алгоритм: «N ближайших соседей» (далее — «N3»). Вместо того чтобы на каждом шаге выбирать только одного ближайшего соседа, алгоритм N3 отслеживает N лучших путей на каждом шаге для некоторого небольшого целого числа N.

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

R (стоимость: 3.56)
N1 (стоимость: 5.52)
N2 (стоимость: 5.52)
P (стоимость: 7.71)

На втором шаге находятся четыре кратчайших пути, проходящих через два узла и начинающихся с одного из четырёх путей предыдущего шага. Если два или более пути эквивалентны (они проходят через один и тот же набор узлов, хотя и в разном порядке), сохраняется только первый путь с наименьшей стоимостью. Получаем:

R-N1 (стоимость: 7.03)
R-N2 (стоимость: 9.08)
N2-N1 (стоимость: 11.04)
R-P {стоимость: 11.27}

На третьем шаге берутся четыре кратчайших пути из двух узлов и находятся четыре кратчайших пути из трёх узлов:

R-N1-N2 (стоимость: 12.55)
R-N1-C (стоимость: 13.43)
R-N1-P (стоимость: 14.74)
R-N2-S (стоимость: 15.08)

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

Но какое значение выбрать для N? Можно попробовать N=K. Тогда алгоритм имеет сложность O(K²), что всё ещё довольно эффективно, поскольку максимальное значение K равно 64, а K редко превышает 10. Но для задачи TPC-H Q8 этого недостаточно. При N=8 алгоритм N3 находит для TPC-H Q8 решение R-N1-C-O-L-S-N2-P со стоимостью 29.78. Это значительно лучше результата NN, но всё ещё не оптимально. Алгоритм N3 находит оптимальное решение для TPC-H Q8 при N не менее 10.

Первоначальная реализация NGQP выбирает N=1 для простых запросов, N=5 для соединений двух таблиц и N=10 для всех соединений из трёх или более таблиц. Позже значение N для соединений из трёх или более таблиц было увеличено до 12, а для соединений со звёздной схемой — до 18. В будущем возможны дальнейшие улучшения.

4. Эвристика звёздных запросов

Алгоритм N3 хорошо работает для большинства запросов. Но в некоторых случаях он создаёт неэффективный план. В частности, для некоторых запросов к звёздной схеме с большой таблицей фактов и шестью или более небольшими таблицами измерений, где имеются индексы в обоих направлениях, алгоритм N3 не находит оптимальный план выполнения запроса, если параметр N не имеет очень большого значения — экспоненциального по числу таблиц измерений. Такие запросы называются «звёздными запросами». В более новых версиях SQLite (примерно с 2024–2025 годов) реализована эвристика, позволяющая обходить эту проблему и выбирать эффективные планы выполнения для звёздных запросов без подсказок программиста.

4.1. Предыстория: что такое звёздный запрос

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

Например, предположим, что у вас есть таблицы измерений, во всех которых в качестве PRIMARY KEY используются целочисленные идентификаторы:

Таблица PRODUCT хранит сведения о каждом товаре.
Таблица SELLER хранит сведения о каждом сотруднике отдела продаж.
Таблица CUSTOMER хранит сведения о каждом клиенте.
Таблица CARRIER хранит сведения о каждом поставщике услуг доставки.
Таблица WAREHOUSE хранит сведения обо всех складах.

Каждая из таблиц измерений относительно невелика. Сколько складов у вашей компании? Возможно, таблицы PRODUCT и CUSTOMER несколько больше, но число записей в них всё равно может измеряться тысячами, а не миллионами.

Таблицы измерений связаны одной таблицей SALES, в которой регистрируется каждая продажа. Таблица SALES содержит, например:

Время и стоимость продажи.
Идентификаторы PRODUCT, SELLER, CUSTOMER, CARRIER и WAREHOUSE.

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

Это классический пример звёздной схемы. Такое представление данных встречается повсеместно и в самых разных областях. Запросы к такой схеме мы называем «звёздными запросами». Например, запрос полного отчёта обо всех продажах с 12:00 до 14:00 2024-01-04 будет звёздным запросом. В таблице SALES будут найдены все записи за указанный период, после чего в различных таблицах измерений будут найдены сведения о каждой отдельной продаже.

4.2. Проблемы планирования запросов со звёздными запросами высокой размерности

Описанный выше алгоритм планирования запросов N3 работает хорошо и формирует оптимальное решение для звёздных запросов менее чем с пятью или шестью таблицами измерений. Однако, если число таблиц измерений увеличивается, алгоритм N3 иногда находит неоптимальный план — в зависимости от того, как определены индексы и как соотносятся размеры таблиц фактов и измерений.

Это происходит потому, что N3 по-прежнему является жадным алгоритмом. Хотя на каждом шаге он отслеживает до N различных решений, он рассматривает только N лучших решений. Это приводит к следующим проблемам:

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

При достаточно большом значении N алгоритм N3 всё равно в итоге всегда найдёт наилучший план. Проблема в том, что достаточно большое значение N может быть экспоненциальным относительно числа таблиц измерений. Это означает, что общий алгоритм планирования запросов потребует экспоненциального времени. N3 отлично работает с тремя или четырьмя таблицами измерений. Однако при большем их количестве он начинает генерировать планы запросов, включающие полное сканирование небольших таблиц измерений, что серьёзно снижает производительность.

4.3. Пример с большим числом таблиц

Тестовый скрипт test/starschema1.test в дереве исходного кода SQLite демонстрирует звёздный запрос с одной таблицей фактов и 63 таблицами измерений. Этот тестовый пример искусственный, но он показывает, как алгоритм N3 может дать сбой, если его не изменить, как описано в следующем разделе.

4.4. Изменения N3 для поддержки звёздных запросов

Чтобы помочь планировщику запросов SQLite формировать более удачные планы звёздных запросов, для корректировки оценок стоимости поиска в различных таблицах используются эвристики.

Текущая эвристика, начиная с версии 3.49.0 (2025-02-06), искусственно повышает оценочную стоимость полного сканирования таблиц измерений, чтобы она была немного выше стоимости поиска нужных строк в таблице фактов. Это не позволяет множеству бесполезных полных сканирований таблиц измерений вытеснить поиск в таблице фактов из набора N лучших решений на ранних этапах алгоритма, благодаря чему в итоге предпочтение отдаётся поиску в таблице фактов. Изменяется только стоимость полного сканирования таблиц измерений. Оценочные стоимости всех остальных способов доступа остаются прежними, как и стоимости таблиц запроса, которые явно не являются таблицами измерений или порядок обработки которых уже ограничен конструкциями OUTER JOIN. Поэтому алгоритм затрагивается минимально, но этого достаточно, чтобы всегда находить хорошее решение для звёздных запросов даже при большом числе измерений.

В версиях SQLite 3.47.0 и 3.48.0 использовалась другая эвристика. Ранее снижалась стоимость всех способов доступа к таблице фактов, чтобы они могли конкурировать с полными сканированиями таблиц измерений и, таким образом, не исключались из рассмотрения на ранних этапах алгоритма. Однако такое искусственное снижение стоимости доступа к таблице фактов приводило к другим искажениям, вызывавшим ухудшение производительности при выполнении других сложных соединений.

5. Риски перехода на NGQP

→ Этот раздел устарел и сохранён только для справки. ← Этот раздел был важен, когда NGQP только появился. Но с тех пор прошло десять лет, NGQP успешно используется на миллиардах устройств, и все обновились; разработчики SQLite так и не получили сообщений об ухудшении производительности. Риск обновления исчез. Перейдите к списку рекомендаций по планировщику запросов.

Для большинства приложений переход с прежнего планировщика запросов на NGQP требует совсем немного обдумывания или усилий. Просто замените старую версию SQLite на новую, перекомпилируйте приложение — и оно будет работать быстрее. Изменений API и процедуры компиляции не требуется.

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

Основные положения:

NGQP всегда найдёт план запроса не хуже, чем прежние планировщики запросов, если ему доступны точные данные ANALYZE в файле SQLITE_STAT1.
NGQP всегда найдёт хороший план запроса, если схема не содержит индексов, в которых более примерно 10 или 20 строк имеют одинаковое значение в крайнем левом столбце индекса.

Не все приложения соответствуют этим условиям. К счастью, даже без них NGQP обычно находит хорошие планы запросов. Однако иногда (хотя и редко) всё же может происходить ухудшение производительности.

5.1. Практический пример: переход Fossil на NGQP

Fossil DVCS — система контроля версий, используемая для отслеживания всего исходного кода SQLite. Репозиторий Fossil — это файл базы данных SQLite. (Предлагаем читателям самостоятельно поразмышлять над этой рекурсией.) Fossil — и система контроля версий SQLite, и тестовая платформа для SQLite. Когда в SQLite добавляются улучшения, Fossil становится одним из первых приложений, которые проверяют и оценивают эти улучшения. Поэтому Fossil одним из первых начал использовать NGQP.

К сожалению, NGQP вызвал ухудшение производительности Fossil.

В числе множества отчётов, доступных в Fossil, есть временная шкала изменений одной ветки, показывающая все слияния в эту ветку и из неё. Типичный пример такого отчёта см. по адресу https://sqlite.org/src/timeline?nd&n=200&r=trunk. Обычно формирование такого отчёта занимает всего несколько миллисекунд. Однако после перехода на NGQP мы заметили, что для ветки trunk репозитория этот отчёт стал формироваться почти 10 секунд.

Основной запрос для формирования временной шкалы ветки показан ниже. (Читателям не обязательно понимать детали этого запроса. Далее последуют пояснения.)

SELECT
     blob.rid AS blobRid,
     uuid AS uuid,
     datetime(event.mtime,'localtime') AS timestamp,
     coalesce(ecomment, comment) AS comment,
     coalesce(euser, user) AS user,
     blob.rid IN leaf AS leaf,
     bgcolor AS bgColor,
     event.type AS eventType,
     (SELECT group_concat(substr(tagname,5), ', ')
        FROM tag, tagxref
       WHERE tagname GLOB 'sym-*'
         AND tag.tagid=tagxref.tagid
         AND tagxref.rid=blob.rid
         AND tagxref.tagtype>0) AS tags,
     tagid AS tagid,
     brief AS brief,
     event.mtime AS mtime
  FROM event CROSS JOIN blob
 WHERE blob.rid=event.objid
   AND (EXISTS(SELECT 1 FROM tagxref
                WHERE tagid=11 AND tagtype>0 AND rid=blob.rid)
        OR EXISTS(SELECT 1 FROM plink JOIN tagxref ON rid=cid
                   WHERE tagid=11 AND tagtype>0 AND pid=blob.rid)
        OR EXISTS(SELECT 1 FROM plink JOIN tagxref ON rid=pid
                   WHERE tagid=11 AND tagtype>0 AND cid=blob.rid))
 ORDER BY event.mtime DESC
 LIMIT 200;

Этот запрос не особенно сложен, но даже он заменяет сотни, а возможно, и тысячи строк процедурного кода. Суть запроса такова: просмотреть таблицу EVENT и найти последние 200 фиксаций, удовлетворяющих хотя бы одному из трёх условий:

Фиксация имеет тег "trunk".
У фиксации есть потомок с тегом "trunk".
У фиксации есть родитель с тегом "trunk".

Первое условие приводит к отображению всех фиксаций ветки trunk, а второе и третье включают также фиксации, которые сливаются с trunk или ответвляются от неё. Эти три условия реализованы тремя операторами EXISTS, соединёнными через OR в предложении WHERE запроса. Замедление, возникшее при использовании NGQP, было вызвано вторым и третьим условиями. В обоих случаях проблема одинакова, поэтому рассмотрим только второе. Подзапрос второго условия можно переписать (с небольшими несущественными упрощениями) следующим образом:

SELECT 1
  FROM plink JOIN tagxref ON tagxref.rid=plink.cid
 WHERE tagxref.tagid=$trunk
   AND plink.pid=$ckid;

Таблица PLINK хранит связи «родитель — потомок» между фиксациями. Таблица TAGXREF сопоставляет теги фиксациям. Для справки ниже показаны соответствующие фрагменты схем этих двух таблиц:

CREATE TABLE plink(
  pid INTEGER REFERENCES blob,
  cid INTEGER REFERENCES blob
);
CREATE UNIQUE INDEX plink_i1 ON plink(pid,cid);

CREATE TABLE tagxref(
  tagid INTEGER REFERENCES tag,
  mtime TIMESTAMP,
  rid INTEGER REFERENCE blob,
  UNIQUE(rid, tagid)
);
CREATE INDEX tagxref_i1 ON tagxref(tagid, mtime);

Есть только два разумных способа реализовать этот запрос. (Существуют и многие другие возможные алгоритмы, но ни один из них не претендует на звание «лучшего».)

Найти всех потомков фиксации $ckid и проверить, есть ли у каждого из них тег $trunk.
Найти все фиксации с тегом $trunk и проверить, является ли каждая из них потомком $ckid.

Интуитивно мы понимаем, что алгоритм-1 лучше. У каждой фиксации, скорее всего, мало потомков (чаще всего — один), а наличие тега $trunk у каждого потомка можно проверить за логарифмическое время. Действительно, на практике алгоритм-1 работает быстрее. Но у NGQP нет интуиции. NGQP должен опираться на строгие математические расчёты, а с математической точки зрения алгоритм-2 немного лучше. Это происходит потому, что при отсутствии других сведений NGQP должен предполагать, что индексы PLINK_I1 и TAGXREF_I1 имеют одинаковое качество и селективность. Алгоритм-2 использует одно поле индекса TAGXREF_I1 и оба поля индекса PLINK_I1, тогда как алгоритм-1 использует только первое поле каждого индекса. Поскольку алгоритм-2 использует больше данных индексов, NGQP обоснованно считает его лучшим. Оценки близки, и алгоритм-2 лишь немного опережает алгоритм-1. Но здесь алгоритм-2 действительно является правильным выбором.

К сожалению, в этом приложении алгоритм-2 работает медленнее алгоритма-1.

Проблема в том, что индексы не имеют одинакового качества. У фиксации, скорее всего, будет только один потомок. Поэтому первое поле PLINK_I1 обычно сокращает поиск до одной строки. Но существует много тысяч фиксаций с тегом "trunk", поэтому первое поле TAGXREF_I1 мало помогает сузить поиск.

NGQP не может знать, что TAGXREF_I1 почти бесполезен для этого запроса, если в базе данных не выполнена команда ANALYZE. Команда ANALYZE собирает статистику о качестве различных индексов и сохраняет её в таблице SQLITE_STAT1. Получив доступ к этой статистике, NGQP легко выбирает алгоритм-1 как лучший, причём с большим отрывом.

Почему прежний планировщик запросов не выбрал алгоритм-2? Всё просто: алгоритм NN даже не рассматривал алгоритм-2. Графы задачи планирования выглядят так:

В случае «без ANALYZE» слева алгоритм NN выбирает цикл P (PLINK) в качестве внешнего, поскольку 4.9 меньше 5.2, и получает путь P-T, то есть алгоритм-1. NN рассматривает только один лучший вариант на каждом шаге, поэтому полностью упускает тот факт, что 5.2+4.4 даёт план немного дешевле, чем 4.9+4.8. Однако алгоритм N3 отслеживает 5 лучших путей для соединения двух таблиц и в итоге выбирает путь T-P из-за его немного меньшей общей стоимости. Путь T-P — это алгоритм-2.

Обратите внимание: при использовании ANALYZE оценки стоимости лучше соответствуют действительности, и алгоритм-1 выбирают и NN, и N3.

(Примечание: оценки стоимости в двух последних графах были рассчитаны NGQP с использованием логарифма по основанию 2 и немного иных предположений о стоимости, чем в прежнем планировщике запросов. Поэтому оценки стоимости на этих двух графах нельзя напрямую сравнивать с оценками стоимости на графе TPC-H Q8.)

5.2. Устранение проблемы

Выполнение ANALYZE для базы данных репозитория сразу устранило проблему производительности. Однако мы хотим, чтобы Fossil работал надёжно и быстро независимо от того, выполнялся ли анализ его репозитория. Поэтому запрос был изменён: вместо обычного оператора JOIN в нём используется оператор CROSS JOIN. SQLite не меняет порядок таблиц в CROSS JOIN. Эта давно существующая возможность SQLite специально предназначена для того, чтобы опытные программисты могли задавать определённый порядок вложенности циклов. После замены JOIN на CROSS JOIN (добавления одного ключевого слова) NGQP был вынужден выбирать более быстрый алгоритм-1 независимо от того, собиралась ли статистика с помощью ANALYZE.

Мы называем алгоритм-1 «более быстрым», но это не совсем так. Алгоритм-1 быстрее в обычных репозиториях, однако можно создать репозиторий, в котором каждая фиксация находится в отдельной ветке с уникальным именем, а все фиксации являются потомками корневой фиксации. В таком случае TAGXREF_I1 станет селективнее PLINK_I1, и алгоритм-2 действительно будет быстрее. Однако такие репозитории вряд ли встретятся на практике, поэтому в данном случае жёстко заданный порядок вложенности циклов с помощью синтаксиса CROSS JOIN — разумное решение проблемы.

5.3. Обновление 2017 года: лучшее решение

Предыдущий текст был написан в начале 2013 года, до первого выпуска SQLite версии 3.8.0. Этот абзац добавлен в середине 2021 года. Хотя всё сказанное выше остаётся верным, в планировщик запросов внесено много улучшений, из-за чего весь этот раздел во многом утратил актуальность.

В 2017 году Fossil был улучшен: в нём начали использовать новую инструкцию PRAGMA optimize. Перед закрытием соединения с базой данных репозитория Fossil сначала выполняет «PRAGMA optimize», которая, в свою очередь, запускает ANALYZE, если это необходимо. Обычно выполнять ANALYZE не требуется, поэтому измеримого снижения производительности из-за этого нет. Но время от времени ANALYZE может выполняться для нескольких таблиц базы данных репозитория. Благодаря этому в Fossil больше не возникают проблемы планирования запросов, подобные описанной здесь. Периодическое выполнение ANALYZE для поддержания актуальности таблицы sqlite_stat1 означает, что ручная настройка запросов больше не нужна. Мы уже давно не меняли запросы в Fossil.

Поэтому сейчас для предотвращения подобных проблем рекомендуется просто выполнять «PRAGMA optimize» непосредственно перед закрытием каждого соединения с базой данных. Если же приложение работает длительное время и никогда не закрывает соединения с базой данных, выполняйте «PRAGMA optimize» примерно раз в день. Также рекомендуется выполнять «PRAGMA optimize» после любого изменения схемы.

6. Список рекомендаций по предотвращению и устранению проблем планировщика запросов

Не паникуйте! Случаи, когда планировщик запросов выбирает неоптимальный план, на самом деле довольно редки. Вряд ли в вашем приложении возникнут какие-либо проблемы. Если у вас нет проблем с производительностью, беспокоиться обо всём этом не нужно.
Создавайте подходящие индексы. Большинство проблем с производительностью SQL возникает не из-за планировщика запросов, а из-за отсутствия подходящих индексов. Убедитесь, что для всех больших запросов доступны индексы. Большинство проблем с производительностью можно решить одной или двумя командами CREATE INDEX без каких-либо изменений кода приложения.
Не создавайте низкокачественные индексы. (В рамках этого списка рекомендаций) низкокачественным считается индекс, если в таблице более 10 или 20 строк имеют одинаковое значение в крайнем левом столбце индекса. В частности, не используйте логические столбцы или столбцы-перечисления в качестве крайних левых столбцов индексов.

Описанная в предыдущем разделе проблема производительности Fossil возникла из-за того, что в таблице TAGXREF было более десяти тысяч записей с одинаковым значением крайнего левого столбца (столбца TAGID) индекса TAGXREF_I1.
Если необходимо использовать низкокачественный индекс, обязательно выполните ANALYZE. Низкокачественные индексы не будут вводить планировщик запросов в заблуждение, если он знает об их низком качестве. Планировщик получает эти сведения из таблицы SQLITE_STAT1, данные которой вычисляет команда ANALYZE.

Разумеется, ANALYZE эффективна только в том случае, если в базе данных уже есть значительный объём данных. Создавая новую базу данных, в которой со временем должно накопиться много данных, можно выполнить команду «ANALYZE sqlite_schema», чтобы создать таблицу SQLITE_STAT1, а затем предварительно заполнить таблицу sqlite_stat1 (с помощью обычных операторов INSERT) данными, описывающими типичную базу данных для вашего приложения. Например, можно взять данные из хорошо заполненной шаблонной базы данных в лаборатории после выполнения ANALYZE. Или же перед закрытием соединений с базой данных можно просто выполнить «PRAGMA optimize», чтобы ANALYZE запускалась автоматически по мере необходимости и поддерживала актуальность таблицы sqlite_stat1.
Инструментируйте код. Добавьте логику, которая позволит быстро и просто определять, какие запросы выполняются слишком долго. Затем займитесь только этими конкретными запросами.

Обновление 2024 года: За прошедшие годы планировщик запросов был настолько улучшен, что вам никогда не понадобится использовать какие-либо хаки, описанные ниже. Указанные ниже возможности по-прежнему доступны для обеспечения обратной совместимости. Но использовать их не следует. Если вы обнаружите случай, когда получаете неоптимальный план запроса, сообщите об этом разработчикам SQLite на форуме SQLite, чтобы они могли попытаться устранить проблему. Иными словами:

Дальше читать не нужно!
Чтобы помочь вам не продолжать чтение, оставшаяся часть этого списка теперь отображается серым цветом.
Используйте SQL-функции unlikely() и likelihood(). Обычно SQLite предполагает, что условия в предложении WHERE, которые нельзя использовать с индексами, с высокой вероятностью истинны. Если это предположение неверно, оно может привести к неоптимальному плану запроса. SQL-функции unlikely() и likelihood() позволяют сообщить планировщику запросов, что условия в предложении WHERE, вероятно, ложны, и тем самым помочь ему выбрать наилучший возможный план.
Используйте синтаксис CROSS JOIN, чтобы задать определённый порядок вложенности циклов в запросах, которые могут использовать низкокачественные индексы в базе данных, для которой не выполнялся анализ. SQLite особым образом обрабатывает оператор CROSS JOIN, заставляя таблицу слева быть внешним циклом относительно таблицы справа.
Используйте унарный оператор «+», чтобы исключить условия из предложения WHERE. Если планировщик запросов упорно выбирает низкокачественный индекс для конкретного запроса, хотя доступен индекс гораздо более высокого качества, то осторожное использование унарного оператора «+» в предложении WHERE может заставить планировщик отказаться от низкокачественного индекса. По возможности избегайте этого приёма, особенно на ранних этапах разработки приложения. Имейте в виду, что добавление унарного оператора «+» к выражению равенства может изменить результат этого выражения, если задействована аффинность типа.
Используйте синтаксис INDEXED BY, чтобы принудительно выбрать определённые индексы для проблемных запросов. Как и в случае с двумя предыдущими рекомендациями, по возможности избегайте этого шага, особенно на ранних этапах разработки: это явно преждевременная оптимизация.

7. Итоги

Обычно планировщик запросов SQLite отлично справляется с выбором быстрых алгоритмов выполнения SQL-операторов. Это справедливо для прежнего планировщика запросов и ещё в большей степени — для нового NGQP. Иногда из-за неполной информации планировщик запросов может выбрать неоптимальный план. С NGQP такое случается реже, чем с прежним планировщиком запросов, но всё же возможно. Только в этих редких случаях разработчикам приложений нужно вмешаться и помочь планировщику запросов сделать правильный выбор. В обычной ситуации NGQP — просто новое улучшение SQLite, которое немного ускоряет работу приложения и не требует от разработчика никаких новых размышлений или действий.

Последнее обновление этой страницы: 2025-07-12 15:11:36Z

SQLite is in the Public Domain.
https://sqlite.org/queryplanner-ng.html