Beyond Radius Search: Building 'Within a 30-Minute Walk' Queries with PostGIS and Isochrones

Tuần này trên Hacker News có một project leo lên hơn 1600 điểm: Local Wikipedia, tức là Wikipedia nhưng chỉ hiện những thứ cách bạn khoảng nửa tiếng đi bộ. Ý tưởng nghe thì đơn giản, nhưng ai từng làm tính năng "gần tôi" (quán ăn gần đây, shipper trong khu vực, phòng trọ quanh trường) đều biết có một cái bẫy: "30 phút đi bộ" không phải là một hình tròn. Ở Hà Nội, một điểm cách bạn 1.5km theo đường chim bay có thể nằm bên kia sông Hồng, và đi bộ tới đó mất cả tiếng. Bài này chia sẻ cách mình chuyển từ radius search ngây thơ sang dùng isochrone, với PostGIS 3.4 và Valhalla, kèm code chạy được.

Vấn đề của radius search

Cách phổ biến nhất là lấy tốc độ đi bộ trung bình (~5 km/h), nhân với 30 phút ra 2.5km, rồi query mọi điểm trong bán kính 2.5km. Trong PostGIS, câu này viết khá gọn:

-- PostgreSQL 16 + PostGIS 3.4
CREATE EXTENSION IF NOT EXISTS postgis;

CREATE TABLE places (
  id      BIGSERIAL PRIMARY KEY,
  name    TEXT NOT NULL,
  geom    GEOGRAPHY(Point, 4326) NOT NULL
);

CREATE INDEX places_geom_gix ON places USING GIST (geom);

-- Tìm mọi điểm trong 2.5km quanh Hồ Hoàn Kiếm
SELECT id, name,
       ROUND(ST_Distance(geom, ST_MakePoint(105.8524, 21.0287)::geography)) AS meters
FROM places
WHERE ST_DWithin(geom, ST_MakePoint(105.8524, 21.0287)::geography, 2500)
ORDER BY meters
LIMIT 50;

Mấy lưu ý từ kinh nghiệm thực tế:

• Dùng GEOGRAPHY thay vì GEOMETRY nếu bạn muốn tính bằng mét mà không phải lo phép chiếu. Đổi lại thì chậm hơn một chút.
• ST_DWithin dùng được GIST index, còn ST_Distance(...) < 2500 trong WHERE thì không. Đây là lỗi mình gặp nhiều nhất khi review code.
• Thứ tự là ST_MakePoint(lon, lat), kinh độ đứng trước. Nhầm thứ tự là điểm của bạn chạy sang Nam Cực.

Vấn đề là kết quả sai về mặt ngữ nghĩa. Với người dùng thì đường chim bay chẳng có ý nghĩa gì; thứ họ cần biết là "đi bộ tới được không". Sông, đường sắt, cao tốc, khu quân sự, ngõ cụt đều làm vùng đi được bị méo đi so với hình tròn.

Isochrone: vùng thực sự đi tới được

Isochrone là polygon bao quanh mọi điểm có thể tới trong X phút theo mạng lưới đường thật. Engine routing sẽ chạy Dijkstra trên graph đường (lấy từ OpenStreetMap), dừng lại khi chi phí vượt ngưỡng, rồi dựng polygon từ các node đã tới được.

flowchart LR
    A[User location] --> B{Isochrone cache?}
    B -- hit --> D[Polygon GeoJSON]
    B -- miss --> C[Valhalla /isochrone]
    C --> E[Save cache]
    E --> D
    D --> F[PostGIS ST_Intersects]
    F --> G[Ranked results]

Có vài engine open source: OSRM (nhanh, nhưng không có isochrone native), GraphHopper (có isochrone, Java), và Valhalla (C++, isochrone native, hỗ trợ costing pedestrian, bicycle, auto). Mình chọn Valhalla vì setup bằng Docker khá nhẹ và costing cho người đi bộ chịu được cả bậc thang, đường cấm xe.

Dựng Valhalla với dữ liệu Việt Nam từ Geofabrik:

mkdir -p ~/valhalla/custom_files && cd ~/valhalla

docker run -d --name valhalla \
  -p 8002:8002 \
  -v $PWD/custom_files:/custom_files \
  -e tile_urls=https://download.geofabrik.de/asia/vietnam-latest.osm.pbf \
  -e serve_tiles=True \
  -e build_admins=True \
  ghcr.io/valhalla/valhalla-scripted:latest

# Lần đầu build tiles mất khoảng 10-20 phút cho Việt Nam (~300MB pbf)
docker logs -f valhalla

# Test nhanh: isochrone 15 và 30 phút đi bộ quanh Hồ Gươm
curl -s http://localhost:8002/isochrone --json '{
  "locations": [{"lat": 21.0287, "lon": 105.8524}],
  "costing": "pedestrian",
  "contours": [{"time": 15}, {"time": 30}],
  "polygons": true
}' | jq '.features | length'

Kết quả trả về là một GeoJSON FeatureCollection, mỗi contour là một Feature. Nếu so với hình tròn 2.5km, bạn sẽ thấy polygon thực tế nhỏ hơn đáng kể và bị "cắt cụt" ở phía sông Hồng, vì cầu Long Biên và cầu Chương Dương là hai lối đi bộ duy nhất gần đó.

Ghép isochrone vào PostGIS

Đây là phần backend chính. Mình dùng Python 3.12, httpx và psycopg 3. Ý tưởng là gọi Valhalla lấy polygon, cache lại theo vị trí đã làm tròn, sau đó để PostGIS lọc.

import json
import httpx
import psycopg

VALHALLA = "http://localhost:8002/isochrone"
DSN = "postgresql://app:app@localhost:5432/geo"

def cache_key(lat: float, lon: float, minutes: int) -> str:
    # Làm tròn 3 chữ số thập phân ~ 110m, đủ chính xác cho đi bộ
    return f"{round(lat, 3)}:{round(lon, 3)}:{minutes}"

def get_isochrone(conn, lat: float, lon: float, minutes: int = 30) -> str:
    key = cache_key(lat, lon, minutes)
    row = conn.execute(
        "SELECT ST_AsGeoJSON(geom) FROM iso_cache WHERE key = %s", (key,)
    ).fetchone()
    if row:
        return row[0]

    resp = httpx.post(VALHALLA, json={
        "locations": [{"lat": lat, "lon": lon}],
        "costing": "pedestrian",
        "costing_options": {"pedestrian": {"walking_speed": 4.5}},
        "contours": [{"time": minutes}],
        "polygons": True,
        "denoise": 0.5,
        "generalize": 50,
    }, timeout=10)
    resp.raise_for_status()
    geometry = json.dumps(resp.json()["features"][0]["geometry"])

    conn.execute(
        """INSERT INTO iso_cache (key, geom)
           VALUES (%s, ST_GeomFromGeoJSON(%s)::geography)
           ON CONFLICT (key) DO NOTHING""",
        (key, geometry),
    )
    return geometry

def nearby_walkable(lat: float, lon: float, minutes: int = 30):
    with psycopg.connect(DSN, autocommit=True) as conn:
        iso = get_isochrone(conn, lat, lon, minutes)
        return conn.execute(
            """
            WITH iso AS (SELECT ST_GeomFromGeoJSON(%s)::geography AS g)
            SELECT p.id, p.name,
                   ROUND(ST_Distance(p.geom, ST_MakePoint(%s, %s)::geography)) AS meters
            FROM places p, iso
            WHERE ST_DWithin(p.geom, ST_MakePoint(%s, %s)::geography, 3000)
              AND ST_Intersects(p.geom, iso.g)
            ORDER BY meters
            LIMIT 50
            """,
            (iso, lon, lat, lon, lat),
        ).fetchall()

if __name__ == "__main__":
    for r in nearby_walkable(21.0287, 105.8524):
        print(r)

Vài chi tiết đáng chú ý:

• ST_DWithin làm pre-filter. Polygon isochrone không bao giờ vượt quá bán kính tối đa (tốc độ × thời gian), nên mình lọc thô bằng index trước, sau đó mới ST_Intersects với polygon phức tạp. Trên bảng 2 triệu điểm, query giảm từ ~400ms xuống ~15ms.
• generalize và denoise giúp polygon ít đỉnh hơn. Polygon thô từ Valhalla có thể tới vài nghìn đỉnh, làm ST_Intersects chậm hẳn.
• walking_speed: 4.5: mặc định của Valhalla là 5.1 km/h. Với vỉa hè Việt Nam toàn xe máy đỗ thì 4.5 vẫn còn lạc quan.

Bảng cache thì đơn giản: CREATE TABLE iso_cache (key TEXT PRIMARY KEY, geom GEOGRAPHY, created_at TIMESTAMPTZ DEFAULT now());. Nên có job xoá các bản ghi cũ hơn 30 ngày, vì dữ liệu OSM vẫn thay đổi.

Kiến trúc khi lên production

sequenceDiagram
    participant C as Client
    participant API as API Server
    participant DB as PostGIS
    participant V as Valhalla
    C->>API: GET /nearby?lat&lon&min=30
    API->>DB: lookup iso_cache
    alt cache miss
        API->>V: POST /isochrone
        V-->>API: GeoJSON polygon
        API->>DB: insert iso_cache
    end
    API->>DB: ST_DWithin + ST_Intersects
    DB-->>API: rows
    API-->>C: JSON results

Những điều mình rút ra sau khi chạy thật:

1. Valhalla tốn RAM lúc build, không tốn lúc serve. Build tiles cho Việt Nam cần khoảng 4GB RAM, còn serve thì 512MB là chạy ổn. Bạn có thể build trên máy dev rồi copy thư mục valhalla_tiles lên server.
2. Cache hit rate rất cao. Người dùng tập trung ở vài khu vực (quanh trường, văn phòng, trung tâm), nên làm tròn tới 3 chữ số thập phân cho hit rate trên 80% chỉ sau vài ngày.
3. Có fallback. Valhalla chết thì quay về radius search với bán kính nhỏ hơn (khoảng 1.8km), kết quả kém hơn một chút nhưng service vẫn chạy.
4. Đừng gọi isochrone theo từng request trên mobile. Mỗi lần GPS nhảy vài mét không đáng để tính lại polygon. Debounce phía client, và chỉ tính lại khi người dùng di chuyển quá 100m.

Kết luận

Tính năng "gần tôi" dễ làm sai vì hình tròn trông rất hợp lý trên giấy. Vài điểm bạn có thể áp dụng ngay:

• Luôn dùng ST_DWithin thay vì so sánh ST_Distance trong WHERE để tận dụng GIST index. Chỉ riêng việc này đã đáng để kiểm tra lại codebase.
• Radius search để pre-filter, isochrone để lọc chính xác. Kết hợp hai bước này vừa nhanh vừa đúng ngữ nghĩa.
• Self-host Valhalla bằng Docker với dữ liệu Geofabrik, chi phí gần như bằng 0, không phụ thuộc API bên ngoài và không lo bị tính tiền theo request.
• Cache polygon theo toạ độ đã làm tròn, và đơn giản hoá polygon bằng generalize trước khi lưu.
• Hiệu chỉnh tham số theo thực tế địa phương: tốc độ đi bộ, chuyện có được đi qua cầu hay không, đường nào cấm người đi bộ.

Project Local Wikipedia viral vì nó đặt câu hỏi đúng: thứ gì thực sự nằm trong tầm với của tôi? Là developer, chỉ cần thay hình tròn bằng một polygon đúng là bạn đã trả lời câu hỏi đó tốt hơn phần lớn app ngoài kia.