1 /*****************************************************************************
2
3 Copyright (c) 1997, 2021, Oracle and/or its affiliates.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License, version 2.0,
7 as published by the Free Software Foundation.
8
9 This program is also distributed with certain software (including
10 but not limited to OpenSSL) that is licensed under separate terms,
11 as designated in a particular file or component or in included license
12 documentation. The authors of MySQL hereby grant you an additional
13 permission to link the program and your derivative works with the
14 separately licensed software that they have included with MySQL.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License, version 2.0, for more details.
20
21 You should have received a copy of the GNU General Public License along with
22 this program; if not, write to the Free Software Foundation, Inc.,
23 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
24
25 *****************************************************************************/
26
27 /**************************************************//**
28 @file row/row0undo.cc
29 Row undo
30
31 Created 1/8/1997 Heikki Tuuri
32 *******************************************************/
33
34 #include "ha_prototypes.h"
35
36 #include "row0undo.h"
37
38 #ifdef UNIV_NONINL
39 #include "row0undo.ic"
40 #endif
41
42 #include "fsp0fsp.h"
43 #include "mach0data.h"
44 #include "trx0rseg.h"
45 #include "trx0trx.h"
46 #include "trx0roll.h"
47 #include "trx0undo.h"
48 #include "trx0purge.h"
49 #include "trx0rec.h"
50 #include "que0que.h"
51 #include "row0row.h"
52 #include "row0uins.h"
53 #include "row0umod.h"
54 #include "row0upd.h"
55 #include "row0mysql.h"
56 #include "srv0srv.h"
57
58 /* How to undo row operations?
59 (1) For an insert, we have stored a prefix of the clustered index record
60 in the undo log. Using it, we look for the clustered record, and using
61 that we look for the records in the secondary indexes. The insert operation
62 may have been left incomplete, if the database crashed, for example.
63 We may have look at the trx id and roll ptr to make sure the record in the
64 clustered index is really the one for which the undo log record was
65 written. We can use the framework we get from the original insert op.
66 (2) Delete marking: We can use the framework we get from the original
67 delete mark op. We only have to check the trx id.
68 (3) Update: This may be the most complicated. We have to use the framework
69 we get from the original update op.
70
71 What if the same trx repeatedly deletes and inserts an identical row.
72 Then the row id changes and also roll ptr. What if the row id was not
73 part of the ordering fields in the clustered index? Maybe we have to write
74 it to undo log. Well, maybe not, because if we order the row id and trx id
75 in descending order, then the only undeleted copy is the first in the
76 index. Our searches in row operations always position the cursor before
77 the first record in the result set. But, if there is no key defined for
78 a table, then it would be desirable that row id is in ascending order.
79 So, lets store row id in descending order only if it is not an ordering
80 field in the clustered index.
81
82 NOTE: Deletes and inserts may lead to situation where there are identical
83 records in a secondary index. Is that a problem in the B-tree? Yes.
84 Also updates can lead to this, unless trx id and roll ptr are included in
85 ord fields.
86 (1) Fix in clustered indexes: include row id, trx id, and roll ptr
87 in node pointers of B-tree.
88 (2) Fix in secondary indexes: include all fields in node pointers, and
89 if an entry is inserted, check if it is equal to the right neighbor,
90 in which case update the right neighbor: the neighbor must be delete
91 marked, set it unmarked and write the trx id of the current transaction.
92
93 What if the same trx repeatedly updates the same row, updating a secondary
94 index field or not? Updating a clustered index ordering field?
95
96 (1) If it does not update the secondary index and not the clustered index
97 ord field. Then the secondary index record stays unchanged, but the
98 trx id in the secondary index record may be smaller than in the clustered
99 index record. This is no problem?
100 (2) If it updates secondary index ord field but not clustered: then in
101 secondary index there are delete marked records, which differ in an
102 ord field. No problem.
103 (3) Updates clustered ord field but not secondary, and secondary index
104 is unique. Then the record in secondary index is just updated at the
105 clustered ord field.
106 (4)
107
108 Problem with duplicate records:
109 Fix 1: Add a trx op no field to all indexes. A problem: if a trx with a
110 bigger trx id has inserted and delete marked a similar row, our trx inserts
111 again a similar row, and a trx with an even bigger id delete marks it. Then
112 the position of the row should change in the index if the trx id affects
113 the alphabetical ordering.
114
115 Fix 2: If an insert encounters a similar row marked deleted, we turn the
116 insert into an 'update' of the row marked deleted. Then we must write undo
117 info on the update. A problem: what if a purge operation tries to remove
118 the delete marked row?
119
120 We can think of the database row versions as a linked list which starts
121 from the record in the clustered index, and is linked by roll ptrs
122 through undo logs. The secondary index records are references which tell
123 what kinds of records can be found in this linked list for a record
124 in the clustered index.
125
126 How to do the purge? A record can be removed from the clustered index
127 if its linked list becomes empty, i.e., the row has been marked deleted
128 and its roll ptr points to the record in the undo log we are going through,
129 doing the purge. Similarly, during a rollback, a record can be removed
130 if the stored roll ptr in the undo log points to a trx already (being) purged,
131 or if the roll ptr is NULL, i.e., it was a fresh insert. */
132
133 /********************************************************************//**
134 Creates a row undo node to a query graph.
135 @return own: undo node */
136 undo_node_t*
row_undo_node_create(trx_t * trx,que_thr_t * parent,mem_heap_t * heap,bool partial_rollback)137 row_undo_node_create(
138 /*=================*/
139 trx_t* trx, /*!< in/out: transaction */
140 que_thr_t* parent, /*!< in: parent node, i.e., a thr node */
141 mem_heap_t* heap, /*!< in: memory heap where created */
142 bool partial_rollback) /*!< in: true if partial rollback */
143 {
144 undo_node_t* undo;
145
146 ut_ad(trx_state_eq(trx, TRX_STATE_ACTIVE)
147 || trx_state_eq(trx, TRX_STATE_PREPARED));
148 ut_ad(parent);
149
150 undo = static_cast<undo_node_t*>(
151 mem_heap_alloc(heap, sizeof(undo_node_t)));
152
153 undo->common.type = QUE_NODE_UNDO;
154 undo->common.parent = parent;
155
156 undo->state = UNDO_NODE_FETCH_NEXT;
157 undo->trx = trx;
158
159 undo->partial = partial_rollback;
160
161 btr_pcur_init(&(undo->pcur));
162
163 undo->heap = mem_heap_create(256);
164
165 return(undo);
166 }
167
168 /***********************************************************//**
169 Looks for the clustered index record when node has the row reference.
170 The pcur in node is used in the search. If found, stores the row to node,
171 and stores the position of pcur, and detaches it. The pcur must be closed
172 by the caller in any case.
173 @return true if found; NOTE the node->pcur must be closed by the
174 caller, regardless of the return value */
175 bool
row_undo_search_clust_to_pcur(undo_node_t * node)176 row_undo_search_clust_to_pcur(
177 /*==========================*/
178 undo_node_t* node) /*!< in/out: row undo node */
179 {
180 dict_index_t* clust_index;
181 bool found;
182 mtr_t mtr;
183 row_ext_t** ext;
184 const rec_t* rec;
185 mem_heap_t* heap = NULL;
186 ulint offsets_[REC_OFFS_NORMAL_SIZE];
187 ulint* offsets = offsets_;
188 rec_offs_init(offsets_);
189
190 mtr_start(&mtr);
191 dict_disable_redo_if_temporary(node->table, &mtr);
192
193 clust_index = dict_table_get_first_index(node->table);
194
195 found = row_search_on_row_ref(&node->pcur, BTR_MODIFY_LEAF,
196 node->table, node->ref, &mtr);
197
198 if (!found) {
199 goto func_exit;
200 }
201
202 rec = btr_pcur_get_rec(&node->pcur);
203
204 offsets = rec_get_offsets(rec, clust_index, offsets,
205 ULINT_UNDEFINED, &heap);
206
207 found = row_get_rec_roll_ptr(rec, clust_index, offsets)
208 == node->roll_ptr;
209
210 if (found) {
211 ut_ad(row_get_rec_trx_id(rec, clust_index, offsets)
212 == node->trx->id);
213
214 if (dict_table_get_format(node->table) >= UNIV_FORMAT_B) {
215 /* In DYNAMIC or COMPRESSED format, there is
216 no prefix of externally stored columns in the
217 clustered index record. Build a cache of
218 column prefixes. */
219 ext = &node->ext;
220 } else {
221 /* REDUNDANT and COMPACT formats store a local
222 768-byte prefix of each externally stored
223 column. No cache is needed. */
224 ext = NULL;
225 node->ext = NULL;
226 }
227
228 node->row = row_build(ROW_COPY_DATA, clust_index, rec,
229 offsets, NULL,
230 NULL, NULL, ext, node->heap);
231
232 /* We will need to parse out virtual column info from undo
233 log, first mark them DATA_MISSING. So we will know if the
234 value gets updated */
235 if (node->table->n_v_cols
236 && node->state != UNDO_NODE_INSERT
237 && !(node->cmpl_info & UPD_NODE_NO_ORD_CHANGE)) {
238 for (ulint i = 0;
239 i < dict_table_get_n_v_cols(node->table); i++) {
240 dfield_get_type(dtuple_get_nth_v_field(
241 node->row, i))->mtype = DATA_MISSING;
242 }
243 }
244
245 if (node->rec_type == TRX_UNDO_UPD_EXIST_REC) {
246 node->undo_row = dtuple_copy(node->row, node->heap);
247 row_upd_replace(node->undo_row, &node->undo_ext,
248 clust_index, node->update, node->heap);
249 } else {
250 node->undo_row = NULL;
251 node->undo_ext = NULL;
252 }
253
254 btr_pcur_store_position(&node->pcur, &mtr);
255 }
256
257 if (heap) {
258 mem_heap_free(heap);
259 }
260
261 func_exit:
262 btr_pcur_commit_specify_mtr(&node->pcur, &mtr);
263 return(found);
264 }
265
266 /***********************************************************//**
267 Fetches an undo log record and does the undo for the recorded operation.
268 If none left, or a partial rollback completed, returns control to the
269 parent node, which is always a query thread node.
270 @return DB_SUCCESS if operation successfully completed, else error code */
271 static MY_ATTRIBUTE((warn_unused_result))
272 dberr_t
row_undo(undo_node_t * node,que_thr_t * thr)273 row_undo(
274 /*=====*/
275 undo_node_t* node, /*!< in: row undo node */
276 que_thr_t* thr) /*!< in: query thread */
277 {
278 dberr_t err;
279 trx_t* trx;
280 roll_ptr_t roll_ptr;
281 ibool locked_data_dict;
282
283 ut_ad(node != NULL);
284 ut_ad(thr != NULL);
285
286 trx = node->trx;
287 ut_ad(trx->in_rollback);
288
289 if (node->state == UNDO_NODE_FETCH_NEXT) {
290
291 node->undo_rec = trx_roll_pop_top_rec_of_trx(
292 trx, trx->roll_limit, &roll_ptr, node->heap);
293
294 if (!node->undo_rec) {
295 /* Rollback completed for this query thread */
296
297 thr->run_node = que_node_get_parent(node);
298
299 /* Mark any partial rollback completed, so
300 that if the transaction object is committed
301 and reused later, the roll_limit will remain
302 at 0. trx->roll_limit will be nonzero during a
303 partial rollback only. */
304 trx->roll_limit = 0;
305 ut_d(trx->in_rollback = false);
306
307 return(DB_SUCCESS);
308 }
309
310 node->roll_ptr = roll_ptr;
311 node->undo_no = trx_undo_rec_get_undo_no(node->undo_rec);
312
313 if (trx_undo_roll_ptr_is_insert(roll_ptr)) {
314
315 node->state = UNDO_NODE_INSERT;
316 } else {
317 node->state = UNDO_NODE_MODIFY;
318 }
319 }
320
321 /* Prevent DROP TABLE etc. while we are rolling back this row.
322 If we are doing a TABLE CREATE or some other dictionary operation,
323 then we already have dict_operation_lock locked in x-mode. Do not
324 try to lock again, because that would cause a hang. */
325
326 locked_data_dict = (trx->dict_operation_lock_mode == 0);
327
328 if (locked_data_dict) {
329
330 row_mysql_freeze_data_dictionary(trx);
331 }
332
333 if (node->state == UNDO_NODE_INSERT) {
334
335 err = row_undo_ins(node, thr);
336
337 node->state = UNDO_NODE_FETCH_NEXT;
338 } else {
339 ut_ad(node->state == UNDO_NODE_MODIFY);
340 err = row_undo_mod(node, thr);
341 }
342
343 if (locked_data_dict) {
344
345 row_mysql_unfreeze_data_dictionary(trx);
346 }
347
348 /* Do some cleanup */
349 btr_pcur_close(&(node->pcur));
350
351 mem_heap_empty(node->heap);
352
353 thr->run_node = node;
354
355 return(err);
356 }
357
358 void
row_convert_impl_to_expl_if_needed(btr_cur_t * cursor,undo_node_t * node)359 row_convert_impl_to_expl_if_needed(
360 /*===============================*/
361 btr_cur_t* cursor, /*!< in: cursor to record */
362 undo_node_t* node) /*!< in: undo node */
363 {
364 ulint* offsets = NULL;
365
366 /* In case of partial rollback implicit lock on the
367 record is released in the middle of transaction, which
368 can break the serializability of IODKU and REPLACE
369 statements. Normal rollback is not affected by this
370 becasue we release the locks after the rollback. So
371 to prevent any other transaction modifying the record
372 in between the partial rollback we convert the implicit
373 lock on the record to explict. When the record is actually
374 deleted this lock be inherited by the next record. */
375
376 if (!node->partial
377 || (node->trx == NULL)
378 || node->trx->isolation_level < TRX_ISO_REPEATABLE_READ){
379 return;
380 }
381
382 ut_ad(node->trx->in_rollback);
383 dict_index_t* index = btr_cur_get_index(cursor);
384 rec_t* rec = btr_cur_get_rec(cursor);
385 buf_block_t* block = btr_cur_get_block(cursor);
386 ulint heap_no = page_rec_get_heap_no(rec);
387
388 if (heap_no != PAGE_HEAP_NO_SUPREMUM
389 && !dict_table_is_intrinsic(index->table)
390 && !dict_table_is_temporary(index->table)
391 && !dict_index_is_spatial(index)) {
392 lock_rec_convert_active_impl_to_expl(block, rec, index,
393 offsets,node->trx,heap_no);
394 }
395 }
396
397 /***********************************************************//**
398 Undoes a row operation in a table. This is a high-level function used
399 in SQL execution graphs.
400 @return query thread to run next or NULL */
401 que_thr_t*
row_undo_step(que_thr_t * thr)402 row_undo_step(
403 /*==========*/
404 que_thr_t* thr) /*!< in: query thread */
405 {
406 dberr_t err;
407 undo_node_t* node;
408 trx_t* trx;
409
410 ut_ad(thr);
411
412 srv_inc_activity_count();
413
414 trx = thr_get_trx(thr);
415
416 node = static_cast<undo_node_t*>(thr->run_node);
417
418 ut_ad(que_node_get_type(node) == QUE_NODE_UNDO);
419
420 err = row_undo(node, thr);
421
422 trx->error_state = err;
423
424 if (err != DB_SUCCESS) {
425 /* SQL error detected */
426
427 if (err == DB_OUT_OF_FILE_SPACE) {
428 ib::fatal() << "Out of tablespace during rollback."
429 " Consider increasing your tablespace.";
430 }
431
432 ib::fatal() << "Error (" << ut_strerr(err) << ") in rollback.";
433 }
434
435 return(thr);
436 }
437