Time complexity/MySQL performance analysis

Question

Set up(MySQL):

create table inRelation(
    party1 integer unsigned NOT NULL,
    party2 integer unsigned NOT NULL,
    unique (party1,party2)
);

insert into inRelation(party1,party2) values(1,2),(1,3),(2,3),(1,4),(2,5),(3,5),(1,6),(1,7),(2,7),(5,7);

mysql> select * from inRelation a
    -> join inRelation b on a.party2=b.party1
    -> join inRelation c on b.party2=c.party1
    -> where a.party1=1 and c.party2=7;
+--------+--------+--------+--------+--------+--------+
| party1 | party2 | party1 | party2 | party1 | party2 |
+--------+--------+--------+--------+--------+--------+
|      1 |      2 |      2 |      5 |      5 |      7 |
|      1 |      3 |      3 |      5 |      5 |      7 |
+--------+--------+--------+--------+--------+--------+
2 rows in set (0.00 sec)

mysql> explain select * from inRelation a
    -> join inRelation b on a.party2=b.party1
    -> join inRelation c on b.party2=c.party1
    -> where a.party1=1 and c.party2=7;
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
| id | select_type | table | type   | possible_keys | key    | key_len | ref                 | rows | Extra       |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
|  1 | SIMPLE      | b     | index  | party1        | party1 | 8       | NULL                |   10 | Using index |
|  1 | SIMPLE      | a     | eq_ref | party1        | party1 | 8       | const,news.b.party1 |    1 | Using index |
|  1 | SIMPLE      | c     | eq_ref | party1        | party1 | 8       | news.b.party2,const |    1 | Using index |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+

This is a BFS solution for my previous post:

Challenge,how to implement an algorithm for six degree of separation?

But what's the complexity of it?Suppose there are totally n records .

Boolean Boolean · Accepted Answer · 2010-01-20T14:38:48

Assuming there are N vertices and E edges. For every table there can be a join between every pair of vertices and need to check all the vertices for equality. So worst case performance will be O(|V| + |E|)

Updated: If you are considering Mysql, there are lot of things that affect the complexity, if you have primary key index on the field, b-tree index will be used. If its a normal unclustered index, hash index will be used. There are different costs for each of these data structures.

From your other question, I see this is your requirements 1. Calculate the path from UserX to UserY 2. For UserX,calculate all users that is no more than 3 steps away.

For the first one, best thing is to apply djikstra algorithm and construct a table in java and then update it in the table. Note that, adding every new node, needs complete processing.

Other solution to this will be to use recursive SQL introduced in SQL 1999 standard to create a view containing the path from UserX to UserY. Let me know if you need some references for recursive queries.

For the second one, the query you have written works perfectly.

Time complexity/MySQL performance analysis

1 Answers