Обзор внутренних компонентов QHB

Автор:
Эта глава возникла как часть магистерской диссертации Стефана Симковича, подготовленной в Венском технологическом университете под руководством профессора университета доктора Георга Готтлоба (Georg Gottlob) и его ассистентки магистра Катрин Сейр (Katrin Seyr).¹

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

Путь запроса

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

Необходимо установить соединение между прикладной программой и сервером QHB. Прикладная программа передает запрос на сервер и ожидает получения от него результатов.
На этапе синтаксического анализа запрос, переданный прикладной программой, проверяется на предмет корректного синтаксиса, и создается дерево запросов.
Система переписывания принимает дерево запросов, созданное на этапе синтаксического анализа, и ищет любые правила (хранящиеся в системных каталогах), которые будут применяться к этому дереву запросов. Она выполняет преобразования, заданные в телах правил.
Одно из применений системы перезаписи заключается в реализации представлений. Всякий раз, когда выполняется запрос к представлению (т. е. виртуальной таблице), система переписывания переписывает запрос пользователя в запрос, который обращается к базовым таблицам, указанным в определении представления.
Планировщик/оптимизатор берет дерево запросов (переписанное) и создает план запроса, который будет передан на вход исполнителю.
Для этого сначала создаются все возможные пути, ведущие к одному и тому же результату. Например, если по сканируемому отношению есть индекс, существует два способа сканирования. Один — это простое последовательное сканирование, а второй — использовать индекс. Далее оценивается стоимость выполнения каждого пути и из них выбирается самый дешевый. Этот путь разворачивается в полный план, который может использовать исполнитель.
Исполнитель рекурсивно отрабатывает дерево плана и извлекает строки способом, представленным этим планом. Исполнитель сканирует отношения, пользуясь системой хранения, выполняет сортировки и соединения, вычисляет условия отбора и наконец возвращает полученные строки.

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

Как устанавливаются соединения

QHB реализует простую клиент-серверную модель «по процессу на пользователя». В этой модели каждый клиентский процесс подключен ровно к одному обслуживающему процессу. Поскольку мы не знаем заранее, сколько подключений будет сделано, мы должны использовать «процесс-супервизор», который порождает новый обслуживающий процесс каждый раз, когда запрашивается подключение. Этот процесс- супервизор называется qhbmaster и ожидает на указанном TCP/IP порту входящие подключения. Всякий раз, когда обнаруживается запрос на подключение, он порождает новый обслуживающий процесс. Эти обслуживающие процессы взаимодействуют друг с другом и с другими процессами экземпляра СУБД при помощи семафоров и разделяемой памяти для обеспечения целостности данных при одновременном обращении к ним.

Клиентским процессом может быть любая программа, которая понимает протокол QHB, описанный в главе Клиент-серверный протокол. Многие клиенты основаны на библиотеке libpq для языка C, но существует несколько независимых реализаций протокола, например драйвер Java JDBC.

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

Этап синтаксического анализа

Этап синтаксического анализа состоит из двух частей:

Собственно синтаксический анализ, причем анализатор, определенный в gram.y и scan.l, создается с использованием инструментов Unix bison и flex.
Процесс трансформации вносит изменения и дополнения в структуры данных, возвращаемые синтаксическим анализатором.

Синтаксический анализ

Синтаксический анализатор должен проверить строку запроса (которая поступает в виде обычного текста) на допустимый синтаксис. Если синтаксис верен, строится дерево синтаксического анализа, которое передается обратно; в противном случае возвращается ошибка. Лексический и синтаксический анализаторы реализованы с использованием известных инструментов Unix bison и flex.

Лексический анализатор определяется в файле scan.l и отвечает за распознавание идентификаторов, ключевых слов SQL и т. д. Для каждого найденного ключевого слова или идентификатора создается синтаксическая единица, которая передается синтаксическому анализатору.

Синтаксический анализатор определяется в файле gram.y и состоит из набора правил грамматики и действий, которые выполняются всякий раз, когда правило срабатывает. Для построения дерева синтаксического анализа используется код действий (который фактически является кодом C/RUST).

Файл scan.l трансформируется в исходный файл scan.c на языке C с помощью программы flex, а gram.y трансформируется в gram.c с помощью bison. После того, как эти преобразования произошли, для создания синтаксического анализатора можно применить обычный компилятор C. Никогда не вносите никаких изменений в сгенерированные файлы C/RUST, так как они будут перезаписаны при следующем вызове flex или bison.

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

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

Процесс трансформации

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

Причина отделения исходного синтаксического анализа от семантического анализа заключается в том, что поиски в системном каталоге могут выполняться только в рамках транзакции, а нам нежелательно начинать транзакцию сразу после получения строки запроса. Этапа исходного синтаксического анализа достаточно для идентификации команд управления транзакциями (BEGIN, ROLLBACK и т. д.), И их можно выполнить корректно без какого-либо дальнейшего анализа. Как только мы убеждаемся, что имеем дело с настоящим запросом (например SELECT или UPDATE), можно начать транзакцию, если мы еще не находимся в ней. Только тогда можно будет вызвать процесс трансформации.

Дерево запросов, созданное в процессе трансформации, структурно во много похоже на исходное дерево синтаксического анализа, но имеет много отличий в деталях. Например, узел FuncCall в дереве синтаксического анализа представляет собой нечто, синтаксически похожее на вызов функции. Он может быть преобразован в узел FuncExpr или Aggref в зависимости от того, окажется ли функция с указанным именем обычной или агрегатной функцией. Кроме того, в дерево запросов добавляются сведения о фактических типах данных столбцов и результатах выражения.

Система правил QHB

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

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

Планировщик/оптимизатор

Задача планировщика/оптимизатора заключается в создании оптимального плана выполнения. Заданный SQL-запрос (а следовательно, и дерево запросов) на самом деле можно выполнить множеством различных способов, каждый из которых приведет к одному и тому же набору результатов. Если это осуществимо путем вычислений, оптимизатор запросов будет проверять каждый из этих возможных планов выполнения, в итоге выбирая план выполнения, который предположительно будет выполняться быстрее всего.

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

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

Генерирование возможных планов

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

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

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

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

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

Когда значение geqo_threshold превышается, рассматриваемые последовательности соединения определяются эвристически, как описано в главе Генетический оптимизатор запросов. В остальном процесс остается неизменным.

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

Исполнитель

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

Чтобы привести конкретный пример, предположим, что верхний узел является узлом MergeJoin. Прежде чем произойдет какое-либо слияние, нужно извлечь две строки (по одной из каждого подплана). Таким образом, исполнитель рекурсивно вызывает себя для обработки подпланов (он начинает с подплана, добавленного к левому дереву). Новый верхний узел (верхний узел левого подплана) является, скажем, узлом Sort, и, опять же, для получения входной строки требуется рекурсия. Дочерний узел Sort может быть узлом SeqScan, представляющим фактическое чтение таблицы. Выполнение этого узла приводит к тому, что исполнитель извлекает строку из таблицы и возвращает ее вызывающему узлу. Узел Sort будет повторно вызывать свой дочерний элемент для получения всех строк, подлежащих сортировке. Когда входные строки заканчиваются (как сигнализирует дочерний узел, возвращающий вместо строки NULL), узел Sort выполняет сортировку и наконец может вернуть свою первую выходную строку, а именно первую в порядке сортировки. Он сохраняет оставшиеся строки, хранящиеся так, чтобы он мог доставить их в отсортированном порядке в ответ на более поздние требования.

Узел MergeJoin аналогичным образом требует первую строку из своего правого подплана. Затем он сравнивает две строки, чтобы увидеть, можно ли их соединить; если можно, он возвращает соединенную строку вызывающей функции. При следующем вызове, или сразу же, если он не может соединить текущую пару входных строк, этот узел переходит к следующей строке одной таблицы или другой (в зависимости от итога сравнения) и снова проверяет соответствие. В конце концов, строки в одном из подпланов кончаются, и узел MergeJoin возвращает NULL, чтобы указать, что больше нельзя сформировать ни одной строки соединения.

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

Механизм исполнителя используется для вычисления всех пяти основных типов запросов SQL: SELECT, INSERT, UPDATE, DELETE и MERGE. Для команды SELECT узлу исполнителя верхнего уровня нужно только выдавать клиенту каждую строку, возвращенную деревом плана запроса. Команды INSERT ... SELECT, UPDATE, DELETE и MERGE по сути выполняются как SELECT под специальным узлом верхнего уровня плана с именем ModifyTable.

Команда INSERT ... SELECT подает строки в ModifyTable для добавления. Для команды UPDATE планировщик делает так, чтобы каждая вычисляемая строка включала все измененные значения столбцов, а также TID (идентификатор кортежа или строки) исходной целевой строки; эти данные подаются в узел ModifyTable, который использует эту информацию для создания новой измененной строки и пометки старой строки как удаленной. Для команды DELETE единственным столбцом, который фактически возвращается планом, является столбец, содержащий TID, и узел ModifyTable просто использует значения TID, чтобы посетить каждую целевую строку и пометить ее как удаленную. Для команды MERGE планировщик соединяет исходные и целевые отношения и включает все значения столбцов, требуемые для любого из предложений WHEN, плюс TID целевой строки; эти данные подаются в узел ModifyTable, который использует эту информацию, чтобы определить, какое из предложений WHEN выполнить, а затем при необходимости добавляет, изменяет или удаляет целевую строку.

Простая команда INSERT ... VALUES создает тривиальное дерево плана, состоящее из одного узла Result, который вычисляет только одну строку результата и подает ее узлу ModifyTable для выполнения добавления.

Enhancement of the ANSI SQL Implementation of PostgreSQL. Stefan Simkovics. Department of Information Systems, Vienna University of Technology. Vienna, Austria. November 29, 1998.