I suppose that size of data store would be a bit too big for keeping in memory and I am not sure if the memory engine is available. It might be an idea to try InnoDB as that is supposed to work well with very large data stores. I think Google use it.
Maybe you could set up a test database. I think you would use ALTER to convert the tables to the new engine?
Is that database your address book?
Opinions are my own views, not DreamHosts’.
I am NOT a DreamHost employee OK!! :@
You act on my advice at your own risk!