Optimising latitude and longitude selection query

Question

I have table as follows the schema below.

CREATE TABLE `gdata` ( 
`alarmTypeID` tinyint(4) NOT NULL DEFAULT '0', 
`fleetID` smallint(11) NOT NULL, 
`fleetGroupID` smallint(11) DEFAULT NULL, 
`fleetSubGroupID` smallint(11) DEFAULT NULL, 
`deviceID` mediumint(11) NOT NULL, 
`vehicleID` mediumint(11) NOT NULL, 
`gDateTime` datetime NOT NULL, 
`insertDateTime` datetime NOT NULL, 
`latitude` float NOT NULL, 
`longitude` float NOT NULL, 
`speed` smallint(11) NOT NULL, 
(see full text) 
ALTER TABLE `gdata` 
ADD PRIMARY KEY (`vehicleID`,`gDateTime`,`alarmTypeID`), 
ADD KEY `gDateTime` (`gDateTime`), 
ADD KEY `fleetID` (`fleetID`,`vehicleID`,`gDateTime`); 
COMMIT; 

My issue now is that I can run a query as below EXPLAIN select vehicleID,latitude,longitude from gdata where gDateTime between '2017-07-03 00:00:00' and '2017-07-04 00:00:00' and the results of the explains is

1   SIMPLE  gdata       range   gDateTime   gDateTime   5       1251    100.00  Using index condition   

I have the following function which works to test if the a latitude and longitude is withing a rectangle.

DELIMITER $$
--
-- Functions
--
CREATE DEFINER=`root`@`localhost`
    FUNCTION `geoProcessor`(pt POINT, mp MULTIPOLYGON)
        RETURNS int(1)
        DETERMINISTIC
BEGIN 

DECLARE str, xy TEXT; 
DECLARE x, y, p1x, p1y, p2x, p2y, m, xinters DECIMAL(16, 13) DEFAULT 0; 
DECLARE counter INT DEFAULT 0; 
DECLARE p, pb, pe INT DEFAULT 0; 

SELECT MBRWithin(pt, mp) INTO p; 
IF p != 1 OR ISNULL(p) THEN 
RETURN p; 
END IF; 

SELECT X(pt), Y(pt), ASTEXT(mp) INTO x, y, str; 
SET str = REPLACE(str, 'POLYGON((',''); 
SET str = REPLACE(str, '))', ''); 
SET str = CONCAT(str, ','); 

SET pb = 1; 
SET pe = LOCATE(',', str); 
SET xy = SUBSTRING(str, pb, pe - pb); 
SET p = INSTR(xy, ' '); 
SET p1x = SUBSTRING(xy, 1, p - 1); 
SET p1y = SUBSTRING(xy, p + 1); 
SET str = CONCAT(str, xy, ','); 

WHILE pe > 0 DO 
SET xy = SUBSTRING(str, pb, pe - pb); 
SET p = INSTR(xy, ' '); 
SET p2x = SUBSTRING(xy, 1, p - 1); 
SET p2y = SUBSTRING(xy, p + 1); 
IF p1y < p2y THEN SET m = p1y; ELSE SET m = p2y; END IF; 
IF y > m THEN 
IF p1y > p2y THEN SET m = p1y; ELSE SET m = p2y; END IF; 
IF y <= m THEN 
IF p1x > p2x THEN SET m = p1x; ELSE SET m = p2x; END IF; 
IF x <= m THEN 
IF p1y != p2y THEN 
SET xinters = (y - p1y) * (p2x - p1x) / (p2y - p1y) + p1x; 
END IF; 
IF p1x = p2x OR x <= xinters THEN 
SET counter = counter + 1; 
END IF; 
END IF; 
END IF; 
END IF; 
SET p1x = p2x; 
SET p1y = p2y; 
SET pb = pe + 1; 
SET pe = LOCATE(',', str, pb); 
END WHILE; 

RETURN counter % 2; 

END$$

DELIMITER ;

My issue now I want to find out which vehicle is within a rectangle within a time range value. I have to run two separate queries to first run the first queries get the lat, long value then test if its within the rectangle using the second query. How to opmtimise this?

Answer 1

To find which vehicle(s) are in a specific 'rectangle' ("bounding box") during a particular day,

SELECT ...
    FROM gdata
    WHERE gDateTime >= '2017-07-03'
      AND gDateTime  < '2017-07-03' + INTERVAL 1 DAY
      AND latitude > 34.567
      AND latitude < 35.678
      AND longitude > 123.456
      AND longitude < 124.567;

The optimizer cannot do a perfect job of optimizing the query, but you can give it 3 choices and hope that it picks the best:

INDEX(gDateTime),
INDEX(latitude),
INDEX(longitude)

Since each column is used in a "range", there is no advantage in putting two columns in a single index. (Only the first column will be used.)

Or, with SPATIAL index...

If it is a polygon, not a simple rectangle, then something like

SELECT ...
    FROM gdata
    WHERE gDateTime >= '2017-07-03'
      AND gDateTime  < '2017-07-03' + INTERVAL 1 DAY
      AND MBRWithin(pt, ...);

with

• pt being an extra column containing a POINT
• SPATIAL(pt)
• the '...' being a pre-calculated polygon from somewhere else

Do not call your FUNCTION in the WHERE clause; that will be terribly inefficient.

Since you only want a list of vehicleID, not all the locations, this is probably better:

SELECT DISTINCT vehicleID
    FROM gdata
    WHERE ...

DISTINCT is sort of a degenerate case of GROUP BY. I prefer to use DISTINCT in this situation since it makes it clearer what is going on.

Partitioning?

PARTITION BY RANGE(TO_DAYS(gDateTime)) with 20-50 partitions may help performance, especially if the table will be billions of rows long. The partitioning would narrow the focus to one (maybe more) partition, then do the spatial (or lat/lng) lookup within just that partition.

Also, partitioning is an excellent way to purge 'old' data.

Use cases 1 and 2 of my partition blog discuss those two ideas.

Answer 2

Accidentally I have the DB with table that contain 50+ million of NMEA rows in it. The table have the complex index (timestamp, lat, lon). Simple query has been launched:

SELECT DISTINCT vehicle_id
  FROM nmea 
 WHERE ts  BETWEEN '2016-05-10' AND '2016-05-11'
   AND lat BETWEEN 50.00 AND 50.20
   AND lon BETWEEN 30.00 AND 30.20
;

So I've get:

+------------+
| vehicle_id |
+------------+
|      12787 |
|       3123 |
|       9734 |
|      11201 |
|       7241 |
|      21002 |
|       4509 |
+------------+
7 rows in set (0.01 sec)

EXPLAIN shows the next (a bit trimmed):

+----+-------------+-------+-------+------------------+------------+---------+------+-------+----------------------------------------+
| id | select_type | table | type  | possible_keys    | key        | key_len | ref  | rows  | Extra                                  |
+----+-------------+-------+-------+------------------+------------+---------+------+-------+----------------------------------------+
|  1 | SIMPLE      | w     | range | ...ts_lat_lon... | ts_lat_lon | 12      | NULL | 57362 | Using index condition; Using temporary |
+----+-------------+-------+-------+------------------+------------+---------+------+-------+----------------------------------------+
1 row in set (0.00 sec)

Here we can see that there is no penalties for using BETWEENs with proper index.

Here is the suggestion: lat-lon coordinates have the anomaly near to the prime meridian. Every rectangle dissected by it should be splitted into two different rectangles to the left and to the right of PM and checked separately.

Answer 3

I have the following function which works to test if the a latitude and longitude is withing a rectangle.

NOOOOO. You're recreating the wheel.

Use geospatial

First we need to add a column, and then we populate it.

ALTER TABLE geom ADD pt POINT;

UPDATE geom
  SET pt = point(longitude, latitude);

ALTER TABLE geom DROP COLUMN latitude, DROP COLUMN longitude;

We dropped the old columns because they're redundant at this point. You can access what was the longitude and latitude by using ST_X(pt), and ST_Y(pt) respectively.

Then we add the index.

ALTER TABLE geom ADD SPATIAL INDEX(g);

Now, we can use an indexable operation with ST_MakeEnvelope

SELECT *
FROM geom
WHERE MBRContains(
  ST_MakeEnvelope(Point(x1,y1),Point(x2,y2)),
  pt
);

See an example of the above working on MySQL 5.7 on RexTester.

Click here for a list of MySQL's Spatial Functions which you can now use with the new column. When speaking of GIS, I always suggest MySQL users upgrade to a better database. =)