Paging in Google App Engine

Paging in Google App Engine

I've spent the past couple of days spending my time trying to figure out how to do proper paging in Google App Engine. Once I have a workable solution, I'll open the stuff out on google code as I see lots of people struggling with this.

The goal: create a simple but powerful paging solution for GAE, with the following features:
- forward and backward paging, support for first page and last page
- sorting by (a subset) of fields (one order only at a time)
- having a filtering criteria in a like fashion (e.g. typing 'Tom' will filter and only display persons with name starting 'Tom')
- keep track of total number of pages

Design decissions:
- do NOT use limit/offset as it doesn't scale. Instead rely on cursors
- use sharding to keep the total number of pages updated
- accept compromises, but aim for the best performance/scalability

The obstacle (i.e. last bastion):
I feel the only problem left is when I have a filtering criteria (e.g. name begins with 'Tom') and a sorting criteria on a different property.

e.g. Person [name, age]
Filter by name 'Tom*'
Sort by age

Reading through the documentation, I thought I've found the solution:
Query q = new Query("Person");
q.addFilter("name", FilterOperator.GREATER_THAN_OR_EQUAL, nameFilter);
q.addFilter("name", FilterOperator.LESS_THEN, nameFilter + "\uFFFD");
q.addSort("name", SortDirection.ASCENDING);
q.addSort("age", SortDirection.ASCENDING);

I thought this would return:
Tom2 18
Tom1 20

Unfortunately, this returns
Tom1 20
Tom2 18
as the query is first filtered by name, then by age as a secondary key.

The only solution I can think of is to put the whole filter result into a Java structure, sort by using a comparator and then pick the records I want to display. But this has an additional problem that my cursor logic disappears. Which then kinda means I have 2 logical paths for solving paging. Which might be the ultimate solution, but I wonder if anyone smarter has a better idea.

Any ideas welcome.

Thanks,
Matyas