Що таке інвертований індекс, і чому це повинно вас хвилювати?

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

Що таке інвертований індекс?

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

Цю концепцію, можливо, легше зрозуміти візуально, тому розглянемо простий приклад. Уявіть, що у нас є наступна таблиця бази даних, в якій зберігаються різні письмові фрази (в нашому випадку це список функцій CockroachDB):

Нижче наведено інвертований індекс для цієї таблиці. Як ви можете бачити, цей індекс показує розташування кожного слова (так званої лексеми) у таблиці.

Навіщо використовувати інвертовані індекси?

Інвертовані індекси використовуються для полегшення ефективнішого повнотекстового пошуку в базі даних.

Давайте знову подивимося на приклад таблиці та індексу з попереднього розділу, щоб проілюструвати, як це працює. Уявіть, що ми хочемо знайти записи, які містять слово "мульти". Ми можемо використати такий SQL-запит:

SELECT * FROM table WHERE content LIKE '%multi%';

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

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

Інвертовані індекси дозволяють виконувати текстовий пошук набагато ефективніше. Після створення інвертованого індексу, базі даних не потрібно виконувати повне сканування таблиці. Замість цього вона може просто звернутися до індексного запису для multi та відразу виявити, що він з'являється в рядках 101 і 103.

У випадку з наведеним вище прикладом бази даних це означає, що для повернення результатів їй потрібно буде прочитати три рядки (індексний запис і рядки 101 і 103), замість того, щоб читати чотири рядки без інвертованого індексу.

Це вже невелике підвищення ефективності, і це лише дуже простий приклад! У великій реальній базі даних створення інвертованого індексу може призвести до набагато більшого підвищення ефективності при виконанні повнотекстового пошуку.

Які недоліки інвертованих індексів?

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

Це, як правило, незначне зниження продуктивності, і якщо ваша програма регулярно запитує текстові дані, подібні до наведених вище, незначне падіння продуктивності, яке ви побачите при записі, буде компенсовано значним покращенням продуктивності при читанні.

Однак варто пам'ятати, що додавання ще одного індексу не завжди є правильним рішенням, і існують деякі випадки використання - наприклад, дуже інтенсивні навантаження на запис - коли втрати на записі, спричинені додаванням інвертованого індексу, можуть бути не варті того, щоб пожертвувати покращеною продуктивністю на зчитуванні.

Як використовувати інвертовані індекси

По-перше, перевірте, чи підтримуються інвертовані індекси програмним забезпеченням бази даних і типом даних, який ви використовуєте. У CockroachDB, наприклад, наступні типи даних можна зберігати в узагальнених інвертованих (GIN) індексах: JSONB, ARRAY, GEOMETRY, GEOGRAPHY, TSVECTOR (для повнотекстового пошуку) і STRING (з використанням триграмних індексів, які є підтипом інвертованого індексу).

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

Вилучення коренів, яке перетворює слова на їхні корені, відсікаючи кінець. Наприклад, перетворення "бігти" на "біг". Лематизація, яка схожа на стеммінг, але скорочує слова до їх словникової відповідності (знову ж таки, "бігти" буде перетворено на "біг"). Видалення стоп-слів, що означає позбавлення від граматично поширених, але беззмістовних без контексту слів, таких як "і", "та", "з" тощо. До кожного з цих методів можна підійти по-різному. Те, як ви застосуєте їх до свого інвертованого індексу, залежатиме від конкретного випадку використання. Часто ці завдання можна виконати автоматично - деякі або всі ці методи вже можуть бути вбудовані у ваше програмне забезпечення для роботи з базами даних.

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

Створення інвертованих індексів за допомогою SQL

Розгляньмо, як створювати та додавати інвертовані індекси в реляційних базах даних. Зверніть увагу, що конкретний синтаксис, який використовується для цього, буде дещо відрізнятися в залежності від особливостей SQL, який використовується у вашій базі даних. Тут ми використовуємо синтаксис CockroachDB, який буде дуже знайомим для тих, хто знайомий з PostgreSQL (CockroachDB сумісна з Postgres, хоча вона включає деякі розширені можливості, яких немає в синтаксисі Postgres).

Створення інвертованого індексу для таблиці, що існує:

CREATE INDEX index_name ON table_name USING GIN (column_to_index);

Якщо ви створюєте триграмний індекс для полегшення пошуку STRING-даних, вам також необхідно вказати opclass для триграмного індексу, як показано нижче:

CREATE INDEX index_name ON table_name USING GIN({column_to_index} gin_trgm_ops);

CockroachDB також дозволяє створювати частково інвертовані індекси, які індексують лише певну підмножину даних, наприклад, так:

CREATE TABLE table (
 id INT,
 data JSONB,
 INVERTED INDEX index_name(data) WHERE id > 10
);

Наведений вище запит створить інвертований індекс для таблиці, який буде індексувати тільки ті значення в даних, для яких відповідний ідентифікатор більший за 10.

Ви також можете створювати багатостовпчикові GIN-індекси у CockroachDB, хоча існують деякі обмеження щодо їх використання. Синтаксис наступний:

CREATE TABLE users (
  profile_id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
  user_type STRING,
  user_profile JSONB,
  INVERTED INDEX (user_type, user_profile)
);

Звичайно, створення правильного індексу - це лише початок.