← Back to branch summary

~ubuntu-branches/ubuntu/trusty/mariadb-5.5/trusty-proposed

« back to all changes in this revision

Viewing changes to storage/xtradb/row/row0undo.c

  • Committer: Package Import Robot
  • Author(s): Otto Kekäläinen
  • Date: 2013-12-22 10:27:05 UTC
  • Revision ID: package-import@ubuntu.com-20131222102705-mndw7s12mz0szrcn
Tags: upstream-5.5.32
Import upstream version 5.5.32

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/xtradb/row/row0undo.c
 
1
/*****************************************************************************
 
2
 
 
3
Copyright (c) 1997, 2009, Innobase Oy. All Rights Reserved.
 
4
 
 
5
This program is free software; you can redistribute it and/or modify it under
 
6
the terms of the GNU General Public License as published by the Free Software
 
7
Foundation; version 2 of the License.
 
8
 
 
9
This program is distributed in the hope that it will be useful, but WITHOUT
 
10
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 
11
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 
12
 
 
13
You should have received a copy of the GNU General Public License along with
 
14
this program; if not, write to the Free Software Foundation, Inc., 59 Temple
 
15
Place, Suite 330, Boston, MA 02111-1307 USA
 
16
 
 
17
*****************************************************************************/
 
18
 
 
19
/**************************************************//**
 
20
@file row/row0undo.c
 
21
Row undo
 
22
 
 
23
Created 1/8/1997 Heikki Tuuri
 
24
*******************************************************/
 
25
 
 
26
#include "row0undo.h"
 
27
 
 
28
#ifdef UNIV_NONINL
 
29
#include "row0undo.ic"
 
30
#endif
 
31
 
 
32
#include "fsp0fsp.h"
 
33
#include "mach0data.h"
 
34
#include "trx0rseg.h"
 
35
#include "trx0trx.h"
 
36
#include "trx0roll.h"
 
37
#include "trx0undo.h"
 
38
#include "trx0purge.h"
 
39
#include "trx0rec.h"
 
40
#include "que0que.h"
 
41
#include "row0row.h"
 
42
#include "row0uins.h"
 
43
#include "row0umod.h"
 
44
#include "row0upd.h"
 
45
#include "row0mysql.h"
 
46
#include "srv0srv.h"
 
47
 
 
48
/* How to undo row operations?
 
49
(1) For an insert, we have stored a prefix of the clustered index record
 
50
in the undo log. Using it, we look for the clustered record, and using
 
51
that we look for the records in the secondary indexes. The insert operation
 
52
may have been left incomplete, if the database crashed, for example.
 
53
We may have look at the trx id and roll ptr to make sure the record in the
 
54
clustered index is really the one for which the undo log record was
 
55
written. We can use the framework we get from the original insert op.
 
56
(2) Delete marking: We can use the framework we get from the original
 
57
delete mark op. We only have to check the trx id.
 
58
(3) Update: This may be the most complicated. We have to use the framework
 
59
we get from the original update op.
 
60
 
 
61
What if the same trx repeatedly deletes and inserts an identical row.
 
62
Then the row id changes and also roll ptr. What if the row id was not
 
63
part of the ordering fields in the clustered index? Maybe we have to write
 
64
it to undo log. Well, maybe not, because if we order the row id and trx id
 
65
in descending order, then the only undeleted copy is the first in the
 
66
index. Our searches in row operations always position the cursor before
 
67
the first record in the result set. But, if there is no key defined for
 
68
a table, then it would be desirable that row id is in ascending order.
 
69
So, lets store row id in descending order only if it is not an ordering
 
70
field in the clustered index.
 
71
 
 
72
NOTE: Deletes and inserts may lead to situation where there are identical
 
73
records in a secondary index. Is that a problem in the B-tree? Yes.
 
74
Also updates can lead to this, unless trx id and roll ptr are included in
 
75
ord fields.
 
76
(1) Fix in clustered indexes: include row id, trx id, and roll ptr
 
77
in node pointers of B-tree.
 
78
(2) Fix in secondary indexes: include all fields in node pointers, and
 
79
if an entry is inserted, check if it is equal to the right neighbor,
 
80
in which case update the right neighbor: the neighbor must be delete
 
81
marked, set it unmarked and write the trx id of the current transaction.
 
82
 
 
83
What if the same trx repeatedly updates the same row, updating a secondary
 
84
index field or not? Updating a clustered index ordering field?
 
85
 
 
86
(1) If it does not update the secondary index and not the clustered index
 
87
ord field. Then the secondary index record stays unchanged, but the
 
88
trx id in the secondary index record may be smaller than in the clustered
 
89
index record. This is no problem?
 
90
(2) If it updates secondary index ord field but not clustered: then in
 
91
secondary index there are delete marked records, which differ in an
 
92
ord field. No problem.
 
93
(3) Updates clustered ord field but not secondary, and secondary index
 
94
is unique. Then the record in secondary index is just updated at the
 
95
clustered ord field.
 
96
(4)
 
97
 
 
98
Problem with duplicate records:
 
99
Fix 1: Add a trx op no field to all indexes. A problem: if a trx with a
 
100
bigger trx id has inserted and delete marked a similar row, our trx inserts
 
101
again a similar row, and a trx with an even bigger id delete marks it. Then
 
102
the position of the row should change in the index if the trx id affects
 
103
the alphabetical ordering.
 
104
 
 
105
Fix 2: If an insert encounters a similar row marked deleted, we turn the
 
106
insert into an 'update' of the row marked deleted. Then we must write undo
 
107
info on the update. A problem: what if a purge operation tries to remove
 
108
the delete marked row?
 
109
 
 
110
We can think of the database row versions as a linked list which starts
 
111
from the record in the clustered index, and is linked by roll ptrs
 
112
through undo logs. The secondary index records are references which tell
 
113
what kinds of records can be found in this linked list for a record
 
114
in the clustered index.
 
115
 
 
116
How to do the purge? A record can be removed from the clustered index
 
117
if its linked list becomes empty, i.e., the row has been marked deleted
 
118
and its roll ptr points to the record in the undo log we are going through,
 
119
doing the purge. Similarly, during a rollback, a record can be removed
 
120
if the stored roll ptr in the undo log points to a trx already (being) purged,
 
121
or if the roll ptr is NULL, i.e., it was a fresh insert. */
 
122
 
 
123
/********************************************************************//**
 
124
Creates a row undo node to a query graph.
 
125
@return own: undo node */
 
126
UNIV_INTERN
 
127
undo_node_t*
 
128
row_undo_node_create(
 
129
/*=================*/
 
130
        trx_t*          trx,    /*!< in: transaction */
 
131
        que_thr_t*      parent, /*!< in: parent node, i.e., a thr node */
 
132
        mem_heap_t*     heap)   /*!< in: memory heap where created */
 
133
{
 
134
        undo_node_t*    undo;
 
135
 
 
136
        ut_ad(trx && parent && heap);
 
137
 
 
138
        undo = mem_heap_alloc(heap, sizeof(undo_node_t));
 
139
 
 
140
        undo->common.type = QUE_NODE_UNDO;
 
141
        undo->common.parent = parent;
 
142
 
 
143
        undo->state = UNDO_NODE_FETCH_NEXT;
 
144
        undo->trx = trx;
 
145
 
 
146
        btr_pcur_init(&(undo->pcur));
 
147
 
 
148
        undo->heap = mem_heap_create(256);
 
149
 
 
150
        return(undo);
 
151
}
 
152
 
 
153
/***********************************************************//**
 
154
Looks for the clustered index record when node has the row reference.
 
155
The pcur in node is used in the search. If found, stores the row to node,
 
156
and stores the position of pcur, and detaches it. The pcur must be closed
 
157
by the caller in any case.
 
158
@return TRUE if found; NOTE the node->pcur must be closed by the
 
159
caller, regardless of the return value */
 
160
UNIV_INTERN
 
161
ibool
 
162
row_undo_search_clust_to_pcur(
 
163
/*==========================*/
 
164
        undo_node_t*    node)   /*!< in: row undo node */
 
165
{
 
166
        dict_index_t*   clust_index;
 
167
        ibool           found;
 
168
        mtr_t           mtr;
 
169
        ibool           ret;
 
170
        rec_t*          rec;
 
171
        mem_heap_t*     heap            = NULL;
 
172
        ulint           offsets_[REC_OFFS_NORMAL_SIZE];
 
173
        ulint*          offsets         = offsets_;
 
174
        rec_offs_init(offsets_);
 
175
 
 
176
        mtr_start(&mtr);
 
177
 
 
178
        clust_index = dict_table_get_first_index(node->table);
 
179
 
 
180
        found = row_search_on_row_ref(&(node->pcur), BTR_MODIFY_LEAF,
 
181
                                      node->table, node->ref, &mtr);
 
182
 
 
183
        rec = btr_pcur_get_rec(&(node->pcur));
 
184
 
 
185
        offsets = rec_get_offsets(rec, clust_index, offsets,
 
186
                                  ULINT_UNDEFINED, &heap);
 
187
 
 
188
        if (!found || node->roll_ptr
 
189
            != row_get_rec_roll_ptr(rec, clust_index, offsets)) {
 
190
 
 
191
                /* We must remove the reservation on the undo log record
 
192
                BEFORE releasing the latch on the clustered index page: this
 
193
                is to make sure that some thread will eventually undo the
 
194
                modification corresponding to node->roll_ptr. */
 
195
 
 
196
                /* fputs("--------------------undoing a previous version\n",
 
197
                stderr); */
 
198
 
 
199
                ret = FALSE;
 
200
        } else {
 
201
                row_ext_t**     ext;
 
202
 
 
203
                if (dict_table_get_format(node->table) >= DICT_TF_FORMAT_ZIP) {
 
204
                        /* In DYNAMIC or COMPRESSED format, there is
 
205
                        no prefix of externally stored columns in the
 
206
                        clustered index record. Build a cache of
 
207
                        column prefixes. */
 
208
                        ext = &node->ext;
 
209
                } else {
 
210
                        /* REDUNDANT and COMPACT formats store a local
 
211
                        768-byte prefix of each externally stored
 
212
                        column. No cache is needed. */
 
213
                        ext = NULL;
 
214
                        node->ext = NULL;
 
215
                }
 
216
 
 
217
                node->row = row_build(ROW_COPY_DATA, clust_index, rec,
 
218
                                      offsets, NULL, ext, node->heap);
 
219
                if (node->rec_type == TRX_UNDO_UPD_EXIST_REC) {
 
220
                        node->undo_row = dtuple_copy(node->row, node->heap);
 
221
                        row_upd_replace(node->undo_row, &node->undo_ext,
 
222
                                        clust_index, node->update, node->heap);
 
223
                } else {
 
224
                        node->undo_row = NULL;
 
225
                        node->undo_ext = NULL;
 
226
                }
 
227
 
 
228
                btr_pcur_store_position(&(node->pcur), &mtr);
 
229
 
 
230
                ret = TRUE;
 
231
        }
 
232
 
 
233
        btr_pcur_commit_specify_mtr(&(node->pcur), &mtr);
 
234
 
 
235
        if (UNIV_LIKELY_NULL(heap)) {
 
236
                mem_heap_free(heap);
 
237
        }
 
238
        return(ret);
 
239
}
 
240
 
 
241
/***********************************************************//**
 
242
Fetches an undo log record and does the undo for the recorded operation.
 
243
If none left, or a partial rollback completed, returns control to the
 
244
parent node, which is always a query thread node.
 
245
@return DB_SUCCESS if operation successfully completed, else error code */
 
246
static
 
247
ulint
 
248
row_undo(
 
249
/*=====*/
 
250
        undo_node_t*    node,   /*!< in: row undo node */
 
251
        que_thr_t*      thr)    /*!< in: query thread */
 
252
{
 
253
        ulint           err;
 
254
        trx_t*          trx;
 
255
        roll_ptr_t      roll_ptr;
 
256
        ibool           locked_data_dict;
 
257
 
 
258
        ut_ad(node && thr);
 
259
 
 
260
        trx = node->trx;
 
261
 
 
262
        if (node->state == UNDO_NODE_FETCH_NEXT) {
 
263
 
 
264
                node->undo_rec = trx_roll_pop_top_rec_of_trx(trx,
 
265
                                                             trx->roll_limit,
 
266
                                                             &roll_ptr,
 
267
                                                             node->heap);
 
268
                if (!node->undo_rec) {
 
269
                        /* Rollback completed for this query thread */
 
270
 
 
271
                        thr->run_node = que_node_get_parent(node);
 
272
 
 
273
                        return(DB_SUCCESS);
 
274
                }
 
275
 
 
276
                node->roll_ptr = roll_ptr;
 
277
                node->undo_no = trx_undo_rec_get_undo_no(node->undo_rec);
 
278
 
 
279
                if (trx_undo_roll_ptr_is_insert(roll_ptr)) {
 
280
 
 
281
                        node->state = UNDO_NODE_INSERT;
 
282
                } else {
 
283
                        node->state = UNDO_NODE_MODIFY;
 
284
                }
 
285
        }
 
286
 
 
287
        /* Prevent DROP TABLE etc. while we are rolling back this row.
 
288
        If we are doing a TABLE CREATE or some other dictionary operation,
 
289
        then we already have dict_operation_lock locked in x-mode. Do not
 
290
        try to lock again, because that would cause a hang. */
 
291
 
 
292
        locked_data_dict = (trx->dict_operation_lock_mode == 0);
 
293
 
 
294
        if (locked_data_dict) {
 
295
 
 
296
                row_mysql_freeze_data_dictionary(trx);
 
297
        }
 
298
 
 
299
        if (node->state == UNDO_NODE_INSERT) {
 
300
 
 
301
                err = row_undo_ins(node);
 
302
 
 
303
                node->state = UNDO_NODE_FETCH_NEXT;
 
304
        } else {
 
305
                ut_ad(node->state == UNDO_NODE_MODIFY);
 
306
                err = row_undo_mod(node, thr);
 
307
        }
 
308
 
 
309
        if (locked_data_dict) {
 
310
 
 
311
                row_mysql_unfreeze_data_dictionary(trx);
 
312
        }
 
313
 
 
314
        /* Do some cleanup */
 
315
        btr_pcur_close(&(node->pcur));
 
316
 
 
317
        mem_heap_empty(node->heap);
 
318
 
 
319
        thr->run_node = node;
 
320
 
 
321
        return(err);
 
322
}
 
323
 
 
324
/***********************************************************//**
 
325
Undoes a row operation in a table. This is a high-level function used
 
326
in SQL execution graphs.
 
327
@return query thread to run next or NULL */
 
328
UNIV_INTERN
 
329
que_thr_t*
 
330
row_undo_step(
 
331
/*==========*/
 
332
        que_thr_t*      thr)    /*!< in: query thread */
 
333
{
 
334
        ulint           err;
 
335
        undo_node_t*    node;
 
336
        trx_t*          trx;
 
337
 
 
338
        ut_ad(thr);
 
339
 
 
340
        srv_activity_count++;
 
341
 
 
342
        trx = thr_get_trx(thr);
 
343
 
 
344
        node = thr->run_node;
 
345
 
 
346
        ut_ad(que_node_get_type(node) == QUE_NODE_UNDO);
 
347
 
 
348
        err = row_undo(node, thr);
 
349
 
 
350
        trx->error_state = err;
 
351
 
 
352
        if (err != DB_SUCCESS) {
 
353
                /* SQL error detected */
 
354
 
 
355
                fprintf(stderr, "InnoDB: Fatal error %lu in rollback.\n",
 
356
                        (ulong) err);
 
357
 
 
358
                if (err == DB_OUT_OF_FILE_SPACE) {
 
359
                        fprintf(stderr,
 
360
                                "InnoDB: Error 13 means out of tablespace.\n"
 
361
                                "InnoDB: Consider increasing"
 
362
                                " your tablespace.\n");
 
363
 
 
364
                        exit(1);
 
365
                }
 
366
 
 
367
                ut_error;
 
368
 
 
369
                return(NULL);
 
370
        }
 
371
 
 
372
        return(thr);
 
373
}