MySQL 8.1.0
Source Code Documentation
gis0type.h
Go to the documentation of this file.
1/*****************************************************************************
2
3Copyright (c) 2014, 2023, 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 also distributed with certain software (including but not
10limited to OpenSSL) that is licensed under separate terms, as designated in a
11particular file or component or in included license documentation. The authors
12of MySQL hereby grant you an additional permission to link the program and
13your derivative works with the separately licensed software that they have
14included with MySQL.
15
16This program is distributed in the hope that it will be useful, but WITHOUT
17ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
19for more details.
20
21You should have received a copy of the GNU General Public License along with
22this program; if not, write to the Free Software Foundation, Inc.,
2351 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 */
57typedef uint32_t node_seq_t;
58
59/* RTree internal non-leaf Nodes to be searched, from root to leaf */
60typedef 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 */
73
74typedef std::vector<node_visit_t, ut::allocator<node_visit_t>> rtr_node_path_t;
75
76typedef struct rtr_rec {
77 rec_t *r_rec; /*!< matched record */
78 bool locked; /*!< whether the record locked */
80
81typedef std::vector<rtr_rec_t, ut::allocator<rtr_rec_t>> rtr_rec_vector;
82
83/* Structure for matched records on the leaf page */
84typedef struct matched_rec {
85 byte *bufp; /*!< aligned buffer point */
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 */
100constexpr uint32_t RTR_MAX_LEVELS = 100;
101
102/* Number of pages we latch at leaf level when there is possible Tree
103modification (split, shrink), we always latch left, current
104and right pages */
105constexpr uint32_t RTR_LEAF_LATCH_NUM = 3;
106
107/** Vectors holding the matching internal pages/nodes and leaf records */
108typedef 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. */
147
148typedef std::list<rtr_info_t *, ut::allocator<rtr_info_t *>> rtr_info_active;
149
150/* Tracking structure for all onoging search for an index */
151typedef struct rtr_info_track {
152 rtr_info_active *rtr_active; /*!< Active search info */
154 /*!< mutex to protect
155 rtr_active */
157
158/* Node Sequence Number and mutex protects it. */
159typedef struct rtree_ssn {
160 ib_mutex_t mutex; /*!< mutex protect the seq num */
161 node_seq_t seq_no; /*!< the SSN (node sequence number) */
163
164/* This is to record the record movement between pages. Used for corresponding
165lock movement */
166typedef 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 */
uint32_t page_no_t
Page number.
Definition: api0api.h:48
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:148
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:105
std::vector< rtr_rec_t, ut::allocator< rtr_rec_t > > rtr_rec_vector
Definition: gis0type.h:81
constexpr uint32_t RTR_MAX_LEVELS
Definition: gis0type.h:100
std::vector< node_visit_t, ut::allocator< node_visit_t > > rtr_node_path_t
Definition: gis0type.h:74
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:57
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:175
Query graph global types.
Record manager global types.
byte rec_t
Definition: rem0types.h:40
Row operation global types.
The tree cursor: the definition appears here only for the compiler to know struct size!
Definition: btr0cur.h:667
Definition: btr0pcur.h:98
The buffer control block structure.
Definition: buf0buf.h:1689
Data structure for an index.
Definition: dict0mem.h:1045
Structure for an SQL data tuple of fields (logical record)
Definition: data0data.h:681
Definition: gis0type.h:84
byte rec_buf[UNIV_PAGE_SIZE_MAX *2]
buffer used to copy matching rec
Definition: gis0type.h:86
bool valid
whether result in matched_recs or this search is valid (page not dropped)
Definition: gis0type.h:93
byte * bufp
aligned buffer point
Definition: gis0type.h:85
rtr_rec_vector * matched_recs
vector holding the matching rec
Definition: gis0type.h:90
ib_mutex_t rtr_match_mutex
mutex protect the match_recs vector
Definition: gis0type.h:91
bool locked
whether these recs locked
Definition: gis0type.h:96
buf_block_t block
the shadow buffer block
Definition: gis0type.h:88
ulint used
memory used
Definition: gis0type.h:89
The info structure stored at the beginning of a heap block.
Definition: mem0mem.h:301
Definition: gis0type.h:60
double mbr_inc
whether this node needs to be enlarged for insertion
Definition: gis0type.h:70
page_no_t child_no
child page num if for parent recording
Definition: gis0type.h:64
btr_pcur_t * cursor
cursor structure if we positioned FIXME: there is no need to use whole btr_pcur_t,...
Definition: gis0type.h:66
page_no_t page_no
the page number
Definition: gis0type.h:61
node_seq_t seq_no
the SSN (split sequence number
Definition: gis0type.h:62
ulint level
the page's index level
Definition: gis0type.h:63
Definition: que0que.h:241
Definition: gis0type.h:151
rtr_info_active * rtr_active
Active search info.
Definition: gis0type.h:152
ib_mutex_t rtr_active_mutex
mutex to protect rtr_active
Definition: gis0type.h:153
Vectors holding the matching internal pages/nodes and leaf records.
Definition: gis0type.h:108
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_mbr_t mbr
the search MBR
Definition: gis0type.h:122
bool mbr_adj
whether mbr will need to be enlarged for an insertion operation
Definition: gis0type.h:135
page_cur_mode_t search_mode
current search mode
Definition: gis0type.h:140
dict_index_t * index
index it is searching
Definition: gis0type.h:126
const dtuple_t * search_tuple
search tuple being used
Definition: gis0type.h:138
bool fd_del
found deleted row
Definition: gis0type.h:137
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
matched_rec_t * matches
struct holding matching leaf records
Definition: gis0type.h:113
rtr_node_path_t * parent_path
vector holding parent pages during search
Definition: gis0type.h:110
bool need_page_lock
whether we will need predicate page lock the tree
Definition: gis0type.h:130
rtr_node_path_t * path
vector holding matching pages
Definition: gis0type.h:109
que_thr_t * thr
the search thread
Definition: gis0type.h:123
ib_mutex_t rtr_path_mutex
mutex protect the "path" vector
Definition: gis0type.h:114
bool allocated
whether this structure is allocate or on stack
Definition: gis0type.h:133
btr_cur_t * cursor
cursor used for search
Definition: gis0type.h:125
bool * is_dup
whether the current rec is a duplicate record.
Definition: gis0type.h:144
mem_heap_t * heap
memory heap
Definition: gis0type.h:124
bool need_prdt_lock
whether we will need predicate lock the tree
Definition: gis0type.h:127
In memory representation of a minimum bounding rectangle.
Definition: rtree_support.h:39
Definition: gis0type.h:166
rec_t * new_rec
new record location
Definition: gis0type.h:168
bool moved
whether lock are moved too
Definition: gis0type.h:169
rec_t * old_rec
record being moved in old page
Definition: gis0type.h:167
Definition: gis0type.h:76
bool locked
whether the record locked
Definition: gis0type.h:78
rec_t * r_rec
matched record
Definition: gis0type.h:77
Definition: gis0type.h:159
node_seq_t seq_no
the SSN (node sequence number)
Definition: gis0type.h:161
ib_mutex_t mutex
mutex protect the seq num
Definition: gis0type.h:160
Transaction system global type definitions.
Version control for database, common definitions, and include files.
unsigned long int ulint
Definition: univ.i:405
constexpr size_t UNIV_PAGE_SIZE_MAX
Maximum page size InnoDB currently supports.
Definition: univ.i:322
Dynamic memory allocation routines and custom allocators specifically crafted to support memory instr...
A vector of pointers to data items.
A work queue.