I deal with several trees that can vary in size (they all have depths of ~8-10) but it's not unusual for them to consist of ~50-100k nodes.
At the moment, the trees are stored using simple parent_id FKs.
A tree is created/generated in a program, and then it needs to be saved in the database. The catch is that we cannot just wipe the previous tree (of the same type, if one exists), we need to update it to reflect the new (changed) tree. Occasionally this means swapping the entire tree (if the root changed), but a lot of the time it just means minor changes here and there (e.g. add some children/sub-trees, retire others). We also do not delete old children (and their children), they just get marked as old.
The way updates/verifications are done is by traversing through the tree (depth-first) and checking each node one-by-one.
One of the performance issues is that it can take almost 2 minutes to just verify that a tree (~50k nodes) in the db is the same as the one in the program (since it involves n selects where n is the number of total nodes).
While utilizing an ltree structure could be beneficial in terms of reads, I don't think it would solve this issue (inserting/updating/verifying a tree).
I'm not sure what the best way to optimize this is. One idea I had was to calculate and store a hash of every sub-tree, and that way it could potentially speed things up in most cases since it would know what parts of the tree that doesn't need touching. The hash calculation should be pretty fast and can be parallelized in the program, where the workload is easier to manage. However, perhaps there is some other way that I'm missing?
Bulk inserts etc. are impossible since the tree relies on recursive relationships.
Furthermore, the database is naturally in the cloud, which means that these thousands of queries being executed one-by-one probably incur quite a bit of time just in terms of latency (both the program and the db are on AWS so the latency is small, but still exists of course). A part of me wants to bulk insert the newly generated tree into some temporary table and then write a DB function that syncs it into the actual table.
General structure/schema of a tree:
- Each node has an id and a parent_id column (nullable FK to id)
- The root node has parent_id=NULL
- What makes each node unique is (parent_id, attrs...)
- Meaning that duplicate nodes can exist in multiple places in the tree
- Nodes are only added or marked as obsolete
Any advice is much appreciated!