Итераторы, планы запроса, и почему они выполняются в обратном порядке
Пересказ статьи Paul White. Iterators, Query Plans, and Why They Run Backwards
Итераторы
SQL Server обладает расширенной архитектурой для оптимизации и выполнения запросов, используя "итераторы" в качестве строительных блоков.
Вероятно, итераторы более знакомы в их представлении на графическом плане, где каждая иконка представляет отдельный итератор. Они также показаны как узлы RelOp при выводе плана запроса в формате XML.
Каждый итератор выполняет отдельную простую функцию, например, условие фильтрации или агрегацию. Он может представлять собой логическую операцию, физическую операцию или (чаще всего) и ту, и другую.
Например, Aggregate - это логический оператор, а Stream Aggregate и Hash Aggregate являются физическими операторами. Аналогично, Inner Join - это логический оператор; а Nested Loops - физический. В выводе как графических планов, так XML, указываются эти свойства:
Логические итераторы могут составлять сложные комбинации, чтобы удовлетворить любым требованиям, которые могут быть выражены на языке SQL. Физические итераторы комбинируются, создавая исполняемое дерево, используемое ядром сервера для получения результатов.
Логические итераторы представляют исходный запрос, транслированный в реляционную алгебру; физические итераторы представляют физическую алгебру: конкретные алгоритмы, используемые ядром системы хранения SQL Server и процессором запросов для выполнения логической задачи.
Итераторы являются объектами кода, которые разделяют общий интерфейс методов и свойств. Из них наиболее часто используемыми являются методы получения строк и множеств, извлечение информации о свойствах, получение предполагаемой стоимости, которая используется оптимизатором.
Общие черты (и абстракция структуры) дают возможность легкого расширения при обновлении базы данных и языка. Это также позволяет итераторам быть привязанными к структуре дерева без необходимости для них знать что-либо о подключении других итераторов.
Исполняемый код, который формирует ядро выполнения итераторов, тоже написан так, чтобы избежать жестко привязанных зависимостей между родительскими и дочерними итераторами в дереве плана. Это исключает необходимость перекомпиляции базового кода итератора всякий раз, когда он встраивается в новый план (функциональные указатели).
Все итераторы требуют небольшое количество постоянной памяти для хранения состояния (локальные переменные), когда они выполняются. Эта память формирует часть скомпилированного плана, поэтому не требуется формального выделения памяти при всяком выполнении плана. Кэшированный размер плана включает это распределение памяти.
Общие методы, имеющие наибольшее отношение к нашему обсуждению, относятся к обработке множеств строк. Это методы Open (открыть), GetNext (получить следующий) и Close.
Давайте рассмотрим простой план (сам запрос сейчас не важен):
Задавались ли вы когда-нибудь вопросом о том, как выполняется подобный план? Где он стартует, и откуда он знает, где остановиться? Основываясь на линиях и стрелках, которые связывают итераторы в графическом плане, мы можем предположить, что выполнение стартует с производящих данные итераторов (сканирование - scan) и продолжается пока не заканчиваются строки.
Стрелки на соединяющих линиях показывают направление потока данных; между тем, порядок выполнения итераторов совершенно другой. Выполнение запроса всегда начинается с корневого итератора - hash join на диаграмме выше.
Механизм выполнения непосредственно взаимодействует только с этим корневым итератором. Он вызывает метод Open, чтобы подготовить его к возвращению данных, а затем периодически вызывает его метод GetNext, чтобы получать по одной строке вывода запроса. Как только метод GetNext потерпит неудачу при возвращении очередной строки, вызывается метод Close, и выполнение запроса прекращается. Проще не бывает.
Хорошо, теперь немного подробней об этом. Давайте посмотрим, что происходит, когда вызывается метод Open на итераторе hash join:
1. hash join вызывает метод Open для построения входа (build input).
2. Метод Open итератора Scan подготавливает ядро системы хранения к началу подачи строк из таблицы Product. Затем управление передается назад в hash join (помним, что он еще выполняет свой метод Open).
3. hash join периодически вызывает метод GetRow на итераторе Scan.
4. Каждый вызов GetRow возвращает одну строку из Scan в hash join. Эти строки используются для построения хеш-таблицы соединения.
5. Как только вызов GetRow на таблице Product сообщает, что строк больше нет, hash join вызывает метод Close на Scan.
6. Итератор Scan выполняет процедуры очистки и возвращает управление hash join.
7. Теперь Hash join вызывает Open на своем своем внутреннем входе (probe input).
8. Итератор Scan на таблице Inventory подготавливает соединение с системой хранения, а затем передает управление hash join.
9. hash join получает возврат от своего метода Open (окончательно), и управление передается механизму выполнения.
Механизм выполнения теперь периодически вызывает GetRow на hash join, возвращая результаты запроса:
1. hash join вызывает GetRow на своём входном потоке зондирования (probe input).
2. Мотод GetRow на Scan возвращает одну строку из таблицы Inventory.
3. hash join выполняет соединение, используя хэш-таблицу.
4. Если строка не соединяется, возвращаемся к шагу 1.
5. Если строка соединяется, возвращаем её в механизм выполнения.
Процесс продолжается пока Scan на probe input возвращает строки. Тогда hash join тоже выходит из своего метода GetRow без производства строки. Когда это происходит, механизм выполнения узнает, что запрос завершен, и вызывает метод Close на hash join, позволяя ему выполнить очистку:
1. hash join вызывает Close на своем probe input.
2. Scan выполняет свои процедуры очистки и возвращает управление hash join.
3. hash join освобождает память своей хэш-таблицы и выходит из метода Close.
Эта построчная обработка (периодические вызовы метода GetNext) и послужила поводом назвать узлы плана запроса итераторами: итерации выполняются на множестве входных строк, возвращая одну строку за раз в родительский процесс.
Выполнение плана стартует из корня и протекает вниз по плану через серию вызовов вложенных методов. Данные вытягивают план в обратном направлении: от листьев к корню, по строке за раз. Планы запросов действительно бегут назад.
То, что делается в методах Open, GetNext и Close зависит от типа итератора и режима, в котором он запущен. Следующая таблица дает обзор работы, выполняемой различными итераторами, когда вызываются эти методы:
Например, Aggregate - это логический оператор, а Stream Aggregate и Hash Aggregate являются физическими операторами. Аналогично, Inner Join - это логический оператор; а Nested Loops - физический. В выводе как графических планов, так XML, указываются эти свойства:
Логические итераторы могут составлять сложные комбинации, чтобы удовлетворить любым требованиям, которые могут быть выражены на языке SQL. Физические итераторы комбинируются, создавая исполняемое дерево, используемое ядром сервера для получения результатов.
Логические итераторы представляют исходный запрос, транслированный в реляционную алгебру; физические итераторы представляют физическую алгебру: конкретные алгоритмы, используемые ядром системы хранения SQL Server и процессором запросов для выполнения логической задачи.
Общий интерфейс и структура
Итераторы являются объектами кода, которые разделяют общий интерфейс методов и свойств. Из них наиболее часто используемыми являются методы получения строк и множеств, извлечение информации о свойствах, получение предполагаемой стоимости, которая используется оптимизатором.
Общие черты (и абстракция структуры) дают возможность легкого расширения при обновлении базы данных и языка. Это также позволяет итераторам быть привязанными к структуре дерева без необходимости для них знать что-либо о подключении других итераторов.
Исполняемый код, который формирует ядро выполнения итераторов, тоже написан так, чтобы избежать жестко привязанных зависимостей между родительскими и дочерними итераторами в дереве плана. Это исключает необходимость перекомпиляции базового кода итератора всякий раз, когда он встраивается в новый план (функциональные указатели).
Все итераторы требуют небольшое количество постоянной памяти для хранения состояния (локальные переменные), когда они выполняются. Эта память формирует часть скомпилированного плана, поэтому не требуется формального выделения памяти при всяком выполнении плана. Кэшированный размер плана включает это распределение памяти.
Общие методы, имеющие наибольшее отношение к нашему обсуждению, относятся к обработке множеств строк. Это методы Open (открыть), GetNext (получить следующий) и Close.
Выполнение плана
Давайте рассмотрим простой план (сам запрос сейчас не важен):
Задавались ли вы когда-нибудь вопросом о том, как выполняется подобный план? Где он стартует, и откуда он знает, где остановиться? Основываясь на линиях и стрелках, которые связывают итераторы в графическом плане, мы можем предположить, что выполнение стартует с производящих данные итераторов (сканирование - scan) и продолжается пока не заканчиваются строки.
Стрелки на соединяющих линиях показывают направление потока данных; между тем, порядок выполнения итераторов совершенно другой. Выполнение запроса всегда начинается с корневого итератора - hash join на диаграмме выше.
Механизм выполнения непосредственно взаимодействует только с этим корневым итератором. Он вызывает метод Open, чтобы подготовить его к возвращению данных, а затем периодически вызывает его метод GetNext, чтобы получать по одной строке вывода запроса. Как только метод GetNext потерпит неудачу при возвращении очередной строки, вызывается метод Close, и выполнение запроса прекращается. Проще не бывает.
Основные курсоры
Хорошо, теперь немного подробней об этом. Давайте посмотрим, что происходит, когда вызывается метод Open на итераторе hash join:
1. hash join вызывает метод Open для построения входа (build input).
2. Метод Open итератора Scan подготавливает ядро системы хранения к началу подачи строк из таблицы Product. Затем управление передается назад в hash join (помним, что он еще выполняет свой метод Open).
3. hash join периодически вызывает метод GetRow на итераторе Scan.
4. Каждый вызов GetRow возвращает одну строку из Scan в hash join. Эти строки используются для построения хеш-таблицы соединения.
5. Как только вызов GetRow на таблице Product сообщает, что строк больше нет, hash join вызывает метод Close на Scan.
6. Итератор Scan выполняет процедуры очистки и возвращает управление hash join.
7. Теперь Hash join вызывает Open на своем своем внутреннем входе (probe input).
8. Итератор Scan на таблице Inventory подготавливает соединение с системой хранения, а затем передает управление hash join.
9. hash join получает возврат от своего метода Open (окончательно), и управление передается механизму выполнения.
Механизм выполнения теперь периодически вызывает GetRow на hash join, возвращая результаты запроса:
1. hash join вызывает GetRow на своём входном потоке зондирования (probe input).
2. Мотод GetRow на Scan возвращает одну строку из таблицы Inventory.
3. hash join выполняет соединение, используя хэш-таблицу.
4. Если строка не соединяется, возвращаемся к шагу 1.
5. Если строка соединяется, возвращаем её в механизм выполнения.
Процесс продолжается пока Scan на probe input возвращает строки. Тогда hash join тоже выходит из своего метода GetRow без производства строки. Когда это происходит, механизм выполнения узнает, что запрос завершен, и вызывает метод Close на hash join, позволяя ему выполнить очистку:
1. hash join вызывает Close на своем probe input.
2. Scan выполняет свои процедуры очистки и возвращает управление hash join.
3. hash join освобождает память своей хэш-таблицы и выходит из метода Close.
Эта построчная обработка (периодические вызовы метода GetNext) и послужила поводом назвать узлы плана запроса итераторами: итерации выполняются на множестве входных строк, возвращая одну строку за раз в родительский процесс.
Выполнение плана стартует из корня и протекает вниз по плану через серию вызовов вложенных методов. Данные вытягивают план в обратном направлении: от листьев к корню, по строке за раз. Планы запросов действительно бегут назад.
Внутри итератора
То, что делается в методах Open, GetNext и Close зависит от типа итератора и режима, в котором он запущен. Следующая таблица дает обзор работы, выполняемой различными итераторами, когда вызываются эти методы:
| Тип итератора | Метод Open | Метод GetNext | Метод Close |
|---|---|---|---|
| Scan/Seek | Открывает соединение с механизмом хранения | Извлекает новую строку из базовой таблицы | Закрывает соединение с механизмом хранения |
| Filter | Открывает дочерний итератор | Вызывает GetNext на дочернем итераторе пока строка не удовлетворит условию фильтра и возвращает эту строку | Закрывает дочерний вход |
| Sort | Размещает рабочую таблицу. Открывает дочерний итератор. Вызывает GetNext для построчного извлечения строк в рабочую таблицу. Закрывает дочерний итератор. Сортирует содержимое рабочей таблицы. | Возвращает следующую строку в отсортированном порядке. | Разрушает рабочую таблицу. |
| Hash Join | Открывает входной поток создания (build input). Проходит все его строки с помощью вызовов GetNext для построения хэш-таблицы. Закрывает build input. Открывает probe input. | Вызывает GetNext на probe input пока не будет найдено совпадение. Возвращает совпавшую строку. | Закрывает probe input. Освобождает память хэш-таблицы. |
| Merge Join (1 ко многим) | Открывает оба дочерних итератора. | Вызывает GetNext на дочернем входном потоке с текущим значением наименьшего ключа пока не будет найдено совпадение. Возвращает совпавшую строку. | Закрывает оба входных потока. |
Обратные ссылки
Нет обратных ссылок
Автор не разрешил комментировать эту запись
Комментарии
Показывать комментарии Как список | Древовидной структурой