001: /*
002: This source file is part of Smyle, a database library.
003: For up-to-date information, see http://www.drjava.de/smyle
004: Copyright (C) 2001 Stefan Reich (doc@drjava.de)
005:
006: This library is free software; you can redistribute it and/or
007: modify it under the terms of the GNU Lesser General Public
008: License as published by the Free Software Foundation; either
009: version 2.1 of the License, or (at your option) any later version.
010:
011: This library is distributed in the hope that it will be useful,
012: but WITHOUT ANY WARRANTY; without even the implied warranty of
013: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: Lesser General Public License for more details.
015:
016: You should have received a copy of the GNU Lesser General Public
017: License along with this library; if not, write to the Free Software
018: Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
019:
020: For full license text, see doc/license/lgpl.txt in this distribution
021: */
022:
023: package drjava.smyle.tests;
024:
025: import java.io.*;
026: import junit.framework.*;
027: import java.util.*;
028: import drjava.util.*;
029: import drjava.gjutil.*;
030: import drjava.smyle.*;
031: import drjava.smyle.testtypes.*;
032: import drjava.smyle.core.*;
033: import drjava.smyle.core.indexing.*;
034: import drjava.smyle.meta.*;
035: import org.artsProject.mcop.core.*;
036: import org.artsProject.util.*;
037:
038: public class IndexTest extends DiskStoreTestBase {
039: public IndexTest(String name) {
040: super (name);
041: }
042:
043: TableImpl<Person> tableImpl;
044: PersistentBTree<UniversalKey, ChunkRefs> index;
045: IndexAdvisor<Pair<IndexProfile, Function>> indexAdvisor;
046: int ageStats, nameStats;
047: Index<Person> idx;
048: IndexProfile profile;
049: Person_filter filter;
050:
051: public void setUp() throws Exception {
052: super .setUp();
053: snapshot.commit();
054: store.enableIndexing();
055: getNewSnapshot();
056: tableImpl = (TableImpl<Person>) table;
057: ageStats = 0;
058: filter = null;
059: }
060:
061: void checkIndex() throws Exception {
062: // convert tree to map
063:
064: Iterator<Map.Entry<UniversalKey, ChunkRefs>> iIndex = BTreeTestBase
065: .treeToMap(index).entrySet().iterator();
066:
067: // walk through map and compare with table
068:
069: Iterator<Person> iTable = table.iterator();
070: while (iIndex.hasNext()) {
071: Map.Entry<UniversalKey, ChunkRefs> eI = iIndex.next();
072: ArrayList<ChunkRef> v = eI.getValue().list;
073: for (int i = 0; i < v.size(); i++) {
074: assertTrue(
075: "table has next at " + i + " of " + v.size(),
076: iTable.hasNext());
077: Person eT = iTable.next();
078: assertEquals(new UniversalKey(eT.age), eI.getKey());
079: assertEquals(eT, tableImpl.loadElement(v.get(i)));
080: }
081: }
082: assertTrue(!iTable.hasNext());
083: }
084:
085: /** builds an index that is inconsistent with the table contents
086: (prerequisite to verify that certain methods use the index) */
087: void buildInconsistentIndex() throws Exception {
088: table.add(john);
089: table.add(anne);
090: table.add(jane);
091: // john and jane have same age (test duplicates)
092: /*List<Function> fields = Collections.singletonList((Function) Person.f_age);
093: index = tableImpl.buildIndex(fields);
094:
095: // make table and index inconsistent to verify that
096: // queries go through the index
097: table.clear();
098: tableImpl.setIndex(fields, index);XX*/
099: }
100:
101: public void testOrderByOverCutIndex() throws Exception {
102: tableImpl.setMaxKeyLength(4);
103: indexName();
104: Person john1 = new Person("John1", 23);
105: Person john2 = new Person("John2", 23);
106: table.add(john2);
107: table.add(john1);
108:
109: TestUtil.checkIterator(tableImpl.iterator(new Person_filter()
110: .orderByName()), new Person[] { anne, john, john1,
111: john2 });
112: }
113:
114: public void testOrderByPlusFilter() throws Exception {
115: buildInconsistentIndex();
116:
117: TestUtil.checkIterator(tableImpl.iterator(new Person_filter()
118: .ageEquals(23).orderByName().reverse()), new Person[] {
119: john, jane });
120: }
121:
122: public void testIndexedPlusOtherField() throws Exception {
123: buildInconsistentIndex();
124:
125: // iterate
126:
127: TestUtil.checkIterator(tableImpl.iterator(new Person_filter()
128: .nameEquals("John").ageEquals(23)),
129: new Person[] { john });
130: TestUtil.checkIterator(tableImpl.iterator(new Person_filter()
131: .ageEquals(23).nameEquals("John")),
132: new Person[] { john });
133: TestUtil.checkIterator(tableImpl.iterator(new Person_filter()
134: .ageEquals(21).nameEquals("John")), new Person[] {});
135: }
136:
137: public void testContainsOverIndex() throws Exception {
138: buildInconsistentIndex();
139:
140: assertTrue(table.contains(new Person_filter().ageEquals(23)));
141: assertTrue(!table.contains(new Person_filter().ageEquals(99)));
142: }
143:
144: /*public void testIndexOfOverIndex() throws Exception {
145: indexAge();
146:
147: assertEquals(0, table.indexOf(new Person_filter().ageEquals(23)));
148: assertEquals(1, table.indexOf(new Person_filter().ageEquals(21)));
149: assertEquals(-1, table.indexOf(new Person_filter().ageEquals(99)));
150: }*/
151:
152: public void testIndexOfObjectOverIndex() throws Exception {
153: indexAge();
154:
155: assertEquals(0, table.indexOf(john));
156: assertEquals(1, table.indexOf(anne));
157: assertEquals(-1, table.indexOf(jane));
158: }
159:
160: public void testRemoveAllOverIndex() throws Exception {
161: indexAge();
162: tableImpl.removeAll(filter = new Person_filter().ageEquals(95));
163: TestUtil.checkIterator(table.iterator(), new Person[] { john,
164: anne });
165: tableImpl.removeAll(new Person_filter().ageEquals(23));
166: TestUtil.checkIterator(table.iterator(), new Person[] { anne });
167:
168: // indirect way to check that index was used
169: ageStats = 0; // because filter changed
170: assertAgeStats(0);
171: }
172:
173: /*public void testRemoveAllOverCutIndex() throws Exception {
174: tableImpl.setMaxKeyLength(4);
175: indexName();
176: tableImpl.add(new Person("Horst", 45));
177: tableImpl.removeAll(new Person_filter().nameEquals("Horst"));
178: TestUtil.checkIterator(table.iterator(), new Person[] {john, anne});
179: }*/
180:
181: void assertAgeStats(int diff) throws Exception {
182: indexAdvisor = tableImpl.getIndexAdvisor();
183: IndexProfile profile = QueryOptimizer.createProfile(filter);
184: Pair<IndexProfile, Function> key = new Pair<IndexProfile, Function>(
185: profile, Person.f_age);
186: assertEquals("Looking for " + key + " in " + indexAdvisor,
187: ageStats += diff, indexAdvisor.getStats(key));
188: }
189:
190: void assertNameStats(int diff) throws Exception {
191: //assertEquals(nameStats += diff, indexAdvisor.getStats(Person.f_name));
192: }
193:
194: void fillTableAndPerformQuery() throws Exception {
195: table.add(john);
196: table.add(anne);
197: table.count(filter = new Person_filter().nameEquals("Anne")
198: .ageEquals(21));
199: assertAgeStats(1);
200: }
201:
202: public void testTableInformsIndexAdvisor() throws Exception {
203: indexAdvisor = tableImpl.getIndexAdvisor();
204: fillTableAndPerformQuery();
205: table.contains(filter = new Person_filter().ageEquals(9));
206: ageStats = 0; // because filter changed
207: assertAgeStats(2);
208: table.iterator(filter = new Person_filter().orderByAge());
209: ageStats = 0; // because filter changed
210: assertAgeStats(2);
211: table.removeAll(filter = new Person_filter().ageEquals(21));
212: assertAgeStats(1);
213:
214: //assertEquals(1, indexAdvisor.getStats(Person.f_name));
215: }
216:
217: /*public void testAdvisorResetOnSchemaChange() throws Exception {
218: indexAdvisor = tableImpl.getIndexAdvisor();
219: fillTableAndPerformQuery();
220:
221: snapshot.forget();
222: snapshot = store.mutableSnapshot();
223: Table<ExtendedPerson> table = snapshot.getTable("person", ExtendedPerson.getTypeInfo());
224: tableImpl = (TableImpl) table;
225: indexAdvisor = tableImpl.getIndexAdvisor();
226: assertAgeStats(0);
227: }*/
228:
229: public void testAdvisorPreserved() throws Exception {
230: indexAdvisor = tableImpl.getIndexAdvisor();
231: fillTableAndPerformQuery();
232:
233: snapshot.forget();
234: getNewSnapshot();
235: //XXassertAgeStats(0);
236: indexAdvisor = tableImpl.getIndexAdvisor();
237: //XXassertAgeStats(0);
238: }
239:
240: void prepareIndexCreation() throws Exception {
241: indexAdvisor = tableImpl.getIndexAdvisor();
242: indexAdvisor.setInitialHurdle(1);
243: table.add(john);
244: table.add(anne);
245: }
246:
247: void indexAge() throws Exception {
248: prepareIndexCreation();
249:
250: // iterate to trigger index creation
251: Iterator<Person> i = tableImpl
252: .iterator(filter = new Person_filter().orderByAge());
253: TestUtil.checkIterator(i, new Person[] { anne, john });
254: assertAgeStats(2);
255: }
256:
257: void indexName() throws Exception {
258: prepareIndexCreation();
259:
260: // iterate to trigger index creation
261: Iterator<Person> i = tableImpl
262: .iterator(filter = new Person_filter().orderByName());
263: TestUtil.checkIterator(i, new Person[] { anne, john });
264: assertNameStats(2);
265: }
266:
267: void assertAgeIndexCreated() throws Exception {
268: assertEquals(1, tableImpl.numIndexes());
269: //XXassertEquals(Person.f_age, tableImpl.getIndexedField());
270: Iterator<Person> i = tableImpl.iterator(new Person_filter()
271: .orderByAge());
272: TestUtil.checkIterator(i, new Person[] { anne, john });
273: }
274:
275: void assertNameIndexCreated() throws Exception {
276: assertEquals(1, tableImpl.numIndexes());
277: //XXassertEquals(Person.f_name, tableImpl.getIndexedField());
278: Iterator<Person> i = tableImpl.iterator(new Person_filter()
279: .orderByName());
280: TestUtil.checkIterator(i, new Person[] { anne, john });
281: }
282:
283: public void testIntIndex() throws Exception {
284: indexAge();
285: assertAgeIndexCreated();
286: }
287:
288: public void testStringIndex() throws Exception {
289: indexName();
290: assertNameIndexCreated();
291:
292: table.add(new Person(null, 0));
293: assertTrue(table.contains(new Person_filter().nameEquals(null)));
294: }
295:
296: public void testCutIndex() throws Exception {
297: tableImpl.setMaxKeyLength(4);
298: indexName();
299: assertNameIndexCreated();
300: }
301:
302: public void testLongIndex() throws Exception {
303: Table<DataTypes> table = snapshot.getTable("datatypes",
304: DataTypes.getTypeInfo());
305: TableImpl tableImpl = (TableImpl) (Table) table;
306: tableImpl.getIndexAdvisor().setInitialHurdle(1);
307:
308: DataTypes r1 = new DataTypes(), r2 = new DataTypes();
309: r1.strct = new JustName();
310: r2.strct = new JustName();
311: r1.ll = 12345678901234L;
312: r2.ll = -12345678901234L;
313: table.add(r1);
314: table.add(r2);
315:
316: // iterate to trigger indexing
317: TestUtil.checkIterator(table.iterator(new DataTypes_filter()
318: .orderByLl()), new DataTypes[] { r2, r1 });
319:
320: // assert index was created
321: //XXassertEquals(DataTypes.f_ll, tableImpl.getIndexedField());
322: TestUtil.checkIterator(table.iterator(new DataTypes_filter()
323: .orderByLl()), new DataTypes[] { r2, r1 });
324: }
325:
326: /*public void testIndexMaintenance() throws Exception {
327: indexAge();
328: index = tableImpl.getIndex();
329: indexAdvisor.freeze();
330:
331: table.clear();
332: checkIndex();
333:
334: table.add(john);
335: table.add(0, anne);
336: checkIndex();
337:
338: table.set(1, jane);
339: checkIndex();
340:
341: table.remove(john);
342: checkIndex();
343:
344: table.add(john);
345: Iterator<Person> i = table.iterator();
346: i.next();
347: i.remove();
348: checkIndex();
349:
350: table.add(john);
351: // ordered by non-indexed field (SortedTableScan)
352: i = table.iterator(new Person_filter().orderByName());
353: i.next();
354: i.remove();
355: checkIndex();
356: }XX*/
357:
358: /*public void testIndexScanRemove() throws Exception {
359: indexAge();
360: index = tableImpl.getIndex();
361: indexAdvisor.freeze();
362:
363: // ordered by indexed field (IndexScan)
364: Iterator<Person> i = table.iterator(new Person_filter().orderByAge());
365: assertEquals(anne, i.next());
366: i.remove();
367: assertTrue(i.hasNext());
368: assertEquals(john, i.next());
369: assertTrue(!i.hasNext());
370: assertEquals(john, table.get(0));
371: assertEquals(1, table.size());
372: checkIndex();
373: }XX*/
374:
375: /*public void testIndexScanRemoveSameValue() throws Exception {
376: indexAge();
377: index = tableImpl.getIndex();
378: indexAdvisor.freeze();
379:
380: table.clear();
381: for (int age = 15; age <= 25; age += 10)
382: for (int n = 0; n < 5; n++)
383: table.add(new Person(String.valueOf(n), age));
384:
385: Iterator<Person> i = null;
386: for (int age = 15; age <= 25; age += 10) {
387: i = table.iterator(new Person_filter().orderByAge());
388: for (int n = 0; n < 5; n++) {
389: assertTrue(i.hasNext());
390: assertEquals(new Person(String.valueOf(n), age), i.next());
391: i.remove();
392: }
393: }
394: assertTrue(!i.hasNext());
395: assertEquals(0, table.size());
396: checkIndex();
397: }XX*/
398:
399: /** asserts an index in an old snapshot is still accessible
400: even it it was cleared in a more recent snapshot */
401: public void testIndexPreserved() throws Exception {
402: store.setWriteLatency(0);
403: indexAge();
404: commitAndGetNewSnapshot();
405: Snapshot oldSnapshot = store.snapshot();
406: Table<Person> oldTable = oldSnapshot.getTable("person", Person
407: .getTypeInfo());
408: assertEquals(1, tableImpl.numIndexes());
409: ((TableImpl) (Table) table).clearIndexes();
410: assertEquals(1, tableImpl.numIndexes());
411: snapshot.commit();
412: store.collectGarbage();
413: tableImpl = (TableImpl) (Table) oldTable;
414: assertAgeIndexCreated();
415: }
416:
417: /** test "offline" table chunk collection code in SnapshotImpl */
418: public void testIndexPreservedIfTableNotOpen() throws Exception {
419: indexAge();
420: snapshot.commit();
421: rotate();
422: tableImpl = (TableImpl) (Table) table;
423: assertAgeIndexCreated();
424: }
425:
426: public void testIndexBuiltOnRemoveAll() throws Exception {
427: prepareIndexCreation();
428: table.removeAll(new Person_filter().ageEquals(0));
429: assertAgeIndexCreated();
430: }
431:
432: void indexNameIC() throws Exception {
433: prepareIndexCreation();
434:
435: // build subList to trigger index creation
436: Iterator<Person> i = tableImpl.subList(
437: new Person_filter().nameEqualsIgnoreCase("anne"))
438: .iterator();
439: TestUtil.checkIterator(i, new Person[] { anne });
440:
441: // assert this isn't counted for the name field itself
442: assertNameStats(0);
443: }
444:
445: void assertNameICIndexCreated() throws Exception {
446: assertEquals("Index created", 1, tableImpl.numIndexes());
447: //assertEquals(Person.f_name, tableImpl.getIndexedField());
448: Iterator<Person> i = tableImpl.iterator(new Person_filter()
449: .nameEqualsIgnoreCase("anne"));
450: TestUtil.checkIterator(i, new Person[] { anne });
451: }
452:
453: public void testICIndex() throws Exception {
454: indexNameIC();
455: assertNameICIndexCreated();
456: }
457:
458: /*public void testMultidimIndex() throws Exception {
459: indexAge();
460:
461: // iterate to trigger index creation
462: for (int n = 0; n < 2; n++) {
463: Iterator<Person> i = tableImpl.iterator(new Person_filter().orderByName());
464: TestUtil.checkIterator(i, new Person[] {anne, john});
465: assertNameStats(2);
466: }
467:
468: assertNotNull(tableImpl.getIndex());
469: assertEquals(Person.f_age, tableImpl.getIndexedFields().get(0));
470: assertEquals(Person.f_name, tableImpl.getIndexedFields().get(1));
471:
472: // query on both dimensions at once
473: assertTrue(!tableImpl.contains(new Person_filter().nameEquals("John").ageEquals(21)));
474: assertNameStats(0);
475: assertAgeStats(0);
476:
477: // filter on one dimension, sort on other one
478: table.add(jane);
479: TestUtil.checkIterator(table.iterator(new Person_filter().ageEquals(23).orderByName()),
480: new Person[] {jane, john});
481:
482: // sort on one of the two dimensions
483: TestUtil.checkIterator(table.iterator(new Person_filter().orderByName().reverse()),
484: new Person[] {john, jane, anne});
485: }XX*/
486:
487: public void testMultidimStress() throws Exception {
488: int n = 50;
489: tableImpl.getIndexAdvisor().setInitialHurdle(1);
490:
491: for (int i = 0; i < n; i++) {
492: table.add(new Person(String.valueOf(i), i));
493: }
494:
495: for (int i = 0; i < n; i++) {
496: table.removeAll(i % 2 == 0 ? new Person_filter()
497: .ageEquals(i) : new Person_filter()
498: .nameEquals(String.valueOf(i)));
499: if (table.size() != n - i - 1)
500: assertEquals("Table size", n - i - 1, table.size());
501: }
502: }
503:
504: public void testOrderByTwoFieldsFirstIndexed() throws Exception {
505: indexAge();
506:
507: table.clear();
508: table.add(john);
509: table.add(anne);
510: table.add(jane);
511:
512: Iterator<Person> i = table.iterator(new Person_filter()
513: .orderByAge().orderByName());
514: TestUtil.checkIterator(i, new Person[] { anne, jane, john });
515: }
516:
517: public void testBooleanIndex() throws Exception {
518: Table<VeryExtendedPerson> table = snapshot.getTable("ext",
519: VeryExtendedPerson.getTypeInfo());
520: TableImpl<VeryExtendedPerson> tableImpl = (TableImpl<VeryExtendedPerson>) table;
521: indexAdvisor = tableImpl.getIndexAdvisor();
522: indexAdvisor.setInitialHurdle(1);
523: VeryExtendedPerson john = new VeryExtendedPerson().name("John")
524: .married(true), anne = new VeryExtendedPerson().name(
525: "Anne").married(false);
526: table.add(john);
527: table.add(anne);
528:
529: // iterate to trigger index creation
530: Iterator<VeryExtendedPerson> i = tableImpl
531: .iterator(new VeryExtendedPerson_filter()
532: .orderByMarried());
533: TestUtil.checkIterator(i,
534: new VeryExtendedPerson[] { anne, john });
535:
536: /*assertNotNull(tableImpl.getIndex());
537: assertEquals(VeryExtendedPerson.f_married, tableImpl.getIndexedFields().get(0));XX*/
538:
539: // check index
540: i = tableImpl.iterator(new VeryExtendedPerson_filter()
541: .orderByMarried());
542: TestUtil.checkIterator(i,
543: new VeryExtendedPerson[] { anne, john });
544: }
545:
546: /*public void testIndexConstruction() {
547: createNameIndex();
548: checkIndex(new UniversalKey("John"));
549: }
550:
551: public void testAddField() {
552: createNameIndex();
553: idx.addField((Function) Person.f_age);
554: checkIndex(UniversalKey.concatDimensions(new java.lang.Object[] { "John", new Integer(john.age) }));
555: }
556:
557: void createNameIndex() {
558: table = snapshot.getTable("people", Person.getTypeInfo());
559: table.add(john);
560:
561: table.addIndex(
562: idx = new Index<Person>((TableImpl<Person>) table, new Function[] { Person.f_name });
563: }
564:
565: void checkIndex(UniversalKey expectedKey) {
566: // check tree contents
567: MapIterator<UniversalKey,ChunkRefs> i = idx.getTree().iterate();
568: assertTrue(i.hasNext());
569: i.next(); // don't check element...
570: assertEquals(expectedKey, i.getKey());
571: assertFalse(i.hasNext());
572: }*/
573: }
|