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.mvstore.db; |
7 | |
8 | import java.util.ArrayList; |
9 | import java.util.Arrays; |
10 | import java.util.Collections; |
11 | import java.util.Iterator; |
12 | import java.util.List; |
13 | import java.util.TreeSet; |
14 | |
15 | import org.h2.api.ErrorCode; |
16 | import org.h2.engine.Database; |
17 | import org.h2.engine.Session; |
18 | import org.h2.index.BaseIndex; |
19 | import org.h2.index.Cursor; |
20 | import org.h2.index.IndexType; |
21 | import org.h2.message.DbException; |
22 | import org.h2.mvstore.MVMap; |
23 | import org.h2.mvstore.db.TransactionStore.Transaction; |
24 | import org.h2.mvstore.db.TransactionStore.TransactionMap; |
25 | import org.h2.result.Row; |
26 | import org.h2.result.SearchRow; |
27 | import org.h2.result.SortOrder; |
28 | import org.h2.table.Column; |
29 | import org.h2.table.IndexColumn; |
30 | import org.h2.table.TableFilter; |
31 | import org.h2.util.New; |
32 | import org.h2.value.CompareMode; |
33 | import org.h2.value.Value; |
34 | import org.h2.value.ValueArray; |
35 | import org.h2.value.ValueLong; |
36 | import org.h2.value.ValueNull; |
37 | |
38 | /** |
39 | * A table stored in a MVStore. |
40 | */ |
41 | public class MVSecondaryIndex extends BaseIndex implements MVIndex { |
42 | |
43 | /** |
44 | * The multi-value table. |
45 | */ |
46 | final MVTable mvTable; |
47 | |
48 | private final int keyColumns; |
49 | private final String mapName; |
50 | private TransactionMap<Value, Value> dataMap; |
51 | |
52 | public MVSecondaryIndex(Database db, MVTable table, int id, String indexName, |
53 | IndexColumn[] columns, IndexType indexType) { |
54 | this.mvTable = table; |
55 | initBaseIndex(table, id, indexName, columns, indexType); |
56 | if (!database.isStarting()) { |
57 | checkIndexColumnTypes(columns); |
58 | } |
59 | // always store the row key in the map key, |
60 | // even for unique indexes, as some of the index columns could be null |
61 | keyColumns = columns.length + 1; |
62 | mapName = "index." + getId(); |
63 | int[] sortTypes = new int[keyColumns]; |
64 | for (int i = 0; i < columns.length; i++) { |
65 | sortTypes[i] = columns[i].sortType; |
66 | } |
67 | sortTypes[keyColumns - 1] = SortOrder.ASCENDING; |
68 | ValueDataType keyType = new ValueDataType( |
69 | db.getCompareMode(), db, sortTypes); |
70 | ValueDataType valueType = new ValueDataType(null, null, null); |
71 | dataMap = mvTable.getTransaction(null).openMap( |
72 | mapName, keyType, valueType); |
73 | if (!keyType.equals(dataMap.getKeyType())) { |
74 | throw DbException.throwInternalError("Incompatible key type"); |
75 | } |
76 | } |
77 | |
78 | @Override |
79 | public void addRowsToBuffer(List<Row> rows, String bufferName) { |
80 | MVMap<Value, Value> map = openMap(bufferName); |
81 | for (Row row : rows) { |
82 | ValueArray key = convertToKey(row); |
83 | map.put(key, ValueNull.INSTANCE); |
84 | } |
85 | } |
86 | |
87 | @Override |
88 | public void addBufferedRows(List<String> bufferNames) { |
89 | ArrayList<String> mapNames = New.arrayList(bufferNames); |
90 | final CompareMode compareMode = database.getCompareMode(); |
91 | /** |
92 | * A source of values. |
93 | */ |
94 | class Source implements Comparable<Source> { |
95 | Value value; |
96 | Iterator<Value> next; |
97 | int sourceId; |
98 | @Override |
99 | public int compareTo(Source o) { |
100 | int comp = value.compareTo(o.value, compareMode); |
101 | if (comp == 0) { |
102 | comp = sourceId - o.sourceId; |
103 | } |
104 | return comp; |
105 | } |
106 | } |
107 | TreeSet<Source> sources = new TreeSet<Source>(); |
108 | for (int i = 0; i < bufferNames.size(); i++) { |
109 | MVMap<Value, Value> map = openMap(bufferNames.get(i)); |
110 | Iterator<Value> it = map.keyIterator(null); |
111 | if (it.hasNext()) { |
112 | Source s = new Source(); |
113 | s.value = it.next(); |
114 | s.next = it; |
115 | s.sourceId = i; |
116 | sources.add(s); |
117 | } |
118 | } |
119 | try { |
120 | while (true) { |
121 | Source s = sources.first(); |
122 | Value v = s.value; |
123 | |
124 | if (indexType.isUnique()) { |
125 | Value[] array = ((ValueArray) v).getList(); |
126 | // don't change the original value |
127 | array = Arrays.copyOf(array, array.length); |
128 | array[keyColumns - 1] = ValueLong.get(Long.MIN_VALUE); |
129 | ValueArray unique = ValueArray.get(array); |
130 | ValueArray key = (ValueArray) dataMap.getLatestCeilingKey(unique); |
131 | if (key != null) { |
132 | SearchRow r2 = convertToSearchRow(key); |
133 | SearchRow row = convertToSearchRow((ValueArray) v); |
134 | if (compareRows(row, r2) == 0) { |
135 | if (!containsNullAndAllowMultipleNull(r2)) { |
136 | throw getDuplicateKeyException(key.toString()); |
137 | } |
138 | } |
139 | } |
140 | } |
141 | |
142 | dataMap.putCommitted(v, ValueNull.INSTANCE); |
143 | |
144 | Iterator<Value> it = s.next; |
145 | if (!it.hasNext()) { |
146 | sources.remove(s); |
147 | if (sources.size() == 0) { |
148 | break; |
149 | } |
150 | } else { |
151 | Value nextValue = it.next(); |
152 | sources.remove(s); |
153 | s.value = nextValue; |
154 | sources.add(s); |
155 | } |
156 | } |
157 | } finally { |
158 | for (String tempMapName : mapNames) { |
159 | MVMap<Value, Value> map = openMap(tempMapName); |
160 | map.getStore().removeMap(map); |
161 | } |
162 | } |
163 | } |
164 | |
165 | private MVMap<Value, Value> openMap(String mapName) { |
166 | int[] sortTypes = new int[keyColumns]; |
167 | for (int i = 0; i < indexColumns.length; i++) { |
168 | sortTypes[i] = indexColumns[i].sortType; |
169 | } |
170 | sortTypes[keyColumns - 1] = SortOrder.ASCENDING; |
171 | ValueDataType keyType = new ValueDataType( |
172 | database.getCompareMode(), database, sortTypes); |
173 | ValueDataType valueType = new ValueDataType(null, null, null); |
174 | MVMap.Builder<Value, Value> builder = |
175 | new MVMap.Builder<Value, Value>().keyType(keyType).valueType(valueType); |
176 | MVMap<Value, Value> map = database.getMvStore(). |
177 | getStore().openMap(mapName, builder); |
178 | if (!keyType.equals(map.getKeyType())) { |
179 | throw DbException.throwInternalError("Incompatible key type"); |
180 | } |
181 | return map; |
182 | } |
183 | |
184 | @Override |
185 | public void close(Session session) { |
186 | // ok |
187 | } |
188 | |
189 | @Override |
190 | public void add(Session session, Row row) { |
191 | TransactionMap<Value, Value> map = getMap(session); |
192 | ValueArray array = convertToKey(row); |
193 | ValueArray unique = null; |
194 | if (indexType.isUnique()) { |
195 | // this will detect committed entries only |
196 | unique = convertToKey(row); |
197 | unique.getList()[keyColumns - 1] = ValueLong.get(Long.MIN_VALUE); |
198 | ValueArray key = (ValueArray) map.getLatestCeilingKey(unique); |
199 | if (key != null) { |
200 | SearchRow r2 = convertToSearchRow(key); |
201 | if (compareRows(row, r2) == 0) { |
202 | if (!containsNullAndAllowMultipleNull(r2)) { |
203 | throw getDuplicateKeyException(key.toString()); |
204 | } |
205 | } |
206 | } |
207 | } |
208 | try { |
209 | map.put(array, ValueNull.INSTANCE); |
210 | } catch (IllegalStateException e) { |
211 | throw DbException.get(ErrorCode.CONCURRENT_UPDATE_1, |
212 | e, table.getName()); |
213 | } |
214 | if (indexType.isUnique()) { |
215 | Iterator<Value> it = map.keyIterator(unique, true); |
216 | while (it.hasNext()) { |
217 | ValueArray k = (ValueArray) it.next(); |
218 | SearchRow r2 = convertToSearchRow(k); |
219 | if (compareRows(row, r2) != 0) { |
220 | break; |
221 | } |
222 | if (containsNullAndAllowMultipleNull(r2)) { |
223 | // this is allowed |
224 | continue; |
225 | } |
226 | if (map.isSameTransaction(k)) { |
227 | continue; |
228 | } |
229 | if (map.get(k) != null) { |
230 | // committed |
231 | throw getDuplicateKeyException(k.toString()); |
232 | } |
233 | throw DbException.get(ErrorCode.CONCURRENT_UPDATE_1, table.getName()); |
234 | } |
235 | } |
236 | } |
237 | |
238 | @Override |
239 | public void remove(Session session, Row row) { |
240 | ValueArray array = convertToKey(row); |
241 | TransactionMap<Value, Value> map = getMap(session); |
242 | try { |
243 | Value old = map.remove(array); |
244 | if (old == null) { |
245 | throw DbException.get(ErrorCode.ROW_NOT_FOUND_WHEN_DELETING_1, |
246 | getSQL() + ": " + row.getKey()); |
247 | } |
248 | } catch (IllegalStateException e) { |
249 | throw DbException.get(ErrorCode.CONCURRENT_UPDATE_1, |
250 | e, table.getName()); |
251 | } |
252 | } |
253 | |
254 | @Override |
255 | public Cursor find(Session session, SearchRow first, SearchRow last) { |
256 | return find(session, first, false, last); |
257 | } |
258 | |
259 | private Cursor find(Session session, SearchRow first, boolean bigger, SearchRow last) { |
260 | ValueArray min = convertToKey(first); |
261 | if (min != null) { |
262 | min.getList()[keyColumns - 1] = ValueLong.get(Long.MIN_VALUE); |
263 | } |
264 | TransactionMap<Value, Value> map = getMap(session); |
265 | if (bigger && min != null) { |
266 | // search for the next: first skip 1, then 2, 4, 8, until |
267 | // we have a higher key; then skip 4, 2,... |
268 | // (binary search), until 1 |
269 | int offset = 1; |
270 | while (true) { |
271 | ValueArray v = (ValueArray) map.relativeKey(min, offset); |
272 | if (v != null) { |
273 | boolean foundHigher = false; |
274 | for (int i = 0; i < keyColumns - 1; i++) { |
275 | int idx = columnIds[i]; |
276 | Value b = first.getValue(idx); |
277 | if (b == null) { |
278 | break; |
279 | } |
280 | Value a = v.getList()[i]; |
281 | if (database.compare(a, b) > 0) { |
282 | foundHigher = true; |
283 | break; |
284 | } |
285 | } |
286 | if (!foundHigher) { |
287 | offset += offset; |
288 | min = v; |
289 | continue; |
290 | } |
291 | } |
292 | if (offset > 1) { |
293 | offset /= 2; |
294 | continue; |
295 | } |
296 | if (map.get(v) == null) { |
297 | min = (ValueArray) map.higherKey(min); |
298 | if (min == null) { |
299 | break; |
300 | } |
301 | continue; |
302 | } |
303 | min = v; |
304 | break; |
305 | } |
306 | if (min == null) { |
307 | return new MVStoreCursor(session, |
308 | Collections.<Value>emptyList().iterator(), null); |
309 | } |
310 | } |
311 | return new MVStoreCursor(session, map.keyIterator(min), last); |
312 | } |
313 | |
314 | private ValueArray convertToKey(SearchRow r) { |
315 | if (r == null) { |
316 | return null; |
317 | } |
318 | Value[] array = new Value[keyColumns]; |
319 | for (int i = 0; i < columns.length; i++) { |
320 | Column c = columns[i]; |
321 | int idx = c.getColumnId(); |
322 | Value v = r.getValue(idx); |
323 | if (v != null) { |
324 | array[i] = v.convertTo(c.getType()); |
325 | } |
326 | } |
327 | array[keyColumns - 1] = ValueLong.get(r.getKey()); |
328 | return ValueArray.get(array); |
329 | } |
330 | |
331 | /** |
332 | * Convert array of values to a SearchRow. |
333 | * |
334 | * @param array the index key |
335 | * @return the row |
336 | */ |
337 | SearchRow convertToSearchRow(ValueArray key) { |
338 | Value[] array = key.getList(); |
339 | SearchRow searchRow = mvTable.getTemplateRow(); |
340 | searchRow.setKey((array[array.length - 1]).getLong()); |
341 | Column[] cols = getColumns(); |
342 | for (int i = 0; i < array.length - 1; i++) { |
343 | Column c = cols[i]; |
344 | int idx = c.getColumnId(); |
345 | Value v = array[i]; |
346 | searchRow.setValue(idx, v); |
347 | } |
348 | return searchRow; |
349 | } |
350 | |
351 | @Override |
352 | public MVTable getTable() { |
353 | return mvTable; |
354 | } |
355 | |
356 | @Override |
357 | public double getCost(Session session, int[] masks, TableFilter filter, |
358 | SortOrder sortOrder) { |
359 | try { |
360 | return 10 * getCostRangeIndex(masks, |
361 | dataMap.sizeAsLongMax(), filter, sortOrder); |
362 | } catch (IllegalStateException e) { |
363 | throw DbException.get(ErrorCode.OBJECT_CLOSED, e); |
364 | } |
365 | } |
366 | |
367 | @Override |
368 | public void remove(Session session) { |
369 | TransactionMap<Value, Value> map = getMap(session); |
370 | if (!map.isClosed()) { |
371 | Transaction t = mvTable.getTransaction(session); |
372 | t.removeMap(map); |
373 | } |
374 | } |
375 | |
376 | @Override |
377 | public void truncate(Session session) { |
378 | TransactionMap<Value, Value> map = getMap(session); |
379 | map.clear(); |
380 | } |
381 | |
382 | @Override |
383 | public boolean canGetFirstOrLast() { |
384 | return true; |
385 | } |
386 | |
387 | @Override |
388 | public Cursor findFirstOrLast(Session session, boolean first) { |
389 | TransactionMap<Value, Value> map = getMap(session); |
390 | Value key = first ? map.firstKey() : map.lastKey(); |
391 | while (true) { |
392 | if (key == null) { |
393 | return new MVStoreCursor(session, |
394 | Collections.<Value>emptyList().iterator(), null); |
395 | } |
396 | if (((ValueArray) key).getList()[0] != ValueNull.INSTANCE) { |
397 | break; |
398 | } |
399 | key = first ? map.higherKey(key) : map.lowerKey(key); |
400 | } |
401 | ArrayList<Value> list = New.arrayList(); |
402 | list.add(key); |
403 | MVStoreCursor cursor = new MVStoreCursor(session, list.iterator(), null); |
404 | cursor.next(); |
405 | return cursor; |
406 | } |
407 | |
408 | @Override |
409 | public boolean needRebuild() { |
410 | try { |
411 | return dataMap.sizeAsLongMax() == 0; |
412 | } catch (IllegalStateException e) { |
413 | throw DbException.get(ErrorCode.OBJECT_CLOSED, e); |
414 | } |
415 | } |
416 | |
417 | @Override |
418 | public long getRowCount(Session session) { |
419 | TransactionMap<Value, Value> map = getMap(session); |
420 | return map.sizeAsLong(); |
421 | } |
422 | |
423 | @Override |
424 | public long getRowCountApproximation() { |
425 | try { |
426 | return dataMap.sizeAsLongMax(); |
427 | } catch (IllegalStateException e) { |
428 | throw DbException.get(ErrorCode.OBJECT_CLOSED, e); |
429 | } |
430 | } |
431 | |
432 | @Override |
433 | public long getDiskSpaceUsed() { |
434 | // TODO estimate disk space usage |
435 | return 0; |
436 | } |
437 | |
438 | @Override |
439 | public boolean canFindNext() { |
440 | return true; |
441 | } |
442 | |
443 | @Override |
444 | public Cursor findNext(Session session, SearchRow higherThan, SearchRow last) { |
445 | return find(session, higherThan, true, last); |
446 | } |
447 | |
448 | @Override |
449 | public void checkRename() { |
450 | // ok |
451 | } |
452 | |
453 | /** |
454 | * Get the map to store the data. |
455 | * |
456 | * @param session the session |
457 | * @return the map |
458 | */ |
459 | TransactionMap<Value, Value> getMap(Session session) { |
460 | if (session == null) { |
461 | return dataMap; |
462 | } |
463 | Transaction t = mvTable.getTransaction(session); |
464 | return dataMap.getInstance(t, Long.MAX_VALUE); |
465 | } |
466 | |
467 | /** |
468 | * A cursor. |
469 | */ |
470 | class MVStoreCursor implements Cursor { |
471 | |
472 | private final Session session; |
473 | private final Iterator<Value> it; |
474 | private final SearchRow last; |
475 | private Value current; |
476 | private SearchRow searchRow; |
477 | private Row row; |
478 | |
479 | public MVStoreCursor(Session session, Iterator<Value> it, SearchRow last) { |
480 | this.session = session; |
481 | this.it = it; |
482 | this.last = last; |
483 | } |
484 | |
485 | @Override |
486 | public Row get() { |
487 | if (row == null) { |
488 | SearchRow r = getSearchRow(); |
489 | if (r != null) { |
490 | row = mvTable.getRow(session, r.getKey()); |
491 | } |
492 | } |
493 | return row; |
494 | } |
495 | |
496 | @Override |
497 | public SearchRow getSearchRow() { |
498 | if (searchRow == null) { |
499 | if (current != null) { |
500 | searchRow = convertToSearchRow((ValueArray) current); |
501 | } |
502 | } |
503 | return searchRow; |
504 | } |
505 | |
506 | @Override |
507 | public boolean next() { |
508 | current = it.hasNext() ? it.next() : null; |
509 | searchRow = null; |
510 | if (current != null) { |
511 | if (last != null && compareRows(getSearchRow(), last) > 0) { |
512 | searchRow = null; |
513 | current = null; |
514 | } |
515 | } |
516 | row = null; |
517 | return current != null; |
518 | } |
519 | |
520 | @Override |
521 | public boolean previous() { |
522 | throw DbException.getUnsupportedException("previous"); |
523 | } |
524 | |
525 | } |
526 | |
527 | } |