dimanche 28 juin 2015

Mysql sub-filtering

Let's say I have a table U of users and a table R which represents the relations (friendships) between the users. Users are able to create posts which are saved in another table P (with the user_id of the user who sent the post).

I want to retrieve all the posts made by friends of friends of friends.... of friends of a specific person. This means when e.g. I have the following setup:

users (U)
  id - name
  1 - Mark
  2 - Eve
  3 - Peter

relations (R)
  id_user1 - id_user2
  1 - 2
  2 - 3

posts (P)
  id - user_id - text
  1 - 1 - "Hello from Mark"
  2 - 2 - "Hello from Eve"
  3 - 3 - "Hello from Peter"

and I want to retrieve all messages made by Mark, i would simply select all posts with Mark's user_id. But its getting tricky when I want to retrieve all the posts made by Mark's friends. Mark has only one friend in this example, so it's kind of obvious that we would get Eve's and Mark's post here. But let's assume he has 500. I would first execute a SQL command to retrieve all his friends and then do something like

SELECT * from posts WHERE user_id in (2,4,5,6,7,8,9,10,11,12.....,1442);

Well that seems quite inefficient, but it gets even worse when I want to get the messages made by friends of his friends (or even more sub-friend layers n): I would make n requests (one for each layer) to retrieve the id's of his friend's friends like in the example above. Then, when I have the result of the Id's of his n-sub-friends, I would do the same as above. For example, when we want to retrieve all posts by Marks friend's friends, we would get all the posts because Mark's friend Eve has Peter as a friend.

When the user has only 10 friends and each friend also got 10 friends, I would get 10^n ids. When I want to create a network containing ALL the posts of "somehow connected" friends, it would take ages to only get the ID's of all the users. And I guess the filtering with " in (....) " would take even longer when I pass like 100'000 id's.

Is there an efficient way to solve this problem?

I thought about saving some redundant data like associating every single sub-friend with every user directly in another table, but I doubt that this will work well because this would become a really gigantic table..

Aucun commentaire:

Enregistrer un commentaire