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).

  • 3
    I question your 3 database connections assumption. I would expect sharding to be done at the database level, and be almost invisible to the application.
    – kiwiron
    Jan 15 at 7:57
  • I must agree with @kiwiron's comment. Sharding should be a feature you enable and configure on the database. If you are doing this in application code, then you are either not using the database correctly or using the wrong database. Jan 15 at 19:58
  • Or you have a need to push data to a reporting database, but those are typically used to aggregate data from multiple data sources, not to fix a misconfigured database. Jan 15 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.