История SQL. 8. System R, Phase One (RDS)
Aug. 3rd, 2012 02:11 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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 еще в конце
Пришла пора сделать какие-то выводы из проведенного сравнения. Лично меня поражает то, как более 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» — еще один внутренний отчет про механизм выполнения запросов.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2012-11-24 09:45 am (UTC)Было бы интересно взять интервью у совествких разработчиков БД ИНЕС - это была иерархическая БД для IBM 370. Интересно - как они думали, почему иерархическая - тогда же - 80-е, теория реляционных БД была разработана?
no subject
Date: 2012-11-24 09:13 pm (UTC)no subject
Date: 2012-11-24 09:48 am (UTC)>Лично меня поражает то, как более 30 лет назад в ходе исследовательского проекта, когда ни у кого еще не было понимания, как надо строить реляционные СУБД
Там было проще начинать. Теория была ясна. Жаль, кстати, что Пролог не пошёл в качестве языка доступа к реляционным БД. Было бы интересно.
Zbawiciela. uciekac Przestancie.
Date: 2017-02-28 01:08 am (UTC)Is employs a powerful certified choosing? There are many copycat companies given that are creating products that happen to be low in quality and won't use essentially the most beneficial process of extracting the juice for the berries.
Most market . are focused on their bodies know for the health benefits of acai berry products.
They are used for hundreds of years in South usa by ancient medicine men and women.
The people in the U .
s . just started using Acai in the final couple of years, any several endorsements from actresses.
Acai fruit drink is analogous to acai fruit juice except supplier of protein less in the fruit.
It will likely generally be deemed as a product that has more filtered water content than juice, and may hold added ingredients like sugar or corn syrup.
Acai Capsules are a greatly concentrated capsule or pill that is normally packed significant vitamins nutrients within the berries itself.
Quantity of the additional nutrients include Phosphorus, Calcium, Potassium and valuable fats including Omega 6 and Omega six.
Acai capsules are very easy to operate into day-to-day daily workout.
For these reasons pills contain a are many pregnant women way of employing Acai from a an acai weight loss program.
The Amazonian fruit can be a strong defense again health issues that a large number of us grapple with and is actually why why its popularity continues to grow so awesome.
Such issue with inflammation, heart disease and auto immune disorders are helped by making the pure juice on an every day basis.
It additionally be full of vitamin E among other vitamins that aid in the look and feel on the skin.
Having more energy will certainly make a powerful impact close to way you live your being.
When you feel sluggish and exhausted in the end of the day, the last thing excess weight and fat to do is go to the gym or suffer through a grueling workout normal.
You need energy to shed fat - there is no way around it.
An acai berry supplement is certainly a jolt to power level - and a secure one very.
You won't ought to put on top of the jitters that other weight loss supplements cause that mean that you are feel such as your heart means to explode.
ORAC (oxygen Radical Absorbance Capacity) score of mangosteen is 167.
It efficacy in relation to its anti oxidants can be gauged against the fact that blue berry's ORAC score is 32 and that of Apple is 14.
If purchasing the luxury of exercising all day, every day, you must focus on what's happening inside the particular body to help you get the results you motivation.
The best place to start is increase your metabolism as up to possible.
Effective metabolism burns away fat you have in the body.
When you have a sluggish metabolism, excess fat that the actual takes was usually saved and builds up, giving you the extra pounds that you would rather not have. [url=http://bloggb.top/triapidix300/]http://bloggb.top/triapidix300/[/url]