diff options
Diffstat (limited to 'innobase/include/btr0sea.h')
| -rw-r--r-- | innobase/include/btr0sea.h | 269 |
1 files changed, 269 insertions, 0 deletions
diff --git a/innobase/include/btr0sea.h b/innobase/include/btr0sea.h new file mode 100644 index 00000000000..c319e16d740 --- /dev/null +++ b/innobase/include/btr0sea.h @@ -0,0 +1,269 @@ +/************************************************************************ +The index tree adaptive search + +(c) 1996 Innobase Oy + +Created 2/17/1996 Heikki Tuuri +*************************************************************************/ + +#ifndef btr0sea_h +#define btr0sea_h + +#include "univ.i" + +#include "rem0rec.h" +#include "dict0dict.h" +#include "btr0types.h" +#include "mtr0mtr.h" +#include "ha0ha.h" + +/********************************************************************* +Creates and initializes the adaptive search system at a database start. */ + +void +btr_search_sys_create( +/*==================*/ + ulint hash_size); /* in: hash index hash table size */ +/************************************************************************ +Returns search info for an index. */ +UNIV_INLINE +btr_search_t* +btr_search_get_info( +/*================*/ + /* out: search info; search mutex reserved */ + dict_index_t* index); /* in: index */ +/********************************************************************* +Creates and initializes a search info struct. */ + +btr_search_t* +btr_search_info_create( +/*===================*/ + /* out, own: search info struct */ + mem_heap_t* heap); /* in: heap where created */ +/************************************************************************* +Updates the search info. */ +UNIV_INLINE +void +btr_search_info_update( +/*===================*/ + dict_index_t* index, /* in: index of the cursor */ + btr_cur_t* cursor);/* in: cursor which was just positioned */ +/********************************************************************** +Tries to guess the right search position based on the search pattern info +of the index. */ + +ibool +btr_search_guess_on_pattern( +/*========================*/ + /* out: TRUE if succeeded */ + dict_index_t* index, /* in: index */ + btr_search_t* info, /* in: index search info */ + dtuple_t* tuple, /* in: logical record */ + ulint mode, /* in: PAGE_CUR_L, ... */ + ulint latch_mode, /* in: BTR_SEARCH_LEAF, ... */ + btr_cur_t* cursor, /* out: tree cursor */ + mtr_t* mtr); /* in: mtr */ +/********************************************************************** +Tries to guess the right search position based on the hash search info +of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts, +and the function returns TRUE, then cursor->up_match and cursor->low_match +both have sensible values. */ + +ibool +btr_search_guess_on_hash( +/*=====================*/ + /* out: TRUE if succeeded */ + dict_index_t* index, /* in: index */ + btr_search_t* info, /* in: index search info */ + dtuple_t* tuple, /* in: logical record */ + ulint mode, /* in: PAGE_CUR_L, ... */ + ulint latch_mode, /* in: BTR_SEARCH_LEAF, ... */ + btr_cur_t* cursor, /* out: tree cursor */ + ulint has_search_latch,/* in: latch mode the caller + currently has on btr_search_latch: + RW_S_LATCH, RW_X_LATCH, or 0 */ + mtr_t* mtr); /* in: mtr */ +/************************************************************************ +Moves or deletes hash entries for moved records. If new_page is already hashed, +then the hash index for page, if any, is dropped. If new_page is not hashed, +and page is hashed, then a new hash index is built to new_page with the same +parameters as page (this often happens when a page is split). */ + +void +btr_search_move_or_delete_hash_entries( +/*===================================*/ + page_t* new_page, /* in: records are copied to this page */ + page_t* page); /* in: index page */ +/************************************************************************ +Drops a page hash index. */ + +void +btr_search_drop_page_hash_index( +/*============================*/ + page_t* page); /* in: index page, s- or x-latched */ +/************************************************************************ +Drops a page hash index when a page is freed from a fseg to the file system. +Drops possible hash index if the page happens to be in the buffer pool. */ + +void +btr_search_drop_page_hash_when_freed( +/*=================================*/ + ulint space, /* in: space id */ + ulint page_no); /* in: page number */ +/************************************************************************ +Updates the page hash index when a single record is inserted on a page. */ + +void +btr_search_update_hash_node_on_insert( +/*==================================*/ + btr_cur_t* cursor);/* in: cursor which was positioned to the + place to insert using btr_cur_search_..., + and the new record has been inserted next + to the cursor */ +/************************************************************************ +Updates the page hash index when a single record is inserted on a page. */ + +void +btr_search_update_hash_on_insert( +/*=============================*/ + btr_cur_t* cursor);/* in: cursor which was positioned to the + place to insert using btr_cur_search_..., + and the new record has been inserted next + to the cursor */ +/************************************************************************ +Updates the page hash index when a single record is deleted from a page. */ + +void +btr_search_update_hash_on_delete( +/*=============================*/ + btr_cur_t* cursor);/* in: cursor which was positioned on the + record to delete using btr_cur_search_..., + the record is not yet deleted */ +/************************************************************************ +Prints info of the search system. */ + +void +btr_search_print_info(void); +/*=======================*/ +/************************************************************************ +Prints info of searches on an index. */ + +void +btr_search_index_print_info( +/*========================*/ + dict_index_t* index); /* in: index */ +/************************************************************************ +Prints info of searches on a table. */ + +void +btr_search_table_print_info( +/*========================*/ + char* name); /* in: table name */ +/************************************************************************ +Validates the search system. */ + +ibool +btr_search_validate(void); +/*=====================*/ + + +/* Search info directions */ +#define BTR_SEA_NO_DIRECTION 1 +#define BTR_SEA_LEFT 2 +#define BTR_SEA_RIGHT 3 +#define BTR_SEA_SAME_REC 4 + +/* The search info struct in an index */ + +struct btr_search_struct{ + /* The following 4 fields are currently not used: */ + rec_t* last_search; /* pointer to the lower limit record of the + previous search; NULL if not known */ + ulint n_direction; /* number of consecutive searches in the + same direction */ + ulint direction; /* BTR_SEA_NO_DIRECTION, BTR_SEA_LEFT, + BTR_SEA_RIGHT, BTR_SEA_SAME_REC, + or BTR_SEA_SAME_PAGE */ + dulint modify_clock; /* value of modify clock at the time + last_search was stored */ + /*----------------------*/ + /* The following 4 fields are not protected by any latch: */ + page_t* root_guess; /* the root page frame when it was last time + fetched, or NULL */ + ulint hash_analysis; /* when this exceeds a certain value, the + hash analysis starts; this is reset if no + success noticed */ + ibool last_hash_succ; /* TRUE if the last search would have + succeeded, or did succeed, using the hash + index; NOTE that the value here is not exact: + it is not calculated for every search, and the + calculation itself is not always accurate! */ + ulint n_hash_potential;/* number of consecutive searches which would + have succeeded, or did succeed, using the hash + index */ + /*----------------------*/ + ulint n_fields; /* recommended prefix length for hash search: + number of full fields */ + ulint n_bytes; /* recommended prefix: number of bytes in + an incomplete field */ + ulint side; /* BTR_SEARCH_LEFT_SIDE or + BTR_SEARCH_RIGHT_SIDE, depending on whether + the leftmost record of several records with + the same prefix should be indexed in the + hash index */ + /*----------------------*/ + ulint n_hash_succ; /* number of successful hash searches thus + far */ + ulint n_hash_fail; /* number of failed hash searches */ + ulint n_patt_succ; /* number of successful pattern searches thus + far */ + ulint n_searches; /* number of searches */ +}; + +/* The hash index system */ + +typedef struct btr_search_sys_struct btr_search_sys_t; + +struct btr_search_sys_struct{ + hash_table_t* hash_index; +}; + +extern btr_search_sys_t* btr_search_sys; + +/* The latch protecting the adaptive search system: this latch protects the +(1) positions of records on those pages where a hash index has been built. +NOTE: It does not protect values of non-ordering fields within a record from +being updated in-place! We can use fact (1) to perform unique searches to +indexes. */ + +extern rw_lock_t* btr_search_latch_temp; + +#define btr_search_latch (*btr_search_latch_temp) + +extern ulint btr_search_n_succ; +extern ulint btr_search_n_hash_fail; + +/* After change in n_fields or n_bytes in info, this many rounds are waited +before starting the hash analysis again: this is to save CPU time when there +is no hope in building a hash index. */ + +#define BTR_SEARCH_HASH_ANALYSIS 17 + +#define BTR_SEARCH_LEFT_SIDE 1 +#define BTR_SEARCH_RIGHT_SIDE 2 + +/* Limit of consecutive searches for trying a search shortcut on the search +pattern */ + +#define BTR_SEARCH_ON_PATTERN_LIMIT 3 + +/* Limit of consecutive searches for trying a search shortcut using the hash +index */ + +#define BTR_SEARCH_ON_HASH_LIMIT 3 + +#ifndef UNIV_NONINL +#include "btr0sea.ic" +#endif + +#endif |