Proposal: Improve Merkle-Tree Database Layout

Approach

Currently we save nodes and edges in the same table: merkle_sbom_edges (subtree_hash, component_id, direct_dependency_subtree_hash)

A cleaner approach would be to separate nodes from edges. This would look like this:

Node table: component_id + subtree_hash
Edge table: subtree_hash + direct_dependency_subtree_hash

Possibly with a foreign key on edge_table.subtree_hash to node_table.subtree_hash

Performance Aspects

The whole performance improvements only stem from different scalings of nodes vs edges. Its effectiveness scales with the branching factor of each node , meaning how many edges each node has. If it were 1 meaning each node only has 1 edge we would just save redundant data in the node table.

But Currently the branching factor is a little over 6. So for each 6 rows in the edges table we get 1 row in the node table. therefore saving 6 times the component_id column in return for 1 extra record consisting of the subtree-hash and the component id. This is already a pretty decent ration in terms of columns , but if we translate that to bytes we get the following saving on paper:

Each component_id averages 80 characters = 80 bytes. Each subtree_hash ist exactly 128bit = 16 Byte in size. Meaning we strip 5 * 80 Bytes from the edges table for 16 more Bytes in the node table. This equals an improvement in disk space by a factor of 25 (regarding the component_id information).

When tested on the real data, the disk space goes from

• Edges: 75mb to 25mb
• Nodes: +7mb
  = Net saving of 57% in disk space

Less disk space also means overall better performance on all sorts of table scans and a bunch of other operations.

Summary

This approach lets us increase the scaling factor of our whole merkle strucure significantly, making it more resilient in the future where DevGuard handles a lot more data.

Performance is a feature

Locate the schema or migration entry point for merkle_sbom_edges, then trace uses of subtree_hash, component_id, and direct_dependency_subtree_hash. Done means nodes and edges are stored separately as proposed, with the relationship and performance implications addressed without losing existing Merkle-tree behavior.