Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Add LTREE Path in Groups #1980

Open
5 of 7 tasks
arvindh123 opened this issue Dec 15, 2023 · 4 comments · May be fixed by #2223
Open
5 of 7 tasks

Add LTREE Path in Groups #1980

arvindh123 opened this issue Dec 15, 2023 · 4 comments · May be fixed by #2223
Assignees
@arvindh123
Labels
enhancement
Milestone
0.15.0

Comments

@arvindh123
Copy link
Contributor

arvindh123 commented Dec 15, 2023 •
edited by WashingtonKK

We should have Postgres LTREE for groups https://www.postgresql.org/docs/current/ltree.html, which can use to query the group in hierarchy.

Implmentation

  • Create Extension LTREE in postgres
  • Add a column with name path and type as LTREE
  • While inserting new row
    • If the inserting new row have no parent . path column should have value of id
    • If the inserting new row have parent, Get the path column should have parent path + . + id
  • Retrieve Ancestors / Parents and Descendants / Children by using the below given examples as reference
  • If groups retrieve type is tree, then use nlevel to retrieve with level (depth) and let the max level be 5 or 10
    • Need to think about limits and offest if group retrieve type is tree , May be we can refer Magsitrala v0.12 implementation
      Ideas / Approaches :
      • By default we can show level 1 with pagination limit and offset. Stop support for view multiple level in retrieve. ( For this we already have get parent and children endpoints)
      • Retrieve groups with type tree supports only level and not support offset and limit
  • Use subpath to change parent. https://www.postgresql.org/docs/current/ltree.html#LTREE-FUNC-TABLE https://patshaughnessy.net/2017/12/14/manipulating-trees-using-sql-and-the-postgres-ltree-extension
  • Handle parent delete case. When parent is removed, in all path we should remove parent id

Example Group table

id parent_id domain_id name description metadata created_at updated_at updated_by status path
327b7cb1-15cc-4676-97a1-eebf42160e05 5a4faa5e-603d-4091-b0ec-5b7c3c894add group_1 {} 2024-04-03 15:41:20.425 0 327b7cb1-15cc-4676-97a1-eebf42160e05
ef5afb1b-942d-48a7-86c7-52fb00f2fb80 327b7cb1-15cc-4676-97a1-eebf42160e05 5a4faa5e-603d-4091-b0ec-5b7c3c894add group_2 {} 2024-04-26 11:32:06.402 0 327b7cb1-15cc-4676-97a1-eebf42160e05.ef5afb1b-942d-48a7-86c7-52fb00f2fb80
c8893978-74e2-49c1-bb3d-3678fc0cad2d 327b7cb1-15cc-4676-97a1-eebf42160e05 5a4faa5e-603d-4091-b0ec-5b7c3c894add group_2.1 2024-04-26 11:32:25.219 0 327b7cb1-15cc-4676-97a1-eebf42160e05.c8893978-74e2-49c1-bb3d-3678fc0cad2d
5c6de392-6dc4-46fc-8e2c-e6f4ce4fffab ef5afb1b-942d-48a7-86c7-52fb00f2fb80 5a4faa5e-603d-4091-b0ec-5b7c3c894add group_3 {} 2024-04-26 11:32:25.219 0 327b7cb1-15cc-4676-97a1-eebf42160e05.ef5afb1b-942d-48a7-86c7-52fb00f2fb80.5c6de392-6dc4-46fc-8e2c-e6f4ce4fffab
72e43862-86bb-4d01-9328-75734be53a3b ef5afb1b-942d-48a7-86c7-52fb00f2fb80 5a4faa5e-603d-4091-b0ec-5b7c3c894add group_4 {} 2024-04-26 11:32:29.941 0 327b7cb1-15cc-4676-97a1-eebf42160e05.ef5afb1b-942d-48a7-86c7-52fb00f2fb80.72e43862-86bb-4d01-9328-75734be53a3b

Above table in SQL

INSERT INTO public."groups" (id,parent_id,domain_id,"name",description,metadata,created_at,updated_at,updated_by,status,"path") VALUES
	 ('327b7cb1-15cc-4676-97a1-eebf42160e05',NULL,'5a4faa5e-603d-4091-b0ec-5b7c3c894add','group_1','','{}','2024-04-03 15:41:20.425',NULL,NULL,0,'327b7cb1-15cc-4676-97a1-eebf42160e05'::ltree),
	 ('ef5afb1b-942d-48a7-86c7-52fb00f2fb80','327b7cb1-15cc-4676-97a1-eebf42160e05','5a4faa5e-603d-4091-b0ec-5b7c3c894add','group_2','','{}','2024-04-26 11:32:06.402',NULL,NULL,0,'327b7cb1-15cc-4676-97a1-eebf42160e05.ef5afb1b-942d-48a7-86c7-52fb00f2fb80'::ltree),
	 ('c8893978-74e2-49c1-bb3d-3678fc0cad2d','327b7cb1-15cc-4676-97a1-eebf42160e05','5a4faa5e-603d-4091-b0ec-5b7c3c894add','group_2.1',NULL,NULL,'2024-04-26 11:32:25.219',NULL,NULL,0,'327b7cb1-15cc-4676-97a1-eebf42160e05.c8893978-74e2-49c1-bb3d-3678fc0cad2d'::ltree),
	 ('5c6de392-6dc4-46fc-8e2c-e6f4ce4fffab','ef5afb1b-942d-48a7-86c7-52fb00f2fb80','5a4faa5e-603d-4091-b0ec-5b7c3c894add','group_3','','{}','2024-04-26 11:32:25.219',NULL,NULL,0,'327b7cb1-15cc-4676-97a1-eebf42160e05.ef5afb1b-942d-48a7-86c7-52fb00f2fb80.5c6de392-6dc4-46fc-8e2c-e6f4ce4fffab'::ltree),
	 ('72e43862-86bb-4d01-9328-75734be53a3b','ef5afb1b-942d-48a7-86c7-52fb00f2fb80','5a4faa5e-603d-4091-b0ec-5b7c3c894add','group_4','','{}','2024-04-26 11:32:29.941',NULL,NULL,0,'327b7cb1-15cc-4676-97a1-eebf42160e05.ef5afb1b-942d-48a7-86c7-52fb00f2fb80.72e43862-86bb-4d01-9328-75734be53a3b'::ltree);

Get Parents (Ancestors)

select *, nlevel(path) from "groups"   where '327b7cb1-15cc-4676-97a1-eebf42160e05.ef5afb1b-942d-48a7-86c7-52fb00f2fb80' <@ path;

or

select *, nlevel(path) from "groups"   where ( select path from "groups" where id = 'ef5afb1b-942d-48a7-86c7-52fb00f2fb80') <@ path;

Output

id parent_id domain_id name description metadata created_at updated_at updated_by status path nlevel
ef5afb1b-942d-48a7-86c7-52fb00f2fb80 327b7cb1-15cc-4676-97a1-eebf42160e05 5a4faa5e-603d-4091-b0ec-5b7c3c894add group_2 {} 2024-04-26 11:32:06.402 0 327b7cb1-15cc-4676-97a1-eebf42160e05.ef5afb1b-942d-48a7-86c7-52fb00f2fb80 2
327b7cb1-15cc-4676-97a1-eebf42160e05 5a4faa5e-603d-4091-b0ec-5b7c3c894add group_1 {} 2024-04-03 15:41:20.425 0 327b7cb1-15cc-4676-97a1-eebf42160e05 1

Get Parents Count

select count(*) from "groups"  where  '327b7cb1-15cc-4676-97a1-eebf42160e05.ef5afb1b-942d-48a7-86c7-52fb00f2fb80' <@ path;

or

select count(*) from "groups"  where  ( select path from "groups" where id = 'ef5afb1b-942d-48a7-86c7-52fb00f2fb80') <@ path;

Output

count
2

Get Children (Descendants)

select *, nlevel(path)from "groups"   where '327b7cb1-15cc-4676-97a1-eebf42160e05.ef5afb1b-942d-48a7-86c7-52fb00f2fb80' @> path;

or

select *, nlevel(path)from "groups"   where ( select path from "groups" where id = 'ef5afb1b-942d-48a7-86c7-52fb00f2fb80') @> path;
id parent_id domain_id name description metadata created_at updated_at updated_by status path nlevel
ef5afb1b-942d-48a7-86c7-52fb00f2fb80 327b7cb1-15cc-4676-97a1-eebf42160e05 5a4faa5e-603d-4091-b0ec-5b7c3c894add group_2 {} 2024-04-26 11:32:06.402 0 327b7cb1-15cc-4676-97a1-eebf42160e05.ef5afb1b-942d-48a7-86c7-52fb00f2fb80 2
5c6de392-6dc4-46fc-8e2c-e6f4ce4fffab ef5afb1b-942d-48a7-86c7-52fb00f2fb80 5a4faa5e-603d-4091-b0ec-5b7c3c894add group_3 {} 2024-04-26 11:32:25.219 0 327b7cb1-15cc-4676-97a1-eebf42160e05.ef5afb1b-942d-48a7-86c7-52fb00f2fb80.5c6de392-6dc4-46fc-8e2c-e6f4ce4fffab 3
72e43862-86bb-4d01-9328-75734be53a3b ef5afb1b-942d-48a7-86c7-52fb00f2fb80 5a4faa5e-603d-4091-b0ec-5b7c3c894add group_4 {} 2024-04-26 11:32:29.941 0 327b7cb1-15cc-4676-97a1-eebf42160e05.ef5afb1b-942d-48a7-86c7-52fb00f2fb80.72e43862-86bb-4d01-9328-75734be53a3b 3

Get Children count

select count(*) from "groups"  where  '327b7cb1-15cc-4676-97a1-eebf42160e05.ef5afb1b-942d-48a7-86c7-52fb00f2fb80' @> path;

or

select count(*) from "groups"  where ( select path from "groups" where id = 'ef5afb1b-942d-48a7-86c7-52fb00f2fb80') @> path;
count
3
@arvindh123 arvindh123 self-assigned this Dec 19, 2023
@dborovcanin dborovcanin transferred this issue from absmach/magistrala-old Jan 10, 2024
@dborovcanin dborovcanin added this to the 0.15.0 milestone Mar 7, 2024
@arvindh123 arvindh123 mentioned this issue May 3, 2024
Open
4 tasks
@WashingtonKK WashingtonKK linked a pull request May 7, 2024 that will close this issue
Open
@WashingtonKK
Copy link
Contributor

WashingtonKK commented May 15, 2024 •
edited

@rodneyosodo and @arvindh123

Using LTREE to fetch groups as compared to using Recursion offers better performance.

I used retrieve all parents as an example, retrieving up to level 20 of the groups and here are the results.

Jaeger Results

Operation: Retrieve parents

Groups LTREE Time (ms) Recursion Time (ms)
10 0.386 1.03
30 0.703 0.986
45 0.832 1.96

SQL Explain

Insert into Groups:

Operation LTREE Cost Recursion Cost
Insert 0.00..0.06 0.00..0.06

Get Ancestors:

Operation LTREE Cost Recursion Cost
Get Ancestors 0.00..4.69 119.17..121.19

Get Parents Count:

Operation LTREE Cost Recursion Cost
Get Parents Count 0.00..4.69 121.44..121.45

Get Children:

Operation LTREE Cost Recursion Cost
Get Children 4.69..9.38 119.17..121.19

Get Children Count:

Operation LTREE Cost Recursion Cost
Get Children Count 0.00..4.69 121.44..121.45

Hyperfine Statistical Method

The operations below were carried out on 50 groups.

Operation LTREE Time (s) Recursion Time (s)
Create Groups(50) 1.155 1.107s
Get Parents 4.229 2.7 ms
Get Children 4.342s 2.6 ms

@rodneyosodo
Copy link
Member

Can you send the branch you used for testing?

@WashingtonKK
Copy link
Contributor

WashingtonKK commented May 15, 2024 •
edited

It is on this PR: #2223

Comparison is made with main.

@WashingtonKK
Copy link
Contributor

Additional remarks on this:

Using LTREE has a limitation since the trigger that creates the path in the db causes a significant use of the stack memory. This implies that creating more than 50 groups in a single family tree, i.e., descendants up to the 200th + level, which is possible with the current Recursive implementation.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@arvindh123 arvindh123

Labels
enhancement
Projects
Magistrala
Status: 🚧 In Progress
Milestone
0.15.0
Development

Successfully merging a pull request may close this issue.

MG-2214 - Add LTREE Path to Groups WashingtonKK/magistrala
4 participants
@dborovcanin @rodneyosodo @arvindh123 @WashingtonKK