«Під капотом» індексів Postgres


Капітан Немо у штурвала «Наутілуса»

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

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

Пошук послідовностей
Алгоритм пошуку послідовностей в Postgres демонструє дива: він навіщо-то переглядає значення в таблиці. В моєму минулому пості використовувався ось такий простий SQL-оператор для пошуку значення «Captain Nemo»:



Postgres спарсил, проаналізував і спланував запит. Потім ExecSeqScan (вбудована функція на мові С реалізує пошук послідовностей SEQSCAN) швидко знайшла потрібне значення:



Але потім з незрозумілої причини Postgres продовжив сканувати всю базу, порівнюючи кожне значення з шуканим, хоча воно вже було знайдено!



Якби таблиця містила мільйони значень, то пошук зайняв би дуже багато часу. Звичайно, цього можна уникнути, якщо прибрати сортування і переписати запит так, щоб він зупинявся на першому знайденому збігу. Але проблема глибша, і полягає вона в неефективності самого механізму пошуку в Postgres. Використання пошуку послідовностей для порівняння кожного значення в таблиці — процес повільний, неефективний і залежить від порядку розміщення записів. Має бути інший спосіб!

Рішення просте: потрібно створити індекс.

Створення індексу
Зробити це просто, достатньо виконати команду:


Розробники на Ruby воліли б використовувати міграцію add_index з допомогою ActiveRecord, при якій була б виконана та ж команда CREATE INDEX. Зазвичай, коли ми перезапускаємо select, Postgres створює дерево планування. Але в даному випадку воно буде дещо відрізнятися:



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

Створення індексу дозволяє вирішити проблему продуктивності, але не дає відповідей на ряд питань:
  • Що саме являє собою індекс Postgres?
  • Як саме він виглядає, яка його структура?
  • Яким чином індекс прискорює пошук?
Давайте відповімо на ці питання, вивчивши код на мові С.

Що являє собою індекс Postgres
Почнемо з документації для команди CREATE INDEX:



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



Виявляється, в Postgres реалізовано чотири різних види індексів. Їх можна використовувати для різних типів даних або в залежності від ситуації. Оскільки ми не визначали параметр USING, то index_users_on_name за замовчуванням являє собою індекс виду «btree» (B-Tree).

Що таке B-Tree і де знайти про нього інформацію? Для цього вивчимо відповідний файл із вихідним кодом Postgres:



Ось що говориться про нього в README:



До речі, сам README є 12-сторінковим документом. Тобто нам доступні не тільки корисні коментарі в коді, але і вся необхідна інформація про теорії і конкретної реалізації сервера БД. Читання і розбір коду в opensource-проекти часто є непростим завданням, але тільки не в Postgres. Розробники постаралися полегшити нам процес розуміння устрою їхнього дітища.

Зверніть увагу, що в першому ж реченні є посилання на наукову публікацію, в якій пояснено, що таке B-Tree (а значить, і як працюють індекси в Postgres): Efficient Locking for Concurrent Operations on B-Trees за авторством Лемана (Lehman) і Яо (Yao).

Що таке B-Tree
У статті описується поліпшення, внесена авторами в алгоритм B-Tree в 1981 році. Про це ми поговоримо трохи пізніше. Сам алгоритм був розроблений в 1972 році, так виглядає приклад простого B-Tree:



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



Воно порівнюється з шуканим значенням. Оскільки 53 > 40, то далі ми йдемо по правій гілці дерева. А якщо б ми шукали, наприклад, число 29, то пішли б з лівої гілки, тому що 29 < 40. Дотримуючись правої гілки, ми потрапляємо в дочірній вузол, що містить два значення:



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



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



За рахунок чого цей алгоритм прискорює пошук:
  1. Значення (ключі) всередині кожного вузла відсортовані.
  2. Алгоритм збалансований: ключі рівномірно розподілені по вузлам, що дозволяє мінімізувати кількість переходів. Кожна гілка веде до дочірнього вузла, що містить приблизно така ж кількість ключів, що і всі інші дочірні вузли.


Як виглядає індекс Postgres
Леман і Яо намалювали свою діаграми більше 30 років тому, яке вона має відношення до сучасного Postgres? Виявляється, створений нами index_users_on_name дуже схожий на цю саму діаграму. При виконанні команди CREATE INDEX Postgres зберігає всі значення з користувацької таблиці у вигляді ключів дерева B-Tree. Так виглядає вузол індексу:



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

От як виглядає структура IndexTupleData:



t_tid: це покажчик на який-небудь інший індекс або запис в БД. Зверніть увагу, що це не вказівник на фізичну пам'ять з мови С. містить дані, за якими Postgres шукає зіставлені сторінки пам'яті.

t_info: тут міститься інформація про елементи індексу. Наприклад, скільки значень у ньому зберігається, чи рівні вони NULL і т. д.

Для кращого розуміння розглянемо декілька записів з index_users_on_name:



Тут замість value вставлені деякі імена з БД. Вузол з верхнього дерева містить ключі “Dr. Edna Kunde" і «Julius Powlowski», а вузол нижнього — «Julius Powlowski» і «Juston Quitzon». На відміну від діаграми Лемана і Яо, Postgres повторює батьківські ключі в кожному дочірньому сайті. Наприклад, «Julius Powlowski» є ключем у верхньому дереві і на підсайті. Покажчик t_tid посилається з Julius у верхньому вузлі на таке ж ім'я в нижньому вузлі. Якщо ви хочете глибше вивчити зберігання значень ключів у вузлах B-Tree, зверніться до файлу itup.h:



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

Саме в Postgres здійснюється пошук значення «Captain Nemo» в індексі index_users_on_name? Чому використання індексу дозволяє шукати швидше порівняно з пошуком послідовності? Давайте поглянемо на деякі імена, які зберігаються в нашому індексі:



Це кореневий вузол у index_users_on_name. Я просто розгорнув дерево так, щоб імена вміщалися цілком. Тут чотири імені і одне значення NULL. Postgres автоматично створив цей кореневий вузол, як тільки був створений сам індекс. Зверніть увагу, що за винятком NULL, позначає початок індексу, інші чотири імені йдуть в алфавітному порядку.

Як ви пам'ятаєте, B-Tree є збалансованим деревом. Тому в даному прикладі дерево має п'ять дочірніх вузлів:
  • Імена, які йдуть в алфавітному порядку до “Dr. Edna Kunde"
  • Імена між “Dr. Edna Kunde" і «Julius Powlowski»
  • Імена між «Julius Powlowski» і «Monte Nicolas»
    ...і т. д.


Оскільки ми шукаємо «Captain Nemo», то Postgres йде по першій гілці направо (при алфавітній сортування шукане значення йде до «Dr. Edna Kunde»):



Як видно з ілюстрації, далі Postgres знаходить вузол з потрібним значенням. Для тесту я додав в таблицю 1000 імен. Цей правий вузол містив 240 з них. Так що дерево суттєво прискорило процес пошуку, оскільки інші 760 значень залишилися «за бортом».

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



Пошук нашого значення всередині вузла
Отже, Postgres перейшов у вузол, що містить 240 імен, серед яких йому треба знайти значення «Captain Nemo».



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



Шукане значення йде за алфавітом після «Breana Witting», тому Postgres перескакує до ключа, що знаходиться на позиції 75% (три чверті списку):



На цей раз наш значення повинно бути вище. Тоді Postgres стрибає на деяке значення вище. В моєму випадку системі знадобилося вісім разів стрибати за списком ключів у вузлі, поки вона не знайшла нарешті потрібне значення:



Детальніше про алгоритм пошуку значення в межах вузла можна почитати в коментарях до функції _bt_binsrch:



Інші цікаві речі
Якщо у вас є бажання, то деяка кількість теорії про деревах B-Tree можна почерпнути з наукової роботи Efficient Locking for Concurrent Operations on B-Trees.

Додавання ключів в B-Tree. Процедура внесення нових ключів в дерево виконується по дуже цікавому алгоритмом. Зазвичай ключ записується у вузол у відповідності з прийнятою сортуванням. Але що робити, якщо у вузлі вже немає вільного місця? У цьому випадку Postgres поділяє вузол на два більш дрібних і вставляє в один з них ключ. Також додає в батьківський вузол ключ з «точки поділу» і покажчик на новий дочірній вузол. Звичайно, батьківський вузол теж доводиться розділяти, щоб вставити ключ, у результаті додавання в дерево одного єдиного ключа перетворюється в складну рекурсивні операцію.

Видалення ключів з B-Tree. Теж досить цікава процедура. При видаленні ключа з якогось сайту Postgres, якщо це можливо, об'єднує його дочірні вузли. Це теж може бути рекурсивна операція.

Дерева B-Link-Tree. Насправді, в роботі Лемана і Яо описується придумане ними нововведення, пов'язане з паралелізмом і блокуванням, коли одне дерево використовується декількома потоками. Код Postgres і його алгоритми повинні підтримувати багатопоточність, тому що до одного індексу можуть звертатися (або модифікувати його) одночасно кілька клієнтів. Якщо додати за вказівником від кожного вузла на наступний дочірній вузол (стрілка вправо), то один потік може шукати по дереву, в той час як інший буде розділяти вузол без блокування всього індексу:



Не бійтеся дослідити
Можливо, ви знаєте все про те, як використовувати Postgres, але чи знаєте ви, як він влаштований всередині, що у нього «під капотом»? Вивчення інформатики, крім роботи над поточними проектами, не досужее розвага, а частина процесу розвитку розробника. Рік від року наші програмні інструменти стають складніше, багатогранніша, краще, полегшуючи нам процес створення сайтів і додатків. Але ми не повинні забувати, що в основі всього цього лежить наука інформатика. Ми, як і всі співтовариство opensource-розробників Postgres, стоїмо на плечах наших попередників, таких як Леман і Яо. Тому не довіряйтеся сліпо інструментів, які ви щоденно використовуєте, вивчайте їх пристрій. Це допоможе вам досягти більш високого професійного рівня, ви зможете знайти для себе інформацію і рішення, про які раніше і не підозрювали.

Джерело: Хабрахабр

0 коментарів

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