Location-based services (LBS) often require finding points of interest (POIs) near a given location—such as nearby users or landmarks. This functionality relies on the coordinates of stored POIs (relatively static data) and the dynamic query point provided at runtime.

1. Distance Calculation Using Standard SQL

A straightforward approach involves computing distances directly in SQL using the haversine formula, which approximates great-circle distance on a sphere:

SELECT id,
  (3959 * ACOS(
    COS(RADIANS(78.3232)) *
    COS(RADIANS(lat)) *
    COS(RADIANS(lng) - RADIANS(65.3234)) +
    SIN(RADIANS(78.3232)) *
    SIN(RADIANS(lat))
  )) AS distance
FROM markers
HAVING distance < 30
ORDER BY distance
LIMIT 20;

To improve performance, a bounding box filter is often applied first to reduce the dataset before applying the expensive trigonometric calculation:

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
  AND locations.lat BETWEEN 42.0 AND 42.5
  AND locations.lng BETWEEN -71.6 AND -71.1
HAVING distance < 10
ORDER BY distance;

This method is simple to implement but inefficient for large datasets due to full-table scans and lack of index-friendly operations.

2. Native Geospatial Support in Databases

Modern databases offer built-in geospatial capabilities:

• Redis: Uses GEOADD, GEORADIUS, and related commands to store and query locations via sorted sets encoded with geohash-like values.
• MySQL (5.7+): Supports spatial data types (POINT, POLYGON) and spatial indexes. Functions like ST_Distance_Sphere() and MBRContains() enable efficient proximity queries.
• MongoDB: Leverages GeoJSON objects and 2dsphere indexes to support queries such as $near and $geoWithin.

These solutions offload spatial logic to the database engine, offering better performance and correctness than manual calculations, especially when proper index are used.

3. Custom Implementation Using Geohash

Geohash encodes latitude and longitude into a single string by interleaving bits of both coordinates. Nearby locations share longer common prefixes, enabling range queries using standard B-tree indexes.

However, edge cases near grid boundaries require checking adjacent geohash cells (typically up to 8 neighbors). After retrieving candidates via prefix matching, a final distance filter (e.g., haversine) is often applied to ensure accuracy.

Example workflow:

1. Encode query point in to a geohash (e.g., u4pruydqqvj).
2. Generate neighboring hashes.
3. Query database for all POIs with hashes matching any of these prefixes.
4. Filter results by actual distance.

Libraries for geohash encoding/decoding exist in most languages (JavaScript, Python, Java, etc.), and integration with relational databases is straightforward.

While this approach enables efficient indexing in non-spatial databases, precision must be carefully chosen—shorter hashes cover larger areas (more false positives), while longer ones increase storage and reduce neighbor overlap effectiveness.