Ask HN: Implementing a graph database using Postgres tables for nodes and edges?

Storing the data isn&#x27;t an issue. It&#x27;s fairly trivial to come up with a number of very good solutions to describing a graph.<p>The issue is querying the data, specifically when that involves walking the graph.<p>The real question then, is how do you want to query the data? If you are willing to make an assumption now that adds a tight constraint on your future work... i.e. &quot;We will only ever perform queries that are at most 1 or 2 hops from the nodes&#x2F;edges being queried&quot; then perhaps PostgreSQL will work for you.

The boring answer is that it depends on your data and what you need to do with it. Insights like &quot;all data structures are graphs!&quot; are dangerous - it can actually add vagueness that might prevent more useful understanding of your problem. Excessively generic handling of data often ends in pain when it comes to the real world (performance and complexity) compared to domain specific approaches.<p>If you have multi GB graphs and need to run intensive classic graph analysis algorithms then a lot of that can come optimised out of the box with a dedicated graph db. They will still leave you with plenty of hard problems.<p>However, if you have small graphs or only need conventional crud operations then using a new and unfamiliar graph db would probably be insane.<p>If your case is the latter and postgres is your comfort zone and you can get a working solution quickly, I would be tempted to prototype along the lines you suggest. When you start getting performance problems or need graph analysis, you can then make a better decision whether a graphdb or restructuring your relational db will solve it the best.

The PostgreSQL Conference 2011 :&quot;Trees and Graphs in the database&quot; <a href="https:&#x2F;&#x2F;www.pgcon.org&#x2F;2011&#x2F;schedule&#x2F;events&#x2F;357.en.html" rel="nofollow">https:&#x2F;&#x2F;www.pgcon.org&#x2F;2011&#x2F;schedule&#x2F;events&#x2F;357.en.html</a><p>* Trees in the database - Slides: <a href="http:&#x2F;&#x2F;www.slideshare.net&#x2F;quipo&#x2F;trees-in-the-database-advanced-data-structures" rel="nofollow">http:&#x2F;&#x2F;www.slideshare.net&#x2F;quipo&#x2F;trees-in-the-database-advanc...</a><p>* Graphs in the database - Slides : <a href="http:&#x2F;&#x2F;www.slideshare.net&#x2F;quipo&#x2F;rdbms-in-the-social-networks-age" rel="nofollow">http:&#x2F;&#x2F;www.slideshare.net&#x2F;quipo&#x2F;rdbms-in-the-social-networks...</a>

I am a huge fan of the Tinkerpop Stack (<a href="http:&#x2F;&#x2F;tinkerpop.incubator.apache.org" rel="nofollow">http:&#x2F;&#x2F;tinkerpop.incubator.apache.org</a>) -- they have written a common set of interfaces for graph databases. There is an implementation that can use Postgres as its storage engine (<a href="https:&#x2F;&#x2F;github.com&#x2F;pietermartin&#x2F;sqlg" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;pietermartin&#x2F;sqlg</a>), there is one that can use ElasticSearch, I even seen one that uses MongoDB. Check it out

This sounds broadly sensible. It&#x27;s basically a classic normalised relational design, which is as perfect as alligators or sewing needles, but with extracted supertables for nodes and edges.<p>I would challenge the idea that you need these supertables, though. What those allow you to do is to write graph queries which are generic (polymorphic?) over multiple kinds of node and edge. So as well as &quot;find me all the people who are friends with my friends&quot;, you can write &quot;find me all the people who are friends with my friends, or who have been to a place i&#x27;ve been, or who own a thing i own&quot; without using a union. Do you actually need to write queries like that?<p>There are two downsides to the supertables. Firstly, more complexity, although it&#x27;s a minor, or at least constant-factor, amount. Secondly, a loss of type safety. If your edges are defined in a supertable, then the columns which point to the ends of the edge have to be foreign keys to the node supertable. That means they can be any type of node; there&#x27;s no way to constrain particular kinds of edge to connecting particular kinds of node. That seems like a considerable drawback to me.

Why re-invent the wheel ! All you need to do is properly understand your tool of choice. I have used Neo4j extensively for years and have had great results. Our biggest hurdle was understanding how to model the data for a graph properly. Get this right and everything falls into place. The one thing you are going to need is a good visualisation tool, so be prepared to roll one of these too :)

I was also wondering about the same thing:<p>Implementing a graph on top of a RDBMS is trivial, and if the semantics are correct (the same as the ones exposed by a graph db?), then I&#x27;m not sure why would people want to use a proper graph db.<p>I thought that probably it&#x27;d be an issue of performance: the &quot;right tool for the job&quot; that &quot;does one thing and does it well&quot; probably is leaner and more efficient. After all, unlike a trivial implementation, getting a graph on a RDBMS to perform well might not be that simple after all (still, your idea of inheriting tables might make things more flexible and maybe more efficient)<p>But then, when looking up some Neo4j benchmarks, the numbers seems to not be good at all:<p><a href="http:&#x2F;&#x2F;baach.de&#x2F;Members&#x2F;jhb&#x2F;neo4j-performance-compared-to-mysql" rel="nofollow">http:&#x2F;&#x2F;baach.de&#x2F;Members&#x2F;jhb&#x2F;neo4j-performance-compared-to-my...</a><p>I&#x27;d like to hear from someone that used Neo4j (also, other graph databases are interesting) in production, and benchmarked it against a RDBMS prototype, finding the former as the better solution of the two.

I&#x27;ve done this a few times. First, see the list of PostgreSQL-based extensions and tools listed by other folks below; they&#x27;re all good things to look at before you implement something from scratch. Regardless, this is probably a good approach if you are using Postgres anyway and just need a graph for part of your application.<p>For short graph traversals, recursive queries and joins perform surprisingly well, even when compared against dedicated graph databases -- at least, the open source ones I&#x27;ve been able to try, including neo4j. The ones I&#x27;ve tried perform better than Postgres mostly when you get more than two hops away -- but then at least Neo and the MySQL thing tend to suffer if the data set doesn&#x27;t fit in memory.<p>I had at least one project which reverted from a dedicated graph database to Postgres specifically because it needed decent on-disk performance (2TB per shard).<p>Anyway, to your question: you could build a PostgreSQL database like that, but why would you? If you have distinct types of entities (person vs. furniture vs. town), why would you denormalize them into generic node interitance? Having a completely abstracted database with one big table called &quot;things&quot; and another big table called &quot;relationships&quot; seems really attractive before you actually do it. Then it starts to suck.<p>Relational databases are designed to perform well, and to be easy to query, with &quot;normalized&quot; databases in which different types of entities are represented by different tables and relationships are defined by foreign keys. The further you get away from that model, the harder the database gets to use.<p>This is one of the problems with using graph concepts for questions which are not, fundamentally, graphs. Yes, you can define people&#x27;s nationality as a graph from location to nation, but that makes it pretty hard to do voter registration stats. Graphs are a great tool for answering many important questions, but they are not a great tool for answering <i>all</i> questions.<p>Now, if you are answering an actual graphing question (i.e. show me everyone who shares something in common with me via at least two links within 3 hops), then proceed. But figure out what kinds of questions you specifically want to answer before you get too far.

some alternatives to check :<p>* RDFLib Store for PostgreSQL ( <a href="https:&#x2F;&#x2F;github.com&#x2F;RDFLib&#x2F;rdflib-sqlalchemy" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;RDFLib&#x2F;rdflib-sqlalchemy</a> )<p>* Sparqlify is a SPARQL-SQL rewriter that enables one to define RDF views on relational databases and query them with SPARQL. ( PostgreSQL supported <a href="http:&#x2F;&#x2F;aksw.org&#x2F;Projects&#x2F;Sparqlify.html" rel="nofollow">http:&#x2F;&#x2F;aksw.org&#x2F;Projects&#x2F;Sparqlify.html</a> )<p>* PostgreSQL-Neo4j Foreign Data Wrappers <a href="https:&#x2F;&#x2F;github.com&#x2F;nuko-yokohama&#x2F;neo4j_fdw" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;nuko-yokohama&#x2F;neo4j_fdw</a><p>* PgRouting (network ) <a href="http:&#x2F;&#x2F;docs.pgrouting.org&#x2F;dev&#x2F;doc&#x2F;src&#x2F;tutorial&#x2F;analytics.html#graph-analytics" rel="nofollow">http:&#x2F;&#x2F;docs.pgrouting.org&#x2F;dev&#x2F;doc&#x2F;src&#x2F;tutorial&#x2F;analytics.htm...</a>

I think you want to google &quot;triple store&quot; because that is effectively what you are trying to do AIUI. Triple stores are the persistence strategy of choice for RDF and other Semantic-Web-type applications.<p>Each row in a triple store stores a relationship between 2 objects, with unique IDs for the subject, the relationship type, and the object. The IDs could refer to other tables that store entity and relationship details.<p>There are specialised triple store DBMSs, but implementing one in PostgreSQL should be pretty easy.

No-one seems to have yet mentioned Facebook&#x27;s TAO paper, which describes scaling basically this approach to 1 billion reads per second. <a href="https:&#x2F;&#x2F;cs.uwaterloo.ca&#x2F;~brecht&#x2F;courses&#x2F;854-Emerging-2014&#x2F;readings&#x2F;data-store&#x2F;tao-facebook-distributed-datastore-atc-2013.pdf" rel="nofollow">https:&#x2F;&#x2F;cs.uwaterloo.ca&#x2F;~brecht&#x2F;courses&#x2F;854-Emerging-2014&#x2F;re...</a><p>The nice thing about your approach is that you can shard your objects by their id and your edges by their &quot;from&quot; id, and have all lookups go to one box when you shard. Throw in some caching and it scales to multiple boxes really well.

If directed acyclic is sufficient for your use case, you can use this approach, which has worked perfectly for me in the past: <a href="http:&#x2F;&#x2F;www.codeproject.com&#x2F;Articles&#x2F;22824&#x2F;A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o" rel="nofollow">http:&#x2F;&#x2F;www.codeproject.com&#x2F;Articles&#x2F;22824&#x2F;A-Model-to-Represe...</a>

I use Neo4J and I&#x27;m curious what negative experiences you are referring to, and what benefit this might have over that. The biggest problem I foresee is querying and possibly data integrity. Querying since doing any kind of graph traversal would probably require writing hacks in software, and data integrity for much of the same reason. It may be easy to ensure a basic relationship but beyond that I would think it would be more difficult.

I&#x27;ve done this a few times. Depending on the size&#x2F;density of your data, it can be fine. If you have billions of entities and&#x2F;or highly dense relations, it&#x27;s not very efficient though.<p>I didn&#x27;t use table inheritance, and I don&#x27;t distinguish relationships at the query stage, so if that&#x27;s core to your method you should think about it. I assume with that setup it&#x27;d be easier to take advantage of partial indexes though.<p>Recursive queries work but if the intermediate tables gets large it explodes fast. You can&#x27;t use aggregates in the recursive function either (e.g. to count number of leaf nodes in a tree), you have to apply them at the end, in which case the intermediate table has to be large...<p>I&#x27;ve had decent experience so far with GIN indexes and @&gt; operators on an ARRAY[] column adjacency list. In my case I stored &quot;ancestors&quot; so I could select by object id and get all ancestors, or use `ancestors @&gt; ARRAY[parent_id]` to select all object ids as descendants.<p>Of course, if you don&#x27;t need any &quot;self&quot; relationships, then none of the really complicated stuff matters...

I had a similar challenge and ended up using ElasticSearch in a thoroughly denormalized data format Allowed me the flexibility of stateful (contextual) queries etc. Bit of a hack, but served my purpose. Hope that helps.

A lot of the early academic RDF graph databases used this approach. However, performance was no where near to what is required. This let to for the SPARQL&#x2F;RDF graph databases to now a whole set of independently developed stores. Some on top of existing solutions e.g. Oracle semnet, Virtuoso and DB2 sparql. More on their own solid foundations.<p>You could test out 3 or 4 different SPARQL solutions in the time that it would take you to develop something graph like on your own.<p>On the other hand, cutting edge approaches, actually take a graph representation of data and lay it out in a relational manner. <a href="http:&#x2F;&#x2F;ercim-news.ercim.eu&#x2F;en96&#x2F;special&#x2F;monetdb-rdf-discovering-and-exploiting-the-emergent-schema-of-rdf-data" rel="nofollow">http:&#x2F;&#x2F;ercim-news.ercim.eu&#x2F;en96&#x2F;special&#x2F;monetdb-rdf-discover...</a> giving the best of both worlds.<p>In short you can build something yourself. But don&#x27;t expect that it will be better than something build and supported by someone else.<p>So investigate the competition: BlazeGraph, Virtuoso, StarDog, Oracle 12c EE&#x2F;semnet, DB9, Dydra before deciding to build your own. Building your own because its fun to do is great, but unless it pays your bills not a good idea for production environment.<p>PS. The edge table (EAV) is the major problem, it leads to a lot of self joins and difficult exercises for the query planner.<p>You can improve a lot on this if you can put &quot;different&quot; edges into different tables or partitions.<p>Triple stores with support for JSON-LD framing such as Dydra can also make it easier to have a front-end on top of your DB without extensive middle layer code.<p>A store like StarDog and BlazeGraph on the other hand gives you a lot of flexibility by both supporting SPARQL and TinkerPop. (both cluster and scale out, although BlazeGraph has GPL option. StarDog is only Commercial)

<a href="https:&#x2F;&#x2F;www.facebook.com&#x2F;notes&#x2F;facebook-engineering&#x2F;tao-the-power-of-the-graph&#x2F;10151525983993920" rel="nofollow">https:&#x2F;&#x2F;www.facebook.com&#x2F;notes&#x2F;facebook-engineering&#x2F;tao-the-...</a>

One technique you might look into is &quot;Materialized Path&quot;:<p>* usually one single query to fetch an entire tree or subtree * more work on reconstructing tree from query result * requires prefix pattern matching operator, e.g. &quot;like&quot; from RDBMS

Dropbox does something similar called Edgestore which is built on top of MySQL: <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=VZ-zJEWi-Vo" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=VZ-zJEWi-Vo</a>

Building a graph database is time consuming. Why are you putting edge&#x27;s children (person, place, friend) in a separate table instead of using a json field? Do you plan to query the person, place, friend table directly? You need to benchmark the different queries.<p>My understanding is that big5 and others do not use graphdb for all their stuff since they are not as good as rdbms to do queries with a single hop or JOIN. They embrace microservices and maintain a graphdb (in memory, persistent or distributed) to answer domain specific queries. That approach is similar to your schema except that graph queries run on a single node without superfluous network roundtrips.<p>It would be nice to be able to use a single database for all data related stuff to have atomic writes and simpler architecture. That&#x27;s what multi-model databases are tackling have a look at OrientDB and ArangoDB [1].<p>Also, Tinkerpop, already mentioned in the thread, is a ready-to-scale graphdb with much love I recommend you have a look at Tales of the Tinkerpop [2].<p>[1] <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=10180185" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=10180185</a><p>[2] <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=10316140" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=10316140</a>

I&#x27;ve done this before with MySQL in 2011 after throwing my hands in the air with two different graph DBs.<p>By far the most productive thing I did. People will say that you need recursive queries, etc, but I found most of the time just keeping the query set in the application layer was easy enough and super fast. Scaling it was easier too because there are lots of articles on scaling the MySQL &#x2F; Postgres.

I&#x27;d do the same. I think this book is still relevant: <a href="http:&#x2F;&#x2F;www.amazon.com&#x2F;SQL-Antipatterns-Programming-Pragmatic-Programmers&#x2F;dp&#x2F;1934356557" rel="nofollow">http:&#x2F;&#x2F;www.amazon.com&#x2F;SQL-Antipatterns-Programming-Pragmatic...</a>

If you want to help hack on this, I&#x27;ve written a Postgres backend for the graph database Cayley that&#x27;s fairly fast and about to merge (for use on a prod feature): <a href="https:&#x2F;&#x2F;github.com&#x2F;google&#x2F;cayley&#x2F;pull&#x2F;289" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;google&#x2F;cayley&#x2F;pull&#x2F;289</a><p>For traversals, it tries its level best to let Postgres create the appropriate JOINs, which Postgres does well... most of the time anyway. In doing this, I learned really fast how many weird semantic corners of bog-standard SQL are, and the optimization choices Postgres makes based on the way you formulate the query.<p>Ping me on that PR! And&#x2F;or join #cayley on Freenode

What are you actually trying to do? If you just need some queries on a small amount of read-only data, objects in memory (in a dedicated process, perhaps) are a perfectly sane approach, and much faster than ping-ponging queries with any database.

I believe Redis and Hyperdex have constructs such as bitarrays and sets that can be easily used for representing and querying graphs&#x2F;hypergraphs. For Redis there are some success stories and even ready to use extensions.

I don&#x27;t know much about this but Joe Celko has a whole book on representing trees in SQL: <a href="http:&#x2F;&#x2F;www.amazon.co.uk&#x2F;Hierarchies-Smarties-Kaufmann-Management-Systems&#x2F;dp&#x2F;0123877334&#x2F;" rel="nofollow">http:&#x2F;&#x2F;www.amazon.co.uk&#x2F;Hierarchies-Smarties-Kaufmann-Manage...</a><p>The obvious first question would be: why are you representing your data as a graph? Can you represent it better as sets of predicates (ie: relations)?<p>Using views should not reduce the number of queries: a view is just a query with a name. If you can do it by combining views you can do it by combining queries.

I would love to see a SQLite extension to support graphs...

This is fairly timely as I&#x27;m investigating possibilities for our data model and graphdb just popped up on my radar. Are gdb good for modeling multiple types of products? Let&#x27;s say v1 of product has attributes a, b, c but v2 now adds x, y, z and removes a. Would that be 2 separate nodes?<p>I too am interested in understanding the downsides of a gdb (seeing some refs to performance but nothing concrete).

Do you have a gist that implements this approach?

I met with Kyle Kingsbury (Aphyr of Call Me Maybe the Jepsen database testing series) out in Berlin and I recall him mentioning at one point that Postgres was a good generic database especially with the JSON blob storage. So I am wondering if making the extensions you propose might not be worth it cause it will come with all that extra overhead.<p>I do however recommend exploring and even building your own graph database, it is a great learning exercise. But don&#x27;t fool yourself by doing it on top of Postgres, actually jump in and become immersed. I built <a href="http:&#x2F;&#x2F;gunDB.io&#x2F;" rel="nofollow">http:&#x2F;&#x2F;gunDB.io&#x2F;</a> to scratch a similar itch, I wanted an easy graph database with realtime updates like Firebase. I would love to hear your feedback, or even have you contribute.