Привіт, Хабре! Представляю вашій увазі переклад статті
"How does a relative database work".

Коли справа доходить до реляційних баз даних, я не можу не думати, що чогось не вистачає. Вони використовуються скрізь. Існує безліч різних баз даних: від невеликого та корисного SQLite до потужної Teradata. Але є лише кілька статей, які пояснюють, як працює база даних. Ви можете шукати самі на запит "howdoesarelationaldatabasework" («як працюють реляційні бази даних»), щоб побачити, як мало результатів. Більше того, ці статті є короткими. Якщо ви шукаєте останні модні технології (BigData, NoSQL або JavaScript), ви знайдете більше поглиблених статей, які пояснюють, як вони працюють.

Чи є реляційні бази даних надто старими та надто нудними, щоб їх можна було пояснити поза університетськими курсами, дослідницькими роботами та книгами?

Як розробник я ненавиджу використати те, що не розумію. І якщо бази даних використовуються протягом більш ніж 40 років, то має бути причина. За ці роки я витратив сотні годин, щоб по-справжньому зрозуміти ці дивні чорні ящики, які я використовую щодня. Реляційні бази даних дуже цікаві, тому що вони засновані на корисних і багаторазово використовуваних концепціях. Якщо вас цікавить розуміння бази даних, але ви ніколи не мали часу або бажання копатися в цій широкій темі, вам повинна сподобатися ця стаття.

Хоча назва цієї статті є явною, Мета цієї статті не в тому, щоб зрозуміти, як використовувати базу даних. отже, ви вже повинні знати, як написати простий запит з'єднання та базові запити Сирий; інакше ви можете не зрозуміти цю статтю. Це єдине, що вам потрібно знати, я поясню все інше.

Почну з деяких основ комп'ютерних наук, таких як часова складність алгоритмів (BigO). Я знаю, деякі з вас ненавидять цю концепцію, але без неї ви не зможете зрозуміти тонкощі всередині бази даних. Оскільки це величезна тема, я зосереджуся на тому, що вважаю важливим: як база даних обробляє SQL запит. Я представлю тільки основні концепції бази даних, щоб наприкінці статті ви мали уявлення про те, що відбувається під капотом

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

Для більш обізнаних із вас, ця стаття поділена на 3 частини:

• Огляд низькорівневих та високорівневих компонентів бази даних
• Огляд процесу оптимізації запитів
• Огляд управління транзакціями та буферним пулом

Повертаючись до основ

Багато років тому (у далекій, далекій галактиці…), розробники мали точно знати кількість операцій, які вони кодували. Вони знали напам'ять свої алгоритми та структури даних, тому що не могли дозволити собі витрачати ЦП та пам'ять своїх повільних комп'ютерів.

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

O(1) vs O(n2)

В даний час багато розробників не піклуються про тимчасову складність алгоритмів … і вони мають рацію!

Але коли ви маєте справу з великою кількістю даних (я не говорю про тисячі) або якщо ви боретеся за мілісекунди, стає критично важливим зрозуміти цю концепцію. І як ви розумієте, бази даних повинні мати справу з обома ситуаціями! Я не примушу вас витратити більше часу, ніж потрібно, щоб схопити суть. Це допоможе нам пізніше зрозуміти концепцію оптимізації на основі витрат (коштувати заснований оптимізація).

Концепція

Тимчасова складність алгоритму використовується, щоб побачити, скільки часу займе виконання алгоритму для даного обсягу даних. Щоб описати цю складність, використовують математичні позначення великих О. Ця нотація використовується з функцією, яка описує скільки операцій потрібно алгоритму для заданої кількості вхідних даних.

Наприклад, коли я говорю "цей алгоритм має складність O (some_function() )", це означає, що для обробки певного обсягу даних алгоритму потрібно some_function(a_certain_amount_of_data) операцій.

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

На цьому графіку можна побачити залежність кількості операцій від обсягу вхідних даних для різних типів тимчасових складностей алгоритмів. Я використовував логарифмічну шкалу, щоб їх відобразити. Іншими словами, кількість даних швидко збільшується з 1 до 1 млрд. Ми можемо побачити, що:

• O(1) або постійна складність залишаються постійними (інакше це не називатиметься постійною складністю).
• O(журнал(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 (злиття)

Як і багато корисних алгоритмів, сортування злиттям засноване на хитрощі: об'єднання 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-місце (Сортування без додаткової пам'яті).

• Ви можете змінити його для одночасного використання дискового простору та невеликого об'єму пам'яті без значних витрат на дискове введення/виведення. Ідея полягає в тому, щоб завантажувати на згадку тільки ті частини, які в даний момент обробляються. Це важливо, коли вам потрібно відсортувати таблицю розміром кілька гігабайт тільки з буфером пам'яті об'ємом 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.

Допустимо, ви знайшли М наступників, і дерево має 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+Дерево. Якщо ви хочете приклад реалізації B+Tree у базі даних, перегляньте цю статтю и цю статтю від провідного розробника MySQL. Вони обидва зосереджені у тому, як InnoDB (движок MySQL) обробляє індекси.

Примітка: читач сказав мені, що через низькорівневі оптимізації дерево B+ має бути повністю збалансоване.

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

Наша остання важлива структура даних – це хеш-таблиця. Це дуже корисно, коли ви хочете швидко шукати значення. Більше того, розуміння хеш-таблиці допоможе нам пізніше зрозуміти загальну операцію з'єднання з базою даних, яку називають хеш-з'єднанням ( хеш-з'єднання). Ця структура даних також використовується базою даних для зберігання деяких внутрішніх речей (наприклад, таблиця блокування або буферний пул, ми побачимо обидві ці концепції пізніше).

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

• ключ для ваших елементів
• хеш-функцію для ключів. Обчислені хеші ключів дають розташування елементів (званих сегментами ).
• функцію для порівняння ключів. Як тільки ви знайшли правильний сегмент, ви повинні знайти елемент, який ви шукаєте всередині сегмента за допомогою цього порівняння.

простий приклад

Давайте візьмемо наочний приклад:

Ця хеш-таблиця має 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 немає елементів. Реальна задача - знайти хорошу хеш-функцію, яка створюватиме сегменти, що містять дуже невелику кількість елементів.

У моєму прикладі знайти хорошу хеш-функцію легко. Але це простий приклад, знайти хорошу хеш-функцію складніше, коли ключ:

• рядок (наприклад - прізвище)
• 2 рядки (наприклад - прізвище та ім'я)
• 2 рядки та дата (наприклад - прізвище, ім'я та дата народження)
• ...

З гарною хеш-функцією пошук у хеш-таблиці обходиться в O(1).

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

Чому б не використовувати масив?

Хм, гарне питання.

• Хеш-таблиця може бути частково завантажена на згадкуа інші сегменти можуть залишатися на диску.
• З масивом ви повинні використовувати безперервний простір у пам'яті. Якщо ви завантажуєте велику таблицю дуже складно знайти досить безперервного простору.
• Для хеш-таблиці ви можете вибрати потрібний ключ (наприклад, країну та прізвище людини).

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

Джерело: habr.com