Optimizing Geospatial Distance Queries with MySQL Spatial Indexes

Problem Background and Performance Bottleneck Analysis

When processing large-scale geospatial data, traditional distance calculation queries often face severe performance challenges. Taking a database with nearly a million location records as an example, each query needs to calculate the spherical distance between all points and the target point. This full-table scan approach becomes completely infeasible in high-concurrency scenarios with 100+ queries per second.

The original query uses MySQL implementation of Haversine formula:

SELECT 
  name, 
   ( 3959 * acos( cos( radians(42.290763) ) * cos( radians( locations.lat ) ) 
   * cos( radians(locations.lng) - radians(-71.35368)) + sin(radians(42.290763)) 
   * sin( radians(locations.lat)))) AS distance 
FROM locations 
WHERE active = 1 
HAVING distance < 10 
ORDER BY distance;

The main issue with this query is that it requires complex trigonometric calculations for every record in the table, making it impossible to effectively utilize index optimization. Even with the active=1 condition filter, the computational overhead remains enormous.

Spatial Index Optimization Solution

Starting from MySQL 5.7.5, the InnoDB storage engine officially supports SPATIAL indexes, providing new possibilities for geospatial query optimization. The core idea of the optimization solution is to use spatial indexes to quickly screen candidate points that may meet the conditions, and then perform precise distance calculations.

Data Table Structure Optimization

First, it's necessary to change from traditional separate latitude and longitude storage to using MySQL's geometry data types:

ALTER TABLE locations ADD COLUMN coordinates POINT;
UPDATE locations SET coordinates = Point(lng, lat);
ALTER TABLE locations ADD SPATIAL INDEX(coordinates);

Note that MySQL's Point constructor parameter order is Point(longitude, latitude), which differs from the common latitude-first convention.

Bounding Box Pre-screening Principle

Based on the Earth's approximate spherical characteristics, we can construct a rectangular bounding box containing the target point and use the MBRContains function to quickly filter points within this region. The construction of this bounding box needs to consider the impact of latitude on longitude spacing:

SELECT *
FROM locations
WHERE MBRContains(
    LineString(
        Point(
            @lon + 10 / (111.1 / COS(RADIANS(@lat))),
            @lat + 10 / 111.1
        ),
        Point(
            @lon - 10 / (111.1 / COS(RADIANS(@lat))),
            @lat - 10 / 111.1
        )
    ),
    coordinates
)

Where 111.1 kilometers is the approximate distance per degree of latitude, and the distance per degree of longitude needs to be multiplied by COS(RADIANS(@lat)) to account for latitude's effect on longitude spacing.

Complete Optimized Query Implementation

Combining spatial index screening and precise distance calculation, the complete optimized query is as follows:

SELECT 
    *,
    (6371 * ACOS(COS(RADIANS(56.946285)) * COS(RADIANS(Y(coordinates))) 
    * COS(RADIANS(X(coordinates)) - RADIANS(24.105078)) + SIN(RADIANS(56.946285))
    * SIN(RADIANS(Y(coordinates))))) AS distance
FROM locations
WHERE active = 1
AND MBRContains(
    LineString(
        Point(
            24.105078 + 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 + 15 / 111.133
        ),
        Point(
            24.105078 - 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 - 15 / 111.133
        )
    ),
    coordinates
)
HAVING distance < 15
ORDER BY distance

The execution process of this query consists of three key steps: first, basic filtering using active=1; then quickly locating candidate points within the bounding box through spatial indexes; finally performing precise distance calculation and filtering on candidate points.

Performance Comparison and Optimization Effects

Through actual test comparisons, the optimized query shows significant performance improvements:

• Original Query: Requires Haversine calculation for all active records, time complexity O(n)
• Optimized Query: Spatial indexes reduce candidate point count to 1%-5% of original, dramatically decreasing computation

In tests with million-level data volume, query response time decreases from several seconds to millisecond level, fully meeting high-concurrency scenario requirements.

Technical Details and Considerations

In practical applications, several key technical details need attention:

Earth Radius Parameter Selection

The Earth radius parameter in Haversine formula needs selection based on distance units:

• Miles: Use 3959
• Kilometers: Use 6371

Bounding Box Approximation

The constructed bounding box is actually a spherical rectangle, differing significantly from planar rectangles in polar regions, but this approximation is sufficiently accurate in most inhabited areas.

Index Selection Strategy

For different MySQL versions, spatial index support varies:

• MySQL 5.7.5+: Both InnoDB and MyISAM support SPATIAL indexes
• Earlier versions: Only MyISAM tables support SPATIAL indexes

Extended Optimization Approaches

Beyond the core optimization solution discussed in this article, consider the following extended optimizations:

Multi-level Screening Strategy

For extremely large range queries, employ multi-level bounding box strategies, starting with larger bounding boxes for quick screening and gradually narrowing the range.

Cache Optimization

For hotspot queries, cache calculation results to avoid repeated computations.

Distributed Solutions

In ultra-large-scale data scenarios, consider distributed database solutions based on geographic partitioning.

Conclusion

By reasonably utilizing MySQL's spatial index functionality combined with bounding box pre-screening strategies, significant performance improvements in geospatial distance queries can be achieved. This optimization solution not only applies to the specific scenario discussed in this article but its core concepts can also be extended to other applications requiring efficient queries based on spatial relationships. In practical applications, appropriate parameter tuning and architectural design based on specific data scale and query patterns are recommended.