Explanation of index failure principle and its common situations

Let's first look at the single valued index b+ Tree image

Each node stores only one key value pair

Let's take a look at the structure of the joint index

Yes （2,4） Conduct joint indexing

We are right. a The index value sort is ：1,1,2,2,3,3
Yes b Sort ：1,2,1,4,1,2

You can see a The fields are ordered ,b Fields are out of order （ because B+ The tree can only select one field to build an ordered tree ）

We can see that a Is ordered , stay a Under the premise of confirmation, our b It's also ordered

---

Best left prefix principle

select * from testTable where a=1 and b=2

a Field in B+ There's order in the trees , So we can locate... By binary search a=1 The location of .

Secondly, in a In certain cases ,b It's relatively orderly , Because of order , So we can also find it by binary search b=2 The location of .

Take a look at the special case

select * from testTable where b=2

b The premise of order is in a In certain cases , Now? a It's gone , that b There must be no order , In a disordered B+ It's impossible to locate... In a tree by binary search b Field . So the index is invalid

---

Range queries Right failure principle

select * from testTable where a>1 and b=2

First a Field in B+ There's order in the trees , So we can use binary search to locate 1, And then put all the greater than 1 We'll take out the data ,a You can use indexes .

however b The premise of order is a It's a certain value , So now a The value of is greater than 1 Of , There may be 10 More than 1 Of a, There may be a hundred a.

---

like Index invalidation principle

The principle is almost the same as the above , Let's take an example

where name like "a%"

where name like "%a%"

where name like "%a"

% Use of

1.% Put it on the right side. , On behalf of the inquiry to "a" Initial data , Such as ：abc
2. Two %%, Represents that the query data contains "a" The data of , Such as ：cab、cba、abc
3.% Put it on the left side. , On behalf of the inquiry to "a" For the ending data , Such as cba

Why? % On the right, you can sometimes use indexes
1.% On the right, it's called ： Prefix
2.%% be called ： Infix
3.% On the left is called ： suffix

Here is still the best left prefix ：

How strings are sorted ： First, sort by the first letter , If the first letter is the same , Just sort by the second letter ... And so on

So there are three situations

One 、% Number one on the right （ Prefix ）

because B+ The index order of the tree , It's sorted by the size of the first letter , Prefix matching is also matching initials . So it can be B+ An orderly search on the tree , Find the data whose initials match the requirements . So sometimes you can use indexes .

Two 、% Number one on the left

Is the data that matches the end of the string , We said sort rules above , The letters at the end are out of order , So you can't query in index order , You don't need an index .

3、 ... and 、 Two %% Number

This is to query the letters in any position to meet the conditions , Only the initials are indexed , The letters in other places are relatively unordered , So there's no index to find letters anywhere .

Index failure condition portal

In summary ：

1. Implicit type conversion is used

2. The expression used by the index calculation

select * from user where age - 2 =18;//1
select * from user where age = 18+2 ;//2

In the first case, the index will be used , The second is not

3. A function expression is used

select * from user where left(phone,3)='133';//1
select * from user where phone like='133%';//2

In the first case, the index will be used , The second is not

The above three situations are summarized
In fact, the use of index depends on B-tree Traversal of index tree , The traversal of the index tree depends on the ordering of the underlying leaf nodes , When the indexed field performs the above three operations , It is possible that the new arrangement order of this field is different from the original arrangement order in the leaf node layer of the index tree , It destroys the order of leaf nodes ,sql Statement execution time ,mysql The executor of cannot judge whether the original index tree can be retrieved . Led to sql The statement executor does not use the index . Our intuitive feeling is that the index is invalid

4.% Fuzzy matching , There is analysis on it .

5. The used index field is not the leftmost field of the union index , See above for analysis

A small summary ：4,5 The situation is the above analysis , Follow the leftmost matching principle

If index coverage occurs in these five cases , That is, when there is no need to return the table , The index tree will still be used