Оптимизация SQL-запросов в SQLite: планирование и индексы

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

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

Как SQLite выбирает алгоритм выполнения запроса

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

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

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

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

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

Методы поиска строк и оптимизация SQL-запросов в SQLite

Полное сканирование таблицы: когда индексы отсутствуют

Большинство таблиц в SQLite состоят из нуля или более строк с уникальным целочисленным ключом (rowid или INTEGER PRIMARY KEY), за которым следует содержимое. Исключение составляют таблицы WITHOUT ROWID. Строки логически хранятся в порядке возрастания rowid.

В качестве примера в этой статье используется таблица с именем «FruitsForSale», которая связывает различные фрукты со штатом, где они выращиваются, и их рыночной ценой за единицу. Схема выглядит следующим образом:

CREATE TABLE FruitsForSale( Fruit TEXT, State TEXT, Price REAL
);

При наличии некоторых произвольных данных такая таблица может логически храниться на диске, как показано на рисунке 1:

Рисунок 1: Логическая структура таблицы «FruitsForSale»

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

Но независимо от того, что происходит, rowid всегда уникальны и строго возрастают.

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

SELECT price FROM fruitsforsale WHERE fruit='Peach';

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

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

Рисунок 2: Полное сканирование таблицы

1.2. Поиск по Rowid

Один из способов избежать полного сканирования таблицы — выполнять поиск по rowid (или по эквивалентному INTEGER PRIMARY KEY). Чтобы узнать цену персиков, можно запросить запись с rowid равным 4:

SELECT price FROM fruitsforsale WHERE rowid=4;

Поскольку информация хранится в таблице в порядке rowid, SQLite может найти нужную строку с помощью бинарного поиска. Если таблица содержит N элементов, время, необходимое для нахождения нужной строки, пропорционально logN, а не N, как при полном сканировании таблицы. Если таблица содержит 10 миллионов элементов, это означает, что запрос будет выполняться примерно в N/logN, то есть приблизительно в 1 миллион раз быстрее.

Рисунок 3: Поиск по Rowid

Поиск по индексу: ускорение SQL-запросов в SQLite

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

Чтобы сделать исходный запрос более эффективным, можно добавить индекс на столбец «fruit» таблицы «fruitsforsale» следующим образом:

CREATE INDEX Idx1 ON fruitsforsale(fruit);

Индекс — это ещё одна таблица, похожая на исходную таблицу «fruitsforsale», но с содержимым (в данном случае столбцом fruit), хранящимся перед rowid, и со всеми строками, упорядоченными по содержимому. На рисунке 4 представлено логическое представление индекса Idx1.

Столбец «fruit» является первичным ключом, используемым для упорядочивания элементов таблицы, а «rowid» — вторичным ключом, используемым для разрешения коллизий, когда две или более строк имеют одинаковое значение «fruit». В примере rowid приходится использовать в качестве разрешителя коллизий для строк «Orange».

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

Рисунок 4: Индекс на столбце Fruit

Этот новый индекс можно использовать для реализации более быстрого алгоритма выполнения исходного запроса «Цена персиков»:

Запрос начинается с бинарного поиска в индексе Idx1 записей, у которых fruit='Peach'. SQLite может выполнить этот бинарный поиск по индексу Idx1, но не по исходной таблице FruitsForSale, поскольку строки в Idx1 отсортированы по столбцу «fruit». Найдя в индексе Idx1 строку с fruit='Peach', движок базы данных извлекает rowid для этой строки.

Затем выполняется второй бинарный поиск по исходной таблице FruitsForSale, чтобы найти исходную строку, содержащую fruit='Peach'. Из строки в таблице FruitsForSale SQLite затем извлекает значение столбца price. Эта процедура иллюстрируется рисунком 5.

Рисунок 5: Поиск по индексу для получения цены персиков

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

1.4. Несколько строк результата

В предыдущем запросе ограничение fruit='Peach' сузило результат до единственной строки. Но тот же метод работает даже в случае, когда получается несколько строк. Предположим, мы ищем цену апельсинов вместо персиков:

SELECT price FROM fruitsforsale WHERE fruit='Orange'

Рисунок 6: Поиск по индексу для получения цены апельсинов

В этом случае SQLite по-прежнему выполняет единственный бинарный поиск, чтобы найти первую запись индекса, где fruit='Orange'. Затем он извлекает rowid из индекса и использует этот rowid для поиска исходной записи таблицы с помощью бинарного поиска и вывода цены из исходной таблицы.

Но вместо завершения работы движок базы данных переходит к следующей строке индекса, чтобы повторить процесс для следующей записи fruit='Orange'. Переход к следующей строке индекса (или таблицы) обходится значительно дешевле, чем бинарный поиск, поскольку следующая строка нередко находится на той же странице базы данных, что и текущая.

Фактически, стоимость перехода к следующей строке настолько мала по сравнению с бинарным поиском, что мы обычно ею пренебрегаем. Таким образом, суммарная стоимость данного запроса составляет 3 бинарных поиска. Если количество строк вывода равно K, а количество строк в таблице равно N, то в общем случае стоимость выполнения запроса пропорциональна (K+1)*logN.

1.5. Несколько условий WHERE, соединённых оператором AND

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

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA'

Рисунок 7: Поиск по индексу для калифорнийских апельсинов

Один из подходов к этому запросу — использовать условие fruit='Orange' из секции WHERE для нахождения всех строк, связанных с апельсинами, а затем отфильтровать эти строки, отбросив те, которые относятся к штатам, отличным от Калифорнии. Этот процесс показан на рисунке 7. В большинстве случаев это вполне разумный подход.

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

Предположим, что в дополнение к индексу по столбцу «fruit» существует также индекс по столбцу «state»:

CREATE INDEX Idx2 ON fruitsforsale(state);

Рисунок 8: Индекс по столбцу state

Индекс «state» работает точно так же, как и индекс «fruit»: это новая таблица с дополнительным столбцом перед rowid, отсортированная по этому дополнительному столбцу как по первичному ключу. Единственное отличие состоит в том, что в Idx2 первым столбцом является «state», а не «fruit», как в Idx1. В нашем примере данных в столбце «state» больше повторяющихся значений, поэтому в индексе больше дублирующихся записей. Совпадения по-прежнему разрешаются с помощью rowid.

Используя новый индекс Idx2 по столбцу «state», SQLite получает ещё один вариант поиска цены калифорнийских апельсинов: он может найти все строки, содержащие фрукты из Калифорнии, и отфильтровать те строки, которые не являются апельсинами.

Рисунок 9: Поиск по индексу для калифорнийских апельсинов

Использование Idx2 вместо Idx1 заставляет SQLite рассматривать другой набор строк, но в итоге он получает тот же ответ — что очень важно: индексы никогда не должны изменять ответ, а лишь помогать SQLite быстрее к нему прийти — и выполняет тот же объём работы. Таким образом, индекс Idx2 в данном случае не улучшил производительность.

В нашем примере оба последних запроса занимают одинаковое время. Так какой же индекс выберет SQLite — Idx1 или Idx2? Если над базой данных была выполнена команда ANALYZE, что дало SQLite возможность собрать статистику о доступных индексах, то SQLite будет знать, что индекс Idx1 обычно сужает поиск до единственного элемента (наш пример с fruit='Orange' является исключением из этого правила), тогда как индекс Idx2 обычно сужает поиск лишь до двух строк.

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

1.6. Многоколоночные индексы

Чтобы добиться максимальной производительности при запросе с несколькими условиями, соединёнными оператором AND в секции WHERE, нужен многоколоночный индекс со столбцами для каждого из условий AND. В данном случае мы создаём новый индекс по столбцам «fruit» и «state» таблицы FruitsForSale:

CREATE INDEX Idx3 ON FruitsForSale(fruit, state);

Рисунок 10: Двухколоночный индекс

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

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

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

Благодаря новому многоколоночному индексу Idx3, SQLite теперь может найти цену калифорнийских апельсинов, используя всего 2 бинарных поиска:

Рисунок 11: Поиск с использованием двухколоночного индекса

Имея индекс Idx3 по обоим столбцам, ограниченным условиями WHERE, SQLite может выполнить единственный бинарный поиск по Idx3, чтобы найти единственный rowid для калифорнийских апельсинов, а затем выполнить единственный бинарный поиск для нахождения цены этого элемента в исходной таблице. Нет тупиков и нет лишних бинарных поисков — это более эффективный запрос.

Обратите внимание, что Idx3 содержит всю ту же информацию, что и исходный Idx1. Поэтому, если у нас есть Idx3, Idx1 нам больше не нужен. Запрос «цена персиков» может быть выполнен с использованием Idx3 путём простого игнорирования столбца «state» в Idx3:

Рисунок 12: Поиск по одному столбцу в многоколоночном индексе

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

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

Запрос «цена апельсинов из Калифорнии» стал более эффективным благодаря использованию двухколоночного индекса. Но SQLite может сделать ещё лучше с помощью трёхколоночного индекса, который также включает столбец «price»:

CREATE INDEX Idx4 ON FruitsForSale(fruit, state, price);

Рисунок 13: Покрывающий индекс

Этот новый индекс содержит все столбцы исходной таблицы FruitsForSale, которые используются запросом — как условия поиска, так и выходные данные. Мы называем это «покрывающим индексом» (covering index). Поскольку вся необходимая информация находится в покрывающем индексе, SQLite никогда не обращается к исходной таблице для получения цены.

Рисунок 14: Запрос с использованием покрывающего индекса

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

Но с другой стороны, это всего лишь уточнение; двукратный прирост производительности далеко не так впечатляет, как увеличение в миллион раз, которое наблюдалось при первом индексировании таблицы. И для большинства запросов разница между 1 микросекундой и 2 микросекундами вряд ли будет заметна.

1.8. Условия, соединённые OR в предложении WHERE

Многоколоночные индексы работают только в том случае, если условия в предложении WHERE запроса соединены через AND. Поэтому Idx3 и Idx4 полезны при поиске элементов, которые одновременно являются апельсинами и выращены в Калифорнии, но ни один из этих индексов не был бы особенно полезен, если бы мы хотели найти все элементы, которые либо являются апельсинами, либо выращены в Калифорнии:

SELECT price FROM FruitsForSale WHERE fruit='Orange' OR state='CA';

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

Рисунок 15: Запрос с ограничениями OR

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

Это лишь деталь реализации — диаграмма, хотя и не является на 100% точной, даёт хорошее представление о происходящем.

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

Можно видеть, как техника OR-через-объединение могла бы также использоваться для применения нескольких индексов в запросах, где предложение WHERE содержит условия, соединённые AND, путём использования оператора пересечения вместо объединения. Многие движки баз данных SQL именно так и поступают.

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

2. Сортировка

SQLite (как и все другие движки баз данных SQL) может также использовать индексы для выполнения предложений ORDER BY в запросе, помимо ускорения поиска. Иными словами, индексы можно использовать для ускорения как поиска, так и сортировки.

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

SELECT * FROM fruitsforsale ORDER BY fruit;

SQLite обрабатывает его, собирая все выходные данные запроса, а затем пропуская их через сортировщик.

Рисунок 16: Сортировка без индекса

Если количество выходных строк равно K, то время, необходимое для сортировки, пропорционально KlogK. Если K мало, время сортировки обычно не является определяющим фактором, но в таком запросе, как приведённый выше, где K==N, время, необходимое для сортировки, может быть значительно больше времени, необходимого для полного сканирования таблицы.

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

2.1. Сортировка по Rowid

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

SELECT * FROM fruitsforsale ORDER BY rowid;

Рисунок 17: Сортировка по Rowid

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

SELECT * FROM fruitsforsale ORDER BY rowid DESC;

SQLite всё равно пропустит шаг сортировки. Но для того чтобы вывод появлялся в правильном порядке, SQLite будет выполнять сканирование таблицы начиная с конца и двигаясь к началу, а не начиная с начала и двигаясь к концу, как показано на рисунке 17.

2.2. Сортировка по индексу

Конечно, упорядочивание результатов запроса по rowid редко бывает полезным. Обычно требуется упорядочить результаты по какому-либо другому столбцу.

Если для столбца ORDER BY доступен индекс, этот индекс можно использовать для сортировки. Рассмотрим запрос всех элементов, отсортированных по «fruit»:

Рисунок 18: Сортировка с использованием индекса

Индекс Idx1 сканируется сверху вниз (или снизу вверх, если используется «ORDER BY fruit DESC»), чтобы найти rowid для каждого элемента в порядке по fruit. Затем для каждого rowid выполняется бинарный поиск для получения и вывода соответствующей строки. Таким образом, результат выводится в запрошенном порядке без необходимости собирать весь вывод и сортировать его отдельным шагом.

Но действительно ли это экономит время? Количество шагов при исходной сортировке без индекса пропорционально NlogN, поскольку именно столько времени требуется для сортировки N строк. Но когда мы используем Idx1, как показано здесь, нам нужно выполнить N поисков по rowid, каждый из которых занимает logN времени, так что суммарное время NlogN остаётся тем же.

SQLite использует планировщик запросов на основе стоимости (cost-based query planner). Когда существует два или более способа решить один и тот же запрос, SQLite пытается оценить общее время, необходимое для выполнения запроса каждым из планов, а затем использует план с наименьшей оценочной стоимостью.

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

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

2.3. Сортировка по покрывающему индексу

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

Рисунок 19: Сортировка с использованием покрывающего индекса

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

3. Поиск и сортировка одновременно

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

3.1. Поиск и сортировка с многоколоночным индексом

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

SELECT price FROM fruitforsale WHERE fruit='Orange' ORDER BY state

Запрос содержит как ограничение поиска в предложении WHERE, так и порядок сортировки в предложении ORDER BY. И поиск, и сортировка могут быть выполнены одновременно с использованием двухколоночного индекса Idx3.

Рисунок 20: Поиск и сортировка с использованием многоколоночного индекса

Запрос выполняет бинарный поиск по индексу для нахождения подмножества строк, у которых fruit='Orange'. Поскольку столбец fruit является крайним левым столбцом индекса, а строки индекса упорядочены, все такие строки будут смежными. Затем он сканирует совпадающие строки индекса сверху вниз, чтобы получить rowid исходной таблицы, и для каждого rowid выполняет бинарный поиск по исходной таблице для нахождения цены.

В приведённой выше диаграмме нигде нет блока «sort». Предложение ORDER BY запроса стало холостой операцией. Здесь не нужно выполнять никакой сортировки, потому что порядок вывода задан по столбцу state, а столбец state также оказывается первым столбцом после столбца fruit в индексе. Таким образом, если мы сканируем записи индекса с одинаковым значением столбца fruit сверху вниз, эти записи индекса гарантированно упорядочены по столбцу state.

3.2. Поиск и сортировка с покрывающим индексом

Покрывающий индекс также можно использовать для одновременного поиска и сортировки. Рассмотрим следующее:

SELECT * FROM fruitforsale WHERE fruit='Orange' ORDER BY state

Рисунок 21: Поиск и сортировка с использованием покрывающего индекса

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

А при сканировании совпадающих строк индекса сверху вниз результат гарантированно упорядочен по state, поскольку столбец state является следующим столбцом непосредственно правее столбца fruit. Таким образом, результирующий запрос оказывается очень эффективным.

SQLite может применить аналогичный приём для ORDER BY по убыванию:

SELECT * FROM fruitforsale WHERE fruit='Orange' ORDER BY state DESC

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

3.3. Частичная сортировка с использованием индекса (блочная сортировка)

Иногда с помощью индексов можно удовлетворить лишь часть предложения ORDER BY. Рассмотрим, например, следующий запрос:

SELECT * FROM fruitforsale ORDER BY fruit, price

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

Рисунок 22: Частичная сортировка с использованием индекса

В примере вместо одной сортировки 7 элементов выполняются 5 сортировок по одному элементу и 1 сортировка 2 элементов для случая fruit=='Orange'.

Преимущества выполнения множества небольших сортировок вместо одной большой сортировки:

• Множество небольших сортировок в совокупности используют меньше циклов процессора, чем одна большая сортировка.
• Каждая небольшая сортировка выполняется независимо, что означает необходимость хранить значительно меньше информации во временном хранилище в любой момент времени.
• Те столбцы ORDER BY, которые уже находятся в правильном порядке благодаря индексам, могут быть исключены из ключа сортировки, что дополнительно снижает требования к хранилищу и время процессора.
• Строки результата могут возвращаться приложению по мере завершения каждой небольшой сортировки, задолго до завершения сканирования таблицы.
• Если присутствует предложение LIMIT, может оказаться возможным избежать сканирования всей таблицы.

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

4. Таблицы WITHOUT ROWID

Основные принципы, описанные выше, применимы как к обычным таблицам с rowid, так и к таблицам WITHOUT ROWID. Единственное отличие состоит в том, что столбец rowid, который служит ключом для таблиц и появляется в качестве крайнего правого элемента в индексах, заменяется на PRIMARY KEY.

5. Типичные ошибки при работе с индексами

На практике я замечаю, что большинство проблем с производительностью SQLite сводятся к нескольким повторяющимся ошибкам.

Индекс есть, но он не используется. Если крайний левый столбец многоколоночного индекса не фигурирует в предложении WHERE, SQLite не сможет воспользоваться этим индексом для поиска. Например, индекс по (fruit, state) не поможет при запросе только по state — для этого нужен отдельный индекс по state.

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

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

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

Условия OR без индексов на каждую ветку. Техника OR-через-объединение работает только тогда, когда каждое из условий OR индексировано. Если хотя бы одно условие не индексировано, SQLite откажется от этой техники и выполнит полное сканирование таблицы.

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

Что такое покрывающий индекс и когда его стоит создавать?

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

Зачем запускать команду ANALYZE и как часто это нужно делать?

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

Почему многоколоночный индекс не помогает при использовании OR в предложении WHERE?

Многоколоночный индекс эффективен только при условиях, соединённых AND, поскольку позволяет сузить поиск до единственного диапазона строк. При OR каждое условие генерирует независимый набор rowid, которые затем объединяются. Для этого SQLite использует отдельный индекс для каждого условия OR — и если хотя бы одно условие не индексировано, вся техника OR-через-объединение отменяется в пользу полного сканирования таблицы.

Что такое частичная сортировка с использованием индекса и чем она лучше обычной сортировки?

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

Когда стоит использовать таблицы WITHOUT ROWID?

Таблицы WITHOUT ROWID полезны, когда у таблицы уже есть естественный составной первичный ключ и добавление отдельного rowid было бы избыточным. Все принципы работы индексов, описанные в этом документе, применимы к таким таблицам без изменений — единственное отличие состоит в том, что роль rowid берёт на себя PRIMARY KEY.