Detailed explanation of the underlying implementation of descending index, a new feature of MySQL 8

What is a descending index?

You may be familiar with indexes, but unfamiliar with descending indexes. In fact, descending indexes are a subset of indexes.

We usually use the following statement to create an index:

create index idx_t1_bcd on t1(b,c,d);

The above SQL means to create a joint index for the three fields b, c, and d in the t1 table.

But what everyone doesn’t know is that the above SQL is actually equivalent to the following SQL:

create index idx_t1_bcd on t1(b asc,c asc,d asc);

asc means ascending order. The index created using this syntax is called an ascending index. That is, when we usually create indexes, we create ascending indexes.

You may think that when creating an index, you can set asc for the field, so can you also set desc?

Of course it is possible, for example, the following three statements:

create index idx_t1_bcd on t1(b desc,c desc,d desc);
create index idx_t1_bcd on t1(b asc,c desc,d desc);
create index idx_t1_bcd on t1(b asc,c asc,d desc);

This syntax is also supported in MySQL. The index created using this syntax is called a descending index . The key issue is that before MySQL 8.0, it was only supported at the syntax level, and there was no real support at the bottom level.

We use Mysql7 and Mysql8 to illustrate the following examples:

Create a table in Mysql7 and Mysql8 respectively, with five fields: a, b, c, d, and e:

create table t1 (
a int primary key,
b int,
c int,
d int,
e varchar(20)
) engine=InnoDB;

Then create a descending index separately:


create index idx_t1_bcd on t1(b desc,c desc,d desc);

After successful creation, we use the following sql to view the index information:


show index from t1;

In MySQL 7 you will get the result:

In MySQL 8 you will get the result:

We only care about the three rows of records with Key_name idx_t1_bcd. If you are careful, you should be able to find that the results of the Collation field in these two results are different:

• In MySQL 7, the result of the Collation field is A, A, A, which means that the sorting method of the three fields b, c, and d is asc
• In MySQL 8, the result of the Collation field is D, D, D, which means that the sorting method of the three fields b, c, and d is desc

However, when we created the index, we clearly specified at the syntax level that the sorting method for the three fields b, c, and d is desc. This shows that in MySQL 7, descending indexes are only supported at the syntax level, and there is no real support at the bottom level, and the index is fixed to ascending order. In MySQL 8, descending indexes are truly supported from the bottom up .

So far, everyone should have a general understanding of ascending indexes and descending indexes, but they do not really understand them because everyone does not know how ascending indexes and descending indexes are implemented at the bottom layer.

Ascending index underlying implementation

We know that indexes are used to improve query speed, but why can indexes improve query speed?

Given a sequence of numbers, such as [1,3,7,9,2,5,4,6,8], which is an unordered sequence or array, if you want to increase the query speed of this sequence, what will you do first? I believe most people can think of sorting first, sorting this unordered sequence in ascending order, for example, getting [1,2,3,4,5,6,7,8,9]. After having this ordered sequence, we can use algorithms such as binary search to improve the query speed of this sequence.

What I want to tell you by giving this example is : if you want to increase the query speed of a data set, you can first sort the data.

Therefore, the same is true for the data stored in the Mysql table. If we want to increase the query speed of this table, we can sort the data in this table first. Then a row of data in the table includes many fields. We now want to sort these data rows. Which fields should we use to determine the order? This is the index. The column you specify when creating the index is used to sort the data rows in the table.

For example, we still use the t1 table created above and insert 8 records into the t1 table:

insert into t1 values(4,3,1,1,'d');
insert into t1 values(1,1,1,1,'a');
insert into t1 values(8,8,8,8,'h');
insert into t1 values(2,2,2,2,'b');
insert into t1 values(5,2,3,5,'e');
insert into t1 values(3,3,2,2,'c');
insert into t1 values(7,4,5,5,'g');
insert into t1 values(6,6,4,4,'f');

Then the data must be stored in the file, so the format of saving the data in the file is roughly as follows, and the order is consistent with the insertion order:

4311d
1111a
8888h
2222b
5235e
3322c
7455g
6644f

Note that t1 is the Innodb storage engine, and the a field is the primary key, so the Innodb storage engine will sort by the primary key when processing the inserted data. That is, the format of saving these data in the file I mentioned above is inaccurate. Because I don’t want the article to be too long, I won’t go into it in depth. Students who are interested can follow the official account: 1:25. I will write an article specifically to explain the specific implementation of indexes in Innodb, including how B+ trees are generated.

If we search for data based on the above storage method, for example, to search for the row of records with a=3, we need to start from the first row of records, so we need to search 6 times. If we sort the above data according to the size of the a field:

1111a
2222b
3322c
4311d
5235e
6644f
7455g
8888h

After sorting, if we still search for the row with a=3, we only need to search 3 times. Another advantage of this is that if we need to find the row of data a=3.5 now, if we use the storage method before sorting, we need to query all 8 rows of data to finally confirm that the row of data a=3.5 does not exist. If we use the storage method after sorting, we only need to check 4 times, because when you find the row of records 4311d, you will find that 4>3.5, which means that the row of records a=3.5 does not exist.

And if we now create an index for t1, just like creating the index above, if we write the following SQL:

create index idx_t1_bcd on t1(b,c,d);

This SQL statement indicates that an index is to be created for t1. The index fields are b, c, and d, and are in ascending order. Therefore, the original data is actually sorted according to the three fields b, c, and d. After sorting, the result is similar to:

1111a
2222b
5235e
4311d
3322c
7455g
6644f
8888h

You can take a closer look. The records above are sorted by the three fields b, c, and d. For example, the values ​​of the three fields b, c, and d in 1111a are 111, and the values ​​of the three fields b, c, and d in 2222b are 222. 111 is less than 222, so the corresponding row is ranked first.

So what are the benefits of sorting the data in this way? In fact, the benefits are similar to those of sorting by field a. For example, if you want to search for data where b=4, c=4 and d=4, the search can be faster. In fact, this is the principle of indexing: we create an index for a table, which means we sort the data in the table, and the sorted data can improve the search speed.

Another point to note is that there are many ways to sort, or you can use some data structures, such as binary trees, red-black trees, and B+ trees. These data structures are actually sorting data, but the sorting forms are different. Each data structure has its own characteristics, and everyone should know that the most commonly used one in MySQL is the B+ tree.

I believe that after reading this, everyone should have a new understanding of indexes. The only difference is that the examples we gave above are all in ascending order, and the sorted data can not only improve the query speed, but also is useful for order by. For example, if we now want to order t1 by b asc, c asc, d asc; for this sort, if an ascending index of b, c, d has been established in the t1 table, it means that the data in the t1 table has been sorted in advance according to b, c, d, so the order by statement can directly use the sorted data without using filesort to sort it again.

And if our order by is order by b desc, c desc, d desc, we can also use the ascending index of b, c, d, because if it is order by b asc, c asc, d asc, we can traverse from top to bottom, and if it is order by b desc, c desc, d desc, we can traverse from bottom to top.

So, what if it is order by b asc, c desc, d desc? Is it true that this order by statement cannot utilize the ascending index of b, c, and d?

At this time, a descending index is needed.

Descending index underlying implementation

We have spent a lot of time introducing the implementation principle of ascending index. In summary, it is to sort the data in the table in ascending order according to the size of the specified field.

What is ascending order? After the data is compared in size, the smaller one is on the top and the larger one is on the bottom, or if it is a B+ tree, the smaller one is on the left and the larger one is on the right. And descending order means the larger ones are on the top and the smaller ones are on the bottom, or if it is a B+ tree, the larger ones are on the left and the smaller ones are on the right.

So, for the original data above:

4311d
1111a
8888h
2222b
5235e
3322c
7455g
6644f

If we sort this data by a desc, it will be:

8888h
7455g
6644f
5235e
4311d
3322c
2222b
1111a

It's very simple, right? If we sort the data by b desc, c desc, d desc, it will be:

8888h
6644f
7455g
3322c
4311d
5235e
2222b
1111a

It's also very simple. What if we want to sort the data according to b desc, c asc, d desc? Isn’t this a bit confusing?

In fact, it is not difficult. Sorting is actually comparing the size of data. Let's use the following three rows of data to simulate it:

3322c
7455g
4311d

First, sort by b desc, c desc, d desc, and the results are as follows:

7455g
3322c
4311d

Sort by b desc, c asc, d desc, and the results are as follows:

7455g
4311d
3322c

Maybe some of you have already understood that, in fact, what b desc means is that the data in field b with larger data is on the top, and the data in field c with smaller data is on the bottom. If the data is equal, field c is compared, and field c is sorted in ascending order, that is, the data in field c with smaller data is on the bottom, and the data in field c with larger data is on the top. So we got the above result.

This is the descending index.

Summarize

In fact, ascending index and descending index are just different sorting methods. After the descending index is implemented in MySQL 8, we are more flexible in creating indexes. We can create appropriate indexes according to the sorting rules required by the business, which can make your query faster.

Of course, this article only explains the principle. Everyone must know that the B+ tree used for sorting in MySQL is not the very simple method I gave as an example above. However, even if the B+ tree is used, the principle is the same, just comparing the size of the data.

Another point is that currently only the Innodb storage engine supports descending indexes .

This is the end of this article about the detailed implementation of the underlying descending index of the new feature of MySQL 8. For more relevant MySQL 8 descending index content, please search for previous articles on 123WORDPRESS.COM or continue to browse the following related articles. I hope everyone will support 123WORDPRESS.COM in the future!