Denormalization of trees

Very often, a tree is taken as the basis of the application architecture. A simple example: there are countries, in countries - areas, in areas - cities, in cities - organizations, in organizations - workers, goods or something else. The use of the tree is quite logical and justified. The hierarchy of such a system shows some abstract table. Let's call it object :

CREATE TABLE object ( id NUMBER(11), parent_id NUMBER(11), type VARCHAR2(16) NOT NULL, name VARCHAR2(255) NOT NULL, CONSTRAINT pk_object PRIMARY KEY (id), CONSTRAINT fk_object_parent FOREIGN KEY (parent_id) REFERENCES object (id) ON DELETE CASCADE ENABLE ); 

Fill it with some data:

 id | parent_id | type | name ------------------------------------------------------ 1 | NULL | country |  2 | 1 | region |   3 | 1 | region |   4 | 2 | city |  5 | 3 | city |  

At the same time, we can easily get the connections we need in one request:
')

 --     SELECT * FROM object WHERE type = 'city' START WITH id = 1 CONNECT BY PRIOR id = parent_id; --  ,     SELECT * FROM object WHERE type = 'country' START WITH id = 5 CONNECT BY PRIOR parent_id = id; 

However, problems appear when there are so many records in the table that any recursive query is executed for two minutes or even more. Changing the whole architecture is somehow a bit late ... Here we are helped by denormalization of the tree. In this article I will talk about one of the ways such denormalization.

The basic idea is to use a materialized view that stores links in a more convenient form for queries:

 CREATE MATERIALIZED VIEW object_fast REFRESH COMPLETE ON DEMAND START WITH trunc(sysdate)+4/24 NEXT (trunc(sysdate)+1)+4/24 AS SELECT rownum id, tree.* FROM ( SELECT CONNECT_BY_ROOT id object_id, CONNECT_BY_ROOT name object_name, CONNECT_BY_ROOT type object_type, id parent_id, name parent_name, type parent_type, level-1 nesting_level FROM object CONNECT BY PRIOR parent_id = id ORDER BY object_id, nesting_level ) tree;; ALTER TABLE object_fast ADD CONSTRAINT pk_object_fast PRIMARY KEY (id); 

Now we have a denormalized table that we can use in our queries.

 id | object_id | object_name | object_type | parent_id | parent_name | parent_type | nesting_level ---------------------------------------------------------------------------------------------------------------------- 1 | 1 |  | country | 1 |  | country | 0 2 | 2 |   | region | 2 |   | region | 0 3 | 2 |   | region | 1 |  | country | 1 4 | 3 |   | region | 3 |   | region | 0 5 | 3 |   | region | 1 |  | country | 1 6 | 4 |  | city | 4 |  | city | 0 7 | 4 |  | city | 2 |   | region | 1 8 | 4 |  | city | 1 |  | country | 2 9 | 5 |  | city | 5 |  | city | 0 10 | 5 |  | city | 3 |   | region | 1 11 | 5 |  | city | 1 |  | country | 2 

As you can see, in the table there are links of each object with all its parents, and nesting_level is the number of levels up to the parent. Note, I added an id field, which is optional, but quite reasonable if you plan to access data through ORM. Now the above requests will look like this:

 --     SELECT * FROM object_fast WHERE parent_id = 1 AND object_type = 'city'; --  ,     SELECT * FROM object_fast WHERE object_id = 5 AND parent_type = 'country'; 

Well, if you wish, you can add indexes:

 CREATE INDEX object_fast_obj_id ON object_fast (object_id); CREATE INDEX object_fast_par_id ON object_fast (parent_id); CREATE INDEX object_fast_obj_type ON object_fast (object_type); CREATE INDEX object_fast_par_type ON object_fast (parent_type); CREATE INDEX object_fast_nesting ON object_fast (nesting_level); 

That's all. From myself I will say that on our project this method gave an increase in the speed of requests by about 60 times. Use wisely and do not forget that the data obtained will not always be relevant. I recommend to apply this method only to rarely added and deleted objects. Well, or then it is worth implementing a quick update of the materialized view. There is no limit to the flight of fancy ...

update: The article was corrected and the method was significantly simplified thanks to the xtender comment.