How to handle billions of rows in MySQL for biometric project?
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?
) ENGINE=InnoDB.


The 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.

Another note:  INSERTing into this table has similar caching considerations.  Each insert into the BTree starting with hash (whether 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,
        PRIMARY KEY(x)
    ) ENGINE=InnoDB;


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.)

Checking is SELECTing WHERE x=? and looking through y.

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.)