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

Использование команды EXPLAIN QUERY PLAN поможет вам понять, как NGQP формирует планы выполнения SQL-запросов. EXPLAIN QUERY PLAN

Планировщик запросов определяет лучший алгоритм, или план, для выполнения SQL-запроса. С версии SQLite 3.8.0 (26 августа 2013 года) компонент планировщика запросов был переработан для повышения скорости и качества создаваемых планов. Новая версия называется «планировщик запросов следующего поколения» или NGQP.

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

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

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

Планировщики запросов делают СУБД на основе SQL особенно полезными, позволяя программам сосредоточиться на более высокоуровневых задачах и обеспечивать большую ценность для пользователей.

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

2.1. Как планировщик запросов SQLite строит план выполнения

SQLite вычисляет соединения с помощью вложенных циклов — по одному циклу на каждую таблицу в соединении. Дополнительные циклы могут вставляться для операторов IN и OR в предложении WHERE; SQLite учитывает и их, но для простоты мы проигнорируем их в этой статье.

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

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

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

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

Когда Гарантия стабильности планировщика запросов (Query Planner Stability Guarantee, QPSG) включена, SQLite всегда будет выбирать один и тот же план запроса для любого заданного SQL-оператора при условии, что:

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

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

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

Клиент-серверные СУБД обычно не предоставляют такой гарантии. В клиент-серверных СУБД сервер отслеживает статистику по размерам таблиц и качеству индексов, и планировщик запросов использует эту статистику для выбора наилучших планов.

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

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

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

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

См. также:

• Recommended usage patterns for ANALYZE
• PRAGMA optimize

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

«TPC-H Q8» — это тестовый запрос от Transaction Processing Performance Council. Планировщики запросов в SQLite версий 3.7.17 и более ранних не выбирают хорошие планы для TPC-H Q8, и было установлено, что никакая настройка устаревшего планировщика это не исправит.

Для того чтобы найти хорошее решение для запроса TPC-H Q8 и продолжить повышение качества планировщика запросов SQLite, стало необходимым перепроектировать его. В этом разделе делается попытка объяснить, почему это перепроектирование было необходимо и чем NGQP отличается от предшественника и как решает проблему TPC-H Q8.

3.1. Детали запроса

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

6.00 2.08 9.17 2.30 2.77 4.03 2.64 5.30 2.08 6.40 1.79 3.47 2.64 6.01
* 5.52 * 9.47 * 16.40 * 13.87 * 12.56 * 5.52 * 3.56 * 7.71

На диаграмме каждая из 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 всегда использовал эвристику «Ближайшего соседа» (Nearest Neighbor, NN) при поиске наилучшего плана запроса. Эвристика NN выполняет единственный обход графа, всегда выбирая дугу с наименьшей стоимостью в качестве следующего шага. Эвристика NN работает удивительно хорошо в большинстве случаев.

При этом NN работает быстро, так что SQLite способен быстро находить хорошие планы даже для больших join из 64 таблиц. Для сравнения, другие СУБД на основе SQL, выполняющие более обширный поиск, как правило, замедляются, когда количество таблиц в join превышает 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 — количество таблиц в join), и поэтому при join более чем из 10 таблиц время выполнения sqlite3_prepare() становится очень большим.

3.4. Алгоритм N ближайших соседей (N3) в планировщике SQLite

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 есть 8 узлов, поэтому процесс повторяется в общей сложности 8 раз. В общем случае K-стороннего соединения требование к памяти составляет O(N), а время вычисления — O(K*N), что значительно быстрее точного решения O(2^K).

Но какое значение выбрать для N? Можно попробовать N=K. Это делает алгоритм O(K²), что по-прежнему вполне эффективно, поскольку максимальное значение K равно 64, а K редко превышает 10. Но для задачи TPC-H Q8 этого недостаточно. При N=8 на TPC-H Q8 алгоритм N3 находит решение 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. Предыстория: что такое звёздный запрос

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

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

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

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

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

• время и сумма продажи;
• идентификаторы PRODUCT-id, SELLER-id, CUSTOMER-id, CARRIER-id и WAREHOUSE-id.

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

Это классический пример схемы типа «звезда». Подобные представления данных встречаются постоянно и в самых разных областях. Запросы к такой схеме мы называем «звёздными запросами». Например, запрос полного отчёта обо всех продажах в период с 12:00 до 14:00 4 января 2024 года будет звёздным запросом.

Сначала в таблице SALES будут найдены все записи в указанном временном диапазоне, а затем в различных таблицах измерений будет выполнен поиск информации о каждой отдельной продаже.

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

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

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

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

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

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

N3 в конечном счёте всегда найдёт лучший план при достаточно большом значении N. Проблема в том, что достаточно большое 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 наиболее свежих коммитов, удовлетворяющих хотя бы одному из трёх условий:

1. Коммит имеет тег «trunk».
2. Коммит имеет дочерний коммит с тегом «trunk».
3. Коммит имеет родительский коммит с тегом «trunk».

Первое условие обеспечивает отображение всех коммитов ветки trunk, а второе и третье — включение коммитов, которые сливаются в trunk или ответвляются от него. Три условия реализованы тремя связанными оператором OR выражениями EXISTS в предложении 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);

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

• Алгоритм-1: найти всех потомков коммита $ckid и проверить каждого из них на наличие тега $trunk.
• Алгоритм-2: найти все коммиты с тегом $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:
4.8 2.08
* 4.9 * 5.2
P T

с ANALYZE:
4.4 3.8
* 3.9 * 6.1
P T

В случае «без 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 был надёжным и всегда работал быстро независимо от того, был ли выполнен ANALYZE для его репозитория или нет. По этой причине запрос был изменён: вместо обычного оператора 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 строк имеют одинаковое значение в крайнем левом столбце индекса. В частности, избегайте использования булевых столбцов или столбцов типа «enum» в качестве крайних левых столбцов ваших индексов.

Проблема с производительностью 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 для принудительного выбора конкретных индексов в проблемных запросах. Как и в случае с двумя предыдущими пунктами, по возможности избегайте этого шага, и особенно избегайте его на ранних этапах разработки, поскольку это явно является преждевременной оптимизацией

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

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

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

Ответы на эти вопросы могут быть для вас полезными

Что такое NGQP и чем он отличается от прежнего планировщика запросов SQLite?

NGQP (Next-Generation Query Planner) — планировщик запросов следующего поколения, введённый в SQLite 3.8.0. В отличие от прежнего планировщика, использовавшего эвристику «Ближайшего соседа» (NN), NGQP применяет алгоритм N ближайших соседей (N3), который отслеживает сразу N лучших путей на каждом шаге поиска и потому находит более оптимальные планы для сложных многотабличных соединений.

Почему для звёздных запросов с большим числом таблиц измерений N3 иногда выбирает неоптимальный план?

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

Когда стоит запускать ANALYZE и как это влияет на планировщик запросов?

ANALYZE собирает статистику о качестве индексов и сохраняет её в таблице SQLITE_STAT1. Имея эти данные, NGQP делает значительно более точные оценки стоимости и выбирает лучшие планы. Рекомендуется запускать PRAGMA optimize перед закрытием каждого соединения с базой данных — это автоматически инициирует ANALYZE там, где это необходимо.

Что такое Гарантия стабильности планировщика запросов (QPSG) и зачем она нужна?

QPSG гарантирует, что SQLite будет выбирать один и тот же план запроса для одного и того же SQL-оператора при неизменной схеме, без повторного запуска ANALYZE и при использовании одной и той же версии SQLite. Это особенно важно для встраиваемых приложений, где нет администратора базы данных, способного оперативно реагировать на неожиданные изменения планов после развёртывания.

Как принудительно задать порядок вложенности циклов, если планировщик выбирает неоптимальный план?

Используйте синтаксис CROSS JOIN вместо обычного JOIN. SQLite не переупорядочивает таблицы в CROSS JOIN, что позволяет явно зафиксировать нужный порядок вложенности циклов. Именно этот приём был применён в Fossil DVCS для устранения регрессии производительности после перехода на NGQP.