Further thoughts on BlitzDB’s Index Handling
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.
I think it is a right approch.
every PK gets a tail :) (index)
otherwise things like range scans will be too expensive.
If you look at other planets (say oracle) every primary key got an index..as they call “unique index”.
if it is named PK, index will have the same name. otherwise system generated name. obviously citizens are not allowed to drop this index.
Hi Toru!
“Perhaps Drizzle/MySQL provides an internal normalization function that respects this. I still need to study this area of the storage subsystem.”
Indeed, there is such a normalization routine :)
my_strcasecmp() is probably what you are looking for. Use it like so:
const char *key= “KEY”;
int found= my_strcasecmp(&my_charset_utf8_general_ci, “key”, key);
if (found)
printf(“found it.”);
You will probably have to also:
#include
#include
Cheers!
-jay
Sorry above should be:
int found= ! my_strcasecmp(…);
the function returns 0 on a match.
=-jay
@Jobin Augustine Thanks for the encouragement. I think I’ll try this approach and see how it goes.
@Jay Pipes As always, thanks for the awesome advises! This means a lot to me. I was talking to mtaylor last week and it seems MY_COLLATION_HANDLER object inside MY_CHARSET_INFO has lots of goodies inside it. I’ll look into these plus your advise and hopefully solve my problem :)