Materialized Path в 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)