File btree.h¶
File List > cubrid > src > storage > btree.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.h: B+tree index manager module(interface)
*/
#ifndef _BTREE_H_
#define _BTREE_H_
#ident "$Id$"
#if !defined (SERVER_MODE) && !defined (SA_MODE)
#error Belongs to server module
#endif /* !defined (SERVER_MODE) && !defined (SA_MODE) */
#include "access_spec.hpp"
#include "config.h"
#include "disk_manager.h"
#include "object_domain.h"
#include "oid.h"
#include "lock_manager.h"
#include "log_lsa.hpp"
#include "mvcc.h"
#include "query_evaluator.h"
#include "recovery.h"
#include "statistics.h"
#include "storage_common.h"
// forward definition
class btree_unique_stats;
struct key_val_range;
struct or_buf;
typedef struct or_buf OR_BUF;
#define SINGLE_ROW_INSERT 1
#define SINGLE_ROW_DELETE 2
#define SINGLE_ROW_UPDATE 3
#define SINGLE_ROW_MODIFY 4 /* used in case of undo */
#define MULTI_ROW_INSERT 5
#define MULTI_ROW_DELETE 6
#define MULTI_ROW_UPDATE 7
#define BTREE_IS_MULTI_ROW_OP(op) \
(op == MULTI_ROW_INSERT || op == MULTI_ROW_UPDATE || op == MULTI_ROW_DELETE)
#define BTREE_NEED_UNIQUE_CHECK(thread_p, op) \
(logtb_is_current_active (thread_p) \
&& (op == SINGLE_ROW_INSERT || op == MULTI_ROW_INSERT || op == SINGLE_ROW_UPDATE))
/* For next-key locking */
#define BTREE_CONTINUE -1
#define BTREE_GETOID_AGAIN -2
#define BTREE_GETOID_AGAIN_WITH_CHECK -3
#define BTREE_SEARCH_AGAIN_WITH_CHECK -4
#define BTREE_GOTO_END_OF_SCAN -5
#define BTREE_GOTO_START_LOCKING -6
#define BTREE_GOTO_LOCKING_DONE -7
#define BTREE_RESTART_SCAN -8
enum
{ BTREE_COERCE_KEY_WITH_MIN_VALUE = 1, BTREE_COERCE_KEY_WITH_MAX_VALUE = 2 };
/* B+tree node types */
typedef enum
{
BTREE_LEAF_NODE = 0,
BTREE_NON_LEAF_NODE,
BTREE_OVERFLOW_NODE
} BTREE_NODE_TYPE;
#define BTREE_IS_PRIMARY_KEY(unique_pk) ((unique_pk) & BTREE_CONSTRAINT_PRIMARY_KEY)
#define BTREE_IS_UNIQUE(unique_pk) ((unique_pk) & BTREE_CONSTRAINT_UNIQUE)
#define BTREE_IS_PART_KEY_DESC(btid_int) ((btid_int)->part_key_desc != 0)
#define BTREE_NORMAL_KEY 0
#define BTREE_OVERFLOW_KEY 1
#define BTREE_SET_UNIQUE_VIOLATION_ERROR(THREAD,KEY,OID,C_OID,BTID,BTNM) \
btree_set_error(THREAD, KEY, OID, C_OID, BTID, BTNM, \
ER_ERROR_SEVERITY, ER_BTREE_UNIQUE_FAILED, __FILE__, __LINE__)
/* Fixed part of a non_leaf record */
typedef struct non_leaf_rec NON_LEAF_REC;
struct non_leaf_rec
{
VPID pnt; /* The Child Page Pointer */
short key_len;
};
/* Fixed part of a leaf record */
typedef struct leaf_rec LEAF_REC;
struct leaf_rec
{
VPID ovfl; /* Overflow page pointer, for overflow OIDs */
short key_len;
};
/* BTID_INT structure from btree_load.h */
typedef struct btid_int BTID_INT;
struct btid_int
{ /* Internal btree block */
BTID *sys_btid;
int unique_pk; /* if it is an unique index, is PK */
int part_key_desc; /* the last partial-key domain is desc */
TP_DOMAIN *key_type;
TP_DOMAIN *nonleaf_key_type; /* With prefix keys, the domain of the non leaf keys might be different. It will be
* different when the domain of index is one of the fixed character types. In that
* case, the domain of the non leaf keys will be the varying counterpart to the index
* domain. */
VFID ovfid;
char *copy_buf; /* index key copy_buf pointer info; derived from INDX_SCAN_ID.copy_buf */
int copy_buf_len; /* index key copy_buf length info; derived from INDX_SCAN_ID.copy_buf_len */
int rev_level;
int deduplicate_key_idx; /* support for SUPPORT_DEDUPLICATE_KEY_MODE */
OID topclass_oid; /* class oid for which index is created */
};
/* key range structure */
typedef struct btree_keyrange BTREE_KEYRANGE;
struct btree_keyrange
{
RANGE range; /* range type */
DB_VALUE *lower_key;
DB_VALUE *upper_key;
int num_index_term;
};
/* Forward definition. */
struct indx_scan_id;
typedef struct indx_scan_id INDX_SCAN_ID;
enum bts_key_status
{
BTS_KEY_IS_NOT_VERIFIED,
BTS_KEY_IS_VERIFIED,
BTS_KEY_IS_CONSUMED,
};
typedef enum bts_key_status BTS_KEY_STATUS;
struct bts_attid_idx_info
{
bool is_init;
int keyflt_attid_idx_arr[32];
int readval_attid_idx_arr[32];
int *keyflt_attid_idx;
int *readval_attid_idx;
};
#define BTREE_INIT_SCAN_ATTID_IDXS_INFO(bts) do { \
(bts)->attid_idxs.is_init = false; \
(bts)->attid_idxs.keyflt_attid_idx_arr[0] = -1; \
(bts)->attid_idxs.readval_attid_idx_arr[0] = -1; \
(bts)->attid_idxs.keyflt_attid_idx = NULL; \
(bts)->attid_idxs.readval_attid_idx = NULL; \
} while(0)
/* Btree range search scan structure */
/* TODO: Move fields used to select visible objects only from BTREE_SCAN to
* a different structure (that is pointed by bts_other).
*/
#define COMMON_PREFIX_UNKNOWN (-1)
// *INDENT-OFF*
#ifndef NDEBUG
#define CHECK_VERIFY_COMMON_PREFIX_PAGE_INFO
#endif
#if defined(CHECK_VERIFY_COMMON_PREFIX_PAGE_INFO)
#define COMMON_PREFIX_PAGE_DEBUG_INFO_RESET(bts) do { \
VPID_SET_NULL (&((bts)->cur_common_prefix_page_vpid)); \
LSA_SET_NULL(&((bts)->cur_common_prefix_page_lsa)); \
} while(0)
#else
#define COMMON_PREFIX_PAGE_DEBUG_INFO_RESET(bts)
#endif
// *INDENT-ON*
typedef struct btree_scan BTREE_SCAN; /* BTS */
struct btree_scan
{
BTID_INT btid_int;
/* TO BE REMOVED when btree_prepare_next_search is removed. */
bool read_uncommitted;
/* TO BE REMOVED when btree_find_next_index_record is removed. */
VPID P_vpid; /* vpid of previous leaf page */
VPID C_vpid; /* vpid of current leaf page */
/* TO BE REMOVED - maybe */
VPID O_vpid; /* vpid of overflow page */
/* TO BE REMOVED when btree_find_next_index_record is removed. */
PAGE_PTR P_page; /* page ptr to previous leaf page */
PAGE_PTR C_page; /* page ptr to current leaf page */
INT16 slot_id; /* current slot identifier */
/* TO BE REMOVED */
int oid_pos; /* current oid position */
DB_VALUE cur_key; /* current key value */
bool clear_cur_key; /* clear flag for current key value */
//---------------------------------------------------------------------------------------------
#if defined(CHECK_VERIFY_COMMON_PREFIX_PAGE_INFO)
VPID cur_common_prefix_page_vpid;
LOG_LSA cur_common_prefix_page_lsa;
#endif
int common_prefix_size; // size of common prefix key parts.
DB_VALUE common_prefix_key; // common prefix key part
bool clear_common_prefix_key; //
bool is_cur_key_compressed; /* If false, cur_key is a complete key.
* Otherwise it must be combined with common_prefix_key. */
bts_attid_idx_info attid_idxs;
bool is_cur_key_copied;
//---------------------------------------------------------------------------------------------
BTREE_KEYRANGE key_range; /* key range information */
FILTER_INFO *key_filter; /* key filter information pointer */
FILTER_INFO key_filter_storage; /* key filter information storage */
bool use_desc_index; /* use descending index */
/* TO BE REMOVED */
int restart_scan; /* restart the scan */
/* for query trace */
int read_keys;
int qualified_keys;
bool key_range_max_value_equal;
/*
* cur_leaf_lsa
*/
LOG_LSA cur_leaf_lsa; /* page LSA of current leaf page */
LOCK lock_mode; /* Lock mode - S_LOCK or X_LOCK. */
RECDES key_record;
bool need_to_check_null;
LEAF_REC leaf_rec_info;
BTREE_NODE_TYPE node_type;
int offset;
BTS_KEY_STATUS key_status;
bool end_scan;
bool end_one_iteration;
bool is_interrupted;
bool is_key_partially_processed;
int n_oids_read; /* */
int n_oids_read_last_iteration; /* */
OID *oid_ptr;
OID match_class_oid;
DB_BIGINT *key_limit_lower;
DB_BIGINT *key_limit_upper;
struct indx_scan_id *index_scan_idp;
bool is_btid_int_valid;
bool is_scan_started;
bool force_restart_from_root;
bool is_fk_remake; /* support for SUPPORT_DEDUPLICATE_KEY_MODE */
PERF_UTIME_TRACKER time_track;
void *bts_other;
};
#define BTREE_INIT_SCAN(bts) \
do { \
(bts)->P_vpid.pageid = NULL_PAGEID; \
(bts)->C_vpid.pageid = NULL_PAGEID; \
(bts)->O_vpid.pageid = NULL_PAGEID; \
(bts)->P_page = NULL; \
(bts)->C_page = NULL; \
(bts)->slot_id = NULL_SLOTID; \
(bts)->oid_pos = 0; \
(bts)->restart_scan = 0; \
(bts)->is_cur_key_compressed = false; \
(bts)->common_prefix_size = COMMON_PREFIX_UNKNOWN; \
BTREE_INIT_SCAN_ATTID_IDXS_INFO((bts)); \
btree_init_temp_key_value (&(bts)->clear_common_prefix_key, &(bts)->common_prefix_key); \
COMMON_PREFIX_PAGE_DEBUG_INFO_RESET((bts)); \
db_make_null (&(bts)->cur_key); \
(bts)->clear_cur_key = false; \
(bts)->is_btid_int_valid = false; \
(bts)->read_uncommitted = false; \
(bts)->key_filter = NULL; \
(bts)->use_desc_index = false; \
(bts)->read_keys = 0; \
(bts)->qualified_keys = 0; \
(bts)->key_range_max_value_equal = false; \
LSA_SET_NULL (&(bts)->cur_leaf_lsa); \
(bts)->lock_mode = NULL_LOCK; \
(bts)->key_record.data = NULL; \
(bts)->offset = 0; \
(bts)->need_to_check_null = false; \
VPID_SET_NULL (&(bts)->leaf_rec_info.ovfl); \
(bts)->node_type = BTREE_LEAF_NODE; \
(bts)->key_status = BTS_KEY_IS_NOT_VERIFIED; \
(bts)->end_scan = false; \
(bts)->end_one_iteration = false; \
(bts)->is_interrupted = false; \
(bts)->is_key_partially_processed = false; \
(bts)->n_oids_read = 0; \
(bts)->n_oids_read_last_iteration = 0; \
(bts)->oid_ptr = NULL; \
(bts)->key_limit_lower = NULL; \
(bts)->key_limit_upper = NULL; \
(bts)->index_scan_idp = NULL; \
(bts)->is_scan_started = false; \
(bts)->force_restart_from_root = false; \
OID_SET_NULL (&(bts)->match_class_oid); \
(bts)->time_track.is_perf_tracking = false; \
(bts)->bts_other = NULL; \
(bts)->is_fk_remake = false; \
} while (0)
#define BTREE_RESET_SCAN(bts) \
do { \
(bts)->P_vpid.pageid = NULL_PAGEID; \
(bts)->C_vpid.pageid = NULL_PAGEID; \
(bts)->O_vpid.pageid = NULL_PAGEID; \
(bts)->P_page = NULL; \
(bts)->C_page = NULL; \
(bts)->slot_id = -1; \
(bts)->oid_pos = 0; \
(bts)->restart_scan = 0; \
(bts)->is_cur_key_compressed = false; \
(bts)->common_prefix_size = COMMON_PREFIX_UNKNOWN; \
btree_clear_key_value (&(bts)->clear_common_prefix_key, &(bts)->common_prefix_key); \
COMMON_PREFIX_PAGE_DEBUG_INFO_RESET((bts)); \
pr_clear_value (&(bts)->cur_key); \
db_make_null (&(bts)->cur_key); \
(bts)->clear_cur_key = false; \
(bts)->is_scan_started = false; \
(bts)->is_fk_remake = false; \
} while (0)
#define BTREE_END_OF_SCAN(bts) \
((bts)->C_vpid.pageid == NULL_PAGEID \
&& (bts)->O_vpid.pageid == NULL_PAGEID \
&& !(bts)->is_scan_started)
#define BTREE_START_OF_SCAN(bts) BTREE_END_OF_SCAN(bts)
#define BTS_IS_DESCENDING_SCAN(bts) \
((bts)->index_scan_idp->indx_info->use_desc_index)
#define BTS_SET_INDEX_SCANID(bts, index_scan_idp) \
((bts)->index_scan_idp = index_scan_idp)
#define BTS_SET_KEY_LIMIT(bts, lower, upper) \
do \
{ \
(bts)->key_limit_lower = lower; \
(bts)->key_limit_upper = upper; \
} while (false)
typedef struct btree_iscan_oid_list BTREE_ISCAN_OID_LIST;
struct btree_iscan_oid_list
{
OID *oidp; /* OID buffer. */
int oid_cnt; /* Current OID count. */
int max_oid_cnt; /* Maximum desired OID count. */
int capacity; /* Maximum capacity of buffer. Can be different than maximum desired OID count. */
BTREE_ISCAN_OID_LIST *next_list; /* Pointer to next list of OID's. */
}; /* list of OIDs */
typedef struct btree_checkscan BTREE_CHECKSCAN;
struct btree_checkscan
{
BTID btid; /* B+tree index identifier */
BTREE_SCAN btree_scan; /* B+tree search scan structure */
BTREE_ISCAN_OID_LIST oid_list; /* Data area to store OIDs */
}; /* B+tree <key-oid> check scan structure */
struct btree_ovfl_oid_capacity
{
int max_pg_cnt_per_key; /* Distinct key count with overflow oid page) */
int dis_key_cnt; /* Distinct key count (with ovfl pages) */
int64_t tot_val_cnt; /* Total number of values stored in overflow oid pages */
int tot_pg_cnt; /* Total overflow oid page count */
float tot_free_space; /* Total free space in overflow oid pages */
float tot_space; /* Total space occupied by overflow oid pages */
float tot_used_space; /* Total used space in overflow oid pages */
float avg_pg_free_sp; /* Average free space on the occupied overflowoid page */
};
typedef struct btree_capacity BTREE_CAPACITY;
struct btree_capacity
{
int fence_key_cnt; /* Number of fence-keys */
int dis_key_cnt; /* Distinct key count (in leaf pages) */
int64_t tot_val_cnt; /* Total number of values stored in tree */
int deduplicate_dis_key_cnt; /* support for SUPPORT_DEDUPLICATE_KEY_MODE */
int avg_val_per_dedup_key; /* Average number of values (OIDs) per deduplicate key */
int avg_val_per_key; /* Average number of values (OIDs) per key */
int leaf_pg_cnt; /* Leaf page count */
int nleaf_pg_cnt; /* NonLeaf page count */
int tot_pg_cnt; /* Total page count */
int height; /* Height of the tree */
float sum_rec_len; /* Sum of all record lengths */
float sum_key_len; /* Sum of all distinct key lengths */
int avg_key_len; /* Average key length */
int avg_rec_len; /* Average page record length */
float tot_free_space; /* Total free space in index */
float tot_space; /* Total space occupied by index */
float tot_used_space; /* Total used space in index */
int avg_pg_key_cnt; /* Average page key count (in leaf pages) */
float avg_pg_free_sp; /* Average page free space */
struct btree_ovfl_oid_capacity ovfl_oid_pg; /* For overflow OID page */
};
/*
* B-tree node scan section
*/
/* Structure used to queue b-tree nodes on index node info scan */
typedef struct btree_node_scan_queue_item BTREE_NODE_SCAN_QUEUE_ITEM;
struct btree_node_scan_queue_item
{
VPID crt_vpid; /* VPID for current node */
BTREE_NODE_SCAN_QUEUE_ITEM *next; /* Next node */
};
/* Structure used for index node info scan */
typedef struct btree_node_scan BTREE_NODE_SCAN;
struct btree_node_scan
{
BTID_INT btid_int; /* index btid_int structure */
VPID crt_vpid; /* VPID for current node */
PAGE_PTR crt_page; /* Current node PAGE_PTR */
bool first_call; /* First call for node info scan */
BTREE_NODE_SCAN_QUEUE_ITEM *queue_head; /* B-tree node queue head */
BTREE_NODE_SCAN_QUEUE_ITEM *queue_tail; /* B-tree node queue tail */
};
/* Initialize BTREE_NODE_SCAN structure for node info scan */
#define BTREE_NODE_SCAN_INIT(bns) \
do \
{ \
VPID_SET_NULL (&(bns)->crt_vpid); \
(bns)->crt_page = NULL; \
(bns)->queue_head = (bns)->queue_tail = NULL; \
(bns)->first_call = true; \
} \
while (0)
/* Add new item to b-tree node queue */
#define BTREE_NODE_SCAN_ADD_PAGE_TO_QUEUE(bns, node) \
if ((bns)->queue_tail == NULL) \
{ \
(bns)->queue_head = (bns)->queue_tail = node; \
} \
else \
{ \
(bns)->queue_tail->next = node; \
(bns)->queue_tail = node; \
}
/* Pop first item from b-tree node queue */
#define BTREE_NODE_SCAN_POP_PAGE_FROM_QUEUE(bns, node) \
if ((bns)->queue_head == NULL) \
{ \
node = NULL; \
} \
else \
{ \
if ((bns)->queue_head == (bns)->queue_tail) \
{ \
/* Only one item in queue */ \
node = (bns)->queue_head; \
(bns)->queue_tail = NULL; \
(bns)->queue_head = NULL; \
} \
else \
{ \
node = (bns)->queue_head; \
(bns)->queue_head = node->next; \
node->next = NULL; \
} \
}
/* Check if b-tree node queue is empty */
#define BTREE_NODE_SCAN_IS_QUEUE_EMPTY(bns) ((bns)->queue_head == NULL)
#define DBVAL_BUFSIZE 4096
#define BTREE_INIT_MVCC_HEADER(p_mvcc_rec_header) \
do \
{ \
MVCC_SET_FLAG (p_mvcc_rec_header, 0); \
MVCC_SET_INSID (p_mvcc_rec_header, MVCCID_NULL); \
MVCC_SET_DELID (p_mvcc_rec_header, MVCCID_NULL); \
MVCC_SET_CHN (p_mvcc_rec_header, 0); \
MVCC_SET_REPID (p_mvcc_rec_header, 0); \
LSA_SET_NULL (&((p_mvcc_rec_header)->prev_version_lsa)); \
} \
while (0)
/* When MVCC is enabled, btree_delete/btree_insert functionality are extended
* to do additional types of action. Depending on the context, an object can
* be added or removed, delete MVCCID can be added/removed or insert MVCCID
* can be removed.
*/
enum btree_op_purpose
{
BTREE_OP_NO_OP, /* No op. */
BTREE_OP_INSERT_NEW_OBJECT, /* Insert a new object into b-tree along with its insert MVCCID. */
BTREE_OP_INSERT_MVCC_DELID, /* Insert delete MVCCID for object when deleted. */
BTREE_OP_INSERT_MARK_DELETED, /* Mark object as deleted. This is used on a unique index of a non-MVCC class. It is
* very similar to BTREE_OP_INSERT_MVCC_DELID. The differences are: 1. The context they
* are used for. MVCC delete is used to delete from MVCC-enabled classes. Mark deleted
* is used for unique indexes of MVCC-disabled classes like _db_serial. 2. Mark deleted
* is followed by a postpone operation which removes the object after commit. 3. Mark
* deleted is not vacuumed. Object will be "cleaned" on commit/rollback. */
BTREE_OP_INSERT_UNDO_PHYSICAL_DELETE, /* Undo of physical delete. */
BTREE_OP_DELETE_OBJECT_PHYSICAL, /* Physically delete an object from b-tree when MVCC is enabled. */
BTREE_OP_DELETE_OBJECT_PHYSICAL_POSTPONED, /* Physical delete was postponed. */
BTREE_OP_DELETE_UNDO_INSERT, /* Undo insert */
BTREE_OP_DELETE_UNDO_INSERT_UNQ_MULTIUPD, /* Undo insert into unique index, when multi-update exception to unique
* constraint violation is applied. Previous visible object must be
* returned to first position in record. */
BTREE_OP_DELETE_UNDO_INSERT_DELID, /* Remove only delete MVCCID for an object in b-tree. It is called when object
* deletion is roll-backed. */
BTREE_OP_DELETE_VACUUM_OBJECT, /* All object info is removed from b-tree. It is called by vacuum when the
* object becomes completely invisible. */
BTREE_OP_DELETE_VACUUM_INSID, /* Remove only insert MVCCID for an object in b-tree. It is called by vacuum when the
* object becomes visible to all running transactions. */
BTREE_OP_NOTIFY_VACUUM, /* Notify vacuum of an object in need of cleanup. */
/* Below purposes are used during online index loading. */
BTREE_OP_ONLINE_INDEX_IB_INSERT, /* Insert done by the Index Builder. */
BTREE_OP_ONLINE_INDEX_IB_DELETE, /* Delete done by the Index Builder. */
BTREE_OP_ONLINE_INDEX_TRAN_INSERT, /* Insert done by a transaction. */
BTREE_OP_ONLINE_INDEX_TRAN_INSERT_DF, /* Insert done by a transaction with DELETE_FLAG set. */
BTREE_OP_ONLINE_INDEX_UNDO_TRAN_INSERT, /* Undo an insert */
BTREE_OP_ONLINE_INDEX_TRAN_DELETE, /* Delete done by a transaction. */
BTREE_OP_ONLINE_INDEX_UNDO_TRAN_DELETE /* Undo a delete. */
};
typedef enum btree_op_purpose BTREE_OP_PURPOSE;
/* BTREE_MVCC_INFO -
* Structure used to store b-tree specific MVCC information.
* Flags field will show which information exists (insert and/or delete
* MVCCID's).
*/
typedef struct btree_mvcc_info BTREE_MVCC_INFO;
struct btree_mvcc_info
{
short flags; /* Has insert and has delete flags. */
MVCCID insert_mvccid; /* Insert MVCCID value. */
MVCCID delete_mvccid; /* Delete MVCCID value. */
};
#define BTREE_MVCC_INFO_INITIALIZER \
{ 0, MVCCID_ALL_VISIBLE, MVCCID_NULL }
/* BTREE_OBJECT_INFO -
* Structure used to store b-tree specific object information.
*/
typedef struct btree_object_info BTREE_OBJECT_INFO;
struct btree_object_info
{
OID oid; /* Instance OID. */
OID class_oid; /* Class OID. */
BTREE_MVCC_INFO mvcc_info; /* MVCC information. */
};
#define BTREE_OBJECT_INFO_INITIALIZER \
{ OID_INITIALIZER, OID_INITIALIZER, BTREE_MVCC_INFO_INITIALIZER }
struct key_oid
{
DB_VALUE m_key;
OID m_oid;
};
// *INDENT-OFF*
struct page_key_boundary
{
DB_VALUE m_left_key;
DB_VALUE m_right_key;
bool m_is_inf_left_key;
bool m_is_inf_right_key;
page_key_boundary ();
~page_key_boundary ();
void set_value (DB_VALUE &dest_value, DB_VALUE &src_value, bool &clear_src_value);
int set_value (THREAD_ENTRY * thread_p, DB_VALUE &dest_value, BTID_INT * btid, PAGE_PTR page_ptr, const INT16 slot);
int set_value (THREAD_ENTRY * thread_p, DB_VALUE &dest_value, BTID_INT * btid, PAGE_PTR page_ptr, RECDES &rec);
int update_boundary_eq (THREAD_ENTRY * thread_p, BTID_INT * btid, PAGE_PTR page_ptr,
DB_VALUE &subtree_value, bool &clear_subtree_value, const INT16 subtree_slot);
int update_boundary_lt (THREAD_ENTRY * thread_p, BTID_INT * btid, PAGE_PTR page_ptr,
RECDES &left_subtree_rec, DB_VALUE &subtree_value, bool &clear_subtree_value);
int update_boundary_gt_or_eq (THREAD_ENTRY * thread_p, BTID_INT * btid, PAGE_PTR page_ptr,
DB_VALUE &subtree_value, bool &clear_subtree_value, const INT16 subtree_slot,
const int key_cnt);
};
struct btree_insert_list
{
enum
{
KEY_AVAILABLE = 0,
KEY_NOT_AVAILABLE
};
std::vector<key_oid> m_keys_oids;
std::vector<key_oid*> m_sorted_keys_oids;
DB_VALUE *m_curr_key;
OID *m_curr_oid;
int m_curr_pos;
const TP_DOMAIN *m_key_type;
int m_ignored_nulls_cnt;
page_key_boundary m_boundaries;
bool m_use_page_boundary_check;
bool m_use_sorted_bulk_insert;
int m_keep_page_iterations;
int m_ovf_appends;
int m_ovf_appends_new_page;
btree_insert_list () = delete;
btree_insert_list (const TP_DOMAIN *&key_type)
: m_curr_key (NULL)
, m_curr_oid (NULL)
, m_curr_pos (0)
, m_key_type (key_type)
, m_ignored_nulls_cnt (0)
, m_use_page_boundary_check (false)
, m_use_sorted_bulk_insert (false)
{
}
btree_insert_list (DB_VALUE *key, OID *oid);
~btree_insert_list ();
int next_key ();
OID *get_oid ()
{
return m_curr_oid;
}
DB_VALUE *get_key ()
{
return m_curr_key;
}
size_t add_key (const DB_VALUE *key, const OID &oid);
void reset_boundary_keys ();
void prepare_list (void);
bool check_release_latch (THREAD_ENTRY * thread_p, void *arg, PAGE_PTR leaf_page);
};
// *INDENT-ON*
/* BTREE_RANGE_SCAN_PROCESS_KEY_FUNC -
* btree_range_scan internal function that is called for each key that passes
* range/filter checks.
*
* Functions:
* btree_range_scan_select_visible_oids.
*/
typedef int BTREE_RANGE_SCAN_PROCESS_KEY_FUNC (THREAD_ENTRY * thread_p, BTREE_SCAN * bts);
extern int btree_find_foreign_key (THREAD_ENTRY * thread_p, BTID * btid, DB_VALUE * key, OID * class_oid,
OID * found_oid);
/* support for SUPPORT_DEDUPLICATE_KEY_MODE */
extern int btree_remake_foreign_key_with_PK (THREAD_ENTRY * thread_p, BTID * btid, DB_VALUE * key, OID * class_oid,
key_val_range * kv_range, bool * is_newly);
extern int btree_remake_reference_key_with_FK (THREAD_ENTRY * thread_p, TP_DOMAIN * pk_domain, DB_VALUE * fk_key,
DB_VALUE * new_key);
extern void btree_scan_clear_key (BTREE_SCAN * btree_scan);
extern void bts_reset_scan (THREAD_ENTRY * thread_p, BTREE_SCAN * bts);
extern bool btree_is_unique_type (BTREE_TYPE type);
extern int xbtree_get_unique_pk (THREAD_ENTRY * thread_p, BTID * btid);
extern int btree_get_unique_statistics (THREAD_ENTRY * thread_p, BTID * btid, long long *oid_cnt, long long *null_cnt,
long long *key_cnt);
extern int btree_get_unique_statistics_for_count (THREAD_ENTRY * thread_p, BTID * btid, long long *oid_cnt,
long long *null_cnt, long long *key_cnt);
extern int btree_get_stats (THREAD_ENTRY * thread_p, BTREE_STATS * stat_info_p, bool with_fullscan);
extern int btree_get_pkey_btid (THREAD_ENTRY * thread_p, OID * cls_oid, BTID * pkey_btid);
extern DISK_ISVALID btree_check_by_class_oid (THREAD_ENTRY * thread_p, OID * cls_oid, BTID * idx_btid);
extern DISK_ISVALID btree_check_all (THREAD_ENTRY * thread_p);
extern int btree_keyoid_checkscan_start (THREAD_ENTRY * thread_p, BTID * btid, BTREE_CHECKSCAN * btscan);
extern DISK_ISVALID btree_keyoid_checkscan_check (THREAD_ENTRY * thread_p, BTREE_CHECKSCAN * btscan, OID * cls_oid,
DB_VALUE * key, OID * oid);
extern void btree_keyoid_checkscan_end (THREAD_ENTRY * thread_p, BTREE_CHECKSCAN * btscan);
#if defined(ENABLE_UNUSED_FUNCTION)
extern int btree_estimate_total_numpages (THREAD_ENTRY * thread_p, int dis_key_cnt, int avg_key_len, int tot_val_cnt,
int *blt_pgcnt_est, int *blt_wrs_pgcnt_est);
#endif
extern int btree_index_capacity (THREAD_ENTRY * thread_p, BTID * btid, BTREE_CAPACITY * cpc);
extern int btree_physical_delete (THREAD_ENTRY * thread_p, BTID * btid, DB_VALUE * key, OID * oid, OID * class_oid,
int *unique, int op_type, btree_unique_stats * unique_stat_info);
extern int btree_vacuum_insert_mvccid (THREAD_ENTRY * thread_p, BTID * btid, OR_BUF * buffered_key, OID * oid,
OID * class_oid, MVCCID insert_mvccid);
extern int btree_vacuum_object (THREAD_ENTRY * thread_p, BTID * btid, OR_BUF * buffered_key, OID * oid, OID * class_oid,
MVCCID delete_mvccid);
extern int btree_update (THREAD_ENTRY * thread_p, BTID * btid, DB_VALUE * old_key, DB_VALUE * new_key, OID * cls_oid,
OID * oid, int op_type, btree_unique_stats * unique_stat_info, int *unique,
MVCC_REC_HEADER * p_mvcc_rec_header);
extern int btree_reflect_global_unique_statistics (THREAD_ENTRY * thread_p, GLOBAL_UNIQUE_STATS * unique_stat_info,
bool only_active_tran);
extern int btree_find_min_or_max_key (THREAD_ENTRY * thread_p, BTID * btid, DB_VALUE * key, int flag_minkey);
extern bool btree_multicol_key_is_null (DB_VALUE * key);
extern int btree_multicol_key_has_null (DB_VALUE * key);
extern DISK_ISVALID btree_find_key (THREAD_ENTRY * thread_p, BTID * btid, OID * oid, DB_VALUE * key, bool * clear_key);
/* for migration */
extern TP_DOMAIN *btree_read_key_type (THREAD_ENTRY * thread_p, BTID * btid);
/* Dump routines */
extern int btree_dump_capacity (THREAD_ENTRY * thread_p, FILE * fp, BTID * btid);
extern void btree_dump (THREAD_ENTRY * thread_p, FILE * fp, BTID * btid, int level);
/* Recovery routines */
extern int btree_rv_util_save_page_records (THREAD_ENTRY * thread_p, PAGE_PTR page_ptr, INT16 first_slotid, int rec_cnt,
INT16 ins_slotid, char *data, int *length);
#if defined(ENABLE_UNUSED_FUNCTION)
extern void btree_rv_util_dump_leafrec (THREAD_ENTRY * thread_p, FILE * fp, BTID_INT * btid, RECDES * Rec);
extern void btree_rv_util_dump_nleafrec (THREAD_ENTRY * thread_p, FILE * fp, BTID_INT * btid, RECDES * Rec);
#endif
extern int btree_rv_roothdr_undo_update (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_update_tran_stats (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern void btree_rv_roothdr_dump (FILE * fp, int length, void *data);
extern int btree_rv_ovfid_undoredo_update (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern void btree_rv_ovfid_dump (FILE * fp, int length, void *data);
extern int btree_rv_nodehdr_undoredo_update (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_nodehdr_redo_insert (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_nodehdr_undo_insert (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_noderec_undoredo_update (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern void btree_rv_noderec_dump (FILE * fp, int length, void *data);
extern int btree_rv_noderec_redo_insert (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_noderec_undo_insert (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern void btree_rv_noderec_dump_slot_id (FILE * fp, int length, void *data);
extern int btree_rv_pagerec_insert (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_pagerec_delete (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_newpage_redo_init (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_save_keyval_for_undo (BTID_INT * btid, DB_VALUE * key, OID * cls_oid, OID * oid,
BTREE_MVCC_INFO * mvcc_info, BTREE_OP_PURPOSE purpose,
char *preallocated_buffer, char **data, int *capacity, int *length);
extern int btree_rv_keyval_undo_insert (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_keyval_undo_insert_unique (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_keyval_undo_insert_mvcc_delid (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_keyval_undo_delete (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_remove_marked_for_delete (THREAD_ENTRY * thread_p, LOG_RCV * rcv);
extern void btree_rv_keyval_dump (FILE * fp, int length, void *data);
extern int btree_rv_undoredo_copy_page (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_nop (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_redo_global_unique_stats_commit (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_undo_global_unique_stats_commit (THREAD_ENTRY * thread_p, LOG_RCV * recv);
#include "scan_manager.h"
extern int btree_keyval_search (THREAD_ENTRY * thread_p, BTID * btid, SCAN_OPERATION_TYPE scan_op_type,
BTREE_SCAN * BTS, key_val_range * key_val_range, OID * class_oid, FILTER_INFO * filter,
INDX_SCAN_ID * isidp, bool is_all_class_srch);
extern int btree_range_scan (THREAD_ENTRY * thread_p, BTREE_SCAN * bts, BTREE_RANGE_SCAN_PROCESS_KEY_FUNC * key_func);
extern int btree_range_scan_select_visible_oids (THREAD_ENTRY * thread_p, BTREE_SCAN * bts);
extern int btree_attrinfo_read_dbvalues (THREAD_ENTRY * thread_p, DB_VALUE * curr_key, BTREE_SCAN * bts,
int *btree_att_ids, int btree_num_att, HEAP_CACHE_ATTRINFO * attr_info,
int func_index_col_id, int *attr_idx_ptr);
extern int btree_coerce_key (DB_VALUE * src_keyp, int keysize, TP_DOMAIN * btree_domainp, int key_minmax);
extern int btree_set_error (THREAD_ENTRY * thread_p, const DB_VALUE * key, const OID * obj_oid, const OID * class_oid,
const BTID * btid, const char *bt_name, int severity, int err_id, const char *filename,
int lineno);
extern DISK_ISVALID btree_repair_prev_link (THREAD_ENTRY * thread_p, OID * oid, BTID * btid, bool repair);
extern int btree_index_start_scan (THREAD_ENTRY * thread_p, int show_type, DB_VALUE ** arg_values, int arg_cnt,
void **ctx);
extern int btree_index_end_scan (THREAD_ENTRY * thread_p, void **ctx);
extern SCAN_CODE btree_index_next_scan (THREAD_ENTRY * thread_p, int cursor, DB_VALUE ** out_values, int out_cnt,
void *ctx);
extern SCAN_CODE btree_get_next_key_info (THREAD_ENTRY * thread_p, BTID * btid, BTREE_SCAN * bts, int num_classes,
OID * class_oids_ptr, INDX_SCAN_ID * index_scan_id_p, DB_VALUE ** key_info);
extern SCAN_CODE btree_get_next_node_info (THREAD_ENTRY * thread_p, BTID * btid, BTREE_NODE_SCAN * btns,
DB_VALUE ** node_info);
extern int xbtree_get_key_type (THREAD_ENTRY * thread_p, BTID btid, TP_DOMAIN ** key_type);
extern int btree_leaf_get_first_object (BTID_INT * btid, RECDES * recp, OID * oidp, OID * class_oid,
BTREE_MVCC_INFO * mvcc_info);
extern void btree_leaf_change_first_object (THREAD_ENTRY * thread_p, RECDES * recp, BTID_INT * btid, OID * oidp,
OID * class_oidp, BTREE_MVCC_INFO * mvcc_info, int *key_offset,
char **rv_undo_data_ptr, char **rv_redo_data_ptr);
extern int btree_insert (THREAD_ENTRY * thread_p, BTID * btid, DB_VALUE * key, OID * cls_oid, OID * oid, int op_type,
btree_unique_stats * unique_stat_info, int *unique, MVCC_REC_HEADER * p_mvcc_rec_header);
extern int btree_mvcc_delete (THREAD_ENTRY * thread_p, BTID * btid, DB_VALUE * key, OID * class_oid, OID * oid,
int op_type, btree_unique_stats * unique_stat_info, int *unique,
MVCC_REC_HEADER * p_mvcc_rec_header);
extern void btree_set_mvcc_header_ids_for_update (THREAD_ENTRY * thread_p, bool do_delete_only, bool do_insert_only,
MVCCID * mvccid, MVCC_REC_HEADER * mvcc_rec_header);
extern int btree_compare_btids (void *mem_btid1, void *mem_btid2);
extern char *btree_pack_mvccinfo (char *ptr, BTREE_MVCC_INFO * mvcc_info);
extern int btree_packed_mvccinfo_size (BTREE_MVCC_INFO * mvcc_info);
extern void btree_set_mvcc_flags_into_oid (MVCC_REC_HEADER * p_mvcc_header, OID * oid);
extern void btree_clear_mvcc_flags_from_oid (OID * oid);
extern int btree_rv_read_keyval_info_nocopy (THREAD_ENTRY * thread_p, char *datap, int data_size, BTID_INT * btid,
OID * cls_oid, OID * oid, BTREE_MVCC_INFO * mvcc_info, DB_VALUE * key);
extern void btree_rv_read_keybuf_nocopy (THREAD_ENTRY * thread_p, char *datap, int data_size, BTID_INT * btid,
OID * cls_oid, OID * oid, BTREE_MVCC_INFO * mvcc_info, OR_BUF * key_buf);
extern void btree_rv_read_keybuf_two_objects (THREAD_ENTRY * thread_p, char *datap, int data_size, BTID_INT * btid_int,
BTREE_OBJECT_INFO * first_version, BTREE_OBJECT_INFO * second_version,
OR_BUF * key_buf);
#if !defined (NDEBUG)
extern int btree_check_valid_record (THREAD_ENTRY * thread_p, BTID_INT * btid, RECDES * recp, BTREE_NODE_TYPE node_type,
DB_VALUE * key);
#endif
extern int btree_check_foreign_key (THREAD_ENTRY * thread_p, OID * cls_oid, HFID * hfid, OID * oid, DB_VALUE * keyval,
int n_attrs, OID * pk_cls_oid, BTID * pk_btid, const char *fk_name);
extern void btree_get_root_vpid_from_btid (THREAD_ENTRY * thread_p, BTID * btid, VPID * root_vpid);
extern int btree_get_btid_from_file (THREAD_ENTRY * thread_p, const VFID * vfid, BTID * btid_out);
extern int btree_prepare_bts (THREAD_ENTRY * thread_p, BTREE_SCAN * bts, BTID * btid, INDX_SCAN_ID * index_scan_id_p,
key_val_range * key_val_range, FILTER_INFO * filter, const OID * match_class_oid,
DB_BIGINT * key_limit_upper, DB_BIGINT * key_limit_lower, bool need_to_check_null,
void *bts_other);
extern void btree_mvcc_info_from_heap_mvcc_header (MVCC_REC_HEADER * mvcc_header, BTREE_MVCC_INFO * mvcc_info);
extern void btree_mvcc_info_to_heap_mvcc_header (BTREE_MVCC_INFO * mvcc_info, MVCC_REC_HEADER * mvcc_header);
extern int btree_rv_redo_record_modify (THREAD_ENTRY * thread_p, LOG_RCV * rcv);
extern int btree_rv_undo_record_modify (THREAD_ENTRY * thread_p, LOG_RCV * rcv);
extern int btree_rv_remove_unique_stats (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern void btree_leaf_record_change_overflow_link (THREAD_ENTRY * thread_p, BTID_INT * btid_int, RECDES * leaf_record,
VPID * new_overflow_vpid, char **rv_undo_data_ptr,
char **rv_redo_data_ptr);
extern int btree_rv_undo_mark_dealloc_page (THREAD_ENTRY * thread_p, LOG_RCV * rcv);
extern unsigned int btree_hash_btid (void *btid, int hash_size);
extern int btree_create_file (THREAD_ENTRY * thread_p, const OID * class_oid, int attrid, BTID * btid);
extern int btree_initialize_new_page (THREAD_ENTRY * thread_p, PAGE_PTR page, void *args);
extern int btree_locate_key (THREAD_ENTRY * thread_p, BTID_INT * btid_int, DB_VALUE * key, VPID * pg_vpid,
INT16 * slot_id, PAGE_PTR * leaf_page_out, bool * found_p);
extern int btree_get_num_visible_from_leaf_and_ovf (THREAD_ENTRY * thread_p, BTID_INT * btid_int, RECDES * leaf_record,
int offset_after_key, LEAF_REC * leaf_info, int *max_visible_oids,
MVCC_SNAPSHOT * mvcc_snapshot, int *num_visible);
extern int btree_write_record (THREAD_ENTRY * thread_p, BTID_INT * btid, void *node_rec, DB_VALUE * key,
BTREE_NODE_TYPE node_type, int key_type, int key_len, bool during_loading,
OID * class_oid, OID * oid, BTREE_MVCC_INFO * mvcc_info, RECDES * rec);
extern int btree_read_record (THREAD_ENTRY * thread_p, BTID_INT * btid, PAGE_PTR pgptr, RECDES * Rec, DB_VALUE * key,
void *rec_header, BTREE_NODE_TYPE node_type, bool * clear_key, int *offset, int copy,
BTREE_SCAN * bts);
extern DB_VALUE_COMPARE_RESULT btree_compare_key (DB_VALUE * key1, DB_VALUE * key2, TP_DOMAIN * key_domain,
int do_coercion, int total_order, int *start_colp);
extern PERF_PAGE_TYPE btree_get_perf_btree_page_type (THREAD_ENTRY * thread_p, PAGE_PTR page_ptr);
extern void btree_dump_key (FILE * fp, const DB_VALUE * key);
extern int btree_online_index_dispatcher (THREAD_ENTRY * thread_p, BTID * btid, DB_VALUE * key, OID * cls_oid,
OID * oid, int unique, BTREE_OP_PURPOSE purpose, LOG_LSA * undo_nxlsa);
extern int btree_online_index_list_dispatcher (THREAD_ENTRY * thread_p, BTID * btid, OID * cls_oid,
btree_insert_list * insert_list, int unique, BTREE_OP_PURPOSE purpose,
LOG_LSA * undo_nxlsa);
extern int btree_rv_keyval_undo_online_index_tran_insert (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_rv_keyval_undo_online_index_tran_delete (THREAD_ENTRY * thread_p, LOG_RCV * recv);
extern int btree_online_index_check_unique_constraint (THREAD_ENTRY * thread_p, BTID * btid, const char *index_name,
OID * class_oid);
extern int btree_get_class_oid_of_unique_btid (THREAD_ENTRY * thread_p, BTID * btid, OID * class_oid);
extern bool btree_is_btid_online_index (THREAD_ENTRY * thread_p, OID * class_oid, BTID * btid);
extern void btree_range_scan_free_matched_idx (BTREE_SCAN * bts);
#endif /* _BTREE_H_ */