Теория индексов
Что нужно знать, чтобы писать быстрые SQL запросы

Введение

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

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

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

Волшебная сила порядка

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

В конце концов мэр стал обладателем большого списка телефонов, данные в котором никак не упорядочены. Захоти мы найти в этом списке телефон Пушкина Александра Сергеевича, нам придётся читать все записи подряд, пока мы не встретим нужное имя. Если в городе 100 000 жителей, в худшем случае нам придётся прочитать все 100 000 записей.

Если жителей много, поиск займёт много времени. Поэтому в настоящих справочниках жители упорядочены по фамилии и имени. Поиск нужного жителя идёт методом половинного деления или двоичного поиска. Мы открываем справочник где-то посередине и смотрим, какая там фамилия. Предположим, мы видим фамилию Лермонтов. Это значит, что Пушкин находится дальше, во второй половине справочника, потому что жители в списке расположены в алфавитном порядке.

Таким образом мы сразу сокращаем зону поиска приблизительно в два раза. Повторим поиск, пока не найдём нужный разворот. На каждом шаге список будет сокращаться наполовину. Если в справочнике 100 000 жителей, нужного человека мы найдём в худшем случае за 17 попыток. Это наименьшее целое число, которое больше, чем log₂ 100000.

Поиск в неупорядоченном списке из 100 000 жителей требует проверить 100 000 записей, а двоичный поиск — всего 17. Разница огромна. И чем больше число жителей, тем она больше.

Вот таблица, которая показывает, насколько медленно растёт log₂ N по сравнению с N.

Скобки ⌈ и ⌉ означают округление вверх, а ⌊ и ⌋ — вниз.

В третьей колонке видно, насколько двоичный поиск быстрее перебора. Для тысячи записей в сто раз,, для миллиона — в пятьдесят тысяч раз, а для миллиарда — в тридцать миллионов раз!

Такова волшебная сила упорядоченного набора данных.

Способы упорядочивания

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

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

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

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

Мы размещаем карточки в алфавитном порядке. Чтобы найти книгу, мы сначала ищем карточку, используя метод половинного деления, как и в примере с телефонным справочником. Узнав место хранения книги, идём и забираем её.

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

Другое название картотеки — указатель, поскольку карточки указывают, где лежит книга. По английски указатель называется index. Индексы в СУБД по сути и есть карточки, которые позволяют сделать поиск быстрым.

Немного SQL

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

CREATE TABLE Books
(
  Id INT NOT NULL,
  Author VARCHAR(100) NOT NULL,
  Title VARCHAR(100) NOT NULL,
)

Здесь у нас суррогатный ключ Id и поля для хранения автора и названия каждой книги.

CREATE INDEX IX_Books_Author ON Books (Author);
CREATE INDEX IX_Books_Title ON Books (Title);

Мы создали индексы для быстрого поиска по полям Author и Title. Вы обратили внимание, что для каждого индекса надо придумать имя? PostgreSQL умеет генерировать имена сам, а MySQL и SQL Server —нет.

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

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

Название индекса начинается с IX_, где ix — это сокращение от index. Затем идёт имя таблицы, а за ним — через символ подчёркивания — имя поля, по которому составляется индекс.

Таким образом индекс для поля Author в таблице Books называется IX_Books_Author.

Запрос, который позволяет найти все книги автора:

SELECT * FROM Books WHERE Author = 'Толстой Лев Николаевич'

Если в библиотеке 100 000 книг, поиск без индекса потребует полного перебора всех 100 000 записей. Как мы помним, после создания индекса нужно будет не больше 17 сравнений, что быстрее почти в 6 000 раз.

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

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

Диапазоны и составные ключи

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

Как найти все журналы, выпущенные весной 2004-го года? Если у нас нет картотеки по дате выхода, то найти их можно будет только методом перебора, то есть медленно. А если у нас есть картотека?

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

CREATE TABLE Magazines
(
  Id INT NOT NULL,
  Title VARCHAR(100) NOT NULL,
  ISBN VARCHAR(13) NOT NULL
  Year INT NOT NULL,
  Month INT NOT NULL
);

CREATE INDEX IX_Magazines_Year_Month ON Magazines (Year, Month);

С помощью двоичного поиска мы сначала найдём начало диапазона: карточку 2004-03 за март 2004-го года. Затем найдём конец диапазона: карточку 2004-05. Поскольку карточки упорядочены по возрастанию даты, результатом поиска будут первая карточка, последняя карточка и всё, что окажется между ними.

SELECT * FROM Magazines WHERE Year = 2004 AND Month >= 3 AND Month <= 5

Алгоритм поиска будет немного отличаться от простого варианта. Очевидно, в марте 2004-го года вышел не один журнал, и в картотеке наверняка окажется несколько карточек с датой 2004-03. В начале диапазона нам надо искать самую первую, а в конце — самую последнюю. Этот более сложный алгоритм, но он требует приблизительно столько же сравнений — log₂ N.

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

Сейчас объясню, почему.

Если мы захотим найти все журналы за 2004 и 2005 годы, нам не придётся создавать новую картотеку с ключом «год», поскольку индекс по году у нас уже присутствует — нам достаточно просто не учитывать месяц.

SELECT * FROM Magazines WHERE Year = 2004 OR Year = 2005

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

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

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

Детали реализации — данные

Всякая аналогия ложна. Чтобы избежать неверных выводов из нашей библиотечной метафоры, поговорим о том, как устроены полки и карточки в компьютерах. Исторически базы данных появлись чуть позже дисковых накопителей, которые сейчас называют жёсткими дисками или винчестерами. Какие особенности жёстких дисков важны в работе сервера БД?

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

Во-вторых, на жёстком диске большое время занимает первоначальное позиционирование магнитной головки. Гораздо быстрее прочитать несколько секторов подряд на соседних дорожках, чем в разных местах диска. Из-за этого операционные системы хранят данные не в единичных секторах, а в кластерах. Кластеры состоят из 4-х, 8-ми, 16-ти секторов и так далее. Возможны разные варианты, и мы не будем углубляться в детали. Нам важно понять, почему размер блока при работе с жёстким диском обычно составляет несколько килобайт.

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

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

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

Точный размер страниц зависит от СУБД, обычно это от 4 до 64 килобайт. Страницы используются как для хранения записей, так и для хранения индексов, в каждом случае есть своя специфика.

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

Чтобы избавиться от пустых страниц в середине, нужно выполнить сжатие (shrink) базы. Эта операция не входит в стандарт SQL и не все серверы её поддерживают.

Размер одной записи не может превышать размер страницы. Прочитав это, вы, наверное, удивитесь, потому что в базе данных можно хранить и большие двоичные объекты (BLOB’ы, от Binary Large Objects), и большие текстовые поля. На самом деле такие поля хранятся отдельно от остальной записи на страницах специального типа, но детали сейчас неважны. Важно, что записи всегда помещаются на странице целиком, и что записей на странице может быть несколько, иногда даже несколько десятков или сотен.

Детали реализации — индексы

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

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

Время поиска в отсортированном массиве пропорционально log N. Математики говорят, что временная сложность двоичного поиска равна Θ(log N), то есть тета-большое от логарифма эн. Вместо греческой буквы Θ часто используют латинскую букву O и пишут O(log N), о-большое от логарифма эн. Это не совсем корректно, но считается приемлимым для прикладной литературы.

Проблемы массива начинаются тогда, когда мы добавляем или удаляем элемент. Чтобы поиск продолжал работать, нам надо сохранять порядок элементов — мы не можем просто добавлять новые элементы в конец, мы должны вставлять их в правильные места. Найти правильное место недолго — O(log N), но вставка и удаление в середине массива требуют сдвига элементов к началу или к концу. Временная сложность сдвига составляет O(N). Мы помним, что это очень медленно для больших таблиц.

Чтобы ускорить вставку и удаление, вместо массива применяют двоичное дерево, в котором и поиск, и вставка, и удаление выполняются за время O(log N). К сожалению у двоичного дерева бывает вырожденный случай, который возникает, если добавлять в дерево упорядоченные элементы. В каждом узле вырожденного дерева есть только правые (или только левые) поддеревья. Скорость поиска, вставки и удаления в таком дереве снова будет равна O(N).

Мы избежим вырожденного случая, если будем балансировать дерево после удалений и вставок. В сбалансированном дереве узлы распределены более-менее равномерно. Есть несколько алгоритмов балансировки, и каждый из них приводит к тому, что худшее время поиска, вставки и удаления составляет O(log N).

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

К счастью, эту задачу уже решили за нас, придумав B-дерево. Мы не будем останавливаться на этой структуре подробно, но отметим несколько важных моментов:

1. У таблицы в базе данных может быть несколько индексов. Для каждого идекса будет создано своё B-дерево.
2. В узлах B-дерева хранятся копии ключевых полей. Это нужно для быстрого поиска: все данные для сравнения должны быть под рукой.
3. В узлах B-дерева помимо ключевых полей хранятся адреса записей на диске в виде пары чисел номер страницы данных, номер записи на странице.
4. Поиск единичного ключа, вставка ключа и удаление ключа требуют O(log N) времени.
5. Каждый новый индекс увеличивает время вставок и удалений, поэтому чем меньше индексов, тем быстрее.
6. Каждое новое поле в индексе увеличивает размер ключа и всё B-дерево, поэтому чем меньше полей, тем быстрее.

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

Типичные задачи

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

Книга по автору и названию

Запрос

SELECT Id, Author, Title
  FROM Books
 WHERE Author = 'Толстой Лев Николаевич' AND Title = 'Анна Каренина'

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

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

SELECT Id, Author, Title
  FROM Books
 WHERE Author = 'Толстой Лев Николаевич' AND Title = 'Анна Каренина'
 FETCH FIRST 1 ROWS ONLY

Странная конструкция FETCH FIRST 1 ROWS ONLY говорит серверу, что нам нужна одна любая книга из тех, что удовлетворяют условиям. Долгое время стандарт SQL не описывал, как ограничивать количество записей в выборке, и каждая реализация вводила собственный синтаксис.

Так это будет в MS SQL:

SELECT TOP 1 Id, Author, Title
  FROM Books
 WHERE Author = 'Толстой Лев Николаевич' AND Title = 'Анна Каренина'

Так — в My SQL:

SELECT Id, Author, Title
  FROM Books
 WHERE Author = 'Толстой Лев Николаевич' AND Title = 'Анна Каренина'
 LIMIT 1

Конструкция FETCH работала в DB2 и Oracle и с 2008-го года она входит в стандарт SQL.

Обсуждение

Предположим, в библиотеке есть индекс по автору. Это значит, что на каждой карточке записаны только автор и место книги зале. Как такой запрос выполнит библиотекарь?

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

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

Точно такая же ситуация возникнет, если у нас будет индекс не по автору, а по названию.

Производительность выполнения такого запроса составляет O(M + log N), где N — общее количество книг, а M — среднее количество книг в выборке.

В нашем случае M не очень велико, вряд ли в библиотеке будет несколько тысяч книг Толстого, поэтому мы можем оставить один простой индекс. Специалисты по базам данных говорят, что у полей Author и Title высокая селективность.

Чтобы вычислить селективность поля, надо разделить количество его уникальных значений на общее количество записей, и выразить результат в процентах. Селективность уникального поля равна 100%.

Поле Пол может содержать всего два значения — мужчина и женщина —. Его селективность для таблицы из тысячи записей равна 2/1000 × 100%, то есть 0,2%.

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

Любой из индексов (Author, Title) и (Title, Author) позволит быстро найти книгу непосредственно в картотеке. Зная положение книги в зале, библиотекарь быстро принесёт её читателю.

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

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

Индекс (Author, Title) нам не поможет. Библиотекарь будет вынужден проверить все книги в шкафах, а сервер БД — все записи в таблице.

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

Все книги автора, упорядоченные по названию

Запрос

  SELECT Id, Author, Title
    FROM Books
   WHERE Author = 'Толстой Лев Николаевич'
ORDER BY Title

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

Обсуждение

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

Библиотекарь находит первую книгу Льва Толстого и выписывает названия книг подряд.

Затем он упорядочивает их по названию.

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

Мы можем убрать сторой шаг — сортировку — создав составной индекс и по автору и по названию (Author, Title). Карточки в таком индексе уже находятся в нужном порядке и их можно просто выписать.

Обратите внимание, что когда нам нужна сортировка книг автора, надо создавать составной индекс (Author, Title). Сначала автор, потом название. Индекс (Title) содержит упорядоченный список всех книг без учёта автора.

Количество книг автора

Запрос

SELECT COUNT(*)
  FROM Books
 WHERE Author = 'Толстой Лев Николаевич'

Функция COUNT относится к агрегатным функциям. Агрегировать означает собирать или объединять. Агрегатные функции применяются не к одному значению, а к множеству значений. Функция MIN(Salary) возвращает минимальное значение поля Salary в выборке, а функция AVG(Salary) — среднее.

В отличие от них, функция ROUND(Salary) округляет одно конкретное значение. Она не является агрегатной.

Синтаксис COUNT(*) значит, что нас интересует общее количество строк в выборке. Мы получим тот же результат, если укажем в качестве параметра первичный ключ — COUNT(Id).

Обсуждение

Как такой запрос выполнит библиотекарь? Очевидно, что не имея индексов придётся действовать методом перебора. А если у нас есть индекс по полю Author?

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

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

Что значит небыстрым? В середине 90-х пользователь дожидался бы результата несколько десятков секунд. Сейчас он выполнится за несколько секунд, даже за доли секунды.

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

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

SELECT COUNT(*)
  FROM Books

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

В каком году впервые выписан журнал

Запрос

SELECT MIN(Year)
  FROM Magazines
 WHERE Title = 'Наука и жизнь'

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

Обсуждение

Если у нас нет никаких индексов, библиотекарь (и сервер БД) будет действовать методом полного перебора. Что, если у нас есть индекс по полю Title?

Библиотекарь составит список экземпляров и отправится к книжным полкам, чтобы перебрать все наличные номера в поисках самого раннего. Это тоже перебор, но не полный, а частичный.

Выражаясь языком математики, полный перебор выполняется за время O(N), где N — все журналы в библиотеке. Их может быть тридцать тысяч. Частичный перебор выполняется за время O(M + log₂ N), где M — только журналы «Наука и жизнь». Их на два порядка меньше, скажем, всего пара сотен.

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

Но что, если селективность у поля невысокая? На помощь приходят составные индексы, в нашем случае — (Title, Year).

По такому индексу библиотекарь сразу найдёт нужную запись методом половинного деления. Если говорить о сервере, то он вычислит MIN(Year) за время O(log₂ N).

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

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

Агрегатные функции COUNT, AVG, SUM не смогут работать настолько быстро, потому что они вынуждены учитывать каждое значение в выборке. Время их выполнения всегда O(M + log₂ N).

А MIN и MAX могут «работать на стероидах».

Важные детали

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

Размер выборки

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

Проблемы с производительностью возникают, если нам это не удаётся.

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

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

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

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

Агрегатные функции могут скрадывать реальный объём данных, которые обрабатывает сервер. Мы помним пример с функцией COUNT, быстродействие которой O(M + log₂ N). Сервер возвращает одно число, но если значение M велико, запрос будет выполняться медленно.

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

  SELECT Posts.Id, Posts.Title, COUNT(Comments.Id)
    FROM Posts
    LEFT JOIN Comments ON Posts.Id = Comments.PostId
GROUP BY Posts.Id, Posts.Title
   FETCH FIRST 10 ROWS ONLY

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

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

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

Диапазон

Покрывающие (включающие) индексы

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

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

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

Сервер баз данных работает похожим образом. Представим, что мы сделали индекс (Title, Year, Month) для таблицы журналов.

CREATE INDEX IX_Magazines_Title_Year_Month ON Magazines (Title, Year, Month)

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

Пример. Получаем список журналов в хронологическом порядке.

  SELECT Title, Year, Month
    FROM Magazines
   WHERE Title = 'Наука и жизнь'
ORDER BY Year, Month

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

Теперь мы хотим получить не только номера журналов, но и номер ISBN.

  SELECT Title, Year, Month, ISBN
    FROM Magazines
   WHERE Title = 'Наука и жизнь'
ORDER BY Year, Month

ISBN в индексе нет, поэтому сервер вынужден загружать страницы данных, искать там нужные записи и брать ISBN оттуда. Это долго.

Если у вас встречается такой запрос, вы можете его ускорить, просто добавив поле ISBN в индекс (Title, Year, Month). Это нужно не для быстрого поиска, а для того, чтобы иметь под рукой все поля, которые встречаются в запросе.

CREATE INDEX IX_Magazines_Title_Year_Month ON Magazines (Title, Year, Month, ISBN)

Индексы, которые содержат все поля из запроса, называют покрывающими (covering) или включающими (included).

Некоторые серверы, например Microsoft SQL Server, поддерживают включащие индексы особым образом. Поскольку сортировка по дополнительным полям нам не нужна, они по ним и не сортируют, а просто сохраняют значения.

CREATE INDEX IX_Magazines_Title_Year_Month ON Magazines (Title, Year, Month) INCLUDE (ISBN)

Кластерные индексы

У покрывающих индексов есть частный случай, который встречается особенно часто — кластерные индексы (clustered). Если в наших запросах нужны все поля записи, мы можем создать максимальный покрывающий индекс. В этом случае дублировать запись ещё и на странице данных не нужно.

В отличии от обычных покрывающих индексов, кластерный индекс может быть только один. Очевидно, он всегда делается по первичному ключу. Например, в Microsoft SQL Server класетрный индекс создаётся так:

CREATE TABLE Magazines
(
  Id INT IDENTITY (1,1) NOT NULL,
  CONSTRAINT PK_Magazines_Id PRIMARY KEY CLUSTERED (Id)
)

Заключение

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

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

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

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

• MySQL. Оригинальная документация на её перевод на русский язык по оператору EXPLAIN.

• PostreSQL. Документация на английском и русском языке по оператору EXPLAIN.

• Microsoft SQL Server. Инструмент SQL Server Management Studio умеет графически отображать планы выполнения. Впрочем, оператор EXPLAIN тоже есть.

• Oracle. EXPLAIN PLAN.