DynamoDB schema for querying nearby coordinates

Question

I'm struggling with DynamoDB schema design of a table storing locations. The table will have [userId, lastUpdatedTime, locationGooglePlaceId, longitude, latitude, hideOnUI(bool)]

one of the main query is given user current location (x, y) as GPS coordinate, query nearby userId based on their longitude and latitude.

The problem is how would I design index for this purpose? The table itself can have HASH key UserId, SORT key lastUpdatedTime; but how would GSI go? I seem can't identify any partition key for "equal" operation

In SQL it'll be something like:

select * from table where x-c <= longitude and longitude < x+c AND y-c <= latitude and latitude < y+c

Thanks

Ivan Mushketyk Ivan Mushketyk · Accepted Answer · 2017-07-24T12:22:49

First of all, I am not sure if DynamoDB is a good fit here, maybe it's better to use another database, since Dynamo does not support complicated indexes.

Nonetheless, here is a design that you can try.

First of all you can split your map into multiple square blocks, every square block would have an id, and known position and size.

Then if you have a location and you want to find all nearby points, you can do the following.

Every point in your database will be storred in the Points table and it will have following keys:

BlockId (String, UUID, partition key) - id of a block this point belongs to

Latitude (Number, sort key) - latitute of a point

Longtitude (Number) - simple attribute

Now if you know what square a user location in and what squares are nearby, you can perform in all nearby squares the following search:

BlockId = <nearby_block_id>
Latitute between(y-c, y+c)

and use a filter expression based on the Longtitude attribute:

Longtitutede between(x-c, x+c)

It does not really matter what to use as a sort key latitude or longtitude here.

Between is a DynamoDB operator that can be used with sort keys or for filtering expressions:

BETWEEN : Greater than or equal to the first value, and less than or equal to the second value. AttributeValueList must contain two AttributeValue elements of the same type, either String, Number, or Binary (not a set type). A target attribute matches if the target value is greater than, or equal to, the first element and less than, or equal to, the second element. If an item contains an AttributeValue element of a different type than the one provided in the request, the value does not match. For example, {"S":"6"} does not compare to {"N":"6"}. Also, {"N":"6"} does not compare to {"NS":["6", "2", "1"]}

Now the downside of this is that for every partition key there can be no more than 10GB of data with this key. So the number of dots that you can put in a single square is limited. You can go around this if your squares are small enough or if your squares have variable sizes and you use big squares for not very crowded areas and small squares for very crowded areas, but seems to be a non-trivial project.

DynamoDB schema for querying nearby coordinates

1 Answers