Gitiles
Code Review Sign In
asterix-gerrit.ics.uci.edu / asterixdb / be011392864814d06dd0ad0624feafde60c4ac89 / . / hyracks-storage-am-btree / src / test / java / BTreeTest.java
blob: 1d0ff55f69efa3349cb3ffaeaf34ed390844334a [file] [log] [blame]
alexander.behm0aecb4f2010-08-30 17:52:33 +0000[diff] [blame]1package edu.uci.ics.asterix.test.storage;
2
3import java.io.File;
4import java.io.RandomAccessFile;
5import java.nio.ByteBuffer;
6import java.util.Random;
7import java.util.logging.Level;
8
9import org.junit.Test;
10
11import edu.uci.ics.asterix.common.config.GlobalConfig;
12import edu.uci.ics.asterix.indexing.btree.impls.BTree;
13import edu.uci.ics.asterix.indexing.btree.impls.BTreeDiskOrderScanCursor;
14import edu.uci.ics.asterix.indexing.btree.impls.BTreeMetaFactory;
15import edu.uci.ics.asterix.indexing.btree.impls.BTreeNSMInteriorFactory;
16import edu.uci.ics.asterix.indexing.btree.impls.BTreeNSMLeafFactory;
17import edu.uci.ics.asterix.indexing.btree.impls.BTreeRangeSearchCursor;
18import edu.uci.ics.asterix.indexing.btree.impls.MultiComparator;
19import edu.uci.ics.asterix.indexing.btree.impls.OrderedSlotManagerFactory;
20import edu.uci.ics.asterix.indexing.btree.impls.RangePredicate;
21import edu.uci.ics.asterix.indexing.btree.interfaces.IBTreeCursor;
22import edu.uci.ics.asterix.indexing.btree.interfaces.IBTreeFrameInterior;
23import edu.uci.ics.asterix.indexing.btree.interfaces.IBTreeFrameInteriorFactory;
24import edu.uci.ics.asterix.indexing.btree.interfaces.IBTreeFrameLeaf;
25import edu.uci.ics.asterix.indexing.btree.interfaces.IBTreeFrameLeafFactory;
26import edu.uci.ics.asterix.indexing.btree.interfaces.IBTreeFrameMeta;
27import edu.uci.ics.asterix.indexing.btree.interfaces.IBTreeFrameMetaFactory;
28import edu.uci.ics.asterix.indexing.btree.interfaces.IComparator;
29import edu.uci.ics.asterix.indexing.btree.interfaces.IFieldAccessor;
30import edu.uci.ics.asterix.indexing.btree.interfaces.ISlotManagerFactory;
31import edu.uci.ics.asterix.indexing.types.Int32Accessor;
32import edu.uci.ics.asterix.indexing.types.Int32Comparator;
33import edu.uci.ics.asterix.indexing.types.StringAccessor;
34import edu.uci.ics.asterix.indexing.types.StringComparator;
35import edu.uci.ics.asterix.om.AInt32;
36import edu.uci.ics.asterix.storage.buffercache.BufferAllocator;
37import edu.uci.ics.asterix.storage.buffercache.BufferCache;
38import edu.uci.ics.asterix.storage.buffercache.ClockPageReplacementStrategy;
39import edu.uci.ics.asterix.storage.buffercache.IBufferCache;
40import edu.uci.ics.asterix.storage.buffercache.ICacheMemoryAllocator;
41import edu.uci.ics.asterix.storage.buffercache.IPageReplacementStrategy;
42import edu.uci.ics.asterix.storage.file.FileInfo;
43import edu.uci.ics.asterix.storage.file.FileManager;
44
45public class BTreeTest {
46 private static final int PAGE_SIZE = 128;
47 // private static final int PAGE_SIZE = 8192;
48 private static final int NUM_PAGES = 10;
49
50 // to help with the logger madness
51 private void print(String str) {
52 if(GlobalConfig.ASTERIX_LOGGER.isLoggable(Level.FINEST)) {
53 GlobalConfig.ASTERIX_LOGGER.finest(str);
54 }
55 }
56
57 // FIXED-LENGTH KEY TEST
58 // create a B-tree with one fixed-length "key" field and one fixed-length "value" field
59 // fill B-tree with random values using insertions (not bulk load)
60 // perform ordered scan and range search
61 @Test
62 public void test01() throws Exception {
63
64 print("FIXED-LENGTH KEY TEST\n");
65
66 FileManager fileManager = new FileManager();
67 ICacheMemoryAllocator allocator = new BufferAllocator();
68 IPageReplacementStrategy prs = new ClockPageReplacementStrategy();
69 IBufferCache bufferCache = new BufferCache(allocator, prs, fileManager, PAGE_SIZE, NUM_PAGES);
70
71 File f = new File("/tmp/btreetest.bin");
72 RandomAccessFile raf = new RandomAccessFile(f, "rw");
73 int fileId = 0;
74 FileInfo fi = new FileInfo(fileId, raf);
75 fileManager.registerFile(fi);
76
77 ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
78 ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
79 IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
80 IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
81 IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
82
83 IBTreeFrameLeaf leafFrame = leafFrameFactory.getFrame();
84 IBTreeFrameInterior interiorFrame = interiorFrameFactory.getFrame();
85 IBTreeFrameMeta metaFrame = metaFrameFactory.getFrame();
86
87 IFieldAccessor[] fields = new IFieldAccessor[2];
88 fields[0] = new Int32Accessor(); // key field
89 fields[1] = new Int32Accessor(); // value field
90
91 int keyLen = 1;
92 IComparator[] cmps = new IComparator[keyLen];
93 cmps[0] = new Int32Comparator();
94 MultiComparator cmp = new MultiComparator(cmps, fields);
95
96 BTree btree = new BTree(bufferCache, interiorFrameFactory, leafFrameFactory, interiorSlotManagerFactory, leafSlotManagerFactory, cmp);
97 btree.create(fileId, leafFrame, metaFrame);
98 btree.open(fileId);
99
100 Random rnd = new Random();
101 rnd.setSeed(50);
102
103 long start = System.currentTimeMillis();
104
105 print("INSERTING INTO TREE\n");
106
107 byte[] record = new byte[8];
108 for (int i = 0; i < 10000; i++) {
109 AInt32 field0 = new AInt32(rnd.nextInt() % 10000);
110 AInt32 field1 = new AInt32(5);
111
112 byte[] f0 = field0.toBytes();
113 byte[] f1 = field1.toBytes();
114
115 System.arraycopy(f0, 0, record, 0, 4);
116 System.arraycopy(f1, 0, record, 4, 4);
117
118 if (i % 1000 == 0) {
119 long end = System.currentTimeMillis();
120 print("INSERTING " + i + " : " + field0.getIntegerValue() + " " + field1.getIntegerValue() + " " + (end - start) + "\n");
121 }
122
123 try {
124 btree.insert(record, leafFrame, interiorFrame, metaFrame);
125 } catch (Exception e) {
126 }
127 }
128 //btree.printTree(leafFrame, interiorFrame);
129
130 print("TOTALSPACE: " + f.length() + "\n");
131
132 String stats = btree.printStats();
133 print(stats);
134
135 long end = System.currentTimeMillis();
136 long duration = end - start;
137 print("DURATION: " + duration + "\n");
138
139 // ordered scan
140 print("ORDERED SCAN:\n");
141 IBTreeCursor scanCursor = new BTreeRangeSearchCursor(leafFrame);
142 RangePredicate nullPred = new RangePredicate(true, null, null, null);
143 btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
144 try {
145 while (scanCursor.hasNext()) {
146 scanCursor.next();
147 byte[] array = scanCursor.getPage().getBuffer().array();
148 int recOffset = scanCursor.getOffset();
149 String rec = cmp.printRecord(array, recOffset);
150 print(rec + "\n");
151 }
152 } catch (Exception e) {
153 e.printStackTrace();
154 } finally {
155 scanCursor.close();
156 }
157
158 // disk-order scan
159 print("DISK-ORDER SCAN:\n");
160 BTreeDiskOrderScanCursor diskOrderCursor = new BTreeDiskOrderScanCursor(leafFrame);
161 btree.diskOrderScan(diskOrderCursor, leafFrame, metaFrame);
162 try {
163 while (diskOrderCursor.hasNext()) {
164 diskOrderCursor.next();
165 byte[] array = diskOrderCursor.getPage().getBuffer().array();
166 int recOffset = diskOrderCursor.getOffset();
167 String rec = cmp.printRecord(array, recOffset);
168 print(rec + "\n");
169 }
170 } catch (Exception e) {
171 e.printStackTrace();
172 } finally {
173 diskOrderCursor.close();
174 }
175
176 // range search in [-1000, 1000]
177 print("RANGE SEARCH:\n");
178
179 IBTreeCursor rangeCursor = new BTreeRangeSearchCursor(leafFrame);
180
181 AInt32 lk = new AInt32(-1000);
182 byte[] lowKey = lk.toBytes();
183
184 AInt32 hk = new AInt32(1000);
185 byte[] highKey = hk.toBytes();
186
187 IComparator[] searchCmps = new IComparator[1];
188 searchCmps[0] = new Int32Comparator();
189 MultiComparator searchCmp = new MultiComparator(searchCmps, fields);
190
191 RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, searchCmp);
192 btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
193
194 try {
195 while (rangeCursor.hasNext()) {
196 rangeCursor.next();
197 byte[] array = rangeCursor.getPage().getBuffer().array();
198 int recOffset = rangeCursor.getOffset();
199 String rec = cmp.printRecord(array, recOffset);
200 print(rec + "\n");
201 }
202 } catch (Exception e) {
203 e.printStackTrace();
204 } finally {
205 rangeCursor.close();
206 }
207
208 btree.close();
209
210 bufferCache.close();
211 fileManager.close();
212 print("\n");
213 }
214
215 // COMPOSITE KEY TEST (NON-UNIQUE B-TREE)
216 // create a B-tree with one two fixed-length "key" fields and one fixed-length "value" field
217 // fill B-tree with random values using insertions (not bulk load)
218 // perform ordered scan and range search
219 @Test
220 public void test02() throws Exception {
221
222 print("COMPOSITE KEY TEST\n");
223
224 FileManager fileManager = new FileManager();
225 ICacheMemoryAllocator allocator = new BufferAllocator();
226 IPageReplacementStrategy prs = new ClockPageReplacementStrategy();
227 IBufferCache bufferCache = new BufferCache(allocator, prs, fileManager, PAGE_SIZE, NUM_PAGES);
228
229 File f = new File("/tmp/btreetest.bin");
230 RandomAccessFile raf = new RandomAccessFile(f, "rw");
231 int fileId = 0;
232 FileInfo fi = new FileInfo(fileId, raf);
233 fileManager.registerFile(fi);
234
235 ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
236 ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
237 IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
238 IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
239 IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
240
241 IBTreeFrameLeaf leafFrame = leafFrameFactory.getFrame();
242 IBTreeFrameInterior interiorFrame = interiorFrameFactory.getFrame();
243 IBTreeFrameMeta metaFrame = metaFrameFactory.getFrame();
244
245 IFieldAccessor[] fields = new IFieldAccessor[3];
246 fields[0] = new Int32Accessor(); // key field 1
247 fields[1] = new Int32Accessor(); // key field 2
248 fields[2] = new Int32Accessor(); // value field
249
250 int keyLen = 2;
251 IComparator[] cmps = new IComparator[keyLen];
252 cmps[0] = new Int32Comparator();
253 cmps[1] = new Int32Comparator();
254 MultiComparator cmp = new MultiComparator(cmps, fields);
255
256 BTree btree = new BTree(bufferCache,
257 interiorFrameFactory,
258 leafFrameFactory,
259 interiorSlotManagerFactory,
260 leafSlotManagerFactory,
261 cmp);
262 btree.create(fileId, leafFrame, metaFrame);
263 btree.open(fileId);
264
265 Random rnd = new Random();
266 rnd.setSeed(50);
267
268 long start = System.currentTimeMillis();
269
270 print("INSERTING INTO TREE\n");
271 byte[] record = new byte[12];
272 for (int i = 0; i < 10000; i++) {
273 AInt32 field0 = new AInt32(rnd.nextInt() % 2000);
274 AInt32 field1 = new AInt32(rnd.nextInt() % 1000);
275 AInt32 field2 = new AInt32(5);
276
277 byte[] f0 = field0.toBytes();
278 byte[] f1 = field1.toBytes();
279 byte[] f2 = field2.toBytes();
280
281 System.arraycopy(f0, 0, record, 0, 4);
282 System.arraycopy(f1, 0, record, 4, 4);
283 System.arraycopy(f2, 0, record, 8, 4);
284
285 if (i % 1000 == 0) {
286 print("INSERTING " + i + " : " + field0.getIntegerValue() + " " + field1.getIntegerValue() + "\n");
287 }
288
289 try {
290 btree.insert(record, leafFrame, interiorFrame, metaFrame);
291 } catch (Exception e) {
292 }
293 }
294 //btree.printTree(leafFrame, interiorFrame);
295
296 long end = System.currentTimeMillis();
297 long duration = end - start;
298 print("DURATION: " + duration + "\n");
299
300 // try a simple index scan
301 print("ORDERED SCAN:\n");
302 IBTreeCursor scanCursor = new BTreeRangeSearchCursor(leafFrame);
303 RangePredicate nullPred = new RangePredicate(true, null, null, null);
304 btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
305
306 try {
307 while (scanCursor.hasNext()) {
308 scanCursor.next();
309 byte[] array = scanCursor.getPage().getBuffer().array();
310 int recOffset = scanCursor.getOffset();
311 String rec = cmp.printRecord(array, recOffset);
312 print(rec + "\n");
313 }
314 } catch (Exception e) {
315 e.printStackTrace();
316 } finally {
317 scanCursor.close();
318 }
319
320 // range search in [(-3),(3)]
321 print("RANGE SEARCH:\n");
322 IBTreeCursor rangeCursor = new BTreeRangeSearchCursor(leafFrame);
323
324 AInt32 lk = new AInt32(-3);
325 byte[] lowKey = lk.toBytes();
326
327 AInt32 hk = new AInt32(3);
328 byte[] highKey = hk.toBytes();
329
330 IComparator[] searchCmps = new IComparator[1];
331 searchCmps[0] = new Int32Comparator();
332 MultiComparator searchCmp = new MultiComparator(searchCmps, fields); // use only a single comparator for searching
333
334 RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, searchCmp);
335 btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
336
337 try {
338 while (rangeCursor.hasNext()) {
339 rangeCursor.next();
340 byte[] array = rangeCursor.getPage().getBuffer().array();
341 int recOffset = rangeCursor.getOffset();
342 String rec = cmp.printRecord(array, recOffset);
343 print(rec + "\n");
344 }
345 } catch (Exception e) {
346 e.printStackTrace();
347 } finally {
348 rangeCursor.close();
349 }
350
351 btree.close();
352
353 bufferCache.close();
354 fileManager.close();
355
356 print("\n");
357 }
358
359 // VARIABLE-LENGTH TEST
360 // create a B-tree with one variable-length "key" field and one variable-length "value" field
361 // fill B-tree with random values using insertions (not bulk load)
362 // perform ordered scan and range search
363 @Test
364 public void test03() throws Exception {
365
366 print("VARIABLE-LENGTH KEY TEST\n");
367
368 FileManager fileManager = new FileManager();
369 ICacheMemoryAllocator allocator = new BufferAllocator();
370 IPageReplacementStrategy prs = new ClockPageReplacementStrategy();
371 IBufferCache bufferCache = new BufferCache(allocator, prs, fileManager, PAGE_SIZE, NUM_PAGES);
372
373 File f = new File("/tmp/btreetest.bin");
374 RandomAccessFile raf = new RandomAccessFile(f, "rw");
375 int fileId = 0;
376 FileInfo fi = new FileInfo(fileId, raf);
377 fileManager.registerFile(fi);
378
379 ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
380 ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
381 IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
382 IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
383 IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
384
385 IBTreeFrameLeaf leafFrame = leafFrameFactory.getFrame();
386 IBTreeFrameInterior interiorFrame = interiorFrameFactory.getFrame();
387 IBTreeFrameMeta metaFrame = metaFrameFactory.getFrame();
388
389 IFieldAccessor[] fields = new IFieldAccessor[2];
390 fields[0] = new StringAccessor(); // key
391 fields[1] = new StringAccessor(); // value
392
393 int keyLen = 1;
394 IComparator[] cmps = new IComparator[keyLen];
395 cmps[0] = new StringComparator();
396
397 MultiComparator cmp = new MultiComparator(cmps, fields);
398
399 BTree btree = new BTree(bufferCache,
400 interiorFrameFactory,
401 leafFrameFactory,
402 interiorSlotManagerFactory,
403 leafSlotManagerFactory,
404 cmp);
405 btree.create(fileId, leafFrame, metaFrame);
406 btree.open(fileId);
407
408 Random rnd = new Random();
409 rnd.setSeed(50);
410
411 int maxLength = 10; // max string length to be generated
412 for (int i = 0; i < 10000; i++) {
413 String field0 = randomString(Math.abs(rnd.nextInt()) % maxLength + 1, rnd);
414 String field1 = randomString(Math.abs(rnd.nextInt()) % maxLength + 1, rnd);
415
416 byte[] f0 = field0.getBytes();
417 byte[] f1 = field1.getBytes();
418
419 byte[] record = new byte[f0.length + f1.length + 8];
420 ByteBuffer buf = ByteBuffer.wrap(record);
421
422 int start = 0;
423 buf.putInt(start, f0.length);
424 start += 4;
425 System.arraycopy(f0, 0, record, start, f0.length);
426 start += f0.length;
427 buf.putInt(start, f1.length);
428 start += 4;
429 System.arraycopy(f1, 0, record, start, f1.length);
430 start += f1.length;
431
432 if (i % 1000 == 0) {
433 print("INSERTING " + i + ": " + cmp.printRecord(record, 0) + "\n");
434 }
435
436 try {
437 btree.insert(record, leafFrame, interiorFrame, metaFrame);
438 } catch (Exception e) {
439 }
440 }
441 // btree.printTree();
442
443 // ordered scan
444 print("ORDERED SCAN:\n");
445 IBTreeCursor scanCursor = new BTreeRangeSearchCursor(leafFrame);
446 RangePredicate nullPred = new RangePredicate(true, null, null, null);
447 btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
448
449 try {
450 while (scanCursor.hasNext()) {
451 scanCursor.next();
452 byte[] array = scanCursor.getPage().getBuffer().array();
453 int recOffset = scanCursor.getOffset();
454 String rec = cmp.printRecord(array, recOffset);
455 print(rec + "\n");
456 }
457 } catch (Exception e) {
458 e.printStackTrace();
459 } finally {
460 scanCursor.close();
461 }
462
463 // range search in ["cbf", cc7"]
464 print("RANGE SEARCH:\n");
465
466 IBTreeCursor rangeCursor = new BTreeRangeSearchCursor(leafFrame);
467
468 byte[] lowKey = new byte[7];
469 ByteBuffer lkByteBuf = ByteBuffer.wrap(lowKey);
470 lkByteBuf.putInt(0, 3);
471 System.arraycopy("cbf".getBytes(), 0, lowKey, 4, 3);
472
473 byte[] highKey = new byte[7];
474 ByteBuffer hkByteBuf = ByteBuffer.wrap(highKey);
475 hkByteBuf.putInt(0, 3);
476 System.arraycopy("cc7".getBytes(), 0, highKey, 4, 3);
477
478 IComparator[] searchCmps = new IComparator[1];
479 searchCmps[0] = new StringComparator();
480 MultiComparator searchCmp = new MultiComparator(searchCmps, fields);
481
482 RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, searchCmp);
483 btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
484
485 try {
486 while (rangeCursor.hasNext()) {
487 rangeCursor.next();
488 byte[] array = rangeCursor.getPage().getBuffer().array();
489 int recOffset = rangeCursor.getOffset();
490 String rec = cmp.printRecord(array, recOffset);
491 print(rec + "\n");
492 }
493 } catch (Exception e) {
494 e.printStackTrace();
495 } finally {
496 rangeCursor.close();
497 }
498
499 btree.close();
500
501 bufferCache.close();
502 fileManager.close();
503
504 print("\n");
505 }
506
507 // DELETION TEST
508 // create a B-tree with one variable-length "key" field and one variable-length "value" field
509 // fill B-tree with random values using insertions, then delete entries one-by-one
510 // repeat procedure a few times on same B-tree
511 @Test
512 public void test04() throws Exception {
513
514 print("DELETION TEST\n");
515
516 FileManager fileManager = new FileManager();
517 ICacheMemoryAllocator allocator = new BufferAllocator();
518 IPageReplacementStrategy prs = new ClockPageReplacementStrategy();
519 IBufferCache bufferCache = new BufferCache(allocator, prs, fileManager, PAGE_SIZE, NUM_PAGES);
520
521 File f = new File("/tmp/btreetest.bin");
522 RandomAccessFile raf = new RandomAccessFile(f, "rw");
523 int fileId = 0;
524 FileInfo fi = new FileInfo(fileId, raf);
525 fileManager.registerFile(fi);
526
527 ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
528 ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
529 IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
530 IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
531 IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
532
533 IBTreeFrameLeaf leafFrame = leafFrameFactory.getFrame();
534 IBTreeFrameInterior interiorFrame = interiorFrameFactory.getFrame();
535 IBTreeFrameMeta metaFrame = metaFrameFactory.getFrame();
536
537 IFieldAccessor[] fields = new IFieldAccessor[2];
538 fields[0] = new StringAccessor(); // key
539 fields[1] = new StringAccessor(); // value
540
541 int keyLen = 1;
542 IComparator[] cmps = new IComparator[keyLen];
543 cmps[0] = new StringComparator();
544
545 MultiComparator cmp = new MultiComparator(cmps, fields);
546
547 BTree btree = new BTree(bufferCache,
548 interiorFrameFactory,
549 leafFrameFactory,
550 interiorSlotManagerFactory,
551 leafSlotManagerFactory,
552 cmp);
553 btree.create(fileId, leafFrame, metaFrame);
554 btree.open(fileId);
555
556 Random rnd = new Random();
557 rnd.setSeed(50);
558
559 int runs = 3;
560 for (int run = 0; run < runs; run++) {
561
562 print("DELETION TEST RUN: " + (run+1) + "/" + runs + "\n");
563
564 print("INSERTING INTO BTREE\n");
565 int maxLength = 10;
566 int ins = 10000;
567 byte[][] records = new byte[ins][];
568 int insDone = 0;
569 int[] insDoneCmp = new int[ins];
570 for (int i = 0; i < ins; i++) {
571 String field0 = randomString(Math.abs(rnd.nextInt()) % maxLength + 1, rnd);
572 String field1 = randomString(Math.abs(rnd.nextInt()) % maxLength + 1, rnd);
573
574 byte[] f0 = field0.getBytes();
575 byte[] f1 = field1.getBytes();
576
577 byte[] record = new byte[f0.length + f1.length + 8];
578 ByteBuffer buf = ByteBuffer.wrap(record);
579
580 int start = 0;
581 buf.putInt(start, f0.length);
582 start += 4;
583 System.arraycopy(f0, 0, record, start, f0.length);
584 start += f0.length;
585 buf.putInt(start, f1.length);
586 start += 4;
587 System.arraycopy(f1, 0, record, start, f1.length);
588 start += f1.length;
589
590 records[i] = record;
591
592 if (i % 1000 == 0) {
593 print("INSERTING " + i + ": " + cmp.printRecord(record, 0) + "\n");
594 }
595
596 try {
597 btree.insert(record, leafFrame, interiorFrame, metaFrame);
598 insDone++;
599 } catch (Exception e) {
600 }
601
602 insDoneCmp[i] = insDone;
603 }
604 // btree.printTree();
605 // btree.printStats();
606
607 print("DELETING FROM BTREE\n");
608 int delDone = 0;
609 for (int i = 0; i < ins; i++) {
610
611 if (i % 1000 == 0) {
612 print("DELETING " + i + ": " + cmp.printRecord(records[i], 0) + "\n");
613 }
614
615 try {
616 btree.delete(records[i], leafFrame, interiorFrame, metaFrame);
617 delDone++;
618 } catch (Exception e) {
619 }
620
621 if (insDoneCmp[i] != delDone) {
622 print("INCONSISTENT STATE, ERROR IN DELETION TEST\n");
623 print("INSDONECMP: " + insDoneCmp[i] + " " + delDone + "\n");
624 break;
625 }
626 // btree.printTree();
627 }
628 //btree.printTree(leafFrame, interiorFrame);
629
630 if (insDone != delDone) {
631 print("ERROR! INSDONE: " + insDone + " DELDONE: " + delDone);
632 break;
633 }
634 }
635
636 btree.close();
637
638 bufferCache.close();
639 fileManager.close();
640
641 print("\n");
642 }
643
644 // BULK LOAD TEST
645 // insert 100,000 records in bulk
646 // B-tree has a composite key to "simulate" non-unique index creation
647 // do range search
648 @Test
649 public void test05() throws Exception {
650
651 print("BULK LOAD TEST\n");
652
653 FileManager fileManager = new FileManager();
654 ICacheMemoryAllocator allocator = new BufferAllocator();
655 IPageReplacementStrategy prs = new ClockPageReplacementStrategy();
656 IBufferCache bufferCache = new BufferCache(allocator, prs, fileManager, PAGE_SIZE, NUM_PAGES);
657
658 File f = new File("/tmp/btreetest.bin");
659 RandomAccessFile raf = new RandomAccessFile(f, "rw");
660 int fileId = 0;
661 FileInfo fi = new FileInfo(fileId, raf);
662 fileManager.registerFile(fi);
663
664 ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
665 ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
666 IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
667 IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
668 IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
669
670 IBTreeFrameLeaf leafFrame = leafFrameFactory.getFrame();
671 IBTreeFrameInterior interiorFrame = interiorFrameFactory.getFrame();
672 IBTreeFrameMeta metaFrame = metaFrameFactory.getFrame();
673
674 int keyLen = 2;
675
676 IFieldAccessor[] fields = new IFieldAccessor[3];
677 fields[0] = new Int32Accessor();
678 fields[1] = new Int32Accessor();
679 fields[2] = new Int32Accessor();
680
681 IComparator[] cmps = new IComparator[keyLen];
682 cmps[0] = new Int32Comparator();
683 cmps[1] = new Int32Comparator();
684
685 MultiComparator cmp = new MultiComparator(cmps, fields);
686
687 BTree btree = new BTree(bufferCache,
688 interiorFrameFactory,
689 leafFrameFactory,
690 interiorSlotManagerFactory,
691 leafSlotManagerFactory,
692 cmp);
693 btree.create(fileId, leafFrame, metaFrame);
694 btree.open(fileId);
695
696 Random rnd = new Random();
697 rnd.setSeed(50);
698
699 // generate sorted records
700 int ins = 100000;
701 byte[][] records = new byte[ins][];
702 for (int i = 0; i < ins; i++) {
703 byte[] record = new byte[12];
704
705 AInt32 field0 = new AInt32(i);
706 AInt32 field1 = new AInt32(i);
707 AInt32 field2 = new AInt32(rnd.nextInt() % 100);
708
709 byte[] f0 = field0.toBytes();
710 byte[] f1 = field1.toBytes();
711 byte[] f2 = field2.toBytes();
712
713 System.arraycopy(f0, 0, record, 0, 4);
714 System.arraycopy(f1, 0, record, 4, 4);
715 System.arraycopy(f2, 0, record, 8, 4);
716 records[i] = record;
717 }
718
719 print("BULK LOADING " + ins + " RECORDS\n");
720 long start = System.currentTimeMillis();
721
722 BTree.BulkLoadContext ctx = btree.beginBulkLoad(0.7f, leafFrame, interiorFrame, metaFrame);
723 for (int i = 0; i < ins; i++) {
724 btree.bulkLoadAddRecord(ctx, records[i]);
725 }
726 btree.endBulkLoad(ctx);
727
728 long end = System.currentTimeMillis();
729 long duration = end - start;
730 print("DURATION: " + duration + "\n");
731
732 // range search
733 print("RANGE SEARCH:\n");
734 IBTreeCursor rangeCursor = new BTreeRangeSearchCursor(leafFrame);
735
736 AInt32 lowKey = new AInt32(44444);
737 AInt32 highKey = new AInt32(44500);
738
739 IComparator[] searchCmps = new IComparator[1];
740 searchCmps[0] = new Int32Comparator();
741 MultiComparator searchCmp = new MultiComparator(searchCmps, fields);
742
743 RangePredicate rangePred = new RangePredicate(false, lowKey.toBytes(), highKey.toBytes(), searchCmp);
744 btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
745
746 try {
747 while (rangeCursor.hasNext()) {
748 rangeCursor.next();
749 byte[] array = rangeCursor.getPage().getBuffer().array();
750 int recOffset = rangeCursor.getOffset();
751 String rec = cmp.printRecord(array, recOffset);
752 print(rec + "\n");
753 }
754 } catch (Exception e) {
755 e.printStackTrace();
756 } finally {
757 rangeCursor.close();
758 }
759
760 btree.close();
761
762 bufferCache.close();
763 fileManager.close();
764
765 print("\n");
766 }
767
768 // TIME-INTERVAL INTERSECTION DEMO FOR EVENT PEOPLE
769 // demo for Arjun to show easy support of intersection queries on time-intervals
770 @Test
771 public void test06() throws Exception {
772
773 print("TIME-INTERVAL INTERSECTION DEMO\n");
774
775 FileManager fileManager = new FileManager();
776 ICacheMemoryAllocator allocator = new BufferAllocator();
777 IPageReplacementStrategy prs = new ClockPageReplacementStrategy();
778 IBufferCache bufferCache = new BufferCache(allocator, prs, fileManager, PAGE_SIZE, NUM_PAGES);
779
780 File f = new File("/tmp/btreetest.bin");
781 RandomAccessFile raf = new RandomAccessFile(f, "rw");
782 int fileId = 0;
783 FileInfo fi = new FileInfo(fileId, raf);
784 fileManager.registerFile(fi);
785
786 ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
787 ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
788 IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
789 IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
790 IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
791
792 IBTreeFrameLeaf leafFrame = leafFrameFactory.getFrame();
793 IBTreeFrameInterior interiorFrame = interiorFrameFactory.getFrame();
794 IBTreeFrameMeta metaFrame = metaFrameFactory.getFrame();
795
796 int keyLen = 2;
797
798 IFieldAccessor[] fields = new IFieldAccessor[3];
799 fields[0] = new Int32Accessor();
800 fields[1] = new Int32Accessor();
801 fields[2] = new Int32Accessor();
802
803 IComparator[] cmps = new IComparator[keyLen];
804 cmps[0] = new Int32Comparator();
805 cmps[1] = new Int32Comparator();
806
807 MultiComparator cmp = new MultiComparator(cmps, fields);
808
809 BTree btree = new BTree(bufferCache,
810 interiorFrameFactory,
811 leafFrameFactory,
812 interiorSlotManagerFactory,
813 leafSlotManagerFactory,
814 cmp);
815 btree.create(fileId, leafFrame, metaFrame);
816 btree.open(fileId);
817
818 Random rnd = new Random();
819 rnd.setSeed(50);
820
821 long start = System.currentTimeMillis();
822
823 byte[] record = new byte[12];
824
825 int intervalCount = 10;
826 int[][] intervals = new int[intervalCount][2];
827
828 intervals[0][0] = 10;
829 intervals[0][1] = 20;
830
831 intervals[1][0] = 11;
832 intervals[1][1] = 20;
833
834 intervals[2][0] = 12;
835 intervals[2][1] = 20;
836
837 intervals[3][0] = 13;
838 intervals[3][1] = 20;
839
840 intervals[4][0] = 14;
841 intervals[4][1] = 20;
842
843 intervals[5][0] = 20;
844 intervals[5][1] = 30;
845
846 intervals[6][0] = 20;
847 intervals[6][1] = 31;
848
849 intervals[7][0] = 20;
850 intervals[7][1] = 32;
851
852 intervals[8][0] = 20;
853 intervals[8][1] = 33;
854
855 intervals[9][0] = 20;
856 intervals[9][1] = 35;
857
858 // int exceptionCount = 0;
859 for (int i = 0; i < intervalCount; i++) {
860 AInt32 field0 = new AInt32(intervals[i][0]);
861 AInt32 field1 = new AInt32(intervals[i][1]);
862 AInt32 field2 = new AInt32(rnd.nextInt() % 100);
863
864 byte[] f0 = field0.toBytes();
865 byte[] f1 = field1.toBytes();
866 byte[] f2 = field2.toBytes();
867
868 System.arraycopy(f0, 0, record, 0, 4);
869 System.arraycopy(f1, 0, record, 4, 4);
870 System.arraycopy(f2, 0, record, 8, 4);
871
872 print("INSERTING " + i + " : " + field0.getIntegerValue() + " " + field1.getIntegerValue() + "\n");
873
874 try {
875 btree.insert(record, leafFrame, interiorFrame, metaFrame);
876 } catch (Exception e) {
877 // e.printStackTrace();
878 }
879 }
880 // btree.printTree(leafFrame, interiorFrame);
881 // btree.printStats();
882
883 long end = System.currentTimeMillis();
884 long duration = end - start;
885 print("DURATION: " + duration + "\n");
886
887 // try a simple index scan
888
889 print("ORDERED SCAN:\n");
890 IBTreeCursor scanCursor = new BTreeRangeSearchCursor(leafFrame);
891 RangePredicate nullPred = new RangePredicate(true, null, null, null);
892 btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
893
894 try {
895 while (scanCursor.hasNext()) {
896 scanCursor.next();
897 byte[] array = scanCursor.getPage().getBuffer().array();
898 int recOffset = scanCursor.getOffset();
899 String rec = cmp.printRecord(array, recOffset);
900 print(rec + "\n");
901 }
902 } catch (Exception e) {
903 e.printStackTrace();
904 } finally {
905 scanCursor.close();
906 }
907
908 // try a range search
909 print("RANGE SEARCH:\n");
910 IBTreeCursor rangeCursor = new BTreeRangeSearchCursor(leafFrame);
911
912 AInt32 lowerBound = new AInt32(12);
913 AInt32 upperBound = new AInt32(19);
914 byte[] lbBytes = lowerBound.toBytes();
915 byte[] hbBytes = upperBound.toBytes();
916
917 byte[] lowKey = new byte[8];
918 byte[] highKey = new byte[8];
919
920 System.arraycopy(lbBytes, 0, lowKey, 0, 4);
921 System.arraycopy(lbBytes, 0, lowKey, 4, 4);
922
923 System.arraycopy(hbBytes, 0, highKey, 0, 4);
924 System.arraycopy(hbBytes, 0, highKey, 4, 4);
925
926 IComparator[] searchCmps = new IComparator[2];
927 searchCmps[0] = new Int32Comparator();
928 searchCmps[1] = new Int32Comparator();
929 MultiComparator searchCmp = new MultiComparator(searchCmps, fields);
930
931 print("INDEX RANGE SEARCH ON: " + cmp.printKey(lowKey, 0) + " " + cmp.printKey(highKey, 0) + "\n");
932
933 RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, searchCmp);
934 btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
935
936 try {
937 while (rangeCursor.hasNext()) {
938 rangeCursor.next();
939 byte[] array = rangeCursor.getPage().getBuffer().array();
940 int recOffset = rangeCursor.getOffset();
941 String rec = cmp.printRecord(array, recOffset);
942 print(rec + "\n");
943 }
944 } catch (Exception e) {
945 e.printStackTrace();
946 } finally {
947 rangeCursor.close();
948 }
949
950 btree.close();
951
952 bufferCache.close();
953 fileManager.close();
954
955 print("\n");
956 }
957
958 public static String randomString(int length, Random random) {
959 String s = Long.toHexString(Double.doubleToLongBits(random.nextDouble()));
960 StringBuilder strBuilder = new StringBuilder();
961 for (int i = 0; i < s.length() && i < length; i++) {
962 strBuilder.append(s.charAt(Math.abs(random.nextInt()) % s.length()));
963 }
964 return strBuilder.toString();
965 }
966}