← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

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

  • Committer: Brian Aker
  • Date: 2008-10-29 13:46:43 UTC
  • Revision ID: brian@tangent.org-20081029134643-z6jcwjvyruhk2vlu
Updates for ignore file.

Show diffs side-by-side

added added

removed removed

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