MySQL 9.0.0
Source Code Documentation
gis0type.h
Go to the documentation of this file.
1/*****************************************************************************
2
3Copyright (c) 2014, 2024, Oracle and/or its affiliates.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License, version 2.0, as published by the
7Free Software Foundation.
8
9This program is designed to work with certain software (including
10but not limited to OpenSSL) that is licensed under separate terms,
11as designated in a particular file or component or in included license
12documentation. The authors of MySQL hereby grant you an additional
13permission to link the program and your derivative works with the
14separately licensed software that they have either included with
15the program or referenced in the documentation.
16
17This program is distributed in the hope that it will be useful, but WITHOUT
18ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
19FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
20for more details.
21
22You should have received a copy of the GNU General Public License along with
23this program; if not, write to the Free Software Foundation, Inc.,
2451 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
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 "gis0geo.h"
44#include "hash0hash.h"
45#include "mem0mem.h"
46#include "que0types.h"
47#include "rem0types.h"
48#include "row0types.h"
49#include "trx0types.h"
50#include "ut0new.h"
51#include "ut0vec.h"
52#include "ut0wqueue.h"
53
54#include <list>
55#include <vector>
56
57/* Node Sequence Number. Only updated when page splits */
58typedef uint32_t node_seq_t;
59
60/* RTree internal non-leaf Nodes to be searched, from root to leaf */
61typedef struct node_visit {
62 page_no_t 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 page_no_t 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 */
74
75typedef std::vector<node_visit_t, ut::allocator<node_visit_t>> rtr_node_path_t;
76
77typedef struct rtr_rec {
78 rec_t *r_rec; /*!< matched record */
79 bool locked; /*!< whether the record locked */
81
82typedef std::vector<rtr_rec_t, ut::allocator<rtr_rec_t>> rtr_rec_vector;
83
84/* Structure for matched records on the leaf page */
85typedef struct matched_rec {
86 byte *bufp; /*!< aligned buffer point */
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 */
99
100/* Maximum index level for R-Tree, this is consistent with BTR_MAX_LEVELS */
101constexpr uint32_t RTR_MAX_LEVELS = 100;
102
103/* Number of pages we latch at leaf level when there is possible Tree
104modification (split, shrink), we always latch left, current
105and right pages */
106constexpr uint32_t RTR_LEAF_LATCH_NUM = 3;
107
108/** Vectors holding the matching internal pages/nodes and leaf records */
109typedef struct rtr_info {
110 rtr_node_path_t *path; /*!< vector holding matching pages */
112 /*!< vector holding parent pages during
113 search */
114 matched_rec_t *matches; /*!< struct holding matching leaf records */
115 ib_mutex_t rtr_path_mutex;
116 /*!< mutex protect the "path" vector */
118 /*!< tracking pages that would be locked
119 at leaf level, for future free */
121 /*!< savepoint used to release latches/blocks
122 on each level and leaf level */
123 rtr_mbr_t mbr; /*!< the search MBR */
124 que_thr_t *thr; /*!< the search thread */
125 mem_heap_t *heap; /*!< memory heap */
126 btr_cur_t *cursor; /*!< cursor used for search */
127 dict_index_t *index; /*!< index it is searching */
129 /*!< whether we will need predicate lock
130 the tree */
132 /*!< whether we will need predicate page lock
133 the tree */
134 bool allocated; /*!< whether this structure is allocate or
135 on stack */
136 bool mbr_adj; /*!< whether mbr will need to be enlarged
137 for an insertion operation */
138 bool fd_del; /*!< found deleted row */
140 /*!< search tuple being used */
142 /*!< current search mode */
143
144 /* TODO: This is for a temporary fix, will be removed later */
145 bool *is_dup;
146 /*!< whether the current rec is a duplicate record. */
148
149typedef std::list<rtr_info_t *, ut::allocator<rtr_info_t *>> rtr_info_active;
150
151/* Tracking structure for all onoging search for an index */
152typedef struct rtr_info_track {
153 rtr_info_active *rtr_active; /*!< Active search info */
155 /*!< mutex to protect
156 rtr_active */
158
159/* Node Sequence Number and mutex protects it. */
160typedef struct rtree_ssn {
161 ib_mutex_t mutex; /*!< mutex protect the seq num */
162 node_seq_t seq_no; /*!< the SSN (node sequence number) */
164
165/* This is to record the record movement between pages. Used for corresponding
166lock movement */
167typedef struct rtr_rec_move {
168 rec_t *old_rec; /*!< record being moved in old page */
169 rec_t *new_rec; /*!< new record location */
170 bool moved; /*!< whether lock are moved too */
172#endif /*!< gis0rtree.h */
uint32_t page_no_t
Page number.
Definition: api0api.h:45
The database buffer pool high-level routines.
Data types.
Some type definitions.
Data dictionary global types.
The r-tree define from MyISAM.
struct matched_rec matched_rec_t
std::list< rtr_info_t *, ut::allocator< rtr_info_t * > > rtr_info_active
Definition: gis0type.h:149
struct rtr_info_track rtr_info_track_t
struct rtr_rec_move rtr_rec_move_t
gis0rtree.h
constexpr uint32_t RTR_LEAF_LATCH_NUM
Definition: gis0type.h:106
std::vector< rtr_rec_t, ut::allocator< rtr_rec_t > > rtr_rec_vector
Definition: gis0type.h:82
constexpr uint32_t RTR_MAX_LEVELS
Definition: gis0type.h:101
std::vector< node_visit_t, ut::allocator< node_visit_t > > rtr_node_path_t
Definition: gis0type.h:75
struct rtree_ssn rtr_ssn_t
struct rtr_rec rtr_rec_t
struct node_visit node_visit_t
uint32_t node_seq_t
Definition: gis0type.h:58
struct rtr_info rtr_info_t
Vectors holding the matching internal pages/nodes and leaf records.
The simple hash table utility.
The memory management.
page_cur_mode_t
Definition: page0types.h:176
Query graph global types.
Record manager global types.
byte rec_t
Definition: rem0types.h:41
Row operation global types.
The tree cursor: the definition appears here only for the compiler to know struct size!
Definition: btr0cur.h:668
Definition: btr0pcur.h:99
The buffer control block structure.
Definition: buf0buf.h:1747
Data structure for an index.
Definition: dict0mem.h:1046
Structure for an SQL data tuple of fields (logical record)
Definition: data0data.h:684
Definition: gis0type.h:85
byte rec_buf[UNIV_PAGE_SIZE_MAX *2]
buffer used to copy matching rec
Definition: gis0type.h:87
bool valid
whether result in matched_recs or this search is valid (page not dropped)
Definition: gis0type.h:94
byte * bufp
aligned buffer point
Definition: gis0type.h:86
rtr_rec_vector * matched_recs
vector holding the matching rec
Definition: gis0type.h:91
ib_mutex_t rtr_match_mutex
mutex protect the match_recs vector
Definition: gis0type.h:92
bool locked
whether these recs locked
Definition: gis0type.h:97
buf_block_t block
the shadow buffer block
Definition: gis0type.h:89
ulint used
memory used
Definition: gis0type.h:90
The info structure stored at the beginning of a heap block.
Definition: mem0mem.h:302
Definition: gis0type.h:61
double mbr_inc
whether this node needs to be enlarged for insertion
Definition: gis0type.h:71
page_no_t child_no
child page num if for parent recording
Definition: gis0type.h:65
btr_pcur_t * cursor
cursor structure if we positioned FIXME: there is no need to use whole btr_pcur_t,...
Definition: gis0type.h:67
page_no_t page_no
the page number
Definition: gis0type.h:62
node_seq_t seq_no
the SSN (split sequence number
Definition: gis0type.h:63
ulint level
the page's index level
Definition: gis0type.h:64
Definition: que0que.h:242
Definition: gis0type.h:152
rtr_info_active * rtr_active
Active search info.
Definition: gis0type.h:153
ib_mutex_t rtr_active_mutex
mutex to protect rtr_active
Definition: gis0type.h:154
Vectors holding the matching internal pages/nodes and leaf records.
Definition: gis0type.h:109
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:120
rtr_mbr_t mbr
the search MBR
Definition: gis0type.h:123
bool mbr_adj
whether mbr will need to be enlarged for an insertion operation
Definition: gis0type.h:136
page_cur_mode_t search_mode
current search mode
Definition: gis0type.h:141
dict_index_t * index
index it is searching
Definition: gis0type.h:127
const dtuple_t * search_tuple
search tuple being used
Definition: gis0type.h:139
bool fd_del
found deleted row
Definition: gis0type.h:138
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:117
matched_rec_t * matches
struct holding matching leaf records
Definition: gis0type.h:114
rtr_node_path_t * parent_path
vector holding parent pages during search
Definition: gis0type.h:111
bool need_page_lock
whether we will need predicate page lock the tree
Definition: gis0type.h:131
rtr_node_path_t * path
vector holding matching pages
Definition: gis0type.h:110
que_thr_t * thr
the search thread
Definition: gis0type.h:124
ib_mutex_t rtr_path_mutex
mutex protect the "path" vector
Definition: gis0type.h:115
bool allocated
whether this structure is allocate or on stack
Definition: gis0type.h:134
btr_cur_t * cursor
cursor used for search
Definition: gis0type.h:126
bool * is_dup
whether the current rec is a duplicate record.
Definition: gis0type.h:145
mem_heap_t * heap
memory heap
Definition: gis0type.h:125
bool need_prdt_lock
whether we will need predicate lock the tree
Definition: gis0type.h:128
In memory representation of a minimum bounding rectangle.
Definition: rtree_support.h:40
Definition: gis0type.h:167
rec_t * new_rec
new record location
Definition: gis0type.h:169
bool moved
whether lock are moved too
Definition: gis0type.h:170
rec_t * old_rec
record being moved in old page
Definition: gis0type.h:168
Definition: gis0type.h:77
bool locked
whether the record locked
Definition: gis0type.h:79
rec_t * r_rec
matched record
Definition: gis0type.h:78
Definition: gis0type.h:160
node_seq_t seq_no
the SSN (node sequence number)
Definition: gis0type.h:162
ib_mutex_t mutex
mutex protect the seq num
Definition: gis0type.h:161
Transaction system global type definitions.
Version control for database, common definitions, and include files.
unsigned long int ulint
Definition: univ.i:406
constexpr size_t UNIV_PAGE_SIZE_MAX
Maximum page size InnoDB currently supports.
Definition: univ.i:323
Dynamic memory allocation routines and custom allocators specifically crafted to support memory instr...
A vector of pointers to data items.
A work queue.