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.engine.Constants;
012: import org.h2.engine.DbObject;
013: import org.h2.engine.Session;
014: import org.h2.message.Message;
015: import org.h2.message.Trace;
016: import org.h2.result.Row;
017: import org.h2.result.SearchRow;
018: import org.h2.result.SortOrder;
019: import org.h2.schema.SchemaObjectBase;
020: import org.h2.table.Column;
021: import org.h2.table.IndexColumn;
022: import org.h2.table.Table;
023: import org.h2.util.StringUtils;
024: import org.h2.value.Value;
025: import org.h2.value.ValueNull;
026:
027: /**
028: * Most index implementations extend the base index.
029: */
030: public abstract class BaseIndex extends SchemaObjectBase implements
031: Index {
032:
033: protected IndexColumn[] indexColumns;
034: protected Column[] columns;
035: protected int[] columnIds;
036: protected boolean[] descending;
037: protected Table table;
038: protected IndexType indexType;
039: protected long rowCount;
040:
041: /**
042: * Close this index.
043: *
044: * @param session the session
045: */
046: public abstract void close(Session session) throws SQLException;
047:
048: /**
049: * Add a row to this index.
050: *
051: * @param session the session
052: * @param row the row to add
053: */
054: public abstract void add(Session session, Row row)
055: throws SQLException;
056:
057: /**
058: * Remove a row from the index.
059: *
060: * @param session the session
061: * @param row the row
062: */
063: public abstract void remove(Session session, Row row)
064: throws SQLException;
065:
066: /**
067: * Create a cursor to iterate over a number of rows.
068: *
069: * @param session the session
070: * @param first the first row to return (null if no limit)
071: * @param last the last row to return (null if no limit)
072: */
073: public abstract Cursor find(Session session, SearchRow first,
074: SearchRow last) throws SQLException;
075:
076: /**
077: * Calculate the cost to find rows.
078: *
079: * @param session the session
080: * @param masks the condition mask
081: */
082: public abstract double getCost(Session session, int[] masks)
083: throws SQLException;
084:
085: /**
086: * Remove the index.
087: *
088: * @param session the session
089: */
090: public abstract void remove(Session session) throws SQLException;
091:
092: /**
093: * Truncate the index.
094: *
095: * @param session the session
096: */
097: public abstract void truncate(Session session) throws SQLException;
098:
099: /**
100: * Check if this index can quickly find the first or last value.
101: *
102: * @return true if it can
103: */
104: public abstract boolean canGetFirstOrLast();
105:
106: /**
107: * Find the first (or last) value of this index.
108: *
109: * @param session the session
110: * @param first true for the first value, false for the last
111: */
112: public abstract SearchRow findFirstOrLast(Session session,
113: boolean first) throws SQLException;
114:
115: /**
116: * Check if this index needs to be re-built.
117: *
118: * @return true if it must be re-built.
119: */
120: public abstract boolean needRebuild();
121:
122: public BaseIndex(Table table, int id, String name,
123: IndexColumn[] indexColumns, IndexType indexType) {
124: super (table.getSchema(), id, name, Trace.INDEX);
125: this .indexType = indexType;
126: this .table = table;
127: if (indexColumns != null) {
128: this .indexColumns = indexColumns;
129: columns = new Column[indexColumns.length];
130: columnIds = new int[columns.length];
131: for (int i = 0; i < columns.length; i++) {
132: Column col = indexColumns[i].column;
133: columns[i] = col;
134: columnIds[i] = col.getColumnId();
135: }
136: }
137: }
138:
139: public String getDropSQL() {
140: return null;
141: }
142:
143: public SQLException getDuplicateKeyException() {
144: StringBuffer buff = new StringBuffer();
145: buff.append(getName());
146: buff.append(" ");
147: buff.append(" ON ");
148: buff.append(table.getSQL());
149: buff.append("(");
150: buff.append(getColumnListSQL());
151: buff.append(")");
152: return Message.getSQLException(ErrorCode.DUPLICATE_KEY_1, buff
153: .toString());
154: }
155:
156: public String getPlanSQL() {
157: return getSQL();
158: }
159:
160: public void removeChildrenAndResources(Session session)
161: throws SQLException {
162: table.removeIndex(this );
163: remove(session);
164: database.removeMeta(session, getId());
165: }
166:
167: public boolean canFindNext() {
168: return false;
169: }
170:
171: public Cursor findNext(Session session, SearchRow first,
172: SearchRow last) throws SQLException {
173: throw Message.getInternalError();
174: }
175:
176: public long getRowCount(Session session) {
177: return rowCount;
178: }
179:
180: public int getLookupCost(long rowCount) {
181: return 2;
182: }
183:
184: public long getCostRangeIndex(int[] masks, long rowCount)
185: throws SQLException {
186: rowCount += Constants.COST_ROW_OFFSET;
187: long cost = rowCount;
188: long rows = rowCount;
189: int totalSelectivity = 0;
190: for (int i = 0; masks != null && i < columns.length; i++) {
191: Column column = columns[i];
192: int index = column.getColumnId();
193: int mask = masks[index];
194: if ((mask & IndexCondition.EQUALITY) == IndexCondition.EQUALITY) {
195: if (i == columns.length - 1
196: && getIndexType().isUnique()) {
197: cost = getLookupCost(rowCount) + 1;
198: break;
199: }
200: totalSelectivity = 100 - ((100 - totalSelectivity)
201: * (100 - column.getSelectivity()) / 100);
202: long distinctRows = rowCount * totalSelectivity / 100;
203: if (distinctRows <= 0) {
204: distinctRows = 1;
205: }
206: rows = Math.max(rowCount / distinctRows, 1);
207: cost = getLookupCost(rowCount) + rows;
208: } else if ((mask & IndexCondition.RANGE) == IndexCondition.RANGE) {
209: cost = getLookupCost(rowCount) + rows / 4;
210: break;
211: } else if ((mask & IndexCondition.START) == IndexCondition.START) {
212: cost = getLookupCost(rowCount) + rows / 3;
213: break;
214: } else if ((mask & IndexCondition.END) == IndexCondition.END) {
215: cost = rows / 3;
216: break;
217: } else {
218: break;
219: }
220: }
221: return cost;
222: }
223:
224: public int compareRows(SearchRow rowData, SearchRow compare)
225: throws SQLException {
226: for (int i = 0; i < indexColumns.length; i++) {
227: int index = columnIds[i];
228: Value v = compare.getValue(index);
229: if (v == null) {
230: // can't compare further
231: return 0;
232: }
233: int c = compareValues(rowData.getValue(index), v,
234: indexColumns[i].sortType);
235: if (c != 0) {
236: return c;
237: }
238: }
239: return 0;
240: }
241:
242: public boolean isNull(Row newRow) {
243: for (int i = 0; i < columns.length; i++) {
244: int index = columnIds[i];
245: Value v = newRow.getValue(index);
246: if (v == ValueNull.INSTANCE) {
247: return true;
248: }
249: }
250: return false;
251: }
252:
253: public int compareKeys(SearchRow rowData, SearchRow compare) {
254: int k1 = rowData.getPos();
255: int k2 = compare.getPos();
256: if (k1 == k2) {
257: return 0;
258: }
259: return k1 > k2 ? 1 : -1;
260: }
261:
262: private int compareValues(Value a, Value b, int sortType)
263: throws SQLException {
264: boolean aNull = a == null, bNull = b == null;
265: if (aNull || bNull) {
266: if (aNull == bNull) {
267: return 0;
268: }
269: return SortOrder.compareNull(aNull, bNull, sortType);
270: }
271: int comp = database.compareTypeSave(a, b);
272: if ((sortType & SortOrder.DESCENDING) != 0) {
273: comp = -comp;
274: }
275: return comp;
276: }
277:
278: public int getColumnIndex(Column col) {
279: for (int i = 0; i < columns.length; i++) {
280: if (columns[i] == col) {
281: return i;
282: }
283: }
284: return -1;
285: }
286:
287: public String getColumnListSQL() {
288: StringBuffer buff = new StringBuffer();
289: for (int i = 0; i < indexColumns.length; i++) {
290: if (i > 0) {
291: buff.append(", ");
292: }
293: buff.append(indexColumns[i].getSQL());
294: }
295: return buff.toString();
296: }
297:
298: public String getCreateSQLForCopy(Table table, String quotedName) {
299: StringBuffer buff = new StringBuffer();
300: buff.append("CREATE ");
301: buff.append(indexType.getSQL());
302: if (!indexType.isPrimaryKey()) {
303: buff.append(' ');
304: buff.append(quotedName);
305: }
306: buff.append(" ON ");
307: buff.append(table.getSQL());
308: if (comment != null) {
309: buff.append(" COMMENT ");
310: buff.append(StringUtils.quoteStringSQL(comment));
311: }
312: buff.append("(");
313: buff.append(getColumnListSQL());
314: buff.append(")");
315: return buff.toString();
316: }
317:
318: public String getCreateSQL() {
319: return getCreateSQLForCopy(table, getSQL());
320: }
321:
322: public IndexColumn[] getIndexColumns() {
323: return indexColumns;
324: }
325:
326: public Column[] getColumns() {
327: return columns;
328: }
329:
330: public IndexType getIndexType() {
331: return indexType;
332: }
333:
334: public int getType() {
335: return DbObject.INDEX;
336: }
337:
338: public Table getTable() {
339: return table;
340: }
341:
342: public void commit(int operation, Row row) throws SQLException {
343: }
344:
345: }
|