Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I need 2 capabilities:

  • calculating mutual friends distinguishing between different types of edges, (e.g. FRIEND, ENEMY and other)
  • getting relationships distinguishing between different types of edges as over

My problem is speed: If I use a database as MySQL, I can get thousands of relationships in few moments, but if I need to calculate mutual friends, it costs a lot for my server, doesn't it?

I've about 100,000 accounts on my site, and I want to introduce a relationship system, but obviously I have to decide the right way to develop it. Do you have any idea?

share|improve this question
1  
I hate to disagree with most of the posters but wouldn't a relational database seem the obvious choice for managing relationships? 100,000 rows does not count as "big" or even "medium" these days. –  James Anderson Aug 7 '13 at 7:08

4 Answers 4

Since you have 100k user accounts on site, I will run a quick estimate for you:

  • 100k accounts
  • [assumption] ~30% of accounts are actually active
  • [assumption] ~20% of active accounts will have 100 relationships on average
  • [assumption] ~80% of active accounts will have 10 relationship on average

Or in other words:

  • 70k users are basically inactive
  • 24k users will have 10 relationships on average
  • 6k users will have 100 relationships on average

This means that your many-to-many relationship table will have:

70k * 0 + 24k * 10 + 6k * 100 = 840k rows or ~1 million rows

Honestly, 1M rows is peanuts for a properly configured RDBMS. Furthermore, you will probably able to cope until you have around a few million accounts by just scaling up.


Note: the assumption is that you add a table similar to this:

SourceUserId, DestinationUserId, LoveOrHate
share|improve this answer
1  
hehehe I worked on a project where they had to import about that... 1 000 000 rows spread in about 4 tables (person, phone, address etc) all text, super simple. For some reason we were not allowed to do SQL so we had to use their tools. 2 weeks it took in all for a server running the import 24/7. –  Newtopian Nov 21 '11 at 12:04
1  
@Newtopian, I feel your pain. I once inserted 21 million rows using bulk insert in 16 minutes. 2 weeks for a million is so horrible. –  HLGEM Nov 21 '11 at 15:14

First of all, getting list of mutual friends is fairly easy and fast operation regardless of which solution you choose. It's just get all user A friends, get all user B friends and intersect the results.

Many RDBMSes implement that natively using INTERSECT, some of NoSQL stores also have set intersection commands (eg. SINTER in Redis).

Another thing is the performance of graph DBs isn't that great. Of course they advertise improvement of "1000x or more compared to relational DBs". However, this is improvement for generic graphs and generic graph algorithms. They give you much more flexibility, but if you have only few types of relations, dedicated code built on top of RDBMS or NoSQL will be more efficient.

share|improve this answer

Checkout any new breed of NoSQL Databases. eg. MongoDB, CounchDB, Redis. Even Tokyo Cabinet or Kyoto Cabinet is worth exploring depending on respond time you are looking for.

Basically MySQL or any relational database would employ joins which will be costly !! Consider duplicating the data at the time of storing, so that you don't have to join at the time of query !! Your data need not be in perfect normalized form.

Also important aspect that you have not specified here is how much transactional this operation need to be ! Do you want the integrity of the data to be maintained every second to second or every minute to minute ? Is eventual integrity ok ?

share|improve this answer
    
What design should I use using key-value DB as Redis? The calculation of mutual friends, will be done very often, and the data isn't updated very often. –  rodi Oct 22 '11 at 15:41
    
Please be specific "very often" is very relative term. Could you describe the scenarios that are involved ? Be precise and if possible be concise !! –  Samyak Bhuta Oct 22 '11 at 17:51
    
Mutual friends are calculated at least 5-6 times each page loaded. There is an avarage of 90/100 pages loaded/s including ajax requests. –  rodi Oct 23 '11 at 11:34
    
This answer does not convince me in the least that I should use NoSQL. NoSQL represents a gazillion different paradigms. Not all are appropriate here. Also, "joins are slow", really? –  Ebenezer Sklivvze Nov 21 '11 at 11:13
    
Not having joins basically means to precalculate the connections. This can be done. But assume a user has 500 direct contacts, 10000 indirect contacts, and 50000 contacts to the third degree. of Course one can precalcualte this (one could do this in a relational system , too btw.) and the user account is deleted - you suddenly have to change 60500 documents. This can be done, but changing one row in a normalized relational schema could be more efficient. "NoSQL" per se is not the answer, a Graph database might. A properly configured NoSQL might work, though, as a relational might, too. –  johannes Nov 21 '11 at 12:32

You can use a graph database like Neo4j.

...an open-source, high-performance, enterprise-grade NOSQL graph database.

Neo4j is a robust (fully ACID) transactional property graph database. Due to its graph data model, Neo4j is highly agile and blazing fast. For connected data operations, Neo4j runs a thousand times faster than relational databases....

They are good for relations between users in e.g. a social network site.

share|improve this answer
    
Can it handle more then 2-3kqueries/s on a db with 100k of vertexes and some milion of edges? –  rodi Oct 22 '11 at 15:36
    
@rodi: That totally depends on what hardware you have and how you implement your application. But from the Neo website: "Neo4j offers performance improvements on the order of 1000x or more compared to relational DBs" –  Jonas Oct 22 '11 at 17:22
    
1000x itinerating among vertexes maybe, but how much faster in fetching data having an id? for exemple in a query as SELECT * FROM relations WHERE account_id = 1; –  rodi Oct 22 '11 at 18:07
1  
@rodi: Again, this depends on your hardware. You have to test it. –  Jonas Oct 22 '11 at 18:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.