Оптимизатор и планировщик запросов SQLite: принципы работы

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

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

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

Как оптимизатор SQLite анализирует предложение WHERE

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

Все NATURAL-соединения преобразуются в соединения с предложением USING

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

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

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

Добавить такие метки в чистом SQL невозможно, поэтому во входном SQL для внешних соединений требуется использовать предложения ON

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

Каждый терм в предложении WHERE проверяется на соответствие индексам. Для использования индекса терм должен принимать одну из следующих форм:

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

Если индекс создан с помощью такого оператора:

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

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

Не обязательно, чтобы все столбцы индекса присутствовали в условии предложения WHERE для его использования. Однако пропуски в используемых столбцах недопустимы. То есть, если в WHERE отсутствует условие, которое ограничивает столбец c, условия для a и b могут использоваться с индексом, но условия для столбцов от d до z уже не будут

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

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

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

... 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, который ограничен только неравенствами

... 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'

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

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

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

По этой теме полезно отдельно посмотреть EXPLAIN QUERY PLAN: план выполнения SQL-запроса в SQLite, чтобы расширить контекст и сравнить подходы

По этой теме полезно отдельно посмотреть Создание Flutter-приложения с SQLite, BLoC и Streams, чтобы расширить контекст и сравнить подходы

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

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

expr1 BETWEEN expr2 AND expr3

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

expr1 >= expr2 AND expr1 <= expr3

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

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

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

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

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

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

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

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

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

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

Раздельное вычисление ограничений OR с объединением результатов через UNION

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

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

Разработчики приложений могут использовать префикс EXPLAIN QUERY PLAN для оператора, чтобы получить общее представление о выбранной стратегии запроса

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

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

• Правая часть LIKE или GLOB должна быть либо строковым литералом, либо параметром, привязанным к строковому литералу, который не начинается с символа подстановки.
• Не должно быть возможности сделать оператор LIKE или GLOB истинным, имея числовое значение (вместо строки или blob) в левой части. Это означает, что либо: левая часть оператора LIKE или GLOB является именем проиндексированного столбца с аффинностью TEXT, либо аргумент-шаблон в правой части не начинается со знака минус (-) или цифры.
• Встроенные функции, используемые для реализации LIKE и GLOB, не должны быть перегружены с помощью API sqlite3_create_function().
• Для оператора GLOB столбец должен быть проиндексирован с использованием встроенной последовательности сортировки BINARY.
• Для оператора LIKE: если включён режим case_sensitive_like, столбец должен быть проиндексирован с использованием встроенной последовательности сортировки BINARY; если режим case_sensitive_like отключён, столбец должен быть проиндексирован с использованием встроенной последовательности сортировки NOCASE.
• Если используется параметр ESCAPE, символ ESCAPE должен быть символом ASCII или однобайтовым символом в UTF-8.

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

'a' LIKE 'A'

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

PRAGMA case_sensitive_like=ON;

Тогда оператор LIKE учитывает регистр, и приведённый выше пример будет вычислен как ложный. Обратите внимание, что нечувствительность к регистру применяется только к символам latin1 — по сути, к прописным и строчным буквам английского языка в нижних 127 байтовых кодах ASCII

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

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

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

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

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

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

Предположим, что начальная последовательность символов без подстановки в правой части оператора LIKE или GLOB равна x. Мы используем один символ для обозначения этого префикса без подстановки, но читатель должен понимать, что префикс может состоять из более чем одного символа. Пусть y — наименьшая строка той же длины, что и x, но которая при сравнении больше, чем x

Например, если x равно 'hello', то y будет 'hellp'. Оптимизации LIKE и GLOB состоят в добавлении двух виртуальных термов следующим образом:

column >= x AND column < y

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

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

column LIKE x%
column GLOB x*

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

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

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

Пропускающее сканирование индекса (skip scan)

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

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

CREATE TABLE people( name TEXT PRIMARY KEY, role TEXT NOT NULL, height INT NOT NULL, -- в сантиметрах CHECK( role IN ('student','teacher') )
);
CREATE INDEX people_idx1 ON people(role, height);

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

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

SELECT name FROM people WHERE height>=180;

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

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

Или вот так:

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

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

SQLite сохраняет это первое значение role во внутренней переменной, которую мы здесь будем называть $role. Затем SQLite выполняет запрос вида: SELECT name FROM people WHERE role=$role AND height>=180. Этот запрос имеет ограничение равенства на крайний левый столбец индекса, поэтому индекс может быть использован для его выполнения

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

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

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

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

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

Соединения

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

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

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

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

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

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

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

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

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

Вариант 1:

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

Вариант 2:

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

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

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

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

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

Теперь рассмотрим случай, когда M и N оба равны 3500. Узлов alice много. На этот раз предположим, что каждый из этих узлов соединён лишь одним или двумя рёбрами. Теперь предпочтителен вариант 2

При варианте 2 внешний цикл по-прежнему должен выполниться 3500 раз, но средний цикл выполняется лишь один или два раза для каждой итерации внешнего цикла, а внутренний цикл — не более одного раза для каждой итерации среднего, если вообще выполняется. Таким образом, общее количество итераций внутреннего цикла составляет около 7000

Вариант 1, напротив, должен выполнить и внешний, и средний цикл по 3500 раз каждый, что даёт 12 миллионов итераций среднего цикла. Следовательно, во втором сценарии вариант 2 почти в 2000 раз быстрее варианта 1

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

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

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

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

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

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

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

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

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

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

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

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

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

В последнем запросе план запроса должен соответствовать варианту 2. Обратите внимание, что для отключения оптимизации переупорядочивания таблиц необходимо использовать ключевое слово CROSS; INNER JOIN, NATURAL JOIN, JOIN и другие аналогичные комбинации работают так же, как соединение через запятую — оптимизатор вправе переупорядочивать таблицы по своему усмотрению

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

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

Выбор оптимального индекса при нескольких кандидатах

Каждая таблица в предложении 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, поскольку этот индекс более избирателен

Исключение условий 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 и всегда будет ложным

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

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

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 ex3(w, x);
CREATE INDEX ex3i2 ON ex3(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

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

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

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

Когда индекс содержит все данные, необходимые для запроса, и когда к исходной таблице никогда не требуется обращаться, такой индекс называется «покрывающим индексом» (covering index)

Оптимизации ORDER BY

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

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

Это может быть значительно быстрее, чем альтернативный подход — сравнение каждой строки со всеми предыдущими строками

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

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

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

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

Разворачивание и сглаживание подзапросов

Когда подзапрос встречается в предложении 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

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

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

Условия, при которых сглаживание применяется:

• (Устарело)
• (Устарело)
• Если подзапрос является правым операндом LEFT JOIN, то подзапрос не может быть соединением, и предложение FROM подзапроса не может содержать виртуальную таблицу, и внешний запрос не может быть DISTINCT.
• Подзапрос не является DISTINCT.
• (Устарело — поглощено ограничением 4)
• (Устарело)
• Подзапрос имеет предложение FROM.
• Подзапрос не использует LIMIT, или внешний запрос не является соединением.
• Подзапрос не использует LIMIT, или внешний запрос не использует агрегаты.
• (Устарело)
• Подзапрос и внешний запрос не имеют одновременно предложений ORDER BY.
• (Устарело — поглощено ограничением 3)
• Подзапрос и внешний запрос не используют одновременно LIMIT.
• Подзапрос не использует OFFSET.
• Если внешний запрос является частью составного выбора, то подзапрос не может иметь предложение LIMIT.
• Если внешний запрос является агрегатным, то подзапрос не может содержать ORDER BY.
• Если подзапрос является составным SELECT, то все составные операторы должны быть UNION ALL, и ни один из элементов составного подзапроса не может быть агрегатным или DISTINCT, и каждый элемент внутри подзапроса должен иметь предложение FROM, и внешний запрос не может быть агрегатным или DISTINCT запросом, и подзапрос не может содержать оконные функции, и подзапрос не должен быть правой частью LEFT JOIN, и либо подзапрос является первым элементом внешнего запроса, либо ни в одной из ветвей подзапроса нет RIGHT или FULL JOIN, и соответствующие выражения результирующего набора во всех ветвях составного подзапроса должны иметь одинаковое сродство (affinity).
• Если подзапрос является составным выбором, то все элементы предложения ORDER BY родительского запроса должны быть простыми ссылками на столбцы подзапроса.
• Если подзапрос использует LIMIT, то внешний запрос не может иметь предложение WHERE.
• Если подзапрос является составным выбором, то он не должен использовать предложение ORDER BY.
• Если подзапрос использует LIMIT, то внешний запрос не может быть DISTINCT.
• Подзапрос не может быть рекурсивным CTE.
• Если внешний запрос является рекурсивным CTE, то подзапрос не может быть составным запросом.
• (Устарело)
• Ни подзапрос, ни внешний запрос не могут содержать оконную функцию в результирующем наборе или в предложении ORDER BY.
• Подзапрос не может быть правым операндом RIGHT или FULL OUTER JOIN.
• Подзапрос не может содержать FULL или RIGHT JOIN, если только он не является первым элементом родительского запроса. Два подслучая: подзапрос не является составным запросом; подзапрос является составным запросом, и RIGHT JOIN встречается в любой ветви составного запроса.
• Подзапрос не является MATERIALIZED CTE.

Сглаживание запросов является важной оптимизацией при использовании представлений, поскольку каждое использование представления транслируется в подзапрос

Выполнение подзапросов через сопрограммы

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

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

Этот раздел описывает третью технику: реализацию подзапроса в виде сопрограммы

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

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

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

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

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

Использование сопрограмм для откладывания работы до завершения сортировки

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

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

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

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

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

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

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

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

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

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

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

Когда для вычисления запроса нет доступных индексов, SQLite может создать автоматический индекс, существующий только на протяжении выполнения одного SQL-оператора. Автоматические индексы иногда также называют «индексами времени запроса» (query-time indexes)

Поскольку стоимость построения автоматического индекса составляет 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. Я нахожу этот паттерн особенно показательным: без автоматического индекса каждая строка t1 вызывала бы полное сканирование t2, что давало бы квадратичную сложность. Автоматический индекс позволяет SQLite избежать этого без каких-либо явных действий со стороны разработчика

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

Когда SQLite использует пропускающее сканирование (skip-scan) вместо обычного индексного поиска?

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

Почему команда ANALYZE влияет на выбор плана запроса?

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

Зачем использовать CROSS JOIN вместо обычного JOIN?

CROSS JOIN — единственный способ принудительно зафиксировать порядок таблиц в соединении. SQLite никогда не переупорядочивает таблицы в CROSS JOIN, тогда как обычные JOIN, INNER JOIN и соединения через запятую могут быть переупорядочены оптимизатором. Это полезно, когда разработчик точно знает, какой порядок вложения циклов будет быстрее для конкретных данных

Что такое покрывающий индекс и почему он ускоряет запросы?

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

В чём разница между реализацией подзапроса через временную таблицу и через сопрограмму?

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