← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

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

  • Committer: Monty Taylor
  • Date: 2009-03-25 21:06:47 UTC
  • mto: This revision was merged to the branch mainline in revision 964.
  • Revision ID: mordred@inaugust.com-20090325210647-7j1tm98gvct3jxsu
Removed legacy_db_type.

Show diffs side-by-side

added added

removed removed

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