Как реляционная база данных выполняет и оптимизирует ваш запрос

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

Цели оптимизации запроса

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

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

Индексы

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

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

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

Страница статистики

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

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

Порядок полей

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

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

Оценка предложения WHERE

Самая важная часть оператора SELECT для определения того, какой индекс будет использоваться, - предложение WHERE.4 Предложение WHERE фильтрует записи для вывода и является первым кандидатом для оптимизатора запросов при выборе индекса. Имеется несколько различных способов использования предложения WHERE. Наиболее общие формы подробно объясняются ниже:

Соответствие (равенство)

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

Больше или меньше чем

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

Функции

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

Оценка предложения ORDER BY

Как только анализатор запросов обработает предложение WHERE, он обратится к предложению ORDER BY. То, что ищет оптимизатор запросов, - это способ, который не приведет к необходимости пересортировки уже полученных результатов. Если оптимизатор запросов сможет найти индекс, который уже содержит строки, расположенные в правильном порядке, и они соответствуют предложению WHERE, он будет использовать этот индекс так, чтобы избежать результирующей сортировки.

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

Покрытие индексами

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

Если, например, вы выбираете только User ID, First Name, LastName и EmailAddress из записи пользователя, и у вас имеется индекс, который содержит все эти поля, то анализатор запросов сможет использовать индекс и вообще не обращаться к базовой таблице с требуемыми данными.

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

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

Помоги оптимизатору запросов

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

*Комментарии к статье Дмитрия Зверева:

1. На самом деле кластерные индексы также потребляют дополнительное место на диске. Любой индекс представляет из себя B-дерево. B-дерево имеет несколько уровней. У класетрного индекса, в отличии от некластрного, нижним уровнем (т.е. его листьями) являются сами данные. Это действительно значит, что под нижний уровень кластерного индекса не выделяется дополнительное дисковое пространство, поскольку оно уже выделено под данные. Но все вышестоящие уровни также занимают место на диске. Конечно, кластерные индексы занимают меньше дополнительного места, и часто гораздо меньше, но нельзя сказать, что не занимают совсем. А если, скажем, индекс уникальный, а строки таблицы большие и занимают целую страницу данных, то эти дополнительные объемы данных (требуемые под остальные уровни индекса), будут весьма значительны, поскольку на первом индексном уровне (не считая листьев, являющихся тут страницами данных), должна быть запись для каждой строки данных.

Нельзя также сказать, что использование кластерных индексов не требует дополнительных опреаций чтения. Может конечно и не требовать, но может и требовать - в зависимости от ситуации. Так для разных ситуаций есть две разные операции, работающие с кластерными индексами - Clustering index Seek и Clustering index scan. Первая будет использовать B-дерево и соответственно использовать дополнительные операции чтения. Вторая будет читать только листья дерва (данные) и как следствие дополнительных операций не будет. Стоит, однако заметить, что из этого вовсе не следует, что операция Clustering index scan предпочтительнее. Если можно сделать поиск по индексу, то это как правило лучшее решение, замечание просто говорит о том, что при ее использовании также будут совершаться операции чтения со страницами не являющимися непосредственно страницами данных, т.е. потребуется чтение дополнительных страниц.

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

2. Опять же не совсем корректно. Надо ведь учесть еще чтения верхних уровней индекса. Соответственно получится больше чем 2*х чтений. Это число будет близко к 2*х, но все опять же зависит от разных факторов - например длина индексного поля. Верхние уровни индекса часто находятся в кэше, но опять же все завист от того какого размера таблицы, и значит как много имеется уровней дерева. Или напрмиер если таблица давно (или совсем) не использовалась, то и в кэше их не будет. > Или другой аспект: чтение ведь происходит постранично а не по записям. Поэтому, с учетом того, что в индексах строки хранятся упорядоченно, то нет необходимости делать чтение на каждую запись. Например, есть неуникальный индекс по полю а (тип tinyiny). Есть запрос Select * from Mytable where a=14. В таблице MyTable имеется 1000 строк со значением поля а=14. Для того чтобы прочитать необходимые ссылки на страницах индекса нет необходимости делать 1000 чтений. Достаточно прочитать верхние уровни индекса плюс 1-2 страницы на уровне листьев для считывания всех 1000 записей. после чего уже будут чтения страниц данных (максимально до 1000 чтений). > Т.е. формула 2*х довольно далека от универсальности.

3. Я бы, пожалуй, сказал что на основе статистики оптимизатор сравнивает сколько страниц потребуется считать с использованием индекса и без него и на основе этого сравнения решает что выгоднее. Например, пусть есть таблица, имеющая индекс и содержащая всего одну строку. > При запросе, содержащем условие на проиндексированное поле, проще сделать скан таблицы, т.к. тогда надо будет прочитать 1 страницу. При использовании индекса (когда строка попадает в результат - 2 страницы - индексная+страница данных). Но вообще для описанной ситуации как раз MSSQL Server предпочитает индекс использовать Хотя мне это не кажется оптимальным...

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

Читайте также:
  • Проектирование базы данных: выбор первичного ключа
    Современные системы баз данных основываются на реляционной модели хранения и извлечения данных. Название происходит от слова relationship - отношение между столбцами в таблице (а не из того, что Вы можете связать таблицы между собой). Другими словами, "реляционный" означает, что несколько ...
  • Модель "сущность-связь"
    Первый вариант модели сущность-связь был предложен в 1976 г. Питером Пин-Шэн Ченом. В дальнейшем многими авторами были разработаны свои варианты подобных моделей (нотация Мартина, нотация IDEF1X, нотация Баркера и др.). Кроме того, различные программные средства, реализующие одну и ту же нотацию, м...
  • Целостность реляционных данных
    Это: Целостность сущностей. Целостность внешних ключей. Прежде, чем говорить о целостности сущностей, опишем использование null-значений в реляционных базах данных. Null-значения Основное назначение баз данных состоит в том, чтобы хранить и предоставлять информацию о реальном мире. Для представле...
  • Реляционная алгебра
    В реализациях конкретных реляционных СУБД сейчас не используется в чистом виде ни реляционная алгебра, ни реляционное исчисление. Фактическим стандартом доступа к реляционным данным стал язык SQL (Structured Query Language). Язык SQL представляет собой смесь операторов реляционной алгебры и выражен...
  • Базовые понятия реляционной модели данных
    Согласно Дейту, реляционная модель состоит из трех частей: Структурной части Целостной части Манипуляционной части Структурная часть описывает, какие объекты рассматриваются реляционной моделью. Постулируется, что единственной структурой данных, используемой в реляционной модели, являются нормали...