Java - Google App Engine - modelling graph structures in Google Datastore
google-app-engine, google-cloud-datastore, java, nosql
Solution
First, the search time in the Datastore does not depend on the number of entities that you store, only on the number of entities that you retrieve. Therefore, if you need to find one relationship object out of a billion, it will take the same time as if you had just one object.
Second, the list approach has a serious limitation called "exploding indexes". You will have to index the property that contains a list to make it searchable. If you ever use a query that references more than just this property, you will run into this issue - google it to understand the implications.
Third, the list approach is much more expensive. Every time you add a new relationship, you will rewrite the entire entity at considerable writing cost. The reading costs will be higher too if you cannot use keys-only queries. With the object approach you can use keys-only queries to find relationships, and such queries are now free.
UPDATE:
If your relationships are directed, you may consider making Relationship entities children of User entities, and using an Object id as an id for a Relationship entity as well. Then your Relationship entity will have no properties at all, which is probably the most cost-efficient solution. You will be able to retrieve all objects owned by a user using keys-only ancestor queries.
Problem
Google Apps Engine offers the Google Datastore as the only NoSQL database (I think it is based on BigTable). In my application I have a social-like data structure and I want to model it as I would do in a graph database. My application must save heterogeneous objects (users,files,...) and relationships among them (such as user1 OWNS file2, user2 FOLLOWS user3, and so on). I'm looking for a good way to model this typical situation, and I thought to two families of solutions: List-based solutions: Any object contains a list of other related objects and the object presence in the list is itself the relationship (as Google said in the JDO part https://developers.google.com/appengine/docs/java/datastore/jdo/relationships). Graph-based solution: Both nodes and relationships are objects. The objects exist independently from the relationships while each relationship contain a reference to the two (or more) connected objects. What are strong and weak points of these two approaches? About approach 1: This is the simpler approach one can think of, and it is also presented in the official documentation but: - Each directed relationship make the object record grow: are there any limitations on the number of the possible relationships given for instance by the object dimension limit? - Is that a JDO feature or also the datastore structure allows that approach to be naturally implemented? - The relationship search time will increase with the list, is this solution suitable for large (million) of relationships? About approach 2: Each relationship can have a higher level of characterization (it is an object and it can have properties). And I think memory size is not a Google problem, but: - Each relationship requires its own record, so the search time for each related couple will increase as the total number of relationships increase. Is this suitable for large amount of relationships(millions, billions)? I.e. does Google have good tricks to search among records if they are well structured? Or I will be soon in a situation in which if I want to search a friend of User1 called User4 I have to wait seconds? - On the other side each object doesn't increase in dimension as new relationships are added. Could you help me to find other important points on the two approaches in such a way to chose the best model?