Supporting Indexing MySQL

Once basic read/write operations are implemented in a storage engine, the next stage is to add support for indexing. Without indexing, a storage engine's performance is quite limited.

This section documents the methods that must be implemented to add support for indexing to a storage

Indexing Overview

Adding index support to a storage engine revolves around two tasks: providing information to the optimizer and implementing index-related methods. The information provided to the optimizer helps the optimizer to make better decisions about which index to use or even to skip using an index and instead perform a table scan.

The indexing methods either read rows that match a key, scan a set of rows by index order, or read information directly from the index.

The following example shows the method calls made during an UPDATE query that uses an index, such as UPDATE foo SET ts = now() WHERE id = 1:

In addition to index reading methods, your storage engine must support the creation of new indexes and be able to keep table indexes up to date as rows are added, modified, and removed from tables.

Getting Index Information During CREATE TABLE Operations

It is preferable for storage engines that support indexing to read the index information provided during a CREATE TABLE operation and store it for future use. The reasoning behind this is that the index information is most readily available during table and index creation and is not as easily retrieved afterward.

The table index information is contained within the key_info structure of the TABLE argument of the create() method.

Within the key_info structure there is a flag that defines index behavior:

In addition to the flag, there is an enumerator named algorithm that specifies the desired index type:

In addition to the flag and algorithm, there is an array of key_part elements that describe the individual parts of a composite key.

The key parts define the field associated with the key part, whether the key should be packed, and the data type and length of the index part. See for an example of how this information is parsed.

As an alternative, a storage engine can instead read index information from the TABLE structure of the handler during each operation.

Creating Index Keys

As part of every table-write operation (INSERT, UPDATE, DELETE), the storage engine is required to update its internal index information.

The method used to update indexes will vary from storage engine to storage engine, depending on the method used to store the index.

In general, the storage engine will have to use row information passed in methods such as write_row(), delete_row(), and update_row() in combination with index information for the table to determine what index data needs to be modified, and make the needed changes.

The method of associating an index with its row will depend on your storage approach. Current storage engines store the row offset.

Parsing Key Information

Many of the index methods pass a byte array named *key that identifies the index entry to be read in a standard format. Your storage engine will need to extract the information stored in the key and translate it into its internal index format to identify the row associated with the index.

The information in the key is obtained by iterating through the key, which is formatted the same as the definition in table-> key_ info[index]-> key_part [part_num].

Providing Index Information to the Optimizer

In order for indexing to be used effectively, storage engines need to provide the optimizer with information about the table and its indexes. This information is used to choose whether to use an index, and if so, which index to use.

Implementing the info() Method

The optimizer requests an update of table information by calling the handler::info() method. The info() method does not have a return value, instead it is expected that the storage engine will set a variety of public variables that the server will then read as needed. These values are also used to populate certain SHOW outputs such as SHOW TABLE STATUS and for queries of the INFORMATION_ SCHEMA.

All variables are optional but should be filled if possible:

  • records - The number of rows in the table. If you cannot provide an accurate number quickly you should set the value to be greater than 1 so that the optimizer does not perform optimizations for zero or one row tables.
  • deleted - Number of deleted rows in table. Used to identify table fragmentation, where applicable.
  • data_file_length - Size of the data file, in bytes. Helps optimizer calculate the cost of reads.
  • index_file_length - Size of the index file, in bytes. Helps optimizer calculate the cost of reads.
  • mean_rec_length - Average length of a single row, in bytes.
  • scan_time - Cost in I/O seeks to perform a full table scan.
  • delete_length -
  • check_time -

When calculating values, speed is more important than accuracy, as there is no sense in taking a long time to give the optimizer clues as to what approach may be the fastest. Estimates within an order of magnitude are usually good enough.

Implementing the records_in_range Method

The records_in_range() method is called by the optimizer to assist in choosing which index on a table to use for a query or join. It is defined as follows:

The inx parameter is the index to be checked. The *min_key parameter is the low end of the range while the *max_key parameter is the high end of the range. min_key.flag can have one of the following values:

  • HA_READ_KEY_EXACT - Include the key in the range
  • HA_READ_AFTER_KEY - Don't include key in range
  • max_key.flag can have one of the following values:

  • HA_READ_BEFORE_KEY - Don't include key in range
  • HA_READ_AFTER_KEY - Include all 'end_key' values in the range
  • The following return values are allowed:

  • 0 - There are no matching keys in the given range
  • number > 0 - There is approximately number matching rows in the range
  • HA_POS_ERROR - Something is wrong with the index tree

When calculating values, speed is more important than accuracy.

Preparing for Index Use with index_init()

The index_init() method is called before an index is used to allow the storage engine to perform any necessary preparation or optimization:

Most storage engines do not need to make special preparations, in which case a default implementation will be used if the method is not explicitly implemented in the storage engine: int handler::index_init(uint idx) { active_index=idx; return 0; }

Cleaning up with index_end()

The index_end() method is a counterpart to the index_init() method. The purpose of the index_ end() method is to clean up any preparations made by the index_init() method.

If a storage engine does not implement index_init() it does not need to implement index_end().

Implementing the index_read() Method

The index_read() method is used to retrieve a row based on a key:

The *buf parameter is a byte array that the storage engine populates with the row that matches the index key specified in *key. The key_len parameter indicates the prefix length when matching by prefix, and the find_flag parameter is an enumerator that dictates the search behavior to be used.

The index to be used is previously defined in the index_init() call and is stored in the active_ index handler variable.

The following values are allowed for find_flag:

Storage engines must convert the *key parameter to a storage engine-specific format, use it to find the matching row according to the find_flag, and then populate *buf with the matching row in the MySQL internal row format. For more information on the internal row format, see Section “Implementing the rnd_next() Method”.

In addition to returning a matching row, the storage engine must also set a cursor to support sequential index reads.

If the *key parameter is null the storage engine should read the first key in the index.

Implementing the index_read_idx() Method

The index_read_idx() method is identical to the index_read() with the exception that index_ read_idx() accepts an additional keynr parameter:

The keynr parameter specifies the index to be read, as opposed to index_read where the index is already set.

As with the index_read() method, the storage engine must return the row that matches the key according to the find_flag and set a cursor for future reads.

Implementing the index_next() Method

The index_next() method is used for index scanning:

Implementing the index_prev() Method

The index_prev() method is used for reverse index scanning:

The *buf parameter is populated with the row that corresponds to the previous matching key value according to the internal cursor set by the storage engine during operations such as index_read() and index_last().

Implementing the index_first() Method

The index_first() method is used for index scanning:

The *buf parameter is populated with the row that corresponds to the first key value in the index.

Implementing the index_last() Method

The index_last() method is used for reverse index scanning:

The *buf parameter is populated with the row that corresponds to the last key value in the index.

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd Protection Status

MySQL Topics