Bulk Fetch

Introduction

The TokuDB bulk fetch algorithm speeds up fractal tree scans by returning multiple rows per tree search rather than a single row. This amortizes the cost of a fractal tree search over several rows. We have observed a speedup of between 2x and 5x when using bulk fetch compared to not using it. TokuDB 7.1.7 (and prior versions) only use bulk fetch for simple selects. As a result, only simple selects run fast. Other operations, such as create select, run slow. We describe how to use bulk fetch for these other operations.

Index and range scans

The MySQL query executor uses one of several table scanning algorithms to read rows from a table. An index scan is used to retrieve all of the rows from an index. A range scan is used to retrieve all of the rows from an index within a key range. TokuDB can use its bulk fetch algorithm for both of these types of scans. However, TokuDB must be notified by the MySQL query executor that an index or range scan will happen. The prepare_index_scan handler method informs the storage engine that an index scan will happen. Similarly, the prepare_range_scan handler method informs the storage engine that a range scan will happen. We placed calls to these methods in the appropriate places of the MySQL query executor code.

Partitioned tables

Bulk fetch should be used for index and range scans on simple tables as well as partitioned tables. We recently found that bulk fetch is NOT being used for index scans on partitioned TokuDB tables. #261 Index scans on partitions do not use bulk fetch because the tokudb::prepare_index_scan method is not currently called by the partition storage engine.

Current Implementation

TokuDB enables bulk fetch when MySQL tells it that an index scan will be done by calling the tokudb::prepare_index_scan method. This method prelocks the relevant index and starts TokuDB's bulk fetch mechanism.

When tokudb::index_first or tokudb::index_last is called, TokuDB will do a fractal tree search for the first (or last) key in the tree. When bulk fetch is enabled, the tree search will return multiple rows, which are stored in the bulk fetch buffer. Subsequent tokudb::index_next (or tokudb::index_prev) method calls will pull rows out of the bulk fetch, unless there are no more rows buffered up. In this case, another fractal tree search operation occurs, which fills the bulk fetch buffer. And we repeat.

A similar sequence of operations occurs for range scans.

The key point of the current implementation is that TokuDB must be told that an index or range scan is intended. Sometimes, this does not occur and the scans run slow.

Auto detection of an index scan

Suppose that tokudb::prepare_index_scan is not called by MySQL because of a missing Tokutek patch to the MySQL source. TokuDB can automatically detect an index scan by monitoring the sequence of index calls. If a call to tokudb::index_first is followed by a call to tokudb::index_next, then TokuDB can infer that an index scan is being done and setup bulk fetch appropriately. Similarly, if a call to tokudb::index_last is followed by a call to tokudb::index_prev, then TokuDB can infer that a reverse index scan is begin done.

Simple select

• select ... from s where ...
• Documented in #261
• Bulk fetch can be used when handling simple select statements since the rows that are cached in the bulk fetch buffer are not updated in the fractal tree by this client's thread.

Create select

• create table t as select ... from s where ...
• Documented in #262
• Bulk fetch can be used when handling create select statements since the destination table is new and the rules for simple select apply.

Create temporary table select

• create temporary table t as select ... from s where ...
• Create temporary table documented in #143
• Bulk fetch can be used when handling create temporary table select statements since the destination table is new and the rules for simple select apply.

Insert select

• insert into t select ... from s where ...
• Documented in #263
• MySQL will use a temporary table if the destination table 't' is the same as the source table 's'.

Insert select on duplicate key update

Replace select

• See insert select.

Replace select on duplicate key update

• See insert select on duplicate key update

Delete

• delete from t where ...
• Documented in #264

Update

• update t set ... where ...
• Documented in #265

Multiple table update

• update t1,t2 set t1... where ...