The example
Take the example of a Music table from https://www.amazon.com/Amazon-DynamoDB-Developer-Guide-Services-ebook/dp/B007Q4JGBM. This table has partition key Artist and sort key SongTitle.
The question
If I query for a particular song by a particular artist, is the performance O(1), or does it depend on how many entries that artist has in the database?
Prior research
The linked documentation indicates constant performance:
You can access any item in the Music table immediately, if you provide the Artist and SongTitle values for that item.
However, the phrasing is ambiguous and no support is given.
Here, the architecture is described in a way that indicates performance would not be constant:
DynamoDB uses the partition key value as input to an internal hash function. The output from the hash function determines the partition (physical storage internal to DynamoDB) in which the item will be stored. All items with the same partition key are stored together, in sorted order by sort key value.
I would expect this to result in O(lg m) performance, where m is the number of entries in the database for that particular partition key. This non-constant time would be necessary to search the sorted list of entries for the one with the correct sort key -- in this case, to search for the right SongTitle.
