Faster MySQL B-Tree performance

In our ongoing quest for low-cost, high-performance solutions for our platform I've run across TokuDB from TokuTek. This is a MySQL storage engine that uses a different indexing technology that makes updates to an index faster. Making index maintainence faster means being able to have more indices and that allows for richer queries and more interesting applications and analytics.

For one part of our system, I'm interested simply in faster inserts to the index. Having more indices for each table would help in other areas but I haven't started working on those yet. The table in question manages a many-to-one mapping of tokens (text) to internal database row IDs (integers). Essentially, it's a simple key/value lookup table. Currently a single machine does 150 inserts per second, which is fairly abysmal for a table with only 200M records.
This system uses MySQL and the InnoDB storage engine which uses a B-Tree indexing approach. Since the lookups are simply key/value lookups there really is no need for a B-Tree - a hash indexing scheme would work, but unfortunately InnoDB does not support that. We may migrate to Tokyo Tyrant and Tokyo Cabinet since that supports hash indexing and also seems to have better concurrency support (many non-blocking concurrent requests). The keys inserted are almost sequential, but from what I've read the sequential nature of the inserts should help (although the bottom-up building of a B-tree could be optimized by detecting that the key causing a page split is greater than all the values in the page being split - I think Oracle does this).

While looking for hash based indexing for MySQL I found TokuDB which uses the sexy phrase 'fractal tree' for their indexing. Their site has a few introductory whitepapers but a for deeper understanding I wanted to get to the theoretical foundation of their technology.

I soon found that there are several meanings to 'fractal tree' data indexing

• fpb+ tree. Fractal pre-fetching b+ trees, embeds cache-optimized trees within disk-optimized trees. Unrelated to TokuDB
• Fractal Trees (TM) from TokuTek. Uses 'cache oblivious' algorithms to improve B-tree usage.

One of their founders was kind enough to post some links on the mostly useful MySQL performance blog - here are the links (however, a few seem to be missing)

• http://supertech.csail.mit.edu/cacheObliviousBTree.html
• http://www.cs.sunysb.edu/~bender/pub/sicomp05-BenderDeFa.ps
• http://www.cs.sunysb.edu/~bender/pub/FOCS03-co-searching.ps
• http://www.cs.sunysb.edu/~bender/pub/locality-full.ps
• http://www.cs.sunysb.edu/~bender/pub/BenderHu-TODS07.pdf

The core algorithms seem to be for 'cache oblivious' b-tree structures, based on a description from a masters thesis from 1999. Maybe not all things 20th century suck (postscript files excluded).
Although I haven't finished reading all the papers, what I like about this approach is the way they model algorithm performance as the cost to transfer blocks of data between layers of storage and also that they consider multiple layers. The most important transfer costs being between disk and memory, but including considerations like an OS managed disk cache is good. This models the multi-layer caching that nearly all large scale systems use. We are big fans of measuring algorithm performance and selecting the right tool for the right job.

As an aside, one of the comments on the MySQL performance blog pointed me to InfoBright, a column-oriented store, which might be useful in some of our analytics systems for ad-hoc reporting.

MySQL and LAST_INSERT_ID()

We've recently migrated our software servers from a dedicated server environment (BlueGecko - really good people and service) to Amazon's EC2 'virtual compute cloud' environment.

The new system has a very nice performance monitoring capability based on Ganglia that gives us visibility into the performance of service requests as well as details on more fine-grained functions that take place within each request. We can now see not only the number of requests or functions but also the average duration and the time it took for 50%, 95% or 99% of the requests to complete in a five minute interval. This percentile breakdown gives a quick feel for how 'spiky' performance is and how common outliers are.

So far, things have gone very well but there was one function of the system that seemed to suddenly have terrible performance. I was able to quickly see which area of the code was involved, which pointed me to some SQL statements.

As our system adds new anonymous profiles, the code retrieves the unique number assigned by MySQL using the special query that MySQL provides:

SELECT LAST_INSERT_ID() AS user_id FROM oo_anon_user

However, it turns out that this SQL is actually incorrect - the extra "FROM oo_anon_user" caused the database to return every single record from the table back to the client, on every request that created a new record. This of course took some time.

The correct syntax to retrieve an auto-increment field from a MySQL table is

SELECT LAST_INSERT_ID() AS user_id

Remember to omit any FROM clause.

It's much much much faster now.