takeaway

In the next part of “Why MySQL Chooses Plan A over Plan B”, I explained in detail the strategy of MySQL’s choice of execution plan. Among them, THERE are three methods of query cost calculation:

  1. Query cost calculation based on index scan
  2. Query cost calculation based on index statistics
  3. Query cost calculation based on full table scan

We all hope to have a calculation query cost efficient, and accurate scheme, and MySQL currently only support these three query cost calculation scheme, then, combined with our expectations, let’s see whether the above three scheme is possible to achieve our expectations through some method?

  1. Query cost calculation based on index scan

    According to “Why did MySQL choose plan A over Plan B?” We know that this is an inefficient, but the most accurate calculation of the scheme.

    The low efficiency of the scheme is because the index tree must be scanned to determine the query cost. If the index tree has many forks, the scanning efficiency will be inevitably reduced, thus reducing the efficiency of the query cost calculation. So, it doesn’t meet our expectations.

  2. Query cost calculation based on index statistics

    According to “Why did MySQL choose plan A over Plan B?” , we know that this is a high efficiency, but the calculation is not accurate.

    The calculation of the scheme is not accurate because MySQL samples some nodes of the index tree, and then does related calculations on these nodes, so as to generate index statistical results, and finally, obtain the query cost. So, it doesn’t meet our expectations.

    So, if we can increase the number of sampling nodes, can we calculate the query cost more accurately?

Indeed, MySQL gives us relevant parameter optimizations that allow us to calculate the query cost more accurately. The calculation results are more accurate, and the efficiency of the scheme is high, just to meet our expectations.

  1. Query cost calculation based on full table scan

    According to “Why did MySQL choose plan A over Plan B?” In the query cost calculation process of full table scan, we can know that this scheme is a scheme with high calculation efficiency but inaccurate calculation results.

    In most cases, its cost calculation results tend to be much worse than the above two index based query cost calculation scheme, so the significance of further analysis of this scheme is not very big, I will not do further analysis and explanation here.

To sum up, only the second scheme, that is, the query cost calculation based on index statistics, has room for further optimization. Therefore, next, I will explain in detail how MySQL generates the index related statistical results in the query cost calculation based on index statistics. In the process of explaining, I’ll tell you which parameters of MySQL can improve the accuracy of query cost calculation?

INFORMATION_SCHEMA

Before I talk about how MySQL generates index statistics, I’ll talk about one database: INFORMATION_SCHEMA, because it is the basic data source MySQL needs to generate index statistics.

InnoDB is now the main storage engine, so I will describe in detail the tables in the INFORMATION_SCHEMA database that are related to the InnoDB engine. These tables are commonly referred to as InnoDB Data Dictionaries. INNODB_SYS_TABLES and INNODB_SYS_INDEXES provide the basic information for index statistics. The tables are INNODB_SYS_TABLES and INNODB_SYS_INDEXES.

In order to understand the concept of the columns of the two dictionary tables, I post the user table structure and table records again:

User table structure:

The user table record

INNODB_SYS_TABLES

MySQL > select * from user where user = user; MySQL > select * from user where user = user;

Let’s look at the core fields in this table:

The column name instructions
TABLE_ID Each table is unique, as shown in the figure above: the user table is numbered 40
NAME Table name, structure isDatabase/tableFor example, user_Center /user represents the user table in the user_Center database
N_COLS DB_ROW_ID, DB_TRX_ID, and DB_ROLL_PTR
SPACE The ID of the tablespace where the table is located is unique for each MySQL instance. For example, in the figure above, the user tablespace ID is 57
ROW_FORMAT The row format can be Compact, Redundant, Dynamic, or Compressed. In the preceding figure, the row format of the user table is Dynamic
INNODB_SYS_INDEXES

MySQL > select * from user where user = ‘user’;

The column name instructions
INDEX_ID Select * from user where primary key =41; select * from user where primary key =41;index_age_birthThe index ID = 42
NAME Index name, where PRIMARY key index name PRIMARY, and a nameindex_age_birthSecondary index of
TABLE_ID The ID of the table where the index is located. For example, in the figure above, both indexes in the user table are located in the table whose ID is 40, which is the USER table
TYPE Index types, including clustered indexes, secondary indexes, unique indexes, common indexes, and so on. For example, in the figure above, the primary key index in the user table is of type 3, which is the cluster index. The indexindex_age_birthThe type is 0, that is, secondary index
N_FIELDS The number of columns the index contains. For example, in the figure above, the primary key index contains 1 column, which is the ID.index_age_birthThe index contains two columns, as shown in the INDEXES section of the table structure diagram, i.eageandbirthday
PAGE_NO Specifies the root node of the B+Tree where the index is located. For example, in the figure above, the root node of B+Tree where the primary key index is located is 3.index_age_birthThe root node of the B+Tree where the index resides is 4
SPACE The ID of the tablespace where the index resides, such as in the figure above, the primary key index andindex_age_birthThe indexes are in the user table, so the tablespace ID corresponding to the user table is 57

Index Tables

Next, let’s look at the MySQL index statistics table, because this table stores the index statistics generated by MySQL.

For example, if InnoDB has an index table in the mysql database, run the following SQL query:

SELECT * FROM mysql.innodb_index_stats WHERE table_name = 'user'
Copy the code

Let’s look at the user table and look at the innodb_index_STATS table:

The columns DATABase_name and table_name indicate which table belongs to a certain database. I won’t go into details. Take a look at the following columns:

  • index_name

    This column records the index name. As shown in the figure above, the User table contains two indexes, the PRIMARY key index and the INDEx_age_birth index.

  • stat_name/stat_value

    For rows with the same column index_name, stat_name indicates the name of the statistical item for the index, and stat_value displays the value of the index on the statistical item. Let’s take a look at what statistics an index contains:

    • N_leaf_pages: indicates the number of leaf nodes in the index.

      For example, the user primary key index has 1 leaf node, and the INDEx_age_birth index has 1 leaf node

    • Size: indicates the number of all nodes in the index.

      For example, the primary key index of the user table is 1, and the primary key index index_age_birth is 1

    • N_diff_pfxNN: indicates how many values the corresponding index column does not have. What does NN mean?

      In fact, NN can be replaced with 01, 02, 03… Numbers like that. For example, in the figure above, for the index_age_birth index:

      • n_diff_pfx01Indicates that in the indexageHow many records do not duplicate in this single column. Combined with the above user table record diagram, we find that in the user tableageThere are six records where the columns are not repeated.
      • n_diff_pfx02Indicates that in the indexage,birthdayThe number of records where the two columns are combined that do not repeat. Combined with the above graph of user table records, we find that in the user tableage,birthdayThere are nine records that do not duplicate after the columns are combined.
      • n_diff_pfx03Indicates that in the indexage,birthday,idHow many records do these three columns combine to not repeat. Combined with the above graph of user table records, we find that in the user tableage,birthday,idThere are 10 records that do not duplicate after the columns are combined.

  • sample_size

    The sample_size column indicates the number of leaf nodes sampled when calculating how many distinct records are contained in some index columns. As shown above,

    • primaryThe number of leaf nodes sampled for the primary key index ID is 1
    • index_age_birthThe indexageThe sample leaf number for the column is 1
    • index_age_birthThe indexage,birthdayThe number of sampled leaf nodes for the column combination is 1
    • index_age_birthThe indexage,birthday,iThe number of sampled leaf nodes in column D combination is 1

Build the InnoDB dictionary cache

In the INFORMATION_SCHEMA section, I mentioned that the basic data for the MySQL index statistics results comes from the InnoDB data dictionary, mainly from two tables INNODB_SYS_TABLES and INNODB_SYS_INDEXES. Now, let’s look at this scenario:

INNODB_SYS_TABLES and INNODB_SYS_INDEXES are persistent on disk. To ensure the accuracy of the indexes, MySQL must frequently read the tables from disk in order to obtain the underlying data when building the indexes. In this case, disk IO will increase. The MySQL performance deteriorates. This is certainly not what we want to see.

So, to solve this problem, MySQL caches InnoDB data dictionary, so MySQL can read the basic data from the cache when building index statistics, which improves the performance of reading compared to disk.

How does MySQL build the InnoDB dictionary cache?

The cache structure

Before going through the cache building process, let’s take a look at what a data dictionary cache looks like. Using the user table as an example, I look at the cache structure of two dictionary tables INNODB_SYS_TABLES and INNODB_SYS_INDEXES.

INNODB_SYS_TABLES cache

INNODB_SYS_TABLES cache consists of three main structures: table_hash, table_ID_hash, and table_LRU.

Let’s look at table_hash first:

As shown in the figure above, table_hash is a hash table with the following structure:

  • Cells: A list of nodes in the hash table. The structure of each node is as follows:

    • The hash value of node is calculated by fold the table name. As shown on the left:

      • The hash value of the first node is calculated by performing fold(t1) on the table name t1.

      • The hash value of the second node is obtained by performing fold(user) on the user table name.

      • The third node hash value is calculated by fold(t2) on the t2 table name.

    • Node A node stores a unidirectional linked list of table objects. Each node in the linked list stores a Table object, which contains basic information about the table. The unidirectional linked list is stored to resolve hash conflicts.

      • In the first node’s linked list, the head node stores table T1, the middle node stores table T2, and the last node stores table T3.

      • In the second node’s linked list, the head node stores the user table object, the middle node stores the user2 table object, and the last node stores the user3 table object.

Next, I’m looking at the table_ID_hash structure:

As shown in the figure above, the hash structure is similar to the table_hash structure, except that the node hash value is calculated by fold the table_id (30,40, and 45) instead of the table name.

Finally, let’s look at the table_LRU structure:

Table_LRU is a least used table excommunication linked list, which is a two-way linked list. When a table is not used for a long time, MySQL will remove it from the linked list. At the same time, the nodes in its corresponding Table_hash and table_ID_hash will be deleted to ensure effective memory utilization.

As shown in the figure above, the list contains table objects user, T1, and T2 from front to back.

I will not elaborate on the mechanism of the ejection algorithm because it is not the focus of this chapter.

INNODB_SYS_INDEXES cache

Next, let’s look at the structure of the INNODB_SYS_INDEXES cache.

MySQL maintains a two-way linked list for each index of a table. We call it INNODB_SYS_INDEXES. As shown in the figure above, a two-way linked list has two indexes for each table.

  1. Linked list nodes store information related to indexes. As shown above,

    • The linked list of Table1 contains four nodes, which respectively store the primary key index information, Index2 index information, Index3 index information and Index4 index information from front to back.

    • The linked list of the user table contains two nodes, which respectively store the primary key index information and index_age_birth index information from front to back.

  2. The leading node of a linked list must be the primary key of the table. As shown above,

    • The leading node of a linked table in Table1 stores the primary key index.

    • The leading node of the user table stores the primary key index.

  3. The list has a start pointer to the head node and an end pointer to the tail node. As shown above,

    • The start pointer of the linked list of Table1 points to the primary primary key inode at the head, and the end pointer to the Index4 inode at the tail.

    • The start pointer of the user table’s linked list points to the primary key inode in the head and the end pointer to the index_age_birth inode in the tail.

Now, let’s take a look at the process of building the InnoDB data dictionary cache. There are two main ways to do this:

Alert/Create triggers the build

The first is to trigger the building of the InnoDB data dictionary cache when we execute the SQL statement that creates or modifies the table/index.

Triggered when a table is created

How is the INNODB_SYS_TABLES dictionary table cache built when creating tables?

I’ll show you how to build the INNODB_SYS_TABLES cache using the SQL statement that creates the user table.

CREATE TABLE `user` (
  `id` int(11) NOT NULL,
  `user_id` int(8) DEFAULT NULL COMMENT 'user id',
  `user_name` varchar(29) DEFAULT NULL COMMENT 'Username',
  `user_introduction` varchar(498) DEFAULT NULL COMMENT 'User Profile',
  `sex` tinyint(1) DEFAULT NULL COMMENT 'gender',
  `age` int(3) DEFAULT NULL COMMENT 'age',
  `birthday` date DEFAULT NULL COMMENT 'birthday'.PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
Copy the code

The specific process is as follows:

  1. The SQL statement is parsed to obtain information about the table, such as table name, column name, column information, etc., which corresponds to the SQL statement above, namely user, 7 columns, and corresponding column information.
  2. generateThe user tablethetable_id
  3. According to theThe table name user,table_id, 7 column names, 7 column information, etcThe user table objects, which contains the basic information above
  4. willThe user table objectswritetable_hash,table_id_hash
  5. willThe user table objectsAdded to thetable_LRUList the head
Triggered when an index is created

How is the INNODB_SYS_INDEXES cache built when creating indexes?

I’ll show you how to build the INNODB_SYS_INDEXES cache using the SQL statement that creates index Index_age_birth.

ALTER TABLE `user` ADD UNIQUE INDEX `index_age_birth` (`age`, `birthday`);
Copy the code

The specific process is as follows:

  1. Parse SQL statements to obtain index and table related information, such as index name, index column, table name, etc., corresponding to the above SQL, i.eindex_age_birth,(age, birthday)anduser.
  2. According to theThe table name userfromtable_hashTo fetch the table object
  3. By index nameindex_age_birtH. Index column(age, birthday)To build the basic information of the index
  4. Update the index base information toThe user table objects
  5. willThe user table objectsTo writetable_hashandtable_id_hash
  6. Add index base information toThe user tableThe correspondingINNODB_SYS_INDEXES listAt the end of the
Build at startup

The second way is that InnoDB data dictionary cache will be lost when MySQL restarts, so MySQL will scan InnoDB data dictionary table and load the data into the data dictionary cache. The specific process is as follows:

  1. Scan the InnoDB data dictionary table, read the relevant data from each dictionary table and load it into the cache

    (1) Read records from INNODB_SYS_TABLES row by row, build table objects from records, write objects to table_hash and table_ID_hash one by one, and add objects to the head of table_LRU list

    (2) Read records from INNODB_SYS_INDEXES row by row:

    • Obtain table object from table_ID_hash based on table_ID based on table-> ID in record

    • Writes index information from the record to the table object

    • Add the index information from the record to the end of the INNODB_SYS_INDEXES linked table corresponding to the table object

    • Write the table object back to table_hash and table_ID_hash

We found that by writing the InnoDB data dictionary cache in the above two ways, we can effectively ensure that the cache always has the latest data dictionary, so as to ensure the timeliness of the subsequent update of the index statistics table.

Index statistics table construction

Now, let’s finally take a look at how MySQL generates index statistics and updates index statistics.

MySQL updates index tables in two ways:

  1. Periodic update: The index statistics table is updated every 10 seconds.
  2. ANALYZE TABLEStatement: Manually execute this statement to update the index statistics table.

From the above explanation, we know that the basic information for the index statistics table comes from two InnoDB data dictionary caches: INNODB_SYS_TABLES cache and INNODB_SYS_INDEXES cache. Now let’s take a look at this scenario in conjunction with the periodic update of the index table:

  1. MySQL scans for all tablesINNODB_SYS_INDEXESThe list
  2. Indexes are read one by one to obtain basic index information
  3. Index statistics are calculated one by one based on the basic index information
  4. Writes a statistical entry to the index statistics table

Taking a closer look at this process, we can see that if INNODB_SYS_INDEXES has a linked table with more and more tables, early updated tables may take a long time to scan, resulting in a longer update period for the table and a slower update of statistical items for the table, which ultimately affects the performance of SQL queries related to the table. In this chapter “Introduction”, I said that the faster the index statistics are updated, the more accurate the statistics results are, and the more accurate the SQL execution plan is selected by MySQL based on the statistics results, and the more efficient the SQL execution is.

To solve this problem, MySQL introduced recalc_pool, which allows MySQL to always fetch the basic index information from the earliest table change, and then use this information to calculate the index statistics.

So, let’s look at this recalc_pool first.

recalc_pool

The recalc_pool structure is as follows:

Recalc_pool is a list that stores table ids. As shown in the figure above, the user table id is 40, t1 table ID is 45, and T2 table ID is 80.

The function of recalc_pool is as follows: Add the newly changed table-> ID to the end of recalc_pool. The scheduled task obtains the earliest changed table-> ID from recalc_Pool for index statistics.

Regularly update

Next, let’s look at the process of periodically updating the index statistics table.

Recalc_pool contains two main parts: adding table-> ID to recalc_pool and fetching table-> ID from RECalc_pool.

Add recalc_pool

Add table->id to recalc_pool;

If user A performs an insert operation on the user table and user B performs an update operation on the account table, MySQL will make the following judgment:

If the number of records in the changed table is greater than the total number of records in the table * 10%, then add the id of the table to recalC_pool.

Recalc_pool = recalc_pool = recalc_pool = recalc_pool = recalc_pool = recalc_pool = recalc_pool = recalc_pool

The update operation of the Account table affects only one record. Assume that the Account table has a total of 20 records and 1 < 20 * 10%. Therefore, as shown in the figure above, the ID of the Account table is not added to recalc_Pool.

Read recalc_pool

Select * from recalc_pool where table->id = id; select * from recalc_pool where table->id = id; select * from recalc_pool where table->id = id;

  1. Read the first table-> ID from recalC_pool, that is, read the user table id from head: 40.

  2. Read the user table object from table_ID_hash based on the USER table ID. That’s what we’re going to do in the table_ID_hash up here.

  3. If the current time – the last time the user table was counted > 10 seconds, update the index statistics. Otherwise, continue adding the USER table ID to the end of recalC_pool

  4. Update index statistics

    (1) Since all indexes of the user table have been updated to the user table object when triggering the index creation above, we can obtain all indexes of the table according to the user table object

    (2) Go through the linked list of the user table in INNODB_SYS_INDEXES cache, get each index, that is, the bottom left of the figure, read the primary index and index_age_birth index in turn, here I use index_age_birth index as an example, start to calculate the index statistics. In the compute section of the figure, we combine the statistics in the index table above to see the following calculation process:

    • Enable index_AGe_BIRTH index level MTR, about which I will discuss in how MySQL balances log write performance and data reliability? Explain in detail.

    • According to index_age_birth index ID, find the corresponding index tree in memory, that is, the lower right corner of the figure, calculate the number of total nodes in the index tree, write the number into stat_INDEx_size, so, the stat_INDEx_AGe_birth index stat_INDEx_size = 1

    • Find the corresponding index tree in memory according to index_age_birth index ID, that is, the lower right corner of the figure, calculate the number of leaf nodes of the index tree, and write the number into stat_n_leaf_pages. Therefore, the stat_n_leaf_pages of index_age_birth index = 1

    • According to index_age_birth index ID, find the corresponding index tree in memory, that is, the lower right corner of the figure, and calculate the number of leaf nodes of the index tree:

      • If index_age_birth number of leaves in the index tree < number of leaves sampled parameter * number of index columns, stat_n_sample_sizes is the number of leaves in the index tree. The number of leaves sampled is 20 by default and can be changed by adjusting the innodb_stats_persistent_sample_pages parameter. I’ll talk about changing methods later.

        For example, we now know that the total number of leaf nodes in the index_age_birth index tree is 1 by iterating through the index_age_birth index tree, so,

        • Index_age_birth Total number of leaves 1 < 20 * 1, where 1 on the right represents 1 index column age, so stat_n_SAMple_sizes of age is 1

        • Index_age_birth Total number of index leaves 1 < 20 * 2, where 2 on the right represents one index column group (age,birthday), so stat_n_sample_sizes of age,birthday is 1

        • Index_age_birth Total number of index leaves 1 < 20 * 3, where 3 on the right represents one index column group (age,birthday, ID), so stat_n_SAMple_sizes of this index column group (age,birthday,id) is 1

    • According to index_age_birth index ID, find the corresponding index tree in memory, that is, the lower right corner of the figure, scan the linked list of all leaf node records:

      • Index_age_birth = 1->2->3(age, age,birthday, age,birthday,id)

        • If the number of matching columns for the previous record and the last record is less than 1, the values of the two records in the AGE column are different, and stat_n_DIFF_KEY_VALS [0] + 1

        • Stat_n_diff_key_vals [1] + 1 if the number of matching columns for the previous record and the last record is less than 2, the values of the two records on the age and birthday column combinations are different.

        • If the number of matching columns for the previous record and the last record is less than 3, the values of the two records in the age,birthday, and ID column combinations are different, and stat_n_DIFF_KEY_VALS [2] + 1 is displayed

    • Stat_n_diff_key_vals [0] = 6

      stat_n_diff_key_vals[1] = 9

      stat_n_diff_key_vals[2] = 10

    • Close the index_AGe_BIRTH index level MTR

  5. Update the n_leaf_pages, SIZE, SAMple_size, and n_diff_pfxNN to the index statistics table based on the mapping between the following statistics items, that is, write the statistics table on the right of the figure.

    stat_index_size => size

    stat_n_leaf_pages => n_leaf_pages

    stat_n_sample_sizes => sample_size

    stat_n_diff_key_vals[0] => n_diff_pfx01

    stat_n_diff_key_vals[1] => n_diff_pfx02

    stat_n_diff_key_vals[2] => n_diff_pfx03

ANALYZE TABLE

This method is to manually trigger and execute the two steps described in the section of Periodic Updates, updating index statistics and persisting index statistics.

For example, let’s see how to update an index table with this statement:

ANALYZE TABLE user;
Copy the code
Parameter configuration

Now let’s return to a question mentioned in The Introduction: for the query cost analysis based on index statistics, if we can increase the number of sampling nodes, will the query cost be calculated more accurately?

The number of leaf nodes sampled is determined by the MySQL parameter innodb_stats_persistent_sample_pages. If this parameter is increased, the number of leaf nodes sampled is determined by the innodb_stats_persistent_sample_pages. You can ensure that the statistical items in the index statistics table are calculated accurately, thus enabling MySQL to choose the execution plan more correctly.

The adjustment mode is as follows:

SET GLOBAL innodb_stats_persistent_sample_pages=30;
Copy the code

summary

This chapter explains in detail the process of building index statistics before analyzing the query cost based on index statistics. Through this process, you should know the following:

  1. Two core data dictionary tables: INNODB_SYS_TABLES and INNODB_SYS_INDEXES

    The name of the table instructions
    INNODB_SYS_TABLES MySQL > store basic information about all tables in MySQL
    INNODB_SYS_INDEXES MySQL > select * from ‘MySQL’ where ‘MySQL’ is stored

  2. Two core data dictionary table caches: INNODB_SYS_TABLES cache and INNODB_SYS_INDEXES cache

    Cache name instructions
    INNODB_SYS_TABLES cache There are three main structures: table_hash, table_ID_hash, and table_LRU
    INNODB_SYS_INDEXES cache MySQL maintains a two-way linked list for each table index

  3. Index Tables

    The index statistics table stores the index statistics generated by MySQL. When you look at this table, it seems to be similar to “Why did MySQL choose to execute plan A instead of PLAN B?” The statistics for this part of the query based on index statistics are not the same, but in fact, the latter is derived from the former, so they are statistically the same.

  4. The process of building two core data dictionary table caches

    Build a way instructions
    Build when the table is created Building the INNODB_SYS_TABLES cache is triggered when tables are created
    Built when an index is created Building the INNODB_SYS_INDEXES cache is triggered when an index is created
    Build on MySQL restart When MySQL restarts, INNODB_SYS_TABLES and INNODB_SYS_INDEXES are fully loaded into the cache

  5. The process of building index tables

    • Recalc_pool: a list of tables -> ids. Add the newly changed table-> ID to the end of recalc_pool. The scheduled task obtains the earliest changed table-> ID from the recalC_pool header for index statistics

    • The build process

      process instructions
      Regularly update The index statistics table is updated every 10 seconds
      ANALYZE TABLE Manually execute this statement to update the index statistics table once

    • Parameter configuration

      parameter role
      innodb_stats_persistent_sample_pages Change this parameter to change the number of leaves in the MySQL sampling index tree

To consider

In the Periodic Updates section, one of the steps is the process of calculating STAT_n_sample_sizes, where I show how to calculate stat_n_sample_sizes when the total number of leaves in the index tree < the number of leaves sampled parameter * the number of index columns.

Stat_n_sample_sizes = total leaves > number of leaves sampled * number of index columns

Why did MySQL choose plan A over Plan B? See how to answer this question by referring to the process of querying cost analysis based on scan index trees.