Мы используем Google App Engine с Datastore и Objectify. На нашем локальном компьютере запрос занимает 1 секунду, а в облаке - около 20 секунд. Расположение сервера находится на западе Европы, а я нахожусь в Испании, поэтому не думаю, что это проблема.
Запрос, который мы выполняем, просто извлекает данные с помощью всего одного фильтра:
final CityEntity cityEntity = new CityEntity();
cityEntity.setId(1);
ofy().load().type(Person.class).filter("city =", cityEntity).list();