Since rank is a property of your data, then that should be stored as a column in your table of records. Assuming Amazon's SimpleDB is similar to the typical RDBMS, you can then index this column and quickly satisfy all your above queries with the appropriate indexing strategy. This is normal for an RDBMS.

What kind of load profile do you expect? Are ranks modifiable after the record has been inserted?

If you expect this database to be heavily read-biased, you can cluster the table on the rank or create an index with rank as the leading column.