Modeling friend of friend relationships in MongoDB

Question

We need to be able to quickly perform queries across the set of a user's friends and friends of friends. This would be relatively straightforward in a relational database, but I'm somewhat stuck on the best way to accomplish it in MongoDB. We store the user IDs of a user's friends in an array in the user document, so the obvious solution is to do this:

• Pull all friend user IDs from user doc
• Pull all friend arrays from user docs of those friends (using an $in query across all friend IDs), combine application-side into one set, then combine that with first-level friend user IDs to get set of all friends and friends of friends
• Use that set to perform the final query (using $in) across all friends and friends of friends

While straightforward, this seems like a huge amount of back and forth, as compared to what we could do with a join in a relational database. Is there a more efficient way to do this in MongoDB, or is this a problem best suited for a RDBMS?

Answer 1

I asked Eliot Horowitz this very same question recently at MongoDB SV conference. He said the way he would structure it is to store each users friends as embedded documents within each user. For example, the structure might look like this:

{
  _id : ObjectId("4e77bb3b8a3e000000004f7a"),
  username : "alex",
  friends : ["283956723823626626aa", "226567377578888888as", "8738783888aas88a8a88" ]
}

then you can have an index on user.friends

http://www.mongodb.org/display/DOCS/Indexes#Indexes-IndexingArrayElements

"When a document's stored value for a index key field is an array, MongoDB indexes each element of the array. See the Multikeys page for more information."

so to find all of "alex"'s friends I can just do:

db.user.find( { 'friends' : '4e77bb3b8a3e000000004f7a'});