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

1. Введение

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

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

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

2. Анализ условия WHERE

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

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

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

После переноса всех ограничений в условие 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. Аналогично, столбцы индекса обычно не будут использоваться (для индексации) если они находятся справа от столбца, ограниченного только неравенствами. (См. оптимизацию skip-scan ниже для исключения.)

В случае индексов на выражениях, каждый раз, когда в приведенном выше тексте используется слово «столбец», можно заменить его на «индексируемое выражение» (означающее копию выражения, которое появляется в операторе 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. Обратите внимание, что столбец должен быть одинаковым столбцом во всех подтермах, соединенных оператором OR, хотя столбец может располагаться как слева, так и справа от оператора =.

4.2. Отдельный анализ условий OR и объединение результатов

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

  expr1 OR expr2 OR expr3

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

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

Оператор LIKE имеет два режима, которые могут быть установлены с помощью pragma. По умолчанию сравнения LIKE нечувствительны к различиям в регистре латинских символов. Таким образом, по умолчанию следующее выражение истинно:

'a' LIKE 'A'

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

PRAGMA case_sensitive_like=ON;

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

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

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

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

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

Предположим, что начальная последовательность символов без символов подстановки в правой части операторов LIKE или GLOB — это x. Мы используем один символ для обозначения этого префикса без символов подстановки, но читатель должен понимать, что префикс может состоять из более чем 1 символа. Пусть 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. Оптимизация Skip-Scan

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

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

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

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

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

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

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

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

Пусть число вершин «alice» — M, а число вершин «bob» — N. Рассмотрим два сценария. В первом сценарии M и N оба равны 2, но на каждой вершине есть тысячи ребер. В этом случае предпочтительнее вариант 1. С вариантом 1 внутренний цикл проверяет наличие ребра между парой вершин и выводит результат, если он найден. Поскольку есть всего 2 вершины «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 выполняется для сбора статистики, может быть сделан другой выбор, если статистика указывает, что альтернативный вариант, вероятно, будет выполняться быстрее.

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

См. "Изучение случая обновления NGQP Fossil" для другого реального примера использования 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 имеет сопоставление TEXT, то сравнение "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 и 1000. В этом случае ограничение диапазона для столбца 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 запроса, когда это возможно. Когда SQLite сталкивается с выбором использования индекса для удовлетворения ограничений оператора WHERE или удовлетворения оператора ORDER BY, SQLite выполняет тот же анализ стоимости, что и описано выше, и выбирает индекс, который, по его мнению, даст самый быстрый результат.

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

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

Если запрос содержит условие ORDER BY с несколькими элементами, возможно, SQLite сможет использовать индексы, чтобы строки выводились в порядке некоторого префикса элементов в ORDER BY, но последующие элементы в 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. Если внешний запрос является частью составного запроса, то подзапрос не может иметь оператор LIMIT.
16. Если внешний запрос является агрегатом, то подзапрос не может содержать ORDER BY.
17. Если подзапрос является составным SELECT, то
    1. все составные операторы должны быть UNION ALL, и
    2. ни один элемент с подзапросом составного оператора не может быть агрегатом или DISTINCT, и
    3. каждый элемент внутри подзапроса должен иметь оператор FROM, и
    4. внешний запрос не может быть агрегатным или DISTINCT запросом.
    5. подзапрос не может содержать оконные функции.
    6. подзапрос не должен быть правым операндом LEFT JOIN.
    7. либо подзапрос является первым элементом внешнего запроса, либо в любом из элементов подзапроса нет RIGHT или 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.

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

12. Подзапросы-корутины

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

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

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

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

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

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

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

12.1. Использование сопроцедур для отложенного выполнения работы до сортировки

Начиная с версии SQLite 3.21.0 (24 октября 2017 г.), планировщик запросов всегда будет отдавать предпочтение использованию сопроцедуры для реализации подзапросов 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 (22 января 2018 г.), планировщик запросов будет сводить подзапрос, если внешний запрос не использует какие-либо пользовательские функции или подзапросы в своем наборе результатов. Однако для приведенных выше примеров 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 ожидает, что поиск будет выполняться более чем logN раз в процессе выполнения SQL-запроса. Рассмотрим пример:

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 экземпляров подзапроса.

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

В SQLite версии 3.8.0 (26 августа 2013 г.) и более поздних версиях сообщение 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 или RIGHT JOIN можно преобразовать в обычное (INNER) JOIN, или FULL JOIN может быть преобразован в LEFT или RIGHT JOIN. Это может произойти, если в условии WHERE есть термины, гарантирующие тот же результат после упрощения. Например, если любой столбец в правой таблице LEFT JOIN должен быть не NULL, чтобы условие WHERE было истинным, то LEFT JOIN понижается до обычного JOIN.

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

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

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

Исключение OUTER JOIN часто возникает, когда OUTER JOIN используются внутри представлений, а затем представление используется таким образом, что ни один из столбцов правой таблицы 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 для целочисленного первичного ключа.

Эта страница была в последний раз изменена 24 июля 2024 г. в 12:16:13 UTC