Optimized MySQL query with complex calculation

Question

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.

Answer 1

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