1 /* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 // vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3 #ident "$Id$"
4 /*======
5 This file is part of PerconaFT.
6
7
8 Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
9
10 PerconaFT is free software: you can redistribute it and/or modify
11 it under the terms of the GNU General Public License, version 2,
12 as published by the Free Software Foundation.
13
14 PerconaFT is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
21
22 ----------------------------------------
23
24 PerconaFT is free software: you can redistribute it and/or modify
25 it under the terms of the GNU Affero General Public License, version 3,
26 as published by the Free Software Foundation.
27
28 PerconaFT is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 GNU Affero General Public License for more details.
32
33 You should have received a copy of the GNU Affero General Public License
34 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
35 ======= */
36
37 #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
38
39 // Test keyrange
40
41
42 #include "test.h"
43
44 #include <unistd.h>
45
46 static TOKUTXN const null_txn = 0;
47
48 static const char *fname = TOKU_TEST_FILENAME;
49 static CACHETABLE ct;
50 static FT_HANDLE t;
51
close_ft_and_ct(void)52 static void close_ft_and_ct (void) {
53 int r;
54 r = toku_close_ft_handle_nolsn(t, 0); assert(r==0);
55 toku_cachetable_close(&ct);
56 }
57
open_ft_and_ct(bool unlink_old)58 static void open_ft_and_ct (bool unlink_old) {
59 int r;
60 if (unlink_old) unlink(fname);
61 toku_cachetable_create(&ct, 0, ZERO_LSN, nullptr);
62 r = toku_open_ft_handle(fname, 1, &t, 1<<12, 1<<9, TOKU_DEFAULT_COMPRESSION_METHOD, ct, null_txn, toku_builtin_compare_fun); assert(r==0);
63 }
64
close_and_reopen(void)65 static void close_and_reopen (void) {
66 close_ft_and_ct();
67 open_ft_and_ct(false);
68 }
69
reload(uint64_t limit)70 static void reload (uint64_t limit) {
71 // insert keys 1, 3, 5, ...
72 for (uint64_t i=0; i<limit; i++) {
73 char key[100],val[100];
74 snprintf(key, 100, "%08llu", (unsigned long long)2*i+1);
75 snprintf(val, 100, "%08llu", (unsigned long long)2*i+1);
76 ft_lookup_and_check_nodup(t, key, val);
77 }
78 }
79
80 enum memory_state {
81 LEAVE_IN_MEMORY, // leave the state in main memory
82 CLOSE_AND_RELOAD, // close the fts and reload them into main memory (that will cause >1 partitio in many leaves.)
83 CLOSE_AND_REOPEN_LEAVE_ON_DISK // close the fts, reopen them, but leave the state on disk.
84 };
85
maybe_reopen(enum memory_state ms,uint64_t limit)86 static void maybe_reopen (enum memory_state ms, uint64_t limit) {
87 switch (ms) {
88 case CLOSE_AND_RELOAD:
89 close_and_reopen();
90 reload(limit);
91 return;
92 case CLOSE_AND_REOPEN_LEAVE_ON_DISK:
93 close_and_reopen();
94 return;
95 case LEAVE_IN_MEMORY:
96 return;
97 }
98 assert(0);
99 }
100
verify_keysrange(enum memory_state UU (ms),uint64_t limit,uint64_t intkey1,uint64_t intkey2,uint64_t less,uint64_t equal1,uint64_t middle,uint64_t equal2,uint64_t greater,bool middle3exact)101 static void verify_keysrange(enum memory_state UU(ms), uint64_t limit,
102 uint64_t intkey1,
103 uint64_t intkey2,
104 uint64_t less,
105 uint64_t equal1,
106 uint64_t middle,
107 uint64_t equal2,
108 uint64_t greater,
109 bool middle3exact) {
110 uint64_t max_item = limit * 2 - 1;
111 uint64_t perfect_total = limit;
112 uint64_t perfect_less = intkey1 / 2;
113 uint64_t perfect_equal1 = intkey1 % 2 == 1;
114 uint64_t perfect_equal2 = intkey2 % 2 == 1 && intkey2 <= max_item;
115 uint64_t perfect_greater = intkey2 >= max_item ? 0 : (max_item + 1 - intkey2) / 2;
116 uint64_t perfect_middle = perfect_total - perfect_less - perfect_equal1 - perfect_equal2 - perfect_greater;
117
118 uint64_t total = less + equal1 + middle + equal2 + greater;
119 assert(total > 0);
120 assert(total < 2 * perfect_total);
121 assert(total > perfect_total / 2);
122
123 assert(equal1 == perfect_equal1 || (equal1 == 0 && !middle3exact));
124 assert(equal2 == perfect_equal2 || (equal2 == 0 && !middle3exact));
125
126 // As of 2013-02-25 this is accurate with fiddle ~= total/50.
127 // Set to 1/10th to prevent flakiness.
128 uint64_t fiddle = perfect_total / 10;
129 assert(less + fiddle > perfect_less);
130 assert(less < perfect_less + fiddle);
131
132 assert(middle + fiddle > perfect_middle);
133 assert(middle < perfect_middle + fiddle);
134
135 assert(greater + fiddle > perfect_greater);
136 assert(greater < perfect_greater + fiddle);
137
138 if (middle3exact) {
139 assert(middle == perfect_middle);
140 }
141 }
142
143
test_keyrange(enum memory_state ms,uint64_t limit)144 static void test_keyrange (enum memory_state ms, uint64_t limit) {
145 open_ft_and_ct(true);
146
147 // insert keys 1, 3, 5, ...
148 for (uint64_t i=0; i<limit; i++) {
149 char key[100],val[100];
150 snprintf(key, 100, "%08llu", (unsigned long long)2*i+1);
151 snprintf(val, 100, "%08llu", (unsigned long long)2*i+1);
152 DBT k,v;
153 toku_ft_insert(t, toku_fill_dbt(&k, key, 1+strlen(key)), toku_fill_dbt(&v,val, 1+strlen(val)), null_txn);
154 }
155
156 {
157 struct ftstat64_s s;
158 toku_ft_handle_stat64(t, null_txn, &s);
159
160 assert(0 < s.nkeys && s.nkeys <= limit);
161 assert(0 < s.dsize && s.dsize <= limit * (9 + 9)); // keylen = 9, vallen = 9
162 }
163
164 maybe_reopen(ms, limit);
165
166 {
167 uint64_t prev_less = 0, prev_greater = 1LL << 60;
168 uint64_t count_less_adjacent = 0, count_greater_adjacent = 0; // count the number of times that the next value is 1 more (less) than the previous.
169 uint64_t equal_count = 0;
170
171 // lookup keys 1, 3, 5, ...
172 for (uint64_t i=0; i<limit; i++) {
173 char key[100];
174 snprintf(key, 100, "%08llu", (unsigned long long)2*i+1);
175 DBT k;
176 uint64_t less,equal,greater;
177 toku_ft_keyrange(t, toku_fill_dbt(&k, key, 1+strlen(key)), &less, &equal, &greater);
178 if (verbose > 1)
179 printf("Pkey %llu/%llu %llu %llu %llu\n", (unsigned long long)2*i+1, (unsigned long long)2*limit, (unsigned long long)less, (unsigned long long)equal, (unsigned long long)greater);
180
181 assert(0 < less + equal + greater);
182 assert(less + equal + greater <= 2 * limit);
183 assert(equal == 0 || equal == 1);
184
185 // It's an estimate, and the values don't even change monotonically.
186 // And all the leaves are in main memory so it's always present.
187 if (ms!=CLOSE_AND_REOPEN_LEAVE_ON_DISK) {
188 if (equal==1) equal_count++;
189 #if 0
190 // The first few items are exact for less.
191 if (i<70) {
192 assert(less==i);
193 }
194 // The last few items are exact for greater.
195 if (limit-i<70) {
196 assert(greater<=limit-i-1);
197 }
198 #endif
199 } else {
200 // after reopen, none of the basements are in memory
201 // However, "both" keys can be in the same basement (specifically the last basement node in the tree)
202 // Without trying to figure out how many are in the last basement node, we expect at least the first half not to be in the last basement node.
203 assert(i > limit / 2 || equal == 0);
204 #if 0
205 if (i<10) {
206 assert(less==0);
207 }
208 if (limit-i<10) {
209 assert(greater==0);
210 }
211 #endif
212 }
213 // Count the number of times that prev_less is 1 less than less.
214 if (prev_less+1 == less) {
215 count_less_adjacent++;
216 }
217 if (prev_greater-1 == greater) {
218 count_greater_adjacent++;
219 }
220 // the best we can do: It's an estimate. At least in the current implementation for this test (which has small rows)
221 // the estimate grows monotonically as the leaf grows.
222 prev_less = less;
223 prev_greater = greater;
224 }
225 if (ms!=CLOSE_AND_REOPEN_LEAVE_ON_DISK) {
226 // If we were doing the in-memory case then most keys are adjacent.
227 assert(count_less_adjacent >= 0.9 * limit); // we expect at least 90% to be right.
228 assert(count_greater_adjacent >= 0.9 * limit); // we expect at least 90% to be right.
229 assert(equal_count >= 0.9 * limit);
230 }
231 }
232
233 maybe_reopen(ms, limit);
234
235 // lookup keys 0, 2, 4, ... not in the tree
236 for (uint64_t i=0; i<1+limit; i++) {
237 char key[100];
238 snprintf(key, 100, "%08llu", (unsigned long long)2*i);
239 DBT k;
240 uint64_t less,equal,greater;
241 toku_ft_keyrange(t, toku_fill_dbt(&k, key, 1+strlen(key)), &less, &equal, &greater);
242 if (verbose > 1)
243 printf("Akey %llu/%llu %llu %llu %llu\n", (unsigned long long)2*i, (unsigned long long)2*limit, (unsigned long long)less, (unsigned long long)equal, (unsigned long long)greater);
244
245 assert(0 < less + equal + greater);
246 assert(less + equal + greater <= 2 * limit);
247 assert(equal == 0);
248 #if 0
249 // The first few items are exact (looking a key that's not there)
250 if (ms!=CLOSE_AND_REOPEN_LEAVE_ON_DISK) {
251 if (i<70) {
252 assert(less==i);
253 }
254 // The last few items are exact (looking up a key that's not there)
255 if (limit-i<70) {
256 assert(greater<=limit-i);
257 }
258 } else {
259 if (i<10) {
260 assert(less==0);
261 }
262 if (limit-i<10) {
263 assert(greater==0);
264 }
265 }
266 #endif
267 }
268
269 maybe_reopen(ms, limit);
270
271 {
272 uint64_t totalqueries = 0;
273 uint64_t num_middle3_exact = 0;
274 for (uint64_t i=0; i < 2*limit; i++) {
275 char key[100];
276 char keyplus4[100];
277 char keyplus5[100];
278 uint64_t intkey = i;
279
280 snprintf(key, 100, "%08" PRIu64 "", intkey);
281 snprintf(keyplus4, 100, "%08" PRIu64 "", intkey+4);
282 snprintf(keyplus5, 100, "%08" PRIu64 "", intkey+5);
283
284 DBT k;
285 DBT k2;
286 DBT k3;
287 toku_fill_dbt(&k, key, 1+strlen(key));
288 toku_fill_dbt(&k2, keyplus4, 1+strlen(keyplus4));
289 toku_fill_dbt(&k3, keyplus5, 1+strlen(keyplus5));
290 uint64_t less,equal1,middle,equal2,greater;
291 bool middle3exact;
292 toku_ft_keysrange(t, &k, &k2, &less, &equal1, &middle, &equal2, &greater, &middle3exact);
293 if (ms == CLOSE_AND_REOPEN_LEAVE_ON_DISK) {
294 //TODO(yoni): when reading basement nodes is implemented, get rid of this hack
295 middle3exact = false;
296 }
297 totalqueries++;
298 num_middle3_exact += middle3exact;
299 if (verbose > 1) {
300 printf("Rkey2 %" PRIu64 "/%" PRIu64
301 " %" PRIu64
302 " %" PRIu64
303 " %" PRIu64
304 " %" PRIu64
305 " %" PRIu64
306 " %s\n",
307 intkey, 2*limit, less, equal1, middle, equal2, greater, middle3exact ? "true" : "false");
308 }
309 verify_keysrange(ms, limit, intkey, intkey+4,
310 less, equal1, middle, equal2, greater, middle3exact);
311
312 toku_ft_keysrange(t, &k, &k3, &less, &equal1, &middle, &equal2, &greater, &middle3exact);
313 if (ms == CLOSE_AND_REOPEN_LEAVE_ON_DISK) {
314 //TODO(yoni): when reading basement nodes is implemented, get rid of this hack
315 middle3exact = false;
316 }
317 totalqueries++;
318 num_middle3_exact += middle3exact;
319 if (verbose > 1) {
320 printf("Rkey3 %" PRIu64 "/%" PRIu64
321 " %" PRIu64
322 " %" PRIu64
323 " %" PRIu64
324 " %" PRIu64
325 " %" PRIu64
326 " %s\n",
327 intkey, 2*limit, less, equal1, middle, equal2, greater, middle3exact ? "true" : "false");
328 }
329 verify_keysrange(ms, limit, intkey, intkey+5,
330 less, equal1, middle, equal2, greater, middle3exact);
331 }
332 assert(num_middle3_exact <= totalqueries);
333 if (ms == CLOSE_AND_REOPEN_LEAVE_ON_DISK) {
334 //TODO(yoni): when reading basement nodes is implemented, get rid of this hack
335 assert(num_middle3_exact == 0);
336 } else {
337 // About 85% of the time, the key for an int (and +4 or +5) is in the
338 // same basement node. Check >= 70% so this isn't very flaky.
339 assert(num_middle3_exact > totalqueries * 7 / 10);
340 }
341 }
342
343 close_ft_and_ct();
344 }
345
346 int
test_main(int argc,const char * argv[])347 test_main (int argc , const char *argv[]) {
348 uint64_t limit = 30000;
349
350 for (int i = 1; i < argc; i++) {
351 if (strcmp(argv[i], "-v") == 0) {
352 verbose++;
353 continue;
354 }
355 if (strcmp(argv[i], "-q") == 0) {
356 if (verbose > 0) verbose--;
357 continue;
358 }
359 if (strcmp(argv[i], "-n") == 0 && i+1 < argc) {
360 limit = atoll(argv[++i]);
361 continue;
362 }
363 }
364
365 test_keyrange(LEAVE_IN_MEMORY, limit);
366 test_keyrange(CLOSE_AND_REOPEN_LEAVE_ON_DISK, limit);
367 test_keyrange(CLOSE_AND_RELOAD, limit);
368
369 if (verbose) printf("test ok\n");
370 return 0;
371 }
372
373