DynamoDB vector search without embeddings

Serverless Advocate #85 asks Lee Harding which AWS service he's most excited about, and he picks DynamoDB vector indexes. Not for embeddings, though. His point is that most people hear "vector" and think semantic search, when a vector index is "a general-purpose tool for any domain where you need to find 'nearest neighbours' in some n-dimensional space". Geometry, topology, geography, sensor fusion.

So I had a go at the geography case.

The setup is a store locator, which is about the most ordinary geography question going. Seven real places stand in for shops, five in and around Leeds and two over in York, each carrying its actual latitude and longitude. You stand somewhere and ask which ones are nearest.

A shop is about as plain as a DynamoDB item gets. Partition key, a name, two numbers:

{
  "PK":        { "S": "PLACE#p-101" },
  "name":      { "S": "Briggate" },
  "lat":       { "N": "53.79756" },
  "lon":       { "N": "-1.54169" },
  "openUntil": { "S": "18:00" }
}

No sort key, and the coordinates are ordinary numbers sat on the item. Nothing about that is searchable by distance yet, so the question is what you have to add to make it so.

Degrees aren't a space

You can't hand a vector index a latitude and longitude as two numbers, because degrees aren't a space. Cosine measures the angle your pair makes with the origin, and the origin here is just (0, 0). Nothing is measured from there, so two places on opposite sides of the world can score as basically identical. Euclidean is less daft and still wrong, because a degree of longitude is 111km at the equator and 66km up here in Leeds, so a circle in degree space is an ellipse on the ground. Neither is fixable by picking a different distance function. It's the space that's broken, not the metric.

What works is projecting onto the unit sphere, which is three lines of trig:

x = cos(lat) * cos(lon)
y = cos(lat) * sin(lon)
z = sin(lat)

That triple goes on the item as position, an ordinary list of numbers sitting beside the name and the opening hours, because there is no vector type in DynamoDB. A vector index over that attribute is what makes it searchable.

Now every shop is a point on a ball of radius one, and the straight-line gap between two of those points is 2 * sin(theta / 2), where theta is the angle between them at the centre of the ball. That climbs steadily from zero to pi and never doubles back, so ordering by it gives you the true great-circle ordering. Not an approximation of it. The score converts back to kilometres with 2 * 6371 * asin(score / 2), which across those seven shops agrees with haversine to about half a metre.

Next to a geohash

Worth running that next to the way proximity normally gets done in DynamoDB, which is a geohash. It interleaves the two coordinates into a single string, so nearby places end up sharing a leading prefix and "what's near me" becomes a prefix read. That's a lovely trick, and DynamoDB is very good at prefix reads.

Briggate's full hash is gcwfhct3. To make that queryable you take the first four characters as a cell, key a GSI on it, and keep the whole hash as the sort key so neighbours inside a cell order by position rather than by id:

{
  "PK":      { "S": "PLACE#p-101" },
  "name":    { "S": "Briggate" },
  "geohash": { "S": "gcwfhct3" },
  "GSI1PK":  { "S": "GEO#gcwf" },
  "GSI1SK":  { "S": "gcwfhct3#p-101" }
}

So "what's near me" becomes one Query on GSI1PK = GEO#gcwf, which is cheap and exact. It's also where the problem lives: the cell is the partition key. A shop in a neighbouring cell isn't ranked lower, it's in a different partition, and the query never goes near it.

I put the query point on the concourse at Leeds station, which sits in geohash cell gcwf, and asked both. Here are the five nearest shops of the seven, the York pair being a good 35km out and no trouble for either approach:

Holbeck is a mile or so south of Leeds centre, and the cell boundary runs between it and the station. So the geohash hands you four shops, misses the one at 0.92km, and includes Hyde Park at two and a half times the distance because it happens to share four characters with where you're stood. That cell is roughly 23km by 19km, so this isn't a pathological case I've constructed: any query near an edge has it, which is most of them. Everyone who's built one of these knows about the boundary problem in the abstract. It's a bit sharper when the thing hands you a shop over twice as far away and looks perfectly happy about it.

Both access patterns are loaded in the console below, if you'd rather press it than take my word for it:

That's the engine running in your browser on the seven shops above. Run the vector search, then switch to the cell query, and Holbeck is the row that stops coming back.

Three lines of trig is still a model

So it's tempting to call this the version with no model in it. No weights to ship, and nothing to re-embed when a library version moves.

That's not quite right. Something decided degrees weren't the space and the unit sphere was, and that decision is now part of the index's contract in exactly the way an embedding model would be. Store vectors built one way, query with vectors built another, and nothing will tell you. Swap two components of the projection, or move to a different reference sphere, and you still hand over three finite numbers. The dimension count still matches, and the dimension count is the only thing a vector index ever checks. Every result comes back looking perfectly reasonable.

Which is the same failure people hit with a mismatched embedding model, with no machine learning anywhere near it. So write down whatever turns your data into numbers, keep it next to the index, and version it. When it changes, re-derive the lot.

Have a go

The full write-up for the store locator is on accesspatterns.dev, and there's a geohash-only version of the same seven shops if you want to poke at the prefix read on its own. Everything runs on dynoxide's WASM engine, so there's no account and nothing goes near AWS.

I did two of Harding's other cases the same way if you want them. Sensor fusion is five sensor channels on wildly different scales, where the numbers need normalising before the distance means anything at all, and it's the clearest illustration of the point above. Design tokens matches a pasted hex to the nearest approved colour, where converting to CIELAB makes the distance function a consequence rather than a choice.

And if you've got a geohash doing proximity in production, it's worth firing a few queries near a cell edge and looking at what comes back. It won't tell you it's missing anything.