Proximity Search: How "Restaurants Near Me" Doesn't Scan Every Restaurant

You tap "restaurants near me". Fifty milliseconds later you have a list — even though the database holds ten million restaurants and never measured the distance to even a thousand of them.

That gap is the whole topic. The job isn't finding the nearest thing faster. The job is making the search space smaller before you measure anything. That's spatial indexing.

---

The brute-force floor

Start with the version that obviously works. "Near" means within 2 km, so: compute the distance from your location to every restaurant, keep the ones under 2 km.

-- correct, and hopeless at scale
SELECT id, name
FROM restaurants
WHERE earth_distance(
        ll_to_earth(lat, lng),
        ll_to_earth(47.2088, 7.5323)   -- you
      ) < 2000;

It's correct. It's also ten million distance calculations per tap — trigonometry on every row, on every request, for every user. This is the floor we have to beat.

Why a normal index can't rescue you

The instinct is to throw an index at it. That instinct fails here, and why it fails is the key to everything after.

A B-tree index sorts one column and lets you jump straight to a value or a range. But "near" isn't one column. It's latitude AND longitude together — a circle around a point, not a value on a line.

CREATE INDEX ON restaurants (lat);   -- doesn't help

Sort by latitude and a range scan hands you every restaurant at that height worldwide — your neighborhood plus a band wrapping the entire planet. Add longitude as a second column and it's no better: the index can only use it after pinning latitude, so you still drag in that whole band first. One-dimensional tools can't cut a two-dimensional shape.

---

The idea: index space, not points

Here's the move. Stop trying to index the points. Index the space they sit in.

Chop the map into a grid of cells. When a restaurant is saved, work out which cell it lands in and stamp the row with that cell id. Downtown becomes cell 913.

ALTER TABLE restaurants ADD COLUMN cell_id BIGINT;

-- stamp on write: 1 km-ish cells
UPDATE restaurants
SET cell_id = (floor(lat / 0.01)::bigint * 100000)
            +  floor(lng / 0.01)::bigint;

CREATE INDEX ON restaurants (cell_id);   -- this one DOES help

The trick is that cell_id is just a number. It's one dimension again — exactly the shape a plain B-tree was built for. We didn't invent a magic index; we reshaped the question until an ordinary index could answer it.

The lookup: your cell, plus the eight around it

Now "near me" becomes a different question: which cell am I standing in?

Pull that cell — and the eight cells around it, a 3×3 block. The neighbors aren't optional. If you're standing near a cell border, the closest restaurant of all might be one meter away in the next cell over, and a single-cell lookup would silently miss it.

SELECT id, name, lat, lng
FROM restaurants
WHERE cell_id = ANY($1);   -- 9 cell ids: yours + 8 neighbors

Ten million rows just collapsed to a few hundred candidates — with zero distance math done so far.

Then measure what's left

Only now do you run the real trigonometry, on the survivors:

SELECT id, name
FROM restaurants
WHERE cell_id = ANY($1)                            -- prune (index, cheap)
  AND earth_distance(ll_to_earth(lat, lng),
                     ll_to_earth($2, $3)) < 2000   -- measure (exact, few rows)
ORDER BY 2;

Two phases, and the order is the whole point: prune with the grid, then measure what's left. The grid is allowed to be approximate — it over-fetches a bit, pulling in corners of the 3×3 block that are further than 2 km away. The exact distance filter cleans that up. The result is identical to the brute-force query; only the cost changed, from ten million calculations to a few hundred.

---

Cell size is a real decision

The grid isn't free-form — cell size is a trade-off with two bad extremes:

• Cells too big (a whole city per cell): one lookup hands you a million rows, and you're back to scanning. The index technically works and buys you nothing.
• Cells too small: a 2 km search no longer touches nine cells, it touches thousands of them. You've traded a big scan for an enormous list of cell ids.

The rule of thumb: size the cell to your search radius. If "near" means 2 km, cells about that size mean a 3×3 block genuinely covers the query, and the over-fetch stays small.

The trap: the world isn't evenly populated

A fixed grid quietly assumes the world is spread out evenly. It isn't. A downtown cell holds 50,000 restaurants; a desert cell holds none. Same cell size, wildly different cost — the grid goes lopsided, and the dense cells become exactly the slow scan you were trying to avoid.

The fix is a grid that splits only where it's crowded — adaptive, not fixed:

Approach	How it divides	Where you'll meet it
Fixed grid	Uniform cells, one size everywhere	Hand-rolled `cell_id`, small datasets
Geohash	Recursive halving into a base-32 string; prefix = bigger cell	Elasticsearch, Redis GEO, DynamoDB
Quadtree	Splits a dense cell into 4 children, recursively	Classic in-memory spatial indexes
R-tree / GiST	Nested bounding boxes around actual data	PostGIS (`GIST(geography)`)
H3	Hexagonal cells at fixed resolutions	Uber, analytics-heavy geo workloads

In practice you rarely hand-roll this. You write:

CREATE INDEX ON restaurants USING GIST (geog);

SELECT id, name
FROM restaurants
WHERE ST_DWithin(geog, ST_MakePoint($1, $2)::geography, 2000)
ORDER BY geog <-> ST_MakePoint($1, $2)::geography
LIMIT 20;

ST_DWithin does the prune-then-measure dance for you: the GiST index narrows to a bounding box, then exact distance runs on what survives. Knowing the mechanism is what tells you why it's fast — and why it stops being fast when your cells (or your bounding boxes) don't match your query radius.

---

The same trick, in AI: vector search

If you build anything with LLMs, you have already met this problem wearing a different hat.

RAG asks: "which of my ten million document chunks are nearest to this query embedding?" That is the identical question — nearest neighbors in a space — except the space has 768 or 1536 dimensions instead of 2, and "distance" is cosine similarity instead of meters.

The brute-force floor is the same: compare the query vector to every stored vector, ten million dot products per request. And the escape is the same shape — prune first, measure second:

• IVF (inverted file index) clusters vectors into buckets and searches only the few buckets nearest your query. That is literally the grid: cell ids, in high-dimensional space.
• HNSW builds a navigable graph and hops greedily toward the query, touching a tiny fraction of the nodes. Different data structure, same objective — visit few candidates, then score them exactly.

The one real difference: in 2D you can be exact cheaply, so ST_DWithin returns the true answer. In 1536 dimensions, grids fall apart (the curse of dimensionality — everything is roughly equidistant from everything), so ANN indexes accept an approximate answer and expose a knob (nprobe, ef_search) that trades recall for latency.

Which makes the tuning question a familiar one. ef_search too low is the cell that's too big — fast and wrong. ef_search too high is the grid too fine — accurate and slow. Same dial, different units.

---

The verdict

Spatial indexing isn't a faster distance formula. It's a reordering of the work:

1. Prune with something an ordinary index can answer instantly — a cell id, a bounding box, a cluster.
2. Measure exactly, on the few hundred rows that survived.
3. Size the pruning step to the query — cells to your search radius, nprobe/ef_search to your recall target.

Get that order right and ten million rows become a few hundred before any real math happens. Get it wrong — cells too big, cells too small, or a fixed grid over an uneven world — and you've built an index that's technically present and practically useless.

You don't find the nearest thing faster. You make the search space smaller first.

Want the visual version? Watch the reel.