Materialized Path in PostgreSQL

PostgreSQL, MaterializedPath

Relational databases store information in the form of tree structures is a problem with the additional overhead. Such extra costs can be both, increasing the number of queries and increase the amount of information which is used to organize the data structure.

Widely used approach for the organization of tree structures are:

Adjacency List

The organization of the data structure is that each object on the parent object stores the information that is in a table row has an additional field, which indicates the property ID, which is embedded in the object.
Nested Set Nested sets store information not only about the so-called left and right key, and the level of nesting. This variant of the organization of the data structure easier to read, but it is more difficult amenable to modification.
Materialized Path The idea of this data structure is that each record stores the full path to the root element of the tree.

Consideration of these data structures was caused by the need to support the introduction of the site comments to articles.

Adjacency List seemed somewhat awkward solution for the comments because there may be problems with finding the parent objects and the alignment of the tree structure, although the approach itself makes it quite quickly add or delete items.

Nested Set rather cumbersome method for the organization of comments on a small site, so if you even look at the major resources side, like Habra, there under the articles not so often on the 5000 comments. I was also confused by the fact that it will be necessary to add concealed root element, the so-called first an empty comment in the article, which will be built the whole tree. Why produce extra essence? - Although maybe I am wrong. Well, the last argument "against" was the need for conversion keys when adding new comment. In general, despite the advantages of this structure, in the framework of this site and its current state - this way storage comments will be shooting from a gun on sparrows.

But Materialized Path seemed like just what you need. Each comment contains the full path. And at the same time under the article can organize a few comments of trees. That is, any comment, which is located on the first level are automatically considered to be the root of her tree. And when you add a new comment you need to take the full path of the future parents and to add to it only the ID of the new comment. In addition, in relation to a specific database, but we are talking about PostgreSQL , storage path can be represented as an array of integers, since PostgreSQL supports arrays (By the way, the more I read about working with PostgreSQL in contrast to MySQL , the more I like it). And when selecting trees comments can sort by the data arrays that automatically allows positioning all comments in chronological order with the preservation of the tree structure, and then in Django template to generate the page in the normal cycle without recursion, because all comments will already be sorted properly database means.

Using in PostgreSQL

Now imagine that we have an abstract page, which has a few comments with the following structure:

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

As a result, the comment structure will be formed with the following query:

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

In this structure, there is the auto-increment unique identifier that can be seen more and some semblance of chronological identifier, because theoretically a comment to a later time, can not be in the database before the comment with a smaller ID.

Fill the database:

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');

As a result, we obtain the following table:

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  

Search child elements

To find child elements overlap operator must use an array &&. With this operator will find items that contain in their path parent element ID. Select all the children of the element with ID = 1.

In addition, we can sort all the items in order of nesting, which is the path length.

In the below query :id = 1.

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

At the output we get the following result:

 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)

Search parent elements

Getting a list of all the parent elements is to select all the elements that are part of the path of the current element. For example we get a list of parent cells comment with ID = 3 , that is comment_1_1_1 .

In the above query below :id = 3.

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

As a result, we get the following output:

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

Add items

When you create a new entry, we need to form a path of the current path of the parent element, to which is added a new element ID. Let's add a new record, whose parent ID is equal to 4.

In the above query below :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)
);

The operator || concatenates the path of the parent element with a new element ID. At the same time getting the new value of the sequence ID comments_id_seq , which is created automatically when you create the table, we need to perform a cast, because the path contains an array type Integer[], and currval returns the type biginteger .

We obtain the following table:

 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)

Deleting an item

Delete an item will do with the removal of all child elements that are also realized through the intersection of arrays.

For example to remove an element with an ID of 5. (:id = 5)

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

As a result, the table would be as follows:

 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)

Move an item

Finally, do the movement of one of the elements, together with the descendants of another element. As already choose not particularly out of what, then move the element with ID = 2, the element with an ID of 8.

In general, the movement of one element to another must be replaced at the element and all its children that part of the path, which corresponds to the current parent, on a path that will correspond to the new parent.

The only difficulty lies in the fact that for the level of the element need to write a stored procedure that will help us to make the movement of a single request. Let's call it level and will transfer it to the ID of the element that will be moved.

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;

After the stored procedure has been registered, we will use it in the request for data transfer.

This request includes:

  • :new_parent_id - a unique identifier for the parent of the future, (it equals 8);
  • :movable_id - a unique identifier carried by the element (it equals 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];

The result is a table of the following view:

 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)

We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.
Support the author Donate

простите а Django MPTT в этом варианте не подходит? она вроде как раз для этих целей разрабатывалась

Добрый день. Почитал описание Django MPTT, и да, подойдёт. Рассматривайте статью как базовую теорию.

Comments

Only authorized users can post comments.
Please, Log in or Sign up
How to become an author?

Contribute to the evolution of the EVILEG community.

Learn how to become a site author.

Learn it
Donate

Good day, Dear Users!!!

I am Evgenii Legotckoi, developer of EVILEG. And it is my hobby project, which helps to learn programming another programmers and developers

If the site helped you, and you want also support the development of the site, than you can donate by following ways

PayPalYandex.Money
Timeweb

Let me recommend you the excellent hosting on which EVILEG is located.

For many years, Timeweb has been proving his stability.

For projects on Django I recommend VDS hosting

View Hosting Timeweb
AS
May 26, 2020, 12:29 p.m.
Artem Sun-Dun-Chan

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:50points,
  • Rating points-4
MN
May 25, 2020, 12:33 p.m.
Mitja Nagibin

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:50points,
  • Rating points-4
f
May 25, 2020, 6:05 a.m.
falcon

C++ - Test 001. The first program and data types

  • Result:66points,
  • Rating points-1
Last comments
May 29, 2020, 7:30 a.m.
Evgenij Legotskoj

Qt/C++ - Lesson 039. How to paint stroke in QSqlTableModel by value in the column?

У меня работает. Исправлял в проекте, который приложен к статье. А что происходит в вашем коде, с учётом места вызова этого кода, я знать не могу ;) Дебажьте и добавляйте условия, кото…
MA
May 29, 2020, 7:27 a.m.
Mihail A

Qt/C++ - Lesson 039. How to paint stroke in QSqlTableModel by value in the column?

QModelIndexList rowIndexes = ui->tableView->selectionModel()->selectedRows(); model->removeRows(rowIndexes.first().row(), rowIndexes.size()); model-&…
May 29, 2020, 7:14 a.m.
Evgenij Legotskoj

Django - Tutorial 036. How to add authentication through social networks. VKontakte

Неправильно прописали URL, на который возвращается ответ от OAuth ВКонтакте. Настраивайте ваше приложение в консоли разработчика ВКонтакте
AL
May 29, 2020, 6:24 a.m.
Aleksandr Leonidov

Django - Tutorial 036. How to add authentication through social networks. VKontakte

Здравствуйте! После клика на ссылку авторизации выдает json словарь с ошибкой: {"error":"invalid_request","error_description":"redirect_uri is incorrect, check application redirect uri in …
May 28, 2020, 4:14 p.m.
Evgenij Legotskoj

Qt/C++ - Lesson 039. How to paint stroke in QSqlTableModel by value in the column?

Ну в моём примере, который в статье сработало так model->setData(model->index(1, 1), 7); Поскольку model->index(1, 0) - это индекс колонки id, которая скрыта, поэтому…
Now discuss on the forum
May 29, 2020, 8:52 a.m.
Vladimir Sergeevich

Масштабирование двумя пальцами на мобильных платформах

Я планировал описать этот момент на блоге, но никак руки не доходят (уже год). Летом дойдут. Тем не менее, у меня в репозитории лежит рабочий код игрушки "пазлы", где есть все это. …
May 29, 2020, 7:51 a.m.
Evgenij Legotskoj

Графическое ускорение

Зависит от платформы и поддерживаемых технологий. В QML в первую очередь используется OpenGL и отрисовка производится средствами GPU. Но может переключаться на использование CPU и прог…
IP
May 29, 2020, 2:55 a.m.
Igor' Poroshin

QTablwView + QSqlQueryModel скрыть пустой столбец

Да, понятно. В данном случае лучше использовать серверную процедуру (если такие поддерживаются), в которой будет проверяться наличие всех пустых строк у нужного столбца и вызываться соответ…
RG
May 28, 2020, 7:21 p.m.
Rovshan Gurbanov

Сборка под старые версии Android

У меня SDK почти все версии есть, NDK есть версии 10, 17, 21. Но собирается приложение только с NDK v21 под Android версии 7.0 и выше Версия Qt у меня 5.14.2
May 28, 2020, 8:58 a.m.
Evgenij Legotskoj

Освобождение памяти QMainWindow::setCentralWidget

Да, соглашусь. Просто удаление происходит позже, а не сразу.
About
Services
© EVILEG 2015-2020
Recommend hosting TIMEWEB