1 | /* |
2 | * Copyright 2004-2014 H2 Group. Multiple-Licensed under the MPL 2.0, |
3 | * and the EPL 1.0 (http://h2database.com/html/license.html). |
4 | * Initial Developer: H2 Group |
5 | */ |
6 | package org.h2.index; |
7 | |
8 | import org.h2.api.ErrorCode; |
9 | import org.h2.engine.Constants; |
10 | import org.h2.engine.DbObject; |
11 | import org.h2.engine.Mode; |
12 | import org.h2.engine.Session; |
13 | import org.h2.message.DbException; |
14 | import org.h2.message.Trace; |
15 | import org.h2.result.Row; |
16 | import org.h2.result.SearchRow; |
17 | import org.h2.result.SortOrder; |
18 | import org.h2.schema.SchemaObjectBase; |
19 | import org.h2.table.Column; |
20 | import org.h2.table.IndexColumn; |
21 | import org.h2.table.Table; |
22 | import org.h2.table.TableFilter; |
23 | import org.h2.util.MathUtils; |
24 | import org.h2.util.StatementBuilder; |
25 | import org.h2.util.StringUtils; |
26 | import org.h2.value.Value; |
27 | import org.h2.value.ValueNull; |
28 | |
29 | /** |
30 | * Most index implementations extend the base index. |
31 | */ |
32 | public abstract class BaseIndex extends SchemaObjectBase implements Index { |
33 | |
34 | protected IndexColumn[] indexColumns; |
35 | protected Column[] columns; |
36 | protected int[] columnIds; |
37 | protected Table table; |
38 | protected IndexType indexType; |
39 | protected boolean isMultiVersion; |
40 | |
41 | /** |
42 | * Initialize the base index. |
43 | * |
44 | * @param newTable the table |
45 | * @param id the object id |
46 | * @param name the index name |
47 | * @param newIndexColumns the columns that are indexed or null if this is |
48 | * not yet known |
49 | * @param newIndexType the index type |
50 | */ |
51 | protected void initBaseIndex(Table newTable, int id, String name, |
52 | IndexColumn[] newIndexColumns, IndexType newIndexType) { |
53 | initSchemaObjectBase(newTable.getSchema(), id, name, Trace.INDEX); |
54 | this.indexType = newIndexType; |
55 | this.table = newTable; |
56 | if (newIndexColumns != null) { |
57 | this.indexColumns = newIndexColumns; |
58 | columns = new Column[newIndexColumns.length]; |
59 | int len = columns.length; |
60 | columnIds = new int[len]; |
61 | for (int i = 0; i < len; i++) { |
62 | Column col = newIndexColumns[i].column; |
63 | columns[i] = col; |
64 | columnIds[i] = col.getColumnId(); |
65 | } |
66 | } |
67 | } |
68 | |
69 | /** |
70 | * Check that the index columns are not CLOB or BLOB. |
71 | * |
72 | * @param columns the columns |
73 | */ |
74 | protected static void checkIndexColumnTypes(IndexColumn[] columns) { |
75 | for (IndexColumn c : columns) { |
76 | int type = c.column.getType(); |
77 | if (type == Value.CLOB || type == Value.BLOB) { |
78 | throw DbException.getUnsupportedException( |
79 | "Index on BLOB or CLOB column: " + c.column.getCreateSQL()); |
80 | } |
81 | } |
82 | } |
83 | |
84 | @Override |
85 | public String getDropSQL() { |
86 | return null; |
87 | } |
88 | |
89 | /** |
90 | * Create a duplicate key exception with a message that contains the index |
91 | * name. |
92 | * |
93 | * @param key the key values |
94 | * @return the exception |
95 | */ |
96 | protected DbException getDuplicateKeyException(String key) { |
97 | String sql = getName() + " ON " + table.getSQL() + |
98 | "(" + getColumnListSQL() + ")"; |
99 | if (key != null) { |
100 | sql += " VALUES " + key; |
101 | } |
102 | DbException e = DbException.get(ErrorCode.DUPLICATE_KEY_1, sql); |
103 | e.setSource(this); |
104 | return e; |
105 | } |
106 | |
107 | @Override |
108 | public String getPlanSQL() { |
109 | return getSQL(); |
110 | } |
111 | |
112 | @Override |
113 | public void removeChildrenAndResources(Session session) { |
114 | table.removeIndex(this); |
115 | remove(session); |
116 | database.removeMeta(session, getId()); |
117 | } |
118 | |
119 | @Override |
120 | public boolean canFindNext() { |
121 | return false; |
122 | } |
123 | |
124 | |
125 | @Override |
126 | public Cursor find(TableFilter filter, SearchRow first, SearchRow last) { |
127 | return find(filter.getSession(), first, last); |
128 | } |
129 | |
130 | /** |
131 | * Find a row or a list of rows that is larger and create a cursor to |
132 | * iterate over the result. The base implementation doesn't support this |
133 | * feature. |
134 | * |
135 | * @param session the session |
136 | * @param higherThan the lower limit (excluding) |
137 | * @param last the last row, or null for no limit |
138 | * @return the cursor |
139 | * @throws DbException always |
140 | */ |
141 | @Override |
142 | public Cursor findNext(Session session, SearchRow higherThan, SearchRow last) { |
143 | throw DbException.throwInternalError(); |
144 | } |
145 | |
146 | /** |
147 | * Calculate the cost for the given mask as if this index was a typical |
148 | * b-tree range index. This is the estimated cost required to search one |
149 | * row, and then iterate over the given number of rows. |
150 | * |
151 | * @param masks the search mask |
152 | * @param rowCount the number of rows in the index |
153 | * @param filter the table filter |
154 | * @param sortOrder the sort order |
155 | * @return the estimated cost |
156 | */ |
157 | protected long getCostRangeIndex(int[] masks, long rowCount, |
158 | TableFilter filter, SortOrder sortOrder) { |
159 | rowCount += Constants.COST_ROW_OFFSET; |
160 | long cost = rowCount; |
161 | long rows = rowCount; |
162 | int totalSelectivity = 0; |
163 | if (masks == null) { |
164 | return cost; |
165 | } |
166 | for (int i = 0, len = columns.length; i < len; i++) { |
167 | Column column = columns[i]; |
168 | int index = column.getColumnId(); |
169 | int mask = masks[index]; |
170 | if ((mask & IndexCondition.EQUALITY) == IndexCondition.EQUALITY) { |
171 | if (i == columns.length - 1 && getIndexType().isUnique()) { |
172 | cost = 3; |
173 | break; |
174 | } |
175 | totalSelectivity = 100 - ((100 - totalSelectivity) * |
176 | (100 - column.getSelectivity()) / 100); |
177 | long distinctRows = rowCount * totalSelectivity / 100; |
178 | if (distinctRows <= 0) { |
179 | distinctRows = 1; |
180 | } |
181 | rows = Math.max(rowCount / distinctRows, 1); |
182 | cost = 2 + rows; |
183 | } else if ((mask & IndexCondition.RANGE) == IndexCondition.RANGE) { |
184 | cost = 2 + rows / 4; |
185 | break; |
186 | } else if ((mask & IndexCondition.START) == IndexCondition.START) { |
187 | cost = 2 + rows / 3; |
188 | break; |
189 | } else if ((mask & IndexCondition.END) == IndexCondition.END) { |
190 | cost = rows / 3; |
191 | break; |
192 | } else { |
193 | break; |
194 | } |
195 | } |
196 | // if the ORDER BY clause matches the ordering of this index, |
197 | // it will be cheaper than another index, so adjust the cost accordingly |
198 | if (sortOrder != null) { |
199 | boolean sortOrderMatches = true; |
200 | int coveringCount = 0; |
201 | int[] sortTypes = sortOrder.getSortTypes(); |
202 | for (int i = 0, len = sortTypes.length; i < len; i++) { |
203 | if (i >= indexColumns.length) { |
204 | // we can still use this index if we are sorting by more |
205 | // than it's columns, it's just that the coveringCount |
206 | // is lower than with an index that contains |
207 | // more of the order by columns |
208 | break; |
209 | } |
210 | Column col = sortOrder.getColumn(i, filter); |
211 | if (col == null) { |
212 | sortOrderMatches = false; |
213 | break; |
214 | } |
215 | IndexColumn indexCol = indexColumns[i]; |
216 | if (col != indexCol.column) { |
217 | sortOrderMatches = false; |
218 | break; |
219 | } |
220 | int sortType = sortTypes[i]; |
221 | if (sortType != indexCol.sortType) { |
222 | sortOrderMatches = false; |
223 | break; |
224 | } |
225 | coveringCount++; |
226 | } |
227 | if (sortOrderMatches) { |
228 | // "coveringCount" makes sure that when we have two |
229 | // or more covering indexes, we choose the one |
230 | // that covers more |
231 | cost -= coveringCount; |
232 | } |
233 | } |
234 | return cost; |
235 | } |
236 | |
237 | @Override |
238 | public int compareRows(SearchRow rowData, SearchRow compare) { |
239 | if (rowData == compare) { |
240 | return 0; |
241 | } |
242 | for (int i = 0, len = indexColumns.length; i < len; i++) { |
243 | int index = columnIds[i]; |
244 | Value v = compare.getValue(index); |
245 | if (v == null) { |
246 | // can't compare further |
247 | return 0; |
248 | } |
249 | int c = compareValues(rowData.getValue(index), v, indexColumns[i].sortType); |
250 | if (c != 0) { |
251 | return c; |
252 | } |
253 | } |
254 | return 0; |
255 | } |
256 | |
257 | /** |
258 | * Check if one of the columns is NULL and multiple rows with NULL are |
259 | * allowed using the current compatibility mode for unique indexes. Note: |
260 | * NULL behavior is complicated in SQL. |
261 | * |
262 | * @param newRow the row to check |
263 | * @return true if one of the columns is null and multiple nulls in unique |
264 | * indexes are allowed |
265 | */ |
266 | protected boolean containsNullAndAllowMultipleNull(SearchRow newRow) { |
267 | Mode mode = database.getMode(); |
268 | if (mode.uniqueIndexSingleNull) { |
269 | return false; |
270 | } else if (mode.uniqueIndexSingleNullExceptAllColumnsAreNull) { |
271 | for (int index : columnIds) { |
272 | Value v = newRow.getValue(index); |
273 | if (v != ValueNull.INSTANCE) { |
274 | return false; |
275 | } |
276 | } |
277 | return true; |
278 | } |
279 | for (int index : columnIds) { |
280 | Value v = newRow.getValue(index); |
281 | if (v == ValueNull.INSTANCE) { |
282 | return true; |
283 | } |
284 | } |
285 | return false; |
286 | } |
287 | |
288 | /** |
289 | * Compare the positions of two rows. |
290 | * |
291 | * @param rowData the first row |
292 | * @param compare the second row |
293 | * @return 0 if both rows are equal, -1 if the first row is smaller, |
294 | * otherwise 1 |
295 | */ |
296 | int compareKeys(SearchRow rowData, SearchRow compare) { |
297 | long k1 = rowData.getKey(); |
298 | long k2 = compare.getKey(); |
299 | if (k1 == k2) { |
300 | if (isMultiVersion) { |
301 | int v1 = rowData.getVersion(); |
302 | int v2 = compare.getVersion(); |
303 | return MathUtils.compareInt(v2, v1); |
304 | } |
305 | return 0; |
306 | } |
307 | return k1 > k2 ? 1 : -1; |
308 | } |
309 | |
310 | private int compareValues(Value a, Value b, int sortType) { |
311 | if (a == b) { |
312 | return 0; |
313 | } |
314 | boolean aNull = a == null, bNull = b == null; |
315 | if (aNull || bNull) { |
316 | return SortOrder.compareNull(aNull, sortType); |
317 | } |
318 | int comp = table.compareTypeSave(a, b); |
319 | if ((sortType & SortOrder.DESCENDING) != 0) { |
320 | comp = -comp; |
321 | } |
322 | return comp; |
323 | } |
324 | |
325 | @Override |
326 | public int getColumnIndex(Column col) { |
327 | for (int i = 0, len = columns.length; i < len; i++) { |
328 | if (columns[i].equals(col)) { |
329 | return i; |
330 | } |
331 | } |
332 | return -1; |
333 | } |
334 | |
335 | /** |
336 | * Get the list of columns as a string. |
337 | * |
338 | * @return the list of columns |
339 | */ |
340 | private String getColumnListSQL() { |
341 | StatementBuilder buff = new StatementBuilder(); |
342 | for (IndexColumn c : indexColumns) { |
343 | buff.appendExceptFirst(", "); |
344 | buff.append(c.getSQL()); |
345 | } |
346 | return buff.toString(); |
347 | } |
348 | |
349 | @Override |
350 | public String getCreateSQLForCopy(Table targetTable, String quotedName) { |
351 | StringBuilder buff = new StringBuilder("CREATE "); |
352 | buff.append(indexType.getSQL()); |
353 | buff.append(' '); |
354 | if (table.isHidden()) { |
355 | buff.append("IF NOT EXISTS "); |
356 | } |
357 | buff.append(quotedName); |
358 | buff.append(" ON ").append(targetTable.getSQL()); |
359 | if (comment != null) { |
360 | buff.append(" COMMENT ").append(StringUtils.quoteStringSQL(comment)); |
361 | } |
362 | buff.append('(').append(getColumnListSQL()).append(')'); |
363 | return buff.toString(); |
364 | } |
365 | |
366 | @Override |
367 | public String getCreateSQL() { |
368 | return getCreateSQLForCopy(table, getSQL()); |
369 | } |
370 | |
371 | @Override |
372 | public IndexColumn[] getIndexColumns() { |
373 | return indexColumns; |
374 | } |
375 | |
376 | @Override |
377 | public Column[] getColumns() { |
378 | return columns; |
379 | } |
380 | |
381 | @Override |
382 | public IndexType getIndexType() { |
383 | return indexType; |
384 | } |
385 | |
386 | @Override |
387 | public int getType() { |
388 | return DbObject.INDEX; |
389 | } |
390 | |
391 | @Override |
392 | public Table getTable() { |
393 | return table; |
394 | } |
395 | |
396 | @Override |
397 | public void commit(int operation, Row row) { |
398 | // nothing to do |
399 | } |
400 | |
401 | void setMultiVersion(boolean multiVersion) { |
402 | this.isMultiVersion = multiVersion; |
403 | } |
404 | |
405 | @Override |
406 | public Row getRow(Session session, long key) { |
407 | throw DbException.getUnsupportedException(toString()); |
408 | } |
409 | |
410 | @Override |
411 | public boolean isHidden() { |
412 | return table.isHidden(); |
413 | } |
414 | |
415 | @Override |
416 | public boolean isRowIdIndex() { |
417 | return false; |
418 | } |
419 | |
420 | @Override |
421 | public boolean canScan() { |
422 | return true; |
423 | } |
424 | |
425 | @Override |
426 | public void setSortedInsertMode(boolean sortedInsertMode) { |
427 | // ignore |
428 | } |
429 | |
430 | } |