Image via CrunchBase

I was recently working with a dataset in Amazon’s SimpleDB, and I needed to be able to sort query results on multiple attributes. SimpleDB currently only allows sorting by a single attribute, so I was stuck. The solution is rather simple: combine the columns that I need to sort on into a single new attribute, and use this new composite attribute to perform my sorting. I kept the existing attributes in their current form, but added a new attribute that is the concatenation of the two attributes I wished to sort.

SimpleDB sorts lexicographically, so concatenating two fields produces exactly the expected results provided you handle a few situations properly. There are a few things to keep in mind as you produce the multi-sort attribute.

Properly pad your fields

Sorting numbers in SimpleDB requires some encoding to provide the expected results. The SimpleDB documentation provides examples of this. If you have properly encoded your numeric fields, then the length of each attribute will be the same as all the rest. Each values of an attribute must be the same length to provide consistent results.

Align the sort order of each field

You can only sort your one field one direction; ascending or descending. If you wish to sort column 1 ascending and column 2 descending, then you must reverse the encoding of field 2 prior to concatenation, then sort the combined column ascending. You could also do the reverse: reverse the encoding of field 1, then sort the combined attribute descending.

The SimpleDB documentation describes encoding numeric values, but this concept applies to both numeric an alphanumeric fields, as long as the length of the attribute value is either the same, or can be padded to be the same.

Reversed encoding is nothing more then changing the data to be the reverse of what it really is. A single digit number attribute value could be subtracted from a base value, such that 0 becomes 9, 1 becomes 8, and so on. Characters can be reversed as well, turning a into z, b into y, etc. The exact encoding used will depend on the properties of the data being stored.

Keep in mind that the value of the multi-sort attribute never needs to be parsed or read: it is only used for sorting results. Even if the translation is an ugly one, it only needs to be done on an update.

Concatenate attributes in order of sorting preference

If you wish to sort on attribute A, then attribute B, followed by C, your combined attribute must be combined in that order, left to right.

Flexibility

This approach is fairly flexible, including creating a sorting attribute from any number of attributes and creating multiple sorting attributes, as long as the attribute length and number of attributes fall within the restrictions of SimpleDB.

While this technique is not new, I wanted to explain it here to provide hints to others with no idea how to solve the problem. Credit for revealing this concept to me go to Phil Windley, who told me that the only reason I don’t know it already is that I’m “too young� to remember a time when most database platforms carried the same restriction. I’m just glad to have experienced old guys to learn from. :)