Предлагаю вашему вниманию немного дополненный доклад, который я делал на конференции PGConf.СПб 2024. В нем я рассказываю о том, как появились первые реляционные системы, как возник и всех победил язык SQL.
Доисторические времена
Начиная с изобретения абака, история развития вычислительной техники — это так или иначе история автоматизации вычислений. Даже само слово «вычислительная» говорит об этом (и в английском языке тоже: computer, calculator — вычислитель).
Важная переломная точка приходится на XIX век. Типичной задачей того времени, требовавшей большого объема вычислений, был расчет различных таблиц (например, логарифмических или тригонометрических). Работа над устройствами, способными автоматически справляться с вычислениями, привела Чарльза Бэббиджа к его знаменитой ныне Аналитической машине. Другие современные ей устройства были спроектированы для решения какой-либо одной конкретной задачи, Аналитическая же машина была по задумке Бэббиджа программируема.
Она состояла из блоков, присутствующих теперь в любой ЭВМ: арифметическое устройство, запоминающее устройство, управляющее устройство, периферия (ввод программы и данных с жаккаровских перфокарт и вывод результатов на печать). К сожалению, Аналитическая машина никогда не была построена, хотя это и неудивительно: за неимением лучшего в середине XIX века, Бэббидж спроектировал ее на механической элементной базе (то есть в прямом смысле на рычагах и шестеренках).
Однако заложенные в машину принципы оказались настолько удачными, что они во многом определили дальнейшее развитие вычислительной техники. Говард Эйкен, создавший в 1943 году (при участии IBM — так уж получилось, что эта корпорация будет встречаться нам постоянно) первую реально работавшую программируемую машину Automatic Sequence Controlled Calculator (для краткости названную Mark I), признавался: «Живи Бэббидж на 75 лет позже, я остался бы безработным». Фактически Mark I повторял архитектуру Аналитической машины, но на более современной элементной базе (Эйкен использовал как механические элементы, как и электромеханические реле).
Некоторое время после появления ЭВМ их продолжали использовать только для вычислительных задач (в основном с военной спецификой: расчет баллистических таблиц, вычисления для создания водородной бомбы, криптография). Но уже к концу 1940-х появилось понимание, что наряду с чисто математическими задачами, программируемый компьютер может решать и задачи бизнеса. Первыми ласточками стали великобританский EDSAC (1949) и построенная в начале 1950-х на его основе коммерческая система LEO (применялась для расчета зарплаты, складского учета, планирования производства — практически ERP), а также американский UNIVAC (1951), созданный для хранения, обработки и печати большого объема данных (в качестве внешней памяти использовалась магнитная лента емкостью порядка миллиона символов, лентопротяжное устройство обеспечивало скорость 12500 символов в минуту).
Более широкому применению ЭВМ в бизнесе мешало отсутствие запоминающего устройства большой емкости с произвольным доступом: магнитная лента по своей сути последовательна, а магнитные барабаны имели небольшую емкость и использовались в основном как дополнительное «медленное» ОЗУ. Ситуация изменилась в 1956 году с изобретением IBM жестких магнитных дисков и появлением первого НЖМД IBM 350 Disk File (устройство имело емкость 5 миллионов символов и состояло из 50 дисков, вращающихся со скоростью 1200 оборотов в минуту).
Появление запоминающих устройств прямого доступа стало причиной переворота в мышлении... Направления, обозначаемые словами в и из, поменялись на обратные. Если директива ввод в мире последовательного доступа к файлам означала с ленты в вычислительную машину, то новая директива ввод означает в базу данных.
— Чарльз Бахман
Примерно в то же время (середина 1950-х) начали появляться и первые операционные системы, которые, среди прочего, унифицировали работу с внешними устройствами, введя понятие файла. В отличие от обычного современного понимания файла как потока байтов, в операционных системах мейнфреймов файл был структурирован и представлял собой набор записей фиксированного или переменного размера. Доступ к файлам мог быть как последовательный (запись за записью), так и индексированный (по части записи, объявленной ключом, можно перейти сразу к подходящим записям). В таком файле нетрудно разглядеть прообраз базы данных.
Однако многими важными для информационных систем свойствами ОС все-таки не обладают. Взаимосвязанные данные сложной структуры нужно хранить в нескольких файлах, обеспечивая при этом их согласованность (пользователь БД не должен увидеть «промежуточной» ситуации, когда в одном файле информация уже изменилась, а в другом еще нет). Должна быть возможность одновременного доступа к данным многими пользователями (как для чтения, так и для изменения), а механизмы файловых систем для этого слишком грубы. Требуется надежное хранение информации с возможностью восстановления базы данных в согласованном состоянии после сбоя. Кроме того, нужны пользовательский и программный интерфейсы для выборки и изменения информации.
Какое-то время все эти задачи — с тем или иным успехом — решали заново в каждом приложении, работающем с базой данных.
Человеком, который первым понял, что СУБД имеет смысл как отдельная универсальная программа, стал Чарльз Бахман. Он работал в General Electric (а это была одна из крупнейших компаний, она производила и собственные компьютеры). Занимаясь системой управления производством, он выделил компонент управления данными — Integrated Data Store, IDS. Сначала IDS смогли воспользоваться для своих задач другие подразделения GE, им понравилось — это существенно экономило силы, — и в 1964 году IDS была выпущена как отдельный продукт.
В 1973 году Бахман был удостоен премии Тьюринга. А это одна из главных премий в нашем мире, признание огромного вклада в развитие отрасли.
Сетевая модель
Из языков программирования высокого уровня в те времена были Фортран для математики (1954), академический Алгол и своеобразный Лисп (1958). На чем писать коммерческие задачи, было не очень понятно, и вот в 1959 году был образован комитет по языкам систем обработки данных CODASYL, который разработал язык COBOL (Common Business-Oriented Language).
В 1965 году внутри этого комитета была создана группа DBTG (Data Base Task Group) для разработки языка для баз данных. В 1969 году эта группа, основываясь на идеях Бахмана (а Бахман сам и входил в эту группу), представила спецификацию сетевой модели данных CODASYL.
Приведу простой классический пример: детали (PART) и поставщики (VENDOR). Они связаны отношением «многие ко многим» через дополнительную сущность «поставка» (SUPPLY). Диаграмма Бахмана выглядит вполне привычно, похоже на обычную ER-диаграмму (только ее в то время еще не изобрели):
А вот упрощенный фрагмент программы на Коболе с описанием схемы такой базы данных (Хабр не умеет расцвечивать Кобол, это упущение):
01 PART.
02 PART_ID PIC X(8).
02 PART_DESC PIC X(50).
01 SUPPLY.
02 SUP_PRICE PIC S9(6)V9(2).
01 VENDOR.
02 VEND_ID PIC X(8).
02 VEND_NAME PIC X(40).
SET NAME PART_INFO
OWNER PART
MEMBER SUPPLY
SET NAME VENDOR_SUPPLY
OWNER VENDOR
MEMBER SUPPLYУ детали есть идентификатор и описание, у поставщика — идентификатор и имя, атрибут поставки — срок. Тоже вполне привычно, не считая синтаксиса. Но на что стоит обратить внимание: записи PART, VENDOR и SUPPLY не содержат ничего, что связывало бы их друг с другом. Это именно отдельные записи. А связи — это отдельная штука, которая называется SET — множество. У множества есть родительная запись (OWNER) и дочерние записи (MEMBER). Здесь два множества: PART_INFO (поставки данной детали) и VENDOR_SUPPLY (поставки данного поставщика).
Бахман продвигал идею, что программист — это навигатор в мире данных. Так, кстати, называлась и его тьюринговская лекция.
Сейчас мы посмотрим одну очень простую программу (на Коболе, конечно), и смысл этих слов сразу станет ясен. Попробуйте, кстати, догадаться, что делает этот код.
FETCH-THE-PART.
MOVE 15 TO PART_ID.
FETCH FIRST PART USING PART_ID.
AT END GO TO ALL-DONE.
FIND-SUPPLY.
FIND NEXT SUPPLY WITHIN PART_INFO.
AT END GO TO ALL-DONE.
FETCH OWNER WITHIN VENDOR_SUPPLY.
DISPLAY VEND_ID.
GO TO FIND-SUPPLY.
ALL-DONE.Мы разберем программу на примере: пусть у нас два поставщика, три детали и три поставки. Ниже показаны записи и множества, существующие в базе данных (обозначения не я придумал — так было принято):
Сначала программа получает запись типа PART с идентификатором 15 (FETCH FIRST PART), она будет нашей точкой входа в базу данных. Эта запись является родительской в множестве типа PART_INFO.
Теперь мы находим следующую поставку в текущем множестве PART_INFO (FIND NEXT SUPPLY). Все дочерние записи множества связаны двунаправленными ссылками, так что между ними можно перемещаться, используя команды FIND FIRST, FIND NEXT или FIND LAST, FIND PRIOR.
Дальше находим и выводим родительскую запись в текущем множестве типа VENDOR_SUPPLY (FETCH OWNER). Такая ссылка на родителя есть у каждой дочерней записи.
Продолжаем цикл (GO TO FIND-SUPPLY). Пока мы «гуляли» по множеству VENDOR_SUPPLY, множество PART_INFO помнило нашу текущую позицию. Теперь мы получаем следующую дочернюю запись (FIND NEXT SUPPLY).
Находим и выводим родительскую запись множества типа VENDOR_SUPPLY (FETCH OWNER).
Попытка получить следующую запись в множестве типа PART_INFO приводит к завершению цикла, и выполнение заканчивается.
Как легко видеть, программа выводит всех поставщиков детали номер 15. Понравилось? Кстати, свою заметку Go To Statement Considered Harmful Эдсгер Дейкстра написал в 1968 году.
И это очень простая программа. Можете себе представить, чего стоило написать и отладить какой-нибудь отчет, собирающий данные по нескольким десяткам сущностей, а потом — что самое печальное — поддерживать его.
Что мы должны извлечь из этого примера, прежде чем двигаться дальше: сетевая база содержит не только данные, но и связи между ними, причем программист-навигатор должен эти связи знать, чтобы по ним перемещаться. Если мы добавим новые связи, программы придется переписать, чтобы они смогли ими воспользоваться.
Начало 1970-x. Первый луч света
К нашему счастью, в это время в исследовательском центре IBM в Сан-Хосе (это сердце того района, который сейчас называется Кремниевой долиной) работал Эдгар Кодд.
Тед, как называли Эдгара знакомые, думал над тем, как можно хранить и обрабатывать данные. Будучи математиком, он понял: раз данные — это множества записей, то и работать с ними можно как с множествами, математическими методами.
Реляционная модель
В 1969 году Кодд написал внутренний отчет о своей работе (Derivability, Redundancy and Consistency of Relations Stored in Large Data Banks), который никто толком не понял, а в 1970-м опубликовал ставшую впоследствии знаменитой статью A Relational Model of Data for Large Shared Data Banks, в которой описал реляционную модель и ввел реляционную алгебру. Модель работает с отношениями. Алгебра дает набор операций (проекция, селекция, соединение…), который является замкнутым: выполняя любую операцию над отношениями, мы снова получаем отношение. Это дает возможность составлять из операций выражения любой сложности. Эти выражения и становятся запросами.
В последующих статьях (A Data Base Sublanguage Founded on the Relational Calculus 1971 года, Relational Completeness of Data Base Sublanguages 1972 года) он расширил теорию и добавил реляционное счисление, основанное на логике предикатов первого порядка. Это выражения типа «существует такой поставщик, для которого верно...».
Позвольте ограничиться этим кратким описанием и не вдаваться в подробности реляционной теории, они и без меня хорошо известны. Лучше обращу ваше внимание на то, что привычный нам термин database в то время состоял еще из двух отдельных слов data base, а иногда использовалось и data bank.
Важно, что в реляционной модели связи между данными определяются самими данными, и больше ничем. Поэтому — продолжая пример — мы должны в поставку включить идентификаторы поставщика и детали:
PART (p#, desc)
VENDOR (v#, name)
SUPPLY (v#, p#, price)А ниже приведен пример того же запроса, выбирающего поставщиков детали 15, в нотации Кодда:
s[v#]: SUPPLY(s) ∧ s[p#]=15Одна короткая и понятная строчка. В ней мы говорим, что переменная s – это поставка (SUPPLY), номер детали (p#) должен быть равен 15, и из поставки нас интересует номер поставщика (v#).
Казалось бы, преимущество реляционной модели перед сетевой очевидно? Но не стоит думать, что идеи Кодда были немедленно приняты.
Во-первых, были серьезные сомнения о реализуемости такого подхода. В сетевой модели путь доступа определял программист, а в реляционной? Написать выражение мы можем, а как его вычислять?
Ситуация напоминала период первых языков высокого уровня. Когда Джон Бэкус придумал Фортран (тоже в IBM, кстати), он заявил, что программист не должен тратить свое время на возню с регистрами процессора, а вместо этого может просто написать формулу. Эта идея была воспринята в штыки профессионалами, привыкшими оптимизировать свой код на низком уровне. Чтобы преодолеть сопротивление, Бэкусу пришлось написать эффективный компилятор.
Во-вторых, у IBM уже была своя система IMS (Information Management System), созданная еще в 1966 году по заказу НАСА для управления спецификацией материалов ракеты Сатурн-5. IMS использовала не сетевую модель, но похожую на нее — иерархическую. Естественно, никто не спешил бросать то, что приносит деньги. (IMS, кстати, до сих пор вполне себе жива, как и Кобол.)
Кодд не унывал и рассказывал про свои идеи и наработки всем, до кого мог дотянуться. В 1972 году он доехал до исследовательского центра IBM в Йорктауне (IBM была богатой компанией со множеством исследовательских центров по всем Штатам).
Среди слушателей были Дональд Чемберлин и недавно защитившийся Рэймонд Бойс. Они как раз изучали модель CODASYL и думали над возможными пути ее развития. Простота формул Кодда буквально ошарашила их и стала чем-то вроде глотка свежего воздуха. Они поняли, что надо не развивать CODASYL, а заниматься реляционной моделью.
Пришел Тед и начал придумывать из головы запросы и писать их на доске на своем реляционном языке. И они получались очень короткие и понятные. ... С той поры мне уже больше не хотелось работать с CODASYL.
— Дон Чемберлин
Рэя Бойса вы наверняка знаете, если слышали про нормальную форму Бойса — Кодда. Это тот самый Бойс. К сожалению, он очень рано умер от аневризмы, ему было всего 26, но все же успел оставить яркий след. А вот найти его достоверную фотографию было непросто (в сети попадаются разные, откровенно неправильные варианты).
SQUARE
Итак, Кодд вернулся в Сан-Хосе, а Дон и Рэй стали играть в запросы: придумывали задачи и пытались написать решение в реляционном стиле.
Они быстро пришли к мысли, что простым программистам нужны не математические символы Кодда, а что-то более простое и понятное, похожее на язык программирования. Этот язык не должен строго следовать реляционной теории, но должен манипулировать множествами строк.
В результате в 1973 году у них получился язык SQUARE (Specifying Queries as Relational Expressions).
Строительный блок языка — «отображение» (mapping). Идея та же, что в реляционном счислении: берем отношение (SUPPLY), говорим, что номер детали (p#) должен быть равен 15, а нас интересует идентификатор поставщика (v#). Но Дон и Рэй решили отказаться от переменной, им показалось, что так проще.
SUPPLY (15)
v# p#Отображения устраняют дубликаты, но иногда это не нужно, например, для вычисления агрегатной функции. В таком случае отношение указывается со штрихом:
AVG ( SUPPLY' (15))
price p#Можно строить композицию отображений, получается аналог IN или соединения:
VENDOR ○ SUPPLY (15)
name v# v# p#
Оказалось, что в IBM возникло несколько групп, заинтересовавшихся реляционной моделью, около дюжины человек, и в 1973 году было принято решение собрать их вместе и перевезти в Сан-Хосе, поближе к Кодду.
Проект за неимением хороших идей назвали просто System R — реляционная система.
Проект сразу разделили на две части. Группа RDS (Дон и Рэй) занималась языком. Группа RSS стала разрабатывать движок: формат хранения, индексы, блокировки, журналирование, транзакции — вот это вот все. Поскольку быстро разработать движок невозможно, для прототипа взяли уже готовый, не особо подходящий, но это дало возможность сразу экспериментировать с языком.
Кстати, помимо научных статей, бесценным источником информации о ранних днях реляционных СУБД и о System R в частности является стенограмма The 1995 SQL Reunion: People, Projects, and Politics (есть и перевод на русский Сергея Дмитриевича Кузнецова; на том же сайте выложены его переводы множества полезных статей).
SEQUEL
У Дона и Рэя уже были наработки в виде SQUARE, но было понятно, что в таком двухэтажном виде язык не годится: запросы было удобно писать на доске, но трудно набирать на клавиатуре. Поэтому они свернули все в строчку и заменили математические символы простыми английскими словами. Заодно и отказались от терминов «отношение», «кортеж», «атрибут» в пользу всем понятных «таблица», «строка», «столбец».
В идеале они хотели, чтобы «человек не в теме» мог хотя бы примерно понять, что делает запрос, и вообще старались сделать так, чтобы с базой данных мог взаимодействовать не программист, а пользователь. С этой целью в группе некоторое время даже работал лингвист. В итоге, как мы знаем, из этой затеи ничего не вышло, но первопроходцами быть трудно.
SELECT v#
FROM SUPPLY
WHERE p# = 15Язык назвали SEQUEL. По сравнению со SQUARE он оброс такими конструкциями, как подзапросы и GROUP BY:
SELECT name
FROM VENDOR
WHERE v# =
SELECT v#
FROM SUPPLY
WHERE p# = 15Причем сначала GROUP BY трактовался как «приставка» к FROM, а HAVING еще не придумали:
SELECT v#
FROM SUPPLY GROUP BY v#
WHERE COUNT(p#) > 10Мне всегда было любопытно, кто первый додумался выравнивать запросы по нескольким вертикалям. Оказалось, что сами авторы это и придумали, запросы взяты из статьи 1974 года SEQUEL: A Structured English Query Language. А язык описывается в этой статье через нотацию SQUARE.
Интересно, что Кодд не принимал непосредственного участия в проекте System R, хотя с ним, конечно, советовались. Он бы не особо доволен тем, что его строгая красивая теория компрометируется каким-то странным языком, не похожим на формулы, и держался на расстоянии. Впоследствии его критика стала настолько противоречить интересам компании, что он был вынужден покинуть IBM.
А в это время в Калифорнийском университете в Беркли — не через дорогу, но прям рядом с Сан-Хосе — преподавали Майкл Стоунбрейкер и Юджин (Джин) Вонг.
Стоунбрейкера мы конечно все хорошо знаем как основателя проекта POSTGRES, превратившегося в конечном счете в PostgreSQL. Сравнительно недавно, в 2014 году, Майклу тоже вручили премию Тьюринга.
А тогда, в 1972 году, Стоунбрейкер получил грант на создание геоинформационной системы. Как утверждает Лоренс Роу в статье History of the Ingres Corporation, проект был назван INGRES в честь французского художника Jean Auguste Dominique Ingres, с подобранной расшифровкой Interactive Graphics and Retrieval System. Правда, французское имя произносится не Ингрес, а Энгр, поэтому не исключено, что и нам надо не мелочиться и вместо Постгри говорить Постгр.
Первая часть проекта была связана с графической системой для картографии, она нас не очень интересует. А вот вторая — с разработкой базы данных. Стоунбрейкер с Вонгом организовали семинар для изучения систем управления базами данных. В числе прочего они ознакомились со статьями Кодда и решили создать свою реляционную систему. Она унаследовала имя всего проекта — INGRES.
В отличие от проекта System R, который, естественно, использовал мейнфреймы IBM, университет купил машину попроще, PDP-11. Говорят, сами Кен Томпсон и Денис Ритчи приезжали из Белл Лабс помогать с установкой на нее системы UNIX, которую буквально только что переписали с ассемблера на C.
Стоунбрейкер решил рискнуть и вести разработку под недавно появившуюся ОС на недавно появившемся языке.
Quel
Группа под руководством Вонга разработала язык, названный QUEL (query language). Его первая версия описана в статье 1974 года INGRES — A relational data base system.
Сложно сказать, какое имя — QUEL или SEQUEL — появилось раньше, но получился такой вот каламбур. Вообще надо отметить, что отношения между группами в Сан-Хосе и в Беркли сложились напряженные: хотя группы работали рядом и фактически над одной и той же задачей, у них постоянно возникали споры о первенстве публикаций. Поэтому в итоге они практически не общались между собой, хотя, конечно, отслеживали статьи.
QUEL довольно точно следовал идеям Кодда. Первый пример выглядит практически так же, как в нотации Кодда. Предложение INTO помещает выборку во временное отношение, для вывода на экран можно было написать INTO TERMINAL. Конечно, были оставлены «академические» понятия отношения, кортежа и атрибута, которые достались в наследство и Постгресу.
RANGE OF S IS SUPPLY
RANGE OF V IS VENDOR
RETRIEVE INTO W(V.name)
WHERE V.v# = S.v# AND S.p# = 15QUEL отличался от SEQUEL большей строгостью, некоторые вещи в нем были продуманы лучше, в частности, агрегация.
Второй запрос находит поставщиков, поставляющих более десяти деталей. Обратите внимание, что BY встроен внутрь агрегатной функции. Это дает возможность вкладывать одну группировку в другую.
RETRIEVE INTO W(S.v#)
WHERE COUNT(S.p# BY S.v#) > 10Третий запрос находит поставщиков, у которых все детали стоят дороже, чем в среднем по всем поставщикам:
RETRIEVE INTO W(S.v#)
WHERE COUNT (S.p# BY S.v# WHERE S.price
>
AVG'(S.price BY S.p#))
= COUNT (S.p# BY S.v#)Здесь мы сравниваем количество деталей в разбивке по каждому поставщику (COUNT (S.p# BY S.s#)), но в первом выражении добавляем условие, которое выбирает только те детали, которые стоят дороже среднего. Штрих после AVG означает (как и в SEQUEL), что перед вычислением агрегатной функции из множества не удаляются дубликаты (разные поставщики могут продавать деталь по одной стоимости).
Это выглядит очень непривычно, но запросы получаются весьма изящными и компактными.
На дворе 74-й год. На конференции ACM SIGMOD состоялся «великий спор» между сторонниками реляционной и сетевой моделей. Астрономы знают, у них был свой великий спор, а у нас вот — свой.
При подготовке к выступлению Кодд проанализировал пример простого приложения, управляющего магазином. В решении в стиле CODASYL он насчитал около десятка типов операций, всего более 60 операторов. При реляционном подходе потребовалось всего 3 оператора!
Победили хорошие парни.
— Крис Дейт
«Великий спор» стал одним из переломных моментов в становлении реляционного подхода, но не был окончательной победой. Оппоненты снова отметили, что эффективность остается под вопросом.
Вторая половина 1970-x. Борьба за скорость
System R
Получив определенный опыт, команда System R начала создавать СУБД заново, уже без заглушек и временных решений. Отчетная статья System R: Relational Approach to Database Management вышла в 1976 году.
Команда RDS во главе с Доном Чемберлином создала вторую версию языка SEQUEL (SEQUEL 2: A Unified Approach to Data Definition, Manipulation, and Control, 1976). Она включала и DDL, и DML, в ней уже появилось ключевое слово HAVING. Поддерживались не только транзакции, но и операция ASSERT и триггеры. Были реализованы курсоры и представления. Язык значительно подрос.
В 1977 году произошел забавный юридический казус: оказалось, что имя SEQUEL уже занято какой-то компанией. Тогда Дон выкинул гласные и получилось SQL, что рифмовалось с APL, CPL и прочими трехбуквенными именами на PL.
Так язык получил современное название. Но по-прежнему есть два общепризнанных произношения: эс-ку-эл и сиквел. В английском это доставляет определенные хлопоты из-за артиклей: как правильно, an SQL или a SQL? В документации Постгреса не так давно разбирались, какой артикль оставить, и сошлись на an.
Команда RSS тем временем заменила временное решение собственным движком, который учитывал особенности системы.
И оказалось, что оптимизированный и скомпилированный запрос представляет собой очень короткий фрагмент кода, вызывающий RSS. Тогда родилась идея запоминать этот код и использовать его до тех пор, пока не меняется структура данных. Получился такой гибрид подготовленного оператора и JIT-компиляции (1979 год!). Это очень сильно экономило время для запросов, которые выполнялись неоднократно, и позволило показать на эталонных тестах производительность на уровне нереляционных систем — что было очень важно.
RSS (движок) состоял из 35000 строк кода на языке PL/S (это IBM-овская версия PL/I для системного программирования), а RDS (язык) — из 38000 строк на PL/I и 9000 строк на ассемблере.
System R работала на 32-битных машинах IBM System/370 (например, Model 168) с несколькими мегабайтами ОЗУ. По вычислительной мощности это где-то на уровне 486DX2. Размеры баз данных были в пределах 200 мегабайт, а количество одновременно работающих пользователей обычно не превышало 10 человек.
Постепенно System R стали показывать потенциальным заказчикам. Первыми клиентами стали авиационные компании — Pratt & Whitney, Boeing (база данных хранила поставщиков и детали — все как в примерах из учебника), Upjohn Drug Co. (производство лекарств; база данных хранила результаты клинических испытаний).
Клиенты остались довольны. Но исследовательским проектам всегда тяжело обратить на себя внимание и пробиться в промышленное производство. Флагманским продуктом IBM оставалась IMS, а основные силы были брошены на грандиозный проект-преемник под названием Eagle, который должен был уметь почти все. Попытки System R обратить на себя внимание привели лишь к тому, что в спецификацию этого монстра добавили еще и поддержку реляционной модели.
Команда System R никогда не была большой — несколько десятков человек в пике, — но рассказать обо всех у меня не получится. Однако двух людей я хотел бы отметить особо.
Первый — Джим Грей. Джим занимался (в числе прочего) всем, что связано с транзакциями и согласованностью. Смотрите, например, статьи The notions of consistency and predicate locks in a database system (1976 год) и The Recovery Manager of the System R Database Manager (1981 год).
Джим формализовал понятие транзакции (известное, конечно, и раньше); благодаря его работам появилось всем сейчас известная аббревиатура ACID, на которую все ссылаются, но мало кто понимает. Он исследовал гранулярность блокировок, двухфазную фиксацию.
В 2007 году Джим пропал без вести на своей яхте; с 2012 считается погибшим.
Патрисия Селинджер занималась оптимизатором System R. В своей работе Access Path Selection in a Relational Database Management System 1979 года она описала стоимостной оптимизатор.
Пат предложила математическую модель для вычисления стоимостей на основе статистики. Статистика предполагала равномерное распределение (гистограмм не было). Модель учитывала и доступ к страницам, и ресурсы процессора, а также принимала во внимание наличие буферного кеша. Было два метода соединения: Nested Loops и Merge Join (хеширования не было). Из-за соединения слиянием учитывался и порядок сортировки в узлах.
Патрисия предложила алгоритм динамического программирования и ряд эвристик для сокращения пространства поиска.
По-моему, это удивительно: в 1979 году был создан планировщик абсолютно современного уровня. Да, за прошедшие десятилетия планировщики шагнули вперед, но Патрисия абсолютно точно «угадала» тот подход, который мы до сих пор используем.
Ingres
Первопроходцами быть трудно. К сожалению, авторам INGRES не так повезло, они сделали менее точные предположения, чем их коллеги из IBM.
Они решили, что транзакция всегда состоит из одного оператора, а блокировки должны захватываться на уровне отношений, а не строк (Джим Грей удивлялся этому решению, и впоследствии оказалось, что он был прав).
Восстановление после сбоев было сочтено не слишком критичным — ну, академическая среда, — поэтому не были разработаны утилиты резервного копирования. Запросы каждый раз разбирались и оптимизировались заново — не было компиляции, как в System R.
Зато с самого начала было уделено внимание расширяемости — конек Стоунбрейкера, та идея, которую он привнес и в Постгрес.
Разработчиком оптимизатора был Юджин Вонг. Он боялся, что полноценная оптимизация будет слишком дорогой (PDP-11 — 16-битная машина; даже топовая модель PDP-11/70 уступала по мощности IBM 370, а на ней соединение 8 таблиц выполнялось в System R несколько секунд). Поэтому Вонг реализовал иной подход: сначала оптимизатор выбирал два отношения, выполнялось их соединение, и на основе полученных (точных!) цифр кардинальности выбиралось отношение для следующего соединения. В каких-то случаях этот подход работал хорошо, но в целом качество оптимизации сильно уступало System R. К тому же поддерживались только вложенные циклы.
Тем не менее система была установлена в нескольких сотнях мест — как правило, в университетах, куда попадала вместе с PDP-11 и Unix. Состояла она из 75000 строк кода на языке C.
Отчетная статья The Design and Implementation of INGRES вышла в 1976 году.
В 1977 году на полупустой еще поляне появился третий игрок: Ларри Эллисон с товарищами основал компанию SDL, позже переименованную в RSI.
Эллисон делал некий проект, названный Oracle, и ему нужна была СУБД. Он прочитал работы Кодда, узнал о прототипе, которым занималась IBM, и решил сделать собственную СУБД, но коммерческую. Чтобы было проще переманивать клиентов, он хотел, чтобы она была совместима с System R. Поэтому он взял язык SQL, синтаксис и BNF которого были опубликованы.
Он даже хотел получить список кодов ошибок, но не преуспел. Правда, один код все же промелькнул в статье Support for Repetitive Transactions and Ad-hoc Query in System R:
$SELECT DESCRIP,QOH,QOO INTO $DESCRIP,$QOH,$QOO
FROM PARTS WHERE PARTNO=$PARTNO;
IF SYR_CODE = 0 THEN
Write DESCRIP, QOH, QOO on terminal;
ELSE IF SYR_CODE = 100 THEN
Write 'THERE IS NO SUCH PART' on terminal;
ELSE CALL TROUBLE('SELECT');Теперь можете поразмышлять, почему в Oracle все коды ошибок отрицательные, кроме 100 для no_data_found.
В 1979 году выпустили вторую версию СУБД, написав ее на ассемблере PDP-11. Она унаследовала имя проекта: Oracle. Первую версию Эллисон решил пропустить — вторая выглядела солиднее.
Oracle v2 не поддерживала транзакций, не имела оптимизатора (таблицы просто соединялись в том порядке, в котором были указаны в запросе), ломалась каждый день так, что приходилось загружать данные заново. Но система работала на небольшой машине, предоставляла SQL, приносила клиентам пользу и поэтому продавалась.
Исходный код выглядел так, словно они прочитали статью про SQL, сели за компьютер и начали программировать. Все структуры данных напрямую отображали язык в аппаратуру безо всяких промежуточных слоев. «Так, вот у нас блок запроса, вот у него предложение select...».
— Роджер Бэмфорд
Так начался период коммерциализации.
1980-е. Коммерциализация и окончательная победа
Ingres
В чем Oracle был хорош, так это в агрессивном маркетинге. Утверждалось, что они создали самую быструю СУБД. Один бывший студент Стоунбрейкера усомнился в этом и решил сравнить производительность Oracle и INGRES, благо они работали на одной и той же машине — PDP-11. К удивлению команды INGRES, Oracle оказался позади.
Тогда-то стало понятно, что пора выходить на рынок. В 1980-м были найдены инвесторы и основана компания Relational Technology Inc. Основатели — Стоунбрейкер, Вонг и профессор из Беркли Лоренс Роу.
Университетская разработка продолжалась параллельно и независимо, студентов к работе над коммерческой версий не привлекали: студентам нужны исследования, а продукту нужна поддержка, багфиксинг и другие скучные вещи.
В первую очередь занялись всякими улучшениями: кешированием дерева разбора, написанием недостающих утилит, реализацией полноценных транзакций и гранулярных блокировок.
В 1982 году Боб Куи переписал оптимизатор на модель Пат Селенджер (Query Optimization in INGRES), и тогда стало совсем хорошо. (В Oracle стоимостной оптимизатор появился только в 1992 году, и тоже при участии Боба.)
Посмотрев на весь этот коммерческий движ, IBM решила запустить свой пробный шар. В подразделении IBM в Эндикотте освободилась группа разработчиков, и ей решили поручить сделать из System R продукт. Все мы понимаем разницу между продуктом и прототипом, сделанным учеными на коленке.
Группа не была знакома с базами данных, так что, трезво оценив свои силы, они решили взять код System R и причесать его, доведя до промышленного уровня.
И вот в 1981 году IBM объявила о выходе своей первой коммерческой реляционной СУБД — SQL/DS, — предназначенной для младших машин серии.
Увидев интерес заказчиков к реляционным технологиям, IBM отказалась от полуживого колосса Eagle и бросила основную команду разработчиков из Санта-Терезы (лаборатория в Сан-Хосе) на реляционную базу крупного масштаба для MVS (Multiple Virtual Storage; ныне z/OS). На этот раз код был переписан с нуля, но вдохновение разработчики снова черпали в коде System R, иначе они не выпустили бы первую версию так быстро: официальный релиз состоялся в 1983.
Для понимания: в это время IMS принадлежало 50% рынка СУБД, хотя новые продажи и падали. То есть старые системы не то, чтобы быстро сдавали свои позиции, но переход IBM на реляционную сторону убедил всех, что будущее именно за реляционными базами.
...IBM благословил реляционные СУБД. Все понимали: если уж IBM что-то решил,
то теперь это стратегическое направление.
— Лоренс Роу
Ну а кульминацией, на которой я бы хотел поставить точку, стало появление первого стандарта SQL в 1986 году (ANSI), в 1987 году он был принят как международный (ISO).
Стандарт был полностью продиктован реализацией System R. Представитель комитета изучил System R и все аккуратно записал в формальном виде, включая все странности и случайные решения, вызванные простой нехваткой времени на реализацию (вроде того, что GROUP BY не допускается в запросах с UNION).
Получился небольшой документ на 120 страниц. В нем еще не было дат, первичных и внешних ключей, внешних соединений (был только синтаксис с запятой). Занятно, что говорилось про единственный уровень изоляции — Serializable, а остальные появились уже в стандарте 92-го года. Тем не менее язык включал такие операторы и конструкции, как BETWEEN, IN, EXISTS, LIKE, IS NULL, подзапросы, курсоры, SELECT ... FROM ... WHERE ... GROUP BY ... HAVING.
Принятие стандарта поставило точку в вопросе о том, какой язык останется на рынке. Ingres перешел на SQL в конце 1980-х. Postgres, который Стоунбрейкер запустил в 1986 году, использовал PostQuel, но в 1994 году, после передачи проекта сообществу, сразу перешел на SQL. О былых временах напоминает только библиотека libPQ, буквы PQ в имени которой означают не что иное, как PostQuel.
