Making Updates Fast, by Avoiding Disk SeeksZardosht.Kasheff
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 deletes, clustering keys make the query go fast, as explained here. In this case, the appropriate clustering key would be on ‘product’. And fractal tree data structures make the insertions and deletions go fast, as explained here and here.
So, the same story applies. Updates are a combination of queries and value changes. To make updates fast, both the query and the value changes need to be fast. With B-tree based storage engines, users may be hesitant to add indexes to speed up the query, due to the added cost of value changes in the index. With TokuDB, this tradeoff does not exist, because TokuDB uses fractal tree data structures. Using a clustering key to drive down the cost of the query, and using fractal tree indexes to keep the cost of the data changes down, leads to very fast updates.