Designing Efficient POI Proximity Search with MySQL, GeoHash, and Redis

Finding nearby points of interest (POI) has become a daily necessity, and developers can greatly improve user experience by implementing efficient proximity search algorithms. This article walks through the technical design of POI search using MySQL, GeoHash, and Redis, with complete Go code examples.

1. Distance calculation with MySQL

Geographical coordinates are represented by latitude and longitude. For short distances, the Pythagorean theorem can be used, but for higher accuracy the Haversine formula is preferred. The following Go implementation computes the distance in meters between two coordinates:

const (
    dr          = math.Pi / 180.0
    earthRadius = 6372797.560856
)

func degRad(ang float64) float64 { return ang * dr }

// Distance calculates the distance between two points (latitude1, longitude1) and (latitude2, longitude2) in meters.
func Distance(latitude1, longitude1, latitude2, longitude2 float64) float64 {
    radLat1 := degRad(latitude1)
    radLat2 := degRad(latitude2)
    a := radLat1 - radLat2
    b := degRad(longitude1) - degRad(longitude2)
    return 2 * earthRadius * math.Asin(math.Sqrt(math.Pow(math.Sin(a/2), 2)+
        math.Cos(radLat1)*math.Cos(radLat2)*math.Pow(math.Sin(b/2), 2)))
}

1.2 MySQL table design and query

The positions table stores POI identifiers and their coordinates, plus optional attributes such as business hours and contact information.

CREATE TABLE `positions` (
  `id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 'auto‑increment primary key',
  `poi_uid` VARCHAR(64) NOT NULL COMMENT 'unique POI id',
  `lng` DOUBLE(15,7) NOT NULL COMMENT 'longitude',
  `lat` DOUBLE(15,7) NOT NULL COMMENT 'latitude',
  -- other POI fields ...
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Using the Haversine formula directly in a SELECT statement allows sorting by distance and retrieving the top‑N nearest POIs:

SELECT `id`, `poi_uid`, `lng`, `lat`,
       ROUND(6371.393 * 2 * ASIN(SQRT(
           POW(SIN((? * PI() / 180 - `lat` * PI() / 180) / 2), 2) +
           COS(? * PI() / 180) * COS(`lat` * PI() / 180) *
           POW(SIN((? * PI() / 180 - `lng` * PI() / 180) / 2), 2)
       )) * 1000 AS distance_um
FROM `positions`
WHERE /* optional range filter */
ORDER BY distance_um ASC
LIMIT ?;

1.3 Index optimization

Creating a composite index on (lng, lat) speeds up the range scan, but because the distance calculation still requires scanning all rows, a common optimization is to first limit the search to a square bounding box defined by a latitude/longitude range.

ALTER TABLE `positions` ADD INDEX idx_lng_lat(`lng`, `lat`);

2. Dimensionality reduction with GeoHash

GeoHash converts 2‑D coordinates into a 1‑D integer, enabling fast range queries using B‑tree indexes. The algorithm repeatedly bisects latitude and longitude intervals, interleaving the bits to form the final hash. The following Go code encodes a coordinate into a 52‑bit GeoHash:

const defaultBitSize = 52 // 26 bits for lng, 26 bits for lat

func encode0(lng, lat float64, bitSize uint) ([]byte, [2][2]float64) {
    llbox := [2][2]float64{{-180, 180}, {-90, 90}}
    pos := [2]float64{lng, lat}
    hash := &bytes.Buffer{}
    bit, step := 0, uint8(0)
    var code uint8
    for step < bitSize {
        for direction, val := range pos {
            mid := (llbox[direction][0] + llbox[direction][1]) / 2
            if val < mid {
                llbox[direction][1] = mid
            } else {
                llbox[direction][0] = mid
                code |= 1 << (7 - bit)
            }
            bit++
            if bit == 8 {
                hash.WriteByte(code)
                bit, code = 0, 0
            }
            step++
            if step == bitSize { break }
        }
    }
    if code > 0 { hash.WriteByte(code) }
    return hash.Bytes(), llbox
}

After obtaining the GeoHash bytes, they can be stored as a BIGINT UNSIGNED column for fast equality and range scans.

func ToUint64(buf []byte) uint64 {
    if len(buf) < 8 {
        buf2 := make([]byte, 8)
        copy(buf2, buf)
        return binary.BigEndian.Uint64(buf2)
    }
    return binary.BigEndian.Uint64(buf)
}

Using the first 4‑6 characters of the Base32‑encoded GeoHash as separate indexed columns ( geohash_4 , geohash_5 , geohash_6 ) enables progressive precision queries (gradual recall) without scanning the whole table.

CREATE TABLE `positions` (
  `id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
  `poi_uid` VARCHAR(64) NOT NULL,
  `lng` DOUBLE(15,7) NOT NULL,
  `lat` DOUBLE(15,7) NOT NULL,
  `geohash_4` CHAR(4) NOT NULL DEFAULT '',
  `geohash_5` CHAR(5) NOT NULL DEFAULT '',
  `geohash_6` CHAR(6) NOT NULL DEFAULT '',
  PRIMARY KEY (`id`),
  INDEX idx_geohash4_lng_lat(`geohash_4`, `lng`, `lat`),
  INDEX idx_geohash5_lng_lat(`geohash_5`, `lng`, `lat`),
  INDEX idx_geohash6_lng_lat(`geohash_6`, `lng`, `lat`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Querying with the 6‑character GeoHash reduces the scanned rows dramatically, and if the result set is insufficient, the query can fall back to the 5‑ or 4‑character indexes for a larger search radius.

3. High‑concurrency POI search with Redis Geo

Redis 3.2+ provides a native Geo module that stores coordinates in a sorted‑set (zset) where the score is a 52‑bit GeoHash integer. Adding POIs is as simple as:

redis-cli> GEOADD positions 116.412893 39.948795 abcdf
(redis) (integer) 1

Nearby POIs can be retrieved with GEORADIUS :

redis-cli> GEORADIUS positions 116.432893 39.178795 20 km WITHDIST COUNT 3 ASC
1) 1) "gdfsdas"
   2) "4.7992"
2) 1) "sdgdgd"
   2) "15.0896"

When the top‑N result set is incomplete, a progressive‑recall strategy can be applied by expanding the GeoHash precision or by executing Lua scripts that batch multiple radius queries.

4. Building a local Geo index

For ultra‑low latency requirements, a custom in‑memory index (e.g., a skip‑list or prefix‑tree) can store only (lng, lat, id) triples. A benchmark shows that Go can retrieve the top‑100 POIs from one million entries in ~0.02 ms under 1000 concurrent requests.

package fastgeo

import (
    "math/rand"
    "strconv"
    "testing"
    "time"
)

var fastGeo *FastGeo

func init() {
    fastGeo = MakeFastGeo()
    lngMin, lngMax := 116171356, 116638188
    latMin, latMax := 39748529, 40155613
    rand.Seed(time.Now().UnixNano())
    for i := 1; i <= 1000000; i++ {
        lng := float64(rand.Intn(lngMax-lngMin)+lngMin) / 1e6
        lat := float64(rand.Intn(latMax-latMin)+latMin) / 1e6
        fastGeo.GeoAdd(lng, lat, strconv.Itoa(i))
    }
}

func BenchmarkFastGeo_GeoRadius(b *testing.B) {
    lngMin, lngMax := 116171356, 116638188
    latMin, latMax := 39748529, 40155613
    rand.Seed(time.Now().UnixNano())
    for n := 0; n < b.N; n++ {
        lng := float64(rand.Intn(lngMax-lngMin)+lngMin) / 1e6
        lat := float64(rand.Intn(latMax-latMin)+latMin) / 1e6
        fastGeo.GeoRadius(lng, lat, 10000, 0, 100)
    }
}

The GeoRadius implementation first obtains the nine‑grid GeoHash neighbours, then launches a goroutine for each grid to query the local skip‑list, finally merges and sorts the results.

func (fastGeo *FastGeo) GeoRadius(lng, lat, radius float64, offset, limit int64) []string {
    areas := geohash.GetNeighbours(lat, lng, radius)
    var wg sync.WaitGroup
    wg.Add(len(areas))
    var mu sync.Mutex
    members := []string{}
    for _, area := range areas {
        go func(a [2]uint64) {
            lower := &sortedset.ScoreBorder{Value: float64(a[0])}
            upper := &sortedset.ScoreBorder{Value: float64(a[1])}
            elems := fastGeo.Container.RangeByScore(lower, upper, offset, limit, true)
            mu.Lock()
            for _, e := range elems { members = append(members, e.Member) }
            mu.Unlock()
            wg.Done()
        }(area)
    }
    wg.Wait()
    // TODO: sort by actual distance
    return members
}

5. Conclusion

The article demonstrates that POI proximity search is achievable with standard relational databases, modern geospatial encodings like GeoHash, and high‑performance in‑memory stores such as Redis. By combining these techniques and leveraging Go’s concurrency, developers can build scalable, low‑latency location services for a variety of applications.