Sorting a Terabyte in 197 seconds

I just returned from The 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), held in Calgary, where I gave a talk about my entry to the sorting contest.  I sorted 1TB in 197s on a 400-node machine at MIT Lincoln Laboratory, a record which still stands today.  (And it will likely remain standing, since terabyte sorting is now deprecated because it’s too fast.  Now the challenge is to sort 100TB.)

For many years Jim Gray ran a sorting contest to see how fast anyone could sort a terabtye worth of 100-byte records, how much data could be sorted in one minute, and how much data could be sorted for a penny.  After Jim’s disappearance at sea in January …

Tokutek® announces the release the release of the TokuDB storage engine for MySQL®, version 2.1.0.  This release offers the following improvements over our previous release:

• Faster indexing of sequential keys.
• Faster bulk loads on tables with auto-increment fields.
• Faster range queries in some circumstances.
• Added support for InnoDB.
• Upgraded from MySQL 5.1.30 to 5.1.36.
• Fixed all known bugs.

About TokuDB

TokuDB for MySQL is a storage engine built with Tokutek’s Fractal Tree™ technology. TokuDB provides near seamless compatibility for MySQL applications. Tables can be individually defined to use TokuDB, MyISAM, InnoDB® or other MySQL-compliant storage engines. Data is loaded, inserted, and queried using standard MySQL commands, with no restrictions or special …

In our last post, Bradley described how auto increment works in TokuDB. In this post, I explain one of our implementation’s big benefits, the ability to combine better primary keys with clustered primary keys.

In working with customers, the following scenario has come up frequently. The user has data that is streamed into the table, in order of time. The table will have a primary key that is an auto increment field, ‘id’, and then have an index on the field ‘time’. The queries the user does are all on some range of time (e.g. select sum(clicks) from foo where time > date ‘2008-12-19’ and time < date '2008-14-20';).

For storage engines with clustered primary keys (such as TokuDB and InnoDB), having such a schema hurts query performance. Queries do a range query on a secondary index (time), and then perform point …

In this post I’m going to talk about how TokuDB’s implementation of auto increment works, and contrast it to the behavior of MyISAM and InnoDB.  We feel that the TokuDB behavior is easier to understand, more standard-compliant and offers higher performance (especially when implemented with Fractal Tree indexes).

In TokuDB, each table can have an auto-increment column.  That column can be used as any part of a key, but it doesn’t have to be part of any key.  The value produced by auto incrementing is always greater than the previous maximum value for that column. There are some cases where auto-incremented values are skipped, such as when a transaction aborts, which “uses up” auto-incremented values.

This behavior is close to that required for SQL:2003 (see SQL:2003 at wikipedia), which specifies that each table provides one unnamed sequence which behaves essentially in the way we implemented …

Summary: An alternate approach, offered in response to our original post, provides excellent improvements for smaller databases, but clustered indexes offer better performance as database size increases.  (This posting is by Dave.)

Jay Pipes suggested an alternate approach to improving MySQL performance of Query 17 on a TPC-H-like database.

1. 
   
2. Add the index (l_partkey, l_quantity) to the lineitem table.
   
3. Re-write the query as:
   

   select 
      sum(li.l_extendedprice) / 7.0 as avg_yearly 
   from lineitem li 
      inner join part p on li.l_partkey = p.p_partkey 
      inner join ( select 
                      l_partkey, 0.2 * avg(l_quantity) as quantity 
                   from lineitem 
                   group by l_partkey 
                 ) as quantities 
         on …

Executive Summary: A query like TPC-H Query 17 can be sped up by large factors by using straight_joins and clustering indexes.  (This entry posted by Dave.)

In a previous post, we wrote about queries like TPC-H query 2, and the use of straight_join to improve performance. 
This week, we consider Query 17, described by the TPC-H documentation as

“The Small-Quantity-Order Revenue Query considers parts of a given brand and with a given container type and determines the average lineitem quantity of such parts ordered for all orders (past and pending) in the 7-year database.  What would the average yearly gross (undiscounted) loss in revenue if orders for these parts with a quantity of this average were no longer taken?”

Our initial run on Q17 (same hardware as before) timed out …

This post is for storage engine developers that may be interested in implementing multiple clustering keys.

After blogging about TokuDB’s multiple clustering indexes feature, Baron Schwartz suggested we contribute the patch to allow other storage engine to implement the feature. We filed a feature request to MySQL to support this, along with a proposed patch. The patch, along with known issues, can be found here.

What the patch contains:

This patch has the changes necessary to introduce the new grammar for clustering indexes, and to tell the storage engine what indexes are defined as clustering. With this patch, all indexes that are defined as clustering …

As you can probably guess, I’m catching up on reading my blogs. I’ve just read with interest about TokuDB’s multiple clustering indexes. It’s kind of an obvious thought, once someone has pointed it out to you. I’ve only been around products that insist there can be Only One clustered index (and then there’s ScaleDB, who say “think differently already”).

Anyway, we already know that there are quite a few database products that use clustered indexes and to avoid update overhead, require every non-clustered index to store the clustered key as the “pointer” for row lookups. Thus there are “hidden columns” which are present at the leaf nodes, but not the non-leaf nodes, of secondary indexes. Why not take that idea and run with it a little? Here’s what I mean:

Tokutek have said they are working towards explaining their indexing algorithms. I spoke to some of the Tokutek people over the last 14 months or so about this, although I didn’t really start to pay attention until the beginning of the year. While Vadim, Peter and I were writing our blog post on TokuDB, I asked them to provide scholarly references, and they did, but warned me it would be dense reading, in part because it’s so academic. Mark Callaghan also told me he had gotten them to walk him through the math behind their indexing algorithm and found it hard.

Here’s a blog post with links to the research behind their work. I’m happy to say that after …

I recently posted a blog entry on clustering indexes, which are good for speeding up queries.  Eric Day brought up the concern that clustering indexes might degrade update performance. This is often true, since any update will require updating the clustering index as well.

However, there are some cases in TokuDB for MySQL, where the opposite is true: clustering indexes can drastically improve the performance of updates and deletions.  Consider the following analysis and example.

Updates and deletions generally have two steps. First, a query is done to find the necessary rows (the where clause in the statement), and then the rows are modified: they are deleted or updated, as the case may be. So the total time to do a deletion or an update is

T_total = T_query + T_change

Eric noted that …