1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
/*-
* Copyright (c) 2008-2014 WiredTiger, Inc.
* All rights reserved.
*
* See the file LICENSE for redistribution information.
*/
#include "wt_internal.h"
/*
* __wt_col_search --
* Search a column-store tree for a specific record-based key.
*/
int
__wt_col_search(WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt)
{
WT_BTREE *btree;
WT_COL *cip;
WT_INSERT *ins;
WT_INSERT_HEAD *ins_head;
WT_PAGE *page;
WT_REF *ref;
uint64_t recno;
uint32_t base, indx, limit;
int depth;
__cursor_search_clear(cbt);
recno = cbt->iface.recno;
btree = S2BT(session);
ref = NULL;
/* Search the internal pages of the tree. */
for (depth = 2,
page = btree->root_page; page->type == WT_PAGE_COL_INT; ++depth) {
WT_ASSERT(session, ref == NULL ||
ref->key.recno == page->u.intl.recno);
/* Fast path appends. */
base = page->entries;
ref = &page->u.intl.t[base - 1];
if (recno >= ref->key.recno)
goto descend;
/* Binary search of internal pages. */
for (base = 0, ref = NULL,
limit = page->entries - 1; limit != 0; limit >>= 1) {
indx = base + (limit >> 1);
ref = page->u.intl.t + indx;
if (recno == ref->key.recno)
break;
if (recno < ref->key.recno)
continue;
base = indx + 1;
--limit;
}
descend: WT_ASSERT(session, ref != NULL);
/*
* Reference the slot used for next step down the tree.
*
* Base is the smallest index greater than recno and may be the
* (last + 1) index. The slot for descent is the one before
* base.
*/
if (recno != ref->key.recno) {
/*
* We don't have to correct for base == 0 because the
* only way for base to be 0 is if recno is the page's
* starting recno.
*/
WT_ASSERT(session, base > 0);
ref = page->u.intl.t + (base - 1);
}
/*
* Swap the parent page for the child page; return on error,
* the swap function ensures we're holding nothing on failure.
*/
WT_RET(__wt_page_swap(session, page, page, ref, 0));
page = ref->page;
}
/*
* We want to know how deep the tree gets because excessive depth can
* happen because of how WiredTiger splits.
*/
if (depth > btree->maximum_depth)
btree->maximum_depth = depth;
cbt->page = page;
cbt->recno = recno;
cbt->compare = 0;
/*
* Search the leaf page. We do not check in the search path for a
* record greater than the maximum record in the tree; in that case,
* we arrive here with a record that's impossibly large for the page.
*/
if (page->type == WT_PAGE_COL_FIX) {
if (recno >= page->u.col_fix.recno + page->entries) {
cbt->recno = page->u.col_fix.recno + page->entries;
goto past_end;
} else
ins_head = WT_COL_UPDATE_SINGLE(page);
} else
if ((cip = __col_var_search(page, recno)) == NULL) {
cbt->recno = __col_last_recno(page);
goto past_end;
} else {
cbt->slot = WT_COL_SLOT(page, cip);
ins_head = WT_COL_UPDATE_SLOT(page, cbt->slot);
}
/*
* We have a match on the page, check for an update. Check the page's
* update list (fixed-length), or slot's update list (variable-length)
* for a better match. The only better match we can find is an exact
* match, otherwise the existing match on the page is the one we want.
* For that reason, don't set the cursor's WT_INSERT_HEAD/WT_INSERT pair
* until we know we have a useful entry.
*/
if ((ins = __col_insert_search(
ins_head, cbt->ins_stack, cbt->next_stack, recno)) != NULL)
if (recno == WT_INSERT_RECNO(ins)) {
cbt->ins_head = ins_head;
cbt->ins = ins;
}
return (0);
past_end:
/*
* A record past the end of the page's standard information. Check the
* append list; by definition, any record on the append list is closer
* than the last record on the page, so it's a better choice for return.
* This is a rarely used path: we normally find exact matches, because
* column-store files are dense, but in this case the caller searched
* past the end of the table.
*
* Don't bother searching if the caller is appending a new record where
* we'll allocate the record number; we're not going to find a match by
* definition, and we figure out the position when we do the work.
*/
cbt->ins_head = WT_COL_APPEND(page);
if (recno == UINT64_MAX)
cbt->ins = NULL;
else
cbt->ins = __col_insert_search(
cbt->ins_head, cbt->ins_stack, cbt->next_stack, recno);
if (cbt->ins == NULL)
cbt->compare = -1;
else {
cbt->recno = WT_INSERT_RECNO(cbt->ins);
if (recno == cbt->recno)
cbt->compare = 0;
else if (recno < cbt->recno)
cbt->compare = 1;
else
cbt->compare = -1;
}
/*
* Note if the record is past the maximum record in the tree, the cursor
* search functions need to know for fixed-length column-stores because
* appended records implicitly create any skipped records, and cursor
* search functions have to handle that case.
*/
if (cbt->compare == -1)
F_SET(cbt, WT_CBT_MAX_RECORD);
return (0);
}
|
