Новейший планировщик запросов

1. Введение

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

Переработка называется «планировщиком запросов следующего поколения» или «NGQP».

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

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

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

2. Общие сведения

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

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

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

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

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

1. Выбор вложенного порядка различных циклов
2. Выбор хороших индексов для каждого цикла

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

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

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

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

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

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

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

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

См. также:

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

4. Опасности обновления до NGQP

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

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

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

Основные моменты:

• NGQP всегда найдет такой же или лучший план запроса по сравнению с предыдущими планировщиками запросов, если у него есть доступ к точным данным ANALYZE в файле SQLITE_STAT1.

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

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

4.1. Исследование случая: обновление Fossil до NGQP

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

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

Один из многих отчетов, предоставляемых Fossil, — это временная шкала изменений в отдельной ветке, отображающая все слияния в эту ветку и из нее. См. https://www.sqlite.org/src/timeline?nd&n=200&r=trunk для типичного примера такого отчета. Генерация такого отчета обычно занимает всего несколько миллисекунд. Но после обновления до NGQP мы заметили, что этот отчет для основной ветки репозитория занимает около 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» или разветвляются из нее. Три условия реализованы тремя операторами 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);

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

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» слева алгоритм 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.)

4.2. Исправление проблемы

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

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

4.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» после любых изменений схемы.

5. Список проверок для предотвращения или исправления проблем планировщика запросов

1. Не паникуйте! Случаи, когда планировщик запросов выбирает худший план, на самом деле довольно редки. В вашем приложении вряд ли возникнут какие-либо проблемы. Если у вас нет проблем с производительностью, вам не нужно беспокоиться ни о чем из этого.

2. Создайте соответствующие индексы. Большинство проблем с производительностью SQL возникают не из-за проблем с планировщиком запросов, а скорее из-за отсутствия соответствующих индексов. Убедитесь, что индексы доступны для всех больших запросов. Большинство проблем с производительностью можно решить с помощью одной или двух команд CREATE INDEX и без изменений в коде приложения.

3. Избегайте создания индексов низкого качества. Индекс низкого качества (в целях этой контрольной страницы) — это индекс, в котором в таблице более 10 или 20 строк с одинаковым значением для левого столбца индекса. В частности, избегайте использования логических или столбцов «перечисления» в качестве левых столбцов ваших индексов.

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

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

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

5. Инструментируйте свой код. Добавьте логику, которая позволит вам быстро и легко узнать, какие запросы занимают слишком много времени. Затем работайте только над этими конкретными запросами.

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

   Чтобы побудить вас прекратить чтение, остальная часть этого списка проверок теперь затененная.

6. Используйте функции SQL unlikely() и likelihood(). SQLite обычно предполагает, что члены в операторе WHERE, которые не могут быть использованы индексами, имеют высокую вероятность быть истинными. Если это предположение неверно, это может привести к неэффективному плану запроса. Функции SQL unlikely() и likelihood() могут использоваться для предоставления подсказок планировщику запросов о членах оператора WHERE, которые, вероятно, не являются истинными, и тем самым помочь планировщику запросов в выборе наилучшего плана.

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

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

9. Используйте синтаксис INDEXED BY для принудительного выбора определенных индексов в проблематичных запросах. Как и в предыдущих двух пунктах, избегайте этого шага, если это возможно, и особенно избегайте его на ранних этапах разработки, так как это явно преждевременная оптимизация.

6. Сводка

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

Эта страница была последняя изменена 10 мая 2024 г. в 14:30:36 по UTC