19 сентября 2019 года    
Четверг | 23:26    
Главная
 Новости
Базы данных
Безопасность PC
Всё о компьютерах
Графика и дизайн
Интернет-технологии
Мобильные устройства
Операционные системы
Программирование
Программы
Связь
Сети
 Документация
Статьи
Самоучители
 Общение
Форум







Разделы / Базы данных / MS SQL Server

Исследование и разработка языковой подсистемы SQL сервера.

Российская Академия Наук
Институт Системного Программирования


На правах рукописи

Кимельман Михаил Леонидович

Исследование и разработка языковой подсистемы SQL сервера

Специальность 05.13.11 - математические и программное обеспечение вычислительных машин, комплексов, систем и сетей.

Диссертация
на соискание ученой степени
кандидата физико-математических наук

Научный консультант:
к.ф.-м.н., доц. С.С. Гайсарян

Москва 1996

Оглавление

0. Введение 31. Организация управления данными 62. Диалект GNU SQL 162.1. Описание данных 162.2. Манипулирование данными 182.3. Встраивание SQL в Си 202.4. Резюме 213. Исполнительная подсистема GNU SQL сервера 223.1. Требования 223.2. Архитектура 233.3. Система команд 254. Компиляция 334.1. Схема компиляции 344.2. Первичные преобразования 374.3. Генерация кода 384.4. Оптимизация 495. Инструментальные средства 515.1. Цели и задачи. 525.2. Kitty 535.3. Выводы. 606. Заключение 617. Литература 62

  1. Введение

Данная диссертационная работа посвящена разработке компилятора SQL свободно распространяемого SQL-сервера [1,2]. Проект свободно распространяемого SQL-сервера входит в число первых проектов, выполняемых в России под эгидой "Фонда свободного программного обеспечения". Целью этого проекта являлось создание мобильной, гибкой, настраиваемой современной системы управления базами данных. С этой точки зрения компилятор языка управления данными должен обеспечивать достаточную гибкость, чтобы быть легко адаптируемым к последующей эволюции как языка, так и подсистемы хранения данных.

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

Актуальность работы определяется прежде всего возрастающими потребностями различных категорий отечественных пользователей в современной многопользовательской реляционной СУБД и практической невозможностью легально приобрести какую-либо качественную зарубежную коммерческую систему по причине чрезмерно высокой стоимости таких систем (по крайней мере для госбюджетных организаций и университетов). Кроме того, в ходе предшествующих проекту исследований, в процессе проектирования системы и ее разработки были применены и развиты наиболее современные методы, выработана технология организации подобных систем и был получен большой практический опыт. Все это может быть с успехом применено в будущих исследованиях и разработках.

В работе получены следующие основные научные результаты:

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

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

Существенными особенностями созданной системы является:

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

В частности хотелось бы отметить:

  • использование компилятором одноуровневого промежуточного представления;
  • протокол взаимодействия с клиентом, позволяющий безболезненно переносить клиентов в не-UNIX среду;
  • "пространство управляющих объектов" - подсистему, ответственную за отображение интерпретируемого кода, его загрузку и редакцию связей.

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

На защиту выносятся:

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

Результаты работы докладывались на конференциях и публиковались в трудах института. [66-69]

Работа состоит из введения, пяти глав, заключения и списка литературы.

Во введении обосновываются цели и задачи данной работы, указываются основные полученные результаты и дается обзор всей диссертации.

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

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

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

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

Пятая глава представляет kitty: инструмент для описания правил трансформации деревьев. Этот программа позволяет встраивать в тексты на Си описания деревьев как просто в виде оператора генерации дерева, так и для сравнения заданного дерева с шаблоном.

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

  1. Организация управления данными

Основным предназначением СУБД является обеспечение эффективного многопользовательского доступа к большим объемам данных. Можно выделить три сравнительно независимые части, вносящие свой вклад в достижение этой цели. Это, во-первых, подсистема хранения данных нижнего уровня, обеспечивающая эффективные формы хранения, размещения и выборки данных из внешней памяти. В случае распределенной базы данных эта же подсистема отвечает также и за эффективное использование копий данных, выбранных с другого компьютера (кэширование, репликация и т.п.). Вторым элементом, влияющим на производительность СУБД, является блок управления и синхронизации транзакций. От того, насколько стратегия, используемая этим блоком, позволяет отразить реальную зависимость транзакций, зависит уровень параллелизма системы на уровне транзакций и, соответственно, ее производительность. И, наконец, последним и наиболее интересующим нас блоком является языковая подсистема, которая должна, в идеале, обеспечивать компактный, выразительный, прозрачный и максимально эффективный доступ к данным, используя все возможности подсистемы хранения данных.

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

С ростом мощности компьютеров стало возможным построение более гибких систем с приемлемым временем ответа. В 80-х годах системы первого поколения были существенно потеснены современным семейством систем, основанных на реляционной модели данных, предложенной в начале 70-х годов Коддом [7]. Эти системы разделяют физические и логические структуры данных, обеспечивают относительную независимость данных и предоставляют декларативный язык запросов к ним. К числу наиболее важных успехов в этой области надо отнести разработку высокоуровневых языков запросов, развитие теории и разработку многочисленных алгоритмов оптимизации запросов, механизмов сериализации транзакций и взаимодействия серверов распределенных СУБД. Обладая теоретической изящностью и простотой, реляционные СУБД обладают рядом ограничений, связанных в основном с обязательностью атомарности значений и недостаточным семантическим уровнем представления данных.

Развивающиеся в настоящее время системы третьего поколения [8-9,20] основываются на существующем фундаменте реляционных систем и двигаются в сторону поддержания сложных структур данных и активных элементов (правил и действий), встроенной оптимизации запросов к распределенным ресурсам, поддержки современных архитектур (внутренний параллелизм в запросах), большей открытости и совместимости как друг с другом, так и с новыми аппаратными платформами и операционными системами.

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

  • представление данных и возможности языка манипулирования данными;
  • возможности, предоставляемые интерфейсом исполнительной системы;
  • контекст - возможности среды, в которой должна функционировать СУБД и архитектура СУБД, т.е. взаимодействие частей системы.
  • баланс компиляция/интерпретация;
  • организация обработки языка;
  • используемые методы оптимизации.
  • Одним из первых проектов экспериментальной реляционной СУБД была проект System R компании IBM, выполнявшийся во второй половине 70-х [10,11]. В нем были опробованы многие базовые идеи этого подхода, являющиеся сейчас стандартными в любой реляционной СУБД. В рамках проекта был разработан язык взаимодействия с реляционной БД SQL (SEQUEL2 [12]), который содержал:

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

    В языке отсутствовали средства синхронизации доступа к объектам БД со стороны параллельно выполняемых транзакций: с самого начала предполагалось, что необходимую синхронизацию неявно выполняет СУБД. Язык предназначался для использования в двух вариантах: в интерактивном мониторе и встроенным в традиционные языки программирования. Поэтому в языке отсутствовали средства ввода/вывода, переменные, операции присваивания и ряд других непременных атрибутов традиционных языков программирования.

    Подсистема хранения данных нижнего уровня (RSS) предоставляла возможности оперирования с тремя базовыми объектами - отношениями, индексами на отношениях и списками кортежей[13]. Отношения можно было сканировать как в порядке хранения, так и в порядке, определяемом индексом. При открытии сканирования указывались условия выборки данных в форме интервала значений для каждого поля отношения. Интерфейс RSS также включал операции модификации и удаления кортежей, создания, удаления и модификации (наращивания) таблиц и индексов и команды управления транзакцией (начало/конец/установка контрольной точки). Любопытной возможностью, введенной позже в систему, была возможность создания кластеризованного индекса (не более одного на таблицу) для сильносвязанных (как правило инженерных) отношений.

    В System R была впервые предложена схема динамической перекомпиляции запросов. Прекомпилятор SQL собирал операторы языка из содержащего их текста прикладной программы (на Cobol'e или PL/1) и заменял их на вызовы библиотеки поддержки. Сами же операторы передавались собственно компилятору, который порождал непосредственно исполняемый код, содержащий вызовы разделяемой библиотеки RSS (Relational Storage System). В случае статической компиляции этот код сохранялся в БД и вместе с них сохранялась информация об объектах БД (таблицах и индексах), от которых этот код зависел и исходные запросы. При изменении или уничтожении каких-либо определяющих объектов код помечался как недействительный и при очередном вызове на исполнение система автоматически организовывала его перекомпиляцию.

    Компилятор SQL System R структурно делился на три части: анализ, оптимизацию и синтез. На фазе анализа выполнялся грамматический разбор операторов и разрешение имен с учетом контекста БД. В процессе оптимизации запрос сначала приводился к до некоторой степени канонической форме. На этом этапе оптимизатор принимал решение о порядке вычисления составляющих запрос блоков (SELECT-FROM-WHERE). Дальнейшая оптимизация состояла в нахождении наиболее эффективной реализации для каждого отдельного блока. Надо заметить, что при этой стратегии некоторые планы запросов не рассматривались никогда, но при этом значительно уменьшалось пространство поиска. В частности, если пользователь писал последовательность вложенных запросов план генерировался в соответствии с указанным пользователем порядком, что далеко не всегда лучший метод. Для реализации соединений рассматривались методы сортировки со слиянием, выборки по индексу и "грубой силы". Оценка стоимости выборки из таблиц осуществлялась на основе статистической информации, предполагавшей равномерность распределения данных. После того, как оптимизатор находил наиболее дешевый метод выполнения блока, происходила генерация детального плана выполнения этого блока. Для представления этого плана использовался Access Specificaton Language[13] - "деревообразный" язык, конструкции которого содержали как полную информацию о выбранных путях выборки данных, так и традиционные для языков программирования управляющие структуры. Единственной особенностью языка были структуры для итерации по таблице и поддержка табличного интерфейса функций, во всяком случае внешнего. Фактически передача основных данных при вызове и, что существеннее, возврате результатов процедур (фактически столбцов сканируемой таблицы) происходила через глобальные переменные. Сами функции были 3-х видов: ScanProc для сканирования таблицы, BuildProc - для построения и заполнения временной таблицы и BuildValueProc - для вычисления значения (агрегатной функции). Последним шагом компиляции была генерация выполняемого кода на основе ASL-представления запроса.

    Построенная как продолжение этого проекта System R* [14,15] - прототип распределенной реляционной СУБД. Эта СУБД не поддерживала фрагментации и репликации данных. Оптимизация выборок в этой системе подробно описана в [16]. Фактически это естественное расширение локальной стратегии с учетом того, что передача параметров (промежуточной таблицы) в данном случае далеко не бесплатно. Надо заметить что стоимость локальной обработки не предполагается несравнимо более высокой, чем стоимость передачи по сети, как этот делалось в SDD-1 [17-19].

    Другим примером ранней реляционной системы является Ingres [21-22], разработанный на рубеже 70 и 80-х годов в Беркли. Эта университетская система изначально была настроена на работу в UNIX'e и не ориентировалась на фиксированную аппаратную платформу. Каждому хранимому отношению соответствовал отдельный файл. Индексы являлись частным случаем отношений. При добавлении или модификации индексируемых данных индексы уничтожались и требовалось явное указание о переиндексации. Первоначально система строилась как набор соединенных через каналы (pipes) процессов:
    Приложение Грамматический Оптимизация, Исполнение
    пользователя разбор Генерация плана

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

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

    Вопрос оптимизации запросов подробно рассматривался в огромном количестве работ [23-25]. В целом можно считать общепризнанной схему четырехшаговой компиляции: преобразование текста запроса в некоторое высокоуровневое внутреннее представление - преобразование к канонической форме с использованием различных законов преобразования (семантическая оптимизация) - выбор возможных низкоуровневых методов для реализации операторов в каноническом представлении запроса - генерация планов выполнения запроса и выбор наиболее дешевого на основе хранимой статистики и формул вычисления стоимости.

    Первая фаза мало чем отличается от аналогичных фаз в традиционных компиляторах. Отличие состоит в подкачке контекста из БД и уровне внутреннего представления. Это представление обычно соответствует дереву (точнее ориентированному графу) запросов, узлы которого представляют операции реляционной алгебры (см. примеры в [26,27]).

    Преобразование запросов, производимое на 2-м шаге, идет в двух направлениях. Во-первых, запросы приводятся в каноническую форму, то есть переписываются так, чтобы они содержали минимальное количество операторов SELECT (соединение-фильтрация-проекция). Философией этого шага можно считать требование: "Везде, где возможно, запрос должен быть приведен к форме единственного оператора SELECT". Это может позволить последующим фазам оптимизации сгенерировать значительно более эффективный (на 2-3 порядка) план выполнения для сложных запросов. Различные варианты такого типа преобразований запросов описаны в [28-39]. Отдельного упоминания заслуживает система правил, предлагаемая в Starburst[26] - экспериментальной управляемой правилами СУБД, созданной в исследовательском центре IBM в Альмадене. Типичными примерами преобразований, выполняемых на этом шаге, является поднятие представлений:
    ( T where cond1 ) where cond2
    T where ( cond1 and cond2),

    преобразования выборок с подзапросами в соединения[D-18.18-]:

    select distinct T.a from T

    where T.b in ( select T1.b

    from T1 where T1.c < T.c)

    select distinct T.a

    from T,T1

    where T.b = T1.b and T1.c < T.c,

    и спуск предикатов ("predicate pushdown"):
    select * from T

    where T.b in ( select T1.b

    from T1 where T1.c < T.c)

    select * from T

    where exist ( select * from T1

    where T.b = T1.b and T1.c < T.c),

    ( A join B) where condA and condB
    (A where condA) join (B where condB).

    Вторым направлением преобразований на этой фазе является преобразование условий выборки. Они переводятся в конъюнктивную нормальную форму, Здесь также производится анализ и упрощение условий выборки, генерация новых простых предикатов и подстановка ограничений целостности вида:
    select * from T

    where T.c < T.b-2 and T.c=3 and T.e=4;

    CHECK( T.e is null or T.b < 7 );

    T.b - integer

    select * from T

    where T.e=4 and T.c=3 and T.b = 6

    Следующий шаг компиляции по традиционной схеме предполагает выбор возможных методов для реализации реляционных операторов, т.е. проекции, соединения и агрегирования. Типичный набор применимых стратегий включает метод "грубой силы", выборка по индексу, выборка с использованием хэш-функции, слияние (если необходимо, то с сортировкой) и слияние с построением хэш-функции [28]. С учетом имеющейся информации о наличие индексов и размещении данных формируются наборы применимых для реализации заданных операций методов с соответствующими параметрами. Здесь же рассматривается возможность выборки данных из индекса, частичной сортировки, а также разные схемы удаления дубликатов. В случае фрагментации данных (когда части отношения хранятся в различных местах - в общем случае на различных компьютерах сети) запрос на выборку данных из таблицы расщепляется на группу параллельно выполняемых запросов [21]. Вопросы эффективной фрагментации в свете параллельных баз данных рассматриваются в [41]. В случае распределения данных в сети в число организационных операций необходимо включать сетевые пересылки, если конечно их стоимость не предполагается неоценимо высокой.

    Последняя фаза обработки запросов - генерация всевозможных планов выполнения запроса и выбор наиболее дешевого. Ключевыми моментами здесь является количество рассматриваемых планов и оценка стоимости. Задача нахождения оптимального плана является задачей на полный перебор. При этом с ростом числа отношений, участвующих в запросе, число вариантов и время перебора растет экспоненциально и может превысить время выполнения запроса. Для ускорения поиска используется разные эвристики. Разработчики System R сужали пространства поиска, рассматривая выборки из блоков Select-From-Where независимо. Этот же метод используют иногда и в постреляционных системах, в которых процедуры выборки могут использоваться рекурсивно. В университетском INGRES'e используемая техника декомпозиции запросов приводила к тому, что к этому шагу большая часть вариантов уже отсеивалась. Одним из первых шагов коммерческого INGRES'а [22] стало изменение этой стратегии так, чтобы перебирать все возможные варианты. Это было оправдано для большинства запросов, используемых в коммерческих системах. В остальных случаях пространство поиска ограничивалось по времени - как только время оптимизации превышало оценку времени выполнения запроса, оптимизация прекращалась и найденный к тому моменту результат признавался приемлемым. Кроме вышеперечисленных используются различные варианты динамического ограничения пространства поиска по мере нахождения все более оптимальных планов и все более раннего отсечения неоптимальных.

    Формулы оценки стоимости выполнения каждой из низкоуровневых операций опираются на данные об размерах сканируемого отношения и результата. Для оценки размера промежуточных отношений используется статистическая информация о распределении данных, на основании которой делаются выводы о селективности использованных при сканирования предикатов. Как правило в основе статистических оценок лежит предположение о независимости распределения данных в столбцах отношения. Статистические данные для отношения обычно включают количество записей, занимаемых страниц памяти, а также распределение данных в столбцах таблицы. Распределение может быть представлено как просто максимальным и минимальным значениями (и предположением о равномерном распределении) в System R, так и гистограммой, как это сделано в коммерческом INGRES'e. Сбор статистических данных также проводится как "на лету", так и отдельными утилитами.

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

    Практически во всех коммерческих реляционных СУБД сегодня реализован SQL[42-46]. Все фирмы провозглашают соответствие своей реализации стандарту SQL, и на самом деле реализованные диалекты SQL очень близки. Вариации в языке касаются поддержки триггеров и правил, наличия механизма хранимых процедур, представления сложных структур данных и ряда других элементов, дискутируемых в драфтах очередной версии стандарта SQL.

    Принятый в 1989 г. [42] Международный Стандарт SQL во многих частях имеет чрезвычайно общий характер и допускает очень широкое толкование. В этом стандарте полностью отсутствуют такие разделы, как манипулирование схемой БД и динамический SQL. Многие существенные аспекты языка в соответствии со стандартом определяются в реализации. В марте 1992г. был выработан окончательный проект стандарта SQL2 [43]. Этот стандарт существенно более полный и охватывает практически все необходимые для реализации аспекты: манипулирование схемой БД, управление транзакциями и сессиями (сессия - это последовательность транзакций, в пределах которой сохраняются временные отношения), подключение к БД, динамический SQL. Cтандартизованы также отношения-каталоги БД, которые хотя и не связаны с языком непосредственно, но сильно влияют на реализацию. Предполагается, что SQL3 будет содержать механизм триггеров и возможность использования абстрактных типов данных. Принятие стандарта планировалось в 1995 г.

    Несколько последних лет идут также работы по стандартизации межпрограммного интерфейса СУБД. Наиболее известными сейчас являются предложенные соответственно Microsoft и Borland протоколы ODBC и IDAPI. Sybase предлагает в качестве стандартной свою архитектуру Open Client и Open Server. Весьма перспективным, хотя и не относящимся исключительно к базам данных, является стандарт CORBA [47], разработанный OMG. Пока ни одно из этих предложений не стало фактическим стандартом, но круг рассматриваемых вариантов уже очерчен.

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

    Хотя поставщики популярных реляционных СУБД делали попытки перенести их под MS-DOS, ничего путного из этого не вышло. На сегодня стандартным окружением для современной СУБД можно считать UNIX, точнее совокупность стандартов открытых систем из него вышедших.

    На сегодняшний день стандартным набором требований СУБД к окружению можно считать: a) поддержку многозадачности и множественных нитей управления; b) средства разделения памяти, очередей сообщений, а также сетевого взаимодействия на уровне не ниже socket'ов (а лучше RPC - удаленного вызова процедур); c) стандартный интерфейс к аппаратуре (поддержка эффективного доступа на аппаратном уровне сейчас не популярна ввиду таких средств, как дисковые массивы).

    Компиляция и выполнение операторов SQL - по крайней мере в рамках одной транзакции - позволяет разделить практически любая из промышленных систем. Любопытным исключением из этого правила является пример компилятора СУБД Informix, который заменяет каждый оператор встроенного SQL на динамический вызов компилятора со строкой, содержащий исходный замещаемый оператор, так что описав курсор внутри цикла вы будете компилировать это описание на каждом шаге.

    Задачи СУБД современной формации рассматривались в нескольких статьях. Помимо отдельного взгляда компании Microsoft, отраженного в статье Д.Васкевича [57], в целом авторы сходятся в том, что находящееся в фокусе исследований новое поколение СУБД должно обеспечивать поддержку сложных структур данных, выполнение правил, быть адекватным новым моделям данным (в частности темпоральной) и обеспечивать эффективный поиск по ним (например поиск 10 прямоугольников, ближайших к данному). Используемые в этих системах алгоритмы должны быть масштабируемы для эффективной обработки объемов данных, превосходящих имеющиеся сейчас на несколько порядков величины, и должны обеспечивать близкое к линейному ускорение. Требуется найти эффективные и не требующие излишнего пространства механизмы управления версиями и конфигурациями (сборками). Весьма актуальной является задача объединения существующих разнородных баз данных в единую среду подобно телефонной сети. В свете этих задач выдвинуто несколько подходов к построению постреляционных систем.

    Направление объектно-ориентированных БД, зародилось еще в начале 80-х на основе работ в области БД и развивающегося направления языков программирования с абстрактными типами данных и объектно-ориентированных языков программирования. Возникшие прежде всего как ответ на требования сложных информационных прикладных систем, ООБД претендовали на то, чтобы со временем вытеснить реляционные системы также, как реляционные системы вытесняли системы первого поколения. Попытка изложить основные положения этого подхода была сделана в 89 году в манифесте ООБД [9,48,49]. К настоящему времени создано значительное количество экспериментальных и даже несколько коммерческих систем [55,56]. Несмотря на это общего согласия об объектной модели до сих пор не выработано.

    Языковая среда этого класса систем представляет собой традиционный (как правило) объектно-ориентированный язык программирования, включающий поддержку хранимых (persistent) объектов. Доступ к объектам осуществляется как спецификацией пути (вида var.f1.f2), так и с помощью встроенных тем или иным способом запросов. Большая часть серверов таких БД являются серверами страниц, а идентификаторы объектов фактически представляют адреса в смысле БД. В случае обращения к еще не выбранным данным клиентская система обращается к серверу страниц. В остальном схема действий очень напоминает работу с виртуальной памятью - одна из систем на основе EXODUS [50,54] именно ею и пользовалась.

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

    Другим подходом являются системы "следующего поколения". Идея этого подхода выражена в [8] и основывается на трех принципах. СУБД третьего поколения:

    • помимо традиционных услуг по управлению данными обеспечат поддержку более богатых структур объектов и правил.
    • должны включать в себя СУБД второго поколения (непроцедурный доступ и независимость данных)
    • должны быть открыты для других подсистем (4Gl, инструменты поддержки принятия решений, доступ из многих языков программирования, lotus 1-2-3, и т.п.).

    Сторонники этого направления придерживаются эволюционного принципа развития. Системы этого направления являются прямыми наследниками реляционных систем. Языком общения этих систем предполагается расширенный соответствующими свойствами SQL. Хотя в этом варианте язык выглядит явно перегруженным, это лучшее, что есть в этой области. Сторонники этого направления предлагают свой подход к построению объектно-ориентированных систем, при котором, в частности, вопросы выборки данных по "OID" (идентификаторам объектов) будут скрыты от пользователя и могут быть, в свою очередь, реализованы через служебное отношения вида (Oid,DBpointer). Одним из наиболее известных представителей этого направления является СУБД Postgres [51-53]. Она поддерживает темпоральную модель хранения данных, мощный механизм ограничений целостности, допускает хранение абстрактных типов данных и наследование. В последней версии системы язык запросов PostQuel заменен на диалект SQL.

    В целом представляется осмысленным придерживаться направления систем "следующего поколения". Единственной реальной возможностью для нас была опора на Стандарт SQL'89 с необходимыми уточнениями и расширениями. Ориентация на использование языка Си в качестве основного (и на первых порах единственного) языка со встроенным SQL позволила в первой версии системы ограничиться поднабором типов, определяемых стандартом, которые соответствуют базовым типам данных языка Си. В целом при формировании реализационного диалекта SQL руководствовались следующими требованиями:

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

    1. Диалект GNU SQL

    Как уже было сказано, диалект данной реализации описывает SQL, рассчитанный на встраивание в Cи, и использует ASCII-совместимый набор символов. Диалект допускает использование величин с типами, адекватными базовым типам Си, а также строк переменной длины. Операции определения данных позволяют создавать и удалять отношения и представления, а также передавать права на операции с ними другим пользователям. Поддерживаемые средства ограничения целостности могут блокировать ввод неопределенных значений и задавать на отношениях ограничения уникальности. Допускается также задание проверочных ограничений на таблице (условий, которые должны выполняться для каждой из строк) и ограничений целостности по ссылкам.

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

    Диалект предполагает работу в среде UNIX. Из нее берется идентификатор полномочий (имя пользователя) и имя модуля, ассоциируемого с данной программой на Си со встроенным SQL. Последнее формируется как имя файла, содержащего эту программу, квалифицированное именем пользователя.

    Явные операторы подключения к базе данных (CONNECT) диалектом в данной версии не поддерживаются. Подключение выполняется автоматически к указанному при компиляции серверу SQL. В качестве имени сервера SQL используется сетевое имя компьютера, на котором установлен сервер.

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

    Рассмотрим эти вопросы более подробно.

    1. Описание данных

    Элементами данных, которыми манипулирует SQL, являются константы (числа и строки), параметры (переменные объемлющего языка - Си), столбцы, таблицы и пользовательские схемы. Идентификаторы, которые используются для их именования, могут быть либо идентификаторами в традиционном виде ([A-Za-z][A-Za-z0-9]*, например A0z9), либо быть заданными в виде строки в двойных кавычках ("Это тоже Идентификатор"). При этом переменные объемлющего языка (Си), должны также удовлетворять и правилам именования переменных в языке. Никаких ограничений на длину идентификаторов переменных объемлющего языка и параметров процедур диалект SQL не накладывает. Хранимые же идентификаторы, то есть имена таблиц, столбцов, схем (пользователей), процедур и модулей, не должны превышать 18 символов. Строки SQL ('ограничиваются одинарными кавычками') могут содержать любые символы из используемого набора. Сортировка строк производится в соответствии с кодами символов (поэтому использование koi-8 не всегда будет приводить к желаемым результатам).

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

    1. Типы данных

    Диалект поддерживает в качестве базовых типов только те, которые можно напрямую отобразить в типы языка Си. Кроме того, обеспечивается частичная поддержка типа SQL FLOAT - вместо него подставляется тип C float или double в зависимости от требуемой точности. Если требование к точности задано слишком высоким (тип double ее не обеспечивает), то генерируется сообщение об ошибке. Также обрабатывается и тип SQL DECIMAL в случае, когда шкала равна 0. Этот тип заменяется аналогичным образом на short или long. Значения даты и времени равны соответственно числу дней с 1 января 1970 и числу миллисекунд после полуночи. Тип DATETIME отображается в структуру, содержащую оба этих значения.

    1. Манипулирование схемой и поддержка целостности

    Схемой пользователя называется совокупность всех хранимых в БД объектов данного пользователя: таблиц, представлений, модулей (набор скомпилированных операторов SQL, соответствующих одной пользовательской программе) и триггеров. Фактически схема создается, когда создается первый принадлежащий данному пользователю объект. Оператор CREATE SCHEMA сам по себе ничего не создает, а только задает контекст (идентификатор полномочий по умолчанию) для вложенных в него операторов создания таблиц и представлений.

    При создании таблицы (оператор CREATE TABLE) задаются имя таблицы, описания столбцов и применяемые к данной таблице ограничения целостности. Столбцы специфицируются именем и типом, а также необязательным значением по умолчанию. В диалекте допускаются ограничения целостности трех видов: на уникальность, по ссылкам и проверочные ограничения. Каждое ограничение на уникальность и по ссылкам фактически соответствует созданию индекса (в первом случае уникального). В случае ограничений по ссылкам требуется также, чтобы в ссылаемой таблице на соответствующий набор столбцов существовало ограничение уникальности. Выполнение ограничений на уникальность и проверочных ограничений проверяется при каждом изменении строки из данной таблицы. Проверка корректности ссылок выполняется при изменении строки в данной или в ссылаемой таблице. Для каждого проверочного ограничения и ограничения целостности по ссылкам в БД создается соответствующий триггер. Его единственной функцией является проверка этого ограничения и откат в случае необходимости оператора SQL, вызвавшего нарушение целостности. Диалект не поддерживает явного описания триггеров.

    При модификации таблицы (оператор MODIFY TABLE) возможно только добавление столбцов и/или ограничений целостности. Удаление таблицы (оператор DROP TABLE) допускается лишь при отсутствии ссылок на нее.

    Диалект поддерживает также механизм представлений, то есть именованных запросов, к которым можно обращаться как к таблицам.

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

    1. Контроль доступа к данным

    Любой пользователь может создавать объекты с любым, не обязательно совпадающим с его собственным, идентификатором полномочий. Изменять же или удалять эти объекты может только их владелец. При создании объекта БД владелец обладает правами на все операции с этим объектом. Остальные пользователи изначально не могут производить с ним никаких операций. В дальнейшем пользователь может передавать права (оператор GRANT PRIVILEGES) на часть или все операции с объектом, включая права на транзитивную передачу прав. Диалект также позволяет отменить (оператор REVOKE PRIVILEGES) переданные другому пользователю полномочия. При этом полномочий будут лишены и пользователи, получившие эти права транзитивно.

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

    Операций с полномочиями на модули и триггеры диалект не предусматривает.

    1. Манипулирование данными

    В части манипулирования данными диалект поддерживает стандартный набор операций.

    1. Выборка данных

    Выборка данных выполняется с помощью запросов. Они содержат спецификации таблиц и условия выборки данных, а также операции группирования и агрегатные функции. Условия выборки данных могут включать предикаты сравнения, существования, включения, проверки неопределенных значений и соответствия строк шаблону.
    select * from T
    where exist ( select * from T1 where T.b = T1.b and T1.c < T.c),

    select count(distinct T.b) from T
    where T.b > 5 and T.a < :a
    group by T.c ;

    В случае предиката сравнения выражения с неквантифицированным подзапросом результат подзапроса должен быть значением - числом или строкой - но не таблицей и не кортежем со множеством столбцов.
    select * from T
    where T.b = ( select T1.b from T1 where T1.c < T.c);

    В операциях запроса допускается специфицировать более одной таблицы для выполнения соединений. Результаты операций запросов можно объединять, удалять дубликаты и сортировать в одном из двух направлений (если вы выбираете данные с использованием курсора).

    (select * from T where T.a = 3 ) union ( select * from T where T.c = 2);

    (select * from T where T.a = 3 ) union all ( select * from T where T.c = 2);

    Для получения выборки, состоящей из одной строки, используется оператор SELECT.

    Char name[50];
    int birthday;
    exec sql
    select "ФИО", "г/р"
    from person
    into :name, :birthday
    where person.passport_ID = :id ;
    printf(" ФИО='%s' д.р.=%d \n",name,birthday);

    В случае, когда выборка содержит более одной строки, используются курсоры, для работы с которыми существуют 4 оператора: 'DECLARE CURSOR', 'OPEN', 'FETCH' и 'CLOSE', которые, соответственно, объявляют, открывают, выбирают данные (по одной строке за обращение) и закрывают курсор.

    Char name[50];
    int birthday;
    $ declare cursor c1 for
    ( select "ФИО", "г/р"
    from person
    where person.passport_ID = :id
    )
    order by 2 ;
    $ open c1;
    $ whenever not found goto exit;
    while(1) {
    $ fetch c1 into :name, :birthday ;
    printf(" ФИО='%s' д.р.=%d \n",name,birthday);
    }
    :exit
    $ close c1;

    1. Добавление, удаление и модификация данных

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

    Модификация и удаление строк таблицы выполняются операторами UPDATE и DELETE соответственно. Каждый из этих операторов имеет 2 формы. В одном случае операция выполняется для каждой строки таблицы, удовлетворяющей указанному в операторе условию. В другом действие выполняется над строкой, на которую позиционирован курсор.

    1. Управление транзакциями

    Транзакция открывается при выполнении в приложении первого оператора SQL. Изменения БД, производимые в течение данной транзакции, фиксируются оператором 'COMMIT WORK'. Для отката транзакции используется оператор 'ROLLBACK WORK'. Оба они завершают транзакцию. В случае фатального завершения приложения неявно вызывается оператор 'ROLLBACK WORK'.

    1. Встраивание SQL в Си

    Каждый оператор SQL начинается со стоящих в новой строке ключевых слов 'EXEC SQL' или просто одиночного '$', а заканчивается ';'. В SQL-коде переменные языка Си предваряются ':'. Компилятор SQL, встроенного в Си, не производит никакого типового контроля для переменных Си - он только генерирует подстановки, которые приведут к ошибкам на фазе компиляции порожденного Си-кода, если переменные Си не соответствуют предполагаемым СУБД типам.

    Для связи СУБД и приложения также используется специальная структура gsqlca (sql communication area), содержащая поля 'sqlcode' (оно также имеет макро псевдоним SQLCODE) и 'errmsg'. В первом из них содержится код возврата оператора SQL, а во втором - текст сообщения об ошибке, если таковая произошла. Значение SQLCODE равное 0 соответствует успешному выполнению оператора, 100 - обнаружению конца таблицы при выборке данных по курсору, а значения меньшие 0 - ошибке при выполнении. Оператор WHENEVER задает стандартную реакцию последующих (текстуально) операторов на ошибки или конец сканирования:

    $ whenever not found continue;

    $ whenever sqlerror goto exit;

    1. Резюме

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

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

    1. Исполнительная подсистема GNU SQL сервера

    Исполнительная подсистема GNU SQL сервера базируется на работе, начатой в рамках проекта кластерной операционной системы [58-60] и исходно ориентированной на то, чтобы обеспечить основу реляционной СУБД в среде этой операционной системы. Впоследствии уже в рамках проекта GNU SQL-сервера подсистема управления данными и транзакциями кластерной операционной системы (далее ПУДТ[61-64]) была перенесена в среду ОС UNIX и доработана. Функции ПУДТ включают синхронизацию транзакций, управление хранимыми данными, восстановление после сбоев и т.д. Помимо ПУДТ, исполнительная подсистема включает интерпретатор, который является ее верхним уровнем и ответственен за вызов функций ПУДТ и организацию сложных запросов.

    Далее в главе рассматриваются

    • требования к исполнительной системе со стороны языка;
    • архитектура SQL-сервера, схема компиляции и выполнения операторов SQL;
    • функции ПУДТ или низкоуровневая поддержка языка;
    • интерфейс исполнительной подсистемы или "То, Что Должен Генерировать Компилятор".
      1. Требования

    Говоря о требованиях к исполнительной подсистеме реляционной БД, надо заметить, что имеются два набора требований. Первые из них касаются непосредственной поддержки конструкций языка SQL. Вторые же в языке практически не упоминаются, но их наличие жизненно необходимо для функционирования СУБД. К первой группе относятся в основном вопросы манипулирования данными. Ко второй - сериализации транзакций, восстановление после сбоев, администрирование и т.п. Глядя на исполнительную машину сервера реляционной БД, нетрудно видеть, что подсистема хранения данных (в нашем случае ПУДТ), выполняя много полезных, но невидимых для языка функций, обеспечивает лишь простейший доступ к данным. Все сложные действия (вычисление сложных условий, соединений, подзапросов, использование механизма временных таблиц и т.п.) должны организовываться на более высоком уровне. Мы будем обсуждать здесь, за редким исключением, только те требования, которые относятся к первой группе и наибольшим образом влияют на интерфейс исполнительной подсистемы.

    Для реализации операторов SQL необходим хотя бы минимальный поддерживающий операции SQL набор функций подсистемы хранения данных. Он включает:

    • создание и удаление отношений (creattab/droptab);
    • создание и удаление индексов (creatindex/dropindex);
    • создание и удаление временных отношений (creattmptable/droptmptable)
    • операции открытия сканирования в естественном порядке и по индексу, выборки очередной строки и закрытия сканирования (openscan / nextrow / readrow / findrow / closescan);
    • добавление, модификация, удаление строки отношения (insert-modify-delrow)
    • фиксация и откат транзакции (rollback/commit);
    • сортировка таблиц

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

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

    Помимо всего перечисленного, исполнительная подсистема должна быть легко переносима на новые платформы и быть легко адаптируемой к распределенной работе в сети.

    1. Архитектура

    Система предназначена для работы в распределенных открытых UNIX-подобных системах и следует архитектуре "клиент-сервер". Можно выделить два слоя процессов БД. Внутренний слой представляет собой группу процессов ПУДТ. Они предоставляют сервисы Синхронизатора, Логического Журнала (модификаций логического уровня), Микрожурнала (журнал микроопераций), Буфера (обмены с диском, захваты буферов) и Сортировщика. Кроме них в ПУДТ входят утилиты восстановления от сбоев и модули транзакций. Последние являются библиотекой и реализуют внешний интерфейс подсистемы на уровне вызовов функций. Взаимодействие процессов в этом слое осуществляется с помощью обменов сообщениями и разделяемой памяти.
    Рисунок 1 Структура процессов системы

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

    Клиентская часть системы, находящаяся на любом из компьютеров сети, состоит из программы компилятора-клиента и библиотеки, содержащей клиентскую часть интерпретатора. Для работы клиентской части необходимо, что бы среда поддерживала механизм удаленного вызова процедур (RPC)[70].

    Клиентская часть компилятора ответственна за выделение чистого SQL текста и передачу его на обработку основной части компилятора на стороне сервера. После обработки клиент получает программу на чистом Си, в котором SQL-код заменен на вызовы runtime библиотеки клиентской части интерпретатора запросов, и соответствующий данной программе пользователя интерпретируемый код, сохраненный в базе данных. При выполнении программы серверу интерпретатора помимо параметров оператора SQL будут переданы ссылки на ранее скомпилированный и хранящийся в БД код. По ним интерпретатор извлечет этот код из БД и выполнит его, обращаясь с соответствующими параметрами к подсистеме управления данными и транзакциями.

    Решение об использовании специального интерпретируемого языка без формирования представления операторов SQL в машинных кодах было принято главным образом в целях увеличения мобильности и надежности системы. В силу того, что при выполнении программ может потребоваться динамическая компиляция и подгрузка кода (триггеров) из БД с последующим немедленным связыванием с уже работающим кодом, невозможно использовать стандартные загрузчики. Это значит, что для каждой пары "процессор - операционная система" необходимо было бы дописывать значительный блок. Если же учесть, что в процессе разработки системы мы сменили 4 аппаратных платформы, то становится ясна полная нереалистичность подобного подхода в наших условиях. Более того, большая часть времени тратится вовсе не на интерпретацию кода, а на выборку данных и, в меньшей степени, анализ пересчитываемых условий. Поэтому данное решение не может значительно сказаться на производительности системы.

    1. Система команд

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

    • предельно компактной (команда вводилась, только если была абсолютно необходима или значительно повышала эффективность);
    • емкой (если мы обнаруживали часто повторяемую последовательность команд, она заменялась на одну единственную команду)
    • адекватной набору низкоуровневых операций доступа к БД (ПУДТ) и легко адаптируемой к изменениям в нем;

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

    1. Модули и динамическое связывание

    Реализация ограничений целостности (они же триггеры) и операторов динамического SQL, требует раздельной компиляции кода и связывания сегментов кода при выполнении. Для решения этих задач (динамического загрузки и редакции связей) была написана библиотека "пространства управляющих объектов", схема которого похожа на общепринятую сейчас в ЭВМ схему сегментно-страничной адресации.

    Используется принцип деления на "сегменты" (segments), соответствующие независимо компилируемым и, как правило, слабо связанным частям программы (фактически объектным модулям), и составляющие каждый сегмент связанные в список "страницы" (pages) разных длин. В случае с программами для интерпретатора сегментам соответствуют модули таких программ, в страницах же хранятся программы для работы с отдельными операторами ("основные процедуры", вызываемые при обращении к интерпретатору), и вспомогательные процедуры, которые могут быть вызваны только с помощью специальных команд самого интерпретатора.

    Для доступа к объектам в сегментах используются виртуальные адреса, состоящие из двух зон: старшие биты соответствуют номеру сегмента (для внутрисегментной адресации используется значение "0"), остальные - смещению в сегменте.

    Для настройки межсегментной адресации используется таблица перемещаемых адресов (relocation table), ассоциируемая с каждым сегментом, и список экспортируемых имен с соответствующими им перемещаемыми адресами для разрешения внешних ссылок.

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

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

    1. Арифметика и управление

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

    • логическим операциям (AND,OR,NOT);
    • предикатам сравнения ('<','>','=','<>','>=','<=');
    • предикату сравнения строки с шаблоном (like);
    • предикату Exist - (практически все подзапросы приводятся к этому виду;
    • арифметическим операциям ('+','-','*','/');
    • полученным вне данного дерева значениям (т.е. столбцам, параметрам оператора SQL - переменным Си -, величинам, полученным в результате каких-либо предшествующих вычислений, коду состояния SQLCODE и, наконец, просто константам);
    • вызову функции (несмотря на отличие в формате, узел полностью эквивалентен описанной ниже команде вызова подпрограммы);
    • специальному узлу формирования маски изменений (как правило удается обойтись единственным таким узлом в корне каждого дерева - но в принципе это позволяет решить проблему отслеживания зависимостей от слишком большого числа меняющихся элементов - таблиц, столбцов, параметров).

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

    Store(address to store, tree to compute) - вычисление значения дерева и помещение результата по указанному адресу.

    Jmp(address) - безусловный переход

    Jif(address, cond) - условный переход. Если при вычислении дерева, на которое указывает cond, будет получено истинное значение, переход будет выполнен. В случае ложного или неопределенного значения условия выполнение продолжится со следующего оператора.

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

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

    Call(objptr, entry, inptr, outptr, exit) - вызов подпрограммы. 'objptr' здесь адрес объекта. Код entry используется для подпрограмм с сохранением состояния, реализующих выборку данных. В таких случаях вход 0 используется, как правило, для инициализации выборки, вход 1 - для выборки очередной строки, а вход 2 - для возвращения в исходное состояние. Параметр 'inptr' задает ссылку на массив ссылок на входные параметры. Параметр 'outptr' задает ссылку на массив ссылок на выходные параметры. Exit - адрес перехода по окончании сканирования (entry=2, код возврата -100). При выполнении команды Call происходит копирование входных параметров по указанным в описателе вызываемого объекта адресам в соответствии с указанными там же типами. При возврате управления (если код возврата 0) происходит аналогичное копирование в обратном направлении для возвращаемых параметров.

    Return(code) - возврат из подпрограммы, на верхнем уровне возврат из интерпретатора. 'code' является кодом возврата и сохраняется в SQLCODE.

    Suspend(entry,code) - возврат из подпрограммы с запоминанием точки выхода. При последующем вызове этого объекта с входом 'entry' выполнение будет продолжено с этого адреса. 'code' является кодом возврата и сохраняется в SQLCODE.

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

    1. Операции доступа к БД

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

    Операции, связанные с изменением схемы БД:

    • создать постоянное или временное отношение;
    • создать фильтр (объект, содержащий набор идентификаторов кортежей отношения - правда в отличие от самого отношения этот набор содержит, в осмысленных случаях, идентификаторы далеко не всех кортежей);
    • создать индекс;
    • уничтожить временный объект;
    • уничтожить постоянное отношение;
    • уничтожить индекс.

    Операция изменения схемы отношения:

    • добавить поля к существующему отношению.

    Операции сканирования отношения. Имеется три способа сканирования отношения:

    • последовательное сканирование в порядке, предопределенном ПУДТ;
    • сканирование отношения в порядке, задаваемом каким-либо из индексов, заданном на этом отношении;
    • сканирование отношения в порядке, задаваемом существующим на этом отношении фильтром.

    Для синхронизации транзакций в ПУДТ используется метод предикатных захватов. Поэтому при открытии сканирования указывается также набор предикатов сканирования, задаваемых в виде "константа<=столбец<=константа". Эти условия служат и для первичной фильтрации данных.

    С открытым сканом можно выполнять следующие операции:

    • найти следующий кортеж;
    • выбрать из текущего;
    • запомнить текущую позицию сканирования;
    • сделать запомненную позицию текущей;
    • удалить кортеж, задаваемый текущей позицией сканирования;
    • модифицировать кортеж, задаваемый текущей позицией сканирования;
    • закрыть сканирование.

    В набор "макро"-операций входят следующие операции:

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

    Операция вставки кортежей в отношение:

    • вставить кортеж.

    Сортировка и теоретико-множественные операции над отсортированными временными объектами:

    • отсортировать временный объект.

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

    Операции управления прохождением транзакций:

    • установить контрольную точку;
    • откатить транзакцию до указанной контрольной точки.
    • Операция завершения транзакции:
    • завершить транзакцию.

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

    На основе этих операций построены следующие команды интерпретатора:

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

    AlterTab(TblId,NewClmsInfo) - модификация структуры постоянного отношения: добавление новых столбцов и индексов; занесение информации о них в системные таблицы и регистрация в системе (опять же запись в системные таблицы) дополнительных триггеров; все это сопровождается проверкой правомочности каждого из шагов.

    CreatTmp() -> TblId - Создание временного отношения.

    Open(TblId,Scond,clist) -> Scan - Открытие сканирования отношения в порядке, определяемом ПУДТ, по столбцам, перечисленным в списке clist. Параметр 'SCond' задает набор простых предикатов сканирования, используемых как для захватов, так и для предварительной фильтрации. Этот параметр может быть задан в двух видах. Один из них полностью подготавливается компилятором в случае только константных предикатов в форме, требуемой функциями ПУДТ. Во всех прочих случаях этот параметр представляется в виде обычного дерева, которое преобразуется интерпретатором при каждом вызове к требуемому функциями ПУДТ виду.

    Open(IndId,Scond,clist) -> Scan - Открытие сканирования отношения в порядке, определяемом заданным индексом. В данном случае условие сканирования тоже может содержать предикаты захвата на любой столбец сканируемой таблицы, но ограничения на столбцы, входящие в индекс, обрабатываются существенно эффективнее, чем в предыдущем случае.

    Open(FltId,Scond,clist) -> Scan - Открытие сканирования отношения в соответствии с заданным фильтром (фильтр создается заранее).

    InsRow(Tid,values) - добавление строки в отношение.

    InsertScаn(Tid,Scan) - добавление в заданное отношение строк выборки по заданному скану (допускается проекция и фильтрация по простому условию, то есть группе ограничений вида "столбец-операция сравнения-константа).

    FindRow(Scan,direction,rlist) -> values - выборка из отношения очередной строки и запись значений в указанные в списке rlist адреса. (параметр направления выборки, необходимый для поддержки SQL2, введен лишь формально для дальнейшего развития - сейчас эта операция не поддерживается нижним уровнем ПУДТ).

    ReadRow(Scan,clist,rlist) -> values - выборка из текущей строки значений заданного набора столбцов из текущей строки сканирования.

    ModRow(Scan,clist,values) - модификация значений части столбцов в текущей строке сканирования; непосредственно перед вызовом операции модификации строки ПУДТ считывается предыдущее значение столбцов и активизируются все относящиеся к делу триггеры, при этом в качестве параметров им передаются старые и новые значения модифицируемых столбцов; в случае успешного завершения работы триггеров (они могут в свою очередь инициировать обновления других строк) новые значения записываются в базу данных.

    DelRow(Scan) - удаление текущей строки сканирования; непосредственно перед вызовом операции удаления строки ПУДТ активизируются все относящиеся к делу триггеры, при этом в качестве параметров им передаются значения столбцов удаляемой строки; в случае успешного завершения работы триггеров (они могут в свою очередь инициировать удаления или модификации других строк) строка действительно удаляется.

    Close(Scan) - закрытие скана.

    SORT(Tid,clist,<distinct>) - сортировка отношения с возможным удалением дубликатов.

    MKGROUP(Tid,grplist,funclist) - группирование заданной таблицы и вычисление значений требуемых функций для каждой группы.

    DropTmp(tid) - уничтожение временного объекта.

    DropTbl(TblId) - удаление отношения; предварительная проверка на наличие зависимых объектов, удаление триггеров, уничтожение индексов, записей, удаление всех записей в системных таблицах, относящихся к таблице, ее индексам или связанным с ней триггерам.

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

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

    1. Стоимость исполнения

    При оценке планов выполнения запросов используются следующие данные, получаемые на основании хранимой в системных каталогах статистической информации:
    cd(ST,O) -количество различных значений в столбце ST некоторой таблицы O;
    glub(I) -глубина В-дерева для индекса I ;
    N(I) -количество листовых страниц в индексе I;
    T(O) -количество строк в таблице O ;
    K(O) -количество строк в одной странице для постоянной таблицы O ;
    K1(BO) -количество строк в одной странице для временной таблицы ВО ;
    sel(O,cond)-оценка количества строк таблицы O, удовлетворяющих условию cond (из раздела WHERE).
    Indsel(I,ПП) -оценка количества строк таблицы с индексом I, удовлетворяющих простому предикату ПП (вырабатывается на основе информации об индексе).

    Кроме того, используются следующие предположения о БД, основанные на статистике работы с ней :
    sort(N) - затрата ресурсов (время, выборка страниц) на сортировку таблицы из N строк ;
    uniq(N) - затрата ресурсов (время, выборка страниц) на сортировку таблицы из N строк с удалением дубликатов.

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

    1. Компиляция

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

    Компилятор использует одноуровневое промежуточное представление на всех фазах обработки оператора SQL. Это представление, с одной стороны, близко к исходному языку. По мере преобразований в нем появляется несколько дополнительных конструкций (например sort вместо order by) и заполняются дополнительные атрибуты части существующих узлов (идентификаторы используемых индексов в узлах экземпляров таблиц). В результате на последней фазе из этого "почти SQL" представления можно получить желаемый исполняемый код, однозначным образом интерпретируя конструкции промежуточного представления (подробнее это описано в пункте 4.3, посвященном кодогенерации). Для оптимизации вычислений каждый узел условий (и тем более подзапросы) имеет маску зависимостей и лежащее под ним поддерево пересчитывается только когда это действительно необходимо. Фактически основной целью всех промежуточных преобразований является перестроение дерева запроса так, чтобы создать иерархию подзапросов, в которой самые внутренние почти не перевычислялись бы.

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

    1. Схема компиляции
      1. Компиляция оператора: шаг за шагом

    На первой фазе (грамматический разбор) выполняется лексический и синтаксический анализ оператора, представленного на языке SQL, в результате которого строится неполное дерево внутреннего представления. Это дерево отражает структуру оператора и содержит информацию об именах использованных в операторе объектов (отношений, полей, констант и переменных). Что именно соответствует этим именам и соответствует ли им хоть что-нибудь к этому моменту еще не выясняется. На этой же фазе генерируется код на языке Си, который может быть использован для замены текста компилируемого оператора SQL в случае статической компиляции. Для части операторов SQL, выполнение которых не зависит от контекста БД (например rollback), промежуточное представление не генерируется и их обработка на этой фазе и завершается.

    Вторая фаза компиляции (семантический анализ) проводит полного контроль существования использованных таблиц, представлений, столбцов, заменяет имена объектов БД на внутренние идентификаторы и проверяет корректность типов в выражениях. Информация о хранимых в базе данных объектах выбирается из системных каталогов базы данных. На этой же фазе производится контроль прав доступа (для тех операторов, для которых это уместно).

    На третьей фазе оператор SQL в своем внутреннем представлении подвергается логической оптимизации. В компиляторе SQL-сервера применяются различные преобразования, "улучшающие" начальное представление операторов. Среди этих преобразований имеются эквивалентные преобразования, после проведения которых получается внутреннее представление, синтаксически эквивалентное начальному (например, приведение запроса к канонической форме). Применяются и семантические преобразования, когда получаемое представление не является синтаксически эквивалентным начальному, но гарантируется, что результат выполнения преобразованного оператора совпадает с результатом оператора в начальной форме при соблюдении ограничений целостности, существующих в базе данных.

    Четвертый этап обработки запроса состоит в выборе на основе информации, которой располагает оптимизатор, набора альтернативных процедурных планов выполнения данного оператора в соответствии с его внутреннем представлением, полученным на предыдущей фазе. Кроме того, для каждого плана оценивается предполагаемая стоимость выполнения запроса ( некоторая характеристика затрат машинных ресурсов) по этому плану. При оценках используется статистическая информация о состоянии базы данных, доступная оптимизатору. Из полученных альтернативных планов выбирается наиболее "дешевый", и именно его внутреннее представление будет соответствовать обрабатываемому запросу. На этой фазе определяются используемые индексы, генерируются подзапросы, создающие временные таблицы и соединения из более чем двух таблиц преобразуются в дерево подзапросов, реализующих парные соединения.Рисунок 2 Структура компилятора

    На пятой фазе (собственно кодогенерация) по внутреннему представлению наиболее оптимального плана выполнения запроса формируется выполняемое представление плана - модуль из команд интерпретатора.

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

    1. Промежуточное представление операторов SQL

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

    • при описании каждого типа узла задается его код и соответствующий ему описатель типов атрибутов (для удобства использования узла часто описывается эквивалентная структура языка Си);
    • все атрибуты имеют одинаковый фиксированный размер и расширение числа типов атрибутов требует изменений в библиотеке поддержки деревьев.

    Несмотря на кажущуюся серьезность последнего утверждения, оно не накладывает сколько-либо действительно серьезных ограничений. Фактически это вынуждает вместо использования структур в качестве атрибутов ссылаться на них, предварительно описав эти структуры как узлы дерева. Можно также описать часть атрибутов узла, как "нетипизированные", и работать с ними любым желаемым способом - библиотека поддержки будет обходить это место стороной.

    Каждому типу узла соответствует уникальный код из задаваемого множества, битовые флаги (не более 32) и свой набор позиционных атрибутов. Атрибутами могут быть числа (long, float), строки (char*), описатели типов SQL, а также ссылки на другие узлы (поддеревья), векторы ссылок или просто целых чисел. Кроме того, узел может содержать ссылки на старшего из сыновей (если о таковых имеет смысл говорить для данного типа узла) и правого брата.

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

    Пример операции сложения констант.

     (Add Real[7,0] { 	(Const "2.1" Real[7,0]) 	(Const "1"  Int[10,0])  }) 

    Пример некоторого абстрактного узла со всеми мыслимыми параметрами.

     (theCode:flag1:another_flag  ;; код и флаги узла                              ;; атрибуты:   Int[9,0]                   ;;  тип SQL(длинное целое)   "some C like string"  12   ;;  строка и целое число   (SomeOtherCode ...)        ;;  ссылка на другой узел   [ 1 7 5 90 13 ]            ;;  вектор целых   [ (Code1 ...) (Code2 ...)  ;;  вектор     (Code1 ...)              ;;    узлов   ]                          ;;  .   {                          ;; сыновья 	(Code3 ...)                 ;; 	...                         ;; 	(Code4 ...)                 ;; . })                           ;; конец узла. 
    1. Первичные преобразования

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

    Что касается фазы грамматического разбора, то она реализована с использованием стандартных генераторов bison (parser generator) и flex (scanner generator). Порождаемое на этой фазе первичное дерево разбора точно следует конструкциям входного языка и, фактически, несет минимум семантический нагрузки. Практически все объекты БД представлены в дереве именованными заглушками, а все деревья выражений нетипизированы. На этой фазе распознаются, принимаются к сведению, но не порождают никаких структур данных объявления начала и конца области определений операторы реакции на ошибки, создания схемы и модуля, отката и фиксации транзакций. Для последней пары генерируется также стандартный текст подстановки.

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

    Следующим шагом в преобразовании дерева является его постепенное преобразование в более функциональную (или скорее менее декларативную) форму. На этом шаге в деревья вводятся узлы, соответствующие временным таблицам, операциям их сортировки и, возможно, удаления дубликатов, а также операциям группирования и подсчета агрегатных функций. При этом чисто языковые узлы либо исчезают из дерева (ORDER_BY), либо меняют семантику на более функциональную. Последнее касается в основном узлов объединения (UNION) и выборки (SELECT), над которыми в случае необходимости возникает операция сортировки и удаления дубликатов. При этих преобразованиях в дереве может возникнуть избыточное число сортировок (каждая операция удаления дубликатов требует сортировки) и временных таблиц (сортировка предполагает наличие таблицы как на входе, так и на выходе). В тех случаях, когда они не являются необходимыми, они будут удалены при дальнейших преобразованиях. Данное же состояние дерева упрощает дальнейший семантический анализ, разбивая запросы на сравнительно небольшие части дерева между порождениями временных таблиц.

    В рамках этого процесса все обращения к представлениям (view) заменяются на обращения к временным таблицам, на которые, в свою очередь, подвешиваются формирующие их запросы. (Вся эта информация также закачивается из БД). Здесь же одноуровневые операции формирования запроса и сортировки конечного результата перестраиваются в более оправданную с точки зрения семантики иерархическую конструкцию. Затем деревья просматриваются для замены всех операций выборки и объединения с удалением дубликатов в аналогичные предыдущей иерархические конструкции, содержащие сортировку с удалением дубликатов и формирующие входную таблицу для нее операции выборки или объединения. И, наконец, последней и, пожалуй, наиболее трудоемкой операцией является преобразование запросов с группированием, в которых операции where и having расположены на одном уровне, в конструкцию запроса, имеющего подзапрос в разделе from, где последний является результатом операции группирования (MakeGroup) и порождает временную таблицу.

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

    1. Генерация кода

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

    1. Сканеры

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

    Как правило каждая временная (и уж точно каждая постоянная) таблица в дереве промежуточного представления порождает отдельный сканер. Теоретически, при вызове операции открытия сканера создается и заполняется временная таблица, из которой потом по заданным условиям выбираются строки данных. Понятно, что необходимости реально создавать каждый раз временную таблицу нет, но такого рода детали скрываются в коде конкретного сканера и не влияют на код других объектов.

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

    1. Простейший сканер

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

    Исходный текст на SQL, который приводит к генерации такого сканера, должен выглядеть примерно так:

     select 'exprlist' from tbl where 'condition' 

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

     query   from scan tbl(clist)   selection 'exprlist'   where 'condition' 

    Код сканера содержит 4 точки входа: L_open, L_fetch, L_close и L_getsc. Первый вход задает открытие сканирования по таблице tbl в порядке определяемом ПУДТ при отсутствии каких-либо простых предикатов. Для сканирования открываются столбцы из списка clist. Используемый в последующих операторах список рассылки выбранных значений соответствует ему. Затем управление возвращается в вызывающую программу, а точка L_fetch запоминается как точка входа для выборки. При последующих запросах на выборку последовательно выбираются строки, проверяется условие сканирования и в случае успеха формируется набор возвращаемых значений. При достижении конца сканирования управление передается на зацикленный участок кода, возвращающий признак конца сканирования. При обращении к третьей точке входа - закрытию сканирования - сканирование закрывается и вход выборки блокируется. Последняя точка входа возвращает идентификатор сканирования таблицы по заданному идентификатору таблицы. Этот метод необходим в случаях позиционного удаления или модификации по курсорам с соединениями. Стандартом языка подобная функциональность не требуется, но в принципе может быть весьма полезной.

     CODE:L_open: Open(&ScanId,TblId('tbl'),NULL,clist)  Suspend(1,0)   ;; возврат и сохранение точки входа для выборкиL_fetch:FindRow(ScanId,rlist,L_bc)  ;; выбрать новую строку  Jif(L_fetch,"not 'condition'") ;; проверить условие  Store(outp1ptr,'expr1')  ;; вычислить выбираемые     ...                   ;;  выражения  Store(outpNptr,'exprN')  Suspend(1,0)     ;; возвратить значения выборки  Jmp(L_fetch)     ;; читать следуюшую строкуL_bc: Suspend(1,100)     ;; конец сканирования  Jmp(L_bc)      ;; и зациклится в этом состоянииL_close:Close(ScanId)     ;; закрыть сканирование и вернуть  Suspend(1,0)      ;; управление, заблокировав вход          ;;  выборки данныхL_c1: Return('error')     ;; "чтение по неоткрытому курсору"L_getsc:Jif(L_Tok,"TblId('tbl') == 'asked TblId'")  Return(-1)      ;; Адрес и тип возвращаемогоL_Tok: Return(0)      ;; параметра для этого входа уже 										;; настроены на ScanId 

    В данном коде имеет смысл подробнее рассмотреть оператор:

     	Jif(L_fetch,"not 'condition'") ;; проверить условие 

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

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

    Сканер с простыми предикатами отличается от предыдущего случая только наличием простого предиката в условии и параметрами команды открытия сканирования в генерируемом коде.

     SQL: select 'exprlist' from tbl where     'condition' and tbl.c1 > 3  CODE:L_open: Open(&ScanId,TblId(tbl),'c1 > 3',clist) ;; открытие сканирования по таблице tbl в порядке ;; определяемом ПУДТ по простому предикату 'c1 =3' ... ;; далее без изменений 

    Случай использования индексов в сканере отличается от предыдущего наличием индекса и опять же параметрами команды открытия сканирования.

    1. Выборки с подзапросами

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

     SQL:
    select 'exprlist' from tbl  	where         'condition' 	       and    tbl.c1 = any (select t2.c1 from t2 )  IMR: query   from scan tbl(clist)   selection 'exprlist'   where     'condition'         and exist             (query               from scan t2(t2.c1)              where tbl.c1 = t2.c1 )  CODE:
    Object0:...L_open: Open(&ScanId,TblId('tbl'),NULL,clist) ;; простое сканирование  Suspend(1,0)       L_fetch: FindRow(ScanId,rlist,L_bc)        ;; выбрать новую строку;; проверка условия 'condition' и предиката exist;; Exist вызывает сканирование подзапроса ObjectS ;; результат - логическое значение и, возможно, код ошибки  Jif(L_fetch,"not ('condition' and     (exist <objectS >))") ... ObjectS:...L_open: Open(&ScanId2,TblId('t2'),NULL,c1)   ;; также простое сканирование...  Jif(L_fetch,"not 'c1=tbl.c1'")    ;; проверить условие... 

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

     		Jif(L_next,"exist <внутренний сканер>")  

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

    1. Соединение

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

     SQL: select * from t1,t2 where 'joincondition' IMR: 	query 	  join t1(clist),t2(clist2) 	  selection 'clist+clist2' 	  where     'joincondition' CODE:L_open: Open(&ScanId,TblId('t1'),NULL,clist);; открытие сканирования по таблице t1 в порядке ;; определяемом ПУДТ при отсутствии каких-либо простых ;; предикатов. Для сканирования открываются столбцы из ;; списка clist.  Suspend(1,0)  L_f1: FindRow(ScanId,rlist,L_bc)    ;; новая строка из t1  Open(&ScanId2,TblId('t2'),NULL,clist2) ;; открытие сканирования по таблице t2 в порядке ;; определяемом ПУДТ при отсутствии каких-либо простых ;; предикатов. Для сканирования открываются столбцы из ;; списка clist2.L_f2: FindRow(ScanId2,rlist2,L_uc)   ;; новая строка из t2  Jif(L_f2,"not 'joincondition'")  ;; проверить условие  Suspend(1,0)       ;; возвратить значения выборки  Jmp(L_f2)       ;; читать следуюшую строкуL_bc2: Close(ScanId2)  Jmp(L_f1)L_bc: Suspend(1,100)  ;; возвратить признак конца сканирования  Jmp(L_bc)   ;; и зациклится в этом состоянииL_close: Close(ScanId)      Close(ScanId2)    Suspend(1,0)    L_c1: Return(`error')  ;; "чтение по неоткрытому курсору"L_getsc: Store(ResPtr,ScanId)  Jif(L_gT2,"TblId('t1') != 'asked TblId'")  Return(0)L_gT2: Store(ResPtr,ScanId2)  Jif(L_err,"TblId('t2') != 'asked TblId'")  Return(0) L_err:	Return(-2)

    Ниже приведен код для сканера, выполняющего эквисоединение. Предполагается, что таблицы имеют уникальные индексы на столбцах 'c1'.

     SQL: select * from t1,t2 where 'condition' and t1.c1 = t2.c1 IMR: 	query 	  equijoin t1(clist)  using  t1i1(c1) , 		     t2(clist2)  using t2i1(c1) 	  selection 'clist+clist2' 	  where     t1.c1 = t2.c1 and              'condition'  CODE:L_open: Open(&ScanId ,IndId('t1i1'),NULL,clist)   Open(&ScanId2,IndId('t2i2'),NULL,clist2) ;; открытие сканирования по таблиц в порядке индексов ;; по столбцам соединения   Suspend(1,0)               ;; L_f: FindRow(ScanId,rlist,L_bc)   ;; новая строка из t1  FindRow(ScanId2,rlist2,L_bc) ;; новая строка из t2L_join: Jif(L_ok,"t1.c1 == t2.c1")  Jif(L_2,"t1.c1 < t2.c1")L_1: FindRow(ScanId,rlist,L_bc)   ;; новая строка из t1  Jmp(L_join)L_2: FindRow(ScanId2,rlist2,L_bc) ;; новая строка из t2  Jmp(L_join)L_ok: Jif(L_f,"not 'condition'") ;; проверить условие  Suspend(1,0)        ;; возвратить значения выборки  Jmp(L_1)      ;; читать следуюшую строкуL_bc: Suspend(1,100)      ;; возвратить признак конца сканирования  Jmp(L_bc)     ;; и зациклится в этом состоянииL_close: Close(ScanId)  Close(ScanId2)  Suspend(1,0)L_c1: Return(-1)          ;; "чтение по неоткрытому курсору"L_getsc:Jif(L_gT2,"TblId('t1') != 'asked TblId'")  Store(ResPtr,ScanId(t1))  Return(0)L_gT2: Jif(L_err,"TblId('t2') != 'asked TblId'")  Store(ResPtr,ScanId(t2))  Return(0) L_err:	Return(`error')				;; Идентификатор таблицы не найден 
    1. Объединение

    В случаях запросов с объединениями объединяющий сканер формируется следующим образом.

     SQL: (select c1 from t1 ) union all  (select c1 from t2 ) IMR: union  	  query 	    from scan t1(c1) 	    selection c1 	  query 	    from scan t2(c1) 	    selection c1 CODE:L_open: Open('t1')  Suspend(1,0) L_f1: FindRow('t1',L_bc) ;; новая строка из t1  Suspend(1,0)   ;; возвратить значения выборки  Jmp(L_f1)   ;; читать следуюшую строкуL_bc1: Close('t1')  Open('t2')L_f2: FindRow('t2',L_bc2) ;; новая строка из t2  Suspend(1,0)   ;; возвратить значения выборки  Jmp(L_f2)   ;; читать следуюшую строкуL_bc2: Close('t2')  Suspend(1,100)  ;; признак конца сканирования  Jmp(L_bc2)   ;; и зациклится в этом состоянииL_close: Suspend(1,0)      Return(-1)   ;; "чтение по неоткрытому курсору"L_getsc: Store(ResPtr,ScanId(t1))  Jif(L_gT2,"TblId('t1') != 'asked TblId'")  Return(0)L_gT2: Store(ResPtr,ScanId(t2))  Jif(L_err,"TblId('t2') != 'asked TblId'")  Return(0) L_err:	Return(-1) 
    1. Группирование и сортировка

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

     SQL: select     count(*)  from       t1  where      'wCond'  group by   c1 having     'hCond' ; IMR: query   from scan tmp0(...)   selection c_s   where 'hCond' TmpTable('tmp0') =  makegroup      [ 1 , count(*), ...]     query       from scan t1(c1,...)       selection c1, ...       where 'wCond' CODE:ObjectS: ;; внутрений сканер...L_open: Jif(L_tmps," TmpTblId0 <> 0") ;;  CreatTmp(&TmpTblId1)  Open(&ScanId,TblId('t1'),NULL,clist) L_f: FindRow(ScanId,rlist,L_bc2)  ;; новая строка из t2  Jif(L_f,"not 'wCond'")    ;; проверить условие  InsRow(TmpTblId1,rlist2)  ;; сохранить значения во временной таблице.  Jmp(L_f)      ;; читать следуюшую строкуL_bc2: Close(ScanId)     ;; закрыть сканирование  MKGROUP(&TmpId0,TmpTblId1,"[1,count(*),...]")  DropTmp(TmpTblId1);; формирование сгрупированной таблицы TmpId0 со значениями агрегатных функций L_tmps: Open(&ScanId2, TmpTblId0,"c1=tbl.c1",NULL);; открытие сканирования по временной таблице ... 

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

    1. Операции добавления, модификации и удаления кортежей

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

    1. Добавление
     SQL: insert into t1  (select :a , t2.c1 from t2 where 'condition' ) IMR: insert into t1   query    from scan t2(...)    selection c1    where 'condition' CODE: (в коде 'O_query' - адрес сканера, реализующего запрос) L_0: Call(O_query,0,0,0);;открыть сканирование по запросуL_f: Call(O_query,1,0,0,L_bc);;выбрать очередную строку   InsRow(TblId('t1'),inslist)  Jmp(L_f)L_bc: Call(O_query,2,0,0)  ;; закрыть сканирование 		return(0) 
    1. Позиционные операции удаления и модификации

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

     SQL: update t1  	set c1 = :a , c2 = t1.c1 * 2 	where current of cursor 'cc' IMR: updаte    	scan t1 ('cc')   	set ( c1 = :a , c2 = t1.c1 * 2) CODE: L_0:  Call('cc',3,TblId('t1'),&ScanId);; получить идентификатор сканирования таблицы из курсора   ModRow(ScanId,replacement_list) 		return(sqlcode) 
    1. Они же в групповых операциях
     SQL: update t1    set c1 = :a , c2 = t1.c1 * 2   where 'uCond' IMR: updаte:all    scan t1 ('cc')   set ( c1 = :a , c2 = t1.c1 * 2) scanner('cc') = query   from scan t1(clist)   selection c1,c2,...   where 'uCond' CODE: L_0: Call('cc',0,0,0)  ;; открыть сканирование  Call('cc',3,TblId('t1'),&ScanId);; получить идентификатор сканирования таблицы  L_f: Call(O_query,1,0,0,L_c);;выбрать очередную строку   ModRow(ScanId,replacement_list)  Jif(L_err,"sqlcode<0") ;; если нарушены ограничения целостности ==> выход  Jmp(L_f)L_c: Call(O_query,2,0,0);; закрыть сканирование  return(0)L_err: Call(O_query,2,0,0);; закрыть сканирование 		return(sqlcode) 
    1. Манипулирование метаинформацией

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

    1. Создание, удаление и модификация таблиц

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

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

     SQL: create table t1 (    c1 int default 1 primary key,    c2 string(10),    c3 real not null,     foreign key (c2) references t2(c2) ) 
    IMR: create table ('t1')= table ( c1 int [1], c2 string(10) [], c3 real [] ) constraints ( primary (c1), foreign (c2) reference t2 (c2), check ( not isnull(c3) )

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

     CODE:L_0: CreatTab('t1',clmninfo)   ;;
    CreatInd('t1c1',unique,primary) ;;
    CreatInd('t1c2',not unique) ;;
    ;; последние три операции сопровождаются настройкой кода триггеров на
    ;; конкретные, полученные в результате этих операций идентификаторы
    ;; таблицы и индексов.
    Suspend(1,0)
    L_1: Insrow('systables',tblparms) ;;
    Insrow('syscolumns', clmnparms)
    Insrow('sysindexes',c1indexinfo)
    Insrow('sysindexes',c3indexinfo)
    Insrow('sysconstraints',foreign_check)
    Insrow('sysconstraints',c3_check)
    Suspend(1,0)
    Return(-2)
    1. Манипуляция представлениями

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

    Удаление представлений приводит к набору команд удаления информации о нем из системных каталогов.

    1. Управление правами доступа

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

    1. Триггеры

    Хотя механизм триггеров не присутствует явно в языке, его наличие на нижнем уровне необходимо для более или менее интеллектуальной реакции БД на команды пользователя. Триггеры неявно вызываются командами добавления, модификации или удаления строк таблиц, а также при фиксации транзакций, если их сфера применения касается таблицы в целом, а не отдельных ее строк. Для каждого типа триггера фиксирован интерфейс. Пожалуй наиболее прост он у триггеров вызываемых при фиксации транзакции. Такому триггеру ничего не передается и он ничего не возвращает кроме кода состояния (sqlcode), отрицательное значение которого вызывает откат транзакции. Что касается остальных типов, то наиболее сложным из них является тип триггера, вызываемого при модификации столбцов таблицы. Такой триггер получает в качестве входных параметров набор новых значений изменяемых столбцов и идентификатор сканирования таблицы непосредственно перед изменением данных. На основании этих параметров триггер может считать, если это необходимо, предыдущее значение данных из таблицы и провести все необходимые вычисления и модификации зависимых данных. Понятно, что код триггера может содержать условия и любой другой, приемлемый интерпретатором код. Рассмотрим код одного из триггеров генерируемых для уже описанной в предыдущем пункте таблицы 't1'.

     CODE:;; foreign (c2) reference t2 (c2)
    ReadRow(T2Scan,'c2')
    Jif(L_ok,"new_c2 == c2) ;; выход если поле не изменилось
    return(0)
    L_0: Open(Scant1,IndId('t1c2'),"c2=t2.c2") ;;
    L_f: FindRow(Scant1,L_c)
    ModRow(Scant1, "t1.c2 := new_c2")
    Jmp(L_f)
    L_c: Close(Scant1)
    L_ok: Return(0)
    1. Оптимизация

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

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

    На первом шаге запросы упрощаются и приводятся к более декларативному виду. Базовыми элементами здесь является поднятие представлений, спуск предикатов, приведение условий к КНФ, приведение простых предикатов к виду "Col op Expr" и, наконец, свертка константных выражений. В качестве основы для преобразования запросов взята система правил, предложенная в Starburst [26]. Эти правила выгодно отличаются тем, что корректно отслеживают порождение дубликатов. Все подзапросы тем или иным способом сводятся к подзапросу Exist. (Если подзапрос должен порождать в точности одну строку, то это отмечается специальным флагом). Отдельный случай представляют собой операторы групповой вставки, модификации и удаления. Эти операторы в ряде случаев необходимо переформулировать, разделяя выборку по условию и собственно операцию модификации данных. Типичным примером может служить оператор увеличения уникального ключа на константу для всех записей таблицы.

    Следующие 2 шага традиционной схемы (генерация возможных методов реализации и полный перебор всех вариантов с оценкой стоимости для поиска наиболее дешевого) в нашем случае объединены в одну. Сборка оптимального плана выполнения запроса происходит снизу вверх. Сначала анализируются и формируются оптимальные планы вычисления подзапросов и вычисляется их стоимость. Стоимость формируется в виде "(cost(i)*T(i))" формулы зависимости от внешних объектов, что позволяет учитывать перевычисление подзапросов при изменении порядка сканирования внешних объектов. С другой стороны, свойство деревьев условий содержать маски зависимостей позволяет при выполнении обходить перевычисление подзапросов, если внешние объекты не изменялись. После этого генерация планов и выбор наиболее дешевого повторяется для объемлющего блока. Эта схема значительно сокращает пространство межблочного перебора, но блокирует такие варианты оптимизации, как близкие к эквисоединению алгоритмы сканирования таблиц подзапроса, хотя надо заметить, что подобные случаи довольно редки. Для сокращения затрат времени на поиск оптимального плана внутри блока (оптимизация сканирования и построение дерева соединений) используются методы отсечения по текущему минимуму (рассматриваемый вариант отбрасывается, если нарастающая оценка стоимости превышает стоимость уже выбранного варианта), и времени (время компиляции не должно превышать оценку наилучшего времени выполнения). Кроме того для вычисления затрат на выполнение плана сначала делаются частичные и полная оценки этих затрат снизу, а в каждом варианте отсчет идет относительно заранее вычисленного минимума, что позволяет быстрее обнаруживать неэффективные варианты.

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

    1. Инструментальные средства

    Как уже говорилось, данная работа выполнялась в рамках совместного проекта Free Software Foundation (FSF) и Института Системного Программирования. Специфика этой работы требовала лицензионной чистоты используемого инструментария разработчика - точнее он должен был удовлетворять правилам FSF [65]. Это значит, что любой заинтересованный в изменении SQL-сервера программист должен иметь возможность получить любой использованный при разработке или эквивалентный ему инструмент практически бесплатно - желательно из коллекции FSF. Это условие предопределяло выбор языка программирования (Си) и компилятора (gcc), отладчика (gdb) и даже редактора (emacs). (На первый взгляд привязка к определенному редактору вовсе не кажется необходимой. Тем не менее она весьма существенна, поскольку emacs не просто редактор, а скорее среда разработки. Эффективное использование этой среды требует определенного стиля как при написании текстов программ, так и при подготовке программного проекта в целом.)

    Помимо этих утилит общего назначения необходим был также стандартный набор средств разработки компиляторов:

    • настраиваемая библиотека поддержки деревьев промежуточного представления;
    • генератор программ лексического анализа;
    • генератор программ грамматического анализа;
    • генератор преобразователей деревьев
    • Back-end generator.

    Существующие пакеты как правило предлагают все эти инструменты в комплекте и нужно было либо использовать весь пакет целиком, либо полностью от него отказаться. К моменту начала разработки мы не смогли найти такого пакета, который удовлетворял бы требованиям FSF. Поэтому в качестве инструментальных средств были выбраны утилиты flex и bison из коллекции FSF, а в качестве библиотеки поддержки работы с деревьями была взята несколько переделанная библиотека поддержки внутреннего представления RTL GNU C компилятора. В том же GNU C компиляторе имелись некоторые средства преобразования деревьев, но они нам не подходили из-за особенностей обработки языка SQL. Что касается кодогенерации, то распознавание деревьев в ней делается также, как и при преобразовании деревьев, а собственно генерация кода настолько сильно отличается от генерации традиционного ассемблера (интерпретируемый код может, в частности, содержать деревья - см. главу 2), что стандартные подходы использовать было затруднительно, а новых интересных идей у нас не возникло.

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

    1. Цели и задачи.

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

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

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

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

    При разработке собственно генератора мы ставили перед собой в дополнение к уже перечисленным следующие цели:

    1. минимальность - генератор должен максимально опираться на уже имеющийся программный код;
    2. ненавязчивость - при использовании генератора программист должен иметь столько свободы сколько ему нужно;
    3. простота в использовании - входные конструкции генератора должны быть самоочевидны, а их использование смотреться естественно в тексте программ;
    4. гибкость - генератор должен легко настраиваться на изменения, происходящие с библиотекой поддержки деревьев и вообще быть легко адаптируемым к новым требованиям.
      1. Kitty

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

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

    Пример описания правила.

     ;; ... * 0 * ... ==> 0 (Rule  "shrink_to_0" 	(Mult:0 { 		( Const:exist_op  "0" )  	})          ""  { 		;; удаление поддерева умножения 		(REMOVE:tree  (Op:0) ) 		;; генерация возвращаемой константы 		(Const  "0" )  })  

    Кроме того, в режиме препроцессора kitty воспринимает и отдельно стоящие в тексте на Си конструкторы деревьев. При записи конструкций kitty в тексте на Си они предваряются стоящим в первой позиции символом '#' или должны начинаться с последовательности '#('. Для спецификации внешних переменных в этом режиме используется конструкция '<var>' при задании атрибутов, ссылки вида (Op:n) при задании ссылок на узлы (массив 'Op' необходимо предварительно вручную проинициализировать) или специальных узлов Ccode. Ниже рассмотрен пример добавления списка сыновей и описателя столбца к уже имеющимся сыновьям заданного дерева.

    (здесь и далее: 'tree'-тип "ссылка на узел дерева")

     tree join(tree parent,tree new_children) {   tree Op[2];    char col_name = "column name";   Op[0]=parent;   Op[1]=new_children;   return #    (Op:0 {  			(DOWN:list (Op:0))) 			(Op:1:list ) 			(Column <col_name>) 		    })   ; }  

    Рассмотрим подробнее элементы языка.

    1. Представление правил.

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

     (Rule "SomeName"   ( шаблон )   " C-строка с дополнительным условием "   {     ( действие )      ...      ( действие )   } ) 

    После обработки kitty данное правило будет преобразовано в функцию:

     tree rule_SomeName(int *success,tree reference){...} 

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

    1. Шаблоны.

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

    1. Специальные элементы шаблонов

    Как уже было сказано, в шаблонах можно использовать несколько узлов специального назначения.

    Код "Op" используется для задания узла, код которого невозможно однозначно указать и/или на который накладываются какие-либо сложные нетривиальные условия. Формат этого узла:

     ( Op "test_routine_name" {...}) 

    где "test_routine_name" - задаваемое имя функции или макроопределения, проверяющего эти ограничения, и имеющего интерфейс:

     int "test_routine_name"(tree reference). 

    Если имя функции опущено, то дополнительной проверки не производится. Если вы не указываете ограничений на поддеревья, то этот узел может быть записан как "(Op)" или "Op".

    Кроме того, для пропуска узлов при сравнении используются узлы с кодами "Skip_Code" и "Skip_Codes", обычно задаваемые в тексте как "-" и "-". Узел "Skip_Code" используется для указания наличия произвольного узла в соответствующем месте сравниваемого дерева. Подпрограмма сравнения пропустит во входном дереве этот узел и все находящееся под ним поддерево. Узел с кодом "Skip_Codes" используется для указания последовательности произвольных узлов в соответствующем месте сравниваемого дерева. Подпрограмма сравнения будет пропускать в анализируемом дереве все узлы до тех пор, пока не встретит узел совпадающий со следующим за Skip_Codes узлом в шаблоне. Если Skip_Codes стоит последним в списке сыновей какого-либо узла, это означает, что остаток сыновей соответствующего узла в сравниваемом дереве вас не интересует.

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

     ;; Распознавание сложения двух констант, при котором  ;; результат - целое  (Add Int[9,0] { (Const) (Const) }) ;; Распознавание сложения двух произвольных выражений,  ;; при котором результат - целое  (Add Int[9,0] { - - }) ;; Распознавание сложения двух произвольных выражений (Add - { - - }) ;; Распознавание сложения произвольного числа ;; произвольных выражений (Add) ;; Распознавание узла вида "операция"  ;; (+-*/ "and" "or" и т.п.)  (Op "Is_Operation") 

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

     (Add:0 { - (Const) - }) (Add:exact: { (Const:1:exist_op) }) 
    1. Алгоритм сравнения с шаблоном.

    Сравнение узлов входного дерева с шаблоном правила производится при обходе корень-вниз-вправо. При сравнение текущего узла дерева с текущим узлом шаблона последовательно сравниваются код, флаги и атрибуты. Затем, если шаблон требует эквивалентности поддеревьев распознаваемого дерева, производится проверка текущего поддерева на эквивалентность поддереву, уже распознанному ранее в процессе сравнения. В случае, если все эти сравнения закончились успешно, начинается сравнение сначала сыновей, а потом младших братьев текущего узла. Если при распознавании входное дерево было отвергнуто где-либо дальше текущего узла (ниже или правее), то делается попытка найти следующий узел распознаваемого дерева, подходящий для сравнения данному узлу шаблона. (Это может быть возможно, если узел шаблона имеет флаг "exist_op" или предшествующий в списке братьев узел шаблона имел код "Skip_Codes".) Если это возможно, то повторяется анализ для всех ниже- и правеележащих узлов. Когда найти в распознаваемом дереве еще один узел, подходящий для сравнения текущему узлу шаблона невозможно, то возвращается отрицательный результат распознавания поддерева.

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

     (Add						;;будет распознано сложение   {						;;любых двух одинаковых констант    (Const:2 Int[5,0])		;;типа Int    (Const:2)	 			;;в Op2 будет хранится указатель  })							;; на вектор ссылок на эти 2                       	;; константы 
    1. Действия.

    Исполнительный блок представляет собой последовательность конструкторов деревьев SQL, содержащих помимо обычных узлов дерева специальные узлы (Op:n) для ссылки на элементы распознанного дерева, вызовы других правил трансформации деревьев, узлы подстановки С кода, а также некоторые простейшие операции над деревьями. Любой узел конструктора может иметь цифровые флаги "0"-"14". При этом ссылка на генерируемое данным конструктором дерево будет также помещена и в соответствующий операнд и на нее можно будет сослаться также, как если бы она была получена при распознавании дерева. (Работает подобно оператору присваивания в С).

    1. Конструкторы.

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

     (Add:1                   ;; Op1 <- (Add)   {                       ;;          |   (Mult {(Op:2) (Op:3)}) ;;=>      (Mult) -- (Op4) -...   (Op:4:list)            ;;          | })                       ;;        (Op2) -- (Op3)                          ;;          |        |                          ;;          ...      ... 
    1. Вызов правил

    Поскольку любое правило возвращает результат равный либо входному, либо преобразованному дереву в теле генератора можно подставить вызов другого или этого же правила в форме:

     (Run "rule_name" (sometree ...) ) 
    1. Вставка текста на C.

    Конструкция вида: (C_code "строка на С") используется для подстановки в генерируемый код произвольного текста на языке Си. При использовании в теле конструкторов эти коды должны быть выражениями, порождающими деревья.

    1. Операции.
  • SET
  • Используется для инициализации локальных переменных Op[0], ... Op[14].
    DOWN
    RIGHT
    Результатом применения этих конструкций будет старший сын или правый брат соответственно
  • COPY
  • Генерирует копию заданного в качестве аргумента дерева
  • IMAGE
  • возвращает ссылку на узел, являющийся образом заданного узла при копировании дерева, содержащего этот заданный узел. Если узел не найден и/или задаваемые деревья не являются копиями возвращает NULL.
  •  (IMAGE (mapped_node) (copied_tree) (origin_tree) ) 
  • INSERT
  • Вставляет узел в заданное место заданного дерева. Для определения места вставки используется флаг "before". В любом случае возвращается все заданное дерево, в которое вставляется узел.
  •  (INSERT<:before> (in_tree) (what) <(where)> ) 
  • REPLACE
  • Заменяет узел в задаваемом дереве. В любом случае возвращает ссылку на это дерево.
  •  REPLACE (in_tree) (what) (by) ) 
  • REMOVE
  • Используется для очистки памяти от уже ненужных деревьев или узлов. От всех остальных операций REMOVE отличается тем, что не возвращает ничего. Поэтому его НЕЛЬЗЯ встроить в дерево конструкторов а можно использовать только в форме отдельного действия.
  • SWITCH
  • Оператор SWITCH выполняет последовательно перечисленные в нем действия до тех пор, пока не будет выполнен выполнено успешно какое-либо из вызываемых правил или анализируемый локальная переменная LCC не будет установлена в 1 в подставляемом С коде. Возвращает результат последней выполненной операции, исключая C_code и REMOVE. Вызовы правил выполняются как с помощью конструкции (Run...), так и с помощью специальной, доступной только внутри SWITCH конструкции (CASE...). Эта конструкция полностью эквивалентна "Run", но в качестве входного дерево берется параметр SWITCH.
     (SWITCH <(subtree_for_test_by_CASE)>   {      (операция_1)      (Run "rule1" (intree1) )      (Case "rule2")         ...     (операция_n) }) 
    1. Контекст.

    При включении кода на С помимо всех известных внешних переменных можно использовать следующие данные:
    1. tree Op[15] -
    1. массив ссылок на узлы обрабатываемого дерева ( заполняется частично при сравнении, частично при преобразованиях). В Kitty для ссылки на них используются Op:0, Op:1, .. Op:14. Так как по сути это одно и то же, то иногда возможна путаница
    1. tree in_tree -
    1. ссылка на исходное дерево
    1. tree Rop -
    1. ссылка на возвращаемое дерево
    1. int LCC -
    1. результат отработки вложенных правил.
      LCC равное 1 - признак успеха!
    1. static tree shab -
    1. ссылка на дерево шаблона

    1. Пример.

    Пример демонстрирует приведение к нормальной форме арифметического выражения.

     /*  a*..*b*(c+d+...)*e*...    *   ==> (c*a*...*b*e*...) + (d*a*..*b*e*..) + ...  */ int theSameCode(tree node) {   static int odd=0;   static enum token code = 0;   register enum token ccode = CODE_TRN(node);    if ( ! AssotiativeOperation(node))     return 0;   odd = 1 - odd;   if( odd ) code = ccode;   return (ccode == code); } # (Rule "NestedAssotiative"     (Op:0 "TheSameCode" {  		(Op:1:exist_op "TheSameCode" )  	   } )     ""     { 		(DELETE (Op:1) (Op:0)) ;;  		(Op:0  { 			(DOWN:list (Op:0))  			(DOWN:list (Op:1)) 		}) 		(REMOVE (Op:1) )       ;;  		(Run "NestedAssotiative" (Op:0) )   }) # (Rule "AssotiativeToOne"     (Op:0 "AssotiativeOperation" { (Op:1) } )     ""     { 		(REMOVE (Op:0) ) 		(Op:1) 	   }) int AssotiativeOperation(tree node) {   register enum token ccode = CODE_TRN(node);    if ( ccode!=ADD && ccode!=MULT && ccode!=AND && ccode!=OR)   return 0;   return 1; } # (Rule "SwapMultAdd"     (Mult:0 { (And:1:exist_op ) }) ;; a*..*b*(c+d+...)*e*...     ""     { ;; Op0 -> a*..*b*(c+d+...)*e*..   Op1 -> c+d+... 		(DELETE (Op:1) (Op:0))  ;; Op0 -> a*..*b*e*..   Op1 -> c+d+... 		(COPY:2 (Op:0) ) ;; Op2 -> copy of Op0 		(DOWN:3 (Op:1))) ;; Op3 -> c 		(DELETE (Op:3) (Op:1)) ;; Op1 -> d+... ;; проверяем не единственность операнда у ассоциативной операции  		(Run:1 "AssotiativeToOne" (Op:1)) ;; Op1 -> d (если 'd' было единственным операндом) 		(Run "NestedAssotiative" 			(Add  {			;; (c*a*...*b*e*...) + (d*a*..*b*e*..) + .. 				(Run  "SwapMultAdd"			;; (d*a*..)+(d1*a*..)+.. 					(Run  "NestedAssotiative" 	;; (d+..)*a*..*b*e* 						(Mult {				;; (d+...) * (a*..*b*e*..)  							(Op:1)			;; d+... 							(Op:0)			;; a*..*b*e*..  				 	      })    				)	 ) 				(Run  "SwapMultAdd" 					(Run  "NestedAssotiative" 	;; c*a*..*b*e*.. 						(Mult {				;; c * (a*..*b*e*..) 							(Op:3)			;; c 							(Op:2)			;; a*..*b*e*.. 						}) 				)	 ) 			}) }) 
    1. Выводы.

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

    1. Заключение

    Основные полученные результаты заключаются в следующем:

    1. Разработан мобильный компилятор свободного SQL-сервера, поддерживающий стандарт языка SQL 1989 г. и частично 1992.
    2. В разработке применены современные средства оптимизации запросов, включая методы семантической и логической оптимизации, а также технологические средства построения компиляторов.
    3. Построено технологическое окружение компилятора языка запросов. Спроектированы и разработаны необходимые инструментальные средства.

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

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

    Автор приносит свою искреннюю благодарность своим коллегам Е.В.Воинову, К.В.Дышлевому, В.Н.Пономаренко, А.В.Яхину, О.В.Дмитриевой за постоянную поддержку, внимание и терпимость в течении проекта и без ежедневного труда которых он вряд ли был бы осуществим. Мне особенно хотелось бы поблагодарить руководителя группы С.Д,Кузнецова и моего научного руководителя С.С.Гайсаряна за внимание и готовность отвечать на мои вопросы, а также обсуждать мои не всегда внятные идеи. Я также весьма признателен директору ИСП РАН чл.-корр. РАН В.П.Иванникову, чья поддержка и понимание наших проблем позволила нам завершить эту работу.

    1. Литература

    1. Кузнецов С.Д. Идеология свободного программного обеспечения и проект GNU: текущее состояние и ближайшие задачи. // Ж. "Программирование" ї1, 1992, стр 3-7
    2. Кузнецов С.Д. Свободный SQL-сервер для разработки приложений и проведения исследований в области баз данных /Тезисы докладов Международной конференции SUUG-92 // Ст. Петербург, МЦНТИ, SUUG, 1992, стр. 16-18.
    3. Капп Д., Лебен Дж. Техника программирования для IMS. Методология пользования DL/1 // Москва "Финансы и Статистика" 1983
    4. Язык описания данных КОДАСИЛ // Москва "Статистика" 1981
    5. Мартин Дж. Организация баз данных в вычислительных системах // "Мир" 1980.
    6. Brodie M., Stonebraker M. Migrating Legacy Systems // Morgan Kaufmann Publishers 1995 (ISBN 1-55860-330-1)
    7. Е.Ф.Кодд Реляционная модель данных для больших совместно используемых банков данных. / Ж. "СУБД" ї1, 1995, стр. 145-160
    8. Системы баз данных третьего поколения: манифест / Ж. "СУБД" ї2, 1995, стр 143-158
    9. Malkolm Atkinson, Francois Bansilhon, David DeWitt, Klaus Dittrich, David Maier, Stanley Zdonik. The Object-Oriented Database System Manifesto // 1st Int. Conf. Deductive and Object-Oriented Databases, Kyoto, Japan, Dec. 1989
    10. M.M.Astrahan et al. "System R: Relational Approach to Data Base Management." ACM Trans. Database System 1, No 2, 97-137 (1976)
    11. Blasgen M.W., Astrahan M.M., Chamberlin D.D., Gray, King W.F., Lindsay B.G., Lorie L.A., Mehl J.W., Putzolu, Schkolnick M., Selinger P.G., Slutz D.R., Strong H.R.,Traiger I.L., Wade B.W., Yost R.A. System R: An Architectural Overview // IBM Syst. J.- 1981.- 20, N 1.- C. 41-62
    12. D.D.Chamberlin et al. "SEQUEL 2: A Unified Approach to Data Definition, Manipulation and Control." IBM J. Res. Develop. 20, No 6, 560-575(1976) [R-SQL-76]
    13. Blasgen M.W., Eswaran K.P. Storage and Access in Relational Data Bases // IBM Syst. J.- 1977.- 16, N 4, Lorie R.A., Nilsson J.F. An Access Specification Language for a Relatiomal Data Base System // IBM J. Res. And Dev.- 1979.- 23, N 3.- C. 1-13
    14. R.Williams et al. "R*: An Overview of the Architecture" // IBM Research Report RJ3325 (Dec 1981)
    15. D.Daniels et al. "An Itroduction to Distributed Query Compilation in R*" // Proc 2nd Intl. Symposium on Distributed Databases Sep.1992 New York.
    16. P.G.Selinger and M.E.Adiba "Access path selection in Distributed Database Management System" In Proc. Intl. Conf. on DataBase, Aberdeen, Scotland (July 1980). London England: Heyden and Sons Ltd. (1980)
    17. Philip A. Bernstein et al. "Query Processing in a System for Distributed Databases (SDD-1)" // ACM TODS 6, No 4 (Dec. 1981).
    18. J.B.Rothnie, Jr., et al "Introduction to a System for Distribute Databases(SDD-1)." // ACM TODS 5 No 1 (Mar.1980)
    19. Eugene Wong. "Retrieving Dispersed Data from SDD-1: a System for Distribute Databases" // in Tutorial: Distributed Data Base Management, IEEE, Long Beach, Calif. 1978
    20. Special Section: Next-Generation Database Systems // Comm. ACM.- V.34, N 10.- 1991.- 3-120.
    21. Stonebraker M. Implementation of Integrity Constraints and Views by Query Modification / Proc. ACM SIGMOD Int. Conf. Manag. Data, San Jose, Calif., May 23-26, 1975 // New York, 1975.- C. 65-78
    22. Rowe L.A., Stonebraker M. The Commercial INGRES Epilogue / The INGRES Papers: The Anatomy of a Relational Database Management System // Reading, Mass.: Addison-Wesley.-- C. 121-128
    23. C.J.Date An inroduction To Database Systems, sixth edition. /Addison-Wesley, 1995
    24. Кузнецов С.Д. Логическая оптимизация запросов в реляционных СУБД //Ж."Программирование", N 6, 1989, стр. 46-59
    25. Кузнецов С.Д. Методы оптимизации выполнения запросов в реляционных СУБД / Тем. изд. "Итоги науки и техники. Вычислительные науки". Т.1 // Москва, ВИНИТИ, 1989, стр. 76-153
    26. Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan. Extensible/Rule Based Query Rewrite Optimization in Starburst / Proc. ACM SIGMOD Int. Conf. Manag. Data, San Diego, Calif., June 1992 // New York, 1992.- 39-48.
    27. Daniel F. Lieuwen, Devid J. DeWitt / A Transformation-Based Approach To Optimize Loops in Database Programming Language / Proc. ACM SIGMOD Int. Conf. Manag. Data, San Diego, Calif., June 1992 // New York, 1992.- 91-100.
    28. Gotlieb L.R. Computing Joins of Relations / Proc. ACM SIGMOD Int. Conf. Manag. Data, San Jose, Calif., May 1975 // New York, 1975.- C. 55-63
    29. Kim W. A New Way to Compute the Product and Join of Relations / Proc. ACM SIGMOD Int. Conf. Manag. Data, New Work, May 1980 // New York, 1980.- C. 178-187
    30. Merrett T.H. Why Sort/Merge Gives the Best Implementation of the Natural Join // ACM SIGMOD Record.- - 13, N 2, C. 40-51
    31. Valduriez P. Join Indeces // ACM Trans. Database Syst.- 1987.- 12, N 2.- C. 218-246
    32. Kim W. On Optimizing an SQL-Like Nested Query // ACM Trans. Database Syst.- 1982.- 7, N 3.- C. 443-469
    33. Ganski R.A., Wong H.K.T. Optimization of Nested SQL Queries Rivisited / Proc. ACM SIGMOD Int. Conf. Manag. Data, San Francisco, Calif., May 1987 // New Work, 1987.- C. 23-33
    34. Dayal U. Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers / Proc. 13th Int. Conf. Very Large Data Bases, Brington, England, Sept. 1987 // Los Altos, Calif., 1987.-
    35. Freytag J.C. A Rule-Based View of Query Optimization / Proc. ACM SIGMOD Int. Conf. Manag. Data, San Francisco, Calif., May 1987 // New York, 1987.- C. 173-180
    36. King J.J. QUIST: A System for Semantic Query Optimization in Relational Databases / Proc. 7th Int. Conf. Very Large Data Bases, Cannes, France, Sept. 3-11, 1981 // New York, 1981.- C. 510-517
    37. Shenoy S.T., Ozsoyoglu Z.M. A System for Semantic Query Optimization / Proc. ACM SIGMOD Int. Conf. Manag. Data, San Francisco, Calif., May 1987 // New York, 1987.- C. 181-195
    38. Lee S., Han J. Semantic Query Optimization in Recursive Databases / 4th Int. Conf. Data Eng., West Berlin, Sept. 13-15, 1988 // New York, 1988.- C. 444-451
    39. Ceri S., Gottlob G. Translating SQL into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries // IEEE Trans. on Software Eng.- 1985.- 11, N 4.-
    40. Б.Розенблат "Unix RDBMS: следующее поколение". /Ж. "СУБД" ї1, 1995, стр. 7-23
    41. Д.Девитт, Д.Грэй Параллельные системы баз данных: будущее высоко эффективных систем баз данных. / Ж. "СУБД" ї2, 1995, стр 8-31
    42. International Standard Database Language SQL. ISO 9075:1989 [ISO89]
    43. Information Technology - Database Language SQL. ISO/IEC JTC1/SC21 N6789 - Proposed revised text of DIS 9074. March 1992. [ISO92]
    44. Date C.J. A Critique of the SQL Database Language // ACM SIGMOD Rec..- 1984.- 14, N 3 .- C. 24-31
    45. Ferrante L. A Comparison of the ISO Working Draft Standard for SQL and a Commercial Implementation of SQL // ACM SIGSmall/PC Notes.- 1987.- 13, N 3.- C. 28-55
    46. Jim Melton (ed.) ISO-ANSI Working Draft Database Language SQL (SQL2 and SQL3). October 1990.
    47. Common Object Request Broker: Architecture and Specification. / OMG Document Number 91.12.1
    48. Mattbew Rapaport. Object-Oriented Data Bases: The Next Step in DBMS Evolution // Comp. Lang.- 5, N 10.- 1988.-
    49. Won Kim. Object-Oriented Databases: Definition and Research Directions // IEEE Trans. Data and Knowledge Eng.- 2, N 3.- 1990.- 327-341
    50. Carey, D.J. DeWitt et al. Object and File Management in the EXODUS Extensible Database System // 12th Int. Conf. Very Large Data Bases, Kuoto, Japan, Aug. 1986.-
    51. Rowe, M. Stonebraker. The POSTGRES Data Model // 13th Int. Conf. Very Large Data Bases, Brighton, England, Sept. 1-4, 1987.- 83-96
    52. Stonebraker. The Design of the POSTGRES Storage System // 13th Int. Conf. Very Large Data Bases, Brighton, England, Sept. 1-4, 1987.- 289-300
    53. Michael Stonebraker, Lawrence A. Rowe, Machael Hirohama. The Implementation of POSTGRES // IEEE Trans. Knowlwdge and Data End.- 2, N 1.- 1990.- 125-141
    54. Batory, J. R. Barnett, J. F. Garza, K. P. Smith, K. Tsukuda, T. E. Wise. GENESIS: An Extensible Database Management System // IEEE Trans. on Software Eng.- 14, N 11.- - 1711-1730
    55. Fishman. An Overview of the Iris Object-Oriented DBMS // Digest of papers, 33rd CompCon, Spring Feb. 29 - Mar. 4, USA.- 177-180
    56. Deux et al. The Story of O2 // IEEE Trans. Knowledge and Data Eng.- 2, N 1.- 1990.- 91-108
    57. D.Vaskevitch "Database in Crisis and Transition: A Technical Agenda for the Year 2001" / SIGMOD RECORD Vol 23 Num 2 June 1994 // Proc. of the 1994 ACM SIGMOD Intl. Conf. On Management of Data
    58. В.П.Иванников, И.Б.Бурдонов, А.С.Косачев, Г.В.Копытов, С.Д.Кузнецов. Принципы организации КЛОС - кластерной операционной системы // Ж."Программирование",N.6, 1990,
    59. Бурдонов И.Б., Копытов Г.В., Косачев А.С., Кузнецов, Смиронов Ю.П. КЛОС: операционная система и технология программирования / Сб. "Вопросы кибернетики. Программное обеспечение высокопроизводительной системы" // Москва, НСК, стр. 34-57
    60. Кузнецов С.Д., Юдин В.Н. Управление файлами в кластерной операционной системе // Ж. "Автометрия", Новосибирск, N 5, стр. 19-25
    61. Бурдонов И.Б., Игнатьева Н.В., Кузнецов С.Д., Пономаренко В.Н., Шпекторов С.В., Функции и организация подсистемы управления памятью и синхронизацией реляционной СУБД. / Сб. "Вопросы Кибернетики", вып 165 // Москва, НСК АН СССР, 1991, стр 71-97
    62. Кузнецов С.Д., Пономаренко В.Н. Модульная мобильная система управления данными и транзакциями /Труды 5-ой Всесоюзной конференции по базам данных и знаний // ж. "УСиМ",ї7 1991 стр 37-45
    63. Кузнецов С.Д. Исследование и разработка SQL-сервера. / Рукопись диссертации, Москва,1993
    64. Пономаренко В.Н. Управление внешней памятью и организацией транзакций реляционной СУБД / Рукопись диссертации, Москва,1992
    65. GNU General Public License, Version 2// FSF. 1994
    66. Е.В.Войнов, С.С.Гайсарян, О.Л.Дмитриева, К.В.Дышлевой, М.Л.Кимельман, С.Д.Кузнецов, В.Н.Пономаренко, А.Л.Рыбаков. Свободный SQL-сервер: состояние дел и ближайшие планы /Тезисы докладов международной конференции SUUG-93. //Москва, МЦНТИ, SUUG, 1993
    67. Е.В.Войнов, С.С.Гайсарян, О.Л.Дмитриева, К.В.Дышлевой, М.Л.Кимельман, С.Д.Кузнецов, В.Н.Пономаренко, А.Л.Рыбаков. Российский проект свободно распространяемой СУБД. / ж. "Открытые Системы". ї4. Осень 1993.
    68. М.Кимельман,А.Яхин. "Kitty: Управляемый правилами генератор преобразователей деревьев". / вып. "Вопросы Кибернетики - приложения системного программирования" // сборник ВК-180, РАН, Москва 1995.
    69. К.Дышлевой, М.Кимельман "Оптимизация запросов в GNU SQL Сервере". / в печати. вып. "Вопросы Кибернетики - приложения системного программирования" // РАН, Москва 1996.
    70. J.Bloomer "Power Programming with RPC" / O'Reily & Associates, Inc, 1992
    71. Кузнецов С.Д. Развитие идей и приложений реляционной СУБД System R / Тем. изд. Итоги науки и техники. Вычислительные науки" Т.1. // Москва, ВИНИТИ, 1989, стр. 3-75
    72. Lohman G., Mohan C., Haas L., Lindsay B.G., Selinger, Wilms P., Daniels D. Query Processing in R* / Query Processing in Database Systems // New York e.a.: Springer.-- C. 31-47
    73. Deductive Database Rule Languages: Analysis and Case Study // Lect. Notes Comput. Sci.- 1990.- 466.- 198-216.
    74. Замулин. Системы программирования баз данных и знаний // Новосибирск: Наука, 1990.- 352 с.
    75. Ульман Д. Основы систем баз данных // М.: Финансы и статистика.- 1983.- 335 c.
    76. Christodoulakis S. Estimating Record Selectivities // Inf. Syst.- 1983.- 8, N 2.- C. 105-115
    77. Christodoulakis S. Estimating Block Selectivities // Inf. Syst.- 1984.- 9, N 1.- C. 69-79
    78. Lynch C. Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values / Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Ca, Aug.-Sept. 1988 // Los Altos, Calif., 1988.- C. 240-251
    79. Zahorjan J., Bell B.J., Sevcik K.C. Estimating Block Transfers When Record Access Probabilities Are Non-Uniform // Inf. Process. Lett.- 1983.- 16, N 5.- C. 249-252
     Исследование и разработка языковой подсистемы SQL сервера.
    Лента новостей


    2006 (c) Copyright Hardline.ru