How did they do it: FB prijatelji mojih prijatelja

[cvele]

Nesto od jutros razmisljam... fejsbuk ima zanimljiv feature da mozes da setujes politiku privatnosti tako da prijatelji tvojih prijatelja mogu da vide tvoje slike/updejtove sta god.

Pretpostavimo da mora da postoji tabela korisnika (users) koja primera radi izgleda ovako:

userid | username
------------------
1 | pera
------------------
2 | zika
------------------
3 | mika

i relaciona tabela za prijatelje (user_friends):

userid | friendid
----------------
1 | 2
----------------
2 | 1
----------------
2 | 3
----------------
3 | 2
(znaci pera i zika su se medjusobno dodali u prijatelje, a mika je prijatelj sa zikom dok nije prijatelj sa perom)

Takodje recimo da postoji tabela sa nekim sadrzajem(content) na koji je setovana opcija privatnosti da mogu da ga vide prijatelji i prijatelji prijatelja:

id | userid | content
-----------------------
1 | 1 | lepa brena
(dakle pera je postavio sadrzaj lepa brena)

Dakle imamo situaciju da se korisnik mika ulogovao i otisao na stranicu na kojoj se prikazuje sav sadrzaj koji on moze da vidi.
Mika moze da vidi "lepa brena" jer je prijatelj sa Zikom koji je prijatelj sa Perom. Znaci on je prijatelj prijatelja Pere.

Prva stvar koja bi trebalo da se uradi je spajanje users sa user_friends kako bi dobili Mikine prijatelje, pa onda opet spajanje istih tabela gde bi videli sve prijatelje Mikinih prijatelja (u ovom potskupu je i Pera). Pri svemu tome skup koji se napravi mora da bude distinct. Znajuci da u proseku FB korisnici imaju 150-250 prijatelja (licni zakljucak) dolazimo do situacije eksponencijalnog rasta ovog skupa prijatelja, nad kojim je distinct operacija veoma skupa. Kada uzmemo jos da to treba da spojimo sa sadrzajem, tebelom koja je znatno veca od skupa prijatelja i njihovih prijatelja (pod pretpostavkom da je svaki clan ostavio vise sadrzaja nego sto je ostavio prijatelja), dolazimo do jednog uzasno skupog upita.

Ipak ova operacija na FB ne deluje toliko skupa, tako da mi se cini da su to resili na pametniji nacin nego sto je ovaj moj.

Ima li neko ideju kako ?