2

First-time poster so please be gentle :)

I have a rather large table in my database (MySQL in case it matters) that holds lat/lng values of certain points of interest around the world (table name: Maps). The table is very large (millions of rows) and could grow significantly larger since users can add rows to it.

I have another table called Users that also holds lat/lng values of user locations around the world. It is currently in the low thousands, and I wouldn't expect it to grow to more than a few tens of thousands.

My scenario is that I need to run a query that compares the lat/lng position of some users in the Users table against some locations in the Maps table and return locations less than a certain distance. The SQL is as follows:

SELECT x.type FROM Maps x INNER JOIN Ranges ON Ranges.type = x.type
        WHERE x.user_ID IN ($users)
        AND m.lat BETWEEN
        x.lat - Ranges.range AND
        x.lat + Ranges.range 
        AND m.lng BETWEEN
        x.lng - Ranges.vision_range * COS(RADIANS(x.lat)) AND
        x.lng + Ranges.vision_range * COS(RADIANS(x.lat))
        AND (6378137 * ACOS(COS(RADIANS(x.lat)) * COS(RADIANS(m.lat)) * COS(RADIANS(m.lng) 
         - RADIANS(x.lng)) + SIN(RADIANS(x.lat)) * SIN(RADIANS(m.lat)))) < Ranges.range

This query is currently in production and works OK. It follows my normal practice (and I'm assuming "best" practice) of running the specific query in SQL to return only the result set we are interested in, a so-called "minimum" or if you like "accurate" result set. I then don't need to further process the result set and can return it to the user's front-end app. A usual query returns maybe 100-1,000 values, however due to the relatively complex mathematical calculations takes 300-600ms to complete. This isn't ideal, because it's a web front end and the lag is noticeable.

However, I've been experimenting with running a "dumb" query that simply uses a large bounding box to return all possible values within a range and then use PHP to do the mathematical processing. The SQL is as follows:

SELECT m.type
FROM Maps m
WHERE m.user_ID IN ($users)
AND m.lat BETWEEN $minLat AND $maxLat
AND m.lng BETWEEN $minLng AND $maxLng

This query returns results in 3-6ms! However, the result set is huge and can be tens of thousands of rows. PHP obviously has no issues with the mathematics and can process it in a negligible amount of time.

Is there any reason I should not process the data in PHP? Am I missing something here about the tradeoff between the massive reduction in query time versus the huge volume of data returned (most of which will be "thrown away")?

12
  • 3
    No, you're not missing anything. Software development is always an exercise in tradeoffs, and I've seen many Crystal Cathedral architectures and "best practices" (justifiably) sacrificed on the altar of performance. – Robert Harvey Mar 26 at 23:57
  • 3
    That said, it's possible that there's still some optimizations that could be done on that query. My guess is that it's slow because it has to execute all of those math functions for each and every row in the maps/ranges join, maybe more than once. Check your EXPLAIN. – Robert Harvey Mar 27 at 0:07
  • 1
    Then your new approach sounds like a good plan to me. Just watch your memory usage. – Robert Harvey Mar 27 at 0:16
  • 2
    Just for fun, did you try adding AND m.lat BETWEEN $minLat AND $maxLat AND m.lng BETWEEN $minLng AND $maxLng to the full query – Esben Skov Pedersen Mar 27 at 10:34
  • 1
    and please, never use variables directly in your query unless you want to get hacked. Look into parameters – Esben Skov Pedersen Mar 27 at 10:35
2

You're absolutely right not to take it for granted that a "best practice" is always in fact the best strategy. The important thing is to understand the reasons it's usually a good idea, and then make an informed decision whether those reasons apply to your case.

Reasons it's usually a good idea to put as much filtering as possible on the database include:

  • Flexibility - the DBMS has complex logic to take advantage of indexes, change the order of operations, etc, rather than always following the same strategy.
  • Combining multiple filters - an important consequence of the above is that having more WHERE clauses in a single query can lead to better performance, because the DBMS can decide which one will quickly eliminate the most rows, and not examine them further.
  • Network transfer - transferring the full set of data from MySQL to PHP takes time and uses bandwidth.
  • Memory - the DBMS can work with the data directly on disk, or manage memory as it sees fit; a PHP algorithm will likely have the entire data set in memory.

Reasons it might be sensible to put it in the application layer:

  • The DBMS you're using doesn't have good facilities for the type of filter you want to apply. Your example shows you manually calculating distances for each row, which is not something the DBMS can optimise easily. If there is any GIS / Polygon support for MySQL, using that would probably give you a dramatic performance boost; if there isn't, it may be a good reason to hand the work to PHP.
  • You know that most of the results will meet the conditions. If you need most of the rows anyway, the network and memory factors disappear, so you can look at pure speed of filtering. Be careful how you measure it though: how do the two different approaches scale to larger data sets? How well do they cope with multiple simultaneous requests?
  • Your filters include complex business logic, and you want to be able to unit test them, which is easier in procedural code. (Hat tip to Esben Skov Pedersen for pointing that out.)
2

There is a very good chance that evaluating the condition stops when the outcome is known. You have an expensive and precise filter, and a cheap and coarse filter. If you use the condition “coarse filter AND precise filter”, then you get the precise result, but the expensive filter will not be evaluated for everything, but just for the rows that pass the first filter.

(I really hope I’m wrong here or the database expert you hired is useless).

Another thing: it is quite likely that you can find a formula for distance that doesn’t require cosines.

1

It is absolutely fine to use the database as a coarse filter. Remember there it is hard to do unit tests of database code so we don't want the query to be too complex.

If you are using most of the data you get back I think it's absolutely fine to ask for more data than you need. If you however ask for 5x-10x the data you actually need I would consider it a problem.

Also in your case it is sometimes good to give the databases a few hints meaning if you combine your two queries (you add AND m.lat BETWEEN $minLat AND $maxLat AND m.lng BETWEEN $minLng AND $maxLng) to the full query the db could choose to get that data first, and then only do the complex operations on that small dataset, this could be optimal for query speed and data transfer, but however the query is quite complex and it might be better to get that into some code where it's easier to have unit tests.

Also read up on sql injections unless you want your site to get hacked: https://www.php.net/manual/en/security.database.sql-injection.php

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.