Укажите что такое запись в реляционной базе данных
Реляционные базы данных, как мы уже знаем, состоят из таблиц. Каждая таблица состоит из столбцов (их называют полями или атрибутами) и строк (их называют записями или кортежами). Таблицы в реляционных базах данных обладают рядом свойств. Основными являются следующие:
Все будет понятнее на примере. Предположим, мы захотели создать базу данных для форума. У форума есть зарегистрированные пользователи, которые создают темы и оставляют сообщения в этих темах. Эта информация и должна храниться в базе данных.
Теоретически (на бумаге) мы можем все это расположить в одной таблице, например, так:
Но это противоречит свойству атомарности (одно значение в одной ячейке), а в столбцах Темы и Сообщения у нас предполагается неограниченное количество значений. Значит, нашу таблицу надо разбить на три: Пользователи, Темы и Сообщения.
Кроме того, мы знаем, что каждое сообщение обязательно относится к какой-либо теме. А как это можно узнать из наших таблиц? Никак. Для решения этих проблем, в реляционных базах данных существуют ключи.
Суррогатный ключ представляет собой дополнительное поле в базе данных. Как правило, это порядковый номер записи (хотя вы можете задавать их на свое усмотрение, контролируя, чтобы они были уникальны). Давайте внесем поля первичных ключей в наши таблицы:
Теперь каждая запись в наших таблицах уникальна. Нам осталось установить соответствие между темами и сообщениями в них. Делается это также при помощи первичных ключей. В таблицу сообщения мы добавим еще одно поле:
Последний нюанс. Предположим, у нас добавился новый пользователь, и зовут его тоже Вася:
Как мы узнаем, какой именно Вася оставил сообщения? Для этого поля автор в таблицах «Темы» и «Сообщения» мы сделаем также внешними ключами:
Наша база данных готова. Схематично ее можно представить так:
В нашей маленькой базе данных всего три таблички, а если бы их было 10 или 100? Понятно, что сразу невозможно представить все таблицы, поля и связи, которые нам могут понадобиться. Именно поэтому проектирование базы данных начинается с ее концептуальной модели, которую мы и рассмотрим в следующем уроке.
Видеоуроки php + mysql
Если этот сайт оказался вам полезен, пожалуйста, посмотрите другие наши статьи и разделы.
BestProg
Базовые понятия реляционной модели данных
Содержание
Поиск на других ресурсах:
1. Какие есть базовые понятия реляционной модели данных?
Как известно, реляционная модель данных основывается на сохранении данных в виде взаимосвязанных таблиц. Связь между таблицами может быть реализована по некоторому полю и называется отношением (relation).
Реляционная модель данных использует следующие основные понятия:
2. Что такое тип данных в реляционной модели данных?
Тип данных есть характеристикой объекта в языке программирования. Таким объектом может выступать переменная, константа и т.п. Тип данных определяет допустимое множество значений, которые может принимать переменная величина или объект.
В системах управления базами данных тип данных имеет такое самое значение как и языках программирования.
Пример. Пусть задана таблица Worker, описывающая данные о работнике предприятия.
В вышеприведенной таблице целесообразно установить следующий тип данных для каждого поля:
3. Какие типы данных поддерживаются системами управления базами данных?
Современные СУБД поддерживают следующие основные типы данных:
4. Домены в реляционной модели данных
Домен – это множество отдельных допустимых значений данных, которые:
Пример. Пусть дана таблица Worker, описывающая данные о работнике.
В домене «Идентификационный код» допустимыми являются строки из цифр, которые имеют строго 10 разрядов. В домене «Пол» возможны только 2 значения. В домене «Разряд» могут быть целочисленные значения от 1 до 6.
5. Атрибуты в реляционной модели данных
Атрибуты – это столбцы таблицы (поля таблицы). Атрибуты имеют имена. По имени атрибута осуществляется обращение к таблице.
Пример. В таблице Worker (см. п. 4) названия атрибутов следующие:
6. Что такое схема отношения? Что такое схема базы данных?
Схема отношения – это список имен атрибутов отношения с указанием имен типов.
Пример. Для таблицы Worker схема отношения будет приблизительно следующей:
Множество именованных схем отношения, называется схемой базы данных.
7. Что такое степень отношения?
Количество атрибутов в таблице называется степенью отношения. Для примера (см. п. 4) таблицы Worker степень отношения равна 6 (таблица имеет 6 полей).
Унарное отношение – это отношение степени один. Бинарное отношение – это отношение степени два. Тернарное отношение – это отношение степени три. n-арное отношение – это отношение степени n.
8. Что такое кортеж в базах данных?
Кортеж рассматривается для конкретной (данной) схемы отношения. В такой схеме кортеж есть множество пар, которые представлены следующим образом:
где имя_атрибута – имя конкретного атрибута.
Например. Пусть задана таблица Worker с такими данными
Схема отношения для данной таблицы будет следующая:
Тогда кортеж, который отвечает первой строке таблицы Worker будет иметь вид:
Таким самым образом можно определить кортеж, который соответствует второй строке таблицы Worker а также и следующим строкам таблицы.
9. Что называется кардинальным числом или мощностью отношения?
Кардинальное число – это количество кортежей. В таблице Worker (см. п. 8) кардинальное число равно 7. Кардинальное число еще называют мощностью отношения.
10. Что собою представляет пустое значение (NULL) в базе данных?
Существуют случаи, когда в таблице базы данных некоторые значения еще неизвестны на данный момент времени. Такие значения называются пустыми значениями и могут быть заполнены со временем (позже). Для задавания пустых значений, в базе данных используется слово NULL. Системы управления базами данных допускают использования значения NULL для задавания данных, которые могут быть заполнены позже.
Следует заметить, что значение NULL не является нулем и не является пустой строкой.
Например. В таблице Worker (п. 8) возможна ситуация, когда работник еще не имеет разряда. В этом случае в соответствующей ячейке нужно ввести значение NULL. Как только работнику будет присвоен некоторый разряд, значение NULL будет заменено этим новым значением.
11. Что такое ключи отношения? Что такое первичный ключ?
Важным условием любой базы данных есть то, что в ней не должно быть двух одинаковых записей. Или другими словами, в таблице базы данных не должно быть двух кортежей, которые содержат одинаковые значения. Во избежание этой проблемы, используются первичные ключи.
Первичный ключ – это специальное дополнительное поле (атрибут) таблицы, которое создается для обеспечения уникальности идентификации записей таблицы. Основная цель создания первичного ключа – предотвратить дублирование (повторение) записей таблицы.
Например. Пусть дана таблица Worker (см. п.8). Чтобы не повторялись записи, в этой таблице может быть создано дополнительное поле (атрибут) с именем, например, ID_Worker. Тип этого поля может быть выбран как счетчик (counter), который автоматически увеличивается при добавлении новой записи в таблицу.
12. Что такое простой и составной (сложный) ключи?
Простой ключ – это ключ, который содержит только один атрибут (поле). Сложный или составной ключ– это ключ, который содержит несколько атрибутов, то есть состоит из нескольких полей, значения в которых не могут повторяться.
Пример. Пусть дана таблица Student, содержащая данные о студенте. Таблица содержит следующие поля:
| Название поля | Тип | Описание |
| ID_Student | Целое число, int | Уникальный идентификатор поля, счетчик, первичный ключ, простой ключ |
| Num_book | Целое число, int | Номер зачетной книжки |
| Name | Строка с 100 символов, char(100) | Фамилия и имя студента |
| Course | Целое число, int | Курс, на котором учится студент |
В этой таблице поле ID_Student есть первичным ключом, которое обеспечивает уникальность. Это поле есть счетчиком. При добавлении нового студента в таблицу, значение счетчика увеличивается на некоторое число, как правило на 1. Если удалить студента из таблицы, максимальное значение счетчика уже не уменьшается. Таким образом обеспечивается уникальное число, которое соответствует данному студенту.
В таблице Student составным ключом может быть комбинация полей (атрибутов) ID_Student и Num_book (номер зачетной книжки). Однако, в данной таблице такая комбинация не имеет смысла, поскольку поле ID_Student и без того обеспечивает уникальность.
13. Что такое искусственный (суррогатный) ключ?
Искусственный ключ создается самой СУБД или пользователем. Этот ключ не содержит никакой информации. Искусственный ключ используется для создания уникальных идентификаторов строк. Создание идентификатора строки осуществляется таким образом, что сущность строки описывается полностью. Такой метод позволяет однозначно идентифицировать конкретный элемент (значение).
Система управления базами данных поддерживает искусственный ключ так, что он невидим для пользователя.
14. Что такое естественной ключ?
Естественной ключ базируется на атрибутах (полях), которые имеют смысл. Значение в таких атрибутах (полях) не могут повторяться по своей сущности.
Использование естественных ключей позволяет получить более компактную форму таблиц для представления данных.
Пример 1. В таблице Worker (см. п.8) поле «Идентификационный код» есть уникальным, так как не может быть двух людей с одинаковым идентификационным кодом. Это поле и есть естественном ключом.
Пример 2. В таблице Student поле Num_book (№ зачетной книжки) есть уникальным по своей природе. Не может быть двух студентов с одинаковым номером зачетной книжки.
15. Какие преимущества и недостатки использования естественных ключей?
Преимуществом использования естественных ключей есть то, что они несут информацию, и потому не нужно добавлять в таблицу дополнительных полей. Естественные ключи позволяют избегнуть избыточной (неинформативной) информации, которая используется только для связи между таблицами базы данных.
Основные недостатки естественных ключей:
Как работает реляционная БД
Реляционные базы данных (РБД) используются повсюду. Они бывают самых разных видов, от маленьких и полезных SQLite до мощных Teradata. Но в то же время существует очень немного статей, объясняющих принцип действия и устройство реляционных баз данных. Да и те, что есть — довольно поверхностные, без особых подробностей. Зато по более «модным» направлениям (большие данные, NoSQL или JS) написано гораздо больше статей, причём куда более глубоких. Вероятно, такая ситуация сложилась из-за того, что реляционные БД — вещь «старая» и слишком скучная, чтобы разбирать её вне университетских программ, исследовательских работ и книг.
На самом деле, мало кто действительно понимает, как работают реляционные БД. А многие разработчики очень не любят, когда они чего-то не понимают. Если реляционные БД используют порядка 40 лет, значит тому есть причина. РБД — штука очень интересная, поскольку в ее основе лежат полезные и широко используемые понятия. Если вы хотели бы разобраться в том, как работают РБД, то эта статья для вас.
Сразу нужно подчеркнуть: из этого материала вы НЕ узнаете, как можно использовать БД. Однако для усвоения материала вы должны уметь написать хотя бы простенький запрос на соединение и CRUD-запрос. Этого вполне достаточно для понимания статьи, остальное будет объяснено.
1. Основы
Давным-давно (в далёкой-далёкой галактике) разработчики должны были держать в голове точное количество операций, которые они кодят. Они всем сердцем чувствовали алгоритмы и структуры данных, поскольку не могли себе позволить тратить впустую ресурсы процессора и памяти на своих медленных компьютерах прошлого. В этой главе мы вспомним некоторые концепции, которые необходимы для понимания работы БД.
1.1. О(1) против О(n 2 )
Сегодня многие разработчики не особо задумываются о временнόй сложности алгоритмов… и они правы! Но когда приходится работать с большим объёмом данных, или если нужно экономить миллисекунды, то временнáя сложность становится крайне важна.
Временнáя сложность используется для оценки производительности алгоритма, как долго будет выполняться алгоритм для входных данных определённого размера. Обозначается временнáя сложность как «О» (читается как «О большое»). Это обозначение используется вместе с функцией, описывающей количество операций, осуществляемых алгоритмом для обработки входных данных.
Например, если сказать «этот алгоритм есть О большое от некоторой функции», то это означает, что для определённого объёма входных данных алгоритму нужно выполнить количество операций, пропорциональное значению функции от этого определённого объёма данных.
Здесь важен не объём данных, а динамика увеличения количества операций с ростом объёма. Временнáя сложность не позволяет вычислить точное количество, но зато представляет собой хороший способ оценки.
1.1.3. Ещё немного подробностей
1.2. Сортировка слиянием
Что вы делаете, когда вам нужно отсортировать коллекцию? Вызываете функцию sort(), верно? Но понимаете ли вы, как она работает?
Есть несколько хороших алгоритмов сортировки, но здесь мы рассмотрим только один из них: сортировку слиянием. Возможно, сейчас вам это знание не кажется полезным, но вы поменяете мнение после глав про оптимизацию запросов. Более того, понимание работы этого алгоритма поможет понять принцип важной операции — соединение слиянием.
В основе алгоритма сортировки слиянием лежит одна хитрость: для слияния двух отсортированных массивов размером N/2 каждый требуется всего лишь N операций, называющихся слиянием.
Рассмотрим пример операции слияния:
Пример псевдокода сортировки слиянием:
В три этапа исходный массив делится на подмассивы, состоящие из одного элемента. Вообще, количество этапов деления определяется как log(N) (в данном случае N=8, log(N) = 3). Идея в том, чтобы на каждом этапе делить входящие массивы пополам. То есть описывается логарифмом с основанием 2.
1.2.3. Фаза сортировки
1.2.4. Возможности сортировки слиянием
1.3. Массив, дерево и хэш-таблица
Итак, с временнόй сложностью и сортировкой разобрались. Теперь давайте обсудим три структуры данных, на которых держатся современные БД.
Двумерный массив — простейшая структура данных. Таблица может быть представлена в виде массива:
Здесь каждая строка представляет собой какой-то объект, колонка — свойство объекта. Причём разные колонки содержат разные типы данных (целые числа, строки, даты и т.д.).
Это очень удобный способ хранения и визуализации информации, но очень неподходящий для случаев, когда нужно найти какое-то конкретное значение. Допустим, вам нужно найти всех сотрудников, работающих в Великобритании. Для этого придётся просмотреть все строки, чтобы найти те, где имеется значение “UK”. На это потребуется N операций (N — количество строк). Не так уж и плохо, но хорошо бы и побыстрее. И здесь нам помогут деревья.
Примечание: большинство современных СУБД используют продвинутые виды массивов, позволяющие эффективнее хранить таблицы (например, на основе куч или индексов). Но это не решает проблему скорости поиска по колонкам.
1.3.2. Дерево и индекс БД
Каждый узел представляет собой указатель на строку в связанной таблице.
Но вернёмся к нашей проблеме.
Допустим, у нас есть строковые значения, соответствующие названиям разных государств. Соответственно и узлы дерева содержат строковые ключи. Чтобы найти сотрудников, работающих в “UK”, нужно просмотреть все узлы, чтобы найти соответствующий, и извлечь из него ID всех строк, содержащих данное значение. В отличие от поиска по массиву, здесь нам потребуется всего log(N) операций. Описанная конструкция называется индексом БД.
Такой индекс можно создать для любой группы колонок (для строковых, целочисленных, их комбинаций, дат и т.д.), если у вас есть функция для сравнения ключей (т.е. групп колонок). Таким образом вы можете распределить ключи в определённом порядке.
Несмотря на высокую скорость поиска, дерево плохо работает в случаях, когда нужно получить несколько элементов в пределах двух значений. Временнáя сложность будет равна О(N), потому что нам придётся просмотреть каждый узел и сравнить его с заданными условиями. Более того, данная процедура требует большого количества операций ввода/вывода, ведь нужно считывать всё дерево. То есть нам нужен более эффективный способ запроса диапазона. В современных БД для этого используется модифицированная версия дерева — В+дерево. Его особенность в том, что информацию (ID строк связанной таблицы) хранят лишь самые нижние узлы («листья»), а все остальные узлы предназначены для оптимизации поиска по дереву.
Как видите, здесь вдвое больше узлов. «Узлы принятия решений» помогают найти нужные узлы, содержащие ID строк в таблице. Но сложность поиска всё ещё равна О(log(N)) (добавился один уровень узлов). Однако главной особенностью B-дерева является то, что «листья» образуют наследственные связи.
Подробнее о В+деревьях можно почитать на Википедии, а также в статьях (один, два) от ведущих разработчиков MySQL. В них рассказывается о том, как InnoDB (движок MySQL) работает с индексами.
Здесь 10 блоков, в качестве хэш-функции брался модуль 10 от значения ключа. То есть для поиска нужного блока достаточно знать последнюю цифру значения ключа: если это 0, то элемент хранится в корзине 0, если 1, то в корзине 1, и т.д. В качестве функции сравнения используется операция сравнения двух целочисленных.
Как видите, скорость поиска зависит от искомого значения. Изменим хэш-функцию, будет вычислять хэши по модулю 1 000 000 (то есть берём последние 6 цифр). В этом случае на поиск элемента 59 уйдёт лишь одна операция, поскольку в блоке 000059 нет никаких элементов. Поэтому крайне важно подобрать удачную хэш-функцию, которая будет генерировать блоки с очень небольшим количеством элементов.
Массив против хэш-таблицы
2. Общий обзор
Мы рассмотрели базовые компоненты БД. Теперь давайте отойдём назад и окинем взглядом всю картину.
На самом деле, существует куча разных представлений о том, как может выглядеть структура БД. Так что не надо зацикливаться на данной иллюстрации. Нужно лишь усвоить, что БД состоит из различных компонентов, взаимодействующих между собой.
3. Диспетчер клиентов
Используется для управления соединениями с клиентами — веб-серверами или конечными пользователями/приложениями. Диспетчер клиентов обеспечивает разные способы доступа к БД с помощью как всем известных API (JDBC, ODBC, OLE-DB и т.д.), так и с помощью проприетарных.
4. Диспетчер запросов
4.1. Парсер запросов
Каждый SQL-оператор отправляется в парсер и проверяется на правильность синтаксиса. Если вы сделаете ошибку в запросе, то парсер его отклонит. Например, напишете SLECT вместо SELECT.
Но этим функции парсера не ограничиваются. Он также проверяет, чтобы ключевые слова использовались в правильном порядке. Например, если WHERE будет идти до SELECT, то запрос будет отклонён.
В ходе всех этих проверок SQL-запрос трансформируется во внутреннее представление (чаще всего в дерево). Если всё в порядке, то оно отправляется в рерайтер запросов.
4.2. Рерайтер запросов
4.3. Статистика
Прежде чем перейти к рассмотрению оптимизирования запросов, давайте поговорим о статистике, поскольку без неё БД становится совершенно безмозглой. Если вы не скажете ей проанализировать собственные данные, она этого и не сделает, сделав очень плохие допущения.
Какого рода информация нужна БД?
Сначала давайте вспомним, как БД и ОС хранят данные. Для этого они используют такие минимально возможные сущности, как страницы или блоки (размером по 4 или 8 Кбайт по умолчанию). Если вам нужно сохранить 1 Кбайт, то на это всё-равно уйдёт целая страница. То есть вы попусту тратите много места в памяти и на диске.
Очень большое значение имеет статистика по каждой колонке. Например, нам нужно в таблице объединить две колонки: «фамилия» и «имя». Благодаря статистике БД знает, что в ней содержится 1 000 уникальных значений «имя» и 1 000 000 — «фамилия». Поэтому база объединит данные именно в таком порядке — «фамилия, имя», а не «имя, фамилия»: это требует гораздо меньше операций сравнения, поскольку вероятность совпадения фамилий гораздо ниже, и в большинстве случаев для сравнения достаточно брать 2-3 первые буквы фамилии.
Если вы уже знакомы с динамическим программированием или алгоритмизацией, можете поиграться с этим алгоритмом:
Но если запрос очень велик, или если нам нужно крайне быстро получить ответ, используется другой класс алгоритмов — жадные алгоритмы.
В данном случае план исполнения запроса строится пошагово с помощью некоего правила (эвристики). Благодаря ему жадный алгоритм ищет наилучшее решение для каждого этапа по отдельности. План начинается с оператор JOIN, а затем на каждом этапе добавляется новый JOIN в соответствии с правилом.
Не будем углубляться в подробности, но при хорошем моделировании сложности сортировки N*log(N) данная проблема может быть легко решена. Временнáя сложность алгоритма равна О(N*log(N)) вместо О(3 N ) для полной версии с динамическим программированием. Если у вас большой запрос с 20 объединениями, то это будет 26 против 3 486 784 401. Большая разница, верно?
Но есть нюанс. Мы предполагаем, что если найдём наилучший способ объединения двух таблиц, то получим самую низкую стоимость при объединении результатом предыдущих объединений со следующими таблицами. Однако даже если A JOIN B будет самым дешёвым вариантом, то (A JOIN C) JOIN B может иметь стоимость ниже, чем (A JOIN B) JOIN C.
Так что если вам позарез нужно найти самый дешёвый план всех времён и народов, то можно посоветовать многократно прогонять жадные алгоритмы с использованием разных правил.
Если вы уже сыты по горло всеми этими алгоритмами, то можете пропустить эту главу. Она не обязательна для усвоения всего остального материала.
Многие исследователи занимаются проблемой поиска наилучшего плана исполнения запроса. Зачастую пытаются найти решения для каких-то конкретных задач и шаблонов. Например, для звездообразных объединений, исполнения параллельных запросов и т.д.
Ищутся варианты замены динамического программирования для исполнения больших запросов. Те же жадные алгоритмы являются подмножеством эвристических алгоритмов. Они действуют сообразно правилу, запоминают результат одного этапа и используют его для поиска лучшего варианта для следующего этапа. И алгоритмы, которые не всегда используют решение, найденное для предыдущего этапа, называются эвристическими.
В БД используются и такие эвристические алгоритмы, как симулированная нормализация (Simulated Annealing), итеративное улучшение (Iterative Improvement), двухфазная оптимизация (Two-Phase Optimization). Но не факт, что они применяются в корпоративных системах, возможно, их удел — исследовательские продукты.
4.4.6. Настоящие оптимизаторы
Тоже необязательная глава, можно и пропустить.
Прочие условия (GROUP BY, DISTINCT и т.д.) обрабатываются простыми правилами.
4.4.7. Кэш плана запросов
Поскольку составление плана требует времени, большинство БД хранят план в кэше плана запросов. Это помогает избежать ненужных вычислений одних и тех же этапов. БД должна знать, когда именно ей нужно обновить устаревшие планы. Для этого устанавливается некий порог, и если изменения в статистике его превышают, то план, относящийся к данной таблице, удаляется из кэша.
Исполнитель запросов
На данном этапе наш план уже оптимизирован. Он перекомпилируется в исполняемый код и, если ресурсов достаточно, исполняется. Операторы, содержащиеся в плане (JOIN, SORT BY и т.д.) могут обрабатываться как последовательно, так и параллельно, решение принимает исполнитель. Для получения и записи данных он взаимодействует с диспетчером данных.
5. Диспетчер данных
5.1. Диспетчер кэша
Как уже не раз говорилось, самым узким местом в БД является дисковая подсистема. Поэтому для увеличения производительности используется диспетчер кэша.
Однако тут мы сталкиваемся с другой проблемой. Диспетчеру кэша нужно положить данные в память ДО того, как они понадобятся исполнителю запросов. Иначе тому придётся ждать их получения с медленного диска.
Исполнитель запросов знает, какие данные ему понадобятся, поскольку ему известен весь план, то, какие данные содержатся на диске и статистика.
Когда исполнитель обрабатывает первую порцию данных, он просит диспетчер кэша заранее подгрузить следующую порцию. А когда переходит к её обработке, то просит ДК подгрузить третью и подтверждает, что первую порцию можно удалить из кэша.
Диспетчер кэша хранит эти данные в буферном пуле. Он также добавляет к ним сервисную информацию (триггер, latch), чтобы знать нужны ли они ещё в буфере.
Иногда исполнитель не знает, какие данные ему будут нужны, или некоторые БД не имеют подобного функционала. Тогда используется спекулятивное упреждение (speculative prefetching) (например, если исполнитель запрашивает данные 1, 3, 5, то наверняка запросит в будущем 7, 9, 11) или последовательное упреждение (sequential prefetching) (в данном случае ДК просто подгружает с диска следующую по порядку порцию данных.
Для контроля качества упреждения в современных БД используется метрика «коэффициент использования буфера/кэша» (buffer/cache hit ratio). Она показывает, как часто запрашиваемые данные оказываются в кэше, без необходимости обращения к диску. Однако низкое значение коэффициента не всегда говорит о плохом использовании кэша. Подробнее об этом можно почитать в документации Oracle.
Нельзя забывать, что буфер ограничен объёмом доступной памяти. То есть для загрузки одних данных нам приходится периодически удалять другие. Заполнение и очистка кэша потребляет часть ресурсов дисковой подсистемы и сети. Если у вас есть часто исполняемый запрос, то было бы контрпродуктивно каждый раз загружать и очищать используемые им данные. Для решения данной проблемы в современных БД используется стратегия замены буфера.
5.1.2. Стратегии замены буфера
Большинство БД (по крайне мере, SQL Server, MySQL, Oracle и DB2) используют для этого алгоритм LRU (Least Recently Used). Он предназначен для поддержания в кэше тех данных, которые недавно использовались, а значит велика вероятность, что они могут понадобиться снова.
Чтобы этого не произошло, в некоторых БД используются специальные правила. Согласно документации Oracle:
«Для очень больших таблиц обычно используется прямой доступ, то есть блоки данных считываются напрямую, чтобы избежать переполнения буфера кэша. Для таблиц среднего размера может использоваться как прямой доступ, так и чтение из кэша. Если система решит использовать кэш, то БД помещает блоки данных в конец списка LRU, чтобы предотвратить очистку буфера».
Также используется улучшенная версия LRU — LRU-K. В SQL Server применяется LRU-K при К = 2. Суть этого алгоритма в том, что при оценке ситуации он учитывает больше информации о прошлых операциях, а не только запоминает последние использованные данные. Буква К в названии означает, что алгоритм принимает во внимание, какие данные использовались последние К раз. Им присваивается определённый вес. Когда в кэш загружаются новые данные, то старые, но часто используемые не удаляются, потому что их вес выше. Конечно, если данные больше не используются, то они всё-таки будут удалены. И чем дольше данные остаются невостребованными, тем сильнее уменьшается со временем их вес.
Вычисление веса довольно накладно, поэтому в SQL Server используется LRU-K при К равном всего лишь 2. При некотором увеличении значения К эффективность алгоритма улучшается. Вы можете ближе познакомиться с ним благодаря одной работе 1993-го года.
Конечно, LRU-K не единственное решение. Существуют также 2Q и CLOCK (оба похожи на LRU-K), MRU (Most Recently Used, в котором используется логика LRU, но применяется другое правило, LRFU (Least Recently and Frequently Used) и т.д. В некоторых БД можно выбирать, какой алгоритм будет использоваться.
Мы говорили только о буфере чтения, но БД используют и буферы записи, которые накапливают данные и сбрасывают на диск порциями, вместо последовательной записи. Это позволяет экономить операции ввода/вывода.
Помните, что буферы хранят страницы (неделимые единицы данных), а не ряды из таблиц. Страница в буферном пуле называется «грязной», если она модифицирована, но не записана на диск. Есть много разных алгоритмов, с помощью которых выбирается время записи грязных страниц. Но это во многом связано с понятием транзакций.
5.2. Диспетчер транзакций
В его обязанности входит отслеживание, чтобы каждый запрос исполнялся с помощью собственной транзакции. Но прежде чем поговорить о диспетчере, давайте проясним концепцию ACID-транзакций.
5.2.1. «Под кислотой» (игра слов, если кто не понял)
Например, транзакция А выполняет
Потом транзакция Б добавляет в таблицу Х и коммитит новые данные. И если после этого транзакция А снова выполняет count(1), то результат будет уже другим.
Это называется грязным чтением.
Большинство БД добавляют собственные уровни изолированности (например, на основе снэпшотов, как в PostgreSQL, Oracle и SQL Server). Также во многих БД не реализованы все четыре вышеописанных уровня, особенно чтение незафиксированных данных.
Пользователь или разработчик может сразу же после установления соединения переопределить уровень изолированности по умолчанию. Для этого достаточно добавить очень простую строчку кода.
5.2.2. Управление параллелизмом
Главное, для чего нам нужны изолированность, согласованность и атомарность, это возможность осуществлять операции записи над одними и теми же данными (добавлять, обновлять и удалять).
Если все транзакции будут только читать данные, то смогут работать одновременно, не влияя на другие транзакции.
Если хотя бы одна транзакция изменяет данные, читаемые другими транзакциями, то БД нужно найти способ скрыть от них эти изменения. Также нужно удостовериться, что сделанные изменения не будут удалены другими транзакциями, которые не видят изменённых данных.
Это называется управлением параллелизмом.
Проще всего просто выполнять транзакции поочерёдно. Но такой подход обычно неэффективен (задействуется лишь одно ядро одного процессора), и к тому же теряется возможность масштабирования.
5.2.3. Диспетчер блокировок
Для решения вышеописанной проблемы во многих БД используются блокировки (locks) и/или версионность данных.
Если транзакции нужны какие-то данные, то она блокирует их. Если другой транзакции они тоже потребовались, то её придётся ждать, пока первая транзакция не снимет блокировку.
Это называется эксклюзивной блокировкой.
Но слишком расточительно использовать эксклюзивные блокировки в случаях, когда транзакциям нужно всего лишь считать данные. Зачем мешать чтению данных? В таких случаях используются совместные блокировки. Если транзакции нужно считать данные, они применяет к ним совместную блокировку и читает. Это не мешает другим транзакциям тоже применять совместные блокировки и читать данные. Если же какой-то из них нужно изменить данные, то ей придётся подождать, пока все совместные блокировки не будут сняты. Только после этого она сможет применить эксклюзивную блокировку. И тогда уже всем остальным транзакциям придётся ждать её снятия, чтобы считывать эти данные.
Диспетчер блокировок — это процесс, который применяет и снимает блокировки. Они хранятся в хэш-таблице (ключами являются блокируемые данные). Диспетчер знает для всех данных, какие транзакции применили блокировки или ждут их снятия.
Взаимная блокировка (deadlock)
Использование блокировок может привести к ситуации, когда две транзакции бесконечно ожидают снятия блокировок:
Здесь транзакция А эксклюзивно заблокировала данные 1 и ожидает освобождения данных 2. В то же время транзакция Б эксклюзивно заблокировала данные 2 и ожидает освобождения данных 1.
Представим хэш-таблицу в виде диаграммы, как на иллюстрации выше. Если на диаграмме присутствует циклическая связь, то взаимная блокировка подтверждена. Но поскольку проверять на наличие циклов достаточно дорого (ведь диаграмма, на которой отражены все блокировки, будет весьма большой), зачастую используется более простой подход: использование таймаутов. Если блокировка не снимается в течение определённого времени, значит транзакция вошла в состояние взаимной блокировки.
Перед наложением блокировки диспетчер также может проверить, не приведёт ли это к возникновению взаимной блокировки. Но чтобы однозначно на это ответить, тоже придётся потратиться на вычисления. Поэтому подобные предпроверки зачастую представлены в виде набора базовых правил.
Проще всего полная изолированность обеспечивается, когда блокировка применяется в начале и снимается в конце транзакции. Это означает, что транзакции перед началом приходится дожидаться снятия всех блокировок, а применённые ею блокировки снимаются лишь по завершении. Такой подход можно применять, но тогда теряется куча времени на все эти ожидания снятия блокировок.
До транзакции А X = 1 и Y = 1. Она обрабатывает данные Y = 1, которые были изменены транзакцией В уже после начала транзакции А. В связи с принципом изолированности транзакция А должна обрабатывать Y = 2.
Конечно, реальные БД используют более сложные системы, больше видов блокировок и с большей гранулярностью (блокировки строк, страниц, партиций, таблиц, табличных пространств), но суть та же.
Оба подхода — блокировки и версионность — имеют плюсы и минусы, многое зависит от того, в какой ситуации они применяются (больше чтений или больше записей). Можете изучить очень хорошую презентацию, посвящённую реализации мультиверсионного управления параллелизмом в PostgreSQL.
В некоторых БД (DB2 до версии 9.7, SQL Server) используются только блокировки. Другие, вроде PostgreSQL, MySQL и Oracle, используются комбинированные подходы.
Примечание: версионность оказывает интересное влияние на индексы. Иногда в уникальном индексе появляются дубликаты, индекс может содержаться больше записей, чем строк в таблице и т.д.
Если часть данных считывается при одном уровне изолированности, а потом он увеличивается, то вырастает количество блокировок, а значит теряется больше времени на ожидания транзакций. Поэтому большинство БД не используют по умолчанию максимальный уровень изолированности.
Как обычно, за более подробной информацией обращайтесь к документации: MySQL, PostgreSQL, Oracle.
5.2.4. Диспетчер логов
Как мы уже знаем, ради увеличения производительности БД хранит часть данных в буферной памяти. Но если сервер падает во время коммита транзакции, то находящиеся в памяти данные будут потеряны. А это нарушает принцип надёжности транзакций.
Конечно, можно всё писать на диск, но при падении вы останетесь с недописанными данными, а это уже нарушение принципа атомарности.
Любые изменения, записанные транзакцией, должны быть отменены или завершены.
В больших БД с многочисленными транзакциями теневые копии/страницы занимают невероятно много места в дисковой подсистеме. Поэтому в современных БД используется лог транзакции. Он должен размещаться в защищённом от сбоев хранилище.
За выполнением этих правил следит диспетчер логов. Логически он расположен между диспетчером кэша и диспетчером доступа к данным. Диспетчер логов регистрирует каждую операцию, выполняемую транзакциями, до момента записи на диск. Вроде верно?
НЕВЕРНО! После всего, через что мы с вами прошли в этой статье, пора бы уже запомнить, что всё связанное с БД подвергается проклятью «эффекта базы данных». Если серьёзно, то проблема в том, что нужно найти способ писать в лог, при этом сохраняя хорошую производительность. Ведь если лог транзакций работает медленно, то он тормозит все остальные процессы.
В 1992 год исследователи из IBM создали расширенную версию WAL, которую назвали ARIES. В том или ином виде ARIES используется большинством современных БД. Если вы захотите поглубже изучить этот протокол, можете проштудировать соответствующую работу.
Как это возможно? Чтобы ответить на это, нужно сначала разобраться с тем, какая информация сохраняется в логе.
Насколько известно, UNDO не используется только в PostgreSQL. Вместо этого используется сборщик мусора, убирающий старые версии данных. Это связано с реализацией версионности данных в этой СУБД.
Чтобы вам было легче представить состав записи в логе, вот визуальный упрощённый пример, в котором выполняется запрос UPDATE FROM PERSON SET AGE = 18;. Пусть он исполняется в транзакции номер 18:
Каждый лог имеет уникальный LSN. Связанные логи относятся к одной и той же транзакции, причём линкуются они в хронологическом порядке (последний лог списка относится к последней операции).
Буфер логов
Чтобы запись в лог не превратилась в узкое место системы, используется буфер логов.
Политики STEAL и FORCE
Для увеличения производительности шаг номер 5 нужно делать после коммита, поскольку в случае сбоя всё ещё возможно восстановить транзакцию с помощью REDO. Это называется «политика NO-FORCE».
Но БД может выбрать и политику FORCE ради уменьшения нагрузки во время восстановления. Тогда шаг номер 5 выполняется до коммита.
Также БД выбирает, записывать ли данные на диск пошагово (политика STEAL) или, если диспетчер буфера должен дождаться коммита, записать всё разом (NO-STEAL). Выбор зависит от того, что вам нужно: быструю запись с долгим восстановлением или быстрое восстановление?
Если LSN(страницы_на_диске)>=LSN(записи_в_логе), то значит данные уже были записаны на диск перед сбоем. Но значение было перезаписано операцией, которая была выполнена после записи в лог и до сбоя. Так что ничего не сделано, на самом деле.