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