The original address

  1. MySQL index principle and slow query optimization: tech.meituan.com/2014/06/30/…
  2. Explain: blog.csdn.net/qq_38975553…
  3. BTree and B+Tree blog.csdn.net/weixin_4194…

The index overview

Definition: An index is a data structure used by a storage engine to quickly find records. For example: if you are looking for a specific topic in a book, you will usually start with the table of contents (similar to an index) of the book and find the corresponding page. In MySQL, the storage engine uses indexes in a similar way to efficiently retrieve the data it seeks.

Classification of indexes

1) Partition from storage structure

  • Btree index (B+tree, b-tree)
  • The hash index
  • Full-index Indicates the full-text index

2) From the application level

  • Normal index: that is, an index contains only a single column. A table can have multiple single-column indexes.
  • Unique index: The value of the indexed column must be unique, but empty values are allowed.
  • Composite index: An index contains multiple columns.

3) Divide from the order of the table records and the order of the index is consistent

  • Clustered index: Table records are arranged in the same order as indexes.
  • Nonclustered index: Table records are not in the same order as indexes.

Index the underlying data structure

Disk I/O and prefetch

The data stored in a database is stored on disks. When searching for data, you need to load the data on disks into the memory. Before introducing the implementation of indexes, learn about disk I/O and prefetch.

Disk data reading depends on mechanical movement, and the time spent on each data reading can be divided into three parts: seek time, rotation delay, and transmission time. Seek time refers to the time required for the magnetic arm to move to the specified track, and the mainstream disk is generally less than 5ms. For example, if a disk is 7200 RPM, it can rotate 7200 times per minute. That is to say, it can rotate 120 times per second. The rotation delay is 1/120/2 = 4.17ms. Transfer time refers to the time it takes to read or write data from or to the disk, usually in the order of a few tenths of a millisecond and negligible compared to the first two. So the time to access a disk, namely the time to access a disk IO, is about 5+ 4.17 = 9ms, which sounds good, but remember that a 500-mips machine can execute 500 million instructions per second, because instructions rely on electrical properties, in other words, the time to execute an IO can execute 400,000 instructions. A database with hundreds of millions or even tens of millions of data, nine milliseconds at a time, is a disaster.

The following is a comparison of computer hardware delay for your reference:

Considering the disk IO is a very expensive operation, computer operating system made some optimization, when an I/o, not only the current disk address data, but the adjacent data are read into memory buffer, because local pre-reading sex principle tells us that when the computer access to an address data, the adjacent will soon be access to data. Each IO read is called a page. The specific data size of a page depends on the operating system, and it is usually 4K or 8K. In other words, when we read the data in a page, we actually only have one IO. This theory is very helpful for the data structure design of the index.

B-tree and B + Tree

B-tree

B-tree is a balanced search Tree designed for external storage devices such as disks.

Data in the B-tree structure enables the system to efficiently locate the disk block where the data resides. To describe a B-tree, first define a record as a binary group [key, data]. Key is the key value of the record, corresponding to the primary key value in the table, and data is the data in a row except the primary key. The key values are different for different records.

An M-level B-tree has the following characteristics:

  1. Each node has at mostmChild node
  2. Each non-leaf node (except root node) has at least ⌈m/2⌉ Child node
  3. If the root node is not a leaf node, it has at least two child nodes
  4. There arekNon-leaf nodes of child nodes are ownedk– a key
  5. All the leaf nodes are in the same layer

Each node in the B-tree can contain a large number of keyword information and branches according to the actual situation. The following figure shows a third-order B-tree:

Each node occupies the disk space of a disk block. A node has two keywords in ascending order and three Pointers to the child root node. The Pointers store the address of the disk block where the child node resides. The three scope fields divided into two keywords correspond to the scope fields of the data of the subtree pointed to by the three Pointers. For the root node, the keywords are 17 and 35. The data range of the subtree to which the P1 pointer points is less than 17, the data range of the subtree to which the P2 pointer points is 17-35, and the data range of the subtree to which the P3 pointer points is greater than 35.

Simulate the process of finding keyword 29:

  1. Locate disk block 1 based on the root node and read it into memory. [Disk I/O operation 1]

    Compare keyword 29 in interval (17, 35) to find pointer P2 to disk block 1.

  2. Locate disk block 3 according to P2 pointer and read into memory. [Disk I/O operation 2nd]

    Compare keyword 29 in interval (26, 30) to find pointer P2 to disk block 3.

  3. Locate disk block 8 according to P2 pointer and read into memory. [Disk I/O operation 3]

    Find keyword 29 in the keyword list in disk block 8.

Analyzing the above procedure, we found that three disk I/O operations and three memory lookups were required. Since the keyword in memory is an ordered table structure, dichotomy lookup can be used to improve efficiency. Three disk I/O operations affect the efficiency of the entire B-tree search. Compared with AVLTree, B-tree reduces the number of nodes, so that each disk I/O data from memory plays a role, thus improving the query efficiency.

B+Tree

B+Tree is an optimization based on B-Tree. InnoDB storage engine uses B+Tree to achieve its index structure.

In a B+Tree, all data record nodes are stored on the leaf nodes at the same layer according to the order of key values, instead of the non-leaf nodes only storing key values. This greatly increases the number of key values stored on each node and reduces the height of the B+Tree.

Since the non-leaf nodes of B+Tree only store key value information, assuming that each disk block can store four key value and pointer information, the structure of B+Tree is as follows:

Principles of indexing

  1. A = 1 and b = 2 and C > 3 and d = 4; a = 2 and C > 3 and d = 4; D (a,b,d,c); d (a, B,d,c); d (a, B,d);

  2. = and in can be out of order, such as a = 1 and b = 2 and c = 3. Create (a,b,c) indexes in any order. Mysql’s query optimizer will help you optimize them into a form that can be recognized by the indexes.

  3. Try to select columns with high distinctness as the index. The distinctness formula is count(DISTINCT Col)/count(*), which indicates the proportion of fields that are not duplicated. The larger the ratio is, the fewer records we scan. Is there any rule of thumb for this ratio? This value is also difficult to determine in different application scenarios. Generally, we require join fields to be above 0.1, that is, 10 records are scanned per item on average.

  4. From_unixtime (create_time) = ‘2014-05-29’; from_unixtime(create_time) = ‘2014-05-29’; from_unixtime(create_time) = ‘2014-05-29’; Obviously the cost is too great. The statement should be create_time = unix_TIMESTAMP (‘ 2014-05-29 ‘).

  5. Expand indexes as much as possible, do not create new ones. For example, if you want to add (a,b) to a table that already has an index of A, you only need to modify the original index.

Slow query optimization basic steps

  1. Run it first to see if it’s really slow, and set SQL_NO_CACHE
  2. Lock the minimum return record table. Select * from table where the smallest number of entries is returned. Select * from table where the smallest number of entries is returned. Select * from table where the smallest number of entries is returned
  3. Explain to see if the execution plan is consistent with 2 expectations (start with tables with fewer locked records)
  4. SQL statements in the form of order by limit give precedence to sorted tables
  5. Understand the application scenarios of the service side
  6. When adding an index, follow the principles of building an index
  7. Observed results that do not conform to expectations continue from 0 analysis

Explain,

Explain provides execution plan information for mysql statements. Can be applied to SELECT, DELETE, INSERT, UPDATE, and place statements. The explain execution plan is only a reference to the execution process. The actual execution process may not be exactly the same as the plan, but the information revealed in the execution plan can help select better indexes and write more optimized query statements.

The explain output item

Column JSON Name Meaning
id select_id The SELECT identifier
select_type None The SELECT type
table table_name The table for the output row
partitions partitions The matching partitions
type access_type The join type
possible_keys possible_keys The possible indexes to choose
key key The index actually chosen
key_len key_length The length of the chosen key
ref ref The columns compared to the index
rows rows Estimate of rows to be examined
filtered filtered Percentage of rows filtered by table condition
Extra None Additional information

id

The id column is numbered as the sequence number of the select, and the number of ids increases in the order in which the select appears.

MySQL classifies select queries into SIMPLE and PRIMARY queries. Complex queries fall into three categories: simple subqueries, derived tables (subqueries in from statements), and Union queries.

The larger the ID column is, the higher the execution priority is. If the IDS are the same, the execution is performed from the top down. If the ID is NULL, the execution is performed last.

select_type

Select_type indicates whether the corresponding row is a simple or complex query.

table

This column indicates which table is being accessed by the EXPLAIN row.

When there is a subquery in the FROM clause, the table column is format, indicating that the current query depends on the query id=N, so the query id=N is executed first.

When there is a union, the value of the table column of the Union RESULT is <union1, 2>, and 1 and 2 represent the IDS of the select rows participating in the union.

partitions

type

This column represents the association type or access type, which is the approximate range of data row records that MySQL determines how to find rows in the table.

From the best to the worst: system > const > eq_ref > ref > range > index > ALL

  • NULL: mysql can decompose the query during the optimization phase without accessing the table or index during the execution phase. For example, if you select a minimum value in the index column, you can do this by looking up the index separately without accessing the table during execution.
  • Const, system: mysql can optimize part of a query and convert it to a constant (see the result of show Warnings). Select * from primary key; select * from constant; select * from primary key; System is a special case of const; it is system if only one tuple in the table matches
  • Eq_ref: All parts of the primary key or unique key index are joined, and at most one qualifying record is returned. This is probably the best type of join besides const, and it does not appear in simple SELECT queries.
  • Ref: Compared with eq_ref, it does not use a unique index. Instead, it uses a normal index or a partial prefix of a unique index. The index is compared with a value, and multiple rows may be found that match the condition.
  • The range scan is usually performed in(), between, >, <, >=, etc. Use an index to retrieve rows in a given range.
  • Index: Scans ALL table indexes. This is usually faster than ALL. (Index is read from the index, while all is read from the hard disk)
  • ALL: indicates a full table scan, which means that mysql needs to look for rows from beginning to end. Normally this would need to be optimized by adding an index

possible_keys

This column shows which indexes the query might use to look up.

Possible_keys may have columns while key is NULL when explaining possible_keys. In this case, it is because there is not much data in the table. Mysql thinks that the index is not helpful for the query and selects the full table query.

If the column is NULL, there is no associated index. In this case, you can improve query performance by examining the WHERE clause to see if you can create an appropriate index, and then using Explain to see the effect.

key

This column shows which index mysql actually uses to optimize access to the table.

If no index is used, the column is NULL. If you want to force mysql to use or ignore indexes in the possible_keys column, use force index and ignore index in the query.

key_len

This column shows the number of bytes used by mysql in the index. This value can be used to figure out which columns are used in the index.

ref

This column shows the columns or constants used by the table to find values in the index of the key column. Common examples are const (constant), field names (e.g. Film.id).

rows

This column is the number of rows that mysql expects to read and detect, note that this is not the number of rows in the result set.

filtered

Extra

  • Using index: The column of the query is overwritten by the index, and the WHERE filter condition is the leading column of the index (the leftmost index), which is high performance. Typically, an overwrite index is used (the index contains all the fields of the query). For InnoDB, secondary indexes can improve performance.

  • Using WHERE: The query column is not covered by the index. Where filters the leading column that is not the index.

  • Using WHERE Using index: the column in the query is overwritten by the index, and the where filter condition is one of the index columns but not the leading column of the index.

  • NULL: the column in the query is not covered by the index, and the WHERE filter condition is the leading column of the index. This means that the index is used, but some columns are not covered by the index.

  • Using index condition: Similar to Using WHERE, the column of the query is not completely covered by the index. The where condition is a range of leading columns.

  • Using temporary: mysql needs to create a temporary table to process queries. This situation is generally to optimize, the first is to think of using indexes to optimize.

  • Using filesort: mysql uses an external index sort on the results, rather than reading rows from the table in index order. At this point, mysql will browse all eligible records based on the join type, save the sort key and row pointer, then sort the key and retrieve the row information in order. In this case, index optimization is also generally considered.

Case analysis

1. Writing of complex statements

In many cases, we write SQL just to implement the function. This is just the first step. There is a fundamental difference in the efficiency of different statement writing methods.

select
    distinct cert.emp_id
from
    cm_log cl
    inner join (
        select
            emp.id as emp_id,
            emp_cert.id as cert_id
        from
            employee emp
            left join emp_certificate emp_cert on emp.id = emp_cert.emp_id
        where
            emp.is_deleted = 0
    ) cert on (
        cl.ref_table = 'Employee'
        and cl.ref_oid = cert.emp_id
    )
    or (
        cl.ref_table = 'EmpCertificate'
        and cl.ref_oid = cert.cert_id
    )
where
    cl.last_upd_date >= 'the 2013-11-07 15:03:00'
    and cl.last_upd_date <= 'the 2013-11-08 16:00:00';
Copy the code
  1. Run first, 53 records 1.87 seconds, and did not use aggregate statements, relatively slow
   53 rows in set (1.87 sec)
Copy the code
  1. explain

Mysql > select * from idx_last_upd_date; select * from idx_last_upd_date; select * from idx_last_upd_date; Then table lookup scanned 63,727 records, divided into two parts. Derived, meaning a table that doesn’t exist, is simply the result set of a statement, followed by a number indicating the ID of the statement. Derived2 indicates that the query with ID = 2 constructed a virtual table and returned 63727 records. SQL > select * from EMPLOYEE where emp_CERTIFicate_EMPID from EMPLOYEE where emp_certificate_empID from EMPLOYEE where emp_certificate_empID from EMPLOYEE where emp_certificate_empID from EMPLOYEE where emp_certificate_empID from EMPLOYEE where emp_certificate_EMPID from EMPLOYEE where emp_certificate_EMPID from EMPLOYEE where emp_certificate_EMPID from EMPLOYEE where emp_certificate_EMPID from EMPLOYEE where emp_certificate from EMPLOYEE Each association locks only one record, which is efficient. Then, 379 records of cm_log are associated according to rules. As you can see from the execution, too much data is returned and most of the returned data is not used by cm_log, because cm_log only locks 379 records.

How do you optimize it? As you can see, we still want to join cm_log after running. Can we join cm_log before running? If the ref_table of cm_log is EmpCertificate, then the emp_certificate table will be associated. If the ref_table of cm_log is Employee, then the Employee table will be associated. Join them with a union. Notice that you use union instead of union all because the original statement has “distinct” to get a unique record, and unions do just that. If there is no distinct in the original statement, we can directly use union all, because the action of union removal will affect SQL performance.

The optimized statement is as follows:

   select
       emp.id
   from
       cm_log cl
       inner join employee emp on cl.ref_table = 'Employee'
       and cl.ref_oid = emp.id
   where
       cl.last_upd_date >= 'the 2013-11-07 15:03:00'
       and cl.last_upd_date <= 'the 2013-11-08 16:00:00'
       and emp.is_deleted = 0
   union
   select
       emp.id
   from
       cm_log cl
       inner join emp_certificate ec on cl.ref_table = 'EmpCertificate'
       and cl.ref_oid = ec.id
       inner join employee emp on emp.id = ec.emp_id
   where
       cl.last_upd_date >= 'the 2013-11-07 15:03:00'
       and cl.last_upd_date <= 'the 2013-11-08 16:00:00'
       and emp.is_deleted = 0
Copy the code

  1. You do not need to know the service scenario, but only need to modify the statement to be the same as the original statement

  2. Existing indexes can be satisfied, no need to create an index

  3. To experiment with the modified statement, it takes only 10ms to reduce by nearly 200 times!

2. Determine the application scenario

The purpose of this example is to overturn our perception of the distinctiveness of columns. In general, we think that the more distinguishable the column, the easier it is to lock fewer records, but in some special cases, this theory is limited.

select
  *
from
  stage_poi sp
where
  sp.accurate_result = 1
  and (
      sp.sync_status = 0
      or sp.sync_status = 2
      or sp.sync_status = 4
  );
Copy the code
  1. Let’s take a look at how long it takes. 951 pieces of data, 6.22 seconds.
951 rows in set (6.22 sec)
Copy the code
  1. Rows = 3.61 million; type = ALL;

  1. All fields are applied to the number of records returned by the query, because 951 records have been done by the single-table query 0.

  2. Keep explain rows as close to 951 as possible.

    Accurate_result = 1

select count(*),accurate_result from stage_poi group by accurate_result; +----------+-----------------+ | count(*) | accurate_result | +----------+-----------------+ | 1023 | -1 | | 2114655 | 0 | | 972815 | 1 | + -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- +Copy the code

We can see that the discriminability of accurate_result is very low. The whole table has only -1, 0 and 1 values, and a very small amount of data cannot be locked even with the index.

Look again at the sync_STATUS field:

select count(*),sync_status from stage_poi  group by sync_status;
+----------+-------------+
| count(*) | sync_status |
+----------+-------------+
|     3080 |           0 |
|  3085413 |           3 |
+----------+-------------+
Copy the code

The same distinction is low and, according to theory, not suitable for indexing.

If sync_status 0 and 3 are evenly distributed, the locking records will be in millions. If sync_status 0 and 3 are evenly distributed, the locking records will be in millions.

Communicate with the business side to see the usage scenario. The business side uses the SQL statement like this. Every five minutes, the business side scans the qualified data and changes the sync_STATUS field to 1. The number of qualified records in five minutes is not too many, about 1000. Once you understand the usage scenarios of the business side, it becomes easy to tune this SQL because the business side ensures that the data is unbalanced, and indexes can filter out most of the data that is not needed.

  1. According to the index building rule, use the following statement to create an index
alter table stage_poi add index idx_acc_status(accurate_result,sync_status);
Copy the code
  1. Looking at the expected results, we found that it only takes 200ms, which is more than 30 times faster.
952 rows in set (0.20 sec)
Copy the code

We look back at some problem analysis, the process of the single table query is relatively good optimization, most of the time just need to put field in accordance with the rules of the where condition inside index is good, if only this “mindless” optimization, obviously some very low degree of differentiation, should not be indexed columns will be combined with index, This can have a serious impact on insert and update performance, and may affect other queries. Therefore, the use scenario of SQL in step 4 is very critical. Only when we know this business scenario, can we better assist us to better analyze and optimize the query statement.

3. Statements that cannot be optimized

select
   c.id,
   c.name,
   c.position,
   c.sex,
   c.phone,
   c.office_phone,
   c.feature_info,
   c.birthday,
   c.creator_id,
   c.is_keyperson,
   c.giveup_reason,
   c.status,
   c.data_source,
   from_unixtime(c.created_time) as created_time,
   from_unixtime(c.last_modified) as last_modified,
   c.last_modified_user_id
from
   contact c
   inner join contact_branch cb on c.id = cb.contact_id
   inner join branch_user bu on cb.branch_id = bu.branch_id
   and bu.status in (1.2)
   inner join org_emp_info oei on oei.data_id = bu.user_id
   and oei.node_left >= 2875
   and oei.node_right <= 10802
   and oei.org_category = - 1
order by
   c.created_time desc
limit
   0.10;
Copy the code

Again, a few steps.

  1. Let’s look at how long the statement took to run. The 10 records took 13 seconds, which is unbearable.
10 rows in set (13.06 sec)
Copy the code

  1. explain

    Select * from org_emp_info where idx_userid_STATUS = branch_user and idx_branch_id = contact_branch; select * from org_emp_info where idx_branch_id = contact_branch; Finally, the primary key associates the Contact table.

    Rows returns very little and you can’t see anything unusual. Order by + limit = order by + limit So let’s simplify the SQL and remove the order by and limit to see how many records are used to sort.

select
 count(*)
from
  contact c  
inner join
  contact_branch cb 
     on  c.id = cb.contact_id  
inner join
  branch_user bu 
     on  cb.branch_id = bu.branch_id 
     and bu.status in (
        1.2)  
  inner join
     org_emp_info oei 
        on  oei.data_id = bu.user_id 
        and oei.node_left >= 2875 
        and oei.node_right <= 10802 
        and oei.org_category = - 1  

+----------+
| count(*) |
+----------+
|   778878 |
+----------+
1 row in set (5.19 sec)
Copy the code

We found that 778,878 records were locked before sorting, and it would be disastrous if we sorted for 700,000 result sets. No doubt it is so slow. Can we change our thinking and sort first by created_time of contact and then join?

This was transformed into the following statement, which could also be optimized with straight_join:

select
   c.id,
   c.name,
   c.position,
   c.sex,
   c.phone,
   c.office_phone,
   c.feature_info,
   c.birthday,
   c.creator_id,
   c.is_keyperson,
   c.giveup_reason,
   c.status,
   c.data_source,
   from_unixtime(c.created_time) as created_time,
   from_unixtime(c.last_modified) as last_modified,
   c.last_modified_user_id
from
   contact c
where
   exists (
       select
           1
       from
           contact_branch cb
           inner join branch_user bu on cb.branch_id = bu.branch_id
           and bu.status in (1.2)
           inner join org_emp_info oei on oei.data_id = bu.user_id
           and oei.node_left >= 2875
           and oei.node_right <= 10802
           and oei.org_category = - 1
       where
           c.id = cb.contact_id
   )
order by
   c.created_time desc
limit
   0.10;
Copy the code

Verify the effect is expected to improve more than 13,000 times in 1ms!

10 rows in set (0.00 sec)
Copy the code

Sort before join is the same as join before sort. The cost of joining before sort is the same. The general implementation process is as follows: Mysql selects the first 10 entries by index, and then performs join filtering. When it finds that there are less than 10 entries, it performs 10 entries again and joins again. This will be a disaster if there are too many entries in the inner join filtering. Almost traversed the table!

SQL tests with different parameters:

select
  sql_no_cache c.id,
  c.name,
  c.position,
  c.sex,
  c.phone,
  c.office_phone,
  c.feature_info,
  c.birthday,
  c.creator_id,
  c.is_keyperson,
  c.giveup_reason,
  c.status,
  c.data_source,
  from_unixtime(c.created_time) as created_time,
  from_unixtime(c.last_modified) as last_modified,
  c.last_modified_user_id
from
  contact c
where
  exists (
      select
          1
      from
          contact_branch cb
          inner join branch_user bu on cb.branch_id = bu.branch_id
          and bu.status in (1.2)
          inner join org_emp_info oei on oei.data_id = bu.user_id
          and oei.node_left >= 2875
          and oei.node_right <= 2875
          and oei.org_category = - 1
      where
          c.id = cb.contact_id
  )
order by
  c.created_time desc
limit
  0.10;

Empty set (2 min 18.99 sec)
Copy the code

2 min 18.99 SEC! It’s much worse than it was before. Due to the nested loop mechanism of mysql, this situation cannot be optimized. This statement is ultimately left to the application system to optimize its logic.

As we can see from this example, not all statements can be optimized, and often when we optimize, the consequences can be worse than the original because the SQL use case regression leaves out some extreme cases. So, one: don’t expect all statements to be SQL optimized, and two: don’t be too confident and optimize for a specific case, ignoring more complex cases.

Slow query case analysis to here, the above is just some more typical cases. In the process of optimization, we encountered “garbage SQL” with more than 1000 rows and 16 table joins. We also encountered the difference between online and offline databases, which led to the application being directly dragged to death by slow query. We also encountered vARCHAR equivalence comparison without single quotation marks, and cartesian product query directly killed the slave library. No matter how many cases there are, it’s just a matter of experience, and if we’re familiar with the inner workings of the query optimizer and indexes, it’s easy to analyze them.