Обзор оптимизатора запросов SQLite

1. Введение

В этом документе представлен обзор работы планировщика и оптимизатора запросов SQLite.

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

Дополнительные сведения доступны в документе руководство по индексированию. В документе планировщик запросов нового поколения подробнее описано, как выбирается порядок соединения.

2. Анализ предложения WHERE

Перед анализом выполняются следующие преобразования, чтобы перенести все ограничения соединения в предложение WHERE:

• Все соединения NATURAL преобразуются в соединения с предложением USING.
• Все предложения USING (в том числе созданные на предыдущем шаге) преобразуются в эквивалентные предложения ON.
• Все предложения ON (в том числе созданные на предыдущем шаге) добавляются в предложение WHERE как новые конъюнкты (термины, связанные оператором AND).

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

После переноса всех ограничений в предложение WHERE оно разбивается на конъюнкты (далее — «термины»). Иными словами, предложение WHERE разделяется на части, отделённые друг от друга оператором AND. Если предложение WHERE состоит из ограничений, разделённых оператором OR (дизъюнктов), то всё предложение считается одним «термином», к которому применяется оптимизация предложения OR.

Все термины предложения WHERE анализируются на предмет возможности удовлетворить их с помощью индексов. Чтобы термин можно было использовать с индексом, он обычно должен иметь одну из следующих форм:

  column = expression
  column IS expression
  column > expression
  column >= expression
  column < expression
  column <= expression
  expression = column
  expression IS column
  expression > column
  expression >= column
  expression < column
  expression <= column
  column IN (expression-list)
  column IN (subquery)
  column IS NULL
  column LIKE pattern
  column GLOB pattern

Если индекс создан, например, таким оператором:

CREATE INDEX idx_ex1 ON ex1(a,b,c,d,e,...,y,z);

Тогда индекс можно использовать, если первые столбцы индекса (столбцы a, b и так далее) встречаются в терминах предложения WHERE. Для первых столбцов индекса должны использоваться операторы =, IN или IS. Для самого правого используемого столбца можно применять неравенства. Для самого правого используемого столбца индекса можно задать до двух неравенств, ограничивающих допустимые значения столбца двумя границами.

Для использования индекса необязательно, чтобы каждый его столбец встречался в термине предложения WHERE. Однако в последовательности используемых столбцов индекса не должно быть пропусков. Поэтому, если для приведённого выше примера индекса нет термина предложения WHERE, ограничивающего столбец c, термины, ограничивающие столбцы a и b, можно использовать с индексом, а термины, ограничивающие столбцы от d до z, — нельзя. Аналогично, столбцы индекса обычно не используются для индексирования, если они расположены правее столбца, ограниченного только неравенствами. (Исключение описано ниже в разделе об оптимизации пропуска при сканировании.)

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

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

Для приведённого выше индекса и такого предложения WHERE:

... WHERE a=5 AND b IN (1,2,3) AND c IS NULL AND d='hello'

Можно использовать первые четыре столбца индекса — a, b, c и d, — поскольку они образуют префикс индекса и для всех заданы ограничения равенства.

Для приведённого выше индекса и такого предложения WHERE:

... WHERE a=5 AND b IN (1,2,3) AND c>12 AND d='hello'

Можно использовать только столбцы a, b и c индекса. Столбец d использовать нельзя, поскольку он расположен правее c, а для c заданы только ограничения-неравенства.

Для приведённого выше индекса и такого предложения WHERE:

... WHERE a=5 AND b IN (1,2,3) AND d='hello'

Можно использовать только столбцы a и b индекса. Столбец d использовать нельзя, поскольку для столбца c нет ограничения, а в наборе столбцов, которые можно использовать с индексом, не должно быть пропусков.

Для приведённого выше индекса и такого предложения WHERE:

... WHERE b IN (1,2,3) AND c NOT NULL AND d='hello'

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

Для приведённого выше индекса и такого предложения WHERE:

... WHERE a=5 OR b IN (1,2,3) OR c NOT NULL OR d='hello'

Индекс нельзя использовать, поскольку термины предложения WHERE связаны оператором OR, а не AND. Этот запрос приведёт к полному сканированию таблицы. Однако если добавить ещё три индекса, в которых столбцы b, c и d будут самыми левыми, может примениться оптимизация предложения OR.

3. Оптимизация BETWEEN

Если термин предложения WHERE имеет следующий вид:

  expr1 BETWEEN expr2 AND expr3

Тогда добавляются два «виртуальных» термина:

  expr1 >= expr2 AND expr1 <= expr3

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

4. Оптимизации OR

Ограничения предложения WHERE, связанные оператором OR, а не AND, можно обрабатывать двумя способами.

4.1. Преобразование ограничения, связанного с OR, в оператор IN

Если термин состоит из нескольких подтемов, содержащих общее имя столбца и разделённых оператором OR, например:

  column = expr1 OR column = expr2 OR column = expr3 OR ...

Тогда этот термин переписывается следующим образом:

  column IN (expr1,expr2,expr3,...)

Переписанный термин может использоваться для ограничения индекса по обычным правилам для операторов IN. Обратите внимание: column должен обозначать один и тот же столбец во всех подтерминах, связанных оператором OR, хотя он может находиться как слева, так и справа от оператора =.

4.2. Раздельная оценка ограничений OR и объединение результатов

Если описанное выше преобразование OR в оператор IN неприменимо, предпринимается попытка использовать вторую оптимизацию предложения OR. Предположим, предложение OR состоит из нескольких подтерминов следующего вида:

  expr1 OR expr2 OR expr3

Отдельные подтермины могут быть одиночными выражениями сравнения, такими как a=5 или x>y, выражениями LIKE или BETWEEN либо списками подподтерминов, связанных оператором AND и заключённых в скобки. Каждый подтермин анализируется так, как если бы он сам был всем предложением WHERE, чтобы определить, можно ли отдельно для него использовать индекс. Если каждый подтермин предложения OR по отдельности допускает использование индекса, предложение OR может быть обработано так, чтобы для оценки каждого его термина использовался отдельный индекс. Чтобы представить, как SQLite использует отдельные индексы для каждого термина предложения OR, можно вообразить, что предложение WHERE переписывается следующим образом:

  rowid IN (SELECT rowid FROM table WHERE expr1
            UNION SELECT rowid FROM table WHERE expr2
            UNION SELECT rowid FROM table WHERE expr3)

Приведённое выше выражение — лишь концептуальная иллюстрация; предложения WHERE, содержащие OR, на самом деле так не переписываются. Фактическая реализация предложения OR использует более эффективный механизм, который работает также для таблиц WITHOUT ROWID и таблиц, в которых «rowid» недоступен. Тем не менее суть реализации передаёт приведённое выше утверждение: для поиска строк-кандидатов результата по каждому термину предложения OR используются отдельные индексы, а итоговый результат представляет собой объединение этих строк.

Обратите внимание, что в большинстве случаев SQLite использует только один индекс для каждой таблицы в предложении FROM запроса. Описанная здесь вторая оптимизация предложения OR является исключением из этого правила. Для предложения OR для каждого его подтермина может использоваться отдельный индекс.

Возможность применить описанную здесь оптимизацию предложения OR не гарантирует, что она будет применена для конкретного запроса. SQLite использует планировщик запросов на основе стоимости, который оценивает затраты ЦП и дискового ввода-вывода для различных конкурирующих планов запросов и выбирает тот, который, по его мнению, будет самым быстрым. Если в предложении WHERE много терминов OR или некоторые индексы для отдельных подтерминов OR недостаточно избирательны, SQLite может решить, что быстрее будет использовать другой алгоритм запроса или даже выполнить полное сканирование таблицы. Разработчики приложений могут добавить к оператору префикс EXPLAIN QUERY PLAN, чтобы получить общую картину выбранной стратегии выполнения запроса.

5. Оптимизация LIKE

Термин предложения WHERE с оператором LIKE или GLOB иногда можно использовать с индексом для поиска по диапазону — почти так же, как если бы LIKE или GLOB были альтернативой оператору BETWEEN. Для этой оптимизации существует множество условий:

1. Правая часть LIKE или GLOB должна быть строковым литералом либо параметром, связанным со строковым литералом, который не начинается с подстановочного символа.
2. Оператор LIKE или GLOB не должен становиться истинным при числовом значении (вместо строки или BLOB) в левой части. Это означает, что должно выполняться одно из условий:
   1. левая часть оператора LIKE или GLOB — имя индексированного столбца с текстовой аффинностью, или
   2. аргумент-шаблон в правой части не начинается со знака минуса («-») или цифры.
   Это ограничение связано с тем, что числа не сортируются в лексикографическом порядке. Например: 9<10, но '9'>'10'.
3. Встроенные функции, используемые для реализации LIKE и GLOB, не должны быть переопределены с помощью API sqlite3_create_function().
4. Для оператора GLOB столбец должен быть индексирован со встроенной последовательностью сортировки BINARY.
5. Для оператора LIKE, если включён режим case_sensitive_like, столбец должен быть индексирован со встроенной последовательностью сортировки BINARY; если режим case_sensitive_like отключён, столбец должен быть индексирован со встроенной последовательностью сортировки NOCASE.
6. Если используется параметр ESCAPE, символ ESCAPE должен быть символом ASCII или однобайтовым символом в UTF-8.

Для оператора LIKE предусмотрено два режима, которые можно задать с помощью pragma. В режиме по умолчанию сравнения LIKE не учитывают различия регистра для символов latin1. Поэтому по умолчанию следующее выражение истинно:

'a' LIKE 'A'

Если включить pragma case_sensitive_like следующим образом:

PRAGMA case_sensitive_like=ON;

Тогда оператор LIKE учитывает регистр, и приведённый выше пример будет иметь значение false. Обратите внимание, что нечувствительность к регистру распространяется только на символы latin1 — в основном на прописные и строчные буквы английского алфавита в младших 127 кодах ASCII. Для международных наборов символов SQLite учитывает регистр, если приложение не предоставляет определённую приложением последовательность сортировки и функцию SQL like(), учитывающие символы не из ASCII. Если предоставлена определённая приложением последовательность сортировки и/или функция SQL like(), описанная здесь оптимизация LIKE не применяется.

По умолчанию оператор LIKE не учитывает регистр, поскольку этого требует стандарт SQL. Поведение по умолчанию можно изменить во время компиляции, передав компилятору параметр командной строки SQLITE_CASE_SENSITIVE_LIKE.

Оптимизация LIKE может применяться, если столбец слева от оператора индексирован со встроенной последовательностью сортировки BINARY и включён режим case_sensitive_like. Оптимизация также может применяться, если столбец индексирован со встроенной последовательностью сортировки NOCASE и режим case_sensitive_like отключён. Это единственные два сочетания, при которых операторы LIKE оптимизируются.

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

Оптимизация LIKE предпринимается только в том случае, если правая часть оператора GLOB или LIKE — строковый литерал либо параметр, который был привязан к строковому литералу. Строковый литерал не должен начинаться с подстановочного символа; если правая часть начинается с такого символа, оптимизация не применяется. Если правая часть — параметр, связанный со строкой, оптимизация предпринимается только в том случае, если подготовленный оператор, содержащий выражение, был скомпилирован с помощью sqlite3_prepare_v2() или sqlite3_prepare16_v2(). Оптимизация LIKE не применяется, если правая часть — параметр, а оператор подготовлен с помощью sqlite3_prepare() или sqlite3_prepare16().

Предположим, что начальная последовательность символов справа от оператора LIKE или GLOB, не являющихся подстановочными, — x. Для обозначения этого префикса, не содержащего подстановочных символов, мы используем один символ, но читателю следует иметь в виду, что префикс может состоять более чем из одного символа. Пусть y — наименьшая строка той же длины, что и /x/, которая при сравнении оказывается больше x. Например, если x — 'hello', то y будет 'hellp'. Оптимизации LIKE и GLOB заключаются в добавлении двух виртуальных терминов следующего вида:

  column >= x AND column < y

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

  column LIKE x%
  column GLOB x*

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

Обратите внимание: если правая часть оператора LIKE или GLOB — это параметр, а оператор подготовлен с помощью sqlite3_prepare_v2() или sqlite3_prepare16_v2(), то при первом вызове sqlite3_step() каждого запуска оператор автоматически повторно анализируется и компилируется, если привязка параметра в правой части изменилась с момента предыдущего запуска. Повторный анализ и компиляция по сути совпадают с действиями, выполняемыми после изменения схемы. Повторная компиляция необходима, чтобы планировщик запросов мог проверить новое значение, привязанное к правой части оператора LIKE или GLOB, и определить, следует ли применять описанную выше оптимизацию.

6. Оптимизация пропуска при сканировании

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

Рассмотрим таблицу следующего вида:

CREATE TABLE people(
  name TEXT PRIMARY KEY,
  role TEXT NOT NULL,
  height INT NOT NULL, -- in cm
  CHECK( role IN ('student','teacher') )
);
CREATE INDEX people_idx1 ON people(role, height);

В таблице people хранится по одной записи для каждого человека в крупной организации. Каждый человек является либо «студентом», либо «преподавателем», что определяется полем «role». В таблице также записан рост каждого человека в сантиметрах. Столбцы role и height индексированы. Обратите внимание, что самый левый столбец индекса имеет низкую избирательность — он содержит всего два возможных значения.

Теперь рассмотрим запрос, который находит имена всех людей в организации ростом не менее 180 см:

SELECT name FROM people WHERE height>=180;

Поскольку самый левый столбец индекса не встречается в предложении WHERE запроса, можно предположить, что индекс здесь использовать нельзя. Однако SQLite может использовать этот индекс. Концептуально SQLite работает с ним так, словно запрос имеет примерно следующий вид:

SELECT name FROM people
 WHERE role IN (SELECT DISTINCT role FROM people)
   AND height>=180;

Или такой:

SELECT name FROM people WHERE role='teacher' AND height>=180
UNION ALL
SELECT name FROM people WHERE role='student' AND height>=180;

Приведённые выше альтернативные варианты запросов служат только для иллюстрации. SQLite на самом деле не преобразует запрос. Фактический план запроса работает следующим образом: SQLite находит первое возможное значение для «role». Для этого он перематывает индекс «people_idx1» в начало и считывает первую запись. SQLite сохраняет первое значение «role» во внутренней переменной, которую мы здесь назовём «$role». Затем SQLite выполняет запрос вида: «SELECT name FROM people WHERE role=$role AND height>=180». В этом запросе есть ограничение равенства для самого левого столбца индекса, поэтому для его обработки можно использовать индекс. После выполнения запроса SQLite с помощью индекса «people_idx1» находит следующее значение столбца «role», используя код, логически аналогичный «SELECT role FROM people WHERE role>$role LIMIT 1». Это новое значение «role» перезаписывает переменную $role, и процесс повторяется, пока не будут проверены все возможные значения «role».

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

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

Единственный способ узнать, что в самых левых столбцах индекса много повторяющихся значений, — выполнить команду ANALYZE для базы данных. Без результатов ANALYZE SQLite приходится предполагать «структуру» данных в таблице; по умолчанию он считает, что для каждого значения самого левого столбца индекса в среднем имеется 10 повторов. Пропуск при сканировании становится выгодным (то есть начинает работать быстрее полного сканирования таблицы), только когда число повторов составляет примерно 18 или больше. Поэтому пропуск при сканировании никогда не используется в базе данных, для которой не выполнялась команда ANALYZE.

7. Соединения

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

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

SQLite обрабатывает оператор CROSS JOIN особым образом. Теоретически оператор CROSS JOIN коммутативен. Однако SQLite никогда не меняет порядок таблиц в CROSS JOIN. Это позволяет программисту принудительно задать SQLite определённый порядок вложенности циклов.

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

Порядок соединения меняется автоматически, и обычно это работает достаточно хорошо, чтобы программистам не приходилось об этом задумываться, особенно если команда ANALYZE использовалась для сбора статистики о доступных индексах. Тем не менее иногда необходимы подсказки от программиста. Рассмотрим, например, следующую схему:

CREATE TABLE node(
   id INTEGER PRIMARY KEY,
   name TEXT
);
CREATE INDEX node_idx ON node(name);
CREATE TABLE edge(
   orig INTEGER REFERENCES node,
   dest INTEGER REFERENCES node,
   PRIMARY KEY(orig, dest)
);
CREATE INDEX edge_idx ON edge(dest,orig);

Приведённая выше схема задаёт ориентированный граф, в котором каждому узлу можно присвоить имя. Теперь рассмотрим запрос к этой схеме:

SELECT *
  FROM edge AS e,
       node AS n1,
       node AS n2
 WHERE n1.name = 'alice'
   AND n2.name = 'bob'
   AND e.orig = n1.id
   AND e.dest = n2.id;

Этот запрос извлекает все сведения о рёбрах, ведущих от узлов с меткой «alice» к узлам с меткой «bob». По сути, у оптимизатора запросов SQLite есть два варианта реализации этого запроса. (На самом деле вариантов шесть, но здесь мы рассмотрим только два.) Ниже приведён псевдокод, демонстрирующий эти два варианта.

Вариант 1:

foreach n1 where n1.name='alice' do:
  foreach n2 where n2.name='bob' do:
    foreach e where e.orig=n1.id and e.dest=n2.id
      return n1.*, n2.*, e.*
    end
  end
end

Вариант 2:

foreach n1 where n1.name='alice' do:
  foreach e where e.orig=n1.id do:
    foreach n2 where n2.id=e.dest and n2.name='bob' do:
      return n1.*, n2.*, e.*
    end
  end
end

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

Какой же план запроса лучше? Оказывается, ответ зависит от того, какие данные содержатся в таблицах node и edge.

Пусть число узлов alice равно M, а число узлов bob — N. Рассмотрим два сценария. В первом сценарии M и N равны 2, но у каждого узла тысячи рёбер. В этом случае предпочтителен вариант 1. В варианте 1 внутренний цикл проверяет, существует ли ребро между парой узлов, и, если оно найдено, выводит результат. Поскольку узлов alice и bob всего по два, внутренний цикл выполняется лишь четыре раза, и запрос работает очень быстро. Вариант 2 здесь работает гораздо медленнее. Внешний цикл варианта 2 выполняется всего два раза, но из каждого узла alice выходит много рёбер, поэтому средний цикл должен выполнить тысячи итераций. Это будет намного медленнее. Итак, в первом сценарии предпочтителен вариант 1.

Теперь рассмотрим случай, когда M и N равны 3500. Узлов Alice много. Предположим, что каждый из этих узлов связан всего одним или двумя рёбрами. Теперь предпочтителен вариант 2. Внешний цикл варианта 2 по-прежнему выполняется 3500 раз, но средний цикл выполняется один или два раза для каждой итерации внешнего цикла, а внутренний цикл — не более одного раза для каждой итерации среднего цикла. Таким образом, внутренний цикл выполняется в общей сложности около 7000 раз. Вариант 1, напротив, должен выполнить внешний и средний циклы по 3500 раз, что приводит к 12 миллионам итераций среднего цикла. Поэтому во втором сценарии вариант 2 почти в 2000 раз быстрее варианта 1.

Как видите, в зависимости от структуры данных в таблице лучше может оказаться как план запроса 1, так и план запроса 2. Какой план SQLite выбирает по умолчанию? Начиная с версии 3.6.18, если команда ANALYZE не выполнялась, SQLite выбирает вариант 2. Если выполнить команду ANALYZE для сбора статистики, SQLite может сделать другой выбор, если статистика показывает, что альтернативный вариант, вероятно, будет быстрее.

7.1. Ручное управление порядком соединения

Почти всегда SQLite автоматически выбирает наилучший порядок соединения. Разработчику очень редко приходится вмешиваться и подсказывать планировщику запросов оптимальный порядок соединения. Лучше всего использовать PRAGMA optimize, чтобы планировщик запросов располагал актуальной статистикой о структуре данных в базе данных.

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

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

7.1.1. Ручное управление планами запросов с помощью таблиц SQLITE_STAT

SQLite позволяет опытным программистам управлять планом запроса, выбранным оптимизатором. Один из способов — подправить результаты ANALYZE в таблице sqlite_stat1.

7.1.2. Ручное управление планами запросов с помощью CROSS JOIN

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

В следующем запросе оптимизатор может переставлять таблицы предложения FROM любым подходящим образом:

SELECT *
  FROM node AS n1,
       edge AS e,
       node AS n2
 WHERE n1.name = 'alice'
   AND n2.name = 'bob'
   AND e.orig = n1.id
   AND e.dest = n2.id;

В следующей логически эквивалентной записи того же запроса замена «,» на «CROSS JOIN» означает, что порядок таблиц должен быть N1, E, N2.

SELECT *
  FROM node AS n1 CROSS JOIN
       edge AS e CROSS JOIN
       node AS n2
 WHERE n1.name = 'alice'
   AND n2.name = 'bob'
   AND e.orig = n1.id
   AND e.dest = n2.id;

Для последнего запроса план должен соответствовать варианту 2. Обратите внимание: чтобы отключить оптимизацию перестановки таблиц, необходимо использовать ключевое слово «CROSS»; INNER JOIN, NATURAL JOIN, JOIN и другие подобные сочетания работают так же, как соединение с помощью запятой, поэтому оптимизатор может переставлять таблицы по своему усмотрению. (Перестановка таблиц также отключена для внешнего соединения, но потому, что внешние соединения не обладают ассоциативностью и коммутативностью. Перестановка таблиц в OUTER JOIN меняет результат.)

См. раздел «Практический пример обновления Fossil до NGQP» — ещё один реальный пример использования CROSS JOIN для ручного управления порядком вложения соединений. Контрольный список планировщика запросов, приведённый далее в том же документе, содержит дополнительные рекомендации по ручному управлению планировщиком запросов.

8. Выбор между несколькими индексами

Каждая таблица в предложении FROM запроса может использовать не более одного индекса (кроме случаев применения оптимизации OR-условия), и SQLite стремится использовать хотя бы один индекс для каждой таблицы. Иногда для одной таблицы могут подходить два или более индекса. Например:

CREATE TABLE ex2(x,y,z);
CREATE INDEX ex2i1 ON ex2(x);
CREATE INDEX ex2i2 ON ex2(y);
SELECT z FROM ex2 WHERE x=5 AND y=6;

Для приведённой выше инструкции SELECT оптимизатор может использовать индекс ex2i1, чтобы найти строки ex2, в которых x=5, а затем проверить каждую строку на соответствие условию y=6. Или он может использовать индекс ex2i2, чтобы найти строки ex2, в которых y=6, а затем проверить каждую из этих строк на соответствие условию x=5.

Если приходится выбирать между двумя или более индексами, SQLite пытается оценить общий объём работы, необходимый для выполнения запроса с каждым из вариантов. Затем он выбирает вариант с наименьшим предполагаемым объёмом работы.

Чтобы помочь оптимизатору точнее оценить объём работы, связанный с использованием различных индексов, пользователь может выполнить команду ANALYZE. Команда ANALYZE сканирует все индексы базы данных, для которых возможен выбор между двумя или более индексами, и собирает статистику об избирательности этих индексов. Статистика, собранная при сканировании, хранится в специальных таблицах базы данных, имена которых начинаются с "sqlite_stat". Содержимое этих таблиц не обновляется при изменении базы данных, поэтому после существенных изменений может быть целесообразно повторно выполнить ANALYZE. Результаты команды ANALYZE доступны только подключениям к базе данных, открытым после завершения команды ANALYZE.

Различные таблицы sqlite_statN содержат сведения об избирательности различных индексов. Например, таблица sqlite_stat1 может указывать, что ограничение равенства для столбца x в среднем сокращает область поиска до 10 строк, тогда как ограничение равенства для столбца y сокращает область поиска в среднем до 3 строк. В таком случае SQLite предпочтёт использовать индекс ex2i2, поскольку он более избирателен.

8.1. Исключение условий WHERE с помощью унарного «+»

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

Условия предложения WHERE можно вручную исключить из использования индексов, поставив перед именем столбца унарный оператор +. Унарный оператор + ничего не делает и не приводит к генерации байт-кода в подготовленной инструкции. Однако унарный оператор + не позволяет условию ограничивать индекс. Поэтому, если переписать приведённый выше запрос следующим образом:

SELECT z FROM ex2 WHERE +x=5 AND y=6;

Оператор + для столбца x не позволит этому условию ограничивать индекс. Это принудительно приведёт к использованию индекса ex2i2.

Обратите внимание, что унарный оператор + также удаляет из выражения типовую аффинность, и в некоторых случаях это может привести к незаметным изменениям смысла выражения. В приведённом выше примере, если столбец x имеет текстовую аффинность, сравнение "x=5" будет выполняться как текстовое. Оператор + удаляет аффинность. Поэтому при сравнении "+x=5" текст в столбце x будет сравниваться с числовым значением 5, и результат всегда будет ложным.

8.2. Диапазонные запросы

Рассмотрим немного иной сценарий:

CREATE TABLE ex2(x,y,z);
CREATE INDEX ex2i1 ON ex2(x);
CREATE INDEX ex2i2 ON ex2(y);
SELECT z FROM ex2 WHERE x BETWEEN 1 AND 100 AND y BETWEEN 1 AND 100;

Предположим также, что значения столбца x распределены в диапазоне от 0 до 1 000 000, а значения столбца y — от 0 до 1 000. В таком случае ограничение диапазона для столбца x должно сократить область поиска в 10 000 раз, тогда как ограничение диапазона для столбца y сократит область поиска лишь в 10 раз. Поэтому следует предпочесть индекс ex2i1.

SQLite выполнит это определение, но только если он был собран с параметром SQLITE_ENABLE_STAT3 или SQLITE_ENABLE_STAT4. Параметры SQLITE_ENABLE_STAT3 и SQLITE_ENABLE_STAT4 заставляют команду ANALYZE собирать гистограмму содержимого столбцов в таблицах sqlite_stat3 или sqlite_stat4 и использовать эту гистограмму, чтобы лучше определять оптимальный запрос для диапазонных ограничений, подобных приведённым выше. Главное различие между STAT3 и STAT4 состоит в том, что STAT3 сохраняет данные гистограммы только для самого левого столбца индекса, тогда как STAT4 сохраняет данные гистограммы для всех столбцов индекса. Для одноколоночных индексов STAT3 и STAT4 работают одинаково.

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

Ещё одно ограничение данных гистограммы заключается в том, что они применимы только к самому левому столбцу индекса. Рассмотрим следующий сценарий:

CREATE TABLE ex3(w,x,y,z);
CREATE INDEX ex3i1 ON ex2(w, x);
CREATE INDEX ex3i2 ON ex2(w, y);
SELECT z FROM ex3 WHERE w=5 AND x BETWEEN 1 AND 100 AND y BETWEEN 1 AND 100;

Здесь неравенства относятся к столбцам x и y, которые не являются самыми левыми столбцами индекса. Поэтому данные гистограммы не помогут выбрать между диапазонными ограничениями для столбцов x и y.

9. Покрывающие индексы

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

Если индекс содержит все данные, необходимые для запроса, и обращаться к исходной таблице не требуется, такой индекс называется «покрывающим индексом».

10. Оптимизация ORDER BY

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

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

10.1. Частичная сортировка ORDER BY с помощью индекса

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

11. Сведение подзапросов

Когда подзапрос находится в предложении FROM инструкции SELECT, простейший вариант поведения — вычислить подзапрос во временную таблицу, а затем выполнить внешний SELECT для этой временной таблицы. Такой план может быть неоптимальным, поскольку у временной таблицы не будет индексов, а внешний запрос (который, вероятно, является соединением) будет вынужден либо полностью сканировать временную таблицу, либо создать для неё индекс на время выполнения запроса; ни один из этих вариантов не отличается особой быстротой.

Чтобы решить эту проблему, SQLite пытается свести подзапросы в предложении FROM инструкции SELECT. Для этого предложение FROM подзапроса вставляется в предложение FROM внешнего запроса, а выражения внешнего запроса, ссылающиеся на результирующий набор подзапроса, переписываются. Например:

SELECT t1.a, t2.b FROM t2, (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5

При сведении запроса он был бы переписан следующим образом:

SELECT t1.x+t1.y AS a, t2.b FROM t2, t1 WHERE z<100 AND a>5

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

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

1. (Устарело)
2. (Устарело)
3. Если подзапрос является правым операндом LEFT JOIN, то
   1. подзапрос не может быть соединением, и
   2. предложение FROM подзапроса не может содержать виртуальную таблицу, и
   3. внешний запрос не может быть DISTINCT.
4. Подзапрос не является DISTINCT.
5. (Устарело — включено в ограничение 4)
6. (Устарело)
7. Подзапрос содержит предложение FROM.
8. Подзапрос не использует LIMIT или внешний запрос не является соединением.
9. Подзапрос не использует LIMIT или внешний запрос не использует агрегатные функции.
10. (Устарело)
11. Подзапрос и внешний запрос не должны оба содержать предложения ORDER BY.
12. (Устарело — включено в ограничение 3)
13. Подзапрос и внешний запрос не должны оба использовать LIMIT.
14. Подзапрос не использует OFFSET.
15. Если внешний запрос является частью составного SELECT, подзапрос не может содержать предложение LIMIT.
16. Если внешний запрос является агрегатным, подзапрос не может содержать ORDER BY.
17. Если подзапрос является составным SELECT, то
    1. все составные операторы должны быть UNION ALL, и
    2. ни один из терминов составного подзапроса не должен быть агрегатным или DISTINCT, и
    3. каждый термин подзапроса должен содержать предложение FROM, и
    4. внешний запрос не может быть агрегатным запросом или запросом DISTINCT.
    5. подзапрос не может содержать оконные функции.
    6. подзапрос не должен быть правой частью LEFT JOIN.
    7. подзапрос должен быть первым элементом внешнего запроса либо ни в одной части подзапроса не должно быть RIGHT JOIN или FULL JOIN.
    8. выражения соответствующих результирующих наборов во всех частях составного подзапроса должны иметь одинаковую аффинность.
    Родительский запрос и подзапрос могут содержать предложения WHERE. С учётом правил (11), (12) и (13) они также могут содержать предложения ORDER BY, LIMIT и OFFSET.
18. Если подзапрос является составным SELECT, все термины предложения ORDER BY родительского запроса должны быть простыми ссылками на столбцы подзапроса.
19. Если подзапрос использует LIMIT, внешний запрос не может содержать предложение WHERE.
20. Если подзапрос является составным SELECT, он не должен использовать предложение ORDER BY.
21. Если подзапрос использует LIMIT, внешний запрос не может быть DISTINCT.
22. Подзапрос не может быть рекурсивным CTE.
23. Если внешний запрос является рекурсивным CTE, подзапрос не может быть составным запросом.
24. (Устарело)
25. Ни подзапрос, ни внешний запрос не должны содержать оконную функцию в результирующем наборе или предложении ORDER BY.
26. Подзапрос не может быть правым операндом RIGHT или FULL OUTER JOIN.
27. Подзапрос не может содержать FULL или RIGHT JOIN, если только он не является первым элементом родительского запроса. Возможны два случая:
    1. подзапрос не является составным запросом.
    2. подзапрос является составным запросом, и RIGHT JOIN встречается в любой его части. (См. также (17g)).
28. Подзапрос не является CTE с ключевым словом MATERIALIZED.

Сведение запросов — важная оптимизация при использовании представлений, поскольку каждое обращение к представлению преобразуется в подзапрос.

12. Корутины подзапросов

SQLite реализует подзапросы из предложения FROM одним из трёх способов:

1. Свести подзапрос во внешний запрос
2. Вычислить подзапрос во временную таблицу, существующую в течение выполнения одной SQL-инструкции, а затем выполнить внешний запрос для этой временной таблицы.
3. Вычислить подзапрос в корутине, которая работает параллельно с внешним запросом и по мере необходимости передаёт ему строки.

В этом разделе описан третий способ: реализация подзапроса в виде корутины.

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

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

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

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

12.1. Использование корутин для откладывания вычислений до завершения сортировки

Начиная с версии SQLite 3.21.0 (2017-10-24), планировщик запросов всегда предпочитает использовать корутину для реализации подзапросов из предложения FROM, содержащих ORDER BY и не являющихся частью соединения, если результирующий набор внешнего запроса является «сложным». Эта возможность позволяет приложениям переносить дорогостоящие вычисления с этапа перед сортировкой на этап после неё, что может ускорить работу. Например, рассмотрим следующий запрос:

SELECT expensive_function(a) FROM tab ORDER BY date DESC LIMIT 5;

Цель этого запроса — вычислить некоторое значение для пяти самых новых записей таблицы. В приведённом выше запросе "expensive_function()" вызывается до сортировки и, следовательно, выполняется для каждой строки таблицы, в том числе для строк, которые в итоге будут исключены из результата из-за предложения LIMIT. Чтобы обойти это ограничение, можно использовать корутину:

SELECT expensive_function(a) FROM (
  SELECT a FROM tab ORDER BY date DESC LIMIT 5
);

В изменённом запросе подзапрос, реализованный в виде корутины, вычисляет пять самых новых значений "a". Эти пять значений передаются из корутины во внешний запрос, где "expensive_function()" вызывается только для конкретных строк, которые нужны приложению.

В будущих версиях SQLite планировщик запросов может стать достаточно интеллектуальным, чтобы автоматически выполнять подобные преобразования в обоих направлениях. Иными словами, будущие версии SQLite могут преобразовывать запросы первой формы во вторую и запросы, написанные во второй форме, в первую. Начиная с версии SQLite 3.22.0 (2018-01-22), планировщик запросов сводит подзапрос, если внешний запрос не использует в результирующем наборе пользовательские функции или подзапросы. Однако в приведённых выше примерах SQLite реализует каждый запрос именно в написанной форме.

13. Оптимизация MIN/MAX

Запросы, содержащие одну агрегатную функцию MIN() или MAX(), аргументом которой является самый левый столбец индекса, могут быть выполнены с помощью одного поиска по индексу, а не сканирования всей таблицы. Примеры:

SELECT MIN(x) FROM table;
SELECT MAX(x)+1 FROM table;

14. Автоматические индексы на время выполнения запроса

Если для выполнения запроса нет подходящих индексов, SQLite может создать автоматический индекс, существующий только в течение одной SQL-инструкции. Автоматические индексы иногда также называют «индексами на время выполнения запроса». Поскольку построение автоматического индекса, или индекса на время выполнения запроса, имеет стоимость O(NlogN) (где N — количество записей в таблице), а полное сканирование таблицы имеет стоимость всего O(N), автоматический индекс создаётся только в том случае, если SQLite ожидает, что в ходе выполнения SQL-инструкции поиск будет выполняться более logN раз. Рассмотрим пример:

CREATE TABLE t1(a,b);
CREATE TABLE t2(c,d);
-- Insert many rows into both t1 and t2
SELECT * FROM t1, t2 WHERE a=c;

В приведённом выше запросе, если таблицы t1 и t2 содержат примерно по N строк, то без каких-либо индексов запрос потребует O(N*N) времени. С другой стороны, создание индекса для таблицы t2 требует O(NlogN) времени, а использование этого индекса для выполнения запроса — ещё O(NlogN) времени. Если нет данных ANALYZE, SQLite предполагает, что N равно миллиону, и поэтому считает, что создание автоматического индекса будет более экономичным вариантом.

Автоматический индекс на время выполнения запроса также может использоваться для подзапроса:

CREATE TABLE t1(a,b);
CREATE TABLE t2(c,d);
-- Insert many rows into both t1 and t2
SELECT a, (SELECT d FROM t2 WHERE c=b) FROM t1;

В этом примере таблица t2 используется в подзапросе для преобразования значений столбца t1.b. Если каждая таблица содержит N строк, SQLite ожидает, что подзапрос будет выполнен N раз, и поэтому считает, что быстрее сначала создать автоматический временный индекс для t2, а затем использовать этот индекс для выполнения N экземпляров подзапроса.

Возможность автоматической индексации можно отключить во время выполнения с помощью прагмы automatic_index. По умолчанию автоматическая индексация включена, но это поведение можно изменить, чтобы по умолчанию она была выключена, с помощью параметра компиляции SQLITE_DEFAULT_AUTOMATIC_INDEX. Возможность создавать автоматические индексы можно полностью отключить, собрав SQLite с параметром компиляции SQLITE_OMIT_AUTOMATIC_INDEX.

В SQLite, начиная с версии 3.8.0 (2013-08-26), при каждой подготовке инструкции, использующей автоматический индекс, в журнал ошибок отправляется сообщение SQLITE_WARNING_AUTOINDEX. Разработчики приложений могут и должны использовать эти предупреждения, чтобы выявлять необходимость в новых постоянных индексах схемы.

Не путайте автоматические индексы с внутренними индексами (с именами, например, "sqlite_autoindex_table_N"), которые иногда создаются для реализации ограничения PRIMARY KEY или ограничения UNIQUE. Описанные здесь автоматические индексы существуют только в течение одного запроса, никогда не сохраняются на диске и видны только одному подключению к базе данных. Внутренние индексы являются частью реализации ограничений PRIMARY KEY и UNIQUE, существуют длительное время, сохраняются на диске и видны всем подключениям к базе данных. Термин "autoindex" присутствует в именах внутренних индексов по историческим причинам и не означает, что внутренние и автоматические индексы связаны между собой.

14.1. Хеш-соединения

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

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

15. Оптимизация проталкивания предикатов

Если подзапрос нельзя свести во внешний запрос, производительность всё ещё может быть повышена за счёт «проталкивания» условий предложения WHERE из внешнего запроса в подзапрос. Рассмотрим пример:

CREATE TABLE t1(a INT, b INT);
CREATE TABLE t2(x INT, y INT);
CREATE VIEW v1(a,b) AS SELECT DISTINCT a, b FROM t1;

SELECT x, y, b
  FROM t2 JOIN v1 ON (x=a)
 WHERE b BETWEEN 10 AND 20;

Представление v1 нельзя свести, поскольку оно использует DISTINCT. Вместо этого его необходимо выполнить как подзапрос, сохранив результаты во временной таблице, а затем выполнить соединение между t2 и временной таблицей. Оптимизация проталкивания переносит условие "b BETWEEN 10 AND 20" в представление. Это уменьшает размер временной таблицы и ускоряет выполнение подзапроса, если для t1.b существует индекс. В результате выполняются следующие действия:

SELECT x, y, b
  FROM t2
  JOIN (SELECT DISTINCT a, b FROM t1 WHERE b BETWEEN 10 AND 20)
 WHERE b BETWEEN 10 AND 20;

Оптимизацию проталкивания условий предложения WHERE нельзя применять всегда. Например, если подзапрос содержит LIMIT, проталкивание любой части предложения WHERE из внешнего запроса может изменить результат внутреннего запроса. Есть и другие ограничения; они описаны в комментарии к процедуре pushDownWhereTerms() в исходном коде, реализующей эту оптимизацию.

Не путайте эту оптимизацию с оптимизацией MySQL, имеющей похожее название. Оптимизация проталкивания в MySQL изменяет порядок вычисления ограничений предложения WHERE: сначала вычисляются те из них, которые можно проверить только по индексу, не получая соответствующую строку таблицы. Это позволяет избежать ненужного обращения к строке таблицы, если ограничение не выполняется. Чтобы избежать неоднозначности, SQLite называет её «оптимизацией проталкивания MySQL». SQLite также выполняет оптимизацию проталкивания MySQL наряду с оптимизацией проталкивания условий предложения WHERE. Однако в этом разделе рассматривается именно оптимизация проталкивания условий предложения WHERE.

16. Оптимизация понижения уровня внешнего соединения

Внешнее соединение (LEFT JOIN, RIGHT JOIN или FULL JOIN) иногда можно упростить. LEFT JOIN или RIGHT JOIN можно преобразовать в обычное (INNER) JOIN, а FULL JOIN — в LEFT JOIN или RIGHT JOIN. Это возможно, если в предложении WHERE есть условия, гарантирующие, что после упрощения результат останется тем же. Например, если для истинности предложения WHERE требуется, чтобы любой столбец правой таблицы в LEFT JOIN был не равен NULL, то LEFT JOIN понижается до обычного JOIN.

Средство доказательства теорем, определяющее, можно ли упростить соединение, несовершенно. Иногда оно выдаёт ложноотрицательный результат. Иными словами, оно иногда не может доказать, что понижение уровня внешнего соединения безопасно, хотя на самом деле это безопасно. Например, средство доказательства не знает, что функция SQL datetime() всегда возвращает NULL, если её первый аргумент равен NULL, и поэтому не распознаёт, что в следующем запросе уровень LEFT JOIN можно понизить:

SELECT urls.url
  FROM urls
  LEFT JOIN
    (SELECT *
      FROM (SELECT url_id AS uid, max(retrieval_time) AS rtime
              FROM lookups GROUP BY 1 ORDER BY 1)
      WHERE uid IN (358341,358341,358341)
    ) recent
    ON u.source_seed_id = recent.xyz OR u.url_id = recent.xyz
 WHERE
     DATETIME(recent.rtime) > DATETIME('now', '-5 days');

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

17. Оптимизация удаления внешнего соединения

Иногда LEFT JOIN или RIGHT JOIN можно полностью удалить из запроса, не изменив результат. Это возможно, если выполняются все следующие условия:

1. Запрос не является агрегатным
2. Запрос использует DISTINCT либо предложение ON или USING внешнего соединения ограничивает соединение так, что оно соответствует только одной строке
3. Правая таблица в LEFT JOIN или левая таблица в RIGHT JOIN нигде в запросе не используется за пределами собственного предложения USING или ON.

Удаление внешних соединений часто требуется, когда внешние соединения используются в представлениях, а затем представление применяется так, что ни к одному столбцу правой таблицы в LEFT JOIN или левой таблицы в RIGHT JOIN не обращаются.

Вот простой пример удаления LEFT JOIN:

CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1);
CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2);
CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3);

SELECT v1, v3 FROM t1 
  LEFT JOIN t2 ON (t1.ipk=t2.ipk)
  LEFT JOIN t3 ON (t1.ipk=t3.ipk)

Таблица t2 в приведённом выше запросе вообще не используется, поэтому планировщик запросов может выполнить запрос так, как если бы он был записан следующим образом:

SELECT v1, v3 FROM t1 
  LEFT JOIN t3 ON (t1.ipk=t3.ipk)

На момент написания этого текста удаляются только LEFT JOIN. Эта оптимизация пока не обобщена для работы с RIGHT JOIN, поскольку RIGHT JOIN появился в SQLite сравнительно недавно. Вероятно, эта асимметрия будет устранена в одном из будущих выпусков.

18. Оптимизация распространения констант

Если предложение WHERE содержит два или более ограничений равенства, соединённых оператором AND, и все аффинности этих ограничений совпадают, SQLite может использовать транзитивность равенства для создания новых «виртуальных» ограничений, которые упрощают выражения и/или повышают производительность. Это называется «оптимизацией распространения констант».

Например, рассмотрим следующую схему и запрос:

CREATE TABLE t1(a INTEGER PRIMARY KEY, b INT, c INT);
SELECT * FROM t1 WHERE a=b AND b=5;

SQLite анализирует ограничения "a=b" и "b=5" и делает вывод, что если оба эти ограничения истинны, то истинно и "a=5". Это означает, что нужную строку можно быстро найти, используя значение 5 для INTEGER PRIMARY KEY.

Последнее обновление этой страницы: 2025-05-31 13:08:22Z