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