[Solved] help optimizing query (shows strength of two-way relationships between contacts)

EverSQL Database Performance Knowledge Base

help optimizing query (shows strength of two-way relationships between contacts)

Database type:

i have a contact_relationship table that stores the reported strength of a relationship between one contact and another at a given point in time.

mysql> desc contact_relationship;
+------------------+-----------+------+-----+-------------------+-----------------------------+
| Field            | Type      | Null | Key | Default           | Extra                       |
+------------------+-----------+------+-----+-------------------+-----------------------------+
| relationship_id  | int(11)   | YES  |     | NULL              |                             |
| contact_id       | int(11)   | YES  | MUL | NULL              |                             |
| other_contact_id | int(11)   | YES  |     | NULL              |                             |
| strength         | int(11)   | YES  |     | NULL              |                             |
| recorded         | timestamp | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+------------------+-----------+------+-----+-------------------+-----------------------------+

now i want to get a list of two-way relationships between contacts (meaning there are two rows, one with contact a specifying a relationship strength with contact b and another with contact b specifying a strength for contact a -- the strength of the two-way relationship is the smaller of those two strength values).

this is the query i've come up with but it is pretty slow:

select 
    mrcr1.contact_id, 
    mrcr1.other_contact_id, 
    case when (mrcr1.strength < mrcr2.strength) then 
        mrcr1.strength 
    else 
        mrcr2.strength 
    end strength 
from ( 
    select 
        cr1.* 
    from ( 
        select 
            contact_id,
            other_contact_id,
            max(recorded) as max_recorded 
        from 
            contact_relationship 
        group by 
            contact_id,
            other_contact_id 
    ) as cr2 
    inner join contact_relationship cr1 on 
        cr1.contact_id = cr2.contact_id 
        and cr1.other_contact_id = cr2.other_contact_id 
        and cr1.recorded = cr2.max_recorded 
) as mrcr1, 
( 
    select 
        cr3.* 
    from ( 
        select 
            contact_id,
            other_contact_id,
            max(recorded) as max_recorded 
        from 
            contact_relationship 
        group by 
            contact_id,
            other_contact_id 
    ) as cr4 
    inner join contact_relationship cr3 on 
        cr3.contact_id = cr4.contact_id 
        and cr3.other_contact_id = cr4.other_contact_id 
        and cr3.recorded = cr4.max_recorded 
) as mrcr2 
where 
    mrcr1.contact_id = mrcr2.other_contact_id 
    and mrcr1.other_contact_id = mrcr2.contact_id 
    and mrcr1.contact_id != mrcr1.other_contact_id 
    and mrcr2.contact_id != mrcr2.other_contact_id 
    and mrcr1.contact_id <= mrcr1.other_contact_id; 

anyone have any recommendations of how to speed it up?

note that because a user may specify the strength of his relationship with a particular user more than once, you must only grab the most recent record for each pair of contacts.

update: here is the result of explaining the query...

+----+-------------+----------------------+-------+----------------------------------------------------------------------------------------+------------------------------+---------+-------------------------------------+-------+--------------------------------+
| id | select_type | table                | type  | possible_keys                                                                          | key                          | key_len | ref                                 | rows  | Extra                          |
+----+-------------+----------------------+-------+----------------------------------------------------------------------------------------+------------------------------+---------+-------------------------------------+-------+--------------------------------+
|  1 | PRIMARY     | <derived2>           | ALL   | NULL                                                                                   | NULL                         | NULL    | NULL                                | 36029 | Using where                    |
|  1 | PRIMARY     | <derived4>           | ALL   | NULL                                                                                   | NULL                         | NULL    | NULL                                | 36029 | Using where; Using join buffer |
|  4 | DERIVED     | <derived5>           | ALL   | NULL                                                                                   | NULL                         | NULL    | NULL                                | 36021 |                                |
|  4 | DERIVED     | cr3                  | ref   | contact_relationship_index_1,contact_relationship_index_2,contact_relationship_index_3 | contact_relationship_index_2 | 10      | cr4.contact_id,cr4.other_contact_id |     1 | Using where                    |
|  5 | DERIVED     | contact_relationship | index | NULL                                                                                   | contact_relationship_index_3 | 14      | NULL                                | 37973 | Using index                    |
|  2 | DERIVED     | <derived3>           | ALL   | NULL                                                                                   | NULL                         | NULL    | NULL                                | 36021 |                                |
|  2 | DERIVED     | cr1                  | ref   | contact_relationship_index_1,contact_relationship_index_2,contact_relationship_index_3 | contact_relationship_index_2 | 10      | cr2.contact_id,cr2.other_contact_id |     1 | Using where                    |
|  3 | DERIVED     | contact_relationship | index | NULL                                                                                   | contact_relationship_index_3 | 14      | NULL                                | 37973 | Using index                    |
+----+-------------+----------------------+-------+----------------------------------------------------------------------------------------+------------------------------+---------+-------------------------------------+-------+--------------------------------+

How to optimize this SQL query?

The following recommendations will help you in your SQL tuning process.
You'll find 3 sections below:

  1. Description of the steps you can take to speed up the query.
  2. The optimal indexes for this query, which you can copy and create in your database.
  3. An automatically re-written query you can copy and execute in your database.
The optimization process and recommendations:
  1. Avoid Subqueries In From Clause (modified query below): The database cannot properly optimize subqueries in the FROM clause. Therefore, we recommend to extract the subqueries to temporary tables, index them and join to them in the outer query.
  2. Create Optimal Indexes (modified query below): The recommended indexes are an integral part of this optimization effort and should be created before testing the execution duration of the optimized query.
  3. Push Filtering Conditions Into Subqueries (modified query below): Parts of the WHERE clause can pushed from the outer query to a subquery / union clause. Applying those conditions as early as possible will allow the database to scan less data and run the query more efficiently.
Optimal indexes for this query:
ALTER TABLE `es_temp1` ADD INDEX `es_temp1_idx_contact_id_other_id` (`contact_id`,`other_contact_id`);
ALTER TABLE `es_temp2` ADD INDEX `es_temp2_idx_other_id_contact_id` (`other_contact_id`,`contact_id`);
The optimized query:
SELECT
        mrcr1.contact_id,
        mrcr1.other_contact_id,
        CASE 
            WHEN (mrcr1.strength < mrcr2.strength) THEN mrcr1.strength 
            ELSE mrcr2.strength END strength 
FROM
es_temp1 AS mrcr1,
es_temp2 AS mrcr2 
WHERE
mrcr1.contact_id = mrcr2.other_contact_id 
AND mrcr1.other_contact_id = mrcr2.contact_id 
AND 1 = 1 
AND 1 = 1 
AND 1 = 1

Related Articles



* original question posted on StackOverflow here.