The fastest option would be in-memory caching on the local system. That won't scale well to many millions of relations, but will be very fast and work well for small data sets.
I haven't done performance testing between Memcached/MySQL HEAP, but I'd guess Memcached would be faster because it doesn't have the overhead of a full relational DB engine. Memcached would almost certainly scale better, because you could distribute it between servers and have a round-robin request dispatch between them.
If you need to perform any filtering on the data before retrieving it, you should use MySQL. The performance overhead of transmitting unwanted data will probably outweigh the benefits of faster lookups.
If I were you, I'd load the data set in question into MySQL and Memcached, then run performance tests to see which is better for your data set. If there's a core of data that's accessed particularly often, consider an additional machine-local cache.