LinearHashIndex


1   /*
2    * Copyright 2004-2006 H2 Group. Licensed under the H2 License, Version 1.0 (http://h2database.com/html/license.html).
3    * Initial Developer: H2 Group
4    */
5   package org.h2.index;
6   
7   import java.sql.SQLException  ;
8   
9   import org.h2.engine.Constants;
10  import org.h2.engine.Session;
11  import org.h2.message.Message;
12  import org.h2.result.Row;
13  import org.h2.result.SearchRow;
14  import org.h2.store.DataPage;
15  import org.h2.store.DiskFile;
16  import org.h2.store.Record;
17  import org.h2.store.RecordReader;
18  import org.h2.store.Storage;
19  import org.h2.table.Column;
20  import org.h2.table.TableData;
21  import org.h2.util.ObjectArray;
22  import org.h2.value.Value;
23  import org.h2.value.ValueArray;
24  
25  /**
26   * @author Thomas
27   */
28  public class LinearHashIndex extends Index implements RecordReader {
29  
30      // TODO index / linear hash: tune page size
31      // private static final int MAX_PAGE_SIZE = 256;
32      private static final int RECORDS_PER_BUCKET = 10;
33      private static final int UTILIZATION_FOR_SPLIT = 70;
34      private static final int UTILIZATION_FOR_MERGE = 60;
35      private int readCount;
36      // private static final boolean TRACE = false;
37      private DiskFile diskFile;
38      private Storage storage;
39      private TableData tableData;
40      private int bucketSize;
41      private int blocksPerBucket;
42      private int firstBucketBlock;
43      private LinearHashHead head;
44      private boolean needRebuild;
45      // private ObjectArray buckets = new ObjectArray();
46  
47      public LinearHashIndex(Session session, TableData table, int id, String   indexName, Column[] columns, IndexType indexType)
48              throws SQLException   {
49          super(table, id, indexName, columns, indexType);
50          this.tableData = table;
51          // TODO linear hash: currently, changes are not logged
52          String   name = database.getName()+"."+id+Constants.SUFFIX_HASH_FILE;
53          diskFile = new DiskFile(database, name, false, false, Constants.DEFAULT_CACHE_SIZE_LINEAR_INDEX);
54          diskFile.init();
55          bucketSize = 4 * DiskFile.BLOCK_SIZE - diskFile.getRecordOverhead();
56          blocksPerBucket = 4;
57          firstBucketBlock = 4;
58          storage = database.getStorage(id, diskFile);
59          storage.setReader(this);
60          rowCount = table.getRowCount();
61          int pos = storage.getNext(null);
62          if(pos == -1) {
63              truncate(session);
64              needRebuild = true;
65          } else {
66              head = (LinearHashHead) storage.getRecord(pos);
67          }
68      }
69  
70      void writeHeader(Session session) throws SQLException   {
71          storage.updateRecord(session, head);
72      }
73  
74  //    public String getString() throws Exception {
75  //        // TODO index / linear hash: debug code here
76  //        StringBuffer buff = new StringBuffer();
77  //        buff.append("buckets " + bucketCount);
78  //        int records = 0;
79  //        int chained = 0;
80  //        int foreign = 0;
81  //        int access = 0;
82  //        for (int i = 0; i < bucketCount; i++) {
83  //            LinearHashBucket bucket = getBucket(i);
84  //            if (bucket == null) {
85  //                throw Message.internal("bucket=" + i + " is empty");
86  //            }
87  //            if (bucket.getRecordSize() > RECORDS_PER_BUCKET) {
88  //                throw Message.internal("bucket=" + i + " records=" + bucket.getRecordSize());
89  //            }
90  //            records += bucket.getRecordSize();
91  //            if (bucket.getNextBucket() != -1) {
92  //                chained++;
93  //            }
94  //            for (int j = 0; j < bucket.getRecordSize(); j++) {
95  //                LinearHashEntry record = bucket.getRecord(j);
96  //                if (record.home != i) {
97  //                    foreign++;
98  //                }
99  //                int oldReadCount = readCount;
100 //                get(record.key);
101 //                access += (readCount - oldReadCount);
102 //            }
103 //        }
104 //        buff.append(" records " + records);
105 //        buff.append(" utilization " + getUtilization());
106 //        buff.append(" access " + ((0.0 + access) / records));
107 //        buff.append(" chained " + chained);
108 //        buff.append(" foreign " + foreign);
109 //        if (TRACE) {
110 //            for (int i = 0; i < bucketCount; i++) {
111 //                LinearHashBucket bucket = getBucket(i);
112 //                int f = getForeignHome(i);
113 //                if (f >= 0) {
114 //                    buff.append(" from " + f);
115 //                }
116 //                buff.append(i);
117 //                buff.append(" next ");
118 //                buff.append(bucket.getNextBucket());
119 //                buff.append("{");
120 //                for (int j = 0; j < bucket.getRecordSize(); j++) {
121 //                    if (j > 0) {
122 //                        buff.append(", ");
123 //                    }
124 //                    LinearHashEntry r = bucket.getRecord(j);
125 //                    buff.append(r.key.toString());
126 //                    if (r.home != i && r.home != f) {
127 //                        throw new Exception("MULTIPLE LINKS TO! " + buff.toString());
128 //                    }
129 //                }
130 //                buff.append("} ");
131 //            }
132 //        }
133 //        return buff.toString();
134 //
135 //    }
136 
137     private void add(Session session, Value key, int value) throws SQLException   {
138         // trace.debug("add "+key.toString() + " " + value);
139         if (getUtilization() >= UTILIZATION_FOR_SPLIT) {
140             split(session);
141         }
142         int hash = key.hashCode();
143         int home = getPos(hash);
144         int index = home;
145         LinearHashEntry record = new LinearHashEntry();
146         record.hash = hash;
147         record.key = key;
148         record.home = home;
149         record.value = value;
150         int free = getNextFree(home);
151         while (true) {
152 
153             LinearHashBucket bucket = getBucket(index);
154             if (bucket.getRecordSize() < RECORDS_PER_BUCKET) {
155                 addRecord(session, bucket, record);
156                 break;
157             }
158             // this bucket is full
159             int foreign = getForeignHome(index);
160             if (foreign >= 0 && foreign != home) {
161                 // move out foreign records - add this record - add foreign
162                 // records again
163                 ObjectArray old = new ObjectArray();
164                 moveOut(session, foreign, old);
165                 addRecord(session, bucket, record);
166                 addAll(session, old);
167                 break;
168             }
169             // there is already a link to next
170             if (bucket.getNextBucket() > 0) {
171                 index = bucket.getNextBucket();
172                 continue;
173             }
174 
175             int nextFree = getNextFree(free);
176             if (nextFree < 0) {
177                 // trace.debug("split because no chain " + head.bucketCount);
178                 split(session);
179                 add(session, key, value);
180                 break;
181             }
182 
183             // it's possible that the bucket was removed from the cache (if searching for a bucket with space scanned many buckets)
184             bucket = getBucket(index);
185 
186             bucket.setNext(session, free);
187             free = nextFree;
188             if (getForeignHome(free) >= 0) {
189                 throw Message.getInternalError("next already linked");
190             }
191             index = bucket.getNextBucket();
192         }
193     }
194 
195     private int getNextFree(int excluding) throws SQLException   {
196         for (int i = head.bucketCount - 1; i >= 0; i--) {
197             LinearHashBucket bucket = getBucket(i);
198             if (bucket.getRecordSize() >= RECORDS_PER_BUCKET) {
199                 continue;
200             }
201             if (getForeignHome(i) < 0 && i != excluding) {
202                 return i;
203             }
204         }
205         return -1;
206     }
207 
208     private int getForeignHome(int bucketId) throws SQLException   {
209         LinearHashBucket bucket = getBucket(bucketId);
210         for (int i = 0; i < bucket.getRecordSize(); i++) {
211             LinearHashEntry record = bucket.getRecord(i);
212             if (record.home != bucketId) {
213                 return record.home;
214             }
215         }
216         return -1;
217     }
218 
219     public int getPos(int hash) {
220         hash = Math.abs((hash << 7) - hash + (hash >>> 9) + (hash >>> 17));
221         int pos = hash % (head.baseSize + head.baseSize);
222         int len = head.bucketCount;
223         return pos < len ? pos : (pos % head.baseSize);
224     }
225 
226     private void split(Session session) throws SQLException   {
227         // trace.debug("split " + head.nextToSplit);
228         ObjectArray old = new ObjectArray();
229         moveOut(session, head.nextToSplit, old);
230         head.nextToSplit++;
231         if (head.nextToSplit >= head.baseSize) {
232             head.baseSize += head.baseSize;
233             head.nextToSplit = 0;
234         }
235         addBucket(session);
236         addAll(session, old);
237     }
238 
239     private void addAll(Session session, ObjectArray records) throws SQLException   {
240         for (int i = 0; i < records.size(); i++) {
241             LinearHashEntry r = (LinearHashEntry)records.get(i);
242             add(session, r.key, r.value);
243         }
244     }
245 
246     // moves all records of a bucket to the array (including chained)
247     private void moveOut(Session session, int home, ObjectArray storeIn) throws SQLException   {
248         LinearHashBucket bucket = getBucket(home);
249         int foreign = getForeignHome(home);
250         while (true) {
251             for (int i = 0; i < bucket.getRecordSize(); i++) {
252                 LinearHashEntry r = bucket.getRecord(i);
253                 if (r.home == home) {
254                     storeIn.add(r);
255                     removeRecord(session, bucket, i);
256                     i--;
257                 }
258             }
259             if (foreign >= 0) {
260                 // this block contains foreign records
261                 // and therefore all home records have been found
262                 // (and it would be an error to set next to -1)
263                 moveOut(session, foreign, storeIn);
264                 if(Constants.CHECK && getBucket(foreign).getNextBucket() != -1) {
265                     throw Message.getInternalError("moveout "+foreign);
266                 }
267                 return;
268             }
269             int next = bucket.getNextBucket();
270             if(Constants.CHECK && next >= head.bucketCount) {
271                 throw Message.getInternalError("next="+next+" max="+head.bucketCount);
272             }
273             if (next < 0) {
274                 break;
275             }
276             bucket.setNext(session, -1);
277             bucket = getBucket(next);
278         }
279     }
280 
281     private void merge(Session session) throws SQLException   {
282         if (head.bucketCount <= 1) {
283             return;
284         }
285         if (getUtilization() > UTILIZATION_FOR_MERGE) {
286             return;
287         }
288         ObjectArray old = new ObjectArray();
289         moveOut(session, head.nextToSplit, old);
290         head.nextToSplit--;
291         if (head.nextToSplit < 0) {
292             head.baseSize /= 2;
293             head.nextToSplit = head.baseSize - 1;
294         }
295         moveOut(session, head.nextToSplit, old);
296         moveOut(session, head.bucketCount - 1, old);
297         removeBucket(session);
298 
299 //        for(int i=0; i<head.bucketCount; i++) {
300 //            LinearHashBucket bucket = this.getBucket(i);
301 //            if(bucket.getNextBucket() >= head.bucketCount) {
302 //                System.out.println("error");
303 //            }
304 //        }
305 
306         addAll(session, old);
307 //        int testALot;
308 //        for(int i=0; i<head.bucketCount; i++) {
309 //            LinearHashBucket bucket = this.getBucket(i);
310 //            if(bucket.getNextBucket() >= head.bucketCount) {
311 //                System.out.println("error");
312 //            }
313 //        }
314     }
315 
316     private boolean isEquals(LinearHashEntry r, int hash, Value key) throws SQLException   {
317         if (r.hash == hash) {
318             if(r.key == null) {
319                 r.key = getKey(tableData.getRow(r.value));
320             }
321             if(database.compareTypeSave(r.key, key)==0) {
322                 return true;
323             }
324         }
325         return false;
326     }
327 
328     private int get(Value key) throws SQLException   {
329         int hash = key.hashCode();
330         int home = getPos(hash);
331         LinearHashBucket bucket = getBucket(home);
332         while (true) {
333             for (int i = 0; i < bucket.getRecordSize(); i++) {
334                 LinearHashEntry r = bucket.getRecord(i);
335                 if(isEquals(r, hash, key)) {
336                     return r.value;
337                 }
338             }
339             if (bucket.getNextBucket() < 0) {
340                 return -1;
341             }
342             bucket = getBucket(bucket.getNextBucket());
343         }
344     }
345 
346     private void removeRecord(Session session, LinearHashBucket bucket, int index) throws SQLException   {
347         bucket.removeRecord(session, index);
348         head.recordCount--;
349         rowCount--;
350     }
351 
352     private void addRecord(Session session, LinearHashBucket bucket, LinearHashEntry entry) throws SQLException   {
353         bucket.addRecord(session, entry);
354         head.recordCount++;
355         rowCount++;
356     }
357 
358     private void remove(Session session, Value key) throws SQLException   {
359         merge(session);
360         // trace.debug("remove "+key.toString());
361         int hash = key.hashCode();
362         int home = getPos(hash);
363         int now = home;
364         while (true) {
365             LinearHashBucket bucket = getBucket(now);
366             for (int i = 0; i < bucket.getRecordSize(); i++) {
367                 LinearHashEntry r = bucket.getRecord(i);
368                 if(isEquals(r, hash, key)) {
369                     removeRecord(session, bucket, i);
370                     if (home != now) {
371                         ObjectArray old = new ObjectArray();
372                         moveOut(session, home, old);
373                         addAll(session, old);
374                     }
375                     return;
376                 }
377             }
378             int next = bucket.getNextBucket();
379             if (next < 0) {
380                 throw Message.getInternalError("not found");
381             }
382             now = next;
383         }
384     }
385 
386     private int getBlockId(int i) {
387         return i * blocksPerBucket + firstBucketBlock;
388     }
389 
390     private LinearHashBucket getBucket(int i) throws SQLException   {
391         readCount++;
392         if(Constants.CHECK && i >= head.bucketCount) {
393             throw Message.getInternalError("get="+i+" max="+head.bucketCount);
394         }
395         // trace.debug("read " + i);
396         // return (LinearHashBucket) buckets.get(i);
397         i = getBlockId(i);
398         // System.out.println("getBucket "+i);
399         LinearHashBucket bucket = (LinearHashBucket) storage.getRecord(i);
400         return bucket;
401     }
402 
403     private void addBucket(Session session) throws SQLException   {
404         LinearHashBucket bucket = new LinearHashBucket(this);
405         storage.addRecord(session, bucket, getBlockId(head.bucketCount));
406         // bucket.setPos(buckets.size());
407         // buckets.add(bucket);
408         //System.out.println("addBucket "+bucket.getPos());
409         if(Constants.CHECK && bucket.getBlockCount() > blocksPerBucket) {
410             throw Message.getInternalError("blocks="+bucket.getBlockCount());
411         }
412         head.bucketCount++;
413     }
414 
415     private void removeBucket(Session session) throws SQLException   {
416         // buckets.remove(head.bucketCount-1);
417         int pos = getBlockId(head.bucketCount-1);
418         //System.out.println("removeBucket "+pos);
419         storage.removeRecord(session, pos);
420         head.bucketCount--;
421     }
422 
423     private int getUtilization() {
424         return 100 * head.recordCount / (head.bucketCount * RECORDS_PER_BUCKET);
425     }
426 
427     void updateBucket(Session session, LinearHashBucket bucket) throws SQLException   {
428         storage.updateRecord(session, bucket);
429     }
430 
431     public Record read(DataPage s) throws SQLException   {
432         char c = (char)s.readByte();
433         if (c == 'B') {
434             return new LinearHashBucket(this, s);
435         } else if (c == 'H') {
436             return new LinearHashHead(this, s);
437         } else {
438             throw Message.getSQLException(Message.FILE_CORRUPTED_1, getName());
439         }
440     }
441 
442     public void close(Session session) throws SQLException   {
443         // TODO flush from time to time (after a few seconds of no activity or so)
444         writeHeader(session);
445         diskFile.close();
446     }
447 
448     public void add(Session session, Row row) throws SQLException   {
449         Value key = getKey(row);
450         if(get(key) != -1) {
451             // TODO index duplicate key for hash indexes: is this allowed?
452             throw getDuplicateKeyException();
453         }
454         add(session, key, row.getPos());
455     }
456 
457     public void remove(Session session, Row row) throws SQLException   {
458         remove(session, getKey(row));
459     }
460 
461     private Value getKey(SearchRow row) throws SQLException   {
462         if (columns.length == 1) {
463             Column column = columns[0];
464             int index = column.getColumnId();
465             Value v = row.getValue(index);
466             return v;
467         }
468         Value[] list = new Value[columns.length];
469         for (int i = 0; i < columns.length; i++) {
470             Column column = columns[i];
471             int index = column.getColumnId();
472             Value v = row.getValue(index);
473             list[i] = v;
474         }
475         return ValueArray.get(list);
476     }
477 
478     public Cursor find(Session session, SearchRow first, SearchRow last) throws SQLException   {
479         if(first == null || last == null) {
480             // TODO hash index: should additionally check if values are the same
481             throw Message.getInternalError();
482         }
483         int key = get(getKey(first));
484         if(key == -1) {
485             return new LinearHashCursor(null);
486         }
487         return new LinearHashCursor(tableData.getRow(key));
488     }
489 
490     public int getCost(int[] masks) throws SQLException   {
491         for (int i = 0; i < columns.length; i++) {
492             Column column = columns[i];
493             int index = column.getColumnId();
494             int mask = masks[index];
495             if ((mask & IndexCondition.EQUALITY) != IndexCondition.EQUALITY) {
496                 return Integer.MAX_VALUE;
497             }
498         }
499         return 100;
500     }
501 
502     public void remove(Session session) throws SQLException   {
503         storage.delete(session);
504         diskFile.delete();
505     }
506 
507     public void truncate(Session session) throws SQLException   {
508         storage.truncate(session);
509         // buckets.clear();
510         head = new LinearHashHead(this);
511         head.recordCount = 0;
512         head.bucketCount = 0;
513         head.baseSize = 1;
514         head.nextToSplit = 0;
515         readCount = 0;
516         storage.addRecord(session, head, 0);
517         addBucket(session);
518         rowCount = 0;
519     }
520 
521     public void checkRename() throws SQLException   {
522     }
523 
524     public boolean needRebuild() {
525         return needRebuild;
526     }
527 
528     public int getBucketSize() {
529         return bucketSize;
530     }
531 
532     public boolean canGetFirstOrLast(boolean first) {
533         return false;
534     }
535 
536     public Value findFirstOrLast(Session session, boolean first) throws SQLException   {
537         throw Message.getUnsupportedException();
538     }
539 
540 }
541
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags