Toru Maesaka

I recently gained some decent momentum on developing the indexing component of BlitzDB. Most of my time spent on BlitzDB for the last couple of weeks have been studying the indexing API and digging into how other engines have implemented it. I even referred back to MySQL 4.x to see how the BDB engine pulls off the Indexing API.

The actual coding wasn’t too bad thanks to Tokyo Cabinet’s awesome B+Tree API. I’ve been busier adding new tests and fixing silly bugs as they arise. I also implemented the Primary Key optimization that I blogged about a while back. As a result of all this, the following goodness has been added to BlitzDB’s Trunk.

• Index Lookup
• Forward Index Scan
• Reverse Index Scan

This means that BlitzDB is now equipped with both a Table Scanner and an Index Scanner which are two essential components for a general purpose storage engine. As much as I’d like to work on optimizing the code and adding features (like recovery), I’m going to take a break and spend the rest of the month working on testing and debugging. There’s no point in adding features if the base has notable flaws in it.

Challenges Encountered

Writing the Index Scanner itself is easy. The most difficult thing that slowed me down was developing the comparison function for index keys. The end result was a simple piece of code but I had to study various things before I could start writing any code.

• How to respect collation
• How keys are represented internally
• How types are represented internally
• How to write a custom comparison function for Tokyo Cabinet
• … and so on

I’ve also started using Evernote to jot down my spontaneous ideas on optimizing BlitzDB. I’ve made these notes public and they will most likely be updated while I’m commuting on the train.

• http://www.evernote.com/pub/tmaesaka/blitzdb/

There are much more that I’d like to write about like how I intend on developing the table recovery routine without simply using TC’s recovery mechanism but I shall restrain myself for another day.

Toru Maesaka drizzle, oss blitzdb, drizzle, index

I’ve been thinking quite a bit about collation handling in BlitzDB for the last couple of days. The more I think about it, the more stuck I’ve been getting with BlitzDB’s index design. I’m actually so frustrated with myself at the moment that I want to hit my head against a wall or something.

So, I’m writing this entry to clear up my mind. Heh, my blog is slowly becoming BlitzDB’s design document draft. This should hopefully be good though since by blogging it, people can tell me whether I’m moving towards a stupid direction or not.

Collation Importance

When writing database software that is intended for International use, it is important to handle textual data by respecting collation order. It is arguable that most people are only interested in English lexicographic ordering but unfortunately the world is not so standard.

Internal Primary Key Handling

I want to motivate people to actively define a PRIMARY KEY with BlitzDB. I plan to make this attractive by providing the best performance when PK is defined. In December 2009, my answer to this was to write the PK value as the key for the data dictionary (where actual rows are stored in BlitzDB). This allows BlitzDB to do a direct lookup on the data dictionary for PK based lookup, instead of consulting the B+Tree index. I’m still fond of this lookup optimization approach but it introduces problems too.

Problem 1. Consider the following textual keys: “key” and “KEY”. They obviously have different binary representations but in certain cases they can be logically equivalent. Because the data dictionary is a hash database, this is a problem. The solution that instantly pops up is to normalize the key before writing or reading it. This however, causes a problem in cases where the two keys are inequivalent. Perhaps Drizzle/MySQL provides an internal normalization function that respects this. I still need to study this area of the storage subsystem.

Problem 2. Directly writing a PK to the data dictionary means fast lookup but because of the data structure, it’s not possible to fetch the next “logical” key, meaning I can’t implement index scanning on PK as it is. Quick solution for users is to create an index on the PK column (this would create a separate B+Tree for it) but this is not so friendly because it requires the user to have prior knowledge of all this. So, my plan is to provide the best of both worlds. I’ll elaborate on how I’m planning on tackling this problem next.

Current Primary Key Read/Write Behavior

In general, keys of BlitzDB’s data dictionary is a unique 8 byte integer. The idea is that BlitzDB writes this unique ID along with the key to the B+Tree Index so that it can later identify that row. The difference with PK is that, if a PK is present in a table, BlitzDB will not generate an internal unique ID and use PK for the data dictionary’s key instead. BlitzDB won’t create a B+Tree index for PK at the time I wrote this blog entry.

Next Step

Create a B+Tree index for PK anyway. BlitzDB will still use the PK value as the key for data dictionary if it exists. For PK based lookup requests, BlitzDB will look directly at the data dictionary and for PK based requests that involve index scanning, BlitzDB will look at the B+Tree index.

This approach can consume more space when textual data is used for keys but I think it’s worth it. At the same time, you can save space if you use use types that are smaller than 8 bytes for PK. For example, using a 4 byte integer would reduce BlitzDB’s key space by 50%.

Hmm, I think my mind has cleared a little.

Toru Maesaka drizzle, oss blitzdb, index

Previously you couldn’t create a table without defining a primary key with BlitzDB. This actually sounds like a nice constraint since you should always define a primary key. However, I went ahead and made this possible since one of the reasons that I’m developing BlitzDB is to get a better understanding of how the MySQL/Drizzle storage subsystem works. So, implementing a hidden key-generator and using it internally was something I wanted to do for sometime.

Previously this is what you got if you tried to create a table without a primary key:

drizzle> create table t1 (col1 int, col2 int, col3 text) engine=blitz;
ERROR 1173 (42000): This table type requires a primary key

Now:

drizzle> create table t1 (col1 int, col2 int, col3 text) engine=blitz;
Query OK, 0 rows affected (0 sec)

Inserting rows work as you would expect:

drizzle> insert into t1 values (1, 1, "first row");
Query OK, 1 row affected (0 sec)
 
drizzle> insert into t1 values (1, 2, "second row");
Query OK, 1 row affected (0 sec)
 
drizzle> insert into t1 values (1, 3, "third row");
Query OK, 1 row affected (0 sec)
 
drizzle> insert into t1 values (2, 1, "fourth row");
Query OK, 1 row affected (0 sec)
 
drizzle> insert into t1 values (2, 2, "fifth row");
Query OK, 1 row affected (0 sec)
 
drizzle> insert into t1 values (2, 3, "sixth row");
Query OK, 1 row affected (0 sec)

Selecting rows works fine although since there isn’t a key column in this table, every operation would require a full table scan which is not sexy:

drizzle> select * from t1;
+------+------+------------+
| col1 | col2 | col3       |
+------+------+------------+
|    1 |    1 | first row  | 
|    1 |    2 | second row | 
|    1 |    3 | third row  | 
|    2 |    1 | fourth row | 
|    2 |    2 | fifth row  | 
|    2 |    3 | sixth row  | 
+------+------+------------+
 
drizzle> select * from t1 where col1 = 1;
+------+------+------------+
| col1 | col2 | col3       |
+------+------+------------+
|    1 |    1 | first row  | 
|    1 |    2 | second row | 
|    1 |    3 | third row  | 
+------+------+------------+
3 rows in set (0 sec)
 
drizzle> select * from t1 where col2 = 2;
+------+------+------------+
| col1 | col2 | col3       |
+------+------+------------+
|    1 |    2 | second row | 
|    2 |    2 | fifth row  | 
+------+------+------------+
2 rows in set (0 sec)

How the internal works

BlitzDB does what most people would assume. It atomically generates a sequential unsigned 64bit integer then if necessary, converts it to big endian (network byte order). It then uses that value as a key to store the row into TC. The auto-generated key is made sure to be big-endian because I want BlitzDB tables to work on all platforms. That is, admins should be able to copy the “data files” over to another server and happily keep using the database. Keys are converted and _always_ used as little-endian inside BlitzDB.

Next Step

There’s still some bits and pieces on update related code that I need to work on but in general things are looking good. When I get those tasks done, I can then start working on supporting secondary index which I have cool ideas for.

Toru Maesaka drizzle, oss blitzdb, index