Look at your current solution and check the run plan of your sql. If your data is indexed correctly it shouldn't be too too bad to execute queries. 1M records is about 20 ops to search for a record by key.

If it's modelled in SQL, it's probably relational and normalized so you'll be joining together tables. This balloons the complexity of querying the data pretty fast. Denormalizing data simplifies the problem so see if you can get it into a K/V instead of or relational database. Not saying relational isn't a fine solution - even if you keep it in mysql, denormalizing will benefit the complexity of querying it.

Once you determine if you can denormalize, you can look at sharding the data so instead of having the data in one place, you have it in many places and the key of the record determines where to store and retrieve the data. Now you have the ability to scale your data horizontally across instances to divide the problem's complexity by n where n is the number of nodes.

Unfortunately the network is not reliable so you suddenly have to worry about CAP theorem and what happens when nodes become unavailable so you'll start looking at replication and consistency across nodes and need to figure out with your problem domain what you can tolerate. Eg bank accounts have different consistency requirements than social media data where a stale read isn't a big deal.

Aphyr's Call Me Maybe series has reviews of many datastores in pathological conditions so read about your choice there before you go all in (assuming you do want to look at different stores.) Dynamo style DB's like riak are what I think of immediately but read around - this guy is a wizard. https://aphyr.com/tags/Jepsen

AWS has a notorious network so really think about those failure scenarios. Yes it's hard and the network isn't reliable. Dynamo DBs are cool though and fit the big problems you're looking at if you want to load and query it.

If you want to work with the data, the Apache Spark is worth looking at. You mention mapreduce for instance. Spark is quick.

It's sort of hard because there isn't a lot of information about the problem domain so I can only shoot in the dark. If you have strong consistency needs or need to worry more about concurrent state across data that's a different problem than processing one record at a time without a need for consistent view of the data as a whole. The latter you can just process the data via workers.

But think Sharding to divide the problem across nodes, Denormalization eg via Key/Value lookup for simple runtime complexity. But start where you are - look at your database and make sure it's very well tuned for the queries you're making.

Do you even need to load it into a db? You could distribute the load across clusters of workers if you have some source that you can stream the data from. Then you don't have to load and then query the data. Depends heavily on your domain problem. Good luck. I can email you to discuss if you want - I just don't want to post my email here. Data isn't so much where I hand out as much as processing lots of things concurrently in distributed systems is so others may have better ideas who have gone through similar items.

There are some cool papers like the Amazon Dynamo paper and I read the Google Spanner paper the other day (more globally oriented and around locking and consistency items). You can see how some of the big companies are formalizing thinking by reading some of the papers in that space. Then there are implementations you can actually use but you need to understand them a bit first I think.

http://www.allthingsdistributed.com/files/amazon-dynamo-sosp...
http://static.googleusercontent.com/media/research.google.co...