← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to plugin/innobase/include/page0zip.ic

  • Committer: Monty Taylor
  • Date: 2008-09-16 00:00:48 UTC
  • mto: This revision was merged to the branch mainline in revision 391.
  • Revision ID: monty@inaugust.com-20080916000048-3rvrv3gv9l0ad3gs
Fixed copyright headers in drizzled/

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/innobase/include/page0zip.ic
1
 
/*****************************************************************************
2
 
 
3
 
Copyright (C) 2005, 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., 51 Franklin
15
 
St, Fifth Floor, Boston, MA 02110-1301 USA
16
 
 
17
 
*****************************************************************************/
18
 
 
19
 
/**************************************************//**
20
 
@file include/page0zip.ic
21
 
Compressed page interface
22
 
 
23
 
Created June 2005 by Marko Makela
24
 
*******************************************************/
25
 
 
26
 
#ifdef UNIV_MATERIALIZE
27
 
# undef UNIV_INLINE
28
 
# define UNIV_INLINE
29
 
#endif
30
 
 
31
 
#include "page0zip.h"
32
 
#include "page0page.h"
33
 
 
34
 
/* The format of compressed pages is as follows.
35
 
 
36
 
The header and trailer of the uncompressed pages, excluding the page
37
 
directory in the trailer, are copied as is to the header and trailer
38
 
of the compressed page.
39
 
 
40
 
At the end of the compressed page, there is a dense page directory
41
 
pointing to every user record contained on the page, including deleted
42
 
records on the free list.  The dense directory is indexed in the
43
 
collation order, i.e., in the order in which the record list is
44
 
linked on the uncompressed page.  The infimum and supremum records are
45
 
excluded.  The two most significant bits of the entries are allocated
46
 
for the delete-mark and an n_owned flag indicating the last record in
47
 
a chain of records pointed to from the sparse page directory on the
48
 
uncompressed page.
49
 
 
50
 
The data between PAGE_ZIP_START and the last page directory entry will
51
 
be written in compressed format, starting at offset PAGE_DATA.
52
 
Infimum and supremum records are not stored.  We exclude the
53
 
REC_N_NEW_EXTRA_BYTES in every record header.  These can be recovered
54
 
from the dense page directory stored at the end of the compressed
55
 
page.
56
 
 
57
 
The fields node_ptr (in non-leaf B-tree nodes; level>0), trx_id and
58
 
roll_ptr (in leaf B-tree nodes; level=0), and BLOB pointers of
59
 
externally stored columns are stored separately, in ascending order of
60
 
heap_no and column index, starting backwards from the dense page
61
 
directory.
62
 
 
63
 
The compressed data stream may be followed by a modification log
64
 
covering the compressed portion of the page, as follows.
65
 
 
66
 
MODIFICATION LOG ENTRY FORMAT
67
 
- write record:
68
 
  - (heap_no - 1) << 1 (1..2 bytes)
69
 
  - extra bytes backwards
70
 
  - data bytes
71
 
- clear record:
72
 
  - (heap_no - 1) << 1 | 1 (1..2 bytes)
73
 
 
74
 
The integer values are stored in a variable-length format:
75
 
- 0xxxxxxx: 0..127
76
 
- 1xxxxxxx xxxxxxxx: 0..32767
77
 
 
78
 
The end of the modification log is marked by a 0 byte.
79
 
 
80
 
In summary, the compressed page looks like this:
81
 
 
82
 
(1) Uncompressed page header (PAGE_DATA bytes)
83
 
(2) Compressed index information
84
 
(3) Compressed page data
85
 
(4) Page modification log (page_zip->m_start..page_zip->m_end)
86
 
(5) Empty zero-filled space
87
 
(6) BLOB pointers (on leaf pages)
88
 
  - BTR_EXTERN_FIELD_REF_SIZE for each externally stored column
89
 
  - in descending collation order
90
 
(7) Uncompressed columns of user records, n_dense * uncompressed_size bytes,
91
 
  - indexed by heap_no
92
 
  - DATA_TRX_ID_LEN + DATA_ROLL_PTR_LEN for leaf pages of clustered indexes
93
 
  - REC_NODE_PTR_SIZE for non-leaf pages
94
 
  - 0 otherwise
95
 
(8) dense page directory, stored backwards
96
 
  - n_dense = n_heap - 2
97
 
  - existing records in ascending collation order
98
 
  - deleted records (free list) in link order
99
 
*/
100
 
 
101
 
/** Start offset of the area that will be compressed */
102
 
#define PAGE_ZIP_START          PAGE_NEW_SUPREMUM_END
103
 
/** Size of an compressed page directory entry */
104
 
#define PAGE_ZIP_DIR_SLOT_SIZE  2
105
 
/** Mask of record offsets */
106
 
#define PAGE_ZIP_DIR_SLOT_MASK  0x3fff
107
 
/** 'owned' flag */
108
 
#define PAGE_ZIP_DIR_SLOT_OWNED 0x4000
109
 
/** 'deleted' flag */
110
 
#define PAGE_ZIP_DIR_SLOT_DEL   0x8000
111
 
 
112
 
/**********************************************************************//**
113
 
Determine the size of a compressed page in bytes.
114
 
@return size in bytes */
115
 
UNIV_INLINE
116
 
ulint
117
 
page_zip_get_size(
118
 
/*==============*/
119
 
        const page_zip_des_t*   page_zip)       /*!< in: compressed page */
120
 
{
121
 
        ulint   size;
122
 
 
123
 
        if (UNIV_UNLIKELY(!page_zip->ssize)) {
124
 
                return(0);
125
 
        }
126
 
 
127
 
        size = (PAGE_ZIP_MIN_SIZE >> 1) << page_zip->ssize;
128
 
 
129
 
        ut_ad(size >= PAGE_ZIP_MIN_SIZE);
130
 
        ut_ad(size <= UNIV_PAGE_SIZE);
131
 
 
132
 
        return(size);
133
 
}
134
 
/**********************************************************************//**
135
 
Set the size of a compressed page in bytes. */
136
 
UNIV_INLINE
137
 
void
138
 
page_zip_set_size(
139
 
/*==============*/
140
 
        page_zip_des_t* page_zip,       /*!< in/out: compressed page */
141
 
        ulint           size)           /*!< in: size in bytes */
142
 
{
143
 
        if (size) {
144
 
                int     ssize;
145
 
 
146
 
                ut_ad(ut_is_2pow(size));
147
 
 
148
 
                for (ssize = 1; size > (ulint) (512 << ssize); ssize++) {
149
 
                }
150
 
 
151
 
                page_zip->ssize = ssize;
152
 
        } else {
153
 
                page_zip->ssize = 0;
154
 
        }
155
 
 
156
 
        ut_ad(page_zip_get_size(page_zip) == size);
157
 
}
158
 
 
159
 
#ifndef UNIV_HOTBACKUP
160
 
/**********************************************************************//**
161
 
Determine if a record is so big that it needs to be stored externally.
162
 
@return FALSE if the entire record can be stored locally on the page */
163
 
UNIV_INLINE
164
 
ibool
165
 
page_zip_rec_needs_ext(
166
 
/*===================*/
167
 
        ulint   rec_size,       /*!< in: length of the record in bytes */
168
 
        ulint   comp,           /*!< in: nonzero=compact format */
169
 
        ulint   n_fields,       /*!< in: number of fields in the record;
170
 
                                ignored if zip_size == 0 */
171
 
        ulint   zip_size)       /*!< in: compressed page size in bytes, or 0 */
172
 
{
173
 
        ut_ad(rec_size > comp ? REC_N_NEW_EXTRA_BYTES : REC_N_OLD_EXTRA_BYTES);
174
 
        ut_ad(ut_is_2pow(zip_size));
175
 
        ut_ad(comp || !zip_size);
176
 
 
177
 
#if UNIV_PAGE_SIZE > REC_MAX_DATA_SIZE
178
 
        if (UNIV_UNLIKELY(rec_size >= REC_MAX_DATA_SIZE)) {
179
 
                return(TRUE);
180
 
        }
181
 
#endif
182
 
 
183
 
        if (UNIV_UNLIKELY(zip_size)) {
184
 
                ut_ad(comp);
185
 
                /* On a compressed page, there is a two-byte entry in
186
 
                the dense page directory for every record.  But there
187
 
                is no record header.  There should be enough room for
188
 
                one record on an empty leaf page.  Subtract 1 byte for
189
 
                the encoded heap number.  Check also the available space
190
 
                on the uncompressed page. */
191
 
                return(rec_size - (REC_N_NEW_EXTRA_BYTES - 2)
192
 
                       >= (page_zip_empty_size(n_fields, zip_size) - 1)
193
 
                       || rec_size >= page_get_free_space_of_empty(TRUE) / 2);
194
 
        }
195
 
 
196
 
        return(rec_size >= page_get_free_space_of_empty(comp) / 2);
197
 
}
198
 
#endif /* !UNIV_HOTBACKUP */
199
 
 
200
 
#ifdef UNIV_DEBUG
201
 
/**********************************************************************//**
202
 
Validate a compressed page descriptor.
203
 
@return TRUE if ok */
204
 
UNIV_INLINE
205
 
ibool
206
 
page_zip_simple_validate(
207
 
/*=====================*/
208
 
        const page_zip_des_t*   page_zip)/*!< in: compressed page descriptor */
209
 
{
210
 
        ut_ad(page_zip);
211
 
        ut_ad(page_zip->data);
212
 
        ut_ad(page_zip->ssize < PAGE_ZIP_NUM_SSIZE);
213
 
        ut_ad(page_zip_get_size(page_zip)
214
 
              > PAGE_DATA + PAGE_ZIP_DIR_SLOT_SIZE);
215
 
        ut_ad(page_zip->m_start <= page_zip->m_end);
216
 
        ut_ad(page_zip->m_end < page_zip_get_size(page_zip));
217
 
        ut_ad(page_zip->n_blobs
218
 
              < page_zip_get_size(page_zip) / BTR_EXTERN_FIELD_REF_SIZE);
219
 
        return(TRUE);
220
 
}
221
 
#endif /* UNIV_DEBUG */
222
 
 
223
 
/**********************************************************************//**
224
 
Determine if the length of the page trailer.
225
 
@return length of the page trailer, in bytes, not including the
226
 
terminating zero byte of the modification log */
227
 
UNIV_INLINE
228
 
ibool
229
 
page_zip_get_trailer_len(
230
 
/*=====================*/
231
 
        const page_zip_des_t*   page_zip,/*!< in: compressed page */
232
 
        ibool                   is_clust,/*!< in: TRUE if clustered index */
233
 
        ulint*                  entry_size)/*!< out: size of the uncompressed
234
 
                                        portion of a user record */
235
 
{
236
 
        ulint   uncompressed_size;
237
 
 
238
 
        ut_ad(page_zip_simple_validate(page_zip));
239
 
        UNIV_MEM_ASSERT_RW(page_zip->data, page_zip_get_size(page_zip));
240
 
 
241
 
        if (UNIV_UNLIKELY(!page_is_leaf(page_zip->data))) {
242
 
                uncompressed_size = PAGE_ZIP_DIR_SLOT_SIZE
243
 
                        + REC_NODE_PTR_SIZE;
244
 
                ut_ad(!page_zip->n_blobs);
245
 
        } else if (UNIV_UNLIKELY(is_clust)) {
246
 
                uncompressed_size = PAGE_ZIP_DIR_SLOT_SIZE
247
 
                        + DATA_TRX_ID_LEN + DATA_ROLL_PTR_LEN;
248
 
        } else {
249
 
                uncompressed_size = PAGE_ZIP_DIR_SLOT_SIZE;
250
 
                ut_ad(!page_zip->n_blobs);
251
 
        }
252
 
 
253
 
        if (entry_size) {
254
 
                *entry_size = uncompressed_size;
255
 
        }
256
 
 
257
 
        return((page_dir_get_n_heap(page_zip->data) - 2)
258
 
               * uncompressed_size
259
 
               + page_zip->n_blobs * BTR_EXTERN_FIELD_REF_SIZE);
260
 
}
261
 
 
262
 
/**********************************************************************//**
263
 
Determine how big record can be inserted without recompressing the page.
264
 
@return a positive number indicating the maximum size of a record
265
 
whose insertion is guaranteed to succeed, or zero or negative */
266
 
UNIV_INLINE
267
 
lint
268
 
page_zip_max_ins_size(
269
 
/*==================*/
270
 
        const page_zip_des_t*   page_zip,/*!< in: compressed page */
271
 
        ibool                   is_clust)/*!< in: TRUE if clustered index */
272
 
{
273
 
        ulint   uncompressed_size;
274
 
        ulint   trailer_len;
275
 
 
276
 
        trailer_len = page_zip_get_trailer_len(page_zip, is_clust,
277
 
                                               &uncompressed_size);
278
 
 
279
 
        /* When a record is created, a pointer may be added to
280
 
        the dense directory.
281
 
        Likewise, space for the columns that will not be
282
 
        compressed will be allocated from the page trailer.
283
 
        Also the BLOB pointers will be allocated from there, but
284
 
        we may as well count them in the length of the record. */
285
 
 
286
 
        trailer_len += uncompressed_size;
287
 
 
288
 
        return((lint) page_zip_get_size(page_zip)
289
 
               - trailer_len - page_zip->m_end
290
 
               - (REC_N_NEW_EXTRA_BYTES - 2));
291
 
}
292
 
 
293
 
/**********************************************************************//**
294
 
Determine if enough space is available in the modification log.
295
 
@return TRUE if enough space is available */
296
 
UNIV_INLINE
297
 
ibool
298
 
page_zip_available(
299
 
/*===============*/
300
 
        const page_zip_des_t*   page_zip,/*!< in: compressed page */
301
 
        ibool                   is_clust,/*!< in: TRUE if clustered index */
302
 
        ulint                   length, /*!< in: combined size of the record */
303
 
        ulint                   create) /*!< in: nonzero=add the record to
304
 
                                        the heap */
305
 
{
306
 
        ulint   uncompressed_size;
307
 
        ulint   trailer_len;
308
 
 
309
 
        ut_ad(length > REC_N_NEW_EXTRA_BYTES);
310
 
 
311
 
        trailer_len = page_zip_get_trailer_len(page_zip, is_clust,
312
 
                                               &uncompressed_size);
313
 
 
314
 
        /* Subtract the fixed extra bytes and add the maximum
315
 
        space needed for identifying the record (encoded heap_no). */
316
 
        length -= REC_N_NEW_EXTRA_BYTES - 2;
317
 
 
318
 
        if (UNIV_UNLIKELY(create)) {
319
 
                /* When a record is created, a pointer may be added to
320
 
                the dense directory.
321
 
                Likewise, space for the columns that will not be
322
 
                compressed will be allocated from the page trailer.
323
 
                Also the BLOB pointers will be allocated from there, but
324
 
                we may as well count them in the length of the record. */
325
 
 
326
 
                trailer_len += uncompressed_size;
327
 
        }
328
 
 
329
 
        return(UNIV_LIKELY(length
330
 
                           + trailer_len
331
 
                           + page_zip->m_end
332
 
                           < page_zip_get_size(page_zip)));
333
 
}
334
 
 
335
 
/**********************************************************************//**
336
 
Initialize a compressed page descriptor. */
337
 
UNIV_INLINE
338
 
void
339
 
page_zip_des_init(
340
 
/*==============*/
341
 
        page_zip_des_t* page_zip)       /*!< in/out: compressed page
342
 
                                        descriptor */
343
 
{
344
 
        memset(page_zip, 0, sizeof *page_zip);
345
 
}
346
 
 
347
 
/**********************************************************************//**
348
 
Write a log record of writing to the uncompressed header portion of a page. */
349
 
UNIV_INTERN
350
 
void
351
 
page_zip_write_header_log(
352
 
/*======================*/
353
 
        const byte*     data,/*!< in: data on the uncompressed page */
354
 
        ulint           length, /*!< in: length of the data */
355
 
        mtr_t*          mtr);   /*!< in: mini-transaction */
356
 
 
357
 
/**********************************************************************//**
358
 
Write data to the uncompressed header portion of a page.  The data must
359
 
already have been written to the uncompressed page.
360
 
However, the data portion of the uncompressed page may differ from
361
 
the compressed page when a record is being inserted in
362
 
page_cur_insert_rec_zip(). */
363
 
UNIV_INLINE
364
 
void
365
 
page_zip_write_header(
366
 
/*==================*/
367
 
        page_zip_des_t* page_zip,/*!< in/out: compressed page */
368
 
        const byte*     str,    /*!< in: address on the uncompressed page */
369
 
        ulint           length, /*!< in: length of the data */
370
 
        mtr_t*          mtr)    /*!< in: mini-transaction, or NULL */
371
 
{
372
 
        ulint   pos;
373
 
 
374
 
        ut_ad(PAGE_ZIP_MATCH(str, page_zip));
375
 
        ut_ad(page_zip_simple_validate(page_zip));
376
 
        UNIV_MEM_ASSERT_RW(page_zip->data, page_zip_get_size(page_zip));
377
 
 
378
 
        pos = page_offset(str);
379
 
 
380
 
        ut_ad(pos < PAGE_DATA);
381
 
 
382
 
        memcpy(page_zip->data + pos, str, length);
383
 
 
384
 
        /* The following would fail in page_cur_insert_rec_zip(). */
385
 
        /* ut_ad(page_zip_validate(page_zip, str - pos)); */
386
 
 
387
 
        if (UNIV_LIKELY_NULL(mtr)) {
388
 
#ifndef UNIV_HOTBACKUP
389
 
                page_zip_write_header_log(str, length, mtr);
390
 
#endif /* !UNIV_HOTBACKUP */
391
 
        }
392
 
}
393
 
 
394
 
#ifdef UNIV_MATERIALIZE
395
 
# undef UNIV_INLINE
396
 
# define UNIV_INLINE    UNIV_INLINE_ORIGINAL
397
 
#endif