ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
33
Каждой записи в столбце сопоставляется ее позиция (номер стро-
ки). В большинстве современных колоночных баз данных значения
столбца упорядочиваются по их позициям [14].
На логическом уровне колоночные и строчные СУБД идентичны,
т. е. способны обрабатывать одни и те же SQL-запросы. Но отличия в
физической организации хранения данных существенно влияют на
реализацию процессов, протекающих при формировании плана вы-
полнения запроса и его реализации.
В строчных СУБД план запроса представляет собой дерево, у
каждого узла которого имеется один родитель и один (или два в слу-
чае пересечения) дочерних узла. Реализация исполнителя планов ба-
зируется на следующих трех базовых парадигмах [15]:
—
синхронный конвейер;
—
итераторная модель;
—
скобочный шаблон.
Синхронный конвейер
.
Суть данного метода состоит в том, что,
как только операция получает очередной кортеж своего результиру-
ющего отношения, она передает его по конвейеру выше стоящей
операции (ОП1—ОП6) для обработки. Например, узел, читающий
записи из исходной таблицы, передает их узлу, выполняющему со-
единение записей разных таблиц.
Итераторная модель.
Эта модель является общепринятым мето-
дом, используемым в СУБД для эффективной реализации синхронного
конвейера. В соответствие с итераторной моделью с каждым узлом де-
рева плана запроса связывается специальная структура управления,
называемая итератором. Интерфейс итератора представлен двумя стан-
дартными операциями с предопределенной семантикой:
—
reset — установка итератора в состояние «перед первым
кортежем»;
—
next — выдать очередной кортеж результирующего отношения.
Алгоритм выполнения плана запроса на базе итераторной модели
изображен на рис. 1. На первом шаге выполняется метод reset примени-
тельно к корневому узлу. Затем в цикле выполняется метод next для
этого же узла. Он каждый раз возвращает указатель на очередной кор-
теж результирующего отношения. В приведенном примере эти кортежи
просто выводятся на экран. Цикл завершается, когда метод next выдает
указатель на специальный кортеж, обозначающий конец файла — EOF
(
End Of File). Методы reset и next родителя прямо или косвенно могут
вызывать соответствующие методы дочерних узлов. Эти вызовы изоб-
ражены на рисунке пунктирными стрелками. Реализация итератора ба-
зируется на скобочном шаблоне, который рассмотрен ниже.
Скобочный шаблон.
Основными атрибутами скобочного шабло-
на являются:
—
выходной буфер, в который помещается очередной кортеж
результата (он может быть прочитан путем вызова родителем метода
next соответствующего дочернего узла);