Матеріалізований шлях у PostgreSQL

PostgreSQL, MaterializedPath

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

Поширеними підходами для організації деревоподібних структур є:

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

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

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

А ось Materialized Path здався саме тим, що потрібно. Кожен коментар містить повний шлях. І при цьому під статтею може бути організовано кілька дерев коментарів. Тобто будь-який коментар, який знаходиться на першому рівні, автоматично вважається кореневим для свого дерева. А при додаванні нового коментаря необхідно взяти повний шлях з майбутнього батька і додати до нього тільки ID нового коментаря. До того ж стосовно конкретної БД, а йдеться про PostgreSQL , зберігання шляху можна представити у вигляді масиву цілісних значень, оскільки PostgreSQL підтримує масиви (До речі, чим більше читаю про роботу з PostgreSQL ) на противагу MySQL , тим більше він мені подобається). А також при вибірці дерев коментарів можна виконувати сортування за даними масивами, що автоматично дозволить розташовувати всі коментарі в хронологічному порядку із збереженням структури дерева, а потім уже в шаблоні Django сформувати сторінку у звичайному циклі без жодних рекурсій, оскільки всі коментарі вже будуть відсортовані належним чином засобами бази даних.

Використання в PostgreSQL

А тепер уявімо, що у нас є абстрактна сторінка, у якої є кілька коментарів з наступною структурою:

id | name
-------------------
1  | comment_1
2  |   comment_1_1
3  |     comment_1_1_1
4  |   comment_1_2
5  | comment_2
6  |     comment_2_1
7  |     comment_2_2
8  | comment_3

У результаті структура коментаря формуватиметься таким запитом:

CREATE TABLE comments (
  id serial primary key,
  path integer[] not null,
  content varchar(200) not null
);

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

Заповнимо базу даних коментарями:

INSERT INTO comments (path, content) VALUES 
  ('{1}', 'comment_1'),
  ('{1,2}', 'comment_1_1'),
  ('{1,2,3}', 'comment_1_1_1'),
  ('{1,4}', 'comment_1_2'),
  ('{5}', 'comment_2'),
  ('{5,6}', 'comment_2_1'),
  ('{5,7}', 'comment_2_2'),
  ('{8}', 'comment_3');

У результаті отримаємо таку таблицю:

id | path    | content       
-------------------------
1  | {1}     | comment_1    
2  | {1,2}   | comment_1_1  
3  | {1,2,3} | comment_1_1_1
4  | {1,4}   | comment_1_2
5  | {5}     | comment_2  
6  | {5,6}   | comment_2_1
7  | {5,7}   | comment_2_2
8  | {8}     | comment_3  

Пошук дочірніх елементів

Для пошуку дочірніх елементів необхідно використовувати оператор перекриття масиву && . За допомогою даного оператора знаходитимемо елементи, які містять у своєму шляху ID батьківського елемента. Виберемо всі дочірні елементи елемента з ID = 1.

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

У запиті :id = 1 .

SELECT * FROM comments
WHERE path && ARRAY[:id]
ORDER BY array_length(path, 1);

На виході отримаємо такий висновок:

 id |  path   |    content    
----+---------+---------------
  1 | {1}     | comment_1
  2 | {1,2}   | comment_1_1
  4 | {1,4}   | comment_1_2
  3 | {1,2,3} | comment_1_1_1
(4 rows)

Пошук батьківських елементів

Отримання списку всіх батьківських елементів полягає в тому, щоб вибрати всі елементи, що входять до складу поточного елементу. Наприклад, отримаємо список батьківських елементів коментаря з ID = 3 , тобто comment_1_1_1.

У наведеному нижче запиті : id = 3.

SELECT * FROM comments
WHERE id != :id 
AND array[id] && (
  SELECT path 
  FROM comments 
  WHERE id = :id
)
ORDER BY path;

В результаті отримаємо наступний висновок:

 id | path  |   content   
----+-------+-------------
  1 | {1}   | comment_1
  2 | {1,2} | comment_1_1
(2 rows)

Додавання елементів

При створенні нового запису нам необхідно сформувати шлях поточним шляхом батьківського елемента, до якого буде додано ID нового елемента. Допустимо додамо новий запис, у якого ID батьківського елемента дорівнюватиме 4.

У наступному запиті :id = 4.

INSERT INTO comments (content, path)
values (
  'comment_1_2_3', 
  (SELECT path FROM comments WHERE id = :id) || (select currval('comments_id_seq')::integer)
);

Оператор || конкатенує шлях батьківського елемента з ID нового елемента. При цьому отримуючи нове значення ID із послідовності comments_id_seq , яка створюється автоматично при створенні таблиці, нам необхідно виконати наведення типів, оскільки шлях містить масив типу Integer[] , а currval повертає тип biginteger .

Отримаємо таку таблицю:

 id |  path   |    content    
----+---------+---------------
  1 | {1}     | comment_1
  2 | {1,2}   | comment_1_1
  3 | {1,2,3} | comment_1_1_1
  4 | {1,4}   | comment_1_2
  5 | {5}     | comment_2
  6 | {5,6}   | comment_2_1
  7 | {5,7}   | comment_2_2
  8 | {8}     | comment_3
  9 | {1,4,9} | comment_1_2_3
(9 rows)

Видалення елемента

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

Наприклад, видалимо елемент з ID рівним 5. ( :id = 5 )

DELETE FROM comments
WHERE path && ARRAY[:id];

В результаті таблиця стане такою:

 id |  path   |    content    
----+---------+---------------
  1 | {1}     | comment_1
  2 | {1,2}   | comment_1_1
  3 | {1,2,3} | comment_1_1_1
  4 | {1,4}   | comment_1_2
  8 | {8}     | comment_3
  9 | {1,4,9} | comment_1_2_3
(6 rows)

Переміщення елемента

На закінчення зробимо переміщення одного з елементів разом із нащадками на інший елемент. Оскільки вибирати вже особливо нема з чого, то перемістимо елемент з ID = 2, елемент з ID рівним 8.

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

Єдина складність полягає в тому, що для отримання рівня елемента потрібно написати процедуру, що зберігається, яка допоможе нам зробити переміщення одним запитом. Назвемо її level і передаватимемо до неї ID того елемента, який переміщатимемо.

CREATE OR REPLACE FUNCTION level(element_id integer) RETURNS integer AS
$$
DECLARE result integer;
BEGIN
SELECT array_length(path, 1) FROM comments WHERE comments.id = element_id INTO result;
RETURN result;
END
$$ LANGUAGE plpgsql;

Після того, як процедура, що зберігається, була зареєстрована, скористаємося нею в запиті на перенесення даних.

Цей запит містить:

• :new_parent_id - це унікальний ідентифікатор майбутнього батька, (Равен 8);
• :movable_id - це унікальний ідентифікатор переносного елемента (Рівний 2).

UPDATE comments
SET path = (
  SELECT path
  FROM comments
  WHERE id = :new_parent_id
) || path[(SELECT level(:movable_id)) : array_length(path, 1)]
WHERE path && ARRAY[:movable_id];

В результаті отримаємо таблицю наступного виду:

 id |  path   |    content    
----+---------+---------------
  1 | {1}     | comment_1
  4 | {1,4}   | comment_1_2
  8 | {8}     | comment_3
  9 | {1,4,9} | comment_1_2_3
  2 | {8,2}   | comment_1_1
  3 | {8,2,3} | comment_1_1_1
(6 rows)