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

Этот документ предоставляет обзор того, как планировщик запроса и оптимизатор для SQLite работают.

Учитывая единственный SQL-оператор, могли бы быть десятки, сотни или даже тысячи способов осуществить запрос, в зависимости от сложности самого запроса и основной схемы базы данных. Задача планировщика состоит в том, чтобы выбрать алгоритм, который минимизирует дисковый I/O и нагрузку на CPU

Дополнительная справочная информация доступна здесь.

С release 3.8.0 (2013-08-26) планировщик запроса SQLite был повторно осуществлен как Next Generation Query Planner или "NGQP". Все особенности, методы и алгоритмы, описанные в этом документе, применимы к устаревшим планировщикам pre-3.8.0 и к NGQP. Для получения дополнительной информации о том, чем NGQP отличается от наследия, см. здесь.

2. Анализ оператора Where

Оператор Where в запросе разбит на "условия", где каждый термин отделен от других операцией AND. Если оператор Where состоит из ограничений, отделенных операцией OR, весь пункт считается единственным "термином", к которому применяется оптимизация OR.

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

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 a=5 AND b IN (1,2,3) AND c IS NULL AND d='hello'

Первые четыре колонки a, b, c и d индекса были бы применимы, так как те четыре колонки формируют префикс индекса и все связаны ограничениями равенства.

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

Только колонки a, b и c индекса были бы применимы. Колонка D не была бы применима, потому что она справа от c, а c ограничивается только неравенствами.

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

Только колонки a и b индекса были бы применимы. Колонка D не была бы применима, потому что колонка c не ограничивается и не может быть никаких промежутков в наборе колонок, которые применимы индексом.

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

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

... 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 имеет следующую форму:

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

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

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

Ограничения оператора Where, которые связаны OR вместо AND, могут быть обработаны двумя различными способами. Если термин состоит из многочисленных подусловий, содержащих общее имя столбца и отделенный OR, как это:

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

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

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

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

Переписанное выражение выше концептуально, операторы Where, содержащие OR, действительно не переписаны так. Фактическая реализация пункта OR использует механизм, который более эффективен, и это работает даже на таблицах WITHOUT ROWID или таблицах, в которых "rowid" недоступен. Тем не менее, сущность внедрения захватывается запросом выше: Отдельные индексы используются, чтобы найти строки результата кандидата от каждого условия пункта OR, а конечный результат это союз тех строк.

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

Для любого данного запроса то, что оптимизация OR, описанная здесь, может использоваться, не гарантирует, что она будет использоваться. SQLite использует планировщик запроса на основе издержек, который оценивает CPU и затраты дискового I/O на различные конкурирующие планы запросов и выбирает план, который будет самым быстрым. Если есть много условий OR в операторе Where или если некоторые индексы на отдельных подусловиях OR не очень отборные, то SQLite мог бы решить, что быстрее использовать различный алгоритм запроса или даже полное сканирование таблицы. Разработчики приложений могут использовать префикс EXPLAIN QUERY PLAN, чтобы получить общий обзор выбранной стратегии запроса.

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

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

У оператора LIKE есть два режима, которые могут быть установлены pragma. Режим по умолчанию для сравнений LIKE нечувствительный к различиям регистра для latin1-знаков. Таким образом, по умолчанию следующее выражение верно:

'a' LIKE 'A'

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

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. Мы используем отдельный символ, чтобы обозначить этот неподстановочный префикс, но читатель должен понять, что префикс может состоять больше, чем из 1 символа. Позвольте y быть самой маленькой последовательностью, которая имеет ту же самую длину, как /x/, но которая выдерживает сравнение больше, чем x. Например, если бы x = 'hello', то y 'hellp'. Оптимизация LIKE и GLOB состоят из добавления двух виртуальных условий:

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

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

Обратите внимание на то, что когда правая сторона 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 имеет один вход для каждого человека в крупной организации. Каждый человек "student" или "teacher", как определено полем "role". Таблица также делает запись высоты в сантиметрах каждого человека. Роль и высота внесены в индекс. Заметьте, что крайний левый столбец индекса не очень отборный, это содержит только два возможных значения.

Теперь полагайте, что запрос находит имена всех в организации, кто 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 управляет запросом вроде такого:

У этого запроса есть ограничение равенства на крайний левый столбец индекса и таким образом, индекс может использоваться, чтобы решить этот запрос. Как только этот запрос закончен, SQLite тогда использует индекс "people_idx1", чтобы определить местонахождение следующего значения столбца "role", используя код, который логически подобен "SELECT role FROM people WHERE role>$role LIMIT 1". Новое значение "role" переписывает переменную $role и повторяет процесс, пока все возможные значения для "role" не были исследованы.

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

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

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

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

ON и USING внутреннего объединения преобразовываются в дополнительные условия оператора Where до анализа оператора Where, описанного выше. Таким образом с SQLite нет никакого вычислительного преимущества, чтобы использовать более новый синтаксис соединения SQL92 вместо более старого синтаксиса соединения запятой SQL89. Они оба заканчивают тем, что достигают точно того же самого на внутренних объединениях.

Для OUTER JOIN ситуация более сложна. Следующие два запроса не эквивалентны:

SELECT * FROM tab1 LEFT JOIN tab2 ON tab1.x=tab2.y;
SELECT * FROM tab1 LEFT JOIN tab2 WHERE tab1.x=tab2.y;

Для внутреннего объединения два запроса выше были бы идентичны. Однако, специальная обработка относится к пунктам ON и USING в OUTER join: определенно, ограничения в пункте ON или USING не применяются, если правильная таблица соединения находится на пустой строке, но ограничения действительно применяются в операторе Where. Результирующий эффект состоит в том, что помещение выражений пункта ON или USING для LEFT JOIN в WHERE, эффективно преобразовывает запрос к обычному INNER JOIN, хотя внутреннее объединение работает более медленно.

7.1. Порядок таблиц в соединении

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

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

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.2. Ручное управление планом запросов используя SQLITE_STAT

SQLite обеспечивает опытным программистам возможность осуществить контроль над планом запросов, выбранный оптимизатором. Один метод для того, чтобы сделать это должен уклониться от результатов ANALYZE в таблицах sqlite_stat1, sqlite_stat3 и/или sqlite_stat4. Это не рекомендуется для большинства ситуаций.

7.3. Ручное управление планом запросов, используя CROSS JOIN

Программисты могут вынудить SQLite использовать особый порядок вложения цикла на соединении при помощи оператора CROSS JOIN вместо просто JOIN, INNER JOIN, NATURAL JOIN или ",". Хотя CROSS JOIN коммутативные в теории, SQLite принимает решение никогда не переупорядочить таблицы в 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 изменяет результат.

См. "The Fossil NGQP Upgrade Case Study" для другого реального примера использования 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 могут быть вручную дисквалифицированы для использования с индексами, предварительно указав одноместный оператор + к имени столбца. Одноместный + ничего не делает и не произведет код в подготовленном запросе. Однако, одноместный оператор + будет препятствовать тому, чтобы термин ограничил индекс. Так, в примере выше, если запрос был переписан как:

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 и 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, но что более поздние условия в 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

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

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

12. Совместное выполнение подзапросов

До SQLite 3.7.15 (2012-12-12) подзапрос в пункте FROM был бы сглажен во внешний запрос, или иначе подзапросом будут управлять до завершения, прежде чем внешний запрос начался, набор результатов от подзапроса был бы сохранен в переходной таблице и затем переходная таблица будет использоваться во внешнем запросе. У более новых версий SQLite есть третий вариант, который должен осуществить подзапрос, используя совместное выполнение.

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

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

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

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

12.1. Отсрочка работы до окончания сортировки

С SQLite version 3.21.0 (2017-10-24) планировщик запроса будет всегда предпочитать использовать coзапрос, чтобы осуществить подзапросы ORDER BY, который содержит пункт 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);

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

Планировщик запроса в будущих версиях SQLite мог бы стать достаточно умным, чтобы сделать преобразования таким как вышеупомянутое автоматически в обоих направлениях. То есть будущие версии SQLite могли бы преобразовать запросы первой формы во вторую или наоборот. С версии 3.22.0 (2018-01-22) SQLite планировщик запроса сгладит подзапрос, если внешний запрос не использует определенных пользователями функций или подзапросов в его наборе результатов. Для примеров, показанных выше, однако, 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 экземпляров подзапроса.

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

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

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

14.1. Хэширования

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

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

15. Оптимизация Push-Down

Если подзапрос не может быть сглажен во внешний запрос, все еще может быть возможно увеличить производительность, "снизив" условия оператора 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;

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

16. Оптимизация сокращения OUTER JOIN

OUTER JOIN (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 может быть полностью опущен от запроса, не изменяя результат. Это может произойти, если все следующее верно:

Устранение OUTER JOIN часто подходит, когда OUTER JOIN используются в обзорах, а затем представление используется в так, что ни одна из колонок в правой таблице LEFT JOIN или левой в RIGHT 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, который относительно новое дополнение к 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" = true. Это означает, что желаемая строка может искаться быстро, используя значение 5 для INTEGER PRIMARY KEY.


WebMoney: WMZ Z294115950220 WMR R409981405661 WME E134003968233	Visa 4274 3200 2453 6495

1. Введение