[Из песочницы] Как работают реляционные базы данных (Часть 1)10.02.2020 01:32

Привет, Хабр! Представляю вашему вниманию перевод статьи
«How does a relational database work».

Когда дело доходит до реляционных баз данных я не могу не думать, что чего-то не хватает. Они используются везде. Существует множество различных баз данных: от небольшого и полезного SQLite до мощной Teradata. Но есть только несколько статей, которые объясняют, как работает база данных. Вы можете искать сами по запросу «howdoesarelationaldatabasework» («как работают реляционные базы данных») чтобы увидеть, как мало результатов. Более того, эти статьи — короткие. Если же вы ищете последние модные технологии (BigData, NoSQL или JavaScript), вы найдете больше углубленных статей, объясняющих, как они работают.

Являются ли реляционные базы данных слишком старыми и слишком скучными, чтобы их можно было объяснить вне университетских курсов, исследовательских работ и книг?

Как разработчик я ненавижу использовать то, что не понимаю. И если базы данных используются в течение более чем 40 лет, должна быть причина. За эти годы я потратил сотни часов, чтобы по-настоящему понять эти странные черные ящики, которые я использую каждый день. Реляционные базы данных очень интересны, потому что они основаны на полезных и многократно используемых концепциях. Если вас интересует понимание базы данных, но у вас никогда не было времени или желания копаться в этой широкой теме, вам должна понравиться эта статья.

Хотя название этой статьи является явным, цель этой статьи не в том, чтобы понять, как использовать базу данных. Следовательно, вы уже должны знать, как написать простой запрос соединения и базовые запросы CRUD; иначе вы можете не понять эту статью. Это единственное, что вам нужно знать, я объясню все остальное.

Начну с некоторых основ компьютерных наук, таких как временная сложность алгоритмов (BigO). Я знаю, что некоторые из вас ненавидят эту концепцию, но без нее вы не сможете понять тонкости внутри базы данных. Поскольку это огромная тема, я сосредоточусь на том, что считаю важным: как база данных обрабатывает SQL запрос. Я представлю только основные концепции базы данных, чтобы в конце статьи вы имели представление о том, что происходит под капотом.

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

Для более осведомленных из вас, эта статья разделена на 3 части:

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

Много лет назад (в далекой, далекой галактике…), разработчики должны были точно знать количество операций, которые они кодировали. Они знали наизусть свои алгоритмы и структуры данных, потому что не могли позволить себе тратить ЦП и память своих медленных компьютеров.

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

O (1) vs O (n2)

В настоящее время многие разработчики не заботятся о временной сложности алгоритмов … и они правы!

Но когда вы имеете дело с большим количеством данных (я не говорю о тысячах) или если вы боретесь за миллисекунды, становится критически важным понять эту концепцию. И как вы понимаете, базы данных должны иметь дело с обеими ситуациями! Я не заставлю вас потратить больше времени, чем необходимо чтобы ухватить суть. Это поможет нам позже понять концепцию оптимизации на основе затрат (cost based optimization).

Концепция

Временная сложность алгоритма используется, чтобы увидеть сколько времени займет выполнение алгоритма для данного объема данных. Чтобы описать эту сложность, используют математические обозначения больших О. Эта нотация используется с функцией, которая описывает, сколько операций нужно алгоритму для заданного количества входных данных.

Например, когда я говорю «этот алгоритм имеет сложность O (some_function ())», это означает, что для обработки определенного объема данных алгоритму требуется some_function (a_certain_amount_of_data) операций.

При этом важно не количество данных**, а то, ** как увеличивается количество операций при увеличении объема данных. Сложность по времени не дает точное количество операций, но хороший способ для оценки времени выполнения.

На этом графике вы можете увидеть зависимость числа операций от объема входных данных для различных типов временных сложностей алгоритмов. Я использовал логарифмическую шкалу, чтобы отобразить их. Другими словами, количество данных быстро увеличивается с 1 до 1 млрд. Мы можем увидеть, что:

O (1) или постоянная сложность остаются постоянными (иначе это не будет называться постоянной сложностью).
O(log(n)) остается низкой даже с миллиардами данных.
Наихудшая сложность — O (n2), где количество операций быстро растет.
Две другие сложности так же быстро увеличиваются.

Примеры

При небольшом количестве данных разница между O (1) и O (n2) незначительна. Например, предположим, что у вас есть алгоритм, который должен обрабатывать 2000 элементов.

Алгоритм O (1) обойдется вам в 1 операцию
Алгоритм O (log (n)) обойдется вам в 7 операций
Алгоритм O (n) обойдется вам в 2 000 операций
Алгоритм O (n * log (n)) обойдется вам в 14 000 операций
Алгоритм O (n2) обойдется вам в 4 000 000 операций

Разница между O (1) и O (n2) кажется большой (4 миллиона операций), но вы потеряете максимум 2 мс, просто время моргнуть глазами. Действительно, современные процессоры могут обрабатывать сотни миллионов операций в секунду. Вот почему производительность и оптимизация не являются проблемой во многих ИТ-проектах.

Как я уже сказал, по-прежнему важно знать эту концепцию при работе с огромным количеством данных. Если на этот раз алгоритм должен обработать 1 000 000 элементов (что не так уж много для базы данных):

Алгоритм O (1) обойдется вам в 1 операцию
Алгоритм O (log (n)) обойдется вам в 14 операций
Алгоритм O (n) обойдется вам в 1 000 000 операций
Алгоритм O (n * log (n)) обойдется вам в 14 000 000 операций
Алгоритм O (n2) обойдется вам в 1 000 000 000 000 операций

Я не делал расчетов, но я бы сказал, что с помощью алгоритма O (n2) у вас есть время выпить кофе (даже два!). Если вы добавите еще 0 к объему данных, у вас будет время, чтобы вздремнуть.

Идем глубже

Для справки:

Поиск в хорошей хеш-таблице находит элемент за O (1).
Поиск в хорошо сбалансированном дереве дает результат за O (log (n)).
Поиск в массиве дает результат за O (n).
Лучшие алгоритмы сортировки имеют сложность O (n * log (n)).
Плохой алгоритм сортировки имеет сложность O (n2).

Примечание: в следующих частях мы увидим эти алгоритмы и структуры данных.

Есть несколько типов временной сложности алгоритма:

сценарий среднего случая
лучший вариант развития событий
и худший сценарий

Временная сложность часто является наихудшим сценарием.

Я говорил только о временной сложности алгоритма, но сложность также применима для:

потребления памяти алгоритмом
потребления дискового ввода / вывода алгоритмом

Конечно, есть сложности хуже, чем n2, например:

n4: это ужасно! Некоторые из упомянутых алгоритмов имеют такую сложность.
3n: это еще хуже! Один из алгоритмов, которые мы увидим в середине этой статьи, имеет эту сложность (и он действительно используется во многих базах данных).
факториал n: вы никогда не получите свои результаты даже с небольшим количеством данных.
nn: если вы столкнетесь с этой сложностью, вы должны спросить себя, действительно ли это ваша сфера деятельности …

Примечание: я дал вам не реальное определение обозначения «большой О», а просто идею. Вы можете прочитать эту статью в Википедии для реального (асимптотического) определения.

MergeSort (Сортировка слиянием)

Что вы делаете, когда вам нужно отсортировать коллекцию? Что? Вы вызываете функцию sort ()… Ок, хороший ответ… Но для базы данных вы должны понимать, как работает эта функция sort ().

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

Merge (слияние)

Как и многие полезные алгоритмы, сортировка слиянием основана на хитрости: объединение 2 отсортированных массивов размера N / 2 в N-элементный отсортированный массив стоит всего N операций. Эта операция называется слиянием.

Давайте посмотрим, что это значит на простом примере:

На этом рисунке видно, что для построения окончательного отсортированного массива из 8 элементов вам нужно всего лишь выполнить итерацию один раз в 2×4-элементных массивах. Поскольку оба 4-элементных массива уже отсортированы:

1) вы сравниваете оба текущих элемента в двух массивах (в начале текущий = первому)
2) затем возьмите наименьший, чтобы поместить его в массив из 8 элементов
3) и переходите к следующему элементу в массиве, где вы взяли самый маленький элемент
и повторяйте 1,2,3, пока не дойдете до последнего элемента одного из массивов.
Затем вы берете остальные элементы другого массива, чтобы поместить их в массив из 8 элементов.

Это работает, потому что оба 4-элементных массива отсортированы, и поэтому вам не нужно «возвращаться» в этих массивах.

Теперь, когда мы поняли этот трюк, вот мой псевдокод для merge:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

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

Фаза деления, где массив делится на меньшие массивы
Фаза сортировки, где маленькие массивы объединяются (используя объединение), чтобы сформировать больший массив.

Division phase (фаза деления)

На этапе деления массив делится на унитарные массивы за 3 шага. Формальное количество шагов — log (N) (поскольку N=8, log (N) = 3).

Откуда я это знаю?

Я гений! Одним словом — математика. Идея состоит в том, что каждый шаг делит размер исходного массива на 2. Количество шагов — это количество раз, которое вы можете разделить исходный массив на два. Это точное определение логарифма (с основанием 2).

Sorting phase (Фаза сортировки)

На этапе сортировки вы начинаете с унитарных (одноэлементных) массивов. В течение каждого этапа вы применяете несколько операций слияния, и общая стоимость составляет N = 8 операций:

На первом этапе у вас есть 4 слияния, которые стоят 2 операции каждый
На втором шаге у вас есть 2 слияния, которые стоят 4 операции каждый
На третьем шаге у вас есть 1 слияние, которое стоит 8 операций

Поскольку существует log (N) шагов, общая стоимость N * log (N) операций.

Преимущества merge sort

Почему этот алгоритм такой мощный?

Потому что:

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

Примечание: этот вид алгоритмов называется in-place (сортировка без дополнительной памяти).

Вы можете изменить его для одновременного использования дискового пространства и небольшого объема памяти без значительных затрат на дисковый ввод/вывод. Идея состоит в том, чтобы загружать в память только те части, которые в данный момент обрабатываются. Это важно, когда вам нужно отсортировать таблицу размером в несколько гигабайт только с буфером памяти объемом 100 мегабайт.

Примечание: этот вид алгоритмов называется внешняя сортировка.

Вы можете изменить его для запуска на нескольких процессах / потоках / серверах.

Например, распределенная сортировка слиянием является одним из ключевых компонентов Hadoop (который является структурой в больших данных).

Этот алгоритм может превратить свинец в золото (правда!).

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

Массив, Дерево и Хеш-таблица

Теперь, когда мы понимаем идею временной сложности и сортировки, я должен рассказать вам о 3 структурах данных. Это важно, потому что они являются основой современных баз данных. Я также введу понятие индекса базы данных.

Массив

Двумерный массив — простейшая структура данных. Таблицу можно рассматривать как массив. Например:

Этот 2-мерный массив представляет собой таблицу со строками и столбцами:

Каждая строка представляет сущность
Столбцы хранят свойства, описывающие сущность.
Каждый столбец хранит данные определенного типа (integer, string, date…).

Так удобно хранить и визуализировать данные однако, когда вам нужно найти определенное значение, это не подходит.

Например, если вы хотите найти всех ребят, которые работают в Великобритании, вам нужно будет просмотреть каждую строку, чтобы определить, принадлежит ли эта строка к Великобритании. Это будет стоить вам N операций, где N — количество строк, что неплохо, но может ли быть более быстрый путь? Теперь нам пришло время познакомится с деревьями.

Примечание: большинство современных баз данных предоставляют расширенные массивы для эффективного хранения таблиц: heap-organizedtables и index-organizedtables. Но это не меняет проблему быстрого поиска определенного условия в группе столбцов.

Дерево и индекс базы данных

Двоичное дерево поиска — это двоичное дерево со специальным свойством, ключ в каждом узле должен быть:

больше, чем все ключи, хранящиеся в левом поддереве
меньше всех ключей, хранящихся в правом поддереве

Давайте посмотрим, что это значит визуально

Идея

Это дерево имеет N = 15 элементов. Допустим, я ищу 208:

Я начинаю с корня, чей ключ 136. Поскольку 136<208, я смотрю на правое поддерево узла 136.
398>208, следовательно, я смотрю на левое поддерево узла 398
250>208, следовательно, я смотрю на левое поддерево узла 250
200<208, следовательно, я смотрю на правое поддерево узла 200. Но 200 не имеет правого поддерева, значение не существует (потому что, если оно существует, оно будет в правом поддереве 200).

Теперь, скажем, я ищу 40

Я начинаю с корня, чей ключ 136. Поскольку 136 > 40, я смотрю на левое поддерево узла 136.
80 > 40, следовательно, я смотрю на левое поддерево узла 80
40= 40, узел существует. Я извлекаю идентификатор строки внутри узла (этого нет на рисунке) и смотрю в таблице для данного идентификатора строки.
Знание идентификатора строки, позволяет мне узнать, где именно находятся данные в таблице, и поэтому я могу получить их мгновенно.

В итоге оба поиска обойдутся мне в количество уровней внутри дерева. Если вы внимательно прочитаете часть о сортировке слиянием, вы должны увидеть, что здесь log (N) уровней. Получается, стоимость поиска log (N), не плохо!

Возвращаемся к нашей проблеме

Но это очень абстрактно, поэтому давайте вернемся к нашей проблеме. Вместо простого integer, представьте строку, которая представляет страну кого-то в предыдущей таблице. Предположим, у вас есть дерево, которое содержит поле «country» (column 3) таблицы:

Если вы хотите знать, кто работает в Великобритании
вы смотрите на дерево, чтобы получить узел, который представляет Великобританию
внутри «UKnode» вы найдете расположение записей работников в Великобритании.

Этот поиск будет стоить log (N) операций вместо N операций если вы напрямую будет е использовать массив. То, что вы только что представили — это был индекс базы данных.

Вы можете построить индексное дерево для любой группы полей (строка, число, 2 строки, число и строка, дата …) до тех пор, пока у вас есть функция для сравнения ключей (т.е. групп полей) так что вы можете установить порядок среди ключей (что имеет место для любых основных типов в базе данных).

B+TreeIndex

Хотя это дерево хорошо работает для получения определенного значения, существует БОЛЬШАЯ проблема, когда вам нужно получить несколько элементов между двумя значениями. Это будет стоить O (N) потому что вам придется посмотреть на каждый узел в дереве и проверить, находится ли он между этими двумя значениями (например, с упорядоченным обходом дерева). Более того, эта операция не удобна для дискового ввода-вывода, так как вам придется читать полное дерево. Нам нужно найти способ эффективно выполнить запрос диапазона. Для решения этой проблемы современные базы данных используют модифицированную версию предыдущего дерева под названием B+Tree. В B+Tree дереве:

только самые нижние узлы (листья) хранят информацию (расположение строк в связанной таблице)
остальные узлы находятся здесь для маршрутизации к правильному узлу во время поиска.

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

С этим B+Tree, если вы ищете значения от 40 до 100:

Вам просто нужно искать 40 (или ближайшее значение после 40, если 40 не существует), как вы делали с предыдущим деревом.
Затем соберите наследников 40, используя прямые ссылки на наследников, пока не достигнете 100.

Допустим, вы нашли M преемников, и дерево имеет N узлов. Поиск конкретного узла стоит log (N) подобно предыдущему дереву. Но, получив этот узел, вы получите M преемников в M операциях со ссылками на их преемников. Этот поиск стоит только M+log (N) операций по сравнению с N операций с предыдущим деревом. Более того, вам не нужно читать полное дерево (только M + log (N) узлов), что означает меньшее использование диска. Если М мало (например, 200 строк) и N большой (1 000 000 строк), это будет БОЛЬШАЯ разница.

Но здесь есть новые проблемы (снова!). Если вы добавляете или удаляете строку в базе данных (и, следовательно, в связанном индексе B+Tree):

вы должны поддерживать порядок между узлами внутри дерева B+Tree, иначе вы не сможете найти узлы внутри несортированного дерева.
вы должны сохранить минимально возможное количество уровней в B+Tree, иначе временная сложность в O (log (N)) станет O (N).

Другими словами, B+Tree должно быть самоупорядоченным и сбалансированным. К счастью, это возможно с умными операциями удаления и вставки. Но это обходится дорого: вставка и удаление в дереве B+ обходятся в O (log (N)). Вот почему некоторые из вас слышали, что использование слишком большого количества индексов не очень хорошая идея. Действительно, вы замедляете быструю вставку / обновление / удаление строки в таблице, поскольку базе данных необходимо обновить индексы таблицы с помощью дорогостоящей операции O (log (N)) для каждого индекса. Более того, добавление индексов означает большую нагрузку для менеджера транзакций (будет описан в конце статьи).

Для более подробной информации, вы можете посмотреть статью в Википедии о B+Tree. Если вы хотите пример реализации B+Tree в базе данных, посмотрите эту статью и эту статью от ведущего разработчика MySQL. Они оба сосредоточены на том, как InnoDB (движок MySQL) обрабатывает индексы.

Примечание: читатель сказал мне что, из-за низкоуровневых оптимизаций дерево B+ должно быть полностью сбалансировано.

Hashtable (Хеш-таблица)

Наша последняя важная структура данных — это хеш-таблица. Это очень полезно, когда вы хотите быстро искать значения. Более того, понимание хеш-таблицы поможет нам позже понять общую операцию соединения с базой данных, называемую хеш-соединением (hash join). Эта структура данных также используется базой данных для хранения некоторых внутренних вещей (например, таблица блокировки или буферный пул, мы увидим обе эти концепции позже).

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

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

Простой пример

Давайте возьмем наглядный пример:

Эта хеш-таблица имеет 10 сегментов. Поскольку я ленивый, я изобразил только 5 сегментов, но я знаю, что вы умные, поэтому позволю вам представить 5 других самостоятельно. Я использовал хэш-функцию по модулю 10 ключа. Другими словами, сохраняю только последнюю цифру ключа элемента, чтобы найти его сегмент:

если последняя цифра равна 0, элемент попадает в сегмент 0,
если последняя цифра равна 1, элемент попадает в сегмент 1,
если последняя цифра равна 2, элемент попадает в область 2,
…

Функция сравнения, которую я использовал, это просто равенство между двумя целыми числами.

Допустим, вы хотите получить элемент 78:

Хеш-таблица вычисляет хеш-код для 78, который равен 8.
Хеш-таблица смотрит в сегмент 8, и первый элемент, который она находит, это 78.
Она возвращает вам элемент 78
Поиск стоит только 2 операции (одна для вычисления значения хеш-функции, а другая для поиска элемента внутри сегмента).

Теперь, допустим, вы хотите получить элемент 59:

Хеш-таблица вычисляет хеш-код для 59, который равен 9.
Хеш-таблица ищет в 9 сегменте, первый найденный элемент — это 99. Поскольку 99!=59, элемент 99 не правильный элемент.
Используя эту же логику, берется второй элемент (9), третий (79), …, последний (29).
Элемент не найден.
Поиск стоил 7 операций.

Хорошая хеш-функция

Как видите, в зависимости от значения, которое вы ищете, стоимость не одинакова!

Если я теперь изменю хэш-функцию по модулю 1 000 000 от ключа (то есть, взяв последние 6 цифр), второй поиск будет стоить только 1 операцию, поскольку в сегменте 000059 нет элементов. Реальная задача — найти хорошую хэш-функцию, которая будет создавать сегменты, содержащие очень небольшое количество элементов.

В моем примере найти хорошую хеш-функцию легко. Но это простой пример, найти хорошую хеш-функцию сложнее, когда ключ:

строка (например — фамилия)
2 строки (например — фамилия и имя)
2 строки и дата (например — фамилия, имя и дата рождения)
…

С хорошей хеш-функцией поиск в хеш-таблице обходится в O (1).

Массив vs хеш-таблица

Почему бы не использовать массив?

Хм, хороший вопрос.

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

Для дополнительной информации, вы можете прочитать статью о JavaHashMap, которая является эффективной реализацией хеш-таблицы; вам не нужно понимать Java, чтобы понять концепции, изложенные в этой статье.