File btree_load.h¶
File List > cubrid > src > storage > btree_load.h
Go to the documentation of this file
/*
* Copyright 2008 Search Solution Corporation
* Copyright 2016 CUBRID Corporation
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
*/
/*
* btree_load.h: Contains private information of B+tree Module
*/
#ifndef _BTREE_LOAD_H_
#define _BTREE_LOAD_H_
#ident "$Id$"
#include <assert.h>
#include "btree.h"
#include "dbtype.h"
#include "object_representation_constants.h"
#include "error_manager.h"
#include "storage_common.h"
#include "oid.h"
#include "system_parameter.h"
#include "object_domain.h"
#include "slotted_page.h"
/* Forward declarations for filter predicate and XASL unpack types */
typedef struct pred_expr_with_context PRED_EXPR_WITH_CONTEXT;
typedef struct xasl_unpack_info XASL_UNPACK_INFO;
/* *INDENT-OFF* */
namespace parallel_query
{
class ftab_set;
}
/* *INDENT-ON* */
/*
* Constants related to b+tree structure
*/
#define PEEK_KEY_VALUE PEEK
#define COPY_KEY_VALUE COPY
/* The revision level of the the Btree should be incremented whenever there
* is a disk representation change for the Btree structure.
*/
#define BTREE_CURRENT_REV_LEVEL 0
/* each index page is supposed to be left empty as indicated by the
* UNFILL FACTOR during index loading phase.
*/
#define LOAD_FIXED_EMPTY_FOR_LEAF \
(DB_PAGESIZE * prm_get_float_value (PRM_ID_BT_UNFILL_FACTOR) \
+ DISK_VPID_SIZE)
#define LOAD_FIXED_EMPTY_FOR_NONLEAF \
(DB_PAGESIZE * MAX (prm_get_float_value (PRM_ID_BT_UNFILL_FACTOR), 0.1) \
+ DISK_VPID_SIZE)
/* each page is supposed to have around 30% blank area during merge
considerations of a delete operation */
/* Maximum Alignment */
#define BTREE_MAX_ALIGN INT_ALIGNMENT
/* Maximum Leaf Node Entry Size */
#define LEAF_ENTRY_MAX_SIZE(n) \
(LEAF_RECORD_SIZE \
+ (2 * OR_OID_SIZE) /* OID + class OID */ \
+ (2 * OR_MVCCID_SIZE) /* Insert/delete MVCCID */ \
+ BTREE_MAX_ALIGN /* Alignment */ \
+ n /* Key disk length. */)
/* Maximum size of new fence key. */
#define LEAF_FENCE_MAX_SIZE(n) \
(LEAF_RECORD_SIZE \
+ OR_OID_SIZE /* OID marker for fence key */ \
+ BTREE_MAX_ALIGN /* Alignment */ \
+ n /* Key disk length. */)
/* Maximum Non_Leaf Entry Size */
#define NON_LEAF_ENTRY_MAX_SIZE(n) \
(NON_LEAF_RECORD_SIZE + BTREE_MAX_ALIGN + n)
/* New b-tree entry maximum size. */
#define BTREE_NEW_ENTRY_MAX_SIZE(key_disk_size, node_type) \
((node_type) == BTREE_LEAF_NODE ? \
LEAF_ENTRY_MAX_SIZE (key_disk_size) : \
NON_LEAF_ENTRY_MAX_SIZE (key_disk_size))
/* compare two object identifiers */
#define OIDCMP(n1, n2) \
((n1).pageid == (n2).pageid \
&& (n1).slotid == (n2).slotid \
&& (n1).volid == (n2).volid)
/* Header (Oth) record of the page */
#define HEADER 0
#if !defined(NDEBUG)
#define BTREE_INVALID_INDEX_ID(btid) \
((btid)->vfid.fileid == NULL_FILEID || (btid)->vfid.volid == NULL_VOLID \
|| (btid)->root_pageid == NULL_PAGEID)
#endif
/* The size of an object in cases it has fixed size (includes all required
* info).
* In case of unique: OID, class OID, insert and delete MVCCID.
* In case of non-unique: OID, insert and delete MVCCID.
*
* Fixed size is used when:
* 1. object is saved in overflow page.
* 2. object is non-first in leaf record.
* 3. object is first in a leaf record that has overflow pages.
*/
#define BTREE_OBJECT_FIXED_SIZE(btree_info) \
(BTREE_IS_UNIQUE ((btree_info)->unique_pk) ? \
2 * OR_OID_SIZE + 2 * OR_MVCCID_SIZE : OR_OID_SIZE + 2 * OR_MVCCID_SIZE)
/* Maximum possible size for one b-tree object including all its information.
*/
#define BTREE_OBJECT_MAX_SIZE (2 * OR_OID_SIZE + 2 * OR_MVCCID_SIZE)
/*
* Overflow key related defines
*/
/* We never want to store keys larger than an eighth of the page size
* directly on the btree page since this will make the btree too deep.
* Large keys are automatically stored on overflow pages. With prefix
* keys this shouldn't be much of a problem anyway (when we get them
* turned back on).
*/
#define BTREE_MAX_KEYLEN_INPAGE ((int)(DB_PAGESIZE / 8))
/* in MVCC BTREE_MAX_OIDLEN_INPAGE include MVCC fields too */
#define BTREE_MAX_OIDLEN_INPAGE ((int)(DB_PAGESIZE / 8))
/* Maximum number of objects that surely fit given size including all info. */
#define BTREE_MAX_OIDCOUNT_IN_SIZE(btid, size) \
((int) (size) / BTREE_OBJECT_FIXED_SIZE (btid))
/* Maximum number of objects for a leaf record */
#define BTREE_MAX_OIDCOUNT_IN_LEAF_RECORD(btid) \
(BTREE_MAX_OIDCOUNT_IN_SIZE (btid, BTREE_MAX_OIDLEN_INPAGE))
#define BTREE_MAX_OVERFLOW_RECORD_SIZE \
(DB_PAGESIZE - DB_ALIGN (SPAGE_HEADER_SIZE, BTREE_MAX_ALIGN) \
- DB_ALIGN (sizeof (BTREE_OVERFLOW_HEADER), BTREE_MAX_ALIGN))
#define BTREE_MAX_OIDCOUNT_IN_OVERFLOW_RECORD(btid) \
(BTREE_MAX_OIDCOUNT_IN_SIZE (btid, BTREE_MAX_OVERFLOW_RECORD_SIZE))
extern int btree_node_number_of_keys (THREAD_ENTRY * thread_p, PAGE_PTR page_ptr);
extern int btree_get_next_overflow_vpid (THREAD_ENTRY * thread_p, PAGE_PTR page_ptr, VPID * vpid);
#define BTREE_GET_KEY_LEN_IN_PAGE(key_len) \
(((key_len) >= BTREE_MAX_KEYLEN_INPAGE) ? DISK_VPID_SIZE : (key_len))
/* for notification log messages */
#define BTREE_SET_CREATED_OVERFLOW_KEY_NOTIFICATION(THREAD,KEY,OID,C_OID,BTID,BTNM) \
btree_set_error(THREAD, KEY, OID, C_OID, BTID, BTNM, ER_NOTIFICATION_SEVERITY, \
ER_BTREE_CREATED_OVERFLOW_KEY, __FILE__, __LINE__)
#define BTREE_SET_CREATED_OVERFLOW_PAGE_NOTIFICATION(THREAD,KEY,OID,C_OID,BTID) \
btree_set_error(THREAD, KEY, OID, C_OID, BTID, NULL, ER_NOTIFICATION_SEVERITY, \
ER_BTREE_CREATED_OVERFLOW_PAGE, __FILE__, __LINE__)
#define BTREE_SET_DELETED_OVERFLOW_PAGE_NOTIFICATION(THREAD,KEY,OID,C_OID,BTID) \
btree_set_error(THREAD, KEY, OID, C_OID, BTID, NULL, ER_NOTIFICATION_SEVERITY, \
ER_BTREE_DELETED_OVERFLOW_PAGE, __FILE__, __LINE__)
/* set fixed size for MVCC record header */
inline void
BTREE_MVCC_SET_HEADER_FIXED_SIZE (MVCC_REC_HEADER * p_mvcc_rec_header)
{
assert (p_mvcc_rec_header != NULL);
if (!(p_mvcc_rec_header->mvcc_flag & OR_MVCC_FLAG_VALID_INSID))
{
p_mvcc_rec_header->mvcc_flag |= OR_MVCC_FLAG_VALID_INSID;
p_mvcc_rec_header->mvcc_ins_id = MVCCID_ALL_VISIBLE;
}
if (!(p_mvcc_rec_header->mvcc_flag & OR_MVCC_FLAG_VALID_DELID))
{
p_mvcc_rec_header->mvcc_flag |= OR_MVCC_FLAG_VALID_DELID;
p_mvcc_rec_header->mvcc_del_id = MVCCID_NULL;
}
}
/*
* Type definitions related to b+tree structure and operations
*/
/* Node header information */
typedef struct btree_node_header BTREE_NODE_HEADER;
struct btree_node_header
{
BTREE_NODE_SPLIT_INFO split_info; /* split point info. of the node */
VPID prev_vpid; /* Leaf Page Previous Node Pointer */
VPID next_vpid; /* Leaf Page Next Node Pointer */
short node_level; /* btree depth; Leaf(= 1), Non_leaf(> 1) */
short max_key_len; /* Maximum key length for the subtree */
int common_prefix;
};
/* Root header information */
typedef struct btree_root_header BTREE_ROOT_HEADER;
struct btree_root_header
{
BTREE_NODE_HEADER node;
INT64 num_oids; /* Number of OIDs stored in the Btree */
INT64 num_nulls; /* Number of NULLs (they aren't stored) */
INT64 num_keys; /* Number of unique keys in the Btree */
OID topclass_oid; /* topclass oid or NULL OID(non unique index) */
int unique_pk; /* unique or non-unique, is primary key */
/* support for SUPPORT_DEDUPLICATE_KEY_MODE */
struct
{
int rev_level:16; /* Btree revision level */
int deduplicate_key_idx:16;
#define SET_DECOMPRESS_IDX_HEADER(hdr, idx) ((hdr)->_32.deduplicate_key_idx = ((idx) + 1))
#define GET_DECOMPRESS_IDX_HEADER(hdr) ((hdr)->_32.deduplicate_key_idx - 1)
} _32;
VFID ovfid; /* Overflow file */
MVCCID creator_mvccid; /* MVCCID of creator transaction. */
/* Always leave this field last. */
char packed_key_domain[1]; /* The key type for the index */
};
/* overflow header information */
typedef struct btree_overflow_header BTREE_OVERFLOW_HEADER;
struct btree_overflow_header
{
VPID next_vpid;
};
typedef struct btree_node_info BTREE_NODE_INFO;
struct btree_node_info
{
short max_key_len; /* Maximum key length for the subtree */
int height; /* The height of the subtree */
INT32 tot_key_cnt; /* Total key count in the subtree */
int page_cnt; /* Total page count in the subtree */
int leafpg_cnt; /* Total leaf page count in the subtree */
int nleafpg_cnt; /* Total non_leaf page count */
int key_area_len; /* Current max_key area length malloced */
DB_VALUE max_key; /* Largest key in the subtreee */
}; /* contains statistical data for testing purposes */
/*
* B+tree load structures
*/
typedef struct btree_node BTREE_NODE;
struct btree_node
{
BTREE_NODE *next; /* Pointer to next node */
VPID pageid; /* Identifier of the page */
};
typedef struct filter_index_info FILTER_INDEX_INFO;
struct filter_index_info
{
char *pred_stream;
int pred_stream_size;
};
typedef struct sort_args SORT_ARGS;
struct sort_args
{ /* Collection of information required for "sr_index_sort" */
int unique_pk;
int not_null_flag;
HFID *hfids; /* Array of HFIDs for the class(es) */
OID *class_ids; /* Array of class OIDs */
OID cur_oid; /* Identifier of the current object */
RECDES in_recdes; /* Input record descriptor */
int n_attrs; /* Number of attribute ID's */
ATTR_ID *attr_ids; /* Specification of the attribute(s) to sort on */
int *attrs_prefix_length; /* prefix length */
TP_DOMAIN *key_type;
HEAP_SCANCACHE hfscan_cache; /* A heap scan cache */
HEAP_CACHE_ATTRINFO attr_info; /* Attribute information */
int n_nulls; /* Number of NULLs */
int n_oids; /* Number of OIDs */
int n_classes; /* cardinality of the hfids, the class_ids, and (with n_attrs) the attr_ids arrays */
int cur_class; /* index into the hfids, class_ids, and attr_ids arrays */
bool scancache_inited;
bool attrinfo_inited;
BTID_INT *btid;
OID *fk_refcls_oid;
BTID *fk_refcls_pk_btid;
const char *fk_name;
struct pred_expr_with_context *filter;
PR_EVAL_FNC filter_eval_func;
FILTER_INDEX_INFO *filter_index_info;
FUNCTION_INDEX_INFO *func_index_info;
MVCCID oldest_visible_mvccid;
/* for parallel processing */
/* *INDENT-OFF* */
std::vector<parallel_query::ftab_set> *ftab_sets;
FILE_PARTIAL_SECTOR curr_sec;
int curr_pgoffset;
/* *INDENT-ON* */
};
/* Recovery routines */
extern void btree_rv_nodehdr_dump (FILE * fp, int length, void *data);
extern void btree_rv_mvcc_save_increments (const BTID * btid, long long key_delta, long long oid_delta,
long long null_delta, RECDES * recdes);
STATIC_INLINE bool btree_clear_key_value (bool * clear_flag, DB_VALUE * key_value) __attribute__ ((ALWAYS_INLINE));
STATIC_INLINE void btree_init_temp_key_value (bool * clear_flag, DB_VALUE * key_value) __attribute__ ((ALWAYS_INLINE));
extern int btree_create_overflow_key_file (THREAD_ENTRY * thread_p, BTID_INT * btid);
extern int btree_init_overflow_header (THREAD_ENTRY * thread_p, PAGE_PTR page_ptr, BTREE_OVERFLOW_HEADER * ovf_header);
extern int btree_init_node_header (THREAD_ENTRY * thread_p, const VFID * vfid, PAGE_PTR page_ptr,
BTREE_NODE_HEADER * header, bool redo);
extern int btree_init_root_header (THREAD_ENTRY * thread_p, VFID * vfid, PAGE_PTR page_ptr,
BTREE_ROOT_HEADER * root_header, TP_DOMAIN * key_type);
extern BTREE_NODE_HEADER *btree_get_node_header (THREAD_ENTRY * thread_p, PAGE_PTR page_ptr);
extern BTREE_ROOT_HEADER *btree_get_root_header (THREAD_ENTRY * thread_p, PAGE_PTR page_ptr);
extern BTREE_OVERFLOW_HEADER *btree_get_overflow_header (THREAD_ENTRY * thread_p, PAGE_PTR page_ptr);
extern int btree_node_header_undo_log (THREAD_ENTRY * thread_p, VFID * vfid, PAGE_PTR page_ptr);
extern int btree_node_header_redo_log (THREAD_ENTRY * thread_p, VFID * vfid, PAGE_PTR page_ptr);
extern int btree_change_root_header_delta (THREAD_ENTRY * thread_p, VFID * vfid, PAGE_PTR page_ptr,
long long null_delta, long long oid_delta, long long key_delta);
extern int btree_get_disk_size_of_key (DB_VALUE *);
extern TP_DOMAIN *btree_generate_prefix_domain (BTID_INT * btid);
extern int btree_glean_root_header_info (THREAD_ENTRY * thread_p, BTREE_ROOT_HEADER * root_header, BTID_INT * btid,
bool is_key_type);
extern DISK_ISVALID btree_verify_tree (THREAD_ENTRY * thread_p, const OID * class_oid_p, BTID_INT * btid,
const char *btname);
extern int btree_get_prefix_separator (const DB_VALUE * key1, const DB_VALUE * key2, DB_VALUE * prefix_key,
TP_DOMAIN * key_domain);
extern int btree_get_asc_desc (THREAD_ENTRY * thread_p, BTID * btid, int col_idx, int *asc_desc);
extern int bt_load_heap_scancache_start_for_attrinfo (THREAD_ENTRY * thread_p, SORT_ARGS * args,
HEAP_SCANCACHE * scan_cache, HEAP_CACHE_ATTRINFO * attr_info,
int save_cache_last_fix_page);
extern void bt_load_heap_scancache_end_for_attrinfo (THREAD_ENTRY * thread_p, SORT_ARGS * args,
HEAP_SCANCACHE * scan_cache, HEAP_CACHE_ATTRINFO * attr_info);
extern int
btree_load_filter_pred_function_info (THREAD_ENTRY * thread_p, SORT_ARGS * sort_args,
PRED_EXPR_WITH_CONTEXT ** filter_pred_p, FILTER_INDEX_INFO * filter_index_info_p,
FUNCTION_INDEX_INFO * func_index_info_p, XASL_UNPACK_INFO ** func_unpack_info_p,
DB_TYPE * single_node_type);
extern void bt_load_clear_pred_and_unpack (THREAD_ENTRY * thread_p, SORT_ARGS * args,
XASL_UNPACK_INFO * func_unpack_info);
/*
* btree_clear_key_value () -
* return: cleared flag
* clear_flag (in/out):
* key_value (in/out):
*/
STATIC_INLINE bool
btree_clear_key_value (bool * clear_flag, DB_VALUE * key_value)
{
if (*clear_flag == true || key_value->need_clear == true)
{
pr_clear_value (key_value);
*clear_flag = false;
}
// also set null
db_make_null (key_value);
return *clear_flag;
}
/*
* btree_init_temp_key_value () -
* return: void
* clear_flag (in/out):
* key_value (in/out):
*/
STATIC_INLINE void
btree_init_temp_key_value (bool * clear_flag, DB_VALUE * key_value)
{
db_make_null (key_value);
*clear_flag = false;
}
#endif /* _BTREE_LOAD_H_ */