Disclaimer: This post is based on HEAP/MyISAM’s sourcecode in Drizzle.

Here are my brief notes on investigating how index keys are generated in HEAP and MyISAM. I lurked through these because I’ve started preparing for decent index support in BlitzDB. I also wrote this to assist my biological memory for later grepping (I have terrible memory for names). I’m only going to cover key generation on write in this post. Otherwise this post is going to be massive.

HEAP Engine

The index structure of HEAP can be either BTREE or HASH (in MySQL doc terms). Like other engines HEAP has a structure for keeping Key definition (parts, type, logic and etc). This structure is called HP_KEYDEF and it contains function pointers for write, delete, and getting the length of the key. These function pointers are assigned to at table creation or when the table is opened. The assigned function depends on the data structure …

I have had a wish for a few years. I wanted to find a way to put together the valuable information that the community produces about MySQL, a way that would let me easily find the interesting content that I may have missed when on vacation, or when busy with a conference, a company meeting, or a long stream of coding.

That wish started to take shape last year, when I was traveling with Dups during the East Coast tour. I drove, he took notes. He drove, I took more notes. During meals and walking breaks we discussed and refined the idea. When we went back home, a plan was ready. Dups started coding in January.

At first, his changes were completely invisible. He was refactoring the Planet MySQL code to integrate it with the advanced features that had been developed for the main site. After a series of secondary changes, there came the substantial one. The voting …

I have had a wish for a few years. I wanted to find a way to put together the valuable information that the community produces about MySQL, a way that would let me easily find the interesting content that I may have missed when on vacation, or when busy with a conference, a company meeting, or a long stream of coding.

That wish started to take shape last year, when I was traveling with Dups during the East Coast tour. I drove, he took notes. He drove, I took more notes. During meals and walking breaks we discussed and refined the idea. When we went back home, a plan was ready. Dups started coding in January.

At first, his changes were completely invisible. He was refactoring the Planet MySQL code to integrate it with the advanced features that had been developed for the main site. After a series of secondary changes, there came the substantial one. The voting …

I have had a wish for a few years. I wanted to find a way to put together the valuable information that the community produces about MySQL, a way that would let me easily find the interesting content that I may have missed when on vacation, or when busy with a conference, a company meeting, or a long stream of coding.

That wish started to take shape last year, when I was traveling with Dups during the East Coast tour. I drove, he took notes. He drove, I took more notes. During meals and walking breaks we discussed and refined the idea. When we went back home, a plan was ready. Dups started coding in January.

At first, his changes were completely invisible. He was refactoring the Planet MySQL code to integrate it with the advanced features that had been developed for the main site. After a series of secondary changes, there came the substantial one. The voting …

Something I’ve added to BlitzDB recently that was pretty high on my todo list is support for variable width tables. So what is a variable width table? it is a table that contains columns that can vary in size, namely BLOB and TEXT types.

Going back to the basics, when a new row is to be written, a storage engine is given a pointer to the row data in MySQL format that it must somehow store for later lookup/retrieval. By meaning “somehow”, the storage engine is given the freedom to do whatever it likes with the row.

Writing a row for a fixed length table (a table with columns that are always the same size) is deadly easy. A storage engine can choose to not temper with the row and simply write or copy the data to it’s storage mechanism. This is because the storage engine is given a row that contains all the data. Rows for variable width tables …

I’ve decided to start a series of blog entries on not-so-obvious findings that I’ve found while working on my new project. By archiving the findings, I’m hoping that I can help those that are looking into developing a storage engine for the MySQL family in the future.

Accumulating these mini-knowledge would also be useful for me since I can refer back to it when I forget something. Also, once I write enough entries I’m planning on summarizing them and making it available on the Drizzle Wiki. If MySQL is interested in updating the engine documentation, I would be more than happy to help there too.

So to begin with, I’ll describe something trivial that I stumbled across while trying to catch an error on duplicate primary key insertion to the data table.

Lately I’ve been having lots of fun going through Drizzle and InnoDB‘s sourcecode to get a grasp of how auto increment is processed internally. I think I now have a fairly good grasp of what’s going on so I’m writing this entry as a note for myself. I’m also hoping that this will be helpful to those that are interested in this topic too.

So in MySQL and Drizzle, the storage engine (in this case InnoDB) is responsible for computing the auto increment value. Here’s an abbreviated execution path for a simple INSERT statement to a table with an auto increment column:

mysql_parse() -> mysql_execute_command() -> mysql_insert() ->
write_record() -> handler::ha_write_row() -> ha_innobase::write_row() ->
handler::update_auto_increment() -> ha_innobase::get_auto_increment()