1 /* Copyright (C) 2014 InfiniDB, Inc. 2 3 This program is free software; you can redistribute it and/or 4 modify it under the terms of the GNU General Public License 5 as published by the Free Software Foundation; version 2 of 6 the License. 7 8 This program is distributed in the hope that it will be useful, 9 but WITHOUT ANY WARRANTY; without even the implied warranty of 10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 GNU General Public License for more details. 12 13 You should have received a copy of the GNU General Public License 14 along with this program; if not, write to the Free Software 15 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, 16 MA 02110-1301, USA. */ 17 18 /****************************************************************************************** 19 * $Id: we_index.h 4450 2013-01-21 14:13:24Z rdempsey $ 20 * 21 ******************************************************************************************/ 22 /** @file */ 23 24 #ifndef _WE_INDEX_H_ 25 #define _WE_INDEX_H_ 26 27 #include <bitset> 28 29 #include "we_type.h" 30 31 32 33 /** Namespace WriteEngine */ 34 namespace WriteEngine 35 { 36 37 /***************************************************** 38 * index definition 39 ******************************************************/ 40 const int IDX_BITTEST_SIZE = 10; /** @brief The bit size of bit test */ 41 const int IDX_GROUP_SIZE = 3; /** @brief The bit size of group */ 42 const int IDX_INSTRU_SIZE = 4; /** @brief The bit size of instruction */ 43 const int IDX_PTR_SIZE = 46; /** @brief The bit size of address pointer */ 44 const int IDX_TYPE_SIZE = 3; /** @brief The bit size of type */ 45 46 const int IDX_BITMAP_SUBBLOCK_NO = 1; /** @brief Subblock 1 of root block is for bitmap pointer*/ 47 const int IDX_MAX_TREE_LEVEL = 128; /** @brief The maximum depth of a tree */ 48 const int IDX_MAX_MULTI_COL_BIT = 256; /** @brief The maximum bits of a multi-column tree (256 bit)*/ 49 const int IDX_MAX_MULTI_COL_IDX_LEVEL = 52; /** @brief The maximum depth of a multi-column tree */ 50 const int IDX_MAX_MULTI_COL_IDX_NUM = 64; /** @brief The maximum number of columns for a multi-column index */ 51 const int MAX_IDX_RID = 1024; /** @brief Maximum index rids for one shot */ 52 const int IDX_DEFAULT_READ_ROW = 10000; /** @brief Default number of rows for one read for index */ 53 54 // todo: need to move a higher level share file for dictionary 55 const int RID_SIZE = 46; 56 // const int OID_SIZE = 24; /** @brief The bit size of object id */ 57 const int FBO_SIZE = 36; /** @brief The bit size of file block offset */ 58 const int SBID_SIZE = 5; /** @brief The bit size of sub block id */ 59 const int ENTRY_SIZE = 5; /** @brief The bit size of entry location with a sub block */ 60 61 const int LIST_SIZE_TYPE = 0; 62 const int LIST_RID_TYPE = 3; 63 const int LIST_NOT_USED_TYPE = 7; 64 const int LIST_HDR_SIZE = 32; 65 const int LIST_SUBBLOCK_TYPE = 4 ; 66 const int LIST_BLOCK_TYPE = 5 ; 67 const int LIST_LLP_TYPE = 6 ; 68 const int SUBBLOCK_TOTAL_BYTES = 256; 69 const int LIST_SUB_LLP_POS = 31; 70 const int LIST_LAST_LBID_POS = 30; 71 const int LIST_BLOCK_LLP_POS = 1023; 72 const int MAX_BLOCK_ENTRY = 1024; 73 const int MAX_SUB_RID_CNT = 30; 74 const int MAX_BLK_RID_CNT = 1023; 75 const int MAX_BLK_NARRAY_RID_CNT = 1018; 76 const int LBID_SBID_ENTRY = 46; 77 const int RID_COUNT_SIZE = 10; 78 const int CUR_BLK_POS_WIDTH = 2; 79 const int LLP_STATUS_WIDTH = 2; 80 const int LIST_ENTRY_WIDTH = 8; 81 const int LIST_BLK_LLP_ENTRY_WIDTH = 48; 82 const int BEGIN_LIST_BLK_LLP_POS = 1018; 83 const int NEXT_BLK_PTR_OFFSET = 5; 84 const int PARENT_PTR_OFFSET = 4; 85 const int TOTAL_NUM_ARRAY_PTR = 4; 86 const int ARRAY_LLP_EXIST = 1; 87 const int LLP_NOT_FULL = 0; 88 const int LLP_FULL = 1; 89 const int TOTAL_CUR_LEVEL = 10; 90 const int CUR_LEVEL_POS_WIDTH = 20; 91 const uint64_t INVALID_KEY = -1LL; /** @brief Invalid number */ 92 93 /***************************************************** 94 * mask definition 95 ******************************************************/ 96 const int BIT_MASK_ARRAY[] = { 0x0, 97 0x01, /** @brief 1 bit mask */ 98 0x03, /** @brief 2 bit mask */ 99 0x07, /** @brief 3 bit mask */ 100 0x0F, /** @brief 4 bit mask */ 101 0x1F, /** @brief 5 bit mask */ 102 0x3F /** @brief 6 bit mask */ 103 }; 104 105 /************************************************************************ 106 * Type enumerations 107 ************************************************************************/ 108 enum IdxTreeEntryType /** @brief Index tree entry types */ 109 { 110 EMPTY_ENTRY = 0, /** @brief Empty entry */ 111 UNIQUE_VAL = 7, /** @brief Unique value */ 112 EMPTY_LIST = 1, /** @brief Empty list pointer entry */ 113 EMPTY_PTR = 2, /** @brief Empty pointer entry */ 114 BIT_TEST = 3, /** @brief Bit test entry */ 115 LEAF_LIST = 4, /** @brief Leaf list pointer */ 116 BITMAP_PTR = 5, /** @brief Bitmap pointer */ 117 // SORT_LIST = 5, /** @brief Sorted list pointer */ 118 MULTI_COL = 6 /** @brief Multi-column index pointer */ 119 }; 120 121 enum IdxTreeGroupType /** @brief Index tree group types */ 122 { 123 ENTRY_1 = 0, /** @brief 1 entry per group */ 124 ENTRY_2 = 1, /** @brief 2 entry per group */ 125 ENTRY_4 = 2, /** @brief 4 entry per group */ 126 ENTRY_8 = 3, /** @brief 8 entry per group */ 127 ENTRY_16 = 4, /** @brief 16 entry per group */ 128 ENTRY_32 = 5, /** @brief 32 entry per group */ 129 ENTRY_BLK = 6 /** @brief 1k entry per group */ 130 }; 131 132 enum IdxBitCompareType /** @brief Index bit compare types */ 133 { 134 BIT_5 = 0, /** @brief 5-bit compare */ 135 BIT_10 = 1 /** @brief 10-bit compare */ 136 }; 137 138 enum IdxFreeMgrType /** @brief Index free manager types */ 139 { 140 TREE = 0, /** @brief Index tree type */ 141 LIST = 1 /** @brief Index list type */ 142 }; 143 144 /************************************************************************ 145 * @brief index defintions 146 ************************************************************************/ 147 typedef struct 148 { 149 uint64_t type : 150 IDX_TYPE_SIZE; /** @brief entry type */ 151 uint64_t spare : 12; /** @brief spare bits */ 152 uint64_t group : 153 IDX_GROUP_SIZE; /** @brief entry group type */ 154 // The following is related to ptr 155 uint64_t fbo : 156 FBO_SIZE; /** @brief file block offset */ 157 uint64_t sbid : 158 SBID_SIZE; /** @brief sub block id */ 159 uint64_t entry : 160 ENTRY_SIZE; /** @brief entry within sub block */ 161 } IdxStartSubBlockEntry; /** @brief Index start block entry structure */ 162 163 typedef struct 164 { 165 uint64_t type : 166 IDX_TYPE_SIZE; /** @brief entry type */ 167 uint64_t spare : 2; /** @brief spare bits */ 168 uint64_t group : 169 IDX_GROUP_SIZE; /** @brief entry group type */ 170 // The following is related to ptr 171 uint64_t spare2 : 10; /** @brief spare bits */ 172 uint64_t fbo : 173 FBO_SIZE; /** @brief file block offset */ 174 uint64_t sbid : 175 SBID_SIZE; /** @brief sub block id */ 176 uint64_t entry : 177 ENTRY_SIZE; /** @brief entry within sub block */ 178 } IdxEmptyListEntry; /** @brief Index empty list entry structure */ 179 180 typedef struct 181 { 182 uint64_t type : 183 IDX_TYPE_SIZE; /** @brief entry type */ 184 uint64_t spare : 15; /** @brief spare bits */ 185 // The following is related to ptr 186 uint64_t fbo : 187 FBO_SIZE; /** @brief file block offset */ 188 uint64_t sbid : 189 SBID_SIZE; /** @brief sub block id */ 190 uint64_t entry : 191 ENTRY_SIZE; /** @brief entry within sub block */ 192 } IdxBitmapPointerEntry; /** @brief Index bitmap pointer entry structure */ 193 194 typedef struct 195 { 196 uint64_t type : 197 IDX_TYPE_SIZE; /** @brief entry type */ 198 uint64_t bitTest : 199 IDX_BITTEST_SIZE; /** @brief index bittest */ 200 uint64_t group : 201 IDX_GROUP_SIZE; /** @brief entry group type */ 202 uint64_t bitCompare : 1; 203 uint64_t spare : 1; /** @brief spare bits */ 204 // The following is related to ptr 205 uint64_t fbo : 206 FBO_SIZE; /** @brief file block offset */ 207 uint64_t sbid : 208 SBID_SIZE; /** @brief sub block id */ 209 uint64_t entry : 210 ENTRY_SIZE; /** @brief entry within sub block */ 211 } IdxBitTestEntry; /** @brief Index bit test entry structure */ 212 213 typedef struct 214 { 215 uint64_t type : 216 IDX_TYPE_SIZE; /** @brief entry type */ 217 uint64_t spare : 15; /** @brief spare bits */ 218 // The following is related to ptr 219 uint64_t fbo : 220 FBO_SIZE; /** @brief file block offset */ 221 uint64_t sbid : 222 SBID_SIZE; /** @brief sub block id */ 223 uint64_t entry : 224 ENTRY_SIZE; /** @brief entry within sub block */ 225 } IdxTreePointerEntry; /** @brief Index tree pointer entry structure */ 226 /************************************************************************ 227 * @brief index list node defintions 228 ************************************************************************/ 229 typedef struct 230 { 231 uint64_t type : 232 IDX_TYPE_SIZE; /** @brief entry type 3 */ 233 uint64_t spare : 15; /** @brief spare bits */ 234 RID rid : 235 RID_SIZE; /** @brief row id */ 236 } IdxRidListEntry; /** @brief Index rid list entry structure */ 237 238 typedef struct 239 { 240 uint64_t type : 241 IDX_TYPE_SIZE; /** @brief entry type */ 242 uint64_t spare : 5; 243 uint64_t count : 244 RID_COUNT_SIZE; /** the count of rids on the current blk */ 245 uint64_t llp : 246 LBID_SBID_ENTRY; /** @brief size */ 247 } IdxRidListPtr; 248 249 typedef struct 250 { 251 uint64_t type : 252 IDX_TYPE_SIZE; /** @brief entry type */ 253 uint64_t spare : 5; 254 uint64_t count : 255 RID_COUNT_SIZE; /** the count of rids on the current blk */ 256 uint64_t lbid : 257 FBO_SIZE; /** @brief size */ 258 uint64_t sbid : 259 SBID_SIZE; /** @brief sub block id */ 260 uint64_t entry : 261 ENTRY_SIZE; /** @brief entry within sub block */ 262 } IdxRidLastListPtr; 263 264 typedef struct 265 { 266 uint64_t type : 267 IDX_TYPE_SIZE; /** @brief entry type */ 268 uint64_t spare : 13; 269 uint64_t llpStat : 270 LLP_STATUS_WIDTH; /** llp status */ 271 uint64_t childLbid : 272 FBO_SIZE; /** @brief file block offset */ 273 uint64_t spare2 : 10; 274 } IdxRidChildListPtr; 275 276 typedef struct 277 { 278 uint64_t type : 279 IDX_TYPE_SIZE; /** @brief entry type 0 or 6 */ 280 uint64_t spare : 5; 281 uint64_t count : 282 RID_COUNT_SIZE; /** the count of rids on the current blk */ 283 uint64_t nextLbid : 284 FBO_SIZE; /** @brief file block offset */ 285 uint64_t curLevel : 286 TOTAL_CUR_LEVEL; 287 } IdxRidNextListPtr; 288 289 typedef struct 290 { 291 uint64_t type : 292 IDX_TYPE_SIZE; /** @brief entry type 6*/ 293 uint64_t spare : 3; /** @brief spare bits */ 294 uint64_t curLevelPos : 295 CUR_LEVEL_POS_WIDTH; 296 uint64_t curBlkPos : 297 CUR_BLK_POS_WIDTH; /** the position of current blk */ 298 uint64_t parentLbid : 299 FBO_SIZE; /** @brief file block offset */ 300 } IdxRidParentListPtr; 301 302 typedef struct 303 { 304 IdxRidChildListPtr childIdxRidListPtr[4]; 305 IdxRidParentListPtr parentIdxListPtr; 306 IdxRidNextListPtr nextIdxListPtr; 307 } IdxRidListArrayPtr; 308 309 /************************************************************************ 310 * @brief index list header defintions 311 ************************************************************************/ 312 typedef struct 313 { 314 uint64_t type : 315 IDX_TYPE_SIZE; /** @brief entry type */ 316 uint64_t spare : 15; /** @brief spare bits */ 317 uint64_t size : 318 RID_SIZE; /** @brief size */ 319 } IdxRidListHdrSize; 320 321 typedef struct 322 { 323 uint64_t type : 324 IDX_TYPE_SIZE; /** @brief entry type */ 325 uint64_t spare : 15; /** @brief spare bits */ 326 uint64_t llp : 327 RID_SIZE; /** @brief size */ 328 } IdxRidListHdrPtr; 329 330 typedef struct 331 { 332 IdxRidListHdrSize idxRidListSize; 333 uint64_t key; 334 IdxRidListEntry firstIdxRidListEntry; 335 IdxRidListHdrPtr nextIdxRidListPtr; 336 } IdxRidListHdr; 337 338 typedef struct 339 { 340 uint64_t part1 : 15; /** @brief entry type */ 341 uint64_t part2 : 15; /** @brief spare bits */ 342 uint64_t spare : 34; /** @brief size */ 343 } IdxRidListOffSet; 344 /************************************************************************ 345 * @brief index tree node defintions 346 ************************************************************************/ 347 typedef struct 348 { 349 IdxBitTestEntry next; /** @brief next in the node */ 350 IdxBitTestEntry current; /** @brief current addr */ 351 uint16_t level; /** @brief tree level */ 352 uint16_t allocCount; /** @brief allocated entry cound from free mgr */ 353 uint16_t useCount; /** @brief actual use entry count */ 354 uint16_t offset; /** @brief entry offset */ 355 bool used; /** @brief used flag */ 356 } IdxTreeNode; /** @brief Index tree node */ 357 358 typedef struct 359 { 360 IdxTreeNode node[IDX_MAX_TREE_LEVEL]; /** @brief node array */ 361 uint16_t maxLevel; /** @brief max level */ 362 RID rid; /** @brief current row id */ 363 uint64_t key; /** @brief current key */ 364 uint16_t width; /** @brief current width */ 365 } IdxTree; /** @brief Index tree */ 366 367 struct IdxTreeCacheNode 368 { 369 RID rid; /** @brief RID */ 370 uint64_t key; /** @brief Key */ 371 IdxEmptyListEntry entry; /** @brief List pointer */ 372 bool used; /** @brief Used flag */ IdxTreeCacheNodeIdxTreeCacheNode373 IdxTreeCacheNode() 374 { 375 used = false; 376 } 377 }; 378 379 struct IdxMultiColKey 380 { 381 std::bitset<IDX_MAX_MULTI_COL_BIT> bitSet; /** @brief BitArray for all bits */ 382 std::bitset<IDX_MAX_MULTI_COL_BIT> curBitset;/** @brief Current working column */ 383 std::bitset<IDX_MAX_MULTI_COL_BIT> curMask; /** @brief Current bitset mask */ 384 unsigned char keyBuf[IDX_MAX_MULTI_COL_BIT / 8]; /** @brief Key buffer */ 385 int curLevel; /** @brief Current index level */ 386 int maxLevel; /** @brief Maximum index level */ 387 int totalBit; /** @brief Total bits */ 388 int testbitArray[IDX_MAX_MULTI_COL_IDX_LEVEL]; /** @brief Test bit array */ clearIdxMultiColKey389 void clear() 390 { 391 bitSet.reset(); 392 curBitset.reset(); 393 curMask.reset(); 394 curLevel = maxLevel = 0; 395 totalBit = 0; 396 memset( testbitArray, 0, IDX_MAX_MULTI_COL_IDX_LEVEL * sizeof(testbitArray[0])); 397 memset( keyBuf, 0, IDX_MAX_MULTI_COL_BIT / 8 ); 398 curMask = 0x1F; 399 curMask = curMask << (IDX_MAX_MULTI_COL_BIT - 5); 400 } IdxMultiColKeyIdxMultiColKey401 IdxMultiColKey() 402 { 403 clear(); 404 } 405 }; 406 struct IdxMultiRid 407 { 408 RID* ridArray; /** @brief RID array */ 409 int totalRid; /** @brief Total number of row id */ IdxMultiRidIdxMultiRid410 IdxMultiRid() 411 { 412 totalRid = 0; 413 ridArray = NULL; 414 } setMultiRidIdxMultiRid415 void setMultiRid( RID* rids, const int size ) 416 { 417 totalRid = size; 418 ridArray = rids; 419 /* ridArray = new RID[size]; 420 memcpy( ridArray, rids, size * sizeof( RID ) ); */ 421 } clearMultiRidIdxMultiRid422 void clearMultiRid() { /*if( ridArray != NULL ) delete [] ridArray; ridArray = NULL;*/ } // we don't want to get into this mem business 423 }; 424 425 struct IdxLoadParam 426 { 427 File sourceFile; /** @brief Source file contatin values */ 428 429 OID indexTreeOid; /** @brief Target index tree oid */ 430 OID indexListOid; /** @brief Target index list oid */ 431 execplan::CalpontSystemCatalog::ColDataType indexColDataType; /** @brief Target index column type */ 432 int indexWidth; /** @brief Target index width */ 433 434 int maxLoadRow; /** @brief Max rows for one load */ 435 setIdxLoadParamIdxLoadParam436 void setIdxLoadParam( const OID treeOid, const OID listOid, const execplan::CalpontSystemCatalog::ColDataType colDataType, const int width, const int maxRow ) 437 { 438 indexTreeOid = treeOid; 439 indexListOid = listOid; 440 indexColDataType = colDataType; 441 indexWidth = width; 442 maxLoadRow = maxRow; 443 } isValidIdxLoadParam444 bool isValid() 445 { 446 return indexTreeOid && indexListOid && indexWidth && maxLoadRow; 447 } IdxLoadParamIdxLoadParam448 IdxLoadParam() 449 { 450 indexTreeOid = indexListOid = indexWidth = maxLoadRow = 0; 451 } 452 }; 453 454 } //end of namespace 455 #endif // _WE_INDEX_H_ 456