Number of SELECT queries appropriate in a page

[Sam G]

Hi folks,

What I'd like to do for a website I'm designing with PHP/MySQL is have
a number of registered users who can make friends with each other...
so if person 1 wants to be friends with person 2, 1 can add 2 and then
they will be recognized as friends. I also want, if person 3 is
friends with 2, and goes to person 1's page, person 3 will see that 1
is friends with 2 who is 3's friend. So 3 can see the connections that
lead him to anyone else, up to, say, four friends away.

The design I've come up with so far is that each user will have a
unique userid in a users table, and a Friends table which will contain
two keys: friendID1 and friendID2; basically a many-to-many
relationship. Each time a friend is made a row will be inserted which
will relate one user to another. Then, on the user's profile page, a
SELECT clause will find all the user's friends (WHERE friendID1 =
userid OR friendID2 = userid).

What I'm wondering about is the connections. The best way I can think
of to do this would be, for example, if 3 visited 1, to select all of
3's friends and all of 1's friends, and find the ones in common. Those
are second degree connections. Then select all of 1's friends' friends
(which could be in the hundreds) and compare them to 3's friends and
3's friends' friends, and find the ones that are in common. That would
be third or fourth degree, depending which matches up.

Is that the most efficient way to do this? The site has to be capable
of hundreds of thousands of hits a day, as well as being very speedy.
Could this be an appropriate use of a "heap table"? Any suggestions
anyone can give me as to how to most efficiently execute this task
would be very much appreciated. Thanks.

-Sam

[Bill Karwin]

Sam G wrote:

Hi folks,

What I'd like to do for a website I'm designing with PHP/MySQL is have
a number of registered users who can make friends with each other...
That's very sweet. I'm sure we would all like this to happen! :-)
What I'm wondering about is the connections.
In Joe Celko's "SQL for Smarties", he discusses relational
representations of recursive data structures like trees and graphs.

Basically, once you have a table for users and a table of direct
friendships, you can create a third table that enumerates all unique
paths through the web of connections.

CREATE TABLE pathenum (
friend1 integer not null,
friend2 integer not null,
pathlength integer not null default 0
);

You need to load this table to record all connections. If Jay and Conan
are friends, then enter a row for Jay-to-Conan, length 1. If Conan is
also friends with Ellen and Oprah, then enter Conan-to-Ellen, length 1
and Conan-to-Oprah, length 1. Then also enter Jay-to-Ellen, length 2
and Jay-to-Oprah, length 2. Keep going, as you find the other friends
of Oprah and Ellen, until you run out or you find a friendship
connection back to Jay. This can be done iteratively or recursively.

Now you have a complete graph. You can fetch all users connected to Jay
with SELECT * FROM pathenum WHERE FRIEND1 = Jay_ID OR FRIEND2 = Jay_ID.

If someone new (Dave) is added to the web as a friend of Jay, you enter
Dave-to-Jay, length 1, and then select all connections of Jay, and
insert a new record for each one, substituting Dave for Jay and adding 1
to the pathlength.

It becomes a little bit complex to update this table if someone leaves
the web; it might be easier just to empty the pathenum table and
re-execute the search that populates it based on the current state of
the Friends table.

For more details and pseudocode samples, look in the book "SQL for
Smarties".
Could this be an appropriate use of a "heap table"?

Maybe, but not necessarily. Heap tables (or Memory tables) are
logically similar to conventional tables. The only difference is that
they are stored in system memory, not on disk. They data are lost when
the MySQL server shuts down. They're almost like TEMP tables, but they
are shared among all clients.

It might be worthwhile to make the pathenum table be a Heap table, and
you'd have to rebuild it from your Friends table each time the server
starts up. The advantage would be speed, but as long as the fields of
pathenum are indexed, I believe that speed won't be a problem even if
the table is a conventional disk-based table.

Regards,
Bill K.