My MySQL table looks like this.

animal_id (mediumint) | dna_hash (binary 10)

Currently, we have about 2 billions different dna_hash and it will be increasing every day.

We need to search the animal by dna_hash. So, I have an index on dna_hash.

Currently, I'm starting to worry because after I imported around 20 million rows, my index on dna_hash is over 500MB. If I keep on adding, the final index size will be over 50GB which is very expensive to operate.

So, I just wondering if there are any other possible way to reduce the index size? Or, should I just upgrade my hardware.


  • @mustaccio, I'm not worried of storage. I just worried that 50GB RAM would be very expensive. I'm operating it on AWS and 50GB RAM machine on aws costs around $1/hr. So, do I need to have the same RAM size as index size?
    – moeseth
    Nov 6, 2015 at 4:23
  • not necessarily. It's always good if all the tables and indexes can fit into RAM but you can't always have that. You can still search with WHERE dna_hash = ?. If you moved from RDS to your own server, you could easily build a 64 or 128 or 256 GB RAM machine. You'll have different costs of course (building and administrating the hardware and OS). Nov 6, 2015 at 10:49
  • A MEDIUMINT can only contain 8,388,607 unique values (or ~2x that if unsigned) so, if you have 20M rows... what's defined as the primary key? Nov 6, 2015 at 12:03
  • 2
    @Michael-sqlbot - I don't think there'll be more than 8M animals - just more than 8M DNA samples - if I were the OP, I'd put a primary key on (animal, dna_hash) - unless you're likely to get the same sequence from the same animal - is this possible? Give us a SHOW CREATE TABLE My_Table\G and maybe we can give you some pointers. Tables should virtually always have a PK.
    – Vérace
    Nov 6, 2015 at 13:32
  • 1
    Note "using MRR" in the output of EXPLAIN. Disable that optimization. dev.mysql.com/doc/refman/5.6/en/mrr-optimization.html Nov 6, 2015 at 21:04

1 Answer 1


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

    hash BINARY(10) NOT NULL,
    PRIMARY KEY (hash),
    INDEX(animal_id)  -- might you need this for maintenance?

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.

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

  • good information. what do you think of using a binary file instead of mysql ?
    – moeseth
    Dec 4, 2015 at 17:59
  • How would you read the binary file? Performance is all about how often you have to hit the disk. Scanning a multi-GB file would take minutes, not seconds.
    – Rick James
    Dec 4, 2015 at 18:29
  • I could put the binary file in memory? My binary file will be 20GB large at maximum. So maybe I should just have a dedicated server with the file in memory. However, I think it wouldn't provide consistency and reliability like mysql. What do you think?
    – moeseth
    Dec 5, 2015 at 4:34
  • One machine with the binary file in memory; another with MySQL for persistence and for reloading the other machine. The MySQL machine can be relatively small, since RAM won't be useful for INSERTs. But... You can't easily add one new entry to the memory file. And reloading it may take an hour.
    – Rick James
    Dec 6, 2015 at 8:10
  • so, maybe i should use MySQL and nosql together
    – moeseth
    Dec 6, 2015 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.