A query process

When using index query, if you need to read a page, it is not read directly, but read the page to the buffer pool, and then search the index key from the buffer pool. Instead of using the buffer pool, the index leaf data page is read directly, but the buffer pool can make it faster, so the data page to be queried is read into the buffer pool, and then searched.

Leftmost matching principle

Leftmost matching principle

1: an overview

InnoDB supports the following common indexes:

  • B+ index (B for balance)

The B+ number index does not find a specific row for a given key value, only the page on which the data row is located. The page is read into memory (that is, the buffer pool) and looked up in the memory buffer pool.

  • The full text indexing
  • Hash index (adaptive)

Index of 2:

2.1: Introduction to B+ trees

Each node of the B+ number index is a page! The middle node is the index page and the leaf node is the data page

The bottom B+ tree fan out is 5.

Note that each large box (page) is a node, not a record.

Insertion of B+ tree (non-B + index)

Data page to insert data into (leaf node) Upper index page (middle page) operation
Not full / Insert directly into the data page
Full of Not full Split leaf nodes (insert data in half and half)
Full of Full of Split twice, split the middle page first, then split the data page in the second case

In fact, it consumes a lot of performance and time, so THE B+ tree also has a function similar to rotation. For example, in case two of the table above, if the adjacent leaf node is still free, it can rotate (move), half of the first look at the left, and then see if the right is free, so as to reduce a split.

B+ tree deletion (non-B + index)

The deletion operation is related to the learning of the fill factor, and 50% is the minimum value of the fill factor.

The leaf node is less than the fill factor The intermediate node is less than the fill factor operation
no / Delete it directly on the page (leaf node), and update the middle node if it is the smallest element on the page
is no Merge the leaf node to congratulate its sibling and update the intermediate node
is is How to update the middle node, then merge the middle node, and merge the middle node twice

2.2: B+ tree index

The essence of B+ tree index is the realization of B+ tree in database. However, one of the characteristics of THE B+ tree index in the database is high fanout, so the B+ index has few levels, usually 2-4 levels.

Clustered index

A clustered index constructs a B+ tree based on the primary key of each table. At the same time, leaf nodes store the row record data of the whole table. Leaf nodes that gather indexes are also called data pages. This feature determines that the data in the index organization table is also part of the index. A table will have only one clustered index, which is generated by primary key.

Features: The leaf node of the clustered index (data page) stores the complete row record, while the non-data page (middle node) stores only the key value (primary key in the clustered index case) and the offset to the data page (pointer).

Nonclustered index

Secondary indexes: You can have more than one table, but not more is better. The leaf node does not contain the entire data of the row record, but contains a bookmark for the corresponding row data, which is the corresponding primary key, in addition to the key value (index column).

The presence of a non-clustered index does not affect the organization of data in a clustered index, so there can be multiple non-clustered indexes.

When using the secondary index to find data, the bookmark is first found through the secondary index, and then the bookmark (primary key) is used to find a complete row record in the clustered index.

2.3: B tree splitting in InnoDB

In innoDB you can’t always split in the middle of a page because inserts are incrementally inserted in primary key order. It’s easy to waste page space.

For example: the first page: 123 the second page: 45678. Since the insertion is sequential, the remaining position of the first page will not be inserted any more data, resulting in a waste of space.

InnoDB typically splits to the left or right:

Intermediate insertion: The currently located record is the previous record of the data to be inserted. If there are n data records to the right of the current location record in the current page, regardless of whether the current page is full, the split point is the next record after the current page is full.

Right-most insert: If the current record is the last record on the current page, then the first record to insert is the split point, the new page, which is the most common split in auto-increment primary keys.

2.4:B+ tree index management

Index creation and deletion

Create and delete statements

Fast Index creation- Fast index creation

Before creating or deleting an index, you need to create a new table first, how to replicate data, and delete the original table. For a table with a large amount of data, it can be very time consuming. More critically, if a large number of transactions access the table, the database service becomes unavailable, which is not friendly to high concurrency.

Fast Index creation is supported from InnoDB version 1.0.x. FIC for short.

When creating secondary indexes, you only need to lock the table and do not need to rebuild the table, so it is much faster. To remove a rich index, simply update the internal view and mark the space of the secondary index as available, while removing the index definition on the internal view of the MYSQL database.

Note: Since the secondary index is created with an S lock on the table, only read transactions are supported, and the service is still unavailable for a large number of write transactions. In addition, FIC only deals with secondary indexes, and the creation of clustered indexes requires the rebuilding of tables.

Online DDL Online data definition

Compared to FIC, online DDL allows table modification (INSERT, Update,delete) operations while creating secondary indexes. The online DDl can be used not only for creating and deleting secondary indexes, but also for the following:

  • Secondary index creation and deletion
  • Change the self-growth value
  • Add or remove foreign key constraints
  • Column renaming

Alter TABLE syntax with online DDL:

alter table [tbl_name]
|ADD {index|key} [index_name](index_col.....)
algorithm [=] {default|inplace|copy}
lock [=] {defalult|none|shared|exclusive}
Copy the code

ALGORITHM specifies the ALGORITHM for creating an index

  • COPY: To create an index, COPY a temporary table. (The oldest way)
  • INPLACE: Create or drop indexes without creating temporary tables
  • DEFAULT: The DEFAULT value is INPLACE

LOCK LOCK on a table when an index is created or dropped:

  • NONE: Unlocked. Read and write operations can be performed to achieve maximum concurrency
  • SHARE: add an S lock, concurrent read transaction, cannot write, similar to fic
  • EXCLUSIVE: Add an X lock. Neither read nor write transactions can be performed, similar to copy state, but without creating tables
  • DEFAULT: NONE – > SHARE – > EXCLUSIVE

Online DDL writes DML operation logs to a cache when an index is created or dropped. Wait until the index is created before applying the redo to the table.

2.5: Cardinality values

The pick up

This value represents an estimate of a unique number in the index. Instead of ratios, such as a table with 100 rows, the Cardinality of the primary key index must be 100.

Changes are critical, and the optimizer uses them to determine whether to use the index.

The closer the Cardinality/ table record count is to one, the better the index. The closer you get to 1, the more selective you are and the better the index.

However, this value is only a general value and is not updated in real time. It can be manually updated using the Analyze Table.

Automatic update strategy for Cardinality: Because the cost of updating Cardinality is particularly high, the storage engine will update if:

  • 1/16 of the data in the table changed
  • Table update times >2 000 000 000 000(since it is possible to update the same row every time, the first condition can never be triggered)

Cardinality’s automatic update algorithm: sampling, so Cardinality is only an approximate value, not an exact value.

  • Eight data pages are randomly selected to make statistics on different values of the index column.
  • And then divide by 8 to get Cardinality

This also causes Cardinality values to be computed differently from one table to another, even if there are no updates to the table.

3: use of B+ tree indexes

3.1: Federated index

Refer to the article to index multiple columns on a table when synindexing

The same method is used to create a single-column index, except that there are multiple index columns

alter table table_name add key idx_a_b (a,b)
Copy the code

Each column in the index is sorted. Many times you can eliminate one sort operation. For example, query the data of the top three people in a class Instead of using the class index, the class index is the index of the column class.

3.2: Index coverage

Refer to the article

The results can be queried using only secondary indexes, without the need for clustered indexes. As long as the column used in the query is overwritten by the column used in the index.

Secondary indexes are much smaller than clustered indexes, so you can reduce a lot of IO operations.

Overwriting indexes is useful for counting and can greatly reduce IO operations

Fit statistical problem

For example, if a student table has an index for the class class, the following statistical query can be performed using only secondary indexes.

select count(*) from student where class=1;
Copy the code

This not only can not return to the table, and greatly reduce IO operations. (Because some data pages are read into memory for statistics)

  • Class is a single-column index:

Using index indicates that an index overwrite is used

  • With a federated index, class is the second.

According to the leftmost matching principle, this index should not be used, but can be used in statistical operations when index coverage is possible

Cannot be used without index coverage if not statistics, as follows:

3.3: Case where the optimizer chooses not to use an index

Through the secondary index search, although the index column is ordered, but the primary key is found out of order, that is, is discrete, and then the search through the clustered index becomes a discrete read on disk (for disk operations, the amount of data, sequential read faster than discrete read. A direct full table scan is much faster than a discrete read.

If there are a lot of primary keys in the secondary index, then using the clustered index for lookup is too expensive and slow, and the optimizer will not use the secondary index.

Therefore, in cases where index coverage is not possible, secondary indexes are used only for a small amount of data that is looked up through secondary indexes.

That is:

Fewer discrete primary keys are found in the secondary index, and the optimizer still chooses to use the secondary index. When there are more discrete primary keys (20% of the total table), the optimizer does not use secondary indexes, but queries directly with clustered indexes.

Multiple range search, secondary index to find out the primary key is discrete, if more, directly use clustered index search. Secondary indexes are not selected.

If you are using solid-state drives, random reads are fast enough to be confident that you can use Force Index to force the use of an index

3.4: Index hint

The display tells the optimizer which index to use.

Two situations can be used:

  • The optimizer selected an index incorrectly, causing a slow (but almost never) performance

  • When a query statement can use too many indexes, the optimizer’s choice of execution schedule time (selecting the usage instructions index) can be more expensive than the statement itself.

  • Use index is just a suggestion that the optimizer doesn’t necessarily take.

  • Force index You can force this index. (Use this to determine which index to use.)

3.5: MRR optimization

MRR optimization is designed to reduce random access to disks and convert random access to more sequential data access.

  • When the secondary index is queried, it is sorted by primary key and bookmarks are searched in the order of primary key sorting.
  • Reduce the number of back substitutions in the buffer pool
  • The split of query conditions, to prevent the query to too much useless data (two and connected query conditions, no MRR is to query a first, and then use the second condition for filtering, MRR, then split into key value pairs (K1, L1), (k2, L2)…. Make enquiries)

The working mode is as follows:

  • The secondary key value of the query is stored in a cache (key-value buffer), where the data in the cache is sorted by the secondary key value.
  • Sort the key values in the cache by primary key
  • Access the actual data file based on the sort order of the primary key

Summary is to sort the primary key queried by the secondary index, and then query the primary key index.

In addition, the buffer pool of the Innod storage engine is not large enough to cause cached pages to be replaced out of the buffer pool (InnoDB’s buffer pool) if it is a discrete read, but this repetitive behavior can be minimized if the primary key is accessed in order

Using index overrides shows using MRR.

Refer to the article

3.6: ICP optimization

As with MRR, mysql5.6 is supported from the start.

When an index query is made, records are first found by index and then filtered by WHERE criteria. After index condition pushdown is supported, the mysql database determines whether the where condition can be filtered when the index is fetched. That is, part of the FILTERING operation is placed in the storage engine layer

The only condition where can be filtered is the range that the index can cover.

Using ICP gives a using index condition prompt

Extraction of where conditions

ICP optimization article

4: Full-text index

4.1: an overview

B+ index trees cannot perform the task of full-text indexing well.

For example like ‘% aaa %’

Full-text index is a technology to find out any content information in the whole book or the whole article stored in the database.

4.2: Inverted index

Inverted indexes store mappings between words and documents in secondary tables.

Secondary tables are usually implemented using relational arrays: there are two types:

  • May I have an Inverted file index? {words, Id of the document where the words are located}
  • May I have a full inverted index? {words, (Id of the document where the words are located, number of the position in the document)}

Secondary tables are persistent tables that are stored on disk.

4.3:InnoDB full text search

Full text retrieval is supported after Innodb1.2. x

p233

The secondary table is implemented using a relational array of full Inverted Indexes.

There are six secondary tables in the InnoDB storage engine to improve the parallelism of full-text retrieval.

FTX Index cache Indicates the index cache for full-text search

FTX index cache is a red-black tree structure, sorted by (Word, I list). This means that the inserted data has been updated to the table, but the secondary table has not been updated, so the result of the word operation is still cached in the FTX index cache.

Innodb storage engine updates secondary tables in batches, rather than inserting a secondary table, and now caches insert information in FTX index cache.

When querying full-text retrieval, the secondary table first updates the contents of the FTX index cache to the secondary table and synchronizes the data.

When the database is shut down, data in the FTX Index cache is also synchronized to the secondary table.

If the database is down, the data in the FTX Index cache is probably not synchronized to the secondary table, so innoDB storage engine automatically reads the incomplete documents and performs word parsing when the user performs full text retrieval (insert or query) after the database is restarted. The result of the segmentation is finally put into the FTX index cache.

The FTX index cache size can be set to 32 MB by default. When the cache is full, word segmentation information is synchronized to the secondary table. Larger FTX index cache can enhance full-text retrieval capabilities, but larger FTX index cache can take longer to recover from outages.

Technology Insider P235.

4.4: Full text retrieval

Mysql supports full text search

Refer to the article

Three query modes.

5: adaptive hash index

The creation of hash indexes in InnoDB cannot be considered interference

Adaptive Hash indexes are mapped to a hash table by the hash function, which allows quick lookup of dictionary types, such as where name=” AAA”