Bug #68501 InnoDB fails to merge under-filled pages depending on deletion order
Submitted: 26 Feb 2013 23:13 Modified: 14 Jun 2013 8:37
Reporter: Davi Arnaut (OCA) Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: InnoDB storage engine Severity:S2 (Serious)
Version:5.5,5.6 OS:Any
Assigned to: CPU Architecture:Any
Tags: innodb, page, underfill

[26 Feb 2013 23:13] Davi Arnaut
Description:
Successive deletes in descending key order can lead to drastically under-filled
pages. The problem is that InnoDB only attempts to merge an under-filled (less
than half full) page with its left sibling, failing to check if the sibling page
to the right has enough space.

For example, in practice this can happen if for whatever reason (e.g. parallel
execution) a set of deletes (that fall within sibling pages) are execute in
order such as that the ones using higher key values completes first.

How to repeat:
# Create table.
CREATE TABLE t1 (a INT NOT NULL PRIMARY KEY AUTO_INCREMENT, b VARCHAR(256)) ENGINE=INNODB;

# Populate table.
INSERT INTO t1 VALUES (0, REPEAT('a',256));
INSERT INTO t1 SELECT 0, b FROM t1;
INSERT INTO t1 SELECT 0, b FROM t1;
INSERT INTO t1 SELECT 0, b FROM t1;
INSERT INTO t1 SELECT 0, b FROM t1;
INSERT INTO t1 SELECT 0, b FROM t1;
INSERT INTO t1 SELECT 0, b FROM t1;
INSERT INTO t1 SELECT 0, b FROM t1;
INSERT INTO t1 SELECT 0, b FROM t1;

# Delete records such as that only 5 records are left per page.
DELETE FROM t1 WHERE a >= 369;
DELETE FROM t1 WHERE a BETWEEN 315 AND 363;
DELETE FROM t1 WHERE a BETWEEN 261 AND 309;
DELETE FROM t1 WHERE a BETWEEN 144 AND 255;

# Wait for records to be purged.
# Number of records per page:

mysql> SELECT PAGE_NUMBER, NUMBER_RECORDS, DATA_SIZE FROM
    -> INFORMATION_SCHEMA.INNODB_BUFFER_PAGE WHERE TABLE_NAME
    -> LIKE '%t1%' ORDER BY PAGE_NUMBER;
+-------------+----------------+-----------+
| PAGE_NUMBER | NUMBER_RECORDS | DATA_SIZE |
+-------------+----------------+-----------+
|           3 |              6 |        84 |
|           4 |             27 |      7587 |
|           5 |             54 |     15174 |
|           6 |              5 |      1405 |
|           7 |              5 |      1405 |
|           8 |              5 |      1405 |
|           9 |              5 |      1405 |
+-------------+----------------+-----------+
7 rows in set (0.01 sec)

Suggested fix:
InnoDB should try to merge under-filled pages with its left and right siblings.
The description in btr_compress() says this is done, but it actually only checks the
left sibling in the common case.

Additionally, merges shouldn't be attempted every time a record is deleted from
an under-filled page.
[27 Feb 2013 11:01] Mark Callaghan
Updates to secondary indexes are implemented by delete old - insert new. So can this also be an issue for secondary index pages that get many updates?
[28 Feb 2013 18:30] Sveta Smirnova
Thank you for the report.

Verified as described. In version 5.5 same thing happens if delete in ascending order as well.
[28 Feb 2013 18:31] Sveta Smirnova
test case for MTR

Attachment: bug68501.test (application/octet-stream, text), 1.50 KiB.

[1 Mar 2013 14:28] MySQL Verification Team
Mark,

Yes, it can be an issue in that case too ...
[14 Jun 2013 8:37] Erlend Dahl
[13 Jun 2013 10:49] Daniel T Price:

Added changelog entry for 5.5.33, 5.6.13, 5.7.2:

"Successive deletes in descending key order would lead to under-filled InnoDB
index pages. When an InnoDB index page is under-filled, it is merged with the
left or right sibling node. The check performed to determine if a sibling
node is available for merging was not functioning correctly."