0
\$\begingroup\$

I am trying to pick 3 providers with the highest calculated score based on my algorithm, to recommend them to a user.

The recommendation algorithm takes into account a few things. Most are static values, but the one that is dynamic is the physical distance from the user (based on lat/lng). Since each user's location is different, I can't cache the distance in the DB.

I also need to limit the results to a) providers in a certain category (the WHERE ... IN clause), and b) providers that the user has not already added (the WHERE ... NOT IN clause)

Finally I order by score descending limit 3. Here is the query I am running. {$algorithm} is just a complex equation, {$categories} is a comma-separated list

SELECT `id`,
    {$algorithhm} AS `score`
    FROM `provider`
    WHERE `id` IN (
        SELECT `provider_id`
        FROM `provider_categories`
        WHERE `category_id` IN ( {$categories} )
    )
    AND `id` NOT IN (
        SELECT `provider_id`
        FROM `users_provider`
        WHERE `user_id` = {$current_user->id}
    )
    ORDER BY `score` DESC
    LIMIT 3

I have indexes on every column name you see here. There are only about 13,000 provider records in the database, yet the query takes about .04 seconds on average, which seems pretty slow to me. Back when there were 1,500 providers, it only took .003 seconds. Since I'm hoping to one day have hundreds of thousands, obviously this is a growing concern.

What can I do to speed this query up?

EXPLAIN tells me this:

   type             table                 type             key    ref          rows    Extra
1  PRIMARY          provider              ALL              NULL   NULL         12880   Using where; using filesort
3  DEPENDENT SUBQ   users_provider        eq_ref           PRI    const, func  1       Using where; using index
2  DEPENDENT SUBQ   provider_categories   index_subquery   PRI    func         1       Using index; using where

Edit

One thought I had was to limit it to providers within an X mile radius. But since the dynamic part of the algorithm is the distance calculation, I would still need to calculate the distance for every provider up front, so that doesn't really help. Maybe instead of a circular radius, I could check within a square lat/lng boundary, since those columns are indexed and the distance wouldn't need to be calculated... just thinking out loud. The main problem with this is that the geocoordinate to mile conversion is very different near the equator vs. near the poles.

\$\endgroup\$
2
\$\begingroup\$

Think one problem is that you have no key that it is using on the provider table, hence it is checking every row.

Not tested the following but this might be faster. Uses the provider_categories table as the first one (on which you are limiting the number of rows with a keyed check) and from that joining to the provider table.

SELECT b.id,
    {$algorithhm} AS score
FROM provider_categories a
INNER JOIN provider b ON a.provider_id = b.id
LEFT OUTER JOIN users_provider c ON a.provider_id = c.provider_id AND user_id = {$current_user->id}
WHERE c.provider_id IS NULL AND a.category_id IN ( {$categories} )
ORDER BY score DESC
LIMIT 3
\$\endgroup\$
  • \$\begingroup\$ Thanks, but it doesn't seem to be any faster or limit the results any more. EXPLAIN still gives 13000 rows for the first step (and it says table b, so it's still grabbing from provider first for some reason?). I also tried moving the a.category_ID IN clause to the first INNER JOIN but that didn't help either. \$\endgroup\$ – andrewtweber Jul 4 '13 at 14:45
  • \$\begingroup\$ Try swapping the INNER JOIN for a STRAIGHT_JOIN \$\endgroup\$ – Kickstart Jul 4 '13 at 15:23
  • \$\begingroup\$ That helped immensely! Now averaging .008 seconds! Never even heard of STRAIGHT_JOIN before, looks like I have some research to do \$\endgroup\$ – andrewtweber Jul 4 '13 at 15:56
  • \$\begingroup\$ STRAIGHT_JOIN like that just forces the order that MySQL joins the tables in. Most of the time it gets it right but occasionally if doesn't, and then it is useful. \$\endgroup\$ – Kickstart Jul 4 '13 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.