Description:
The purpose of btr_page_get_split_rec_to_left is to select an appropriate split record. Its main objective is to keep the insert point on the current page while transferring records before the insert point to the new left page. This avoids repeatedly moving the same records before the insert point, especially if multiple insert operations are targeted at the same insert point.
There are two potential weak points of this strategy：
1. The strategy of detecting potential decreasing order inserts by comparing the PAGE_LAST_INSERT with the current insert point is not accurate enough. If the last two insert operations before the split operation are in decreasing order, this strategy will be used, even if the previous inserts were random.
2. Once the strategy is triggered, the insert point is always chosen as the split record. If there are only a few records before the insert point, this left split would result in a sparse new left page and an almost full current page.
If we continue randomly inserting into the current page and only ensure that the last two inserts before the split are in decreasing order and at the front of the page, it will create many new sparse left pages repeatedly. These sparse pages could waste space and mislead the SQL optimizer's index dive.
btr_page_get_split_rec_to_right also has the same problem.
How to repeat:
Here is the reproducing MTR case:
----------------------------------------------------------------------------------
--source include/have_debug.inc
--source include/have_debug_sync.inc
--disable_query_log
SET @old_innodb_limit_optimistic_insert_debug = @@innodb_limit_optimistic_insert_debug;
SET @old_innodb_adaptive_hash_index = @@innodb_adaptive_hash_index;
SET @old_innodb_stats_persistent = @@innodb_stats_persistent;
--enable_query_log
--disable_warnings
DROP TABLE IF EXISTS t1;
DROP TABLE IF EXISTS t2;
--enable_warnings
# Save the initial number of concurrent sessions
--source include/count_sessions.inc
SET GLOBAL innodb_adaptive_hash_index = false;
SET GLOBAL innodb_stats_persistent = false;
CREATE TABLE t1 (
a00 CHAR(16) NOT NULL DEFAULT 'a'
) charset latin1 ENGINE = InnoDB;
ALTER TABLE t1 ADD CONSTRAINT pkey PRIMARY KEY(
a00
);
CREATE TABLE t2 (
a00 CHAR(255) NOT NULL DEFAULT 'a'
) charset latin1 ENGINE = InnoDB;
ALTER TABLE t2 ADD CONSTRAINT pkey PRIMARY KEY(
a00
);
#
# Issue 1
# Left split causes sparse pages
#
# Only root (1)
ANALYZE TABLE t1;
SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t1';
SET GLOBAL innodb_limit_optimistic_insert_debug = 20;
INSERT INTO t1 (a00) VALUES ('aa');
INSERT INTO t1 (a00) VALUES ('ab');
INSERT INTO t1 (a00) VALUES ('ac');
INSERT INTO t1 (a00) VALUES ('ad');
INSERT INTO t1 (a00) VALUES ('ae');
INSERT INTO t1 (a00) VALUES ('af');
INSERT INTO t1 (a00) VALUES ('ag');
INSERT INTO t1 (a00) VALUES ('ah');
INSERT INTO t1 (a00) VALUES ('ai');
INSERT INTO t1 (a00) VALUES ('aj');
INSERT INTO t1 (a00) VALUES ('ak');
INSERT INTO t1 (a00) VALUES ('al');
INSERT INTO t1 (a00) VALUES ('am');
INSERT INTO t1 (a00) VALUES ('an');
INSERT INTO t1 (a00) VALUES ('ao');
INSERT INTO t1 (a00) VALUES ('ap');
INSERT INTO t1 (a00) VALUES ('aq');
INSERT INTO t1 (a00) VALUES ('ar');
INSERT INTO t1 (a00) VALUES ('as');
INSERT INTO t1 (a00) VALUES ('at');
INSERT INTO t1 (a00) VALUES ('au');
# Raise root (1-2)
# (aa,ak)
# (aa,ab,ac,ad,ae,af,ag,ah,ai,aj)(ak,al,am,an,ao,ap,aq,ar,as,at,au)
ANALYZE TABLE t1;
SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t1';
# Insert 8 records in random(non-decreasing) order
INSERT INTO t1 (a00) VALUES ('au1');
INSERT INTO t1 (a00) VALUES ('au2');
INSERT INTO t1 (a00) VALUES ('au3');
INSERT INTO t1 (a00) VALUES ('au4');
INSERT INTO t1 (a00) VALUES ('au5');
INSERT INTO t1 (a00) VALUES ('au6');
INSERT INTO t1 (a00) VALUES ('au7');
INSERT INTO t1 (a00) VALUES ('au8');
# Insert 2 records in decreasing order,
# it would cause left split and create a sparse page with only 4 records.
INSERT INTO t1 (a00) VALUES ('ao2');
INSERT INTO t1 (a00) VALUES ('ao1');
# Split leaf (1-3)
# (aa,ak,ao)
# (aa,ab,ac,ad,ae,af,ag,ah,ai,aj)(ak,al,am,an)(ao,ao1,ao2,ap,aq,ar,as,at,au,au1,au2,au3,au4,au5,au6,au7,au8)
ANALYZE TABLE t1;
SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t1';
# Insert 2 records in random(non-decreasing) order
INSERT INTO t1 (a00) VALUES ('at1');
INSERT INTO t1 (a00) VALUES ('at2');
# Insert 2 records in decreasing order,
# it would cause left split and create a sparse page with only 4 records again.
INSERT INTO t1 (a00) VALUES ('aq2');
INSERT INTO t1 (a00) VALUES ('aq1');
# Split leaf (1-4)
# (aa,ak,ao)
# (aa,ab,ac,ad,ae,af,ag,ah,ai,aj)(ak,al,am,an)(ao,ao1,ao2,ap)(aq,aq1,aq2,ar,as,at,at1,at2,au,au1,au2,au3,au4,au5,au6,au7,au8)
ANALYZE TABLE t1;
SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t1';
############################################################
#
# Issue 2
# Right split causes sparse pages
#
# Only root (1)
ANALYZE TABLE t2;
SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t2';
SET GLOBAL innodb_limit_optimistic_insert_debug = 20;
INSERT INTO t2 (a00) VALUES ('aa');
INSERT INTO t2 (a00) VALUES ('ab');
INSERT INTO t2 (a00) VALUES ('ac');
INSERT INTO t2 (a00) VALUES ('ad');
INSERT INTO t2 (a00) VALUES ('ae');
INSERT INTO t2 (a00) VALUES ('af');
INSERT INTO t2 (a00) VALUES ('ag');
INSERT INTO t2 (a00) VALUES ('ah');
INSERT INTO t2 (a00) VALUES ('ai');
INSERT INTO t2 (a00) VALUES ('aj');
INSERT INTO t2 (a00) VALUES ('ak');
INSERT INTO t2 (a00) VALUES ('al');
INSERT INTO t2 (a00) VALUES ('am');
INSERT INTO t2 (a00) VALUES ('an');
INSERT INTO t2 (a00) VALUES ('ao');
INSERT INTO t2 (a00) VALUES ('ap');
INSERT INTO t2 (a00) VALUES ('aq');
INSERT INTO t2 (a00) VALUES ('ar');
INSERT INTO t2 (a00) VALUES ('as');
INSERT INTO t2 (a00) VALUES ('at');
INSERT INTO t2 (a00) VALUES ('au');
# Raise root (1-2)
# (aa,ak)
# (aa,ab,ac,ad,ae,af,ag,ah,ai,aj)(ak,al,am,an,ao,ap,aq,ar,as,at,au)
ANALYZE TABLE t2;
SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t2';
# Insert 8 records in random(non-increasing) order
INSERT INTO t2 (a00) VALUES ('ab9');
INSERT INTO t2 (a00) VALUES ('ab8');
INSERT INTO t2 (a00) VALUES ('ab7');
INSERT INTO t2 (a00) VALUES ('ab6');
INSERT INTO t2 (a00) VALUES ('ab5');
INSERT INTO t2 (a00) VALUES ('ab4');
INSERT INTO t2 (a00) VALUES ('ab3');
INSERT INTO t2 (a00) VALUES ('ab2');
INSERT INTO t2 (a00) VALUES ('ab1');
# Insert 2 records int increaseing order,
# it would cause right split and create a sparse page with only 4 records.
INSERT INTO t2 (a00) VALUES ('ae1');
INSERT INTO t2 (a00) VALUES ('ae2');
# Split leaf (1-3)
# (aa,ag,ak)
# (aa,ab,ab1,ab2,ab3,ab4,ab5,ab6,ab7,ab8,ab9,ac,ad,ae,ae1,ae2,af)(ag,ah,ai,aj)(ak,al,am,an,ao,ap,aq,ar,as,at,au)
ANALYZE TABLE t2;
SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t2';
# Insert 8 records in random(non-increasing) order
INSERT INTO t2 (a00) VALUES ('aa2');
INSERT INTO t2 (a00) VALUES ('aa1');
# Insert 2 records in increaseing order,
# it would cause right split and create a sparse page with only 4 records again.
INSERT INTO t2 (a00) VALUES ('ac1');
INSERT INTO t2 (a00) VALUES ('ac2');
# Split leaf (1-4)
# (aa,ag,ak)
# (aa,aa1,aa2,ab,ab1,ab2,ab3,ab4,ab5,ab6,ab7,ab8,ab9,ac,ac1,ac2,ad)(ae,ae1,ae2,af)(ag,ah,ai,aj)(ak,al,am,an,ao,ap,aq,ar,as,at,au)
ANALYZE TABLE t2;
SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t2';
# Cleanup
--connection default
DROP TABLE t1;
DROP TABLE t2;
--disable_query_log
SET GLOBAL innodb_limit_optimistic_insert_debug = @old_innodb_limit_optimistic_insert_debug;
SET GLOBAL innodb_adaptive_hash_index = @old_innodb_adaptive_hash_index;
SET GLOBAL innodb_stats_persistent = @old_innodb_stats_persistent;
--enable_query_log
# Wait till all disconnects are completed.
--source include/wait_until_count_sessions.inc
Suggested fix:
Add a counter to track the number of continuous monotonic inserts and if it exceeds a predefined threshold and triggers a split, then apply this strategy
Description: The purpose of btr_page_get_split_rec_to_left is to select an appropriate split record. Its main objective is to keep the insert point on the current page while transferring records before the insert point to the new left page. This avoids repeatedly moving the same records before the insert point, especially if multiple insert operations are targeted at the same insert point. There are two potential weak points of this strategy： 1. The strategy of detecting potential decreasing order inserts by comparing the PAGE_LAST_INSERT with the current insert point is not accurate enough. If the last two insert operations before the split operation are in decreasing order, this strategy will be used, even if the previous inserts were random. 2. Once the strategy is triggered, the insert point is always chosen as the split record. If there are only a few records before the insert point, this left split would result in a sparse new left page and an almost full current page. If we continue randomly inserting into the current page and only ensure that the last two inserts before the split are in decreasing order and at the front of the page, it will create many new sparse left pages repeatedly. These sparse pages could waste space and mislead the SQL optimizer's index dive. btr_page_get_split_rec_to_right also has the same problem. How to repeat: Here is the reproducing MTR case: ---------------------------------------------------------------------------------- --source include/have_debug.inc --source include/have_debug_sync.inc --disable_query_log SET @old_innodb_limit_optimistic_insert_debug = @@innodb_limit_optimistic_insert_debug; SET @old_innodb_adaptive_hash_index = @@innodb_adaptive_hash_index; SET @old_innodb_stats_persistent = @@innodb_stats_persistent; --enable_query_log --disable_warnings DROP TABLE IF EXISTS t1; DROP TABLE IF EXISTS t2; --enable_warnings # Save the initial number of concurrent sessions --source include/count_sessions.inc SET GLOBAL innodb_adaptive_hash_index = false; SET GLOBAL innodb_stats_persistent = false; CREATE TABLE t1 ( a00 CHAR(16) NOT NULL DEFAULT 'a' ) charset latin1 ENGINE = InnoDB; ALTER TABLE t1 ADD CONSTRAINT pkey PRIMARY KEY( a00 ); CREATE TABLE t2 ( a00 CHAR(255) NOT NULL DEFAULT 'a' ) charset latin1 ENGINE = InnoDB; ALTER TABLE t2 ADD CONSTRAINT pkey PRIMARY KEY( a00 ); # # Issue 1 # Left split causes sparse pages # # Only root (1) ANALYZE TABLE t1; SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t1'; SET GLOBAL innodb_limit_optimistic_insert_debug = 20; INSERT INTO t1 (a00) VALUES ('aa'); INSERT INTO t1 (a00) VALUES ('ab'); INSERT INTO t1 (a00) VALUES ('ac'); INSERT INTO t1 (a00) VALUES ('ad'); INSERT INTO t1 (a00) VALUES ('ae'); INSERT INTO t1 (a00) VALUES ('af'); INSERT INTO t1 (a00) VALUES ('ag'); INSERT INTO t1 (a00) VALUES ('ah'); INSERT INTO t1 (a00) VALUES ('ai'); INSERT INTO t1 (a00) VALUES ('aj'); INSERT INTO t1 (a00) VALUES ('ak'); INSERT INTO t1 (a00) VALUES ('al'); INSERT INTO t1 (a00) VALUES ('am'); INSERT INTO t1 (a00) VALUES ('an'); INSERT INTO t1 (a00) VALUES ('ao'); INSERT INTO t1 (a00) VALUES ('ap'); INSERT INTO t1 (a00) VALUES ('aq'); INSERT INTO t1 (a00) VALUES ('ar'); INSERT INTO t1 (a00) VALUES ('as'); INSERT INTO t1 (a00) VALUES ('at'); INSERT INTO t1 (a00) VALUES ('au'); # Raise root (1-2) # (aa,ak) # (aa,ab,ac,ad,ae,af,ag,ah,ai,aj)(ak,al,am,an,ao,ap,aq,ar,as,at,au) ANALYZE TABLE t1; SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t1'; # Insert 8 records in random(non-decreasing) order INSERT INTO t1 (a00) VALUES ('au1'); INSERT INTO t1 (a00) VALUES ('au2'); INSERT INTO t1 (a00) VALUES ('au3'); INSERT INTO t1 (a00) VALUES ('au4'); INSERT INTO t1 (a00) VALUES ('au5'); INSERT INTO t1 (a00) VALUES ('au6'); INSERT INTO t1 (a00) VALUES ('au7'); INSERT INTO t1 (a00) VALUES ('au8'); # Insert 2 records in decreasing order, # it would cause left split and create a sparse page with only 4 records. INSERT INTO t1 (a00) VALUES ('ao2'); INSERT INTO t1 (a00) VALUES ('ao1'); # Split leaf (1-3) # (aa,ak,ao) # (aa,ab,ac,ad,ae,af,ag,ah,ai,aj)(ak,al,am,an)(ao,ao1,ao2,ap,aq,ar,as,at,au,au1,au2,au3,au4,au5,au6,au7,au8) ANALYZE TABLE t1; SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t1'; # Insert 2 records in random(non-decreasing) order INSERT INTO t1 (a00) VALUES ('at1'); INSERT INTO t1 (a00) VALUES ('at2'); # Insert 2 records in decreasing order, # it would cause left split and create a sparse page with only 4 records again. INSERT INTO t1 (a00) VALUES ('aq2'); INSERT INTO t1 (a00) VALUES ('aq1'); # Split leaf (1-4) # (aa,ak,ao) # (aa,ab,ac,ad,ae,af,ag,ah,ai,aj)(ak,al,am,an)(ao,ao1,ao2,ap)(aq,aq1,aq2,ar,as,at,at1,at2,au,au1,au2,au3,au4,au5,au6,au7,au8) ANALYZE TABLE t1; SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t1'; ############################################################ # # Issue 2 # Right split causes sparse pages # # Only root (1) ANALYZE TABLE t2; SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t2'; SET GLOBAL innodb_limit_optimistic_insert_debug = 20; INSERT INTO t2 (a00) VALUES ('aa'); INSERT INTO t2 (a00) VALUES ('ab'); INSERT INTO t2 (a00) VALUES ('ac'); INSERT INTO t2 (a00) VALUES ('ad'); INSERT INTO t2 (a00) VALUES ('ae'); INSERT INTO t2 (a00) VALUES ('af'); INSERT INTO t2 (a00) VALUES ('ag'); INSERT INTO t2 (a00) VALUES ('ah'); INSERT INTO t2 (a00) VALUES ('ai'); INSERT INTO t2 (a00) VALUES ('aj'); INSERT INTO t2 (a00) VALUES ('ak'); INSERT INTO t2 (a00) VALUES ('al'); INSERT INTO t2 (a00) VALUES ('am'); INSERT INTO t2 (a00) VALUES ('an'); INSERT INTO t2 (a00) VALUES ('ao'); INSERT INTO t2 (a00) VALUES ('ap'); INSERT INTO t2 (a00) VALUES ('aq'); INSERT INTO t2 (a00) VALUES ('ar'); INSERT INTO t2 (a00) VALUES ('as'); INSERT INTO t2 (a00) VALUES ('at'); INSERT INTO t2 (a00) VALUES ('au'); # Raise root (1-2) # (aa,ak) # (aa,ab,ac,ad,ae,af,ag,ah,ai,aj)(ak,al,am,an,ao,ap,aq,ar,as,at,au) ANALYZE TABLE t2; SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t2'; # Insert 8 records in random(non-increasing) order INSERT INTO t2 (a00) VALUES ('ab9'); INSERT INTO t2 (a00) VALUES ('ab8'); INSERT INTO t2 (a00) VALUES ('ab7'); INSERT INTO t2 (a00) VALUES ('ab6'); INSERT INTO t2 (a00) VALUES ('ab5'); INSERT INTO t2 (a00) VALUES ('ab4'); INSERT INTO t2 (a00) VALUES ('ab3'); INSERT INTO t2 (a00) VALUES ('ab2'); INSERT INTO t2 (a00) VALUES ('ab1'); # Insert 2 records int increaseing order, # it would cause right split and create a sparse page with only 4 records. INSERT INTO t2 (a00) VALUES ('ae1'); INSERT INTO t2 (a00) VALUES ('ae2'); # Split leaf (1-3) # (aa,ag,ak) # (aa,ab,ab1,ab2,ab3,ab4,ab5,ab6,ab7,ab8,ab9,ac,ad,ae,ae1,ae2,af)(ag,ah,ai,aj)(ak,al,am,an,ao,ap,aq,ar,as,at,au) ANALYZE TABLE t2; SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t2'; # Insert 8 records in random(non-increasing) order INSERT INTO t2 (a00) VALUES ('aa2'); INSERT INTO t2 (a00) VALUES ('aa1'); # Insert 2 records in increaseing order, # it would cause right split and create a sparse page with only 4 records again. INSERT INTO t2 (a00) VALUES ('ac1'); INSERT INTO t2 (a00) VALUES ('ac2'); # Split leaf (1-4) # (aa,ag,ak) # (aa,aa1,aa2,ab,ab1,ab2,ab3,ab4,ab5,ab6,ab7,ab8,ab9,ac,ac1,ac2,ad)(ae,ae1,ae2,af)(ag,ah,ai,aj)(ak,al,am,an,ao,ap,aq,ar,as,at,au) ANALYZE TABLE t2; SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS WHERE NAME = 'test/t2'; # Cleanup --connection default DROP TABLE t1; DROP TABLE t2; --disable_query_log SET GLOBAL innodb_limit_optimistic_insert_debug = @old_innodb_limit_optimistic_insert_debug; SET GLOBAL innodb_adaptive_hash_index = @old_innodb_adaptive_hash_index; SET GLOBAL innodb_stats_persistent = @old_innodb_stats_persistent; --enable_query_log # Wait till all disconnects are completed. --source include/wait_until_count_sessions.inc Suggested fix: Add a counter to track the number of continuous monotonic inserts and if it exceeds a predefined threshold and triggers a split, then apply this strategy