Ask HN: Implementing a graph database using Postgres tables for nodes and edges?
So I am considering a workaround to use a graph structure, but represent the underlying data in a reliable rdbms, in particular postgres.
The approach is: 1. Make two parent tables: node and edge. 2. Make separate tables for all "objects" (like people, places, things, etc.) which would be inherited from node, so they would all have a unique node ID. 3. Make separate tables inherited from edge which would be used to represent the many many relations. So each relation has an edge ID, and each table inherited from edge can be thought of as representing a specific kind of relation (like person lives in place, or person is friends with person).
One thing I have observed so far, is a large number of tables with few columns, but I think that lends itself to the advantage of easy indexing. There can be a large number of individual queries from the front end, but I believe I can use views to make represent tables with more comprehensive info to reduce the number of queries.
What do you guys think of an approach like this? What am I missing, what is wrong with it? I haven't come across this previously, and so am a bit nervous about the ramifications. Is someone else also doing this?
63 comments
[ 4.3 ms ] story [ 1400 ms ] threadIf 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.
However, if you have small graphs or only need conventional crud operations then using a new and unfamiliar graph db would probably be insane.
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.
I definitely need acid transactions, and also some graph capability - which may or may not grow in the future. More pertinently, the kind of representation I was attempting led to a very normalized design anyway, and I think it also lends itself to all but the most sophisticated of graph functionalities! But I am only just starting, so hopefully it works out well.
I do however recommend exploring and even building your own graph database, it is a great learning exercise. But don't fool yourself by doing it on top of Postgres, actually jump in and become immersed. I built http://gunDB.io/ 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.
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.
There are specialised triple store DBMSs, but implementing one in PostgreSQL should be pretty easy.
The issue is querying the data, specifically when that involves walking the graph.
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. "We will only ever perform queries that are at most 1 or 2 hops from the nodes/edges being queried" then perhaps PostgreSQL will work for you.
For shallow or narrow queries of the graph this is the way to go.
But for deep and broad queries, if you want to perform some valuable analysis that involves traversing the graph some non-trivial distance from the point of origin, that's where PostgreSQL is going to let you down and you would probably be better off picking a more appropriate tool.
Same question though: How do you want to query your graph, and are you willing to limit yourself to not querying it in a certain way?
This may be implementation-dependent but in theory, it's solid. I'm not sure what else a graph database would be able to do to beat an indexed adjacency list.
Implementation wise, it is not that different from a query with many joins anyway - which is a standard problem, and is addressed by materialized views as well as indexing. So as long as the complex queries don't need to be ad hoc and real time, I can prepare for them using materialized views.
However you are quite right in that complex, ad hoc, and realtime graph queries Will be a pain point. That is a risk I am prepared to tolerate in the short term. The thing is, I also need transactional integrity, so I am stuck with an rdbms as the primary solution. In the long term, I anticipate the need for both graph queries and transactions - thus, I think it is better to start with postgres and incorporate a graphdb as the need arises than the other way round.
Hopefully this line of reasoning make sense? I am really not experienced at this, so am trying to not bump into too many walls.
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)?
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.
* RDFLib Store for PostgreSQL ( https://github.com/RDFLib/rdflib-sqlalchemy )
* Sparqlify is a SPARQL-SQL rewriter that enables one to define RDF views on relational databases and query them with SPARQL. ( PostgreSQL supported http://aksw.org/Projects/Sparqlify.html )
* PostgreSQL-Neo4j Foreign Data Wrappers https://github.com/nuko-yokohama/neo4j_fdw
* PgRouting (network ) http://docs.pgrouting.org/dev/doc/src/tutorial/analytics.htm...
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 "find me all the people who are friends with my friends", you can write "find me all the people who are friends with my friends, or who have been to a place i've been, or who own a thing i own" without using a union. Do you actually need to write queries like that?
There are two downsides to the supertables. Firstly, more complexity, although it'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's no way to constrain particular kinds of edge to connecting particular kinds of node. That seems like a considerable drawback to me.
The generic kind of queries you mention: actually, yes, I think I will need them.
Your second point on downsides is something I have/had to think about, thanks for raising it. I had some vague premonitions on those lines, but you helped make it concrete. The problem can be avoided by not making meaningless connections, but that's not a real solution. It won't be a preventive, but it could help to audit relationships - by having a script list out which tables FKs originate from.
Since I started writing this post, I have had two ideas on how to address this, it'd be great to have your opinion on them - I'm thinking out loud here.
1. Use referential integrity. Since each relationship/edge will be in its own inherited table, one could impose a constraint that each column_in_the_specific_edge_table REFERENCES another_column_in_a_specific_node_table. Like the columns in the person_lives_in_place relationship table must reference columns in the person table and the place table - each of which is also its own inherited node table.
2. More convoluted and a bit cumbersome, but if the previous/simpler approach is insufficient, one could create data types corresponding to each node type. And impose that as a type constraint on the edge tables.
But maybe the 1st option could actually work...what do you think?
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.
On the other hand, cutting edge approaches, actually take a graph representation of data and lay it out in a relational manner. http://ercim-news.ercim.eu/en96/special/monetdb-rdf-discover... giving the best of both worlds.
In short you can build something yourself. But don't expect that it will be better than something build and supported by someone else.
So investigate the competition: BlazeGraph, Virtuoso, StarDog, Oracle 12c EE/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.
PS. The edge table (EAV) is the major problem, it leads to a lot of self joins and difficult exercises for the query planner.
You can improve a lot on this if you can put "different" edges into different tables or partitions.
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.
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)
> Node <- Entities
> Edge <- M2M
which is strange since an edge is already a M2M.
Thanks for the monetdb link.
That would be better than one big table in performance, which was a major problem in the RDF on SQL databases.
Of course those accepted any graph, if one constrains the number of possible predicates/relations then this solution could more efficient.
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.
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's what multi-model databases are tackling have a look at OrientDB and ArangoDB [1].
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].
[1] https://news.ycombinator.com/item?id=10180185
[2] https://news.ycombinator.com/item?id=10316140
Multi model db's are a good idea indeed. They were the first things I had considered, and extensively so - both OrientDB and ArangoDB. I came back to traditional solutions simply for practical reasons of maturity, and ease of finding professional support.
Someone here mentioned about a Tinkerpop implementation that uses Postgres as the storage engine, I think that might offer the best of both worlds, but I am yet to look into it.
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'm not sure why would people want to use a proper graph db.
I thought that probably it'd be an issue of performance: the "right tool for the job" that "does one thing and does it well" 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)
But then, when looking up some Neo4j benchmarks, the numbers seems to not be good at all:
http://baach.de/Members/jhb/neo4j-performance-compared-to-my...
I'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.
https://github.com/jhb/neo4j-experiements/blob/master/query_...
There's no way that a single HTTP request is responsible for a difference in hundreds of seconds
(his benchmark code isn't really sound, but I don't see how this can affect a difference so striking)
A proper graph db is almost mandatory if there are complex, ad hoc queries that need to be made on real time data.
Using an RDBMS is great if the graph query types are going to be known in advance - so they can be prepared for using materialized views and indexes, and if they aren't too complex - so one doesn't descend into JOIN-hell.
But most applications aren't like that, and not all applications can be completely satisfied using only a graphdb. Hence the rise of the new multimodel databases like OrientDB and ArangoDB. So I think it is a question of what risk one is prepared to tolerate.
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 / Postgres.
I didn't use table inheritance, and I don't distinguish relationships at the query stage, so if that's core to your method you should think about it. I assume with that setup it'd be easier to take advantage of partial indexes though.
Recursive queries work but if the intermediate tables gets large it explodes fast. You can'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...
I've had decent experience so far with GIN indexes and @> operators on an ARRAY[] column adjacency list. In my case I stored "ancestors" so I could select by object id and get all ancestors, or use `ancestors @> ARRAY[parent_id]` to select all object ids as descendants.
Of course, if you don't need any "self" relationships, then none of the really complicated stuff matters...
Indeed, one of the reasons behind inheriting tables was to use partial indexes - which should help with performance. Another was ease scaling out, if needed.
Using the @> operators on array columns is something I also looked into, mainly for materialized paths - I expect them to remain static, so no expensive updates to the paths/arrays. But actually, I don't think I will need many self relationships - that was the third reason for using inherited tables, so I could split entities into separate groups.
Of course, I have no idea how any of it will work out, since this was just a semi-serious line of inquiry initially, and everything was conceptual so far, except the feedback of experienced people such as yourself, on this thread - which has led me to pursue this seriously and actually try to build it out. After reading the responses on this thread, I now think it will be worth the effort.
* Trees in the database - Slides: http://www.slideshare.net/quipo/trees-in-the-database-advanc...
* Graphs in the database - Slides : http://www.slideshare.net/quipo/rdbms-in-the-social-networks...
The nice thing about your approach is that you can shard your objects by their id and your edges by their "from" id, and have all lookups go to one box when you shard. Throw in some caching and it scales to multiple boxes really well.
Actually, Facebook's TAO was an early inspiration for me as well, but it is really customized and complex too, so probably not something for a tiny team. But the concepts from TAO are applicable to many similar scenarios.