Showing entries 11 to 20 of 25
« 10 Newer Entries | 5 Older Entries »
Displaying posts with tag: Fractal Trees (reset)
Tokutek’s Chief Scientist Discusses TokuDB v5.0

Running with Big Data

It’s spring here in Boston, though one could hardly tell (still barely hitting 40°F). So, for those stuck indoors working out on the treadmill, or those lucky enough to do a workout outdoors, we’ve got a great podcast. Our Chief Scientist and co-founder Martín Farach-Colton had the privilege of sitting down with Sheeri Cabral and Sarah Novotny for their weekly MySQL Database Community Podcast (OurSQL Episode 39). In it, he speaks about Tokutek and TokuDB v5.0, which was just released last week (see …

[Read more]
MySQL Partitioning: A Flow Chart

In Part 1, and Part 2 of this series, I presented some thoughts on partitioning. I heard some great feedback on why people use partitioning. Here, I present a flow chart that summarizes what I’ve learned. In summary: with TokuDB in the picture there’s almost no reason to use partitioning. Or I should say, there are almost always better (higher performing, more robust, lower maintenance) alternatives to partitioning.

Here goes:

  1. Spindle contention? In other words, are you partitioning in order to spread your query work load across many disks? I’ve yet to see a compelling technical case that RAIDing your disks doesn’t do this as well, with much less setup and maintenance.
[Read more]
On “Replace Into”, “Insert Ignore”, Triggers, and Row Based Replication

In posts on June 30 and July 6, I explained how implementing the commands “replace into” and “insert ignore” with TokuDB’s fractal trees data structures can be two orders of magnitude faster than implementing them with B-trees. Towards the end of each post, I hinted at that there are some caveats that complicate the story a little. On July 21st I explained one caveat, secondary keys, and on August 3rd, Rich explained another caveat. In this post, I explain the other …

[Read more]
On “Replace Into”, “Insert Ignore”, and Secondary Keys

In posts on June 30 and July 6, I explained how implementing the commands “replace into” and “insert ignore” with TokuDB’s fractal trees data structures can be two orders of magnitude faster than implementing them with B-trees. Towards the end of each post, I hinted at that there are some caveats that complicate the story a little. In this post, I explain one of the complications: secondary indexes.

Secondary indexes act the same way in TokuDB as they do in InnoDB. They store the defined secondary key, and the primary key as a pointer to the rest of the row. So, say the table foo has the following schema:

create …
[Read more]
Why “insert … on duplicate key update” May Be Slow, by Incurring Disk Seeks

In my post on June 18th, I explained why the semantics of normal ad-hoc insertions with a primary key are expensive because they require disk seeks on large data sets. I previously explained why it would be better to use “replace into” or to use “insert ignore” over normal inserts. In this post, I explain why another alternative to normal inserts, “insert … on duplicate key update” is no better in MySQL, because the command incurs disk seeks.

The reason “insert ignore” and “replace into” can be made fast with TokuDB’s fractal trees is that the semantics of what to do in case a duplicate key is found is simple. …

[Read more]
Making “Insert Ignore” Fast, by Avoiding Disk Seeks

In my post from three weeks ago, I explained why the semantics of normal ad-hoc insertions with a primary key are expensive because they require disk seeks on large data sets. Towards the end of the post, I claimed that it would be better to use “replace into” or “insert ignore” over normal inserts, because the semantics of these statements do NOT require disk seeks. In my post last week, I explained how the command “replace into” can be fast with TokuDB’s fractal trees. Today, I explain how “insert ignore” can be fast, using a strategy that is very similar to what we do with “replace into”.

The semantics …

[Read more]
Making “Replace Into” Fast, by Avoiding Disk Seeks

In this post two weeks ago, I explained why the semantics of normal ad-hoc insertions with a primary key are expensive because they require disk seeks on large data sets. Towards the end of the post, I claimed that it would be better to use “replace into” or “insert ignore” over normal inserts, because the semantics of these statements do NOT require disk seeks. In this post, I explain how the command “replace into” can be fast with fractal trees.

The semantics of “replace into” are as follows:


  • if the primary (or unique) key does not exist, insert the new row
  • if the primary (or unique) key does exist, overwrite the existing row with the new row

The slow, expensive way B-trees use to implement these semantics are:

[Read more]
Making Updates Fast, by Avoiding Disk Seeks

The analysis that shows how to make deletions really fast by using clustering keys and TokuDB’s fractal tree based engine also applies to make updates really fast. (I left it out of the last post to keep the story simple). As a quick example, let’s look at the following statement:

update foo set price=price+1 where product=toy;

Executing this statement has two steps:


  • a query to find where product=toy
  • a combination of insertions and deletions to change old rows to new rows

The analysis is identical to that for deletions. Just like for …

[Read more]
Disk seeks are evil, so let’s avoid them, pt. 4

Continuing in the theme from previous posts, I’d like to examine another case where we can eliminate all disk seeks from a MySQL operation and therefore get two orders-of-magnitude speedup. The general outline of these posts is:


  • B-trees do insertion disk seeks. While they’re at it, they piggyback some other work on the disk seeks. This piggyback work requires disk seeks regardless.
  • TokuDB’s Fractal Tree indexes don’t do insertion disk seeks. If we also get rid of the piggyback work, we end up with no disk seeks, and a two order of magnitude improvement.

So it’s all about finding out which piggyback work is important (important enough to pay a huge performance penalty for), and which isn’t.

This blog post is about one of the most …

[Read more]
Making Deletions Fast, by Avoiding Disk Seeks

In my last post, I discussed how fractal tree data structures can be up to two orders of magnitude faster on deletions over B-trees. I focused on the deletions where the row entry is known (the storage engine API handler::delete_row), but I did not fully analyze how MySQL delete statements can be fast. In this post, I do. Here I show how one can use TokuDB, a storage engine that uses fractal tree data structures, to make MySQL deletions run fast.

Let’s take a step back and analyze the work needed to be done to execute a MySQL delete statement. Suppose we have the table:

create table foo (
        id auto_increment
        a int,
        b int,
        primary key (id)
)

Say we wish to perform the following operation that deletes 100,000 rows:

delete from foo where a=1;

In MySQL, …

[Read more]
Showing entries 11 to 20 of 25
« 10 Newer Entries | 5 Older Entries »