Explanation of the principle of MySQL's leftmost matching principle

MYSQL | The principle of the leftmost matching principle

Left most matching principle

• The leftmost matching principle is that in a union index , If your SQL The leftmost index in the union index is used in the statement , So this one SQL Statement can use the union index to match . For example, a performance has an index (a,b,c), Now you have the following sentence ：

• select * from t where a=1 and b=1 and c =1;     # This can take advantage of the defined index （a,b,c）, use a,b,c
  ​
  select * from t where a=1 and b=1;     # This can take advantage of the defined index （a,b,c）, use a,b
  ​
  select * from t where b=1 and a=1;     # This can take advantage of the defined index （a,b,c）, use a,c（mysql There are query optimizers ）
  ​
  select * from t where a=1;     # You can also use the defined index （a,b,c）, use a
  ​
  select * from t where b=1 and c=1;     # You can't use the defined index （a,b,c）
  ​
  select * from t where a=1 and c=1;     # This can take advantage of the defined index （a,b,c）, But only a Indexes ,b,c I can't use the index 

• That is to say, through the leftmost matching principle, you can define a union index , But the index can be used in most query conditions . It is worth noting that , When it comes to range queries (>、<、between、like) Will stop matching . That is to say ：

• select * from t where a=1 and b>1 and c =1; # such a,b You can use （a,b,c）,c I can't use the index 

• This sentence has only a,b You'll use the index ,c You can't use indexes . This can be explained by the structure of the union index . But if it's building (a,c,b) Joint index , be a,b,c You can use indexes , Because the optimizer will automatically rewrite to the optimal query statement

• select * from t where a=1 and b >1 and c=1;  # If it's building (a,c,b) Joint index , be a,b,c You can use indexes 
  # The optimizer changes to 
  select * from t where a=1 and c=1 and b >1;

• This is also part of the leftmost prefix principle , Indexes index1:(a,b,c), I can only walk a、a,b、a,b,c Three types of queries , In fact, there is a problem here ,a,c Go too , But just go a Field index , Not going c Field .

•  In addition, there is a special case ,select * from table where a = '1' and b > ‘2’ and c='3'  This type of one will only have  a And b  Go to the index ,c Not going .

• select * from table where a = '1' and b > ‘2’ and c='3'

• This type of sql sentence , stay a、b After going through the index ,c It must be out of order , therefore c You can't go to the index , database I think it's better to scan the whole table c Fields come fast .

• With index （a,b,c） For example, building such an index is equivalent to building an index a、ab、abc Three indexes . One index top three indexes is certainly a good thing , After all, every additional index , Will increase the cost of write operations and disk space .

The principle of the leftmost matching principle

• The leftmost matching principle is for federated indexes , So we can understand the leftmost matching principle from the principle of joint index .

• We all know that the bottom of the index is a B+ Trees , Then, of course, the joint index is still a B+ Trees , It's just that the number of key values in a union index is not one , It's more than one. . Build a B+ Trees can only be built from one value , So the database is built on the leftmost field of the federated index B+ Trees . Example ： If you create a （a,b,c) Joint index of , So its index tree is like this ：

•  

• This is a picture of (a,b,c) Joint index b+ Trees , The non leaf node stores the index of the first keyword a, The leaf node stores the data of three keywords . You can see here a Is ordered , and b,c It's all out of order . But when a At the same time ,b Is ordered ,b At the same time ,c It's orderly again . Through the understanding of the structure of the joint index , Then you can understand why the leftmost matching principle will stop if you encounter range query . With select * from t where a=5 and b>0 and c =1; # such a,b You can use （a,b,c）,c Can not be As an example , When found b After the value of （ This is a range value ）,c Is chaotic . Therefore, it is impossible to determine which row to take according to the union index .

summary

• stay InnoDB In the union index, only the previous one is determined first （ The value on the left side ） after , To determine the next value . If there is a range query , Then the index after the field of range query is used in the union index is in this article SQL It doesn't work . It is worth noting that ,in and = Can be disordered , For example, there is an index （a,b,c）, sentence select * from t where c =1 and a=1 and b=1, Such a statement can also use the leftmost matching , because MySQL There is an optimizer in , He can analyze SQL sentence , Optimize it to a form that indexes can match , namely select * from t where a =1 and a=1 and c=1

Why use a union index

• To reduce overhead . Build a union index (col1,col2,col3), It's actually equivalent to building (col1),(col1,col2),(col1,col2,col3) Three indexes . Every more index , Will increase the cost of write operations and disk space . For tables with large amounts of data , Using federated indexes can greatly reduce the cost ！

• Overlay index . On union index (col1,col2,col3), If there is one of the following sql: select col1,col2,col3 from test where col1=1 and col2=2. that MySQL You can get the data directly by traversing the index , No need to return the form , This reduces a lot of randomness io operation . Reduce io operation , Special random io It's actually dba The main optimization strategy . therefore , In real application , Coverage index is one of the main optimization methods to improve performance .

• Efficient . More index columns , The less data you can filter through the index . Yes 1000W Table of data , There are the following sql:select from table where col1=1 and col2=2 and col3=3, Suppose that each condition can be screened out 10% The data of , If there is only one value index , Then we can filter out 1000W10%=100w Data , Then return to the table from 100w Match found in data col2=2 and col3= 3 The data of , And then sort , Page again ; If it's a joint index , Filter out... By index 1000w10% 10% *10%=1w, Efficiency improvement can be imagined ！