I've heard repeated that SQL doesn't do friends of my friends very easy. I can't see any reason that that would be true.
select foaf.name from users foaf
join user_friends uf2 on uf2.friend_id = foaf.id
join user_friends uf1 on uf1.friend_id = uf2.user_id
join users me on me.id = uf1.user_id
where me.name = 'Alan';
With a "grouped" index on the user_friends table for user_id and on the users table for id, that should be reasonably efficient. In my thinking, it should be O( log(#users) + #myfriends + #theirfriends) though I don't know of any implementations that will actually do it that efficiently.
And when I say O( log(#users) + #myfriends + #theirfriends) I mean that many rows accessed. In theoretical fact, that should only work out to O(log(#users) + #theirfriends) disk seeks. log(#users) to figure out what my user.id is, two seeks through a grouped index to get the list of my friends (constant so drops out of O()) and then 1 + #theirfriends seeks through the grouped index on user_friends to get their friends' user.ids and 1+#theirfriends through the grouped index on user table to get the names of their friends.
Which leaves what I mean by a grouped index. I'm pretty sure I've seen it somewhere before, though possibly named something else; I don't remember. What I mean is a a multicolumn index on a table that the first column is treated as an offset into an array with pointers into the normal index, so for instance with the user_friends table, the first layer (user_id) is an offset( or cC language index) into a straight array of pointers into the BTree (or similar) of the index (user_id, friend_id). This way to get the my friends, knowing my user_id, you can jump directly to the subtree that has my friends. Why MySQL doesn't do this (assuming it doesn't based on usage) I can't figure out.
SQL as graph database
by alan on Mon 6th Jun 2011 3:33PM
This is a messy technical article.
I've heard repeated that SQL doesn't do friends of my friends very easy. I can't see any reason that that would be true.
With a "grouped" index on the user_friends table for user_id and on the users table for id, that should be reasonably efficient. In my thinking, it should be O( log(#users) + #myfriends + #theirfriends) though I don't know of any implementations that will actually do it that efficiently.SQL as graph database -- addendum
by alan on Mon 6th Jun 2011 3:48PM
And when I say O( log(#users) + #myfriends + #theirfriends) I mean that many rows accessed. In theoretical fact, that should only work out to O(log(#users) + #theirfriends) disk seeks. log(#users) to figure out what my user.id is, two seeks through a grouped index to get the list of my friends (constant so drops out of O()) and then 1 + #theirfriends seeks through the grouped index on user_friends to get their friends' user.ids and 1+#theirfriends through the grouped index on user table to get the names of their friends.
Which leaves what I mean by a grouped index. I'm pretty sure I've seen it somewhere before, though possibly named something else; I don't remember. What I mean is a a multicolumn index on a table that the first column is treated as an offset into an array with pointers into the normal index, so for instance with the user_friends table, the first layer (user_id) is an offset( or cC language index) into a straight array of pointers into the BTree (or similar) of the index (user_id, friend_id). This way to get the my friends, knowing my user_id, you can jump directly to the subtree that has my friends. Why MySQL doesn't do this (assuming it doesn't based on usage) I can't figure out.