2
* PROGRAM: JRD Access Method
4
* DESCRIPTION: Index walking data structures
6
* The contents of this file are subject to the Interbase Public
7
* License Version 1.0 (the "License"); you may not use this file
8
* except in compliance with the License. You may obtain a copy
9
* of the License at http://www.Inprise.com/IPL.html
11
* Software distributed under the License is distributed on an
12
* "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, either express
13
* or implied. See the License for the specific language governing
14
* rights and limitations under the License.
16
* The Original Code was created by Inprise Corporation
17
* and its predecessors. Portions created by Inprise Corporation are
18
* Copyright (C) Inprise Corporation.
20
* All Rights Reserved.
21
* Contributor(s): ______________________________________.
23
* 2002.10.28 Sean Leyne - Code cleanup, removed obsolete "DecOSF" port
30
#include "../jrd/constants.h"
31
#include "../common/classes/array.h"
32
#include "../jrd/jrd_blks.h"
33
#include "../include/fb_blk.h"
35
#include "../jrd/err_proto.h" /* Index error types */
36
#include "../jrd/RecordNumber.h"
37
#include "../jrd/sbm.h"
39
/* 64 turns out not to be enough indexes */
40
/* #define MAX_IDX 64 */ /* that should be plenty of indexes */
42
#define MAX_KEY_LIMIT (dbb->dbb_page_size / 4)
50
template <typename T> class vec;
61
/* Index descriptor block -- used to hold info from index root page */
64
SLONG idx_root; /* Index root */
65
float idx_selectivity; /* selectivity of index */
68
UCHAR idx_runtime_flags; /* flags used at runtime, not stored on disk */
69
USHORT idx_primary_index; /* id for primary key partner index */
70
USHORT idx_primary_relation; /* id for primary key partner relation */
71
USHORT idx_count; /* number of keys */
72
vec<int>* idx_foreign_primaries; /* ids for primary/unique indexes with partners */
73
vec<int>* idx_foreign_relations; /* ids for foreign key partner relations */
74
vec<int>* idx_foreign_indexes; /* ids for foreign key partner indexes */
75
jrd_nod* idx_expression; /* node tree for indexed expresssion */
76
dsc idx_expression_desc; /* descriptor for expression result */
77
jrd_req* idx_expression_request; /* stored request for expression evaluation */
78
// This structure should exactly match IRTD structure for current ODS
80
USHORT idx_field; /* field id */
81
USHORT idx_itype; /* data of field in index */
82
float idx_selectivity; /* segment selectivity */
83
} idx_rpt[MAX_INDEX_SEGMENTS];
86
struct IndexDescAlloc : public pool_alloc_rpt<index_desc> {
90
/* index types and flags */
92
/* See jrd/intl.h for notes on idx_itype and dsc_sub_type considerations */
93
/* idx_numeric .. idx_byte_array values are compatible with VMS values */
95
const int idx_numeric = 0;
96
const int idx_string = 1;
97
// AB: idx_timestamp1 removed
98
const int idx_byte_array = 3;
99
const int idx_metadata = 4;
100
const int idx_sql_date = 5;
101
const int idx_sql_time = 6;
102
const int idx_timestamp2 = 7;
103
const int idx_numeric2 = 8; /* Introduced for 64-bit Integer support */
105
/* idx_itype space for future expansion */
106
const int idx_first_intl_string = 64; /* .. MAX (short) Range of computed key strings */
108
const int idx_offset_intl_range = (0x7FFF + idx_first_intl_string);
110
/* these flags must match the irt_flags */
112
const int idx_unique = 1;
113
const int idx_descending = 2;
114
const int idx_in_progress = 4;
115
const int idx_foreign = 8;
116
const int idx_primary = 16;
117
const int idx_expressn = 32;
119
/* these flags are for idx_runtime_flags */
121
const int idx_plan_dont_use = 1; /* index is not mentioned in user-specified access plan */
122
const int idx_plan_navigate = 2; /* plan specifies index to be used for ordering */
123
const int idx_used = 4; /* index was in fact selected for retrieval */
124
const int idx_navigate = 8; /* index was in fact selected for navigation */
125
const int idx_plan_missing = 16; /* index mentioned in missing clause */
126
const int idx_plan_starts = 32; /* index mentioned in starts clause */
127
const int idx_used_with_and = 64; /* marker used in procedure sort_indices */
128
const int idx_marker = 128; /* marker used in procedure sort_indices */
130
/* Index insertion block -- parameter block for index insertions */
132
struct index_insertion {
133
RecordNumber iib_number; /* record number (or lower level page) */
134
SLONG iib_sibling; /* right sibling page */
135
index_desc* iib_descriptor; /* index descriptor */
136
jrd_rel* iib_relation; /* relation block */
137
temporary_key* iib_key; /* varying string for insertion */
138
RecordBitmap* iib_duplicates; /* spare bit map of duplicates */
139
jrd_tra* iib_transaction; /* insertion transaction */
143
/* these flags are for the key_flags */
145
const int key_empty = 1; /* Key contains empty data / empty string */
146
const int key_all_nulls = 2; /* All key fields are nulls */
148
/* Temporary key block */
150
struct temporary_key {
152
UCHAR key_data[MAX_KEY + 1];
154
USHORT key_null_segment; // index of first encountered null segment.
155
// Evaluated in BTR_key only and used in IDX_create_index for better
158
/* AB: I don't see the use of multiplying with 2 anymore. */
159
//UCHAR key_data[MAX_KEY * 2];
160
// This needs to be on a SHORT boundary.
161
// This is because key_data is complemented as
162
// (SSHORT *) if value is negative.
163
// See compress() (JRD/btr.cpp) for more details
167
/* Index Sort Record -- fix part of sort record for index fast load */
169
// hvlad: index_sort_record structure is stored in sort scratch file so we
170
// don't want to grow sort file with padding added by compiler to please
172
// #pragma pack is supported at least by MSVC and GCC. Don't know about
173
// other compilers, sorry
175
#pragma pack(push, 1)
176
struct index_sort_record {
177
// RecordNumber should be at the first place, because it's used
178
// for determing sort by creating index (see idx.cpp)
179
SINT64 isr_record_number;
180
USHORT isr_key_length;
185
const int ISR_secondary = 1; // Record is secondary version
186
const int ISR_null = 2; // Record consists of NULL values only
190
/* Index retrieval block -- hold stuff for index retrieval */
192
class IndexRetrieval : public pool_alloc_rpt<jrd_nod*, type_irb>
195
index_desc irb_desc; /* Index descriptor */
196
USHORT irb_index; /* Index id */
197
USHORT irb_generic; /* Flags for generic search */
198
jrd_rel* irb_relation; /* Relation for retrieval */
199
USHORT irb_lower_count; /* Number of segments for retrieval */
200
USHORT irb_upper_count; /* Number of segments for retrieval */
201
temporary_key* irb_key; /* key for equality retrieval */
202
jrd_nod* irb_value[1];
205
// Flag values for irb_generic
206
const int irb_partial = 1; /* Partial match: not all segments or starting of key only */
207
const int irb_starting = 2; /* Only compute "starting with" key for index segment */
208
const int irb_equality = 4; /* Probing index for equality match */
209
const int irb_ignore_null_value_key = 8; // if lower bound is specified and upper bound unspecified,
210
// ignore looking at null value keys
211
const int irb_descending = 16; // Base index uses descending order
212
const int irb_exclude_lower = 32; // exclude lower bound keys while scanning index
213
const int irb_exclude_upper = 64; // exclude upper bound keys while scanning index
215
// macros used to manipulate btree nodes
216
#define BTR_SIZE OFFSETA(Ods::btree_page*, btr_nodes)
218
#define NEXT_NODE(node) (btree_nod*)(node->btn_data + node->btn_length)
219
#define NEXT_NODE_RECNR(node) (btree_nod*)(node->btn_data + node->btn_length + sizeof(SLONG))
221
//#define LAST_NODE(page) (btree_nod*) ((UCHAR*) page + page->btr_length)
223
//#define NEXT_EXPANDED(xxx,yyy) (btree_exp*) ((UCHAR*) xxx->btx_data + (yyy)->btn_prefix + (yyy)->btn_length)
225
typedef Firebird::HalfStaticArray<float, 4> SelectivityList;
229
#endif /* JRD_BTR_H */
added
removed
src/jrd/btr.h
