Kickfire: relational algebra in a chip
Posted in Databases on Apr 14, 2008
I spent the day Thursday with some of Kickfire’s engineers at their headquarters. In this article, I’d like to go over a little of the system’s architecture and some other details.
Everything in quotation marks in this article is a quote. (I don’t use quotes when I’m glossing over a technical point – at least, not in this article.)
Even though I saw one of Kickfire’s engineers running queries on the system, they didn’t let me actually take the keyboard and type into it myself. So everything I’m writing here is still second-hand knowledge. It’s an unreleased product that’s in very rapid development, so this is understandable.
Kickfire’s TPC-H benchmarks are now published, so you can see the results of what I’ve been seeing them work on. They are now #1 in the world, in two categories. Visit them at their booth in the exhibition area at the conference, and you will be able to see more for yourself.
At a high level, Kickfire is an appliance consisting of two or more commodity rack-mountable 1U pizza-box units.
One unit contains the Kickfire chip and a lot of standard, high-speed, server-grade ECC memory. This unit is what executes the queries at high speed.
The other unit is connected to the Kickfire chip unit via a standard PCIe interconnect. It runs stock CentOS 5, with MySQL 5.1. Kickfire has their own storage engine, which uses fairly well-known techniques such as column storage and compression.
To the outside world, the unit behaves just like an ordinary MySQL server. You connect to it in the same manner, you issue the same kinds of queries, you manage users and privileges the same way, and so on. However, when you run a query, it doesn’t get executed in the traditional MySQL manner (nested-loop joins with calls to the storage engine via the storage engine API). Instead, the query goes to the Kickfire chip and executes there. The chip is designed to execute queries very fast, through a variety of techiques that a) I’m not allowed to tell you about yet or b) are sometimes unclear to me because Kickfire was being a little protective about some of my technical questions.
I met with quite a few people at Kickfire, but I’ll just mention one: Ravi Krishnamurthy. Before Kickfire approached me, I had not heard of him. Anyway, I’ll just link to Ravi Krishnamurthy on Google Scholar, and let you read up on his papers if you want. It’s enough to say that I really enjoyed speaking with him and the other people at Kickfire.
One of the overall impressions I got was that the Kickfire engineers aren’t the type to do something halfway. When complete, this is not intended to be a system that has only some of the features you’d expect.
The Kickfire chip has no registers. Instead, the Kickfire chip addresses a very large amount of memory directly. Remember, registers are a bottleneck. As I said in my first article on Kickfire, using registers to process large amounts of data is like using a paper cup to fill your bathtub. Allowing the chip to address this memory directly removes a huge bottleneck.
There is still on-disk storage, though. (And no, it’s not SSD.) The interconnect between the on-disk storage and the memory is a standard PCIe connection. Nothing exotic or proprietary. But the system is apparently capable of moving a very large amount of data at very high speed from the disks to the Kickfire chip’s memory, where it can be addressed in O(1) speed like an array lookup.
Another interesting technique is that the system does not decompress the data to operate on it. According to the engineers, the queries run on the data in its compressed form. As Ravi told me, implementing this is “not for the faint of heart.”
Kickfire seems to have really worked hard at removing bottlenecks wherever possible. For example, they’ve rewritten the out-of-the-box drivers for key pieces of the commodity hardware they’re using.
If you know how MySQL executes queries, the statement “Kickfire executes joins directly in the Kickfire chip” implies that the Kickfire system isn’t just a storage engine, because MySQL currently processes many of the most costly parts of queries at the server level, not in the storage engine. Obviously Kickfire is not going to perform well unless it changes that. Kickfire has in fact built their own optimizer, which replaces the MySQL optimizer. It compiles the incoming query into a series of macro-operations, which apparently are very similar to the basic relational operators (project, join, etc). This is then sent to the chip for execution, and as the chip produces results it injects them back into the stream of bytes that the server normally uses to send results back to the client.
The Kickfire chip doesn’t implement everything in hardware. For example, there is no MD5() function in the chip. When it encounters an operation it can’t do in hardware, it makes a call back to the MySQL server to fill in the gaps in its functionality.
The rewritten optimizer sounds like an interesting piece of engineering. Ravi told me with pride that the optimizer is “world-class” and “can stand toe-to-toe with the best optimizers in the database industry.” It is a cost-based optimizer with rewrites (e.g. it transforms the operator tree into the most efficient equivalent structure) and it is exhaustive (e.g. it tries all possible combinations to find the best execution plan, unlike MySQL’s optimizer which by default switches to a greedy search when the number of tables to be joined becomes large [correction: as Timour pointed out to me today, I made it sound like MySQL’s optimizer isn’t exhaustive; I neglected to mention that you can configure it]).
I asked whether they had benchmarked the optimizer’s performance. (I mean how fast it can find an optimal query plan, not the performance of its results.) Of course, there is no standard benchmark for this, but I think it’s interesting just to compare it against the MySQL optimizer. They had not done this, but I think they will now that I have mentioned it. I think it’s relevant because if you use Kickfire for short queries, a slow-performing optimizer could actually become noticeable.
I wanted to know whether the chip really does stream processing, or whether it is only conceptually stream processing that’s really implemented some other way. It sounds to me like it’s the genuine article. I asked some pointed questions to this effect, such as “is there a way to interrupt a partially completed query.” As it turns out there is, but only because the stream processor apparently does time-slicing like a standard chip, and when it comes up for air it can check to see if a query should be aborted. In general, I was told, there is no interruption once the data stream starts flowing. That lets the query literally “run at the speed of electrons.”
But what about subqueries, you ask? That’s what I asked too. Stream processing is all very well for joins, but what about a correlated subquery, for example?
It turns out that if you’re clever, you can figure out ways to decorrelate them and then execute them in streaming fashion. The same holds for aggregation over data that’s not in the order needed for streamed aggregation. Pretty interesting ideas; I can’t go into them, because those are proprietary, but Ravi and I talked about them for quite a while.
And very large IN() lists can be turned into a relation and treated like any other.
Storage is obviously crucial to processing extremely large amounts of data very fast. A few of the things I noted about the storage:
Loading data is also important to accelerate: executing queries on large amounts of data isn’t good if it takes forever to get the data into the server. Kickfire has their own suite of tools, including one for loading data that accelerates the load process with the SQL chip itself.
Kickfire’s attitude towards star schemas is that you shouldn’t need to build a special schema for your data warehouse. They think their system will be so fast that you can keep your data in the same schema you use for OLTP. If that turns out to be true, that will save a lot of work. (How much effort have you put into building a separate schema for your data warehouse?)
Here are some other tidbits I thought I’d share with you:
As you probably know, I’m a strong believer in Free Software. I am not aware of any plans for Kickfire to release the source code for their modified version of MySQL or their storage engine or optimizer. These are the satellite diamonds that surround the crown jewels: open-sourcing them would make it easier to reverse engineer the chip, which they don’t want. However, they’ve promised me that they’re going to open-source some of the migration tools, etc etc. Not initially, but as time permits; and later they’ll look at open-sourcing other parts.
I have made sure that they know where I stand on this: I think the ethical thing to do is GPL all the code that they ship, and I think everyone I talked to heard me say that at least once. If you’re going to buy their magical hardware, you deserve to have the source code for everything that runs on it, too. And they need to release the interface specs for their hardware so people can use it in new and surprising ways. Who knows – someone could use it to find a cure for cancer.
My two days with Kickfire left me with a lot more questions, not surprisingly, and I don’t think that will change until I actually get access to a machine and start testing it myself. I saw a lot of slideshows; I saw some demos; I walked into the server rooms and saw the pretty blinking lights; but I’m not going to tell you that Kickfire will do X or Y because I don’t know a heck of a lot. I was hoping for more hands-on experience and in-depth technical details, but that wasn’t the way it really worked out. However, based on what I’ve seen, I have no reason to believe other than that Kickfire’s system will do what they claim: it will run large, complex queries on very large datasets extremely quickly.