How to best store Google ngrams in a database?

Question

I downloaded google onegrams some days ago and it’s already a huge amount of data. I inserted the first of 10 packages into mysql and now I have a 47 million record database.

I am wondering how one should store Google ngrams in a database best. I mean, if you are not using onegrams, but e.g. twograms or threegrams the amount will be much larger. Can I store 500 million records in one database and work with it or should I split it to different tables?

After how many records should one split it and how should one split it best (considering that twograms has 100 files and thus probably about 5 billion records)? Is it recommended to use MySQL horizontal partitioning or rather build one’s own partitioning (e.g. via first character of word => twograms_a).

Answer 1

There were so many changes I would have to make to my first answer I start this one !!!

USE test
DROP TABLE IF EXISTS ngram_key;
DROP TABLE IF EXISTS ngram_rec;
DROP TABLE IF EXISTS ngram_blk;
CREATE TABLE ngram_key
(
    NGRAM_ID UNSIGNED BIGINT NOT NULL AUTO_INCREMENT,
    NGRAM VARCHAR(64) NOT NULL,
    PRIMARY KEY (NGRAM),
    KEY (NGRAM_ID)
) ENGINE=MyISAM ROW_FORMAT=FIXED PARTITION BY KEY(NGRAM) PARTITIONS 256;
CREATE TABLE ngram_rec
(
    NGRAM_ID UNSIGNED BIGINT NOT NULL,
    YR SMALLINT NOT NULL,
    MC SMALLINT NOT NULL,
    PC SMALLINT NOT NULL,
    VC SMALLINT NOT NULL,
    PRIMARY KEY (NGRAM_ID,YR)
) ENGINE=MyISAM ROW_FORMAT=FIXED;
CREATE TABLE ngram_blk
(
    NGRAM VARCHAR(64) NOT NULL,
    YR SMALLINT NOT NULL,
    MC SMALLINT NOT NULL,
    PC SMALLINT NOT NULL,
    VC SMALLINT NOT NULL
) ENGINE=BLACKHOLE;
DELIMITER $$
CREATE TRIGGER populate_ngram AFTER INSERT ON ngram_blk FOR EACH ROW
BEGIN
    DECLARE NEW_ID BIGINT;

    INSERT IGNORE INTO ngram_key (NGRAM) VALUES (NEW.NGRAM);
    SELECT NGRAM_ID INTO NEW_ID FROM ngram_key WHERE NGRAM=NEW.NGRAM;
    INSERT IGNORE INTO ngram_rec VALUES (NEW_ID,NEW.YR,NEW.MC,NEW.PC,NEW.VC);
END; $$
DELIMITER ;
INSERT INTO ngram_blk VALUES
('rolando',1965,31,29,85),
('pamela',1971,33,21,86),
('dominique',1996,30,18,87),
('diamond',1998,13,28,88),
('rolando edwards',1965,31,29,85),
('pamela edwards',1971,33,21,86),
('dominique edwards',1996,30,18,87),
('diamond edwards',1998,13,28,88),
('rolando angel edwards',1965,31,29,85),
('pamela claricia edwards',1971,33,21,86),
('dominique sharlisee edwards',1996,30,18,87),
('diamond ashley edwards',1998,13,28,88);
UPDATE ngram_rec SET yr=yr+1,mc=mc+30,pc=pc+30,vc=vc+30;
INSERT INTO ngram_blk VALUES
('rolando',1965,31,29,85),
('pamela',1971,33,21,86),
('dominique',1996,30,18,87),
('diamond',1998,13,28,88),
('rolando edwards',1965,31,29,85),
('pamela edwards',1971,33,21,86),
('dominique edwards',1996,30,18,87),
('diamond edwards',1998,13,28,88),
('rolando angel edwards',1965,31,29,85),
('pamela claricia edwards',1971,33,21,86),
('dominique sharlisee edwards',1996,30,18,87),
('diamond ashley edwards',1998,13,28,88);
UPDATE ngram_rec SET yr=yr+1,mc=mc+30,pc=pc+30;
INSERT INTO ngram_blk VALUES
('rolando',1965,31,29,85),
('pamela',1971,33,21,86),
('dominique',1996,30,18,87),
('diamond',1998,13,28,88),
('rolando edwards',1965,31,29,85),
('pamela edwards',1971,33,21,86),
('dominique edwards',1996,30,18,87),
('diamond edwards',1998,13,28,88),
('rolando angel edwards',1965,31,29,85),
('pamela claricia edwards',1971,33,21,86),
('dominique sharlisee edwards',1996,30,18,87),
('diamond ashley edwards',1998,13,28,88);
UPDATE ngram_rec SET yr=yr+1,mc=mc+30;
SELECT * FROM ngram_key;
SELECT * FROM ngram_rec;
SELECT A.ngram NGram,B.yr Year,B.mc Matches,B.pc Pages,B.vc Volumes FROM 
ngram_key A,ngram_rec B
WHERE A.ngram='rolando angel edwards'
AND A.ngram_id=B.ngram_id;

Much smaller tables for year info but much bigger keys to preserve the original ngram. I also increased the amount of test data. You can cut and paste this directly into MySQL.

CAVEAT

Simply remove ROW_FORMAT and it becomes dymanic and compress the ngram_key tables a lot smaller.

---

DiskSpace Metrics

nrgram_rec has 17 bytes per row
8 bytes for ngram_id (max unsigned value 18446744073709551615 [2^64 - 1])
8 bytes for 4 smallints (2 bytes each)
1 byte MyISAM internal delete flag

Index Entry for ngram_rec = 10 bytes (8 (ngram_id) + 2 (yr))

47 million rows X 17 bytes per row = 0799 million bytes = 761.98577 MB
47 million rows X 12 bytes per row = 0564 million bytes = 537.85231 MB
47 million rows X 29 bytes per row = 1363 million bytes = 1.269393 GB

5 billion rows X 17 bytes per row = 085 billion bytes = 079.1624 GB
5 billion rows X 12 bytes per row = 060 billion bytes = 055.8793 GB
5 billion rows X 29 bytes per row = 145 billion bytes = 135.0417 GB

---

ngram_key has 73 bytes 64 bytes for ngram (ROW_FORMAT=FIXED set varchar to char) 8 bytes for ngram_id 1 byte MyISAM internal delete flag

2 Index Entries for ngram_key = 64 bytes + 8 bytes = 72 bytes

47 million rows X 073 bytes per row = 3431 million bytes = 3.1954 GB
47 million rows X 072 bytes per row = 3384 million bytes = 3.1515 GB
47 million rows X 145 bytes per row = 6815 million bytes = 6.3469 GB

5 billion rows X 073 bytes per row = 365 billion bytes = 339.9327 GB
5 billion rows X 072 bytes per row = 360 billion bytes = 335.2761 GB
5 billion rows X 145 bytes per row = 725 billion bytes = 675.2088 GB

Answer 2

Here is a pretty wild suggestion

Convert all ngrams to 32-character MD5 keys

This table will hold all ngrams of any size (up to 255 characters), 1-gram, 2-gram, etc.

use test
DROP TABLE ngram_node;
DROP TABLE ngram_blackhole;
CREATE TABLE ngram_node
(
  NGRAM_KEY  CHAR(32) NOT NULL,
  NGRAM_YEAR SMALLINT NOT NULL,
  M_COUNT    SMALLINT NOT NULL,
  P_COUNT    SMALLINT NOT NULL,
  V_COUNT    SMALLINT NOT NULL,
  PRIMARY KEY   (NGRAM_KEY,NGRAM_YEAR)
) ENGINE=MyISAM
PARTITION BY KEY(NGRAM_KEY)
PARTITIONS 256;
CREATE TABLE ngram_blackhole
(
  NGRAM      VARCHAR(255) NOT NULL,
  NGRAM_YEAR SMALLINT NOT NULL,
  M_COUNT    SMALLINT NOT NULL,
  P_COUNT    SMALLINT NOT NULL,
  V_COUNT    SMALLINT NOT NULL
) ENGINE=BLACKHOLE;
DELIMITER $$
CREATE TRIGGER populate_ngram AFTER INSERT ON ngram_blackhole FOR EACH ROW
BEGIN
    INSERT INTO ngram_node VALUES (MD5(NEW.NGRAM),NEW.NGRAM_YEAR,NEW.M_COUNT,NEW.P_COUNT,NEW.V_COUNT);
END; $$
DELIMITER ;
INSERT INTO ngram_blackhole VALUES
('rolando',1965,31,29,85),
('pamela',1971,33,21,86),
('dominique',1996,30,18,87),
('diamond',1998,13,28,88),
('rolando edwards',1965,31,29,85),
('pamela edwards',1971,33,21,86),
('dominique edwards',1996,30,18,87),
('diamond edwards',1998,13,28,88),
('rolando angel edwards',1965,31,29,85),
('pamela claricia edwards',1971,33,21,86),
('dominique sharlisee edwards',1996,30,18,87),
('diamond ashley edwards',1998,13,28,88);
SELECT * FROM ngram_node;

The reason I chose 256 partitions stems from the fact that the MD5 function returns 16 distinct characters (all hexadecimal digits). First two bytes is 16 X 16, 256.

Here were the result in MySQL 5.5.11 on my Windows 7 Desktop

mysql> use test
Database changed
mysql> DROP TABLE ngram_node;
Query OK, 0 rows affected (0.22 sec)

mysql> DROP TABLE ngram_blackhole;
Query OK, 0 rows affected (0.11 sec)

mysql> CREATE TABLE ngram_node
    -> (
    ->   NGRAM_KEY  CHAR(32) NOT NULL,
    ->   NGRAM_YEAR SMALLINT NOT NULL,
    ->   M_COUNT    SMALLINT NOT NULL,
    ->   P_COUNT    SMALLINT NOT NULL,
    ->   V_COUNT    SMALLINT NOT NULL,
    ->   PRIMARY KEY    (NGRAM_KEY,NGRAM_YEAR)
    -> ) ENGINE=MyISAM
    -> PARTITION BY KEY(NGRAM_KEY)
    -> PARTITIONS 256;
Query OK, 0 rows affected (0.36 sec)

mysql> CREATE TABLE ngram_blackhole
    -> (
    ->   NGRAM      VARCHAR(255) NOT NULL,
    ->   NGRAM_YEAR SMALLINT NOT NULL,
    ->   M_COUNT    SMALLINT NOT NULL,
    ->   P_COUNT    SMALLINT NOT NULL,
    ->   V_COUNT    SMALLINT NOT NULL
    -> ) ENGINE=BLACKHOLE;
Query OK, 0 rows affected (0.11 sec)

mysql> DELIMITER $$
mysql> CREATE TRIGGER populate_ngram AFTER INSERT ON ngram_blackhole FOR EACH ROW
    -> BEGIN
    ->  INSERT INTO ngram_node VALUES (MD5(NEW.NGRAM),NEW.NGRAM_YEAR,NEW.M_COUNT,NEW.P_COUNT,NEW.V_COUNT);
    -> END; $$
Query OK, 0 rows affected (0.05 sec)

mysql> DELIMITER ;
mysql> INSERT INTO ngram_blackhole VALUES
    -> ('rolando',1965,31,29,85),
    -> ('pamela',1971,33,21,86),
    -> ('dominique',1996,30,18,87),
    -> ('diamond',1998,13,28,88),
    -> ('rolando edwards',1965,31,29,85),
    -> ('pamela edwards',1971,33,21,86),
    -> ('dominique edwards',1996,30,18,87),
    -> ('diamond edwards',1998,13,28,88),
    -> ('rolando angel edwards',1965,31,29,85),
    -> ('pamela claricia edwards',1971,33,21,86),
    -> ('dominique sharlisee edwards',1996,30,18,87),
    -> ('diamond ashley edwards',1998,13,28,88);
Query OK, 12 rows affected (0.18 sec)
Records: 12  Duplicates: 0  Warnings: 0

mysql> SELECT * FROM ngram_node;
+----------------------------------+------------+---------+---------+---------+
| NGRAM_KEY                        | NGRAM_YEAR | M_COUNT | P_COUNT | V_COUNT |
+----------------------------------+------------+---------+---------+---------+
| 2ca237192aaac3b3a20ce0649351b395 |       1996 |      30 |      18 |      87 |
| 6f7fd3368170c562604f62fb4e92056d |       1965 |      31 |      29 |      85 |
| fb201333fef377917be714dabd3776d9 |       1971 |      33 |      21 |      86 |
| 4f79e21800ed6e30be4d1cb597f910c6 |       1971 |      33 |      21 |      86 |
| 9068e0de9f3fd674d4fa7cbc626e5888 |       1998 |      13 |      28 |      88 |
| 8a18abe90f2612827dc3a215fd1905d3 |       1965 |      31 |      29 |      85 |
| be60b431a46fcc7bf5ee4f7712993e3b |       1996 |      30 |      18 |      87 |
| c8adc38aa00759488b1d759aa8f91725 |       1996 |      30 |      18 |      87 |
| e80d4ab77eb18a4ca350157fd487d7e2 |       1965 |      31 |      29 |      85 |
| 669ffc150d1f875819183addfc842cab |       1971 |      33 |      21 |      86 |
| b685323e9de65080f733b53b2305da6e |       1998 |      13 |      28 |      88 |
| 75c6f03161d020201000414cd1501f9f |       1998 |      13 |      28 |      88 |
+----------------------------------+------------+---------+---------+---------+
12 rows in set (0.00 sec)

mysql>

Please notice I loaded 1-grams, 2-grams, and 3-grams into the same table but you have no clue which MD5 belongs to the which ngram. Thus, all ngrams can retrofit into this one table. Just remember to insert into the ngram_blackhole table and the rest is done for you.

You must query the ngram_node table using the MD5() of the ngram no matter which ngram.

mysql> select * from ngram_node where ngram_key=MD5('rolando edwards');
+----------------------------------+------------+---------+---------+---------+
| NGRAM_KEY                        | NGRAM_YEAR | M_COUNT | P_COUNT | V_COUNT |
+----------------------------------+------------+---------+---------+---------+
| 6f7fd3368170c562604f62fb4e92056d |       1965 |      31 |      29 |      85 |
+----------------------------------+------------+---------+---------+---------+
1 row in set (0.05 sec)

If you wish to separate 1-grams, 2-grams, and 3-grams into separate repositories, just create another table, another blackhole table, and another trigger on the blackhole table to insert into the other table.

Also, if your ngrams are longer than 255 (if you are doing 7-grams or 8-grams) just increase the VARCHAR size of the NGRAM column in the ngram_blackhole table.

Give it a Try !!!

UPDATE

In the question, it was stated that 47 million rows was loaded into mysql. For my suggested table layout, please note the following:

ngram_node is 41 bytes per row: 32 for NGRAM_KEY
8 for the numbers (2 for each SMALLINT)
1 for the internal MyISAM DELETED flag

Each primary key index entry would be 34 bytes
32 for NGRAM_KEY
2 for NGRAM_YEAR

47 million rows X 41 bytes per row = 1.927 billion bytes, about 1.79466 GB.
47 million rows X 34 bytes per index entry = 1.598 billion bytes, about 1.48825 GB.
The MyISAM table consumption should be about a combined total of 3.28291 GB.

The question also mentioned loading 5 billion rows.

5 billion rows X 41 bytes per row = 205 billion bytes, about 190.9211 GB.
5 billion rows X 34 bytes per index entry = 170 billion bytes, about 158.3248 GB.
The MyISAM table consumption should be about a combined total of 349.2459 GB.

Please notice that the growth rate of the space used in the MyISAM table is linear because of the constant-sized primary key. You can now do some planning for disk space based on this.