Few suggestions based on my prior experience on the same task in production system:- 1. Both the tables (Nodes and Edges) MUST HAVE one more column as "label"

Few suggestions based on my prior experience on the same task in production system:- 1. Both the tables (Nodes and Edges) MUST HAVE one more column as "label" and then you must create partitions based on distinct values of "label" column. This greatly helps queries to run faster as search plan is narrowed when you include it in where clause and PG knows partitions to hit. 2. Instead of one big fat primary key column in each table use, consider having different uniques indexes on each partition. 3. The EDGES table can afford to have "data" column of data type TEXT or perhaps JSONB. PG saves it in different data disk layout and compression works great here. We used it to cache the result for previous/next nodes data or compute the result for many extra hops which are required on frequent basis. 4. Use PG procedures to hide the complexity of reusable DFS/BFS queries.