Geospatial queries in DynamoDB

Amazon's DynamoDB is a key-value database, which is serverless, has on-demand pricing, and has almost infinite performance, which makes it a good solution for small sites. But unfortunately the support for indexes is very basic which makes it impossible to run geospatial queries easily (like, filtering by lat and lon in the same query). This page collects solutions to this problem.

Using square id

One solution is to divide the globe into squares of a fixed size, then assign each object to a square. That way, in theory, it might be enough to run 9 queries to get data for 9 blocks, where center is on the screen and the rest is around it. The problem is that with change in zoom, visible block size changes significantly, and we might end up requesting a huge number of items with one query, like the whole database.

One solution to this might be to use different block size for different zooms. We would need a separate table for that, where each record would have a zoom+square id and a list of items assigned to it, like:

{
 "id": "18,1234567",
 "items": [123, 234, 345]
}

This way we can use up to 9 queries for any zoom level. The downside is that with every tree update, we'd need to go through all supported zoom levels, find the square that the tree belongs to, then find all trees that are in that square, then update the list of item ids in the database. Not impossible, and for a database of this kind, which isn't updated too often, that would be a viable solution. But still much messier than an SQL database.

Actually, this approach might be needed with an SQL database too, because on smallest zoom we'd have to return the whole database, which isn't a good idea. Even clustering 1M of records on the backend before returning to the client doesn't look like a good idea, so we'd need zoom based pre-clustering anyway.

Slicing by longitude

Similar to the above, but instead of assigning square ids, just add a single key with integer longitude degree. Then it would be possible to query data for one particular degree, then filter by latitude on the client. That effectively makes 360 slices of the database. But still, for smallest zoom, we'd need to send 360 queries which isn't going to work.