DynamoDB Single Table Schema Design with Adjacency Lists

Question

I am trying to understand how to properly design a DynamoDB schema. I've read a few articles, watched some YouTube videos but, to be honest, I don't yet feel quite comfortable.

This is what I am trying to design properly:

two entities, "location" (id & name) and "vehicle" (id & name)
a location can have 0-n vehicles
a vehicle can be in 0-1 locations

Access patterns:

get a list of all available locations (id & name)
get a list of all available vehicles and their current location (id, name, location-id, location-name)
get a list of all vehicles in a given location (id, name)

I've read about adjacency lists and because there will be n-m relations I've decided to give it a try.

This is what I've came up with:

# | PK (GSI1-SK)         | SK (GSI1-PK)       | DATA
==|======================|====================|==============
1 | LOCATION#locationId1 | A                  | locationName1
2 | LOCATION#locationId2 | A                  | locationName2
3 | LOCATION#locationId1 | VEHICLE#vehicleId1 |
4 | LOCATION#locationId1 | VEHICLE#vehicleId2 |
5 | LOCATION#locationId2 | VEHICLE#vehicleId3 |
6 | VEHICLE#vehicleId1   | A                  | vehicleName1
7 | VEHICLE#vehicleId2   | A                  | vehicleName2
8 | VEHICLE#vehicleId3   | A                  | vehicleName3

#1-2 & #6-8 are my entity records, those with additional data for the entity itself (e.g. its name).

#3-5 is an example of how I would design a relationship. I've added an inverted GSI in order to be able to search in both ways.

Back to my access patterns:

get a list of all available locations (id & name)

query GSI1 for SK=A and PK begins with LOCATION#
get a list of all available vehicles and their current location (id, name, location-id, location-name)

query GSI1 for SK=A and PK begins with VEHICLE#

for each result item, query GSI1 for SK=VEHICLE#vehicleId and PK begins with LOCATION#

for each result item, query table for PK=LOCATION#locationId and SK=A

... this doesn't seem right
get a list of all vehicles in a given location (id, name)

query table for PK=LOCATION#locationId and SK begins with VEHICLE#

for each result item, query table for PK=VEHICLE#vehicleId and SK=A

... this doesn't seem right

Adjacency lists look like a nice and clean way to design complex relationships but either I am doing something wrong (probably) or they come with alot of querys that are necessary to look things up.

Any advice is appreciated.

user_16654793 · Answer

I modelled this in DynamoDB Workbench:

In order to:

"get a list of all available locations (id & name)"

select * from GS1 where PK1="ALL#LOCATION"

get a list of all available vehicles and their current location (id, name, location-id, location-name)

select * from MAIN-INDEX where PK="ALL#VEHICLE"

get a list of all vehicles in a given location (id, name)

select * from GSI1 where PK1="LOC#ID"

Several things to here:

It's important to distribute the traffic across all partition keys. I'm using "ALL#" partition keys in this design. Ideally you shard that somehow, there are several tricks like using dates or timestamp to the beginning of the day. You can randomly spread them across a fixed number of "ALL#" records and then randomly query 1 if your use case allows it. If you have millions of locations this is probably ok. That's how you take these decisions: think of the traffic and the behaviour of the data.
In order to use both indexes I put the "ALL#LOCATION" and the "ALL#VEHICLE" partition keys in different indexes.
Notice that vehicle 4 doesn't have a PK1. See what happens to GSI1. This is what's called a sparse index.
I denormalized the vehicle-location relationship. Assuming that the location ID and the location name are immutable it's ok to do this, the problem is when the attributes you denormalize are mutable, avoid that if possible.

DynamoDB Single Table Schema Design with Adjacency Lists

1 Answers