Під капотом» індексів Postgres
Індекси — один із найпотужніших інструментів у реляційних базах даних. Ми використовуємо їх, коли потрібно швидко знайти якісь значення, коли поєднуємо бази даних, коли потрібно прискорити роботу SQL-операторів і т.д. Але що є індекси? І як вони допомагають прискорювати пошук БД? Для відповіді на ці запитання я вивчив вихідний код PostgreSQL, відстеживши, як відбувається пошук індексу для рядкового значення. Я очікував знайти складні алгоритми та ефективні структури даних. І знайшов.
Пошук послідовностей
Алгоритм пошуку послідовностей у Postgres демонструє дива: він чомусь переглядаєвсезначення таблиці. У моєму минулому пості використовувався ось такий простий SQL-оператор для пошуку значення Captain Nemo:
Postgres спарив, проаналізував та спланував запит. Потім ExecSeqScan (вбудована функція мовою С, що реалізує пошук послідовностей SEQSCAN) швидко знайшла потрібне значення:
Але потім через незрозумілу причину Postgres продовжив сканувати всю базу, порівнюючи кожне значення з шуканим, хоча воно вже було знайдено!
Якби таблиця містила мільйони значень, то пошук зайняв дуже багато часу. Звичайно, цього можна уникнути, якщо усунути сортування і переписати запит так, щоб він зупинявся на першому знайденому збігу. Але проблема глибша, і полягає вона у неефективності самого механізму пошуку в Postgres. Використання пошуку послідовностей порівняння кожного значення таблиці — процес повільний, неефективний і залежить від порядку розміщення записів. Має бути інший спосіб!
Рішення просте: потрібно створити індекс.
Створення індексу
Зробити це просто, достатньо виконати команду:
Розробники Ruby воліли б використовувати міграцію add_index за допомогою ActiveRecord, при якій була б виконана та ж команда CREATE INDEX. Зазвичай, коли перезапускаємо select, Postgres створює дерево планування. Але в даному випадку воно дещо відрізнятиметься:
Зауважте, що в нижній частині використовується INDEXSCAN замість SEQSCAN. INDEXSCAN не скануватиме всю базу на відміну від SEQSCAN. Натомість він використовує щойно створений індекс, щоб швидко та ефективно знайти потрібний запис.
Створення індексу дозволяє вирішити проблему продуктивності, але не дає відповіді на низку питань:
- Що саме являє собою індекс у Postgres?
- Як саме він виглядає, якою є його структура?
- Як індекс прискорює пошук?
Що являє собою індекс у Postgres
Тут відображаються всі параметри, які можна використовувати під час створення індексу. Зверніть увагу на параметр USING method: він визначає, індекс якого виду нам потрібний. На тій же сторінці наведена інформація про method, аргумент ключового слова USING:
Виявляється, у Postgres реалізовано чотири різні види індексів. Їх можна використовувати для різних типів даних або залежно від ситуації. Оскільки ми не визначали параметр USING, то index_users_on_name за умовчанням є індексом виду “btree” (B-Tree).
Що таке B-Tree і де знайти інформацію? Для цього вивчимо відповідний файл із вихідним кодом Postgres:
Ось що говориться про нього в README:
Що таке B-Tree
Назва є скороченням від англ. "balanced tree". Алгоритм дає змогу прискорити операцію пошуку. Наприклад, нам потрібно знайти значення 53. Почнемо з кореневого вузла, що містить значення 40:
Воно порівнюється з потрібним значенням. Оскільки 53 > 40, то далі ми йдемо правою гілкою дерева. А якби ми шукали, наприклад, значення 29, то пішли б лівою гілкою, бо 29 Теги:
- зрив покривів
- ніхто не читає теги
- postgres
- postgresql
- бази даних