Best way to show friends of a user in alphabetical order

Question

On a social network I am working on in PHP/MySQL, I have a friends page, it will show all friends a user has, like most networks do. I have a friend table in mysql, it only has a few fields. auto_ID, from_user_ID, to_friend_ID, date

I would like to make the friends page have a few different options for sorting the results,
1) By auto_ID which is basicly in the order a friend was added. it is just an auto increment id
2) new friends by date, will use the date field
3) By friends name, will have a list in alphabetical order.

The alphabetical is where I need some advice. I will have a list of the alphabet A-Z, when a user clicks on K it will show all the user's name starting with K and so on. The trick is it needs to be fast so doing a JOIN on the user's table is not an option, even though most will argue it is fast, it is not the performance I am wanting for this action. One idea I had is to add an extra field to my friendship table and store the first letter of the users name in it. User's can change there name at anytime so I would have to make sure this is updated on possible thousands of records, anytime a user changes there name.

Is there a better way to do this?

Answer 1

Well if you don't want to do a join, then storing the user's name or initials on the friendships table is really your only other viable option. You mention the problem of having to update thousands of records every time a name changes, but is this really a problem? Unless you're talking about a major social networking site like Facebook, or maybe MySpace, does the average user really have enough friends to make this problematic? And then you have to multiply that by the probability that a user will change their name, which I would imagine isn't something that happens very often for each user.

If those updates are in fact non-trivial, you could always background or delay that to happen during non-peak times. Sure you would sacrifice up-to-the-second accuracy, but really, would most users even notice? Probably not.

Edit: Note, my answer above really only applies if you already have those levels of users. If you are still basically developing your site, just worry about getting it working, and worry about scaling problems when they become real problems.

Answer 2

I'd just join on the table that contains the name and then sort on the name. Assuming a pretty normal table layout:

Table Person: ID, FirstName, LastName

Table Friend: auto_ID, from_user_ID, to_friend_ID, date

You could do things like:

Select person.id, person.firstname, person.lastname, friend.auto_id 
from Friend
left join on person where person.id = friend.to_friend_ID
where friend.from_user_ID = 1
order by person.lastname, person.firstname

or

Select person.id, person.firstname, person.lastname, friend.auto_id 
from Friend
left join on person where person.id = friend.to_friend_ID
where friend.from_user_ID = 1
order by friend.date desc

I'd really recommend adding a column in the friend table to keep the first letter around, no need to duplicate data like that (and have to worry about keeping it in sync), that's what joins are for.

Answer 3

You could also look at a caching solution like memcached. You can have a background process that is always updating a memcached hash and then when you want this data it is already in memory.