Інформатика за індексами в Постгресе

Друзі, PG Day'16 Russia успішно завершилася, ми перевели дух і вже думаємо над тим, як зробити майбутні заходи ще більш цікавими і корисними для вас. Продовжуємо публікувати цікаві, на наш погляд, матеріали про Постгресе і спілкуватися з вами в коментарях. Сьогодні представляємо переклад статті Pat Shaughnessy про те, що з себе представляють індекси в PostgreSQL.

Всі ми знаємо, що індекси — одна з найпотужніших і найважливіших функцій серверів реляційних баз даних. Як швидко знайти значення? Створити індекс. Що потрібно не забути зробити при об'єднанні двох таблиць? Створити індекс. Як прискорити SQL запит, який почав повільно працювати? Створити індекс.



Але що таке ці індекси? І вони прискорюють пошук по базі даних? Щоб з'ясувати це, я вирішив прочитати вихідний код сервера бази даних PostgreSQL на C і простежити за тим, як він шукає індекс для простого текстового значення. Я очікував знайти складні алгоритми та ефективні структури даних. І я їх знайшов. Сьогодні я покажу вам, як виглядають індекси всередині Постгреса, і поясню, як вони працюють.

Що я не очікував знайти — що я вперше виявив, читаючи вихідний код Постгреса — так це теорію інформатики в основі того, що він робить. Читання вихідного коду Постгреса перетворилося на повернення в школу і вивчення того предмета, на який у мене ніколи не вистачало часу в молодості. Коментарі на C всередині Постгреса пояснюють не тільки, що він робить, але і чому.

Послідовні сканування: бездумний пошук
Коли ми покинули команду Наутилуса, вони були змучені і майже падали в непритомність: алгоритм послідовного сканування Постгреса бездумно петляв по всім записам у таблиці користувачів! Згадайте мій попередній пост, в якому ми виконали цей простий SQL запит, щоб знайти Капітана Немо:


Постгрес опрацював, проаналізував і спланував запит. Потім ExecSeqScanфункція C всередині Постгреса, яка виконує вузол плану Послідовне сканування (SEQSCAN), швидко знайшла Капітана Немо:



Але потім Постгрес нез'ясовним чином продовжив виконувати цикл по всій таблиці користувачів, порівнюючи кожне ім'я з «Captain Nemo», хоча ми вже знайшли те, що шукали!



Уявіть, що в нашій таблиці були б мільйони записів, — процес зайняв би дуже багато часу. Звичайно, ми могли б уникнути цього, видаливши sort і переписавши наш запит так, щоб приймалося тільки перше знайдене ім'я, але більш глибока проблема полягає в неефективності способу, яким Постгрес шукає нашу цільову рядок. Використовувати послідовне сканування для порівняння кожного значення в таблиці користувачів з «Captain Nemo» — це повільно, неефективно і залежить від випадкового порядку, в якому імена з'являються в таблиці. Що ми робимо не так? Повинен бути кращий спосіб!

Відповідь проста: ми забули створити індекс. Давайте зробимо це зараз.

Створення індексу
Створити індекс дуже просто – потрібно всього лише запустити цю команду:



Як розробники Ruby, ми, звичайно ж, використовували б замість цього міграцію ActiveRecord add_index, яка виконає ту ж команду CREATE INDEX «під капотом». Коли ми знову запустимо наш запит select, Постгрес, як зазвичай, створить дерево плану, але на цей раз воно буде трохи іншим:



Зверніть увагу, що внизу Постгрес тепер використовує INDEXSCAN замість SEQSCAN. На відміну від SEQSCAN, INDEXSCAN не буде проводити сканування по всій таблиці користувачів. Замість цього він використовує той індекс, який ми тільки що створили, щоб знайти і повернути запису про Капітана Немо швидко і ефективно.

Створення індексу вирішило нашу проблему з продуктивністю, але залишило нас з безліччю цікавих пропущених питань:

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

Що таке індекс Постгресе?
Ми можемо почати з вивчення документації для команди CREATE INDEX.



Тут ви бачите всі опції, які ми можемо використовувати для створення індексу, наприклад, UNIQUE і CONCURRENTLY. Зверніть увагу, що є така опція, як метод USING. Він повідомляє Постгресу, який саме індекс нам потрібен. Нижче на тій же сторінці є інформація про method — аргументі до ключового слова USING:



Виявляється, Постгрес імплементує чотири різних типи індексів [прим. пер.: тепер вже більше, стаття була написана раніше, ніж з'явився BRIN і інші нові варіанти індексів]. Ви можете використовувати їх для різних типів даних та різних ситуаціях. Оскільки ми ніяк не уточнювали USING, наш індекс index_users_on_name є «btree» (або B-Дерево) індексом, типом за замовчуванням.

Це наша перша підказка: індекс Постгреса — це B-Дерево. Але що таке B-Дерево? Де ми можемо його знайти? Всередині Постгреса, звичайно ж! Давайте пошукаємо у вихідному коді Постгреса на C файли, що містять «btree:»



Ключовий результат виділено жирним шрифтом: “./backend/access/nbtree." Всередині цієї директорії є файл README. Давайте його прочитаємо:


Дивним чином цей файл README виявився детальним документом на 12 сторінок! Вихідний код Постгреса містить не тільки корисні і цікаві коментарі до коду C, але і документацію про теорію і реалізації сервера БД. Прочитати і зрозуміти код в проектах з відкритим вихідним кодом часто буває важко і страшно, але не в PostgreSQL. Розробники, які стоять за Постгресом, приклали величезні зусилля, щоб ми з вами могли зрозуміти їх роботу.

Назва документа README — «Btree Indexing» — підтверджує, що директорія містить код на C, який реалізує B-Tree індекси в Постгресе. Але перше речення представляє ще більший інтерес: це відсилання до наукової роботи, яка пояснює, що таке B-Дерево, і як працюють індекси в Постгресе: Efficient Locking for Concurrent Operations on B-Trees, за авторством Лемана (Lehman) і Яо (Yao).

Ми спробуємо розібратися з тим, що таке B-Tree за допомогою цієї наукової роботи.

Як виглядає B-Tree індекс?
Робота Лемана і Яо пояснює інноваційні зміни, які вони внесли в алгоритм B-Tree в 1981 році. Поговоримо про це трохи пізніше. Але вони починають з простого введення в структуру даних B-Tree, яка була винайдена на 9 років раніше — в 1972 році. Одна з їхніх діаграм показує приклад простого B-Tree:



Термін B-Tree є скороченням від англійського «balanced tree» — «збалансоване дерево». Алгоритм робить пошук простим і швидким. Наприклад, якщо б ми хотіли знайти значення 53 в цьому прикладі, ми б почали з кореневого вузла, що містить значення 40:



Ми порівнюємо наше шукане значення 53 зі значенням, яке ми знайшли у вузлі дерева. 53 — це більше або менше, ніж 40? Оскільки 53 40, ми слідуємо за покажчиком вниз і направо. Якщо б ми шукали 29, ми б пішли вниз наліво. Покажчики праворуч ведуть до великих значень, а ліворуч — до менших.

Прямуючи вниз за покажчиком до наступного дочірнього вузла дерева, ми зустрічаємо вузол, що містить 2 значення:



На цей раз ми порівнюємо 53 відразу з 47 62 і виявляємо, що 47 < 53 < 62. Зверніть увагу, що значення у вузлі дерева відсортовані, тому зробити це буде просто. Тепер ми прямуємо вниз по центральному вказівником.

Тут у нас ще один вузол дерева, вже з трьома значеннями:



Переглянувши відсортований список чисел, ми знаходимо 51 < 53 < 56 і йдемо вниз по другому з чотирьох покажчиків.

Нарешті, ми приходимо до вузла-листу дерева:



І ось воно, наше шукане значення 53!

Алгоритм B-Tree прискорює пошук, тому що:
  • він сортує значення (звані ключами) всередині кожного вузла;
  • він збалансований: ключі рівномірно розподіляються між вузлами, мінімізуючи кількість переходів від одного вузла до іншого. Кожен вказівник веде до дочірнього вузла, який містить приблизно така ж кількість ключів, як і кожен наступний дочірній вузол.
Як виглядає індекс Постгреса?
Леман і Яо намалювали цю діаграму більш 30 років тому. Яке відношення вона має до того, як Постгрес працює сьогодні? Вражаюче, але індекс index_users_on_name, який ми створили раніше, дуже схожий на цю саму діаграму з наукової роботи: ми створили в 2014 році індекс, який виглядає точно так само, як діаграма з 1981-го!

Коли ми виконали команду CREATE INDEX, Постгрес зберіг всі імена з нашої таблиці користувачів B-Tree. Вони стали ключами дерева. Ось як виглядає сайт всередині B-Tree індексу в Постгресе:



Кожна запис в індексі складається з структури на мові C під назвою IndexTupleData, за якою слід бітова карта (bitmap) і значення. Постгрес використовує бітову карту, щоб записувати, приймають якісь атрибути індексу в ключі значення NULL, для економії місця. Фактичні значення знаходяться в індексі після бітової карти.

Давайте докладніше розглянемо структуру IndexTupleData:



На малюнку вище видно, що кожна структура IndexTupleData містить:
  • t_tid: це покажчик на інший index tuple, або на запис в базі даних. Зауважте, що це не вказівник на фізичну пам'ять на мові С. Замість цього він містить числа, які Постгрес може використовувати, щоб знайти шукане значення на сторінках пам'яті.
  • t_info: тут міститься інформація про елементи індексу, наприклад, скільки в ньому значень чи рівні вони null.
Щоб краще це зрозуміти, давайте покажемо кілька записів з нашого індексу index_users_on_name:



Я замінив value якимись іменами з моєї таблиці користувачів. Верхній вузол дерева також містить ключі “Dr. Edna Kunde" і «Julius Powlowski», а нижній — «Julius Powlowski» і «Juston Quitzon». Зверніть увагу, що на відміну від діаграми Лемана і Яо, Постгрес повторює батьківський ключ в кожному дочірньому сайті. Тут «Julius Powlowski» є ключем у верхньому і дочірньому вузлах. Покажчик t_tid у верхньому вузлі відсилає до того ж імені Julius в нижньому вузлі.

Щоб дізнатися більше про те, як саме Постгрес зберігає ключові значення у вузол B-Tree, зверніться до заголовочному файлу itup.h:



image
IndexTupleDataview on postgresql.org





Пошук вузла B-Tree, що містить Капітана Немо
Давайте повернемося до нашого початкового запиту SELECT:



Як саме Постгрес шукає в нашому індексі index_users_on_name значення «Captain Nemo»? Чому використовувати індекс швидше, ніж послідовне сканування, яке ми розглядали в попередньому пості? Щоб це з'ясувати, давайте трохи зменшимо масштаб і подивимося на деякі імена користувачів у нашому індексі:



Це кореневий вузол B-Tree index_users_on_name. Я поклав дерево на бік, щоб імена влізли. Ви можете побачити 4 імені і одне значення NULL. Постгрес створив цей кореневий вузол, коли я створив index_users_on_name. Зауважте, що крім першого значення NULL, яке позначає початок індексу, решта 4 значення більш-менш рівномірно розподілені в алфавітному порядку.

Нагадаю, що B-Tree — це збалансоване дерево. В цьому прикладі в B-Tree є 5 дочірніх вузлів:
  • імена, розташовані за алфавітом до Dr. Edna Kunde;
  • імена, розташовані між Dr. Edna Kunde і Julius Powlowski;
  • імена, розташовані між Julius Powlowski і Monte Nicolas;
  • і т. д.
Оскільки ми шукаємо ім'я Captain Nemo, Постгрес переходить з першої верхній стрілкою праворуч. Це обумовлено тим, що Captain Nemo за алфавітом йде перед Dr. Edna Kunde:



Як бачите, справа Постгрес знайшов вузол B-Tree, в якому міститься Captain Nemo. Для свого тесту я додав в таблицю користувачів 1000 імен. Цей дочірній вузол B-Tree включає близько 200 імен (240, якщо бути точним). Так що алгоритм B-Tree істотно звузив нам пошук в Постгресе.

Щоб дізнатися більше про конкретний алгоритм, що використовується Постгресом для пошуку цільового вузла B-Tree серед всіх його вузлів, почитайте функцію _bt_search.



image
_bt_searchview on postgresql.org





Пошук Капітана Немо всередині конкретного вузла B-Tree
Тепер, коли Постгрес звузив простір для пошуку до вузла B-Tree, що містить близько 200 імен, йому все ще потрібно знайти серед них Капітана Немо. Як же він це зробить? Застосує він послідовне сканування до цього скороченому списку?



Немає. Для пошуку ключового значення в межах вузла дерева Постгрес переключається на використання бінарного алгоритму пошуку. Він починає порівнювати ключ, розташований на 50% позиції у вузлі дерева з «Captain Nemo»:



Оскільки Captain Nemo за алфавітом йде після Breana Witting, Постгрес перескакує до позиції 75% і проводить ще одне порівняння:



На цей раз Captain Nemo йде до Curtis Wolf, так що Постгрес повертається трохи назад. Зробивши ще кілька ітерацій (Постгресу знадобилося 8 порівнянь, щоб знайти Капітана Немо в моєму прикладі), Постгрес нарешті знаходить те, що ми шукали.



Щоб дізнатися більше про те, як Постгрес шукає значення в конкретному вузлі B-Tree, почитайте функцію _bt_binsrch:



image
_bt_binsrchview on postgresql.org





Ще багато чого належить дізнатися
Мені не вистачить місця в цьому пості, щоб розповісти про всі захопливих деталях, що стосуються B-Tree, індексів баз даних або нутрощах Постгреса… можливо, мені варто написати книгу Постгрес під мікроскопом :) А поки ось вам кілька цікавих фактів з теорії, які ви можете прочитати в Efficient Locking for Concurrent Operations on B-Trees або в іншій науковій роботі, на яку вона посилається.

  • Вставки в B-Tree: найпрекрасніша частина алгоритму B-Tree — додавання нових ключів в дерево. Вони додаються у відсортованому порядку у відповідний вузол дерева, але що відбувається, коли місця для нових ключів не залишається? У цьому випадку, Постгрес ділить вузол на два, вставляє в один з них новий ключ і додає ключ з розділеного сайту батьківський вузол разом з покажчиком на новий дочірній вузол. Звичайно, є ймовірність, що батьківський вузол теж доведеться розділити, щоб додати новий ключ, що призведе до складної рекурсивну операції.
  • Видалення з B-Tree: зворотна операція також цікава. Коли ключ видаляється з сайту, Постгрес об'єднує однорівневі вузли, якщо це можливо, видаляючи ключ з батьківського сайту. Ця операція також може бути рекурсивну.
  • B-Link — Tree: Робота Лемана і Яо розповідає про інновації, яку вони досліджували, щодо паралелізму та блокування, коли кілька потоків використовують одне і те ж B-Дерево. Як ви пам'ятаєте, код та алгоритми Постгреса повинні бути мультипоточными, тому що багато клієнтів можуть одночасно шукати і модифікувати один і той же індекс. Додаючи ще один покажчик з кожного вузла B-Tree наступного дочірній вузол – так звана «права стрілка» — один потік може шукати в дереві, навіть якщо другий потік ділить вузли, не блокуючи при цьому весь індекс:


Не бійтеся дослідити невидиму частину айсберга
Професор Ароннакс ризикував своїм життям і кар'єрою, щоб знайти невловимий Наутілус і приєднатися до Капітана Немо в довгій низці дивовижних підводних пригод. Нам варто зробити так само: не боятися пірнути під воду — вглиб інструментів, мов і технологій, які ви використовуєте щодня. Ви можете багато чого знати про Постгресе, але чи знаєте ви, як він працює зсередини? Загляньте всередину, і не встигнете озирнутися, як самі опинитеся в підводному пригоді.

Вивчення на роботі інформатики, що стоїть за нашими додатками, — це не просто розвага, а важлива складова процесу розвитку розробника. Інструменти для розробки програмного забезпечення вдосконалюються з кожним роком, написання веб-сайтів і мобільних додатків спрощується, але ми не повинні упускати з поля зору фундаментальну інформатику, від якої ми залежимо. Ми всі стоїмо на плечах гігантів – таких людей, як Леман і Яо, а також розробників відкритого вихідного коду, використали їх теорії для створення Постгреса. Не сприймайте інструменти, які ви використовуєте щодня, як належне, — вивчайте їх пристрій. Ви станете мудрішими як розробник і знайдете ідеї і знання, про які навіть не підозрювали.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.