MySQL Bugs: #68545: InnoDB should check left/right pages when target page is full to avoid splitting

Bug #68545	InnoDB should check left/right pages when target page is full to avoid splitting
Submitted:	1 Mar 2013 19:56	Modified:	27 May 2013 9:40
Reporter:	Davi Arnaut (OCA)	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: InnoDB storage engine	Severity:	S3 (Non-critical)
Version:	5.5	OS:	Any
Assigned to:		CPU Architecture:	Any
Tags:	innodb, page split

Description:
Currently during insertion, when noting that the intended page is full, InnoDB does not check neighboring pages for space before splitting the target page. This may mean splitting a completely full page which neighbors a nearly empty page when the two could be re-organized to allow insertion without creating a new page.

How to repeat:
Insert into a full page which has neighbors that would have enough space to satisfy the insert.

Suggested fix:
Implement a way to redistribute/balance data (or free space) among sibling pages.

InnoDB could in fact merge the 3 pages into 2, or balance the content of the 3 pages. There could be existing latches to cover that operation in the sibling pages, acquired in btr_cur_latch_leaves().

The only additional adjustment would be updating the node pointers in upper level(s), which could lead to further tree structure modifications. For example, it could be that the node pointers to the 3 pages are not in the same node pointer page. If we want to avoid such tree-wide changes to the node pointers, we would have to limit the type of supported balancing operations.