История SQL. 8. System R, Phase One (RDS)

[egorius]

Начало: 1. Необходимая предыстория, назад: История SQL. 7. System R, Phase One (RSS).

Теперь поговорим о том, что происходило в Фазе 1 с высокоуровневой компонентой System R — Relational Data System.

SEQUEL продолжал развиваться под руководством Дона Чемберлина. Правда, в какой-то момент (1977 или 78 год) имя пришлось изменить, поскольку оно оказалось уже кем-то зарегистрированным. Недолго думая, из имени выбросили гласные; так и получился SQL. Но и сейчас это имя частенько произносят по-старому — «сиквел», — отдавая дань уважения System R.

Среди прочих изменений обрела свой современный вид фраза GROUP BY HAVING, появился привычный синтаксис табличных алиасов, была введена (нереляционная, но полезная) конструкция ORDER BY.

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

В Оракле все перечисленное сохранилось в первозданном виде.

Ограничения целостности в System R были представлены весьма широко, и коммерческие системы далеко не сразу смогли предоставить аналогичные возможности. Во-первых, были реализованы утверждения (assert). Таблицы можно было снабжать произвольными предикатами SQL; нарушение истинности предиката считалось нарушением целостности. Предикаты проверялись в конце каждой транзакции либо по специальной команде ENFORSE INTERGITY.

ASSERT ON UPDATE TO EMP:
  NEW SAL >= OLD SAL

Аналогом Оракла с некоторой натяжкой можно считать ограничение check (обратите внимание на слова old и new).

Во-вторых, имелся более общий и мощный механизм триггеров, перенятый Ораклом (в версии 7 в 1992 году) с небольшими синтаксическими изменениями. Вот пример:

DEFINE TRIGGER EMPINS
  ON INSERTION OF EMP:
    (UPDATE DEPT
     SET    NEMPS = NEMPS + 1
     WHERE  DNO = NEW EMP.DNO)

Интересно посмотреть на программный интерфейс курсоров, предоставляемый RSS, с точки зрения вызывающей стороны. Вот как могла бы выглядеть программа на PL/I, обращающаяся к БД:

CALL BIND('X',ADDR(X));
CALL BIND('Y',ADDR(Y));
CALL SEQUEL(C, 'SELECT NAME:X FROM EMP WHERE JOB=Y');
CALL FETCH(C);
CALL CLOSE(C);

Имелась также команда DESCRIBE, позволяющая получить описание возвращаемых полей. Есть ли сомнения, откуда растут ноги у Oracle Call Interface?

Однако использовать в программе команды RSS не слишком удобно, поэтому несколько позже был сделан препроцессор, заменявший более высокоуровневые команды на соответствующие низкоуровневые вызовы. Команды предварялись знаком доллара — этот символ выбрали, поскольку он не мог встречаться первым в командах PL/I и COBOL:

$LET C BE
  SELECT NAME INTO $X
  FROM EMP
  WHERE JOB = $Y;
$OPEN C;
$FETCH C;
$CLOSE C;

Кстати, в Оракл перекочевал и специальный предикат CURRENT TUPLE OF для ссылки на текущую позицию открытого курсора (только слово tuple подверглось чистке — наверное, как слишком академическое).

Выполнение запросов. Для каждой команды SQL выполнялся разбор (синтаксический и семантический — проверка используемых таблиц). Затем выполнялась оптимизация: выбирался порядок соединения, пути доступа и способы соединения так, чтобы минимизировать стоимость выполнения. Результатом работы оптимизатора являлся план выполнения на специальном «деревянном» языке Access Definition Language. План передавался генератору кода, который транслировал дерево плана в исполняемый (!) код с обращениями к RSS.

Идея компиляции принадлежит Раймонду Лори, который убедил команду, что такой подход позволит ускорить выполнение запросов. Пришлось переписать часть уже готового кода, но ведь одной из задач проекта было показать, что реляционная СУБД может сравниться в скорости с «традиционной». Для генерации использовался сравнительно небольшой (около 100 элементов) набор шаблонов в машинном коде IBM 370.

Общий принцип состоял в том, что подготовительная работа должна выполняться как можно раньше. Например, для конструкции LET CURSOR BE разбор, оптимизация и генерация кода производились еще на этапе компиляции. Сгенерированный модуль доступа сохранялся в базе данных и в дальнейшем использовался для выполнения запроса. При этом RDS автоматически отслеживала зависимости и инвалидировала подготовленный код при изменении структуры таблиц или путей доступа. В этом случае при обращении к запросу оптимизация производилась заново уже во время выполнения программы (прозрачно для приложения). Если же запрос не мог быть обработан заранее (например, во время компиляции могла отсутствовать таблица или сам запрос мог формироваться динамически с помощью команд PREPARE и EXECUTE), то разбор, оптимизация и генерация кода изначально откладывались на время выполнения.

Как видим, общая схема разбора запроса, включая механизм library cache, полностью унаследована Ораклом. Конечно, со временем в ней произошли изменения, но в целом процесс устроен точно так же. Мне даже кажется, что этап «Code Generation» System R проливает свет на происхождение туманного «Row Source Generation» Оракла (интересно, во что сейчас компилируют план?).

Оптимизатор — безусловно, наиболее интересный компонент RDS, поскольку в System R была придумана и реализована стоимостная оптимизация.

В прототипе Фазы 0 стоимость измерялась в обращениях к строкам данных. Но XRM не хранил кортежи как единый фрагмент данных; вместо этого отдельно хранились значения атрибутов и отдельно — объединяющие их ссылки. За счет этого экономилось место (можно было ставить ссылки на один раз записанное значение), но для считывания всего кортежа могло потребоваться много обращений к диску.

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

Оптимизатор имел дело с тремя составляющими пространства перебора:

• Способ доступа к данным — либо полное сканирование сегмента, либо доступ по индексу.
• Способ соединения таблиц — либо метод nested loops (так он и назывался), либо merging scans (аналог в Оракле — sort merge join). Хэш-соединение не было реализовано: при упоре на индексный доступ оно не давало особых преимуществ перед сортировкой-слиянием, которое эффективно использовало отсортированность данных, полученных по индексу.
• Порядок соединения таблиц — уменьшение числа вариантов для перебора достигалось за счет эвристики, исключающей из рассмотрения декартово произведение, пока есть другие варианты.

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

Формулы были основаны на тех же предположениях, что и сейчас в Оракле: на равномерности распределения данных (гистограмм в System R не было) и на некоррелированности предикатов. Сами формулы, конечно, отличаются, отражая разное внутреннее представление данных и упор System R на индексный доступ — пытливый ум может сам сравнить книгу Льюиса и статью Гриффитс. Тем не менее общность подхода налицо.

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

И вновь обращу внимание на то, что современный Оракл пошел по тому же пути. Идеи System R заимствованы вплоть до того, что стоимость запроса в Оракле также выражается в количестве одноблочных чтений и процессорное время пересчитывается в эти единицы. Удивительно только, что в стоимостной оптимизатор в этой системе появился лишь в версии 7 в 1992 году, а учет времени — в версии 9i в 2001 году. А ведь все это работало в System R еще в конце 70-х.

Пришла пора сделать какие-то выводы из проведенного сравнения. Лично меня поражает то, как более 30 лет назад в ходе исследовательского проекта, когда ни у кого еще не было понимания, как надо строить реляционные СУБД, были нащупаны пути и решения, которые продолжают отлично работать в современных системах. Все, чем богат Оракл, так или иначе опирается на идеи System R. Единственное радикальное изменение заключается в механизме мультиверсионности; все остальное не заменило решения System R, а эволюционно улучшило их.

Продолжение следует: 9. System R, Phase Two.

Почитать и посмотреть:

• «Access Path Selection in a Relational Database Management System» — знаковая статья Пат Гриффитс (Селинджер) сотоварищи про оптимизацию.
• Джонатан Льюис, «Oracle: основы стоимостной оптимизации» — глубокое проникновение в недра оптимизатора Оракла.
• «An Access Specification Language for a Relational Data Base System» — про деревянный язык ASL.
• «System R: An Architectural Update» — внутренний исследовательский отчет (1979 год).
• «Support for Repetitive Transactions and Ad Hoc Query in System R» — еще один внутренний отчет про механизм выполнения запросов.

Comments

[nikname.livejournal.com]

Мне кажется, что фишка в том, что реляционные базы данных опирались на реляционную алгебру. Т.е. это было не изобретение велосипеда, как CODASYL или иерархические БД, это были проекты, котороые можно было написать, сначала, на бумаге и покрутить в уме.
Было бы интересно взять интервью у совествких разработчиков БД ИНЕС - это была иерархическая БД для IBM 370. Интересно - как они думали, почему иерархическая - тогда же - 80-е, теория реляционных БД была разработана?

[egorius.livejournal.com]

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