001: /*
002: * Copyright 2004-2008 H2 Group. Licensed under the H2 License, Version 1.0
003: * (http://h2database.com/html/license.html).
004: * Initial Developer: H2 Group
005: */
006: package org.h2.index;
007:
008: import java.sql.SQLException;
009:
010: import org.h2.constant.ErrorCode;
011: import org.h2.constant.SysProperties;
012: import org.h2.engine.Constants;
013: import org.h2.engine.Session;
014: import org.h2.message.Message;
015: import org.h2.result.Row;
016: import org.h2.result.SearchRow;
017: import org.h2.store.DataPage;
018: import org.h2.store.DiskFile;
019: import org.h2.store.Record;
020: import org.h2.store.RecordReader;
021: import org.h2.store.Storage;
022: import org.h2.table.Column;
023: import org.h2.table.IndexColumn;
024: import org.h2.table.TableData;
025: import org.h2.util.ObjectArray;
026: import org.h2.value.Value;
027: import org.h2.value.ValueArray;
028:
029: /**
030: * A linear hash index implementation.
031: * Theoretically, this index type should scale better than a b-tree index.
032: * At this time, this index is not fully tested.
033: */
034: public class LinearHashIndex extends BaseIndex implements RecordReader {
035:
036: // TODO index / linear hash: tune page size
037: // private static final int MAX_PAGE_SIZE = 256;
038: private static final int RECORDS_PER_BUCKET = 10;
039: private static final int UTILIZATION_FOR_SPLIT = 70;
040: private static final int UTILIZATION_FOR_MERGE = 60;
041: private int readCount;
042: // private static final boolean TRACE = false;
043: private DiskFile diskFile;
044: private Storage storage;
045: private TableData tableData;
046: private int bucketSize;
047: private int blocksPerBucket;
048: private int firstBucketBlock;
049: private LinearHashHead head;
050: private boolean needRebuild;
051:
052: // private ObjectArray buckets = new ObjectArray();
053:
054: public LinearHashIndex(Session session, TableData table, int id,
055: String indexName, IndexColumn[] columns, IndexType indexType)
056: throws SQLException {
057: super (table, id, indexName, columns, indexType);
058: this .tableData = table;
059: // TODO linear hash: currently, changes are not logged
060: String name = database.getName() + "." + id
061: + Constants.SUFFIX_HASH_FILE;
062: diskFile = new DiskFile(database, name, "rw", false, false,
063: Constants.DEFAULT_CACHE_SIZE_LINEAR_INDEX);
064: diskFile.init();
065: bucketSize = 4 * DiskFile.BLOCK_SIZE
066: - diskFile.getRecordOverhead();
067: blocksPerBucket = 4;
068: firstBucketBlock = 4;
069: storage = database.getStorage(id, diskFile);
070: storage.setReader(this );
071: rowCount = table.getRowCount(session);
072: int pos = storage.getNext(null);
073: if (pos == -1) {
074: truncate(session);
075: needRebuild = true;
076: } else {
077: head = (LinearHashHead) storage.getRecord(session, pos);
078: }
079: }
080:
081: void writeHeader(Session session) throws SQLException {
082: storage.updateRecord(session, head);
083: }
084:
085: // public String getString() throws Exception {
086: // // TODO index / linear hash: debug code here
087: // StringBuffer buff = new StringBuffer();
088: // buff.append("buckets " + bucketCount);
089: // int records = 0;
090: // int chained = 0;
091: // int foreign = 0;
092: // int access = 0;
093: // for (int i = 0; i < bucketCount; i++) {
094: // LinearHashBucket bucket = getBucket(i);
095: // if (bucket == null) {
096: // throw Message.internal("bucket=" + i + " is empty");
097: // }
098: // if (bucket.getRecordSize() > RECORDS_PER_BUCKET) {
099: // throw Message.internal(
100: // "bucket=" + i + " records=" + bucket.getRecordSize());
101: // }
102: // records += bucket.getRecordSize();
103: // if (bucket.getNextBucket() != -1) {
104: // chained++;
105: // }
106: // for (int j = 0; j < bucket.getRecordSize(); j++) {
107: // LinearHashEntry record = bucket.getRecord(j);
108: // if (record.home != i) {
109: // foreign++;
110: // }
111: // int oldReadCount = readCount;
112: // get(record.key);
113: // access += (readCount - oldReadCount);
114: // }
115: // }
116: // buff.append(" records " + records);
117: // buff.append(" utilization " + getUtilization());
118: // buff.append(" access " + ((0.0 + access) / records));
119: // buff.append(" chained " + chained);
120: // buff.append(" foreign " + foreign);
121: // if (TRACE) {
122: // for (int i = 0; i < bucketCount; i++) {
123: // LinearHashBucket bucket = getBucket(i);
124: // int f = getForeignHome(i);
125: // if (f >= 0) {
126: // buff.append(" from " + f);
127: // }
128: // buff.append(i);
129: // buff.append(" next ");
130: // buff.append(bucket.getNextBucket());
131: // buff.append("{");
132: // for (int j = 0; j < bucket.getRecordSize(); j++) {
133: // if (j > 0) {
134: // buff.append(", ");
135: // }
136: // LinearHashEntry r = bucket.getRecord(j);
137: // buff.append(r.key.toString());
138: // if (r.home != i && r.home != f) {
139: // throw new Exception(
140: // "MULTIPLE LINKS TO! " + buff.toString());
141: // }
142: // }
143: // buff.append("} ");
144: // }
145: // }
146: // return buff.toString();
147: //
148: // }
149:
150: private void add(Session session, Value key, int value)
151: throws SQLException {
152: // trace.debug("add "+key.toString() + " " + value);
153: if (getUtilization() >= UTILIZATION_FOR_SPLIT) {
154: split(session);
155: }
156: int hash = key.hashCode();
157: int home = getPos(hash);
158: int index = home;
159: LinearHashEntry record = new LinearHashEntry();
160: record.hash = hash;
161: record.key = key;
162: record.home = home;
163: record.value = value;
164: int free = getNextFree(session, home);
165: while (true) {
166:
167: LinearHashBucket bucket = getBucket(session, index);
168: if (bucket.getRecordSize() < RECORDS_PER_BUCKET) {
169: addRecord(session, bucket, record);
170: break;
171: }
172: // this bucket is full
173: int foreign = getForeignHome(session, index);
174: if (foreign >= 0 && foreign != home) {
175: // move out foreign records - add this record - add foreign
176: // records again
177: ObjectArray old = new ObjectArray();
178: moveOut(session, foreign, old);
179: addRecord(session, bucket, record);
180: addAll(session, old);
181: break;
182: }
183: // there is already a link to next
184: if (bucket.getNextBucket() > 0) {
185: index = bucket.getNextBucket();
186: continue;
187: }
188:
189: int nextFree = getNextFree(session, free);
190: if (nextFree < 0) {
191: // trace.debug("split because no chain " + head.bucketCount);
192: split(session);
193: add(session, key, value);
194: break;
195: }
196:
197: // it's possible that the bucket was removed from
198: // the cache (if searching for a bucket with space
199: // scanned many buckets)
200: bucket = getBucket(session, index);
201:
202: bucket.setNext(session, free);
203: free = nextFree;
204: if (getForeignHome(session, free) >= 0) {
205: throw Message.getInternalError("next already linked");
206: }
207: index = bucket.getNextBucket();
208: }
209: }
210:
211: private int getNextFree(Session session, int excluding)
212: throws SQLException {
213: for (int i = head.bucketCount - 1; i >= 0; i--) {
214: LinearHashBucket bucket = getBucket(session, i);
215: if (bucket.getRecordSize() >= RECORDS_PER_BUCKET) {
216: continue;
217: }
218: if (getForeignHome(session, i) < 0 && i != excluding) {
219: return i;
220: }
221: }
222: return -1;
223: }
224:
225: private int getForeignHome(Session session, int bucketId)
226: throws SQLException {
227: LinearHashBucket bucket = getBucket(session, bucketId);
228: for (int i = 0; i < bucket.getRecordSize(); i++) {
229: LinearHashEntry record = bucket.getRecord(i);
230: if (record.home != bucketId) {
231: return record.home;
232: }
233: }
234: return -1;
235: }
236:
237: public int getPos(int hash) {
238: hash = Math.abs((hash << 7) - hash + (hash >>> 9)
239: + (hash >>> 17));
240: int pos = hash % (head.baseSize + head.baseSize);
241: int len = head.bucketCount;
242: return pos < len ? pos : (pos % head.baseSize);
243: }
244:
245: private void split(Session session) throws SQLException {
246: // trace.debug("split " + head.nextToSplit);
247: ObjectArray old = new ObjectArray();
248: moveOut(session, head.nextToSplit, old);
249: head.nextToSplit++;
250: if (head.nextToSplit >= head.baseSize) {
251: head.baseSize += head.baseSize;
252: head.nextToSplit = 0;
253: }
254: addBucket(session);
255: addAll(session, old);
256: }
257:
258: private void addAll(Session session, ObjectArray records)
259: throws SQLException {
260: for (int i = 0; i < records.size(); i++) {
261: LinearHashEntry r = (LinearHashEntry) records.get(i);
262: add(session, r.key, r.value);
263: }
264: }
265:
266: // moves all records of a bucket to the array (including chained)
267: private void moveOut(Session session, int home, ObjectArray storeIn)
268: throws SQLException {
269: LinearHashBucket bucket = getBucket(session, home);
270: int foreign = getForeignHome(session, home);
271: while (true) {
272: for (int i = 0; i < bucket.getRecordSize(); i++) {
273: LinearHashEntry r = bucket.getRecord(i);
274: if (r.home == home) {
275: storeIn.add(r);
276: removeRecord(session, bucket, i);
277: i--;
278: }
279: }
280: if (foreign >= 0) {
281: // this block contains foreign records
282: // and therefore all home records have been found
283: // (and it would be an error to set next to -1)
284: moveOut(session, foreign, storeIn);
285: if (SysProperties.CHECK
286: && getBucket(session, foreign).getNextBucket() != -1) {
287: throw Message
288: .getInternalError("moveOut " + foreign);
289: }
290: return;
291: }
292: int next = bucket.getNextBucket();
293: if (SysProperties.CHECK && next >= head.bucketCount) {
294: throw Message.getInternalError("next=" + next + " max="
295: + head.bucketCount);
296: }
297: if (next < 0) {
298: break;
299: }
300: bucket.setNext(session, -1);
301: bucket = getBucket(session, next);
302: }
303: }
304:
305: private void merge(Session session) throws SQLException {
306: if (head.bucketCount <= 1) {
307: return;
308: }
309: if (getUtilization() > UTILIZATION_FOR_MERGE) {
310: return;
311: }
312: ObjectArray old = new ObjectArray();
313: moveOut(session, head.nextToSplit, old);
314: head.nextToSplit--;
315: if (head.nextToSplit < 0) {
316: head.baseSize /= 2;
317: head.nextToSplit = head.baseSize - 1;
318: }
319: moveOut(session, head.nextToSplit, old);
320: moveOut(session, head.bucketCount - 1, old);
321: removeBucket(session);
322:
323: // for(int i=0; i<head.bucketCount; i++) {
324: // LinearHashBucket bucket = this.getBucket(i);
325: // if(bucket.getNextBucket() >= head.bucketCount) {
326: // System.out.println("error");
327: // }
328: // }
329:
330: addAll(session, old);
331: // int testALot;
332: // for(int i=0; i<head.bucketCount; i++) {
333: // LinearHashBucket bucket = this.getBucket(i);
334: // if(bucket.getNextBucket() >= head.bucketCount) {
335: // System.out.println("error");
336: // }
337: // }
338: }
339:
340: private boolean isEquals(Session session, LinearHashEntry r,
341: int hash, Value key) throws SQLException {
342: if (r.hash == hash) {
343: if (r.key == null) {
344: r.key = getKey(tableData.getRow(session, r.value));
345: }
346: if (database.compareTypeSave(r.key, key) == 0) {
347: return true;
348: }
349: }
350: return false;
351: }
352:
353: private int get(Session session, Value key) throws SQLException {
354: int hash = key.hashCode();
355: int home = getPos(hash);
356: LinearHashBucket bucket = getBucket(session, home);
357: while (true) {
358: for (int i = 0; i < bucket.getRecordSize(); i++) {
359: LinearHashEntry r = bucket.getRecord(i);
360: if (isEquals(session, r, hash, key)) {
361: return r.value;
362: }
363: }
364: if (bucket.getNextBucket() < 0) {
365: return -1;
366: }
367: bucket = getBucket(session, bucket.getNextBucket());
368: }
369: }
370:
371: private void removeRecord(Session session, LinearHashBucket bucket,
372: int index) throws SQLException {
373: bucket.removeRecord(session, index);
374: head.recordCount--;
375: rowCount--;
376: }
377:
378: private void addRecord(Session session, LinearHashBucket bucket,
379: LinearHashEntry entry) throws SQLException {
380: bucket.addRecord(session, entry);
381: head.recordCount++;
382: rowCount++;
383: }
384:
385: private void remove(Session session, Value key) throws SQLException {
386: merge(session);
387: // trace.debug("remove "+key.toString());
388: int hash = key.hashCode();
389: int home = getPos(hash);
390: int now = home;
391: while (true) {
392: LinearHashBucket bucket = getBucket(session, now);
393: for (int i = 0; i < bucket.getRecordSize(); i++) {
394: LinearHashEntry r = bucket.getRecord(i);
395: if (isEquals(session, r, hash, key)) {
396: removeRecord(session, bucket, i);
397: if (home != now) {
398: ObjectArray old = new ObjectArray();
399: moveOut(session, home, old);
400: addAll(session, old);
401: }
402: return;
403: }
404: }
405: int next = bucket.getNextBucket();
406: if (next < 0) {
407: throw Message.getInternalError("not found");
408: }
409: now = next;
410: }
411: }
412:
413: private int getBlockId(int i) {
414: return i * blocksPerBucket + firstBucketBlock;
415: }
416:
417: private LinearHashBucket getBucket(Session session, int i)
418: throws SQLException {
419: readCount++;
420: if (SysProperties.CHECK && i >= head.bucketCount) {
421: throw Message.getInternalError("get=" + i + " max="
422: + head.bucketCount);
423: }
424: // trace.debug("read " + i);
425: // return (LinearHashBucket) buckets.get(i);
426: i = getBlockId(i);
427: // System.out.println("getBucket "+i);
428: LinearHashBucket bucket = (LinearHashBucket) storage.getRecord(
429: session, i);
430: return bucket;
431: }
432:
433: private void addBucket(Session session) throws SQLException {
434: LinearHashBucket bucket = new LinearHashBucket(this );
435: storage
436: .addRecord(session, bucket,
437: getBlockId(head.bucketCount));
438: // bucket.setPos(buckets.size());
439: // buckets.add(bucket);
440: //System.out.println("addBucket "+bucket.getPos());
441: if (SysProperties.CHECK
442: && bucket.getBlockCount() > blocksPerBucket) {
443: throw Message.getInternalError("blocks="
444: + bucket.getBlockCount());
445: }
446: head.bucketCount++;
447: }
448:
449: private void removeBucket(Session session) throws SQLException {
450: // buckets.remove(head.bucketCount-1);
451: int pos = getBlockId(head.bucketCount - 1);
452: //System.out.println("removeBucket "+pos);
453: storage.removeRecord(session, pos);
454: head.bucketCount--;
455: }
456:
457: private int getUtilization() {
458: return 100 * head.recordCount
459: / (head.bucketCount * RECORDS_PER_BUCKET);
460: }
461:
462: void updateBucket(Session session, LinearHashBucket bucket)
463: throws SQLException {
464: storage.updateRecord(session, bucket);
465: }
466:
467: public Record read(Session session, DataPage s) throws SQLException {
468: char c = (char) s.readByte();
469: if (c == 'B') {
470: return new LinearHashBucket(this , s);
471: } else if (c == 'H') {
472: return new LinearHashHead(this , s);
473: } else {
474: throw Message.getSQLException(ErrorCode.FILE_CORRUPTED_1,
475: getName());
476: }
477: }
478:
479: public void close(Session session) throws SQLException {
480: // TODO flush from time to time (after a few seconds of no activity or so)
481: writeHeader(session);
482: diskFile.close();
483: }
484:
485: public void add(Session session, Row row) throws SQLException {
486: Value key = getKey(row);
487: if (get(session, key) != -1) {
488: // TODO index duplicate key for hash indexes: is this allowed?
489: throw getDuplicateKeyException();
490: }
491: add(session, key, row.getPos());
492: }
493:
494: public void remove(Session session, Row row) throws SQLException {
495: remove(session, getKey(row));
496: }
497:
498: private Value getKey(SearchRow row) throws SQLException {
499: if (columns.length == 1) {
500: Column column = columns[0];
501: int index = column.getColumnId();
502: Value v = row.getValue(index);
503: return v;
504: }
505: Value[] list = new Value[columns.length];
506: for (int i = 0; i < columns.length; i++) {
507: Column column = columns[i];
508: int index = column.getColumnId();
509: Value v = row.getValue(index);
510: list[i] = v;
511: }
512: return ValueArray.get(list);
513: }
514:
515: public Cursor find(Session session, SearchRow first, SearchRow last)
516: throws SQLException {
517: if (first == null || last == null) {
518: // TODO hash index: should additionally check if values are the same
519: throw Message.getInternalError();
520: }
521: int key = get(session, getKey(first));
522: if (key == -1) {
523: return new LinearHashCursor(null);
524: }
525: return new LinearHashCursor(tableData.getRow(session, key));
526: }
527:
528: public double getCost(Session session, int[] masks)
529: throws SQLException {
530: for (int i = 0; i < columns.length; i++) {
531: Column column = columns[i];
532: int index = column.getColumnId();
533: int mask = masks[index];
534: if ((mask & IndexCondition.EQUALITY) != IndexCondition.EQUALITY) {
535: return Long.MAX_VALUE;
536: }
537: }
538: return 100;
539: }
540:
541: public void remove(Session session) throws SQLException {
542: storage.delete(session);
543: diskFile.delete();
544: }
545:
546: public void truncate(Session session) throws SQLException {
547: storage.truncate(session);
548: // buckets.clear();
549: head = new LinearHashHead(this );
550: head.recordCount = 0;
551: head.bucketCount = 0;
552: head.baseSize = 1;
553: head.nextToSplit = 0;
554: readCount = 0;
555: storage.addRecord(session, head, 0);
556: addBucket(session);
557: rowCount = 0;
558: }
559:
560: public void checkRename() throws SQLException {
561: }
562:
563: public boolean needRebuild() {
564: return needRebuild;
565: }
566:
567: public int getBucketSize() {
568: return bucketSize;
569: }
570:
571: public boolean canGetFirstOrLast() {
572: return false;
573: }
574:
575: public SearchRow findFirstOrLast(Session session, boolean first)
576: throws SQLException {
577: throw Message.getUnsupportedException();
578: }
579:
580: }
|