Что такое селекция данных в бд

Специальные операции реляционной алгебры: проекция, селекция и объединение отношений

Nbsp; 1 вопрос

Назначение информационного обеспечения АСУ ВМФ. Место и роль БД в составе АСУ ВМФ.

ИО АСУ – часть ПО, которое выполняет функции сбора, обработки, накопления и выдачи информации об управлении объекта.

ИО внешнее:

Обработка и определение состава информации для будущей БД и ее вида

ИО внутреннее:

— Перевод входных сообщений на внутремашинный язык

— Обнаружение и исправление ошибок входных сообщений

— определение мест хранения информации при накоплении

Банк данных, БД и СУБД. Назначение и определение.

Банк данных = БД+СУБД

БД – сами данные в виде совокупности двумерных таблиц

СУБД – программа, работающая с БД

БД – именованная, структурированная совокупность данных, отражающая состояние объектов и их связей предметной области

СУБД – комплекс программных и языковых средств, предназначенных для создания, ведения и применения БД многими пользователями

Достоинства концепции БД по сравнению с монопольными файлами.

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

Устранение противоречивости хранения данных

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

Однократный ввод и многоаспектное использование

Обеспечение возможности стандартизации данных при их вводе и хранении в БД

Обеспечение возможности санкционированного доступа к различным данным

Обеспечение независимости прикладных программ от используемых прикладных данных

Основные функции СУБД. Языки СУБД.

— генерация, первоначальное создание структуры БД

— модификация, расширение, изменение БД

— накопление, обновление, исключение данных

— поиск данных по запросам и формирование для выдачи

— обеспечение сохранения данных

— обеспечение целостности и непротиворечивости данных

— обеспечение секретности данных, разграничение доступа

— обеспечение диалогового режима пользователей с БД

Язык Определения Данных – для описания структуры объектов данных

Язык Манипулирования Данными – для ввода и поиска информации

Язык Описания Схемы таблицы – для определения названия таблицы и столбцов

Язык Описания Подсхем – для описания части таблицы

Основные модели данных, их сходства и отличия

Иерархическая модель данных – совокупность элементов данных, расположенных в порядке их подчинения и образующих перевернутое дерево. Основные понятия: уровень, узел, связь

Реляционная модель данных:

— структура записи линейна, все поля еденичны

— связь таблиц осуществляется на программном уровне, а сейчас по общему полю

Реляционная модель данных. Терминология, свойства отношений в РБД

Реляционная модель данных:

— структура записи линейна, все поля единичны

— связь таблиц осуществляется на программном уровне, а сейчас по общему полю

Основные элементы – поле и запись

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

Свойства отношений

— Все значения полей в таблице единичны

— В отношении нет одинаковых записей, т.к. есть ключевые поля

Виды связей в реляционной БД

1 к 1 – если каждая запись в таблице А может иметь не более одной связанной с ней записи в таблице В и наоборот. В этом случае используются первичные ключи связываемых таблиц.

1 ко многим – если каждая запись в таблице А может быть связана с несколькими записями таблицы В, но каждая запись в таблице В не может быть связана более чем с одной записью в таблице А. В этом случае табл. А главная, а В – подчиненная

Многие ко многим– если каждой записи таблицы А соответствует несколько записей таблице В и наоборот. Такая связь реализуется с помощью третьей связующей таблицы С.

Основные операции реляционной алгебры: объединение, пересечение, разность и декартово произведение

Объединение – должна быть одинаковая арность; должны быть одинаковые наборы атрибутов

Специальные операции реляционной алгебры: проекция, селекция и объединение отношений

Проекция – выполняется над одним отношением, формируется новое отношение, где компонуются атрибуты в указанном порядке

Селекция – операция выполняется над одним отношением, результирующее отношение имеет ту же схему отношения, что и исходное, но с меньшим (равным) количеством строк

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

Дата добавления: 2018-08-06 ; просмотров: 480 ; Мы поможем в написании вашей работы!

Источник

Связи между таблицами базы данных

1. Введение

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

1.1. Для кого эта статья?

Эта статья будет полезна тем, кто хочет разобраться со связями между таблицами базы данных. В ней я постарался рассказать на понятном языке, что это такое. Для лучшего понимания темы, я чередую теоретический материал с практическими примерами, представленными в виде диаграммы и запроса, создающего нужные нам таблицы. Я использую СУБД Microsoft SQL Server и запросы пишу на T-SQL. Написанный мною код должен работать и на других СУБД, поскольку запросы являются универсальными и не используют специфических конструкций языка T-SQL.

1.2. Как вы можете применить эти знания?

2. Благодарности

Учтены были советы и критика авторов jobgemws, unfilled, firnind, Hamaruba.
Спасибо!

3.1. Как организовываются связи?

Связи создаются с помощью внешних ключей (foreign key).
Внешний ключ — это атрибут или набор атрибутов, которые ссылаются на primary key или unique другой таблицы. Другими словами, это что-то вроде указателя на строку другой таблицы.

3.2. Виды связей

4. Многие ко многим

Представим, что нам нужно написать БД, которая будет хранить работником IT-компании. При этом существует некий стандартный набор должностей. При этом:

4.1. Как построить такие таблицы?

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

На эту таблицу можно посмотреть с двух сторон:

4.2. Реализация

С помощью ограничения foreign key мы можем ссылаться на primary key или unique другой таблицы. В этом примере мы

4.3. Вывод

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

5. Один ко многим

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

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

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

Другими словами, телефон принадлежит только одному пользователю. А пользователю могут принадлежать 1 и более телефонов (многие).

Как мы видим, это отношение один ко многим.

5.1. Как построить такие таблицы?

Данная таблица представляет три номера телефона. При этом номера телефона с id 1 и 2 принадлежат пользователю с id 5. А вот номер с id 3 принадлежит пользователю с id 17.
Заметка. Если бы у таблицы «Phones» было бы больше атрибутов, то мы смело бы их добавляли в эту таблицу.

5.2. Почему мы не делаем тут таблицу-посредника?

Таблица-посредник нужна только в том случае, если мы имеем связь многие-ко-многим. По той простой причине, что мы можем рассматривать ее с двух сторон. Как, например, таблицу EmployeesPositions ранее:

5.3. Реализация

6. Один к одному

Представим, что на работе вам дали задание написать БД для учета всех работников для HR. Начальник уверял, что компании нужно знать только об имени, возрасте и телефоне работника. Вы разработали такую БД и поместили в нее всю 1000 работников компании. И тут начальник говорит, что им зачем-то нужно знать о том, является ли работник инвалидом или нет. Наиболее простое, что приходит в голову — это добавить новый столбец типа bool в вашу таблицу. Но это слишком долго вписывать 1000 значений и ведь true вы будете вписывать намного реже, чем false (2% будут true, например).

Более простым решением будет создать новую таблицу, назовем ее «DisabledEmployee». Она будет выглядеть так:

Но это еще не связь один к одному. Дело в том, что в такую таблицу работник может быть вписан более одного раза, соответственно, мы получили отношение один ко многим: работник может быть несколько раз инвалидом. Нужно сделать так, чтобы работник мог быть вписан в таблицу только один раз, соответственно, мог быть инвалидом только один раз. Для этого нам нужно указать, что столбец EmployeeId может хранить только уникальные значения. Нам нужно просто наложить на столбец EmloyeeId ограничение unique. Это ограничение сообщает, что атрибут может принимать только уникальные значения.

Выполнив это мы получили связь один к одному.

Заметка. Обратите внимание на то, что мы могли также наложить на атрибут EmloyeeId ограничение primary key. Оно отличается от ограничения unique лишь тем, что не может принимать значения null.

6.1. Вывод

Можно сказать, что отношение один к одному — это разделение одной и той же таблицы на две.

6.2. Реализация

7. Обязательные и необязательные связи

Связи можно поделить на обязательные и необязательные.

7.1. Один ко многим

У одной биологической матери может быть много детей. У ребенка есть только одна биологическая мать.

А) У женщины необязательно есть свои дети. Соответственно, связь необязательна.
Б) У ребенка обязательно есть только одна биологическая мать – в таком случае, связь обязательна.

7.2. Один к одному

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

А) Наличие загранпаспорта необязательно – его может и не быть у гражданина. Это необязательная связь.
Б) У загранпаспорта обязательно есть только один владелец. В этом случае, это уже обязательная связь.

7.3. Многие ко многим

Человек может инвестировать в акции разных компаний (многих). Инвесторами какой-то компании являются определенные люди (многие).

А) Человек может вообще не инвестировать свои деньги в акции.
Б) Акции компании мог никто не купить.

8. Как читать диаграммы?

Выше я приводил диаграммы созданных нами таблиц. Но для того, чтобы их понимать, нужно знать, как их «читать». Разберемся в этом на примере диаграммы из пункта 5.3.

Мы видим отношение один ко многим. Одной персоне принадлежит много телефонов.

9. Итоги

10. Задачи

Для лучшего усвоения материала предлагаю вам решить следующие задачи:

Источник

Большая Энциклопедия Нефти и Газа

Селекция данных может быть задана значениями, относящимися к столбцам таблицы или вершинам графа. [1]

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

Если МД позволяет выполнять селекцию данных по их связям между собой и в БД реализована, например, связь РАБОТАЕТ-В-ОТДЕЛЕ между сущностями СЛУЖАЩИЙ и ОТДЕЛ, то можно выполнять селекцию данных по этой связи. Таким образом, с помощью условия селекции выполняется идентификация требуемых данных в БД. [4]

В существующих языках конкретных СУБД наблюдаются различные комбинации рассмотренных видов селекции данных и формы их выражения средствами конкретного языка. [5]

Данные, выбираемые из одной таблицы, могут быть использованы посредством вложенных операторов SELECT для селекции данных в других таблицах. Хотя здесь есть сходство с операцией соединения, но имеется и различие, состоящее в том, что результирующие данные выбираются только из одной таблицы. [7]

Программа SISPIL реализует алгоритм СРС восстановления решения интегрального уравнения в виде кубического сплайна с сопряжениями в узлах равномерной сетки и одновременной селекцией данных таким образом, чтобы на построенном решении функционал среднего риска принимал гарантированно наименьшее значение. Число узлов сопряжений и данные, подлежащие удалению, определяются в процессе выполнения алгоритма. Подробно алгоритм СРС описан в § 2 гл. [10]

Если МД позволяет выполнять селекцию данных по их связям между собой и в БД реализована, например, связь РАБОТАЕТ-В-ОТДЕЛЕ между сущностями СЛУЖАЩИЙ и ОТДЕЛ, то можно выполнять селекцию данных по этой связи. Таким образом, с помощью условия селекции выполняется идентификация требуемых данных в БД. [11]

Источник

Ограничения целостности. Операции, реализуемые СУБД, включают селекцию (поиск) данных; действия над данными

Операции над данными

Операции, реализуемые СУБД, включают селекцию (поиск) данных; действия над данными.

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

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

§ найти следующее данное (запись);

§ найти предыдущее данное;

§ найти первое (последнее) данное. Этот тип селекции называют селекцией посредством текущей, в качестве которой используется индикатор текущего состояния, автоматически поддерживаемый СУБД и, как правило, указывающий на некоторый экземпляр записи БД.

Критерий селекции по значениям данных формируется из простых или булевых условий отбора. Примерами простых условий поиска являются:

§ (УЧЕНОЕ_ЗВАНИЕ=ДОЦЕНТ:) ИЛИ (УЧЕНОЕЗВАНИЕ-ПРОФЕССОР).

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

Как правило, большинство современных СУБД позволяет осуществлять различные комбинации описанных выше видов селекции данных.

Ограничения целостности — логические ограничения на данные — используются для обеспечения непротиворечивости данных некоторым заранее заданным условиям при вы­полнении операций над ними. По сути ограничения целостности — это набор правил, используемых при создании конкретной модели данных на базе выбранной СУБД.

Различают внутренние и явные ограничения.

Ограничения, обусловленные возможностями конкретной СУБД, называют внутренними ограничениями целостности. Эти ограничения касаются типов хранимых данных (например, «текстовый элемент данных может состоять не более чем из 256 символов» или «запись может содержать не более 100 полей») и допустимых типов связей (например, СУБД может поддерживать только так называемые функциональные связи, т.е. связи типа 1:1, 1:М или М:1). Большинство существующих СУБД поддерживают, прежде всего, именно внутренние ограничения целостности, нарушения которых приводят к некорректности данных и достаточно легко контролируются.

Ограничения, обусловленные особенностями хранимых данных о конкретной ПрОбл, называют явными ограничениями целостности. Эти ограничения также поддерживаются средствами выбранной СУБД, но они формируются обязательно с участием разработчика БД путем определения (программирования) специальных процедур, обеспечивающих непротиворечивость данных. Например, если элемент данных «зачетная книжка» в записи «студент» определен как ключ, он должен быть уникальным, т.е. в БД не должно быть двух записей с одинаковыми значениями ключа. Другой пример: пусть в той же записи предусмотрен элемент «военно-учетная специальность» и для него отведено 6 десятичных цифр. Тогда другие представления этого элемента данных в БД невозможны. С помощью явных ограничений целостности можно организовать как «простой» контроль вводимых данных (прежде всего, на предмет принадлежности элементов данных фиксированному и заранее заданному множеству значений: например, элемент «ученое звание» не должен принимать значение «почетный доцент», если речь идет о российских ученых), так и более сложные процедуры (например, введение значения «профессор» элемента данных «ученое звание» в запись о преподавателе, имеющем возраст 25 лет, должно требовать, по крайней мере, дополнительного подтверждения).

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

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

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

Источник

Как работает реляционная БД

Реляционные базы данных (РБД) используются повсюду. Они бывают самых разных видов, от маленьких и полезных 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(записи_в_логе), то значит данные уже были записаны на диск перед сбоем. Но значение было перезаписано операцией, которая была выполнена после записи в лог и до сбоя. Так что ничего не сделано, на самом деле.

Источник