Что нужно знать, чтобы писать быстрые SQL-запросы

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

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

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

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

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

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

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

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

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

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

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

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

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

Предположим, что мы хотим найти телефон человека, зная его адрес. У нас есть телефонный справочник, где люди записаны по фамилии. Сколько времени нам потребуется, чтобы завершить поиск? Оказывается, речь снова идёт о 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 = 'Толстой Лев Николаевич'

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

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

Если мы захотим найти все журналы за 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‑дерево (читается как «би дерево»). Подробно она описана в третьем томе «Искусства программирования», посвящённом сортировке и поиску.

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

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

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

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

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

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

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

1. У таблицы в базе данных может быть несколько индексов. Для каждого индекса будет создано своё B‑дерево.

2. В узлах B‑дерева хранятся копии ключевых полей. Это нужно для быстрого поиска: все данные для сравнения должны быть под рукой.

3. В узлах B‑дерева помимо ключевых полей хранятся адреса записей на диске в виде пары чисел: номер страницы данных, номер записи на странице.

4. Поиск единичного ключа, его вставка и удаление требуют времени.

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 будет работать точно так же. Из индекса он узнает адреса страниц, где находятся записи с книгами Льва Толстого. Чтобы найти Анну Каренину, сервер будет загружать эти страницы по очереди и перебирать записи, пока не найдёт нужную.

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

В нашем случае 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

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

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

Запрос

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

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

Обсуждение

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

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

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

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

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

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

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

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

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

Важные подробности

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

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

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

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

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

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

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

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

 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.