3

Problem: I have a list of pairs (md5_hash, id). I want to store the data in MySQL and I want to make queries like this

SELECT id FROM table WHERE md5_hash = <some_hash>

The number of pairs can be tens or hundred of millions and the number is static - i.e., I do not add new records. It is important for me to save disk space. The time is not so important in this case (if a lookup takes less than say 1 second it is okey).

My thoughts:

I started by creating a table where md5_hash is represented in this way:

CREATE TABLE `myTable` (
   `md5` binary(16) NOT NULL, ' the values are not unique but we can suppose they are.
   `id` int(10) unsigned NOT NULL
) ENGINE=MyISAM

so md5 hashes are represented as binary numbers instead of hexadecimal characters to save space. For the same reasons the columns are defined as "NOT NULL". I chose MyISAM engine because my tests show that MyISAM requires less disk space than InnoDB. In addition MyISAM tables can be compressed by myisampack utility.

Now the hard part comes. When I create an index on md5 column the index requires more disk space than the data itself! I tested it with 17 millions records and my table took around 300 MB of disk space and the index took about 330 MB of disk space. The size of the index is crazy.

One idea is to provide the md5 hashes presorted to MySQL which should result in smaller index size. But I do not know how to do that.

Another idea is to divide myTable in several smaller tables in order to decrease size of the index. I tried mysql partitioning. However, the purpose of the feature is to improve query time and not disk space usage.

Do you have any idea how to decrease the required disk space usage?

Improve this question
2
  • Yes this is pretty common when you index an lookup table.. That the index will become larger than the data itself.. i assume that the md5 hashes are unique within your set? – Raymond Nijland Oct 5 '13 at 17:12
  • As I wrote in the question: we can assume that they are. – Martin Vseticka Oct 5 '13 at 20:27
3

Some options:

  • Use InnoDB. If not for these reasons, then for compression! With InnoDB you can:

    ALTER TABLE my_table ENGINE=InnoDB ROW_FORMAT=COMPRESSED KEY_BLOCK_SIZE=8;

    Replace 8 with 4 or 2 or 1 to (hopefully) get better compression. Since the table is static, I think this is a great solution for you (with strong compression, writes become slower, but you don't care about that).

    Not only data is compressed - indexes also. I would suggest this is the easiest option you have.

  • Only index part of your column. You agree that the column is not UNIQUE but can be assumed to be. OK; is your index a UNIQUE index? If not, try to:

    ALTER TABLE my_table ADD INDEX `md5_prefix_idx` (md5(8))

    to only index first 8 bytes of the columns.

  • Try TokuDB, which is an alternative storage engine to InnoDB, and which has an amazing compression (I've seen data get 20 times smaller than InnoDB with TokuDB aggressive compression).

Improve this answer
3
  • you could indeed use an prefix index to save some diskspace but maybe 8 is to small and still to many records still needs to be scannend by MySQL – Raymond Nijland Oct 5 '13 at 17:04
  • And read this dev.mysql.com/doc/refman/5.7/en/innodb-compression-usage.html documentation about COMPRESSED KEY_BLOCK_SIZE – Raymond Nijland Oct 5 '13 at 17:21
  • As Shlomi pointed out, TokuDB will far exceed the compression achieved using InnoDB's compression, use row_format=tokudb_lzma to achieve the maximum space savings. – tmcallaghan Oct 9 '13 at 11:15

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.