Fragmentation is a common concern in some database systems. Highly fragmented tables can affect performance and resource allocation. But reducing fragmentation often involves rebuilding the table completely. This blog post will discuss fragmentation and its impact on InnoDB.
What is fragmentation?
We say that something is fragmented when it is formed by parts that are separate or placed in a different order than the natural one. In databases, we can experiment with different types of fragmentation:
- Segment Fragmentation: segments are fragmented; they are stored not following the order of data, or there are empty pages gaps between the data pages.
- Tablespace Fragmentation: the tablespace is stored in non-consecutive filesystem blocks.
- Table Fragmentation: data is stored not following the primary key order (heap tables), or table pages have a significant amount of free space (heap tables or index tables).
- Index Fragmentation: indexes usually store the data following the index order (b-tree) or in a random order (hash). In both cases, fragmentation means free space inside the index pages.
- Row Fragmentation: single rows are spread across multiple pages.
Not all types of fragmentation can happen on all the database technologies, and sometimes you can’t avoid a certain degree of fragmentation. InnoDB tables are index tables, meaning data is organized following the primary key.
The principle of locality
While the principle of locality is usually related to processors and cache access patterns, it also applies to data access in general. This principle describes two data access patterns: spatial and temporal locality.
Temporal locality means that data that has been recently retrieved is more prone to be required again in a short period of time. Spatial locality tells us that somehow related data (near) tends to be accessed together. If your data is organized following the principle of locality, data access will be more efficient.
How does fragmentation affect the locality of data?
Table and index fragmentation often lead to database pages containing significant free space. This reduces the probability of storing frequently accessed data together and goes against the temporal locality principle.
Table fragmentation also affects the spatial locality by storing related data on different database pages. Regarding tablespace and segment fragmentation, modern storage systems tend to reduce the impact of these types of fragmentation.
The situation with row fragmentation is a bit different. We usually have three possibilities: row fragmentation is not supported, it is supported through row chaining (the partial row has a pointer to another page where the row continues), or it is supported only for large datatypes. In the last case, blobs are usually stored out-of-band in a separate area. This type of fragmentation can improve performance and efficiency.
Fragmentation in InnoDB
In InnoDB, everything is an index. Primary keys are important because they define how data will be sorted in the table. One of the effects of this design is that there is no fragmentation due to unordered data. But we still can have fragmentation caused by free space within the table pages.
To split or not to split, that is the question.
InnoDB stores the rows in pages. A new row is placed on a specific page based on the primary key. But what happens when a page becomes full? InnoDB must allocate a new page where the new row will be stored. Here InnoDB is quite clever. Most RDBMS performs a page split: a new page is created, and half the contents of the full page are moved to the recently allocated page, leaving two half-full pages. What InnoDB does instead is to analyze the insertion pattern and, if it is sequential, create a page and place the new row there. This is very efficient for sequential primary key inserts.
The inserts don’t need to be purely sequential; they need to follow a direction: incremental or decremental. We will not cover the internals; just tell you that each index leave page has metadata to indicate the direction of recent inserts and how many rows were inserted following it.
Random vs. Sequential inserts, effect on fragmentation
As we explained before, InnoDB has a clever method to identify if a new row has to be inserted in an empty page or if it makes sense to perform a page split. This method is extremely efficient for sequential insertions because it generates the minimum number of additional pages and, traditionally, has been considered harmful for non-sequential insertions (when the primary key is random or unknown).
We will review the process with sequential and random insertions to understand how rows are inserted. But first, let’s see the contents of an empty page. Initially, we have some metadata and free space for new data.
Once we start inserting data into this page, it does not matter if the data is sequential or not; the page will start filling.
But once we go below 1/16th of free space, we must allocate new pages. How new pages are allocated and filled depends on whether the insertions are sequential or random. For sequential insertions, we have this pattern:
The new data is inserted in the new leaf page. But for random insertions, we have a different behavior:
We must reserve free space on both pages because we can’t assume where new rows will be inserted.
As new rows are inserted, the sequential inserts will continue with a low fragmentation:
But what happens with random insertions? For simplicity, we are assuming that the primary keys are uniformly distributed.
Here we see an interesting phenomenon when fragmentation is low; new inserts may trigger page splits that increase fragmentation. But once we reach a certain level of fragmentation, almost all pages will have enough free space to accept new rows without performing splits. Until the threshold is reached and new splits will happen again.
This means that random insertions lead to temporary fragmentation.
Random inserts and deletes
The previous case covered situations where we only insert data, but what happens when we also remove it? Often we have tables where old rows are periodically purged. If they are sorted by primary key, there is not any problem: empty pages will be removed completely from the beginning of the indexed table.
What we see here is that old rows belong to the same pages, and once they are removed, it is possible to return that page to the tablespace. Later this page will be allocated again to be used for new rows.
But what happens when inserts and deletions are random? The assumption that deletes are also random is correct, as data is distributed randomly.
As we can see, as long as the number of rows deleted and inserted is roughly equal, this pattern will not significantly increase (or decrease) fragmentation.
The ideal situation with random inserts and deletions is having enough space to insert new rows without reaching the split point.
Additional causes of fragmentation
Three factors define additional causes of fragmentation. We’ve been analyzing the first one previously: how data is inserted. The other two are data modification (updates) and data removal (deletes).
When a null field is filled with data or a varchar field content is replaced by a longer text, the page must make room for this extra data. What happens if there is not enough free space? InnoDB will split the page into two half-full pages. This increases fragmentation. To avoid this, InnoDB reserves 1/16th of each page for data modification. This reservation is made regardless of the insertion pattern.
If you increase the size of many rows, you will generate fragmentation.
And what happens with deletes? Deletes increase fragmentation by reducing the number of records stored on affected pages. To fix this, if a page goes below 50% utilization, InnoDB will look at adjacent pages (following the index order), and if one of those pages is below 50%, it will merge both pages into one. The freed space will not return to the file system but will be reused by new pages.
Detecting fragmentation
Currently, there is no easy way to measure page fragmentation. There is a column in the table information_schema.tables that is supposed to contain the average row length.
https://dev.mysql.com/doc/refman/8.0/en/information-schema-tables-table.html
But after some verification, we’ve found this is not properly calculated. We opened a bug to MySQL support and Percona Support to get this fixed.
https://bugs.mysql.com/bug.php?id=107739
To calculate the fragmentation, it is feasible to write an SQL script that returns the total size of the data in the table using the information from the MySQL documentation and the actual data length of variable-length columns. We can estimate the average fragmentation by comparing that data with the number of pages allocated for data. Unfortunately, this would not provide enough information to detect fragmentation hot spots.
https://dev.mysql.com/doc/refman/8.0/en/storage-requirements.html
Measuring page splits
An indirect method to identify that fragmentation is happening is measuring the number of page splits. Unfortunately, it is impossible to measure the number of page splits created during inserts or updates on a specific table.
The global statistics about InnoDB page splits are stored in the information_schema table innodb_metrics.
These statistics must be enabled by using the innodb_monitor_enable global variable.
https://dev.mysql.com/doc/refman/8.0/en/innodb-parameters.html#sysvar_innodb_monitor_enable
https://dev.mysql.com/doc/refman/8.0/en/innodb-information-schema-metrics-table.html
InnoDB Ruby
It is possible to analyze the structure of InnoDB structures using an external open-source tool called InnoDB Ruby. Jeremy Cole has developed this tool, and is accessible here:
https://github.com/jeremycole/innodb_ruby
There is also a wiki page that documents application usage:
https://github.com/jeremycole/innodb_ruby/wiki
To get an overview of fragmentation for a specific table, you can use the following command:
1 | innodb_space -f space-extents-illustrate |
This command returns a graphical representation of the tablespace using different formats to display space allocation on each page.
Reducing fragmentation
Once a table is fragmented, the only method to reduce fragmentation is rebuilding the table. The problem with reducing fragmentation by rebuilding the table is that random inserts will fragment the table quickly. This fragmentation appears quickly because new rows are inserted randomly, and the fragmentation reduction leads to no free space for new rows.
Rebuilding the table could lead to a massive increase in fragmentation shortly after the rebuild, as page splits would bring us to a point where almost all the pages are half full.
Innodb_fill_factor
Ideally, if we perform random inserts, we must allocate enough space for new inserts after a full table rebuild. There is a global variable that exactly does this: innodb_fill_factor.
https://dev.mysql.com/doc/refman/8.0/en/innodb-parameters.html#sysvar_innodb_fill_factor
“Innodb_fill_factor defines the percentage of space on each B-tree page that is filled during a sorted index build, with the remaining space reserved for future index growth. For example, setting innodb_fill_factor to 80 reserves 20 percent of the space on each B-tree page for future index growth. Actual percentages may vary. The innodb_fill_factor setting is interpreted as a hint rather than a hard limit.”
This means that if we perform random inserts and deletes and we rebuild the tables using a fill factor big enough to hold all the inserts before the purge, the table will maintain a low level of fragmentation.
Random insert and delete tests and recommended fill factor
We performed multiple tests with different fill factors. The test performed consisted of the following:
- Create a table.
- Insert 2,000,000 records using md5 as the function to generate the hash.
- Set the fill factor to the test value.
- Optimize the table.
- Repeat 400 times
- Insert 10,000 rows into the table.
- Remove 10,000 rows from the table.
- Measure the fragmentation.
We tested with these fill factors: 75, 80, 82, 83, 85, and 100.
Total space file size
This chart shows the initial and final space allocation.
As we can see, using a fill factor of 83 provides the best results for this test.
Page splits and merges
We also analyzed the number of page splits (the number of times a row does not fit in the corresponding page and the page needs to be split into two pages) and the number of page merges (the number of times that, after a delete operation, a page goes below 50% and InnoDB tries to merge it with adjacent pages).
| Fill factor | Page splits | Merge attempts | Merge successful |
|---|---|---|---|
| 75 | 63 | 4 | 3 |
| 80 | 565 | 108 | 34 |
| 82 | 1363 | 348 | 106 |
| 83 | 2063 | 658 | 203 |
| 85 | 4350 | 1324 | 318 |
| 100 | 44771 | 15527 | 2323 |
As we can see, there are a number of page splits for every fill factor. For the 100 fill factor, we had a page split for every 89 rows processed, while with a fill factor of 83, we had a page split for every 1930 rows processed.
Fragmentation maps
We provide fragmentation maps for 75, 83, and 100 fill factors after 400 iterations.
Conclusions
Fragmentation usually is not a problem for InnoDB tables. InnoDB deals with fragmentation quite efficiently, and table rebuilds are seldom needed.
There is only an edge case when data is inserted following a random primary key. In this case, results will depend on the table’s structure, the keys’ distribution, and how frequently data is inserted or removed.
For our tests, a value of innodb_fill_factor of around 83% was optimal. It allowed for keeping the fragmentation under control. Smaller fill factors did not provide additional benefits. Your mileage may vary.
If you have a large table with random insertions, we recommend using a tool like innodb_ruby to monitor fragmentation and analyze if the table needs a rebuild with a different fill factor.
Percona Distribution for MySQL is the most complete, stable, scalable, and secure open source MySQL solution available, delivering enterprise-grade database environments for your most critical business applications… and it’s free to use!
Try Percona Distribution for MySQL today!
