Nearby search

The problem: "stores near me, open now"

Snip's store-locator links grow up: besides redirecting to the single nearest store, the link can open a small page listing the three nearest stores that are open now and stock the campaign's product, each with its distance. Some visitors are in central London with 40 stores within a kilometre; others are in the Highlands with the nearest store 80 km away.

Two kinds of question

• Radius: everything within 5 km. Good when "near" has a natural limit (delivery areas, "within walking distance").
• Nearest k: the 3 closest, however far. Good when there must always be an answer.

Both are supported directly by the common stores, using the cell indexes of 12.05 Geospatial indexes underneath.

PostGIS (Postgres with geospatial types): store locations as geography so distances are in metres on the Earth's surface, index them with GiST, and use ST_DWithin for radius (it uses the index) and the <-> operator to order by distance with the index:

CREATE INDEX stores_location ON stores USING gist (location);  -- location geography(Point)

-- The 3 nearest open stores within 25 km of the visitor
SELECT id, name, ST_Distance(location, $1::geography) AS metres
  FROM stores
 WHERE chain_id = $2
   AND open_now
   AND ST_DWithin(location, $1::geography, 25000)
 ORDER BY location <-> $1::geography
 LIMIT 3;

Redis keeps geospatial members in a sorted set whose scores are 52-bit geohashes, so a search scans the cells around the point:

GEOADD stores:acme -0.1419 51.5152 store:oxford-st
GEOSEARCH stores:acme FROMLONLAT -0.1278 51.5074 BYRADIUS 5 km ASC COUNT 3 WITHDIST

The PostGIS version answers the whole question in one query; Redis is faster for pure "nearest" lookups in memory but leaves filters like "open now" to the application.

Filters change the plan

"Open now" and "stocks this product" can remove most candidates. With a nearest-k index search, filtering afterwards can come up short, the same problem as filtered vector search (10.05 Vector and hybrid search). Options:

• Filter inside the index query where the database supports it (PostGIS combines the spatial index with other conditions in one plan).
• Over-fetch and filter: ask for the nearest 30, filter to 3.
• Separate indexes per filter value when there are few: one Redis set per chain, or per product category.

Radius that adapts to density

A fixed 5 km radius returns 300 stores in central London and none in the Highlands. Instead, grow the search: try the nearby cells; if fewer than k candidates survive the filters, widen to the next ring of cells or a larger radius; stop at a maximum distance and say so ("no stores within 100 km"). Most queries, in dense areas, finish on the first step.

Ranking by more than distance

For "best nearby" rather than "nearest", score candidates on distance and other signals, like ratings, opening hours, stock, or the chain's preference, the same blend as search ranking (10.02 Ranking: TF-IDF to BM25). Distance usually enters as a decay: a store 300 m away and one 500 m away are about equally good; one 20 km away isn't.

Cache by cell

Many visitors arrive from the same few areas. Cache results by cell, not by exact coordinates (no two visitors share exact coordinates): "nearest open stores for geohash gcpvj at 14:00" serves everyone in that 5 km cell for a few minutes. Store data changes rarely, so the cache can live long, invalidated when a store's details change (06.04 Invalidation and staleness).

When the points move

Stores don't move. Drivers, couriers and scooters do, every few seconds. A disk-based index that's rewritten on every position update struggles, so moving objects usually live in memory: each update moves an ID from one cell's set to another, and searches read the sets for nearby cells. Updates far outnumber queries, positions are slightly stale by design, and the index can be rebuilt from the latest positions after a restart. Matching those moving supplies to demand is 12.07 Matching supply and demand.

Recap

Interview questions