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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
|
This file describes how MySQL index navigation commands are translated into
RocksDB index navigation commands.
Index tuples are shown as
( kv )-aaa-pkN
here
* '(kv)' is the 4-byte index number.
* '-' is just for readability
* everything that follows the '-' is mem-comparable form of the key.
In ascii encoding, aaa < bbb < ccc < xxx.
Tuples that start with '#' do not exist in the database. They are only shown
to demonstrate where Seek() calls end up with.
== HA_READ_KEY_EXACT, forward CF ==
(kv-1)-xxx-pk
# ( kv )-aaa <-- "kv-aaa" doesn't exist in the database, but it would be
here.
( kv )-aaa-pk <--- Seek("kv-aaa") will put us here on the next record.
( kv )-aaa-pk2
( kv )-bbb-...
RocksDB calls:
it->Seek(kv);
if (it->Valid() && kd->covers_key(..) && kd->cmp_full_keys(...))
return record.
== HA_READ_KEY_EXACT, backward CF ==
When we need to seek to a tuple that is a prefix of a full key:
(kv+1)-xxx-pk
( kv )-ccc-pk
( kv )-bbb-pk3
( kv )-bbb-pk2
( kv )-bbb-pk1 <--- SeekForPrev("kv-bbb") will put us here on the previous
record.
# ( kv )-bbb <--- "kv-bbb" doesn't exist in the database, but it would be
( kv )-aaa-pk here.
Even when (kv)-bbb-pk1 is the last record in the CF, SeekForPrev() will find the
last record before "kv-bbb", so it already takes care of this case for us.
RocksDB calls:
it->SeekForPrev(kv);
if (it->Valid() && kd->covers_key(..) && kd->cmp_full_keys(...))
return record.
== HA_READ_KEY_OR_NEXT, forward CF ==
This is finding min(key) such that key >= lookup_tuple.
If lookup tuple is kv-bbb:
( kv )-aaa-pk
# ( kv )-bbb <-- "kv-bbb" doesn't exist in the database, but it would be
here.
( kv )-bbb-pk1 <--- Seek("kv-bbb") will put us here on the next record.
( kv )-bbb-pk2
( kv )-bbb-...
RocksDB calls:
Seek(kv);
if (it->Valid() && kd->covers_key(..))
return record.
== HA_READ_KEY_OR_NEXT, backward CF ==
When specified key tuple is a key prefix:
(kv+1)-xxx-pk
( kv )-ccc-pk
( kv )-bbb-pk3
( kv )-bbb-pk2
( kv )-bbb-pk1 <--- Seek("kv-bbb") will put us here on the previous record.
# ( kv )-bbb <--- "kv-bbb" doesn't exist in the database, but it would be
here.
( kv )-aaa-pk
Even when (kv)-bbb-pk1 is the last record in the CF, SeekForPrev() will find the
last record before "kv-bbb", so it already takes care of this case for us.
Another kind of special case is when we need to seek to the full value.
Suppose, the lookup tuple is kv-bbb-pk1:
(kv+1)-xxx-pk
( kv )-ccc-pk
( kv )-bbb-pk3
( kv )-bbb-pk2
( kv )-bbb-pk1 < -- SeekForPrev(kv-bbb-pk1)
( kv )-bbb-pk0
Then, SeekForPrev(kv-bbb-pk1) may position us exactly at the tuple we need.
Even If kv-bbb-pk1 is not present in the database, we will be positioned on
kv-bbb-pk2 no matter whether kv-bbb-pk2 is the last key or not.
RocksDB calls:
SeekForPrev(...);
if (it->Valid() && kd->covers_key(..))
return record.
== HA_READ_AFTER_KEY, forward CF ==
This is finding min(key) such that key > lookup_key.
Suppose lookup_key = kv-bbb
( kv )-aaa-pk
# ( kv )-bbb
( kv )-bbb-pk1 <--- Seek("kv-bbb") will put us here. We need to
( kv )-bbb-pk2 get to the value that is next after 'bbb'.
( kv )-bbb-pk3
( kv )-bbb-pk4
( kv )-bbb-pk5
( kv )-ccc-pkN <--- That is, we need to be here.
However, we don't know that the next value is kv-ccc. Instead, we seek to the
first value that strictly greater than 'kv-bbb'. It is Successor(kv-bbb).
It doesn't matter if we're using a full extended key or not.
RocksDB calls:
Seek(Successor(kv-bbb));
if (it->Valid() && kd->covers_key(...))
return record;
Note that the code is the same as with HA_READ_KEY_OR_NEXT, except that
we seek to Successor($lookup_key) instead of $lookup_key itself.
== HA_READ_AFTER_KEY, backward CF ==
Suppose, the lookup key is 'kv-bbb':
(kv+1)-xxx-pk
( kv )-ccc-pk7
( kv )-ccc-pk6 <-- We get here when we call Seek(Successor(kv-bbb))
# Successor(kv-bbb)
( kv )-bbb-pk5
( kv )-bbb-pk4
( kv )-bbb-pk3
( kv )-bbb-pk2
( kv )-bbb-pk1
# ( kv )-bbb <-- We would get here if we called SeekForPrev(kv-bbb).
( kv )-aaa-pk
RocksDB calls:
SeekForPrev(Successor(kv-bbb));
if (it->Valid() && kd->covers_key(...))
return record.
Note that the code is the same as with HA_READ_KEY_OR_NEXT, except that
we seek to Successor($lookup_key) instead of $lookup_key itself.
== HA_READ_BEFORE_KEY, forward CF ==
This is finding max(key) such that key < lookup_tuple.
Suppose, lookup_tuple=kv-bbb.
( kv )-aaa-pk1
( kv )-aaa-pk2
( kv )-aaa-pk3 <-- SeekForPrev("kv-bbb") will put us here.
# ( kv )-bbb
( kv )-bbb-pk4
( kv )-bbb-pk5
( kv )-bbb-pk6
If the lookup tuple is a full key (e.g. kv-bbb-pk3), and the key is present in
the database, the iterator will be positioned on the key. We will need to call
Prev() to get the next key.
RocksDB calls:
it->SeekForPrev(kv-bbb);
if (it->Valid() && using_full_key &&
kd->value_matches_prefix(...))
{
/* We are using full key and we've hit an exact match */
it->Prev();
}
if (it->Valid() && kd->covers_key(...))
return record;
== HA_READ_BEFORE_KEY, backward CF ==
This is finding max(key) such that key < lookup_tuple.
Suppose, lookup_tuple=kv-bbb, a prefix of the full key.
( kv )-bbb-pk6
( kv )-bbb-pk5
( kv )-bbb-pk4
# ( kv )-bbb
( kv )-aaa-pk3 <-- Need to be here, and Seek("kv-bbb") will put us here
( kv )-aaa-pk2
( kv )-aaa-pk1
If the lookup tuple is a full key (e.g. kv-bbb-pk4), and the key is present in
the database, the iterator will be positioned on the key. We will need to call
Next() to get the next key.
RocksDB calls:
it->Seek(kv-bbb);
if (it->Valid() && using_full_key &&
kd->value_matches_prefix(...))
{
/* We are using full key and we've hit an exact match */
it->Next();
}
if (it->Valid() && kd->covers_key(...))
return record;
== HA_READ_PREFIX_LAST, forward CF ==
Find the last record with the specified index prefix lookup_tuple.
Suppose, lookup_tuple='kv-bbb'
( kv )-aaa-pk2
( kv )-aaa-pk3
# ( kv )-bbb
( kv )-bbb-pk4
( kv )-bbb-pk5
( kv )-bbb-pk6
( kv )-bbb-pk7 <--- SeekForPrev(Successor(kv-bbb)) will get us here
# ( kv )-ccc
( kv )-ccc-pk8
( kv )-ccc-pk9
RocksDB calls:
SeekForPrev(Successor(kv-bbb));
if (using_full_key && it->Valid() && !cmp_full_keys(Sucessor(lookup_key)))
it->Prev();
if (it->Valid() && kd->covers_key(...))
{
if (!cmp_full_keys(lookup_tuple)) // not needed in _OR_PREV
{
// the record's prefix matches lookup_tuple.
return record;
}
}
== HA_READ_PREFIX_LAST, backward CF ==
Suppose, lookup_tuple='kv-bbb'
( kv )-ccc-pk9
( kv )-ccc-pk8
# ( kv )-ccc <-- 2. Seek(Successor(kv-bbb)) will point here
and it will fall down to the next row.
( kv )-bbb-pk7 <--- 1. Need to be here.
( kv )-bbb-pk6
( kv )-bbb-pk5
( kv )-bbb-pk4
# ( kv )-bbb
( kv )-aaa-pk3
( kv )-aaa-pk2
RocksDB calls:
it->Seek(Successor(kv-bbb));
if (using_full_key && it->Valid() && !cmp_full_keys(Sucessor(lookup_key)))
it->Next();
if (it->Valid() && kd->covers_key(..))
{
if (!cmp_full_keys(...)) // not needed in _OR_PREV
{
// the record's prefix matches lookup_tuple.
return record;
}
}
== HA_READ_PREFIX_LAST_OR_PREV, forward or backward CF ==
This is just like HA_READ_PREFIX_LAST but we don't need to check that the key
we've got is in the search prefix. (search for "not needed in _OR_PREV" above)
|
