Analyse of the feasibility of using Recursive Queries instead of LTREE

- [x] How long does it take to query all descendants or ancestors of an element (LTREE vs Recursive)
- [x] What space is taken by the path (LTREE) vs. parentId (UUID) for recursivity?
- [x] How can we use these queries in TypeORM and in our codebase?
- [ ] #1649
- [ ] Remove the item_path in foreign tables (use item_id instead).
- [ ] What is the additional cost of using functions or views?

# Actions and take away

As we discussed this morning (19.11.2024), recursive queries don't solve all our problems. So here's the plan for the next step:

- Remove propagation of the LTREE in other tables using a `view` or `function` to abstract the way we retrieve children, descendants or ancestors.
- Remove the item_path in foreign tables (use item_id instead).
- What is the additional cost of using functions or views?

> [!NOTE]
> In this step, we always use LTREE, the aim being to limit its propagation to the item table only.

In another step, we need to answer some questions:
- What are the performances on the mean items (mean descendants, ancestors,...)?
- It is possible to use recursive views with good performance (for recursive calls).
- Are we using LTREE correctly? Perhaps we need to check certain recommendations regarding the size of a path?
- What are the gains in terms of moves when using an LTREE compared with recursive calls?

# Replace LTREE By Recursive Queries

> Migration

```
ALTER TABLE item
ADD COLUMN parentId UUID;

UPDATE item
SET parentId = (
CASE
WHEN path IS NULL OR path = '' OR nlevel(path) <= 1 THEN NULL
ELSE replace(subpath(path, nlevel(path) - 2, 1)::text, '_', '-')::uuid
END
);

CREATE INDEX idx_item_parentid ON item (parentId);

```

# What space is taken by the path (LTREE) vs. parentId (UUID) for recursivity?

```
SELECT
pg_size_pretty(total_path_size_bytes) AS total_path_size,
pg_size_pretty(total_parent_id_size_bytes) AS total_parent_id_size,
(total_parent_id_size_bytes::numeric / total_path_size_bytes) * 100 AS efficiency_percentage,
pg_size_pretty(total_path_size_bytes - total_parent_id_size_bytes) AS economized_size
FROM (
SELECT
sum(pg_column_size(path)) AS total_path_size_bytes,
sum(pg_column_size(parentid)) AS total_parent_id_size_bytes
FROM item
) AS subquery;
```

| total_path_size | total_parent_id_size | efficiency_percentage | economized_size |
| :-------------- | :------------------- | :-------------------- | :-------------- |
| 81 MB | 7690 kB | 9.29% | 73 MB |

> [!NOTE]
> The previous table only represents the storage for the item's table, we should also consider all tables where the item path is used as FK to evaluate the total economized space.

```
DO $$
DECLARE
rec record;
searched_column_name text := 'item_path';
path_size bigint := 0;
uuid_size bigint := 0;
total_path_size_bytes bigint := 0;
total_uuid_size_bytes bigint := 0;
table_count int := 0;
BEGIN
FOR rec IN
SELECT t.table_name
FROM information_schema.tables t
INNER JOIN information_schema.columns c ON c.table_name = t.table_name
AND c.table_schema = t.table_schema
WHERE c.column_name = searched_column_name
AND t.table_schema NOT IN ('information_schema', 'pg_catalog')
AND t.table_type = 'BASE TABLE'
ORDER BY t.table_schema
LOOP
EXECUTE format('
SELECT sum(pg_column_size(item_path)), sum(pg_column_size(id))
FROM %I', rec.table_name) INTO path_size, uuid_size;

total_path_size_bytes := total_path_size_bytes + COALESCE(path_size, 0);
total_uuid_size_bytes := total_uuid_size_bytes + COALESCE(uuid_size, 0);
table_count := table_count + 1;
END LOOP;

RAISE NOTICE 'Number of Tables: %', table_count;
RAISE NOTICE 'Total Path Size: %', pg_size_pretty(total_path_size_bytes);
RAISE NOTICE 'Total UUID Size: %', pg_size_pretty(total_uuid_size_bytes);

IF total_path_size_bytes > 0 THEN -- Avoid division by zero
RAISE NOTICE 'Efficiency Percentage: %%%', (total_uuid_size_bytes::numeric / total_path_size_bytes) * 100;
RAISE NOTICE 'Economized Size: %', pg_size_pretty(total_path_size_bytes - total_uuid_size_bytes);
ELSE
RAISE NOTICE 'Efficiency Percentage: N/A (Total Path Size is zero)';
RAISE NOTICE 'Economized Size: N/A (Total Path Size is zero)';
END IF;
END $$;

```

| Number of tables | total_path_size | total_uuid_size | efficiency_percentage | economized_size |
| :--------------- | :-------------- | :-------------- | :-------------------- | :-------------- |
| 9 | 14 MB | 3687 kB | 25% | 11 MB |

So the total economized size when using UUID instead of LTREE is **84 MB**.
> [!NOTE]
> We can also compute the mean size of a LTREE to estimate the economized size according to a given number of items.
>
> ```
> SELECT
> total_items,
> pg_size_pretty(uuid_mean_size_bytes) AS uuid_mean_size,
> pg_size_pretty(ltree_mean_size_bytes) AS ltree_mean_size,
> (uuid_mean_size_bytes::numeric / ltree_mean_size_bytes) * 100 AS efficiency_percentage,
> pg_size_pretty(ltree_mean_size_bytes - uuid_mean_size_bytes) AS economized_size
> FROM (
> SELECT
> count(*) AS total_items,
> avg(pg_column_size(id)) AS uuid_mean_size_bytes,
> avg(pg_column_size(path)) AS ltree_mean_size_bytes
> FROM item
> ) AS subquery;
> ```
>
> | total_items | uuid_mean_size | ltree_mean_size | efficiency_percentage | economized_size |
> | :---------- | :------------- | :-------------- | :-------------------- | :-------------- |
> | 626'918 | 16 bytes | 135.25 bytes | 11.83% | 119.25 bytes |

# How long does it take to query (LTREE vs Recursive)

> [!IMPORTANT]
> We have to disable the cache to ensure to have unoptimized execution time. It's difficult to completely disable the cache in PostgreSQL, so I executed `DISCARD ALL;` and restarted the db between each query to try to mitigate the cache. Each query was also executed 10 times to compute the average execution time.

> [!NOTE]
> We have not defined a threshold to indicate whether a SQL query is good or slow, but it could be a good idea to define if the usage of one technique is acceptable or not. Nikolay from postgres.ai has defined a good query that has an execution time <= 10ms and acceptable queries <= 100ms. Queries > 100ms require optimisation.
>
> 
> [https://postgres.ai/blog/20210909-what-is-a-slow-sql-query#srt-and-slow-sql](https://postgres.ai/blog/20210909-what-is-a-slow-sql-query#srt-and-slow-sql)
>
> Perhaps for us, 60 ms is still good, we may need to define this threshold before deciding whether or not to replace LTREE on the basis of performance.

| | Mean execution time | Min execution time | Max execution time | Number of rows |
|:------------------------------------------|:--------------------|:-------------------|:-------------------|:------------------------------|
| Ancestors with LTREE (@>) | 3.16ms | 1.54ms | 4.79ms | Number of ancestors: 14 |
| Ancestors with recursive | 1.34ms | 0.73ms | 1.74ms | Number of ancestors: 14 |
| Ancestors with recursive using function | 4.67ms | 2.882ms | 6.59ms | Number of ancestors: 14 |
| Descendants with LTREE (<@) | 36.36ms | 23.77ms | 54.21ms | Number of descendants: 4'212 |
| Descendants with recursive | 64.32ms | 39.12ms | 89.43ms | Number of descendants: 4'212 |
| Descendants with recursive using function | 54.27ms | 39.69ms | 80.95ms | Number of descendants: 4'212 |
| Children with LTREE (~) | 18.89ms | 11ms | 41.89ms | Number of children: 14 |
| Children with parentId | 0.51ms | 0.21ms | 0.82ms | Number of children: 14 |
| nlevel with LTREE | 2.33ms | 0.083ms | 0.598ms | nlevel: 15 |
| nlevel with recursive | 1.42ms | 0.3ms | 4.41ms | nlevel: 15 |
| nlevel with recursive using function | 4.78ms | 2.89ms | 7.3ms | nlevel: 15 |

As we can see from the results table, using functions can add a small overhead of 3ms ~, but I think it's negligible as the execution time remains low. I don't know whether this overload increases as the number of simultaneous requests increases.

> Get the item with the greatest number of ancestors

```
SELECT *
FROM item
ORDER BY nlevel(path) DESC
LIMIT 1;

```

- Greatest number of ancestors = 15 (nlvel = 15).
- Greatest number of descendants = 4'2012 (root of the item with the most ancestors).
- Number of children for the item with the most ancestors = 14.

> Ancestors

```
DISCARD ALL;
EXPLAIN ANALYZE
WITH RECURSIVE ancestors AS (
SELECT *
FROM item
WHERE
id = 'starting_item_id'
UNION ALL
SELECT i.*
FROM
item i
INNER JOIN ancestors a ON i.id = a.parentId
)
SELECT * FROM ancestors
```

```
DISCARD ALL;
EXPLAIN ANALYZE
SELECT *
FROM item
WHERE path @> 'starting_item_path'
AND id != 'starting_item_id'

```

> Descendants

```
DISCARD ALL;
EXPLAIN ANALYZE
WITH RECURSIVE descendants AS (
SELECT *
FROM item
WHERE
id = 'starting_item_id'
UNION ALL
SELECT i.*
FROM
item i
INNER JOIN descendants d ON i.parentId = d.id
)
SELECT * FROM descendants
```

```
DISCARD ALL;
EXPLAIN ANALYZE
SELECT id, name, path
FROM item
WHERE path <@ 'starting_item_path'
AND id != 'starting_item_id'

```

> Children

```
DISCARD ALL;
EXPLAIN ANALYZE
SELECT id, name, path
FROM item
WHERE parentId = 'parent_id'
```

```
DISCARD ALL;
EXPLAIN ANALYZE
SELECT id, name, path
FROM item
WHERE path ~ 'parent_item_path.*{1}'

```

> nlevel

```
DISCARD ALL;
EXPLAIN ANALYZE
WITH RECURSIVE ancestors(n) AS (
SELECT 1 as n, *
FROM item
WHERE
id = item_id
UNION ALL
SELECT n + 1, i.*
FROM
item i
INNER JOIN ancestors a ON i.id = a.parentId
)
SELECT max(n) AS nlevel FROM ancestors

```

```
DISCARD ALL;
EXPLAIN ANALYZE
SELECT nlevel(path) AS nlevel
FROM item
WHERE id = 'item_id'

```

> [!IMPORTANT]
> We should be aware of the infinite loop in the case the tree is a cyclic graph.

# How can we use these queries in TypeORM and in our codebase?

[Select using Query Builder \| typeorm](https://orkhan.gitbook.io/typeorm/docs/select-query-builder#common-table-expressions)
[Tree Entities \| typeorm](https://orkhan.gitbook.io/typeorm/docs/tree-entities#closure-table)

TypeORM offers support for common table expressions, but I'm not sure if it also supports recursive expressions. Even if this is the case, I don't feel that using CTE with QueryBuilder is the easiest way to implement this functionality.

```
const users = await connection.getRepository(User)
.createQueryBuilder('user')
.select("user.id", 'id')
.addCommonTableExpression(`
SELECT "userId" FROM "post"
`, 'post_users_ids')
.where(`user.id IN (SELECT "userId" FROM 'post_users_ids')`)
.getMany();
```

TypeORM also supports the Adjacency list and other patterns for storing tree structures. The TypeORM documentation informs us that it is not possible to load large trees at once, due to join limitations when using Adjacency list. I think this solution is interesting because it's similar to the recursive queries, but it makes it easier to use it in the code with tree entities.

```
import {
Entity,
Column,
PrimaryGeneratedColumn,
ManyToOne,
OneToMany,
} from "typeorm"

@Entity()
export class Category {
@PrimaryGeneratedColumn()
id: number

@Column()
name: string

@Column()
description: string

@ManyToOne((type) => Category, (category) => category.children)
parent: Category

@OneToMany((type) => Category, (category) => category.parent)
children: Category[]
}
```

I still see problems with this. First of all, we are still coupled to TypeORM (we tried to remove LTREE to be more independent from TypeORM, but this solution doesn't solve the problem). Another problem I can see is that we don't know how TypeORM implements it. So we need to learn more about it and how to use it correctly, and that can lead to performance issues depending on the TypeORM's implementation.
For these reasons, I wouldn't opt for a ready-made TypeORM solution.

## How to simplify the calls?

> [!NOTE]
> To simplify the calls, we could use our recursive queries in functions.
In those functions, the item is exclude! We are only retrieving its descendants or ancestors. We can adapt the code to include it. In this case, we could add a where clause to exclude it if we don't need it.

> [!NOTE]
> Also, if we only need the id of the items, we should avoid using \`\*\` because it prevent the DB to read the index only. This could be a good optimization.

> [!IMPORTANT]
> It seems that calling a function add an overhead of 3ms~ compared to calling the recursive queries directly.

> f_descendants_of

```
CREATE OR REPLACE FUNCTION f_descendants_of(item_id UUID)
RETURNS SETOF item
LANGUAGE sql AS
$func$
WITH RECURSIVE descendants AS (
SELECT
item.*
FROM item
WHERE
id = item_id
UNION ALL
SELECT
i.*
FROM
item i
INNER JOIN descendants d ON i.parentId = d.id
)
SELECT * FROM descendants where id <> item_id
$func$;

```

```
DISCARD ALL;
EXPLAIN ANALYZE
SELECT * FROM f_descendants_of('ITEM_ID')
```

> f_ancestors_of

```
CREATE OR REPLACE FUNCTION f_ancestors_of(item_id UUID)
RETURNS SETOF item
LANGUAGE sql AS
$func$
WITH RECURSIVE ancestors AS (
SELECT *
FROM item
WHERE
id = item_id
UNION ALL
SELECT i.*
FROM
item i
INNER JOIN ancestors a ON i.id = a.parentId
)
SELECT * FROM ancestors where id <> item_id
$func$;

```

```
DISCARD ALL;
EXPLAIN ANALYZE
SELECT * FROM f_ancestors_of('ITEM_ID')
```

> f_nlevel_of

```
CREATE OR REPLACE FUNCTION f_nlevel_of(item_id UUID)
RETURNS integer
LANGUAGE sql AS
$func$
WITH RECURSIVE ancestors(n) AS (
SELECT 1 as n, *
FROM item
WHERE
id = item_id
UNION ALL
SELECT n + 1, i.*
FROM
item i
INNER JOIN ancestors a ON i.id = a.parentId
)
SELECT max(n) FROM ancestors
$func$;

```

```
DISCARD ALL;
EXPLAIN ANALYZE
SELECT f_nlevel_of('ITEM_ID') as nlevel
```

The question is: How can we use postgresql functions in TypeORM using at least the QueryBuilder?

> Example of join

This code should work (not tested yet):

```
const query = this.repository
.createQueryBuilder('action')
.leftJoinAndSelect('action.item', 'item')
.leftJoinAndSelect('action.account', 'account')
.where('action.created_at BETWEEN :startDate AND :endDate', {
startDate,
endDate,
})
.andWhere('action.item_id IN (SELECT id FROM f_ancestors_of(:item_id))', { item_id })
.orderBy('action.created_at', 'DESC')
.limit(size);
```

As we can see, the code is not more complexe compared to the usage of the LTREE. In my opinion, we are even gaining in clarity (calling `f_ancestores_of` clearly indicates the intention compared to `@>`).

```
SELECT
a.*,
i.*
FROM action a
INNER JOIN item i ON a.item_id = i.id
WHERE i.id IN (SELECT id FROM f_ancestors_of('ITEM_ID'))
LIMIT 10
```

- **Mean:** 3.84ms

```
SELECT
a.*,
i.*
FROM action a
INNER JOIN item i ON a.item_id = i.id
WHERE i.path @> 'item_path' AND i.id != 'item_id'
LIMIT 10
```

- **Mean:** 5.82ms

> [!IMPORTANT]
> We should test other queries with joins to be sure that the performances are acceptable.

## Advantages and disadvantages of recursive queries

- Advantages compared to LTREE:
- Moving an item only requires a change to one row in the database VS updating the path of all the children.
- Combined with the usage of functions simplify the understanding of the code VS using abstract operators like @> or ~. This is also true if we hide LTREE operations behind a function.
- Needs less space to store a simple UUID vs LTREE.
- Disadvantages:
- The performance can be a bit slower (but nothing too significative).
- If we don't want to use the functions, the code is more complexe compared to the LTREE operators.

## How to limit the dependencies on the item's implementation

Using a recursive request does not solve the problem when other services know the details of the implementation. In fact, it is currently difficult to replace LTREE with another solution, as a large number of services or repositories depend on this implementation.

This problem could be mitigated by using functions in the repositories instead of using LTREE or recursive queries directly. Indeed, as all tables would have the item id instead of the item path, we can hide the logic of retrieving ancestors, descendants or direct parents or children behind the function. It's all very theoretical, but it should help us to change the structure of our element hierarchy more easily, without having to update all the dependent repositories, just the functions.
Another possibility would be to decompose a join by running multiple queries on a single table instead of a multi-table join, and then perform the join in the application. In this way, we could use the ItemService to get the ancestors and then use the results in the action query using the IN operator (for example). We need to be aware that this can cause performance problems because of the latency involved in communicating with the database. If this is what we want to achieve, we should test the performance of this solution.

I think the advantage of the latter solution is that we can define clear limits, but at a potential cost in terms of performance. We might prefer to start by encapsulating the logic in the functions and, on a second iteration, we might ask ourselves whether this is an interesting approach or not.

[https://www.kamilgrzybek.com/blog/posts/modular-monolith-integration-styles](https://www.kamilgrzybek.com/blog/posts/modular-monolith-integration-styles)
[https://learn.microsoft.com/en-us/ef/core/querying/single-split-queries](https://learn.microsoft.com/en-us/ef/core/querying/single-split-queries)
[https://github.com/ts-arch/ts-arch](https://github.com/ts-arch/ts-arch)

### Where are the ancestors used in the code (@>)?

> All usages

- ItemRepository
- getAncestors
- getOwn
- getPublishedItemsForMember
- GeolocationRepository
- getByItem
- InvitationRepository
- addMany
- ItemCategoryRepository
- getForItemOrParent
- ItemVisibilityRepository
- getType
- hasMany
- getManyVisibilitiesForTypes
- hasForMany
- getForManyItems
- ItemPublishedRepository
- getForItem (nlevel is needed!)
- getForItems
- getForMember
- ItemMembershipRepository
- getForManyItems
- getInheritedMany
- getInherited
- detachedMoveHousekeeping
- moveHousekeeping
- ItemMembershipUtils
- getPermissionsAtItemSql

### Where are the descendants used in the code (<@)?

> All usages

- ActionRepository
- getForItem
- getAggregationForItem
- ItemRepository
- checkNumberOfDescendants
- getDescendants
- getManyDescendants
- getNumberOfLevelsToFarthestChild??
- move
- getNextOrderCount
- getFirstOrderValue
- ItemGeolocationRepository
- getItemsIn
- ItemVisibilityRepository
- getManyBelowAndSelf
- deleteOne
- RecycledDataRepository
- getOwnRecycledItems
- ItemMembershipRepository
- getAllBelow
- getAccessibleItems
- getAccessibleItemNames

I haven't included the use of ~ and nlevel, but we should bear in mind that they also exist.

# Summary

So, should we change the LTREE to the recursive queries?

I think we should analyse more in depth to take a final decision, but it could be an interesting move (when used with functions or encapsulated in the ItemService) for the following reasons:

1. Saving more space.
2. Potentially remove the limit of number of descendans (to check, maybe the copy is still an issue?).
3. Improving the moves because only the parentId of the root should be updated (to check how much we are improving).
4. Using functions abstract the way we get the descendants or ancestors (still true if we are using LTREE and functions).