Why you are hosed
So, you need to map a 10-byte hash to a 3-byte id, correct? And there are 2B+ of them? Nothing else in the table? (Adding to the table increases the numbers below.)
CREATE TABLE HashToAnimal (
hash BINARY(10) NOT NULL,
animal_id MEDIUMINT UNSIGNED NOT NULL,
PRIMARY KEY (hash),
INDEX(animal_id) -- might you need this for maintenance?
hash is very random. So there are two extreme situations (and not much in between):
- The table lives in the buffer_pool. Accesses would not incur a disk hit (very fast). 2B rows would occupy about 100GB. This implies more than 100GB of RAM. (No it won't fit in 50GB; there are several flavors of overhead.)
- The buffer_pool is much too small to hold the table. Now, each
SELECT will need a disk hit because caching is 'impossible'. How many IOPS can you afford on Amazon? Pessimistically divide that by 3 to get how fast you might be able to fetch rows.
You quoted 1000 fetches took 10 seconds. That sounds like a cold cache and conventional drives. 100 disk hits per second is a good Rule of Thumb for conventional disks. (I thought Amazon was all SSD?) That 10 seconds will get faster as more of the table is cached -- if the buffer_pool is big. Eventually there won't be any disk hits and my "very fast" will come true.
INSERTing into this table has similar caching considerations. Each insert into the BTree starting with
PRIMARY KEY or secondary) is very random. It will be a disk hit if the table is much bigger than the buffer_pool; otherwise it will eventually be cached and fast.
Note: If Amazon does certain kinds of maintenance, the cache may suddenly become 'cold'.
Hashes, MD5s, GUIDs, UUIDs, etc. are all terrible to use. You have to pay for either lots of RAM or lots of IOPs.
Thinking out of the box
You usually expect not to get any animals, correct? So, the preferred test is one of 'existence', not 'fetch'? So a bit string of 2**80 bits would say which hashes have been seen. Well, this is really impractical.
Here's a schema that might take 5GB for a table that lets you test the existence of 2B different hashes:
Let x be the first 27 bits of the hash. Let y be the next 8 bits.
CREATE TABLE CheckHash (
x BINARY(3) NOT NULL,
y BLOB NOT NULL,
INSERTing is a bit complicated. Fetch the row for
x, see if
y is already in the
y column; if not add it. (If no
x row, add one.)
SELECTing WHERE x=? and looking through
There will be some "collisions", but that is OK.
There will be a small percentage of false hits (15%?); you then use the full hash to look them up in the
HashToAnimal. Assuming the percentage is small enough, these disk hits should be small enough to be acceptable.
The goal is to be able to have the smaller
CheckHash fully cached, but not worry that
HashToAnimal is not well cached.
This table will grow gradually; 4B hashes may take only 8GB.
(If you get beyond, say, 5B hashes, you should rebuild the table with 28 instead of 27. It's a tradeoff between space overhead versus more CPU time for scanning the blob.)
(Surely there are other techniques.)