Relações de amigos no MySQL

8

Estou desenvolvendo uma relação de amizade no MySQL, onde a relação de amizade é mútua. Se A é amigo de B, B é amigo de A. Se um dos usuários termina a amizade, a relação cai. Eu quero aprender qual caminho é melhor.

Eu tenho um sistema em execução;

user
-----------
userid p.k
name 

friends
-------
userid
friendid
primary key (`userid`,`friendid`),
key `friendid` (`friendid`)

1 2
2 5
1 3


To get all of my friends;
SELECT u.name, f.friendid , IF(f.userid = $userid, f.friendid, f.userid) friendid 
FROM friends f 
    inner join user u  ON ( u.userid = IF(f.userid = $userid, f.friendid, f.userid)) 
WHERE ( f.userid = '$userid' or f.friendid = '$userid' ) 

Esta consulta funciona bem. Talvez eu possa adicionar um UNION. A consulta é mais complicada que a abaixo e a tabela contém metade do número de registros que a abaixo.

Outra maneira é manter as relações em linhas separadas;

1 2
2 1
2 5
5 2
1 3
3 1

SELECT u.name, f.friendid 
FROM friends f inner join user u ON ( u.userid = f.friendid ) 
WHERE f.userid = '$userid'

Essa consulta é simples, embora a tabela ocupe o dobro do espaço.

Minha preocupação é; assumindo que existem milhões de usuários; para que lado funcionará mais rápido?

Quais são as vantagens e desvantagens de ambas as maneiras?

O que devo ter em mente ou mudar para essas maneiras? E que problemas posso enfrentar pelos dois lados?

kent ilyuk
fonte
Esta foi uma boa pergunta que você fez hoje. +1 para sua pergunta.
RolandoMySQLDBA 10/09/12

Respostas:

4

A primeira coisa que chama minha atenção é a configuração do índice friends.

Você tem isso no momento:

friends
-------
userid
friendid
primary key (`userid`,`friendid`),
key `friendid` (`friendid`)

Ao procurar por amizade mútua, isso pode resultar em uma pequena despesa, pois o ID do usuário pode ser recuperado da tabela ao percorrer o friendidíndice. Talvez você possa indexar da seguinte maneira:

friends
-------
userid
friendid
primary key (`userid`,`friendid`),
unique key `friendid` (`friendid`,`userid`)

Isso pode remover qualquer necessidade de acessar a tabela e pesquisar apenas o índice.

Agora, em termos de consultas, as duas podem melhorar com o novo índice exclusivo. Criando o índice exclusivo também elimina a necessidade de inserir (A,B)e (B,A)na tabela porque (A,B)e (B,A)seria o índice de qualquer forma. Portanto, a segunda consulta não precisaria examinar a tabela para ver se alguém é amigo de outra pessoa porque outra pessoa iniciou a amizade. Dessa forma, se a amizade é quebrada por apenas uma pessoa, não há amizades órfãs unilaterais (parece muito com a vida hoje em dia, não é?)

Sua primeira consulta parece se beneficiar mais do índice exclusivo. Mesmo com milhões de linhas, localizar amigos usando apenas os índices evitaria tocar na tabela. Ainda assim, como você não apresentou uma consulta UNION, eu gostaria de recomendar uma consulta UNION:

SET @givenuserid = ?;
SELECT B.name "Friend's Name"
FROM 
(
    SELECT userid FROM friends WHERE friendid=@givenuserid
    UNION
    SELECT friendid FROM friends WHERE userid=@givenuserid
) A INNER JOIN user B USING (userid);

Isso permitirá que você veja quem são os amigos de cada ID de usuário

Para ver todas as amizades, execute o seguinte:

SELECT A.userid,A.name,B.friendid,C.name
FROM user A
INNER JOIN friends B ON A.userid=B.userid
INNER JOIN user C on B.friendid=C.userid;

Primeiro, aqui estão alguns dados de amostra:

mysql> drop database if exists key_ilyuk;
Query OK, 2 rows affected (0.01 sec)

mysql> create database key_ilyuk;
Query OK, 1 row affected (0.00 sec)

mysql> use key_ilyuk
Database changed
mysql> create table user
    -> (
    ->     userid INT NOT NULL AUTO_INCREMENT,
    ->     name varchar(20),
    ->     primary key(userid)
    -> ) ENGINE=MyISAM;
Query OK, 0 rows affected (0.04 sec)

mysql> insert into user (name) values
    -> ('rolando'),('pamela'),('dominique'),('carlik'),('diamond');
Query OK, 5 rows affected (0.01 sec)
Records: 5  Duplicates: 0  Warnings: 0

mysql> create table friends
    -> (
    ->     userid INT NOT NULL,
    ->     friendid INT NOT NULL,
    ->     primary key (userid,friendid),
    ->     unique key (friendid,userid)
    -> ) ENGINE=MyISAM;
Query OK, 0 rows affected (0.03 sec)

mysql> insert into friends values (1,2),(2,5),(1,3);
Query OK, 3 rows affected (0.00 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> select * from user;
+--------+-----------+
| userid | name      |
+--------+-----------+
|      1 | rolando   |
|      2 | pamela    |
|      3 | dominique |
|      4 | carlik    |
|      5 | diamond   |
+--------+-----------+
5 rows in set (0.00 sec)

mysql> select * from friends;
+--------+----------+
| userid | friendid |
+--------+----------+
|      1 |        2 |
|      1 |        3 |
|      2 |        5 |
+--------+----------+
3 rows in set (0.00 sec)

mysql>

Vamos olhar para todos os relacionamentos

mysql> SELECT A.userid,A.name,B.friendid,C.name
    -> FROM user A
    -> INNER JOIN friends B ON A.userid=B.userid
    -> INNER JOIN user C on B.friendid=C.userid
    -> ;
+--------+---------+----------+-----------+
| userid | name    | friendid | name      |
+--------+---------+----------+-----------+
|      1 | rolando |        2 | pamela    |
|      1 | rolando |        3 | dominique |
|      2 | pamela  |        5 | diamond   |
+--------+---------+----------+-----------+
3 rows in set (0.00 sec)

mysql>

Vamos examinar todos os 5 IDs de usuário e ver se os relacionamentos são mostrados corretamente

mysql> SET @givenuserid = 1;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT B.name "Friend's Name"
    -> FROM
    -> (
    ->     SELECT userid FROM friends WHERE friendid=@givenuserid
    ->     UNION
    ->     SELECT friendid FROM friends WHERE userid=@givenuserid
    -> ) A INNER JOIN user B USING (userid);
+---------------+
| Friend's Name |
+---------------+
| pamela        |
| dominique     |
+---------------+
2 rows in set (0.00 sec)

mysql> SET @givenuserid = 2;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT B.name "Friend's Name"
    -> FROM
    -> (
    ->     SELECT userid FROM friends WHERE friendid=@givenuserid
    ->     UNION
    ->     SELECT friendid FROM friends WHERE userid=@givenuserid
    -> ) A INNER JOIN user B USING (userid);
+---------------+
| Friend's Name |
+---------------+
| rolando       |
| diamond       |
+---------------+
2 rows in set (0.00 sec)

mysql> SET @givenuserid = 3;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT B.name "Friend's Name"
    -> FROM
    -> (
    ->     SELECT userid FROM friends WHERE friendid=@givenuserid
    ->     UNION
    ->     SELECT friendid FROM friends WHERE userid=@givenuserid
    -> ) A INNER JOIN user B USING (userid);
+---------------+
| Friend's Name |
+---------------+
| rolando       |
+---------------+
1 row in set (0.01 sec)

mysql> SET @givenuserid = 4;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT B.name "Friend's Name"
    -> FROM
    -> (
    ->     SELECT userid FROM friends WHERE friendid=@givenuserid
    ->     UNION
    ->     SELECT friendid FROM friends WHERE userid=@givenuserid
    -> ) A INNER JOIN user B USING (userid);
Empty set (0.00 sec)

mysql> SET @givenuserid = 5;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT B.name "Friend's Name"
    -> FROM
    -> (
    ->     SELECT userid FROM friends WHERE friendid=@givenuserid
    ->     UNION
    ->     SELECT friendid FROM friends WHERE userid=@givenuserid
    -> ) A INNER JOIN user B USING (userid);
+---------------+
| Friend's Name |
+---------------+
| pamela        |
+---------------+
1 row in set (0.00 sec)

mysql>

Todos eles parecem corretos para mim.

Agora, vamos usar sua segunda consulta para ver se ela corresponde ...

mysql> SET @givenuserid = 1;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT u.name, f.friendid
    -> FROM friends f inner join user u ON ( u.userid = f.friendid )
    -> WHERE f.userid = @givenuserid;
+-----------+----------+
| name      | friendid |
+-----------+----------+
| pamela    |        2 |
| dominique |        3 |
+-----------+----------+
2 rows in set (0.00 sec)

mysql> SET @givenuserid = 2;
Query OK, 0 rows affected (0.01 sec)

mysql> SELECT u.name, f.friendid
    -> FROM friends f inner join user u ON ( u.userid = f.friendid )
    -> WHERE f.userid = @givenuserid;
+---------+----------+
| name    | friendid |
+---------+----------+
| diamond |        5 |
+---------+----------+
1 row in set (0.00 sec)

mysql> SET @givenuserid = 3;
Query OK, 0 rows affected (0.01 sec)

mysql> SELECT u.name, f.friendid
    -> FROM friends f inner join user u ON ( u.userid = f.friendid )
    -> WHERE f.userid = @givenuserid;
Empty set (0.00 sec)

mysql> SET @givenuserid = 4;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT u.name, f.friendid
    -> FROM friends f inner join user u ON ( u.userid = f.friendid )
    -> WHERE f.userid = @givenuserid;
Empty set (0.00 sec)

mysql> SET @givenuserid = 5;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT u.name, f.friendid
    -> FROM friends f inner join user u ON ( u.userid = f.friendid )
    -> WHERE f.userid = @givenuserid;
Empty set (0.00 sec)

mysql>

Por que não combinar? Isso porque eu não carreguei o (B,A)para todos (A,B). Deixe-me carregar os (B,A)relacionamentos e tente sua segunda consulta novamente.

mysql> insert into friends values (2,1),(5,2),(3,1);
Query OK, 3 rows affected (0.02 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> SET @givenuserid = 1;
Query OK, 0 rows affected (0.01 sec)

mysql> SELECT u.name, f.friendid
    -> FROM friends f inner join user u ON ( u.userid = f.friendid )
    -> WHERE f.userid = @givenuserid;
+-----------+----------+
| name      | friendid |
+-----------+----------+
| pamela    |        2 |
| dominique |        3 |
+-----------+----------+
2 rows in set (0.00 sec)

mysql> SET @givenuserid = 2;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT u.name, f.friendid
    -> FROM friends f inner join user u ON ( u.userid = f.friendid )
    -> WHERE f.userid = @givenuserid;
+---------+----------+
| name    | friendid |
+---------+----------+
| rolando |        1 |
| diamond |        5 |
+---------+----------+
2 rows in set (0.00 sec)

mysql> SET @givenuserid = 3;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT u.name, f.friendid
    -> FROM friends f inner join user u ON ( u.userid = f.friendid )
    -> WHERE f.userid = @givenuserid;
+---------+----------+
| name    | friendid |
+---------+----------+
| rolando |        1 |
+---------+----------+
1 row in set (0.00 sec)

mysql> SET @givenuserid = 4;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT u.name, f.friendid
    -> FROM friends f inner join user u ON ( u.userid = f.friendid )
    -> WHERE f.userid = @givenuserid;
Empty set (0.00 sec)

mysql> SET @givenuserid = 5;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT u.name, f.friendid
    -> FROM friends f inner join user u ON ( u.userid = f.friendid )
    -> WHERE f.userid = @givenuserid;
+--------+----------+
| name   | friendid |
+--------+----------+
| pamela |        2 |
+--------+----------+
1 row in set (0.00 sec)

mysql>

Eles ainda não combinam. Isso ocorre porque sua segunda consulta está apenas verificando um lado.

Vamos verificar sua primeira consulta em todos os valores com apenas (A, B) e não (B, A):

mysql> SET @givenuserid = 1;
SELECT u.name, f.friendid userid, IF(f.userid = @givenuserid, f.friendid, f.userid) friendid
FROM friends f
    inner join user u  ON ( u.userid = IF(f.userid = @givenuserid, f.friendid, f.userid))
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT u.name, f.friendid userid, IF(f.userid = @givenuserid, f.friendid, f.userid) friendid
    -> FROM friends f
    ->     inner join user u  ON ( u.userid = IF(f.userid = @givenuserid, f.friendid, f.userid))
    -> WHERE ( f.userid = @givenuserid or f.friendid = @givenuserid  );
+-----------+--------+----------+
| name      | userid | friendid |
+-----------+--------+----------+
| pamela    |      2 |        2 |
| dominique |      3 |        3 |
+-----------+--------+----------+
2 rows in set (0.00 sec)

mysql> SET @givenuserid = 2;
FROM friends f
    inner join user u  ON ( u.userid = IF(f.userid = @givenuserid, f.friendid, f.userid))
WHERE ( f.userid = @givenuserid or f.friendid = @givenuserid  );
Query OK, 0 rows affected (0.01 sec)

mysql> SELECT u.name, f.friendid userid, IF(f.userid = @givenuserid, f.friendid, f.userid) friendid
    -> FROM friends f
    ->     inner join user u  ON ( u.userid = IF(f.userid = @givenuserid, f.friendid, f.userid))
    -> WHERE ( f.userid = @givenuserid or f.friendid = @givenuserid  );
+---------+--------+----------+
| name    | userid | friendid |
+---------+--------+----------+
| rolando |      2 |        1 |
| diamond |      5 |        5 |
+---------+--------+----------+
2 rows in set (0.00 sec)

mysql> SET @givenuserid = 3;
SELECT u.name, f.friendid userid, IF(f.userid = @givenuserid, f.friendid, f.userid) friendid
FROM friends f
    inner join user u  ON ( u.userid = IF(f.userid = @givenuserid, f.friendid, f.userid))
WHERE ( f.userid = @givenuserid or f.friendid = @givenuserid  );
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT u.name, f.friendid userid, IF(f.userid = @givenuserid, f.friendid, f.userid) friendid
    -> FROM friends f
    ->     inner join user u  ON ( u.userid = IF(f.userid = @givenuserid, f.friendid, f.userid))
    -> WHERE ( f.userid = @givenuserid or f.friendid = @givenuserid  );
+---------+--------+----------+
| name    | userid | friendid |
+---------+--------+----------+
| rolando |      3 |        1 |
+---------+--------+----------+
1 row in set (0.00 sec)

mysql> SET @givenuserid = 4;
FROM friends f
    inner join user u  ON ( u.userid = IF(f.userid = @givenuserid, f.friendid, f.userid))
WHERE ( f.userid = @givenuserid or f.friendid = @givenuserid  );
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT u.name, f.friendid userid, IF(f.userid = @givenuserid, f.friendid, f.userid) friendid
    -> FROM friends f
    ->     inner join user u  ON ( u.userid = IF(f.userid = @givenuserid, f.friendid, f.userid))
    -> WHERE ( f.userid = @givenuserid or f.friendid = @givenuserid  );
Empty set (0.01 sec)

mysql> SET @givenuserid = 5;
FROM friends f
Query OK, 0 rows affected (0.00 sec)

    inner join user u  ON ( u.userid = IF(f.userid = @givenuserid, f.friendid, f.userid))
mysql> SELECT u.name, f.friendid userid, IF(f.userid = @givenuserid, f.friendid, f.userid) friendid
    -> FROM friends f
    ->     inner join user u  ON ( u.userid = IF(f.userid = @givenuserid, f.friendid, f.userid))
    -> WHERE ( f.userid = @givenuserid or f.friendid = @givenuserid  );
+--------+--------+----------+
| name   | userid | friendid |
+--------+--------+----------+
| pamela |      5 |        2 |
+--------+--------+----------+
1 row in set (0.00 sec)

mysql>

Seu primeiro funciona bem. Estou certo de que ele está se beneficiando do índice único, como disse anteriormente, mas IMHO acho que a UNIÃO é mais simples. Com esse índice único, pareceria ser seis de uma e meia dúzia do outro em termos de execução e saída.

Você teria que comparar sua primeira consulta com a minha sugestão UNION e ver.

Esta foi uma boa pergunta que você fez hoje. +1 para sua pergunta.

RolandoMySQLDBA
fonte
Fiz alguns testes para ver a rapidez da configuração atual. Eu não mudei o esquema das tabelas. Primeira consulta 1.000.000 de linhas (tabela de usuários) 2.045.007 linhas (tabela de amigos - uma linha para cada relação. As amizades são criadas aleatoriamente para 10.000 usuários) A primeira consulta leva 0,01094 segundos para retornar 600 linhas. A mesma consulta alterada com UNION leva 0,0086 para retornar 600 linhas. Segunda consulta 1.000.000 de linhas (tabela do usuário) 4.048.781 linhas (tabela friends_twoway - duas linhas para cada relação) A segunda consulta na minha primeira postagem leva 0.0090 segundos. para retornar 600 linhas. O que você acha desses resultados?
precisa saber é o seguinte
Após vários testes, alterarei as configurações da tabela e adicionarei índices diferentes, conforme sugerido.
precisa saber é o seguinte
No seu primeiro teste, .0086 (com UNION) é melhor que .01094 (sem UNION). De fato, isso é 27,21% mais rápido. O desempenho da sua primeira consulta com o dobro de dados é 0,0004 s mais lento. Mesmo com os números fornecidos, eu ainda preferiria o UNION com apenas os dados e a criação de um índice exclusivo, porque os índices seriam totalmente empregados na consulta e deixariam os dados em paz.
RolandoMySQLDBA 10/09/12
Substituí friendid-key por chave exclusiva ( friendid, userid) e agora os resultados são cerca de .00794 É o mais rápido possível? Olhando para os resultados, você acha que a primeira maneira é melhor (uma linha para cada relação)? Porque é duas vezes menos espaço que o segundo e os resultados são praticamente os mesmos nas configurações atuais.
precisa saber é o seguinte
No seu caso particular, menos dados são bons devido à dependência dos índices. Os índices estão inchados, mas com uma finalidade benéfica. Este é um conceito chamado cobrindo índices, cujo propósito é índices criados cujo WHERE, GROUP BYe ORDER BYcláusulas resultar em dados sendo lidos apenas índices. Aqui estão alguns bons links que justificam o uso das chaves exclusivas e primárias como índices de cobertura: 1) peter-zaitsev.livejournal.com/6949.html , 2) mysqlperformanceblog.com/2006/11/23/… , 3) ronaldbradford .com / blog / tag / cover-index
RolandoMySQLDBA