takeaway

Let’s review the structure of the dating platform 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`),
  KEY `index_un_age_sex` (`user_name`,`age`,`sex`),
  KEY `index_age_sex` (`age`,`sex`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
Copy the code

Set user_introduction to varchar(498) and add other fields. The length of a single entry may be large. In this case, if you execute the following SQL:

select user_id, user_name, user_introduction from user where age > 20 and age < 50
Copy the code

Suppose the user table already contains 300w records and executes the SQL above. What happens?

Those who have a preliminary understanding of MySQL must know Query Cache. Its function is to Cache Query results. By establishing the mapping relationship between SQL and results in the first Query, the Query Cache can be hit when the same SQL is queried again, so as to improve the efficiency of the subsequent same Query.

Therefore, for the above SQL Query, MySQL can write the Query result to the Query Cache after the first execution of the SQL, and then retrieve the result from the Query Cache the next time the same SQL is executed.

However, have you ever wondered if more than 10W of the number of users that satisfy the Query condition can be fully written into the Query Cache?

Today, I’ll start with the structure of Query Cache and reveal the answer gradually.

In The Introduction, I mentioned that MySQL realized fast hit of the query by establishing the mapping relationship between SQL and query results. Then, the problem comes: in order to realize such a mapping relationship, there must be a structure to bear such a relationship! So, what structure does MySQL use to host such mappings?

Maybe you’ve already thought of it: HashMap! Yes, MySQL does use HashMap to express the mapping between SQL and result sets. Then it’s easy to figure out what the keys and values of this HashMap are.

  • Key: used by MySQLquery + database + flagForm a key. The structure of this key is straightforward, it indicates which SQL from which library is usedQuery Cache.
  • Value: MySQL uses a name calledquery_cache_blockAs the Map value, this structure holds the results of an SQL query.

Query Cache Block

So how do you store the results of an SQL query in a Query_cache_block? Let’s take a look at the structure of a Query_cache_block in conjunction with the SQL from The Introduction:

As the figure above shows, a Query_cache_block consists of three core fields:

  • Used: Specifies the size of the result set. MySQL obtains the result set from the block offset in memory + this size. As shown in the figure above, suppose the SQL query result in Guide is <10001, Jack, I’m Jack>, then, used is the size of the query result.

  • Type: indicates the type of Block. These types include {FREE, QUERY, RESULT, RES_CONT, RES_BEG, RES_INCOMPLETE, TABLE, INCOMPLETE}. I’ll focus on QUERY and RESULT here, but you can explore the other types on your own.

    • QUERY: Indicates that this block contains a QUERY statement. Why cache queries?

      In the concurrent scenario, multiple sessions may execute the same Query statement. Therefore, MySQL Cache the Key of the Query statement to avoid repeated construction of the Key of the HashMap described in The Guidance.

    • RESULT: Indicates that the block stores the query RESULT. As shown in the figure above, the SQL query RESULT <10001, Jack, I’m Jack> is put into block, so the block type is RESULT.

  • N_tables: indicates the number of tables used by the query statement. So why does the block store the number of tables?

    N_tables field n_tables field n_tables field N_tables field N_tables field N_tables field N_tables field N_tables field

So now we know the structure of a Query_cache_block, which I’ll just call block for short.

Here’s a scenario:

If a block has a size of 1KB and a result of 10W is recorded, it has a size of 1MB. If a block has a size of 1MB, it has a size of 1MB and a result of 10W, it has a size of 1MB.

In order to cache 1MB query results, MySQL designed a bidirectional linked list, linking multiple blocks together, and placing 1MB data in each block of the linked list. Thus, we have the following structure: logical block list.

In the figure, MySQL concatenates multiple blocks through a two-way linked list. Each block is the block structure I described above. Two-way linked lists allow us to concatenate the result sets of a query statement.

For example, for the SQL query results in Introduction, in the figure, the first two blocks respectively store two results that meet the query conditions: <10001, Jack, I’m Jack> and <10009, Lisa, I’m Lisa>. At the same time, the two blocks are concatenated by bidirectional Pointers.

If the query result is <10001, Jack, I’m Jack> and the record size is only 100 bytes, then the query result is smaller than the block size. If you put this query in 1K blocks, you will waste 1024-100=924 bytes of block space. So, to avoid wasting block space, MySQL introduces a new structure:

As shown in the figure above, the physical block below is a new structure introduced by MySQL to solve block space wastage. The structure is also a bidirectional linked list composed of multiple blocks.

Take the SQL in “Introduction” as an example, it is known that the result of SQL query is <10001, Jack, I’m Jack>, then how to express the result in the block by combining the logical block linked list with the physical block linked list?

  • As shown above, the first block of the logical block list is stored<10001, Jack, I'm Jack>The result of this query.
  • As the size of the query result is 100B, which is less than 1K of the size of the block, MySQL splits the first block in the logical block list and divides the following two physical blocks, namely the red arrow part<10001, Jack, I'm Jack>This result goes into the first physical block. The size of the first physical block is 100B, and the size of the second physical block is 924B.

Now that WE’re done with query_cache_block, I think you have a clearer idea. However, I have mentioned the size of a block many times above, so how is the size of the block determined? Why is the block size 1K, not 2K, or 3K?

To answer this question, we need to look at MySQL’s memory management of blocks. To manage blocks, MySQL has designed its own memory-management mechanism called query_cache_Memory_bin.

Let me talk more about this query_cache_Memory_bin.

Query Cache Memory Bin

Query_cache_memory_bin (bin for short) Query_cache_memory_bin

Description:

  • Steps: is the floor number, as shown in the picture above. It is divided into 4 floors from top to bottom: 0, 1, 2 and 3.

  • Bin: Each layer consists of multiple bin. Bin contains the following properties:

    • Size: indicates the size of the bin

    • Free_blocks: list of free Query_cache_blocks. Each bin contains a set of query_cache_blocks, namely a logical Block list and a physical Block list, which I described in Query Cache Block to form a set of Query_cache_blocks.

    • The number of bin in each layer can be calculated by the following formula:

      Bin number = Total number of previous bin + QUERY_CACHE_MEM_BIN_PARTS_INC) * QUERY_CACHE_MEM_BIN_PARTS_MUL

      QUERY_CACHE_MEM_BIN_PARTS_INC = 1 and QUERY_CACHE_MEM_BIN_PARTS_MUL = 1.2

      Therefore, as shown in the figure above, the number of bin of each layer is as follows:

      • Layer 0: The number of bin is 1
      • Layer 1: The number of bin is 2
      • Layer 2: The bin number is 3
      • Layer 3: The number of bin is 4

    • Each layer has a fixed size. The calculation formula for this size is as follows:

      The size of layer 0 = QUERy_cache_size >> QUERY_CACHE_MEM_BIN_FIRST_STEP_PWR2 >> QUERY_CACHE_MEM_BIN_STEP_PWR2

      Size of remaining layer = size of previous layer >> QUERY_CACHE_MEM_BIN_STEP_PWR2

      QUERY_CACHE_MEM_BIN_FIRST_STEP_PWR2 = 4 and QUERY_CACHE_MEM_BIN_STEP_PWR2 = 2

      Therefore, assuming query_cache_size = 25600K, we can calculate the size of each layer as follows:

      • Level 0:400K
      • Level 1:100K
      • Layer 2:25K
      • Level 3:6K

    • The bin in each layer also has a fixed size, but it cannot be smaller than QUERY_CACHE_MIN_ALLOCATION_UNIT. The logarithmic approximation method is used to calculate the size of bin as follows:

      Bin size = layer size/number of bin in each layer

      QUERY_CACHE_MIN_ALLOCATION_UNIT = 512B

      Therefore, as shown in the figure above, the bin sizes of each layer are as follows:

      • Layer 0:400K / 1 = 400K
      • Layer 1:100K / 2 = 50K
      • Layer 2:25K / 3 = 9K, allocate size from the leftmost bin:
        • The first bin is 9K
        • The second bin: 8K
        • The third bin: 8K
      • Layer 3:6K / 4 = 2K, allocate size from the leftmost bin:
        • The first bin: 2K
        • The second bin: 2K
        • Bin 3:1K
        • The fourth bin: 1K

Query_cache_block = query_cache_block = query_cache_block Let me give you a brief illustration:

Since each bin contains a list of query_cache_blocks (logical and physical), if a block size is 1K, you can simply walk through the bin to find a bin larger than 1K and link that block to the free_blocks list in the bin. I’ll talk more about the process below.

After looking at the query_cache_block and query_cache_memory_bin structures, I think you have a clearer understanding of the data structures used in Query Cache processing. So, combining these two data structures, let’s look at several processing scenarios and implementation principles of Query Cache.

Cache writes

Let’s take a look at the process of writing to the Query Cache:

  1. Combined with the above HashMap Key structure, according to the query conditionsage > 20 and age < 50Construct the Key of a HashMap:age > 20 and age < 50 + user + flag.Flag contains the query result, writes the Key to the HashMap. As shown above, Result is the Key.
  2. According to the Result ofquery_cache_mem_binDo a binary search for the layer whose size is larger than the Result size. In the figure above, assume that layer 1 is the target layer found.
  3. If the bin size is larger than the Result size, select this bin to store the Result. If the bin size is larger than the Result size, select this bin to store the Result. If the bin size is larger than the Result size, select this bin to store the Result. Until a suitable bin is found. As shown in the gray bin above, the first bin in layer 2 is selected to store Result.
  4. According to Result, scan from left to right the logical block list of free_blocks in bin obtained from the previous step, and find the first block whose size is larger than that of Result. As shown in the figure above, find the second logical block.
  5. Assume that the Result size is 100B and the second logical block size is 1K. Since the block size is larger than the Result size, the logical block block is split into two physical blocks, in which the first physical block size after splitting is 100B. The second physical block size is 924B.
  6. Write the Result to the first physical block. As shown above, will<10001, Jack, I'm Jack>The Result is written to the gray physical block.
  7. Locate the corresponding block_table based on the Result block and update the table information to the block_table.

The Cache invalidation

When a table changes, all cached queries associated with that table become invalid. A TABLE changes and contains multiple statements, such as INSERT, UPDATE, DELETE, TRUNCATE TABLE,ALTER TABLE, DROP TABLE, or DROP DATABASE.

Query Cache Block Table

Query_cache_block_table Query_cache_block_table Query_cache_block_table The diagram below:

For example, if we join user with T_user_view (visitor table), we can query user visitor information. Then, in the figure, We assume that the logical block list store is the result of the join table query. Therefore, we see that the user table and T_user_view both point to the logical block list.

Let’s look at the core properties that this structure contains:

  • Block: A linked list of query_cache_blocks associated with a table. Query_cache_block_table for the user table. The block property in this block refers to a list of logical blocks. The first block in this list contains the SQL query result <10001, Jack, I’m Jack> in Guide.

  • MySQL > select * from user where user > t_user_view; MySQL > select * from user where user > t_user_view; MySQL > select * from user where user > t_user_view; To solve this problem, MySQL introduced a table to record view information, view source tables all point to this table to express table relationships. As shown in the figure above, user and T_user_View both point to user_View to indicate that the view corresponding to user and T_user_View is user_VIEW.

MySQL > Query_cache_block; MySQL > query_cache_block; MySQL > Query_cache_block; MySQL can quickly find query_cache_block by table name.

MySQL invalidates the Query Cache when a table changes.

Let’s take a look at the graph above, focusing on the red line:

  1. According to the user table to find its correspondingquery_cache_block_table. As shown above, find the second onetable block.
  2. According to thequery_cache_block_tableTo find the logical block list under the table. As shown in the figure above, the logical block list on the right is found.
  3. Traversing the logical block linked list and the physical block linked list under each logical block, releasing all blocks.

The Cache out

If there are not enough blocks in the Query_cache_mem_bin to hold the Result, then the query_cache_mem_bin’s memory elimination mechanism is triggered.

Here, let’s take a look at the elimination mechanism of the Query Cache.

  1. Combined with the above HashMap Key structure, according to the query conditionsage > 20 and age < 50Construct the Key of a HashMap:age > 20 and age < 50 + user + flag.Flag contains the query result, writes the Key to the HashMap. As shown above, Result is the Key.
  2. According to the Result ofquery_cache_mem_binDo a binary search for the layer whose size is larger than the Result size. In the figure above, assume that layer 1 is the target layer found.
  3. If the bin size is larger than the Result size, select this bin to store the Result. If the bin size is larger than the Result size, select this bin to store the Result. As shown in the gray bin above, the first bin in layer 2 is selected to store Result.
  4. According to Result, scan from left to right the logical block list in the block list in bin obtained in the previous step, and find the first block whose block size is larger than that of Result. As shown in the figure above, find the second logical block.
  5. Assume that the Result size is 100B and the second logical block size is 1K. Since the block size is larger than the Result size, the logical block block is split into two physical blocks, in which the first physical block size after splitting is 100B. The second physical block size is 924B.
  6. The first physical block is already occupied, so MySQL has to remove this block and put it in the Result.
    • The second physical block is found to be the least used. Therefore, this physical block and the first physical block are merged into a new block. As shown in the figure above, the gray block and the dotted block are merged to form a gray block below.
  7. Writes the Result to the merged physical block. As shown above, will<10001, Jack, I'm Jack>The Result is written to the merged gray block.

In the Cache elimination scenario, let’s focus on step 6. Let’s look at this scenario:

  1. The scan starts with the first physical block and merges the second block and the first block into a new block
  2. If the combined block size is still insufficient to store the Result, scan for the next block and repeat Step 1
  3. If the combined block size can store the Result, the scan is complete
  4. Writes Result to the merged block

From the above scenario, we find that if the Result is large, MySQL will continuously scan physical blocks and then continuously merge blocks, which is not small overhead. Therefore, we should try to avoid such overhead to ensure the performance of Query Cache Query.

Is there any way to avoid this expense?

I’ll answer that question in the final summary.

summary

Ok, I’ve covered a lot of ground in this post, and now let’s summarize what we’ve learned today:

  1. Data structure: Describes the data structure of Query Cache design:

    The data structure instructions
    Query_cache_block The result of an SQL query is stored
    Query_cache_mem_bin Memory management structure for query_cache_block
    Query_cache_block_table Each table corresponds to a block_TABLE, facilitating fast invalidation of query cache

  2. Query Cache processing scenarios: Cache write, Cache failure, and Cache obsolescence.

Finally, let’s return to the question at the beginning of this article: Can 10W user records be written to the Query Cache? My answer is:

  1. Let’s calculate the size of the 10W record in the user table:

    User_id (8), user_name(29), user_introduction(498), age(3), sex(1) If the length of a record is 8+30(vARCHAR can store 1 or 2 more bytes)+500+3+1= 542bytes, the maximum length of a 10W record is 542 x 10W = 54200000bytes.

    To write 10W records to the Query Cache, you need a Query Cache of approximately 54200K size to store 10W records. The default size of the Query Cache is 1M. Therefore, if the field “user_introduction” is not necessary for business, Remove this field from the select clause to reduce the size of the Query result set, so that the result set can be completely written to the Query Cache. ** This is why the DBA recommends not to use select. If the Query results can be completely written to the Query Cache, the performance of subsequent queries with the same Query conditions will be improved, 😁.

  2. Increase the query_cache_size parameter to 10W user records, or 54200K, if all fields are required to be selected and memory is sufficient.

  3. Increase the query_cache_min_res_unit parameter to minimize bin merges when MySQL first executes a Query and writes to the Query Cache. This reduces the merging cost of physical block lists. So how much of query_cache_min_res_unit is appropriate?

    This needs to be combined with the specific business scenarios, a comprehensive measure, for example, in the center of the users in the system, usually have the function of a member center, and the function of user Query their information is a high frequency of Query operation, in order to guarantee the Query performance of this kind of operation, we are bound to the Query results, namely the basic information of the individual users write the Query Cache, In the first part of my response, I said that the maximum length of a user record is 542bytes. Combined with the 54200K Query Cache required for 10W user records, it is appropriate to set query_cache_MIN_res_unit = 542bytes.

    This has two advantages:

    1. The bin size that can be directly allocated is larger than 542bytes to query the information of a single user, avoiding bin merging and space waste when writing the information of a single user.
    2. 10W user records are written to the Query Cache. Although the first time the Cache is allocated, the merge process is still required. However, in the case of a single user Query, the merge process is acceptable. You can directly take the merged bin and assign it to 10W records, and no more bin merges will occur, so this merge process is acceptable.

  4. Query_cache_limit specifies the maximum size of the Query Cache result set. The default value is 1 MB. Therefore, it is recommended to increase this parameter to 54200K for 10W records.

To consider

Finally, compared to “Tell the Interviewer I Can Optimize groupBy and Know It Deep! In this article, we find that MySQL especially likes to implement its own memory management, rather than using the Linux kernel’s memory management mechanism (e.g., partner system). Why?

The End

If you think it’s good, please like it!