автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Исследование и разработка подсистемы SQL сервера

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ СИСТЕМНОГО ПРОГРАММИРОВАНИЯ

На правах рукописи УДК 682.3.523

л

ш

КИМЕЛЬМАН Михаил Леонидович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ЯЗЫКОВОЙ ПОДСИСТЕМЫ здь СЕРВЕРА

05.13.11 -МАТЕМАТИЧЕСКИЕ И ПРОГРАММНОЕ ОВЕС-ПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ МАШИН, КОМПЛЕКСОВ, СИСТЕМ И СЕТЕЙ.

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

Москза 1996

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

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

Официальные оппоненты:

доктор физико-математических наук Серебряков В.А.

кандидат технических наук Кагаловский М.Р.

Ведущая организация: Институт Проблем Информатики РАН.

Защита состоится _¿Ахял 1996 г. в > час.

на заседании диссертационного совета Д2.00,.50.01 в Институте Системного Программирования РАН, Москг.а, Б.Коммунистическая 25.

С диссертацией можно ознакомится.в библиотеке ИСП РАН. Автореферат рёзослан " ¿У" £2 Ч ' 1996.

Ученый секретарь диссертационного'совета

/С.Прохоров/

ОБЩАЯ ХАРДКТЗРйСТИКа гавозы

Данная диссертационная работа посвящена разработке мпилятора SQL свободно распространяемого SQL-сервера. оект свободно распространяемого SQL-сервера входит в ело первых проектов, выполняемых в России под эгидой F {"Фонд свободного программного обеспечения" - общевенная организация, созданная в Массачусетском Техно-гическом Институте и поддерживаемая многими лроизво-:телями компьютеров - HPr SGI и др.)- Целью этого проза являлось создание мобильной, .гибкой, настраиваемой :стемы управления базами данных. С этой точки зрения мпилятор языка управления данными. должен быть легко оптируемым к последующей эволюции как языка, так и ^системы хранения данных.

Цгл&ю диссертационной работы бьшо исследование ме->дов компиляции непроцедурных языков и языков управле-[я базами данных, анализ и выработка схемы компиляции inpocos, разработка компилятора SQL и его технологиче-;ого окруженх*я.

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

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

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

кается необходимая для их принятия информация, . а не' откладываются до последней фазы);

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

- инструментальные средства распознавания и преобразования деревьев промежуточного представления — компактные, минимальные, естественные (форма описания соответствует существу пред-е§авления).

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

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

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

- использование интерпретатора без потери производительности;

- реализация базового механизма триггеров;

- компактность кода.

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

- использование компилятором одноуровневого, промежуточного представления;

- протокол взаимодействия с клиентом,,. позволяющих безболезненно переносить' клиентов- в не-ШШ среду;

- подсистему, ответственную за отображение интерпретируемого кода, его загрузку и редакцию свя' зей.

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

и наличие отечественного сопровождения и технической щержки. Следует отметить также, что система разраба-¡алась в рамках международного проекта GNU и должна :ь вкгшчена в Фонд свободного программного обеспече-I, доступный программистам всего мира.

За защиту заносятся:

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

- технологическое окружение и инструментальные средства; . •

- средства оптимизации запросов.

Результаты работы докладывались на конференции UG-93.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Работа состоит из введения, пяти глав, заключения и .иска литературы. Объем диссертации составляет 66 раниц машинописного текста. Список литературы состоит 1 79 названий:

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

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

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

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

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

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

- диалект не должен противоречить стандарту SQL'89; ■

- язык должен быть достаточно мощным, чтобы обеспечить возможность практического использования системы;

- расширения языка должны быть практически оправданы, не должны приводить к чрезмерному усложнению реализации и соответствовать стандарту SQL'92;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- предельно компактной (команда вводилась, только если была абсолютно необходима или значительно повышала эффективность);

- емкой {если мы обнаруживали часто повторяемую последовательность команд, она заменялась на одну . единственную команду)

- адекватной набору низкоуровневых операций, доступа к БД (ПУДТ) и легко адаптируемой к изменениям в нем;

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

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

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

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

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

пре^икатам сравнения и т.п.

Деревья выражений значительно сократили набор коя интерпретатора. Команда, связанные с вызовом-под-грамзя и возвратом результатов, тесно связаны с общей уктурой интерпретируемого кода. Основу кода состав-t объекты (сканеры), имеющие несколько точек входа и раняющие состояние между вызовами. Стандартная кода вызова подпрограммы получает в качестве параметра >ес такого объекта и номер -точки входа. Интерфейс .ектов предполагает, что объект в начале содержит ко-[ество точек входа и массив их описателей. Описатель пси входа представляет из себя адрес точки входа в 1уле и ссылки на описатели входных и выходных пара-.■ров.' Описатель параметров содержит, в свою очередь, :ло параметров и массив описателей параметров, сопящих из описателя типа и адреса выделенной для парафа области.

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

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

Компилятор должен ' преобразовывать декларативный зык с определяемым окружением контекстом в последова-гль'ность высокоуровневых интерпретируемых команд. Каж-т оператор входного языка является независимым. Код 2L может содержась внешние объекты (переменные Си, на-ример), реальный типовой кентроль для которых комлиля-

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

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

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

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

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

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

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

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

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

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

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

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

На первом шаге запросы упрощаются и приводятся более декларативному виду.• Базовыми элементами здес является поднятие представлений, спуск предикатов, при ведение условий к КНФ, приведение простых предикатов виду "Col op Expr" и свертка константных выражений, качестве основы для преобразования запросов взята си стема правил, предложенная в Starburst. Эти правила вы

ю отличаются тем, что корректно отслеживают порож-¡е дубликатов. Все подзапросы тем или иным способом ;ятся к подзапросу Exist. {Если подзапрос должен по-гать в точности одну строку, то это отмечается спе-гьным* флагом) . Отдельный случай представляют собой заторы групповой вставки, модификации и удаления.

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

Следующие 2 шага традиционной схемы (генерация воз-ных методов реализации и полный перебор всех вариан-

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

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

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

Пятая глава представляет kitty: инструмент для опи сания правил трансформации деревьев. Этот программа по зволяет встраивать в тексты на Си описания деревьев дл их генерации и/или распознавания. При разработке гене ратора мы ставили перед собой-следующие цели:

- минимальность - генератор должен максимально от раться на уже имеющийся программный код;

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

- простота в использовании - входные конструкт генератора должны быть самоочевидны, а их испол! зование смотреться естественно в тексте пррграмм

'Ч'

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

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

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

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

> сложное условие на узел и возможно все поддерево, ¡и выполнении сгенерированных kitty процедур эти шаб->ны вновь будут созданы и переданы для сравнения емес-

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

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

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

1.Разработан мобильный компилятор .свободного SQL-

сервера, поддерживающий стандарт языка SQL 1989 г.

и частично 3 992.

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

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

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

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

Автор приносит свою искреннюю благодарность .своим ксллегам Е.В.Воинову, К.В.Дышлевому, Е.Н.Пономаренко,

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

B.П.Иванникову, чья поддержка и понимание наших проблем позволила нам завершить эту работу.

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

Е.В.Воинов, С.С.Гайсарян, О.Л.Дмитриева,

К.В.Дышлевой, М.Л.Кимелъман, С.Д.Кузнецов,

В.Н.Пономаренко, А.Л.Рыбаков. Свободный SQL-сервер: состояние дел и ближайшие планы /Тезисы докладов международной конференции SUUG-93. //Москва, МЦНТИ, SDUG, 1993.

B-Boííhob, С.С.Гайсаряв, " 0.Jl.Дмитриева,

В.Дьшшевой, М -Л.Кимельман, С.Д.Кузнецов,

Н.Покомаренко, А.Л.Рыбаков. Российский проект обадно распространяемой СУБД. / ж."Открытые стемы". №4. Осень 1993.

Кимельмаы^А.Яхин. ""Kitty: Управляемый правилами нератор преобразователей деревьев". /. вып. опросы Кибернетики - . приложения системного ограммирования" // сборник ВК-180, РАН, Москва > 95.

Дышлевой; М.Кимельман "Оптимизация запросов в GNU L Сервере". / в печати. еып. "Вопросы Кибернетики приложения системного программирования" // РАН, сква 1996.