Say you have a table of users with their email, sharded into 3 chunks. Literally, there are 3 database connections, where the databases are physically on different machines (though, within the same general geographic region, like considering AWS).
Say the records are sharded by hashing the string and bucketing them into 3 buckets. They are inserted as people sign up, so there is no real default sorted order to the email addresses (i.e. they aren't inserted into the database in sorted email order). How would you select 100 emails, at page 1000, where they are sorted by email alphabetically? Assuming you don't have some sort of cursor yet, we are making a fresh query like equivalent to a SQL query: SELECT email FROM users SORT BY email LIMIT 100 OFFSET 100000. Obviously I don't think you can do that SQL query directly, so how would you do this, given you would have to check all 3 shards.
Also, no cheating, like saying "well MySQL supports cross-shard searching/sorting, so just use MySQL", or anything like that (I don't know if it does, just making this up). I am talking about how this is implemented, I would like to know at a high level the strategy a database engine would typically use or how a cutting edge database might implement such a thing (at a high level). I am going to be trying to implement sharding to learn how it works, and I can't imagine yet how to solve the problem of querying over many shards where the records have no initial sort order relative to the query.
You can really just focus on this one situation described above. You don't need to provide a robust answer on how to handle every type of query and edge case. Just a high level description of how to solve this specific problem. If you make any other assumptions about the data, or know how to structure the data in such a way to more efficiently solve the problem (as long as it doesn't mean, store the data in sorted order ;) ), that is fine as well, just let me know. For now, it's just a simple user table with email column (varchar or something).