1 /***************************************************************************** 2 3 Copyright (c) 2014, 2021, Oracle and/or its affiliates. 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License, version 2.0, 7 as published by the Free Software Foundation. 8 9 This program is also distributed with certain software (including 10 but not limited to OpenSSL) that is licensed under separate terms, 11 as designated in a particular file or component or in included license 12 documentation. The authors of MySQL hereby grant you an additional 13 permission to link the program and your derivative works with the 14 separately licensed software that they have included with MySQL. 15 16 This program is distributed in the hope that it will be useful, 17 but WITHOUT ANY WARRANTY; without even the implied warranty of 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19 GNU General Public License, version 2.0, for more details. 20 21 You should have received a copy of the GNU General Public License along with 22 this program; if not, write to the Free Software Foundation, Inc., 23 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA 24 25 *****************************************************************************/ 26 27 /******************************************************************//** 28 @file include gis0type.h 29 R-tree header file 30 31 Created 2013/03/27 Jimmy Yang 32 ***********************************************************************/ 33 34 #ifndef gis0type_h 35 #define gis0type_h 36 37 #include "univ.i" 38 39 #include "buf0buf.h" 40 #include "data0type.h" 41 #include "data0types.h" 42 #include "dict0types.h" 43 #include "hash0hash.h" 44 #include "mem0mem.h" 45 #include "rem0types.h" 46 #include "row0types.h" 47 #include "trx0types.h" 48 #include "ut0vec.h" 49 #include "ut0wqueue.h" 50 #include "que0types.h" 51 #include "gis0geo.h" 52 #include "ut0new.h" 53 54 #include <vector> 55 #include <list> 56 57 /* Node Sequence Number. Only updated when page splits */ 58 typedef ib_uint32_t node_seq_t; 59 60 /* RTree internal non-leaf Nodes to be searched, from root to leaf */ 61 typedef struct node_visit { 62 ulint page_no; /*!< the page number */ 63 node_seq_t seq_no; /*!< the SSN (split sequence number */ 64 ulint level; /*!< the page's index level */ 65 ulint child_no; /*!< child page num if for parent 66 recording */ 67 btr_pcur_t* cursor; /*!< cursor structure if we positioned 68 FIXME: there is no need to use whole 69 btr_pcur_t, just the position related 70 members */ 71 double mbr_inc; /*!< whether this node needs to be 72 enlarged for insertion */ 73 } node_visit_t; 74 75 typedef std::vector<node_visit_t, ut_allocator<node_visit_t> > rtr_node_path_t; 76 77 typedef struct rtr_rec { 78 rec_t* r_rec; /*!< matched record */ 79 bool locked; /*!< whether the record locked */ 80 } rtr_rec_t; 81 82 typedef std::vector<rtr_rec_t, ut_allocator<rtr_rec_t> > rtr_rec_vector; 83 84 /* Structure for matched records on the leaf page */ 85 typedef struct matched_rec { 86 byte* bufp; /*!< aligned buffer point */ 87 byte rec_buf[UNIV_PAGE_SIZE_MAX * 2]; 88 /*!< buffer used to copy matching rec */ 89 buf_block_t block; /*!< the shadow buffer block */ 90 ulint used; /*!< memory used */ 91 rtr_rec_vector* matched_recs; /*!< vector holding the matching rec */ 92 ib_mutex_t rtr_match_mutex;/*!< mutex protect the match_recs 93 vector */ 94 bool valid; /*!< whether result in matched_recs 95 or this search is valid (page not 96 dropped) */ 97 bool locked; /*!< whether these recs locked */ 98 } matched_rec_t; 99 100 /* In memory representation of a minimum bounding rectangle */ 101 typedef struct rtr_mbr { 102 double xmin; /*!< minimum on x */ 103 double xmax; /*!< maximum on x */ 104 double ymin; /*!< minimum on y */ 105 double ymax; /*!< maximum on y */ 106 } rtr_mbr_t; 107 108 /* Maximum index level for R-Tree, this is consistent with BTR_MAX_LEVELS */ 109 #define RTR_MAX_LEVELS 100 110 111 /* Number of pages we latch at leaf level when there is possible Tree 112 modification (split, shrink), we always latch left, current 113 and right pages */ 114 #define RTR_LEAF_LATCH_NUM 3 115 116 /** Vectors holding the matching internal pages/nodes and leaf records */ 117 typedef struct rtr_info{ 118 rtr_node_path_t*path; /*!< vector holding matching pages */ 119 rtr_node_path_t*parent_path; 120 /*!< vector holding parent pages during 121 search */ 122 matched_rec_t* matches;/*!< struct holding matching leaf records */ 123 ib_mutex_t rtr_path_mutex; 124 /*!< mutex protect the "path" vector */ 125 buf_block_t* tree_blocks[RTR_MAX_LEVELS + RTR_LEAF_LATCH_NUM]; 126 /*!< tracking pages that would be locked 127 at leaf level, for future free */ 128 ulint tree_savepoints[RTR_MAX_LEVELS + RTR_LEAF_LATCH_NUM]; 129 /*!< savepoint used to release latches/blocks 130 on each level and leaf level */ 131 rtr_mbr_t mbr; /*!< the search MBR */ 132 que_thr_t* thr; /*!< the search thread */ 133 mem_heap_t* heap; /*!< memory heap */ 134 btr_cur_t* cursor; /*!< cursor used for search */ 135 dict_index_t* index; /*!< index it is searching */ 136 bool need_prdt_lock; 137 /*!< whether we will need predicate lock 138 the tree */ 139 bool need_page_lock; 140 /*!< whether we will need predicate page lock 141 the tree */ 142 bool allocated;/*!< whether this structure is allocate or 143 on stack */ 144 bool mbr_adj;/*!< whether mbr will need to be enlarged 145 for an insertion operation */ 146 bool fd_del; /*!< found deleted row */ 147 const dtuple_t* search_tuple; 148 /*!< search tuple being used */ 149 page_cur_mode_t search_mode; 150 /*!< current search mode */ 151 } rtr_info_t; 152 153 typedef std::list<rtr_info_t*, ut_allocator<rtr_info_t*> > rtr_info_active; 154 155 /* Tracking structure for all onoging search for an index */ 156 typedef struct rtr_info_track { 157 rtr_info_active* rtr_active; /*!< Active search info */ 158 ib_mutex_t rtr_active_mutex; 159 /*!< mutex to protect 160 rtr_active */ 161 } rtr_info_track_t; 162 163 /* Node Sequence Number and mutex protects it. */ 164 typedef struct rtree_ssn { 165 ib_mutex_t mutex; /*!< mutex protect the seq num */ 166 node_seq_t seq_no; /*!< the SSN (node sequence number) */ 167 } rtr_ssn_t; 168 169 /* This is to record the record movement between pages. Used for corresponding 170 lock movement */ 171 typedef struct rtr_rec_move { 172 rec_t* old_rec; /*!< record being moved in old page */ 173 rec_t* new_rec; /*!< new record location */ 174 bool moved; /*!< whether lock are moved too */ 175 } rtr_rec_move_t; 176 #endif /*!< gis0rtree.h */ 177