| Bug #68069 | mtr_memo_release and dyn_array together are very inefficient | ||
|---|---|---|---|
| Submitted: | 10 Jan 2013 20:02 | Modified: | 12 Feb 2013 20:06 |
| Reporter: | Domas Mituzas | Email Updates: | |
| Status: | Closed | Impact on me: | |
| Category: | MySQL Server: InnoDB storage engine | Severity: | S3 (Non-critical) |
| Version: | 5.1, maybe others | OS: | Any |
| Assigned to: | CPU Architecture: | Any | |
[13 Jan 2013 15:13]
MySQL Verification Team
Thanks Domas!
[13 Jan 2013 19:38]
Marko Mäkelä
Domas, I noticed this O(n^2) in mtr_memo_release() some time ago when I analyzed the stack trace in Bug#67124 (an alleged performance regression in CREATE INDEX, which I was not able to verify). Unfortunately, this was not visible in my testing, and my patch did not make much difference. Thanks to your bug report, we can now develop a test case for this regression. As far as I can tell, the dyn_array and mtr_memo code has remained largely the same since MySQL 4.0, maybe even 3.23.
[12 Feb 2013 20:06]
John Russell
Added to changelog for 5.5.31, 5.6.11: Performance was improved for operations on tables with many rows that were deleted but not yet purged. The speedup applies mainly to workloads that perform bulk deletes, or updates to the primary key columns, and where the system is busy enough to experience purge lag.
[20 Apr 2013 13:38]
Laurynas Biveinis
5.5$ bzr log -r 4165
------------------------------------------------------------
revno: 4165
committer: Marko Mäkelä <marko.makela@oracle.com>
branch nick: mysql-5.5
timestamp: Thu 2013-01-17 17:30:13 +0200
message:
Bug#16138582 MTR_MEMO_RELEASE AND DYN_ARRAY TOGETHER ARE VERY INEFFICIENT
Get rid of O(n^2) scan in dyn array (mtr->memo) operations, accessing
the dyn array blocks directly.
dyn_array_get_last_block(), dyn_array_get_next_block(),
dyn_array_get_prev_block(): Define as a constness-preserving macro.
Add const qualifiers to many dyn_array functions.
mtr_memo_slot_release_func(): Renamed from mtr_memo_slot_release():
Make mtr_t* a debug-only parameter. Assume that slot->object != NULL.
mtr_memo_pop_all(): Access the dyn_array blocks directly, replacing
O(n^2) operation with O(n).
mtr_memo_release(): Access the dyn_array blocks directly, replacing
O(n^2) operation with O(n). This caused the performance problem.
rb#1540 approved by Jimmy Yang
5.6$ bzr log -r 4638 -n0
------------------------------------------------------------
revno: 4638 [merge]
committer: Marko Mäkelä <marko.makela@oracle.com>
branch nick: mysql-5.6
timestamp: Thu 2013-01-17 17:45:20 +0200
message:
Merge mysql-5.5 to mysql-5.6.
------------------------------------------------------------
revno: 2875.417.145
committer: Marko Mäkelä <marko.makela@oracle.com>
branch nick: mysql-5.5
timestamp: Thu 2013-01-17 17:30:13 +0200
message:
Bug#16138582 MTR_MEMO_RELEASE AND DYN_ARRAY TOGETHER ARE VERY INEFFICIENT
Description: This happens on systems that have lots of invisible rows and don't exit InnoDB too much, index reads then will be all CPU heavy at this stack head: Thread 9 (Thread 0x7f4f287ff700 (LWP 20397)): #0 dyn_array_get_next_block (block=<optimized out>, arr=<optimized out>) at ./include/dyn0dyn.ic:86 #1 dyn_array_get_data_size (arr=0x7f4f287fbe50) at ./include/dyn0dyn.ic:335 #2 mtr_memo_release (mtr=0x7f4f287fbe50, object=0x7f50053afb40, type=1) at mtr/mtr0mtr.c:234 #3 0x0000000000838714 in btr_leaf_page_release (mtr=0x7f4f287fbe50, latch_mode=<optimized out>, block=<optimized out>) at ./include/btr0btr.ic:301 Also, this will usually grab index lock, stalling all other operations on the table. Offending code mostly looks like: // THIS WALKS THE MEMO STACK offset = dyn_array_get_data_size(memo); // THIS WALKS THE MEMO STACK AGAIN while (offset > 0) { offset -= sizeof(mtr_memo_slot_t); slot = dyn_array_get_element(memo, offset); if ((object == slot->object) && (type == slot->type)) { mtr_memo_slot_release(mtr, slot); break; } } And indeed, the dyn_array_get_data_size code is walking the dyn_array: while (block != NULL) { sum += dyn_block_get_used(block); block = dyn_array_get_next_block(arr, block); } Queries that hit this problem will burn CPU and will be unkillable while doing that. As these functions are inlined, CPU usage will be all from mtr_memo_release in oprofile/perf/etc How to repeat: Run queries on tables with lots of invisible rows. Suggested fix: At least preaggregate size, if needed.