MySQL Index Creation Internals

Question

Right now there are two ways to build an index of a table in MySQL:

1. Create the table structure first, then import the data and add indexes later.
2. Create the table structure with indexes and then import the data.

In the first process we will have contiguous data (all fields) pages and then we have index pages. So when we query using index, MySQL has to first load the index pages and find out the matching keys and have to look up those primary key on the data pages. For this it has to then again load the data pages to get the data. This is useful when we have larger index scans as we have all index loaded contiguously.

In the second way of index creation the filtered index page will most probably contain the data page near to it as they were created at the same time. So I guess look up will be faster for a small range scans.

Is my understanding correct?

UPDATE:

I should have mentioned that the "PRIMARY KEY is enabled" (an auto increment id column) in the first way of importing data. So internal rowid is not generated and lot of IO is saved as we are not going to add a PRIMARY KEY.

As you noted there is fragmentation when we import data using the Second method.

Considering my requirements is for larger range scans (scanning ~100M rows) I guess I will go with the first way of importing data.

update on Jun 8 11:30

CREATE TABLE `table_dummy` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `column1` bigint(20) DEFAULT NULL,
  `column2` bigint(20) DEFAULT NULL,
  `column3` bigint(20) DEFAULT NULL,
  `created_at` datetime DEFAULT NULL,
  `column4` tinyint(1) DEFAULT NULL,
  `column5` tinyint(4) DEFAULT NULL,
  `column6` bigint(20) DEFAULT NULL,
  `column6_created_at` datetime DEFAULT NULL,
  `column7` int(11) DEFAULT NULL,
  `column8` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `twtaccount_id_2` (`column1`,`column2`),
  KEY `twtaccount_id` (`column1`,`created_at`,`column5`),
  KEY `twt_user_id` (`column3`,`created_at`,`column5`),
  KEY `original_status_id` (`column6`,`column3`,`followers_count`)
)

ENGINE is INNODB

this table has about 800M records and I took a dump and imported it in two ways.

Method 1: table was created with just the primary key and entire data was imported. Then I gave an alter statement to add the remaining indexes.

Method 2: The table was created with indexes and the dump was done. This took much larger time.

P.S The size of the resulting table through 'Method 1' was lesser by ~30GB when compared to size of table dumped through 'Method 2'. Method 1 took very less time than 'Method 2', almost twice the speed.

My primary concern is the performance of the table when I make a select scanning a wide range of index ('index only scan').

Answer 1

There are a few things I can clarify for you here:

• Yes, it is a good practice to delay secondary index creation until after you import the data (starting from MySQL 5.5 - not before). Mysqlpump does this by default.

• When you delay secondary index creation, internally MySQL will read, sort and then create the index (reducing fragmentation). For MySQL 5.7 there are additional optimizations here.

• When you trickle load indexes, they may have more page splits and a lower page fill efficiency (fragmentation). This depends a little on the data, and if it is in order. You are not giving me many clues with column1, column2, but say for example column1 was a timestamp it would probably be in order.

• Pages in an index are logically in order, not necessarily physically. This distinction may matter if you can not fit your working set for ranges in memory and are using spinning disks for backing storage. It's also a little hard to answer because with spinning disks you are probably using RAID with some stripe size, and the blocks at the filesystem level may also be non-contiguous.

• Be aware also that the optimizer may not consider the range scan for large ranges over a tablescan (since prior to 5.7 the cost model assumed pages were not in memory). If you can rely on this being the case, you may want to FORCE INDEX and compare actual run times. (More info on new cost model.)

Answer 2

In the first way, you are sort-of correct. Here is why I say soft-of.

InnoDB has a Clustered Index, known internally as gen_clust_index.Basically, it is a rowid index that is created for the InnoDB table under-the-hood (or if you are from Jersey City, NJ like me, created in-the-hood). These rowids are attached to all secondary indexes.

Creating a PRIMARY KEY after the fact could result in a larger amount of space for the PRIMARY KEY if the width of the columns making up the PRIMARY KEY is wider than the rowid.

For InnoDB, the second method for index creation would make more sense because you are not swapping the PRIMARY KEY's definition under-the-hood. This is in addition to the benefit you already mentioned (data page near to it as they were created at the same time). There is nothing to gain for the first indexing method in this respect, breaking even at best.

Although the second method is better suited for needs (look up will be faster for a small range scans) I have a very strong caveat for you: If you fill the PRIMARY KEY with column data already sorted, you may very well end up with some index fragmentation (See my answer to the Oct 26, 2012 post How badly does innodb fragment in the face of somewhat out-of-order insertions?) Not a bad tradeoff if you know you are doing small range scans.

UPDATE 2015-05-26 16:30 EST

In that instance, the same caveat applies. You will have a fragmented PRIMARY KEY. The proof of that was expressed in my answer to the May 01, 2014 post Why would the size of MySQL MyISAM table indexes (aka MYI file) not match after mysqldump import?

To prove it by hand do the following

Step 01 : mysqldump data from a DB Server

Step 02 : load it into a test server

Run the query

SELECT IFNULL(ENGINE,'Total') "Storage Engine",
LPAD(CONCAT(FORMAT(DAT/POWER(1024,pw1),2),' ',
SUBSTR(units,pw1*2+1,2)),17,' ') "Data Size",
LPAD(CONCAT(FORMAT(NDX/POWER(1024,pw2),2),' ',
SUBSTR(units,pw2*2+1,2)),17,' ') "Index Size",
LPAD(CONCAT(FORMAT(TBL/POWER(1024,pw3),2),' ',
SUBSTR(units,pw3*2+1,2)),17,' ') "Total Size" FROM
(SELECT ENGINE,DAT,NDX,TBL,IF(px>4,4,px) pw1,
IF(py>4,4,py) pw2,IF(pz>4,4,pz) pw3 FROM
(SELECT *,FLOOR(LOG(IF(DAT=0,1,DAT))/LOG(1024)) px,
FLOOR(LOG(IF(NDX=0,1,NDX))/LOG(1024)) py,
FLOOR(LOG(IF(TBL=0,1,TBL))/LOG(1024)) pz
FROM (SELECT ENGINE,SUM(data_length) DAT,SUM(index_length) NDX,
SUM(data_length+index_length) TBL FROM (SELECT engine,data_length,index_length
FROM information_schema.tables WHERE table_schema NOT IN
('information_schema','performance_schema','mysql') AND ENGINE IS NOT NULL) AAA
GROUP BY ENGINE WITH ROLLUP) AAA ) AA) A,(SELECT ' BKBMBGBTB' units) B;

Step 04 : mysqldump from the test server

Step 05 : reload the dump from the test server back into the test server again

Step 06 : run the query from Step 03

Sometimes, large sets of data will produce different sizes when mysql data is reloaded

BOTTOM LINE : Neither method had a significant advantage over the other with InnoDB.

Answer 3

"Near" is not relevant. This is because of the caching of both data blocks and index blocks in the buffer_pool. The caching leads to writing/reading in orders that your logic does not account for.

Do not use the internal auto-generated PRIMARY KEY; always explicitly specify a PRIMARY KEY, even if you add the secondary keys later.

If your PRIMARY KEY is an AUTO_INCREMENT and is not provided by the data being loaded, then loading the data will be essentially "append only" -- very efficient. Each row goes into the "last" data block until it is nearly full, then a new block is started. (More in a moment about secondary keys.)

If your PRIMARY KEY is a 'natural' (one or more columns of the table) then it is very beneficial to sort the incoming data before loading it. Then, again, you get "append only".

A UNIQUE secondary key must be checked as each row is inserted. If the values of this column(s) is random, then the lookup could hit the disk, in which case it will be costly when that index becomes to big to be cached in the buffer_pool. Too bad. (More in a moment.)

A non-unique secondary key is (usually) best created after the fact. Create all such keys in a single ALTER TABLE tbl ADD INDEX(...), ADD INDEX(...), ...;

If you are creating AUTO_INCREMENT values (rather than loading them from elsewhere), then apply the "sort it first" trick to some secondary index, a UNIQUE one if such exists. This will efficiently build that index effectively "append only". And it avoids the caveat above about UNIQUE indexes.

OK, that gives you the most efficient way to load a large InnoDB table. But you asked about internals...

The "data" and the PRIMARY KEY coexist in the same BTree, with each "record" containing all the columns of the table. Each secondary key exists in a separate BTree, with each "record" consisting of the columns of the secondary key plus the columns of the primary key.

The BTrees are composed of 16KB blocks. Or of 1MB "extents" which contain 16KB blocks. The existence of "extents" is to try to achieve "nearness" of blocks. But that is somewhat foolish because the OS won't necessarily give MySQL a contiguous 1MB when it asks for an extent.

There's another wrinkle... If you have TEXT or BLOB columns, they may (depending on size and ROW_FORMAT) be stored elsewhere.

On, another wrinkle... If you use COMPRESSED, things get even more complex.

If you would like to show us your SHOW CREATE TABLE, we might have more tips.

Edit (after OP's edits)

Method 1 (add secondary indexes after loading the table) was clearly better (faster and smaller). I suspected this, but do not have convincing evidence that it is always 'better'.

Method 1 wrote out all the data for each index, sorted it, then built the BTree from the sorted list. This lead to less fragmentation and no jumping around to insert the 'rows' into the index.

Method 2 randomly inserted 'rows' into the index one at a time. The cache (buffer_pool) prevented most I/O, so it was not terribly slow. However, the blocks in the BTree probably had to be split many times, and most ended up partially full. (Theoretical average of 69% full.)

The number of "levels" of the BTree is likely to be the same in either approach. A million-row index needs about 3 levels of BTree. Each factor of 100 leads to another level.

Since Method 1 lead to fewer index blocks, it is more cacheable. This will turn out to be only a minor difference.

A "point query" (SELECT ... WHERE primary_key = constant) needs to drill down the levels of the data (which is structured based on the PRIMARY KEY) to find the bottom node. Normally all the levels, except possibly the bottom level, will be cached in RAM, so I/O is not an issue. The two methods probably hit the same number of blocks, cached or not.

A point query using a secondary index will drill down the BTree of the secondary index, find the primary key, then drill down the data BTree. Again, the methods are likely to have similar performance.

An "index scan" is, for example SELECT ... WHERE secondary_key BETWEEN 1000 AND 2000. This is implemented by drilling down the BTree to find 1000, then scanning forward until hitting 2000. This will (on average) hit about 10 blocks -- a few less for Method 1; a few more for Method 2. So now we have found a potentially noticeable performance difference, especially if the ~10 blocks are not all cached.

Is this difference enough to matter? If you never insert more rows, maybe it is worth something. However, INSERTing for Method 1 will very soon lead to block splits, thereby making the performance closer to Method 2. Method 2 will not do block splits as quickly because the blocks tend to have more spare room.

As you see, I cannot talk about SELECT without some understanding of INSERT.

Bottom line: Go with method 1 for loading (not "dumping").