Продолжаю публиковать перевод статьи Remus Rusanu (CC-BY), о том, как MS SQL Server выполняет запросы. В этой части разберём, как данные хранятся внутри БД, а также как именно происходит их считывание в рамках запроса.
Первая и третья части доступны по соответствующим ссылкам.
Организация данных
Поговорим о том, как SQL Server хранит данные, потому что без этого будет сложно разобраться, как SQL Server обращается к ним при выполнении запроса. Есть три основных варианта хранения данных в SQL Server:
Куча. Это неупорядоченная таблица. Куча хранит данные всех колонок таблицы. Если таблица организована как куча, то при любом упоминании «кучи» подразумевается сама таблица – и наоборот.
Если при создании таблицы вы не указали Primary key – это куча. Если выполнили Select … INTO – то в результате тоже получите кучу. Подробнее о внутренней организации куч рассказано в документации.
Кластерные индексы. В отличие от кучи, это упорядоченная таблица. Кластерный индекс хранит в себе все колонки таблицы. Если таблица организована как кластерный индекс, то такой индекс и есть таблица. Кластерный индекс представляет собой сбалансированное дерево (B-Tree)
Если вы объявили первичный ключ (Primary key) на таблице, этот самый ключ будет использован для кластерного индекса (то есть, индекс будет построен по колонке PK). Если, конечно, вы не стали явно объявлять PK как NONCLUSTERED.
Подробнее о внутренней организации кластерного индекса также рассказано в документации.
Некластерные индексы. Это копия части таблицы, упорядоченная определенным образом. Некластерный индекс содержит в себе одну или несколько колонок из таблицы. Когда речь заходит об «индексах», обычно имеют в виду как раз некластерные индексы.
Нексластерные индексы, так же, как и кластерные - являются сбалансированными деревьями. Детальнее структура хранения некластерных индексов описана в BOL.
От переводчика. По моему скромному мнению, это самая неудачная часть статьи – всё объяснено, но понятнее от этого не становится. Поэтому позволю себе вмешаться.
И кластерные индексы, и некластерные представляют собой деревья. Но у кластерного индекса на последнем, листовом уровне, содержатся сами данные. А некластерный вместо этого хранит ссылки на основное хранилище данных – кластерный индекс или, если его нет, на записи кучи.
Начиная с SQL Server 2012 появились новые способы организации данных – некластерные колоночные индексы (nonclustered columnstore index), а ещё позже – и кластерные колоночные индексы (clustered columnstore index). Об особенностях их работы можно узнать в статьях по соответствующим ссылкам.
Доступ к данным
На "листьях" дерева выполнения (помним про то, как выглядит план запроса?) находятся операторы физического доступа к данным. Эти операторы возвращают строку данных из таблицы (или индекса) каждый раз, когда вызывается их метод next(). Есть три метода доступа к данным:
Оператор сканирования (Scan)
Оператор сканирования пробегается по всем строкам источника. Этот оператор не может выбрать одну конкретную строку – ему всегда приходится сканировать весь набор данных.
Если вы посмотрите на содержимое плана выполнения, вы скорее всего встретите один из этих операторов: Clustered Index Scan, Nonclustered Index Scan, Table Scan, Remote Index Scan или Remote Scan. Это действительно разные операторы, т.к. они обращаются к разным источникам (соответственно, отличается внутренняя механика работы). Но они едины в одном – каждому из этих операторов во время выполнения приходится выполнять полное сканирование источника, от начала до конца.
Поскольку таким операторам всегда приходится считывать весь источник данных, они оказываются довольно дорогими (как минимум, с точки зрения ввода-вывода). Обычно использование таких операторов – это удел тяжёлых аналитических запросов.
Оператор поиска (Seek)
Этот оператор может найти нужную строку при помощи ключа индекса. Поиск выполняется только в структурах сбалансированных деревьев – поэтому, он может работать только по кластерным и некластерным индексам.
Если индекс построен по нескольким колонкам, оператор поиска может сработать только если у него есть значения для самых левых (или первых) колонок в индексе. Разберём это на примере: предположим, у нас есть индекс, построенный по трём колонкам (A, B, C). В этом случае поиск может найти строки, если в условии поиска указаны значения для колонки A (A = ‘a’), для колонок A и B (A = ‘a’ AND B = ‘b123’) или для всех трёх колонок (A = ‘a’ AND B = ‘b123’ AND C = ‘c15’). Но если мы пропустим первую колонку (B = ‘b123’ AND C = ‘c15’) оператор поиска уже будет бессилен найти что-либо.
Кроме чтения отдельных строк, оператор поиска может выполнять поиск диапазонов. Если продолжить наш пример, оператор может найти все строки, где A находится между ‘a’ и ‘z’. Или строки, где A=’d’ и B между ‘b’ и ‘n’. Но не сможет найти строки с условием только по B: B > ‘b’ AND B < ‘n’.
Если вы посмотрите на план выполнения, вы можете встретить операторы Clustered Index Seek или Remote Index Seek. Они обращаются к разным источникам, но каждый из них может быстро найти строку по ключам индекса или же перебирать строки в отведённом диапазоне. Очевидно, не существует оператора для поиска в куче – просто потому, что куча это по определению неупорядоченная структура, для выполнения поиска ее всегда приходится прочитывать полностью.
В большинстве ситуаций оператор поиска является наиболее предпочитаемым методом доступа к данным (я бы не говорил так громко, но это точно справедливо для быстрых OLTP-запросов – прим. перев.)
Оператор поиска по закладкам. (Bookmark lookup)
Это особенный оператор доступа, который может быстро найти строку при помощи специального типа значений – закладки (bookmark). Мы не можем самостоятельно определить закладку – движок СУБД делает это самостоятельно. И в этом состоит особенность этого оператора – он не может быть «первичным», «исходным» оператором чтения данных. Кто-то должен предоставить ему значения закладок, поэтому этот оператор всегда обращается к ключам, которые до этого уже были прочитаны либо оператором сканирования, либо оператором поиска.
Этот оператор может применяться как вместе со структурированными источниками (индексы), так и с кучей. В плане выполнения он может отображаться как Bookmark Lookup, Row ID Lookup (поиск по куче) или Key Value Lookup (поиск, специфичный для B-деревьев).
Подытожив:
Сканирование (Scan) считывает все данные
Поиск (Seek) считывает только минимально необходимый набор данных
Кучи (heap) поддерживают только сканирование
Сбалансированные деревья (т.е. индексы) могут выполнять поиск только если установлен отбор по колонкам, находящимся в начале ключа индекса (т.е. по полям, находящимся «с левого края» списка полей индекса)
Строго говоря, операторы, применяемые для вставки, удаления или модификации строк – это тоже операторы доступа к данным. Например, Inserted Scan и Deleted Scan – это операторы для доступа к псевдо-таблицам inserted и deleted, которые появляются в контексте выполнения триггера. Или вот оператор Log Row Scan – ещё более эзотерический способ доступа к данным, который обращается не к таблицам с данными, а к логу транзакций. Но если мы продолжим спускаться в такие детали, мы слишком далеко отклонимся от цели этой статьи.
Вы можете часто встречать упоминание концепции «сканирование диапазона» (Range Scan). В этом случае имеют в виду оператор поиска (Seek), который быстро находит одну строку по ключу, а затем перебирает последующие строки – иногда, до нахождения другого определённого значения ключа. Получается, что оператор поиска выполняет сканирование внутри диапазона, определённого начальным и конечным значениями ключей. Именно поэтому и используют термин «сканирование диапазона».
Если мы вспомним, как именно происходит выполнение запроса, мы поймём, что именно операторы доступа к данным приводят в действие цикл выполнения запроса. Когда метод next() вызывается для самого верхнего оператора, он передаёт вызов дальше по дереву выполнения, пока не доберётся до оператора доступа к данным. Этот оператор при реализации next() как раз считывает очередную строку данных из соответствующего источника (кучи или B-дерева) – и возвращает считанную строку вверх по дереву. Оператор помнит, где остановилось чтение и при следующем обращении прочитает следующую строку. Операторы доступа к данным не могут иметь подчинённых операторов, они всегда находятся на листовом уровне дерева выполнения. С другой стороны, операторы, располагающиеся выше по дереву, реализуют разные манипуляции со считанными данными: соединение, отбор, сортировка результатов, вычисление агрегатов и т.д.
Чтение данных
Операторы доступа к данным всегда считывают данные из кэша и никогда – с диска. Этот кэш называется Buffer Pool. Если данных нет в кэше, оператор должен запросить их с диска (провоцируя обращения ввода-вывода к диску) и ждать, пока они не будут считаны с диска. Данные в кэше (Buffer pool) доступны всем выполняемым запросам – таким образом, после того, как данные были прочитаны и попали в кэш, любой следующий запрос уже воспользуется преимуществами кэша и не будет тратить время на обращение к диску.
SQL Server всегда читает в кэш столько данных, сколько может. При этом увеличивается частный объем памяти процесса (process allocated private memory), пока вся память системы не достанется SQL Server. Именно поэтому администраторы всегда настраивают максимальный порог потребления памяти (max server memory).
Buffer Pool, так же, как и отдельные операции чтения/записи, никогда не работает с отдельными строками. Вместо этого он работает со страницами, размер которых всегда равен 8Кб.
Посмотрим, как оператор доступа данных (в данном случае Сканирование) будет читать данные из кучи:
При первом вызове next() оператор должен найти первую подходящую строку и вернуть ее. SQL Server хранит метаданные о том, какие именно страницы относятся к таблице. Те, кому интересны подробности, могут обратиться к статье Managing Space Used by Objects и Inside the Storage Engine: IAM pages, IAM chains, and allocation units. Так вот, оператор доступа к данным обращается к Buffer Pool чтобы получить указатель на нужную страницу (точнее, на её расположение в памяти). Если страница не найдена в памяти, запрос приостанавливается до тех пор, пока страница не будет считана с диска.
Страница содержит массив из отдельных записей. Запись не обязательно соответствует целой строке данных. Дело в том, что большие значения или поля переменной длины могут храниться на другой странице. Рекомендую прочитать статью Inside the Storage Engine: Anatomy of a record, где раскрыты дополнительные подробности того, как строки располагаются внутри страниц.
Оператор доступа к данным находит первую строку на странице, считыавет оттуда нужные значения полей и возвращает их вышестоящему оператору. При этом, оператор доступа сохраняет своё внутреннее состояние – это позволяет ему мгновенно вернуться к нужной позиции (к той же странице и строке).
Родительский оператор получает первую строку, переданную оператором доступа к данным. Для получения следующей строки ему нужно будет опять вызвать next() у нижестоящего оператора.
Когда метод next() будет вызван у оператора доступа в следующий раз, этот оператор воспользуется своей памятью состояния: быстро спозиционируется на последней считанной строке, переместится на следующую строку, прочитает нужные данные и передаст управление обратно вышестоящему оператору.
Когда при очередном вызове оператора доступа к данным все строки из текущей страницы будут считаны, оператор запросит у Buffer pool ссылку на следующую страницу. Какая именно страница будет «следующей» описано в метаданных таблицы – тут я опять отсылаю к статье Пола Рэндалла про IAM-страницы, которая подробно раскрывает эту тему.
Как только следующая страница окажется в Buffer Pool, оператор прочитает первую запись (то есть, скопирует нужные поля из этой записи) и вернёт управление назад, к вышестоящему оператору.
Всё это продолжается, пока не будет прочитана последняя строка, принадлежащая таблице. В этот момент внутренний указатель оператора доступа переместится в состояние «за границами таблицы» и оператор не сможет больше вернуть ни одной строки.
Когда оператор доступа к данным больше не может возвращать строки, вышестоящий оператор переходит к следующей стадии: выполняет то, что нужно сделать, когда нижестоящий оператор «завершён».
Например, SORT в этот момент может начать возвращать строки для своего вышестоящего оператора. HASH JOIN начинает перебирать «проверяемую» сторону – и возвращать найденные строки. А SELECT в этот момент возвращает False, что в конце концов приводит к завершению выполнения запроса.
Оператор доступа к данным можно «перемотать назад». Например, если он оказался во «внутренней» части оператора Nested Loops (вложенные циклы), то после завершения сканирования для текущей строки, внешний «ввод» Nested Loops передаст следующую строку – и внутреннему оператору придётся повторить поиск для этой новой строки. В этом случае указатель внутреннего состояния сбрасывается – и полный цикл сканирования повторяется заново, начиная с первой строки первой страницы.
Для сравнения, вот как оператор доступа будет работать с отсортированным B-деревом (помним про индексы?):
При первом вызове next() оператор должен найти (Seek) первую строку, которая содержит искомый ключ поиска. В метаданных, которые SQL Server сохраняет для B-деревьев, есть информация о том, какие страницы принадлежат индексу. Напомню, что в случае с кучей (heap) нам надо было начинать поиск с самой первой страницы. В отличие от кучи, здесь оператор может сразу спозиционироваться на строке, содержащей искомый ключ.
Оператор получает из метаданных идентификатор корневой страницы, затем обращается за ссылкой на неё к Buffer Pool. Используя ключ поиска оператор постепенно «спускается» по дереву вплоть до листовой страницы, содержащей строку с ключом, равным ключу поиска, либо следующим сразу следом за ним. Спускаясь по дереву, на каждом шаге оператор доступа должен запросить из Buffer Pool соответствующую страницу – и, возможно, дождаться, пока она будет считана с диска.
Добравшись до листового уровня, оператор доступа должен будет просмотреть строки, содержащиеся на странице, чтобы найти строку с нужным ключом – затем скопировать нужные значения колонок и вернуть управление вверх по дереву плана.
Допустимо, что оператор поиска вообще не найдёт строки, удовлетворяющей условиям поиска.
Оператор доступа может искать строку по полному совпадению ключа поиска (т.е. «равно»); может искать строку, следующую за ключом поиска (т.е. «больше») или строку, равную или следующую за ключом поиска (т.е. «больше или равно») . Поиск по сбалансированному дереву может выполняться в любом направлении: как «по возрастанию», так и «по убыванию». Поэтому определение строки, следующей за ключом поиска, зависит от направления поиска. Это направление не стоит путать с указанием порядка сортировки для ключа при создании индекса: в последнем случае речь будет идти как раз о физическом порядке следования строк.
Продолжаем. Вышестоящий оператор получает первую строку, переданную оператором Seek
Если оператор доступа используется в рамках «сканирования диапазона», для него будет снова выполнен метод next()
Оператор доступа к сбалансированному дереву помнит последний ключ, который он вернул. При повторном обращении он использует этот ключ, чтобы спозиционироваться на последней считанной строке, используя алгоритм, разобранный выше. После того, как эта последняя строка найдена, оператор просто переходит к следующей строке на странице и возвращает её.
Если на текущей странице закончились строки, оператор обращается к Buffer pool за следующей страницей – и вернёт первую строку с этой страницы (и, естественно, если нужной страницы в Buffer pool не окажется, придётся подождать, пока она будет считана с диска). Тут важно заметить, что листовые страницы B-дерева cвязаны между собой: страница знает номера своих соседей слева и справа. Так что для поиска нужной страницы не придётся повторять весь маршрут по дереву индекса; СУБД сразу знает, какую страницу прочитать.
Вышестоящий оператор получает строку, которую вернул оператор доступа к данным
У «Сканирования диапазона» может быть задано значение границы диапазона. В таком случае, если значение в очередной считываемой строке окажется больше, чем значение границы диапазона, весь вызов next() вернёт False (то есть, не будет возвращать ни одной строки).
Понятие «больше границы диапазона», конечно же, относительно, поскольку поиск по индексу может выполняться как «вверх», так и «вниз», да и сам индекс может быть отсортирован как по возрастанию, так и по убыванию.
Получается, оператор может завершить сканирование по двум причинам: либо найдёт строку за пределами границы сканирования, либо достигнет последней строки последней страницы дерева.
И последнее: операторы доступа к деревьям могут быть не только «перемотаны» (rewind), но и «связаны заново» (rebind). Перемотка сбрасывает оператор к начальной точке, но сохраняет те же значения отбора (по ключу или по диапазону). Повторное связывание, кроме этого, изменит и сами параметры отбора.
Больше подробностей – в статье Showplan Logical and Physical Operators Reference
Упреждающее чтение (Read ahead)
Из описания работы оператора сканирования вы можете заметить, что каждый раз, когда он заканчивает чтение строк со страницы, ему тут же требуется получить из Buffer pool следующую страницу. Если нужной страницы в Buffer pool нет, приходится ждать, пока она не будет считана с диска. И если ожидания чтения с диска будут повторяться после каждой обработанной страницы, общая производительность запроса просядет.
Решение – заранее считать в память те страницы, которые пока ещё не были запрошены, но которые скоро понадобятся оператору доступа для выполнения запроса. SQL Server именно так и поступает: выполняет асинхронное упреждающее чтение тех страниц, которые будут запрошены оператором, ещё до того момента, как оператор запросит их для обработки строк. Таким образом, к тому моменту, как оператор обратится к странице, она уже будет находиться в Buffer pool – и доступ к такой странице будем практически мгновенным. Подробности этого механизма описаны в статьях Reading Pages и Sequential Read Ahead. Кроме того, существует отдельный вариант упреждающего чтения для доступа к случайным страницам в рамках вложенных циклов (Nested Loops): Random Prefetching.
в следующей части - обзор механизма блокировок и разбор процесса записи изменений в БД