MySQL Hardware Bottleneck I have a web application that makes simple queries to a MySQL database. The database is quite large (8.4GB) and the time to lookup an entry needs to be as fast as possible. 

The database represents a graph theory problem and I'm running a shortest path algorithm that queries it possibly millions of times to find a path. I'm looking at server options to host my app. I expect very light traffic to the site. (Database is well indexed and optimized.)

I know that an SSD server is a must. (Average time with SSD 10-20 seconds on Dell laptop clocked at 1.6Ghz Intel i5, compared to several minute wait on HDD with same hardware)

I consider a 10-20 second wait acceptable and want to ensure that the server can achieve similar results.

My question:

What kinds of CPU speeds/cores should I be looking at? What is the processor clock/cores that will ensure that the SSD is the bottleneck.

I expect that this is varies depending on the nature of the program. If so, how might I go about testing speeds at different clocks, considering I have only one PC?
MyISAM or InnoDB?  Depending on which, you need to see the appropriate cache buffer.  If you had 16GB of RAM, you could set that so that the table will (eventually) be entirely in RAM.  That would move it from being I/O bound (as it probably is now) to being CPU bound.  At that point, an old, slow, cheap, spinning drive will be almost as good as SSDs.

Can you parallelize the algorithm?  If so, split it into as many programs (connections) as you have cores.  That will (assuming CPU-bound) give you a nice speed-up.

Let's see the main query.  And the SHOW CREATE TABLE for any table(s) involved.  There may be simple ways to speed it up.

(I estimate that a table of 8.4GB is about the 96th percentile.)