← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to plugin/innobase/btr/btr0sea.c

  • Committer: Brian Aker
  • Date: 2010-04-05 23:46:43 UTC
  • Revision ID: brian@gaz-20100405234643-0he3xnj902rc70r8
Fixing tests to work with PBXT.

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/innobase/btr/btr0sea.c
23
23
 
24
24
*****************************************************************************/
25
25
 
26
 
/************************************************************************
 
26
/********************************************************************//**
 
27
@file btr/btr0sea.c
27
28
The index tree adaptive search
28
29
 
29
30
Created 2/17/1996 Heikki Tuuri
42
43
#include "btr0btr.h"
43
44
#include "ha0ha.h"
44
45
 
45
 
/* Flag: has the search system been enabled?
 
46
/** Flag: has the search system been enabled?
46
47
Protected by btr_search_latch and btr_search_enabled_mutex. */
47
48
UNIV_INTERN bool                btr_search_enabled      = TRUE;
48
49
 
 
50
/** Mutex protecting btr_search_enabled */
49
51
static mutex_t                  btr_search_enabled_mutex;
50
52
 
51
 
/* A dummy variable to fool the compiler */
 
53
/** A dummy variable to fool the compiler */
52
54
UNIV_INTERN ulint               btr_search_this_is_zero = 0;
53
55
 
54
56
#ifdef UNIV_SEARCH_PERF_STAT
 
57
/** Number of successful adaptive hash index lookups */
55
58
UNIV_INTERN ulint               btr_search_n_succ       = 0;
 
59
/** Number of failed adaptive hash index lookups */
56
60
UNIV_INTERN ulint               btr_search_n_hash_fail  = 0;
57
61
#endif /* UNIV_SEARCH_PERF_STAT */
58
62
 
59
 
/* padding to prevent other memory update
 
63
/** padding to prevent other memory update
60
64
hotspots from residing on the same memory
61
65
cache line as btr_search_latch */
62
66
UNIV_INTERN byte                btr_sea_pad1[64];
63
67
 
64
 
/* The latch protecting the adaptive search system: this latch protects the
 
68
/** The latch protecting the adaptive search system: this latch protects the
65
69
(1) positions of records on those pages where a hash index has been built.
66
70
NOTE: It does not protect values of non-ordering fields within a record from
67
71
being updated in-place! We can use fact (1) to perform unique searches to
71
75
same DRAM page as other hotspot semaphores */
72
76
UNIV_INTERN rw_lock_t*          btr_search_latch_temp;
73
77
 
74
 
/* padding to prevent other memory update hotspots from residing on
 
78
/** padding to prevent other memory update hotspots from residing on
75
79
the same memory cache line */
76
80
UNIV_INTERN byte                btr_sea_pad2[64];
77
81
 
 
82
/** The adaptive hash index */
78
83
UNIV_INTERN btr_search_sys_t*   btr_search_sys;
79
84
 
80
 
/* If the number of records on the page divided by this parameter
 
85
/** If the number of records on the page divided by this parameter
81
86
would have been successfully accessed using a hash index, the index
82
87
is then built on the page, assuming the global limit has been reached */
83
 
 
84
88
#define BTR_SEARCH_PAGE_BUILD_LIMIT     16
85
89
 
86
 
/* The global limit for consecutive potentially successful hash searches,
 
90
/** The global limit for consecutive potentially successful hash searches,
87
91
before hash index building is started */
88
 
 
89
92
#define BTR_SEARCH_BUILD_LIMIT          100
90
93
 
91
 
/************************************************************************
 
94
/********************************************************************//**
92
95
Builds a hash index on a page with the given parameters. If the page already
93
96
has a hash index with different parameters, the old hash index is removed.
94
97
If index is non-NULL, this function checks if n_fields and n_bytes are
97
100
void
98
101
btr_search_build_page_hash_index(
99
102
/*=============================*/
100
 
        dict_index_t*   index,  /* in: index for which to build, or NULL if
 
103
        dict_index_t*   index,  /*!< in: index for which to build, or NULL if
101
104
                                not known */
102
 
        buf_block_t*    block,  /* in: index page, s- or x-latched */
103
 
        ulint           n_fields,/* in: hash this many full fields */
104
 
        ulint           n_bytes,/* in: hash this many bytes from the next
 
105
        buf_block_t*    block,  /*!< in: index page, s- or x-latched */
 
106
        ulint           n_fields,/*!< in: hash this many full fields */
 
107
        ulint           n_bytes,/*!< in: hash this many bytes from the next
105
108
                                field */
106
 
        ibool           left_side);/* in: hash for searches from left side? */
 
109
        ibool           left_side);/*!< in: hash for searches from left side? */
107
110
 
108
 
/*********************************************************************
 
111
/*****************************************************************//**
109
112
This function should be called before reserving any btr search mutex, if
110
113
the intended operation might add nodes to the search system hash table.
111
114
Because of the latching order, once we have reserved the btr search system
151
154
        }
152
155
}
153
156
 
154
 
/*********************************************************************
 
157
/*****************************************************************//**
155
158
Creates and initializes the adaptive search system at a database start. */
156
159
UNIV_INTERN
157
160
void
158
161
btr_search_sys_create(
159
162
/*==================*/
160
 
        ulint   hash_size)      /* in: hash index hash table size */
 
163
        ulint   hash_size)      /*!< in: hash index hash table size */
161
164
{
162
165
        /* We allocate the search latch from dynamic memory:
163
166
        see above at the global variable definition */
172
175
        btr_search_sys->hash_index = ha_create(hash_size, 0, 0);
173
176
}
174
177
 
175
 
/************************************************************************
 
178
/********************************************************************//**
176
179
Disable the adaptive hash search system and empty the index. */
177
180
UNIV_INTERN
178
181
void
195
198
        mutex_exit(&btr_search_enabled_mutex);
196
199
}
197
200
 
198
 
/************************************************************************
 
201
/********************************************************************//**
199
202
Enable the adaptive hash search system. */
200
203
UNIV_INTERN
201
204
void
211
214
        mutex_exit(&btr_search_enabled_mutex);
212
215
}
213
216
 
214
 
/*********************************************************************
215
 
Creates and initializes a search info struct. */
 
217
/*****************************************************************//**
 
218
Creates and initializes a search info struct.
 
219
@return own: search info struct */
216
220
UNIV_INTERN
217
221
btr_search_t*
218
222
btr_search_info_create(
219
223
/*===================*/
220
 
                                /* out, own: search info struct */
221
 
        mem_heap_t*     heap)   /* in: heap where created */
 
224
        mem_heap_t*     heap)   /*!< in: heap where created */
222
225
{
223
226
        btr_search_t*   info;
224
227
 
252
255
        return(info);
253
256
}
254
257
 
255
 
/*********************************************************************
 
258
/*****************************************************************//**
256
259
Returns the value of ref_count. The value is protected by
257
 
btr_search_latch. */
 
260
btr_search_latch.
 
261
@return ref_count value. */
258
262
UNIV_INTERN
259
263
ulint
260
264
btr_search_info_get_ref_count(
261
265
/*==========================*/
262
 
                                /* out: ref_count value. */
263
 
        btr_search_t*   info)   /* in: search info. */
 
266
        btr_search_t*   info)   /*!< in: search info. */
264
267
{
265
268
        ulint ret;
266
269
 
278
281
        return(ret);
279
282
}
280
283
 
281
 
/*************************************************************************
 
284
/*********************************************************************//**
282
285
Updates the search info of an index about hash successes. NOTE that info
283
286
is NOT protected by any semaphore, to save CPU time! Do not assume its fields
284
287
are consistent. */
286
289
void
287
290
btr_search_info_update_hash(
288
291
/*========================*/
289
 
        btr_search_t*   info,   /* in/out: search info */
290
 
        btr_cur_t*      cursor) /* in: cursor which was just positioned */
 
292
        btr_search_t*   info,   /*!< in/out: search info */
 
293
        btr_cur_t*      cursor) /*!< in: cursor which was just positioned */
291
294
{
292
295
        dict_index_t*   index;
293
296
        ulint           n_unique;
398
401
        }
399
402
}
400
403
 
401
 
/*************************************************************************
 
404
/*********************************************************************//**
402
405
Updates the block search info on hash successes. NOTE that info and
403
406
block->n_hash_helps, n_fields, n_bytes, side are NOT protected by any
404
 
semaphore, to save CPU time! Do not assume the fields are consistent. */
 
407
semaphore, to save CPU time! Do not assume the fields are consistent.
 
408
@return TRUE if building a (new) hash index on the block is recommended */
405
409
static
406
410
ibool
407
411
btr_search_update_block_hash_info(
408
412
/*==============================*/
409
 
                                /* out: TRUE if building a (new) hash index on
410
 
                                the block is recommended */
411
 
        btr_search_t*   info,   /* in: search info */
412
 
        buf_block_t*    block,  /* in: buffer block */
 
413
        btr_search_t*   info,   /*!< in: search info */
 
414
        buf_block_t*    block,  /*!< in: buffer block */
413
415
        btr_cur_t*      cursor __attribute__((unused)))
414
 
                                /* in: cursor */
 
416
                                /*!< in: cursor */
415
417
{
416
418
#ifdef UNIV_SYNC_DEBUG
417
419
        ut_ad(!rw_lock_own(&btr_search_latch, RW_LOCK_SHARED));
477
479
        return(FALSE);
478
480
}
479
481
 
480
 
/*************************************************************************
 
482
/*********************************************************************//**
481
483
Updates a hash node reference when it has been unsuccessfully used in a
482
484
search which could have succeeded with the used hash parameters. This can
483
485
happen because when building a hash index for a page, we do not check
489
491
void
490
492
btr_search_update_hash_ref(
491
493
/*=======================*/
492
 
        btr_search_t*   info,   /* in: search info */
493
 
        buf_block_t*    block,  /* in: buffer block where cursor positioned */
494
 
        btr_cur_t*      cursor) /* in: cursor */
 
494
        btr_search_t*   info,   /*!< in: search info */
 
495
        buf_block_t*    block,  /*!< in: buffer block where cursor positioned */
 
496
        btr_cur_t*      cursor) /*!< in: cursor */
495
497
{
496
498
        ulint   fold;
497
499
        rec_t*  rec;
547
549
        }
548
550
}
549
551
 
550
 
/*************************************************************************
 
552
/*********************************************************************//**
551
553
Updates the search info. */
552
554
UNIV_INTERN
553
555
void
554
556
btr_search_info_update_slow(
555
557
/*========================*/
556
 
        btr_search_t*   info,   /* in/out: search info */
557
 
        btr_cur_t*      cursor) /* in: cursor which was just positioned */
 
558
        btr_search_t*   info,   /*!< in/out: search info */
 
559
        btr_cur_t*      cursor) /*!< in: cursor which was just positioned */
558
560
{
559
561
        buf_block_t*    block;
560
562
        ibool           build_index;
624
626
        }
625
627
}
626
628
 
627
 
/**********************************************************************
 
629
/******************************************************************//**
628
630
Checks if a guessed position for a tree cursor is right. Note that if
629
631
mode is PAGE_CUR_LE, which is used in inserts, and the function returns
630
 
TRUE, then cursor->up_match and cursor->low_match both have sensible values. */
 
632
TRUE, then cursor->up_match and cursor->low_match both have sensible values.
 
633
@return TRUE if success */
631
634
static
632
635
ibool
633
636
btr_search_check_guess(
634
637
/*===================*/
635
 
                                /* out: TRUE if success */
636
 
        btr_cur_t*      cursor, /* in: guessed cursor position */
 
638
        btr_cur_t*      cursor, /*!< in: guessed cursor position */
637
639
        ibool           can_only_compare_to_cursor_rec,
638
 
                                /* in: if we do not have a latch on the page
 
640
                                /*!< in: if we do not have a latch on the page
639
641
                                of cursor, but only a latch on
640
642
                                btr_search_latch, then ONLY the columns
641
643
                                of the record UNDER the cursor are
642
644
                                protected, not the next or previous record
643
645
                                in the chain: we cannot look at the next or
644
646
                                previous record to check our guess! */
645
 
        const dtuple_t* tuple,  /* in: data tuple */
646
 
        ulint           mode,   /* in: PAGE_CUR_L, PAGE_CUR_LE, PAGE_CUR_G,
 
647
        const dtuple_t* tuple,  /*!< in: data tuple */
 
648
        ulint           mode,   /*!< in: PAGE_CUR_L, PAGE_CUR_LE, PAGE_CUR_G,
647
649
                                or PAGE_CUR_GE */
648
 
        mtr_t*          mtr)    /* in: mtr */
 
650
        mtr_t*          mtr)    /*!< in: mtr */
649
651
{
650
652
        rec_t*          rec;
651
653
        ulint           n_unique;
770
772
        return(success);
771
773
}
772
774
 
773
 
/**********************************************************************
 
775
/******************************************************************//**
774
776
Tries to guess the right search position based on the hash search info
775
777
of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts,
776
778
and the function returns TRUE, then cursor->up_match and cursor->low_match
777
 
both have sensible values. */
 
779
both have sensible values.
 
780
@return TRUE if succeeded */
778
781
UNIV_INTERN
779
782
ibool
780
783
btr_search_guess_on_hash(
781
784
/*=====================*/
782
 
                                        /* out: TRUE if succeeded */
783
 
        dict_index_t*   index,          /* in: index */
784
 
        btr_search_t*   info,           /* in: index search info */
785
 
        const dtuple_t* tuple,          /* in: logical record */
786
 
        ulint           mode,           /* in: PAGE_CUR_L, ... */
787
 
        ulint           latch_mode,     /* in: BTR_SEARCH_LEAF, ...;
 
785
        dict_index_t*   index,          /*!< in: index */
 
786
        btr_search_t*   info,           /*!< in: index search info */
 
787
        const dtuple_t* tuple,          /*!< in: logical record */
 
788
        ulint           mode,           /*!< in: PAGE_CUR_L, ... */
 
789
        ulint           latch_mode,     /*!< in: BTR_SEARCH_LEAF, ...;
788
790
                                        NOTE that only if has_search_latch
789
791
                                        is 0, we will have a latch set on
790
792
                                        the cursor page, otherwise we assume
791
793
                                        the caller uses his search latch
792
794
                                        to protect the record! */
793
 
        btr_cur_t*      cursor,         /* out: tree cursor */
794
 
        ulint           has_search_latch,/* in: latch mode the caller
 
795
        btr_cur_t*      cursor,         /*!< out: tree cursor */
 
796
        ulint           has_search_latch,/*!< in: latch mode the caller
795
797
                                        currently has on btr_search_latch:
796
798
                                        RW_S_LATCH, RW_X_LATCH, or 0 */
797
 
        mtr_t*          mtr)            /* in: mtr */
 
799
        mtr_t*          mtr)            /*!< in: mtr */
798
800
{
799
801
        buf_block_t*    block;
800
802
        rec_t*          rec;
979
981
        return(FALSE);
980
982
}
981
983
 
982
 
/************************************************************************
 
984
/********************************************************************//**
983
985
Drops a page hash index. */
984
986
UNIV_INTERN
985
987
void
986
988
btr_search_drop_page_hash_index(
987
989
/*============================*/
988
 
        buf_block_t*    block)  /* in: block containing index page,
 
990
        buf_block_t*    block)  /*!< in: block containing index page,
989
991
                                s- or x-latched, or an index page
990
992
                                for which we know that
991
993
                                block->buf_fix_count == 0 */
1146
1148
        mem_free(folds);
1147
1149
}
1148
1150
 
1149
 
/************************************************************************
 
1151
/********************************************************************//**
1150
1152
Drops a page hash index when a page is freed from a fseg to the file system.
1151
1153
Drops possible hash index if the page happens to be in the buffer pool. */
1152
1154
UNIV_INTERN
1153
1155
void
1154
1156
btr_search_drop_page_hash_when_freed(
1155
1157
/*=================================*/
1156
 
        ulint   space,          /* in: space id */
1157
 
        ulint   zip_size,       /* in: compressed page size in bytes
 
1158
        ulint   space,          /*!< in: space id */
 
1159
        ulint   zip_size,       /*!< in: compressed page size in bytes
1158
1160
                                or 0 for uncompressed pages */
1159
 
        ulint   page_no)        /* in: page number */
 
1161
        ulint   page_no)        /*!< in: page number */
1160
1162
{
1161
1163
        buf_block_t*    block;
1162
1164
        mtr_t           mtr;
1192
1194
        mtr_commit(&mtr);
1193
1195
}
1194
1196
 
1195
 
/************************************************************************
 
1197
/********************************************************************//**
1196
1198
Builds a hash index on a page with the given parameters. If the page already
1197
1199
has a hash index with different parameters, the old hash index is removed.
1198
1200
If index is non-NULL, this function checks if n_fields and n_bytes are
1201
1203
void
1202
1204
btr_search_build_page_hash_index(
1203
1205
/*=============================*/
1204
 
        dict_index_t*   index,  /* in: index for which to build */
1205
 
        buf_block_t*    block,  /* in: index page, s- or x-latched */
1206
 
        ulint           n_fields,/* in: hash this many full fields */
1207
 
        ulint           n_bytes,/* in: hash this many bytes from the next
 
1206
        dict_index_t*   index,  /*!< in: index for which to build */
 
1207
        buf_block_t*    block,  /*!< in: index page, s- or x-latched */
 
1208
        ulint           n_fields,/*!< in: hash this many full fields */
 
1209
        ulint           n_bytes,/*!< in: hash this many bytes from the next
1208
1210
                                field */
1209
 
        ibool           left_side)/* in: hash for searches from left side? */
 
1211
        ibool           left_side)/*!< in: hash for searches from left side? */
1210
1212
{
1211
1213
        hash_table_t*   table;
1212
1214
        page_t*         page;
1387
1389
        }
1388
1390
}
1389
1391
 
1390
 
/************************************************************************
 
1392
/********************************************************************//**
1391
1393
Moves or deletes hash entries for moved records. If new_page is already hashed,
1392
1394
then the hash index for page, if any, is dropped. If new_page is not hashed,
1393
1395
and page is hashed, then a new hash index is built to new_page with the same
1396
1398
void
1397
1399
btr_search_move_or_delete_hash_entries(
1398
1400
/*===================================*/
1399
 
        buf_block_t*    new_block,      /* in: records are copied
 
1401
        buf_block_t*    new_block,      /*!< in: records are copied
1400
1402
                                        to this page */
1401
 
        buf_block_t*    block,          /* in: index page from which
 
1403
        buf_block_t*    block,          /*!< in: index page from which
1402
1404
                                        records were copied, and the
1403
1405
                                        copied records will be deleted
1404
1406
                                        from this page */
1405
 
        dict_index_t*   index)          /* in: record descriptor */
 
1407
        dict_index_t*   index)          /*!< in: record descriptor */
1406
1408
{
1407
1409
        ulint   n_fields;
1408
1410
        ulint   n_bytes;
1453
1455
        rw_lock_s_unlock(&btr_search_latch);
1454
1456
}
1455
1457
 
1456
 
/************************************************************************
 
1458
/********************************************************************//**
1457
1459
Updates the page hash index when a single record is deleted from a page. */
1458
1460
UNIV_INTERN
1459
1461
void
1460
1462
btr_search_update_hash_on_delete(
1461
1463
/*=============================*/
1462
 
        btr_cur_t*      cursor) /* in: cursor which was positioned on the
 
1464
        btr_cur_t*      cursor) /*!< in: cursor which was positioned on the
1463
1465
                                record to delete using btr_cur_search_...,
1464
1466
                                the record is not yet deleted */
1465
1467
{
1506
1508
        rw_lock_x_unlock(&btr_search_latch);
1507
1509
}
1508
1510
 
1509
 
/************************************************************************
 
1511
/********************************************************************//**
1510
1512
Updates the page hash index when a single record is inserted on a page. */
1511
1513
UNIV_INTERN
1512
1514
void
1513
1515
btr_search_update_hash_node_on_insert(
1514
1516
/*==================================*/
1515
 
        btr_cur_t*      cursor) /* in: cursor which was positioned to the
 
1517
        btr_cur_t*      cursor) /*!< in: cursor which was positioned to the
1516
1518
                                place to insert using btr_cur_search_...,
1517
1519
                                and the new record has been inserted next
1518
1520
                                to the cursor */
1557
1559
        }
1558
1560
}
1559
1561
 
1560
 
/************************************************************************
 
1562
/********************************************************************//**
1561
1563
Updates the page hash index when a single record is inserted on a page. */
1562
1564
UNIV_INTERN
1563
1565
void
1564
1566
btr_search_update_hash_on_insert(
1565
1567
/*=============================*/
1566
 
        btr_cur_t*      cursor) /* in: cursor which was positioned to the
 
1568
        btr_cur_t*      cursor) /*!< in: cursor which was positioned to the
1567
1569
                                place to insert using btr_cur_search_...,
1568
1570
                                and the new record has been inserted next
1569
1571
                                to the cursor */
1707
1709
        }
1708
1710
}
1709
1711
 
1710
 
/************************************************************************
1711
 
Validates the search system. */
 
1712
/********************************************************************//**
 
1713
Validates the search system.
 
1714
@return TRUE if ok */
1712
1715
UNIV_INTERN
1713
1716
ibool
1714
1717
btr_search_validate(void)
1715
1718
/*=====================*/
1716
 
                                /* out: TRUE if ok */
1717
1719
{
1718
1720
        ha_node_t*      node;
1719
1721
        ulint           n_page_dumps    = 0;