MySQL Bugs: #118363: Another Potential Optimization in row_ins_sec_index_entry

Bug #118363	Another Potential Optimization in row_ins_sec_index_entry_low()
Submitted:	4 Jun 2025 18:00	Modified:	25 Jan 21:28
Reporter:	ZHAO SONG	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: InnoDB storage engine	Severity:	S3 (Non-critical)
Version:	mysql-8.0.41	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
In a previous bug report (https://bugs.mysql.com/bug.php?id=118054), I reported a potential optimization in row_ins_sec_index_entry_low() that can eliminate one B-tree search in specific conditions. It has been verified.
Here, I want to propose another optimization that is more general and can further reduce the number of B-tree searches.

------
Analysis

When inserting a record into a unique key index, the current steps are:

1. Search the tuple (with n_fields_cmp set to the full number of columns) in the B-tree.

2. If a record is found that’s duplicated on index columns, then:

3. Search the tuple (with n_fields_cmp set to the unique columns only) in the B-tree.

4. Starting from the first record, continue moving to the next and check if a truly duplicated record exists. If not, then:

5. Search the tuple again (with n_fields_cmp set to the full number of columns) in the B-tree to find the exact insert point.

6. Insert the new record at that position.

I explained why there are 3 B-tree searches here in the previous report.

The current implementation always sets n_fields_cmp = all columns for the secondary index, regardless of whether the index is unique or not.

------
Proposed Optimization
For a unique index, we could change the approach:

1. Search the tuple (with n_fields_cmp set to the unique columns only) in the B-tree.

1.1 If the record it stops at is not duplicated with the tuple, then insert directly.

1.2 If the record is duplicated with the tuple, continue to move to the next and check if a true duplicate exists. At the same time, decide the proper insert point for the entry (using all columns here).

1.3 If no real duplicate is found, insert the entry directly at the determined insert point.

------
Benefits

This approach requires only one B-tree search.
It can significantly reduce page latch conflicts and improve concurrency. Even in the worst case, the number of record comparisons wouldn’t exceed the current implementation.

How to repeat:
It can be easily reproduced by inserting into a unique index that contains many potential duplicate records for the inserted tuple.
You can use the same reproduction approach as in my previous report: https://bugs.mysql.com/bug.php?id=118054.

Thank you for your thoughts

Posted by developer:
 
I mostly agree with the analysis (also found in their post https://www.linkedin.com/posts/zhao-song-733b91269_in-my-previous-post-i-discussed-how-man...)

The devil is in the details around latching (when we start/commit mini-transactions) and locking (which record and gap is locked in what mode and which duration).
At high level the proposal seems very reasonable.
But on the low level it is not obvious to me how to implement it correctly.
The current solution, in step 2, uses peculiar kind of locks which might be released at the end of a statement (as opposed to more typical ones which are not released until COMMIT/ROLLBACK of the transaction).
Also each of three steps uses a separate mtr (with a complication that in step 2 the mtr releases latche on a previous page it moved from when iterating to the next page).

So if we want to combine all that in one big function we might need keep some of that behaviour/side-effects intact to preserve meaning/correctness or even performance.
This in turn might lead to some copy&pasted code or introduction of subtle bugs.

Thus it would be nice to first see some proof that this is indeed a performance bottleneck and that a PoC could indeed improve performance.

Hi Jakub,

Following up on your request for a proof-of-concept demonstrating actual improvements, I've implemented a working POC for this optimization.

Repository: https://github.com/KernelMaker/mysql-server/commit/827c8962c4baec09e103105a8d88f56b738510c...

Approach:
Instead of the current 3-search flow:
1. Use PAGE_CUR_GE with n_unique columns for Search 1
2. Scan forward from cursor position while holding page latches
3. Track insert position during scan (last rec <= entry on all columns)
4. Insert directly without Search 2 and Search 3

Key implementation details:
> Cross-page scanning uses left-to-right latch acquisition (safe ordering)
> Insert position is tracked across pages via insert_pos_block
! Falls back to original path when no potential duplicate found (PAGE_CUR_GE position invalid for insert)

!Note on fallback path: When PAGE_CUR_GE finds no potential duplicate, the current POC falls back to a full re-search with PAGE_CUR_LE. This could be further optimized by simply moving to the previous record within the same page (if cursor is not at infimum) to find the insert position, avoiding the extra B-tree
traversal. I haven't implemented this as it's beyond the scope of demonstrating the core optimization.

Benchmark Methodology:

1. Setup: Table with 200K rows, VARCHAR(700) unique key (latin1), creating a tall B-tree
CREATE TABLE t1 (
id INT PRIMARY KEY AUTO_INCREMENT,
uk_col VARCHAR(700) NOT NULL,
UNIQUE KEY uk_idx (uk_col)
) ENGINE=InnoDB CHARACTER SET latin1;

2. Insert 100 TARGET rows with prefix "TARGET_ROW_"
3. Start a blocker transaction (START TRANSACTION WITH CONSISTENT SNAPSHOT) to prevent purge
4. Delete the 100 TARGET rows (creates delete-marked records)
5. Re-insert the same 100 TARGET rows - this triggers the duplicate check path since delete-marked records with matching unique key exist
6. Instrumentation: Added nanosecond-precision timing around each search operation in row_ins_sec_index_entry_low(). Metrics are accumulated in memory and dumped via system variable to avoid I/O overhead during measurement.
7. Ran benchmark twice: once with original path, reset metrics, then with optimized path.

Results:
Original path (3 B-tree searches):
Search1: ~6,508 ns
Search2: ~5,649 ns
Search3: ~2,498 ns
Total: ~14,656 ns

Optimized path (1 B-tree search + inline scan):
Search1: ~7,272 ns
Inline: ~3,118 ns
Total: ~10,390 ns

Improvement: ~29.1% reduction in search path time

The benchmark focuses on measuring time saved within the scope of the original 3 B-tree searches per insert. Since these searches hold page latches, reducing this time also reduces latch holding duration, which could benefit parallelism under concurrent workloads.

This is a quick POC to verify the potential benefits of this optimization. A production-quality patch would require more careful design and comprehensive consideration of edge cases, error handling, and interaction with other InnoDB components.

I'd appreciate any feedback on the approach or implementation.

Thanks,
Zhao Song