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 java.util.Collections; |
9 | import java.util.HashMap; |
10 | import java.util.HashSet; |
11 | import java.util.Iterator; |
12 | import java.util.List; |
13 | |
14 | import org.h2.api.ErrorCode; |
15 | import org.h2.engine.Constants; |
16 | import org.h2.engine.Session; |
17 | import org.h2.engine.SysProperties; |
18 | import org.h2.engine.UndoLogRecord; |
19 | import org.h2.message.DbException; |
20 | import org.h2.result.Row; |
21 | import org.h2.result.SearchRow; |
22 | import org.h2.result.SortOrder; |
23 | import org.h2.store.Page; |
24 | import org.h2.store.PageStore; |
25 | import org.h2.table.Column; |
26 | import org.h2.table.IndexColumn; |
27 | import org.h2.table.RegularTable; |
28 | import org.h2.table.TableFilter; |
29 | import org.h2.util.MathUtils; |
30 | import org.h2.util.New; |
31 | import org.h2.value.Value; |
32 | import org.h2.value.ValueNull; |
33 | |
34 | /** |
35 | * The scan index allows to access a row by key. It can be used to iterate over |
36 | * all rows of a table. Each regular table has one such object, even if no |
37 | * primary key or indexes are defined. |
38 | */ |
39 | public class PageDataIndex extends PageIndex { |
40 | |
41 | private final PageStore store; |
42 | private final RegularTable tableData; |
43 | private long lastKey; |
44 | private long rowCount; |
45 | private HashSet<Row> delta; |
46 | private int rowCountDiff; |
47 | private final HashMap<Integer, Integer> sessionRowCount; |
48 | private int mainIndexColumn = -1; |
49 | private DbException fastDuplicateKeyException; |
50 | |
51 | /** |
52 | * The estimated heap memory per page, in number of double words (4 bytes |
53 | * each). |
54 | */ |
55 | private int memoryPerPage; |
56 | private int memoryCount; |
57 | |
58 | private final boolean multiVersion; |
59 | |
60 | public PageDataIndex(RegularTable table, int id, IndexColumn[] columns, |
61 | IndexType indexType, boolean create, Session session) { |
62 | initBaseIndex(table, id, table.getName() + "_DATA", columns, indexType); |
63 | this.multiVersion = database.isMultiVersion(); |
64 | |
65 | // trace = database.getTrace(Trace.PAGE_STORE + "_di"); |
66 | // trace.setLevel(TraceSystem.DEBUG); |
67 | if (multiVersion) { |
68 | sessionRowCount = New.hashMap(); |
69 | isMultiVersion = true; |
70 | } else { |
71 | sessionRowCount = null; |
72 | } |
73 | tableData = table; |
74 | this.store = database.getPageStore(); |
75 | store.addIndex(this); |
76 | if (!database.isPersistent()) { |
77 | throw DbException.throwInternalError(table.getName()); |
78 | } |
79 | if (create) { |
80 | rootPageId = store.allocatePage(); |
81 | store.addMeta(this, session); |
82 | PageDataLeaf root = PageDataLeaf.create(this, rootPageId, PageData.ROOT); |
83 | store.update(root); |
84 | } else { |
85 | rootPageId = store.getRootPageId(id); |
86 | PageData root = getPage(rootPageId, 0); |
87 | lastKey = root.getLastKey(); |
88 | rowCount = root.getRowCount(); |
89 | } |
90 | if (trace.isDebugEnabled()) { |
91 | trace.debug("{0} opened rows: {1}", this, rowCount); |
92 | } |
93 | table.setRowCount(rowCount); |
94 | memoryPerPage = (Constants.MEMORY_PAGE_DATA + store.getPageSize()) >> 2; |
95 | } |
96 | |
97 | @Override |
98 | public DbException getDuplicateKeyException(String key) { |
99 | if (fastDuplicateKeyException == null) { |
100 | fastDuplicateKeyException = super.getDuplicateKeyException(null); |
101 | } |
102 | return fastDuplicateKeyException; |
103 | } |
104 | |
105 | @Override |
106 | public void add(Session session, Row row) { |
107 | boolean retry = false; |
108 | if (mainIndexColumn != -1) { |
109 | row.setKey(row.getValue(mainIndexColumn).getLong()); |
110 | } else { |
111 | if (row.getKey() == 0) { |
112 | row.setKey((int) ++lastKey); |
113 | retry = true; |
114 | } |
115 | } |
116 | if (tableData.getContainsLargeObject()) { |
117 | for (int i = 0, len = row.getColumnCount(); i < len; i++) { |
118 | Value v = row.getValue(i); |
119 | Value v2 = v.link(database, getId()); |
120 | if (v2.isLinked()) { |
121 | session.unlinkAtCommitStop(v2); |
122 | } |
123 | if (v != v2) { |
124 | row.setValue(i, v2); |
125 | } |
126 | } |
127 | } |
128 | // when using auto-generated values, it's possible that multiple |
129 | // tries are required (specially if there was originally a primary key) |
130 | if (trace.isDebugEnabled()) { |
131 | trace.debug("{0} add {1}", getName(), row); |
132 | } |
133 | long add = 0; |
134 | while (true) { |
135 | try { |
136 | addTry(session, row); |
137 | break; |
138 | } catch (DbException e) { |
139 | if (e != fastDuplicateKeyException) { |
140 | throw e; |
141 | } |
142 | if (!retry) { |
143 | throw getNewDuplicateKeyException(); |
144 | } |
145 | if (add == 0) { |
146 | // in the first re-try add a small random number, |
147 | // to avoid collisions after a re-start |
148 | row.setKey((long) (row.getKey() + Math.random() * 10000)); |
149 | } else { |
150 | row.setKey(row.getKey() + add); |
151 | } |
152 | add++; |
153 | } finally { |
154 | store.incrementChangeCount(); |
155 | } |
156 | } |
157 | lastKey = Math.max(lastKey, row.getKey()); |
158 | } |
159 | |
160 | public DbException getNewDuplicateKeyException() { |
161 | String sql = "PRIMARY KEY ON " + table.getSQL(); |
162 | if (mainIndexColumn >= 0 && mainIndexColumn < indexColumns.length) { |
163 | sql += "(" + indexColumns[mainIndexColumn].getSQL() + ")"; |
164 | } |
165 | DbException e = DbException.get(ErrorCode.DUPLICATE_KEY_1, sql); |
166 | e.setSource(this); |
167 | return e; |
168 | } |
169 | |
170 | private void addTry(Session session, Row row) { |
171 | while (true) { |
172 | PageData root = getPage(rootPageId, 0); |
173 | int splitPoint = root.addRowTry(row); |
174 | if (splitPoint == -1) { |
175 | break; |
176 | } |
177 | if (trace.isDebugEnabled()) { |
178 | trace.debug("{0} split", this); |
179 | } |
180 | long pivot = splitPoint == 0 ? row.getKey() : root.getKey(splitPoint - 1); |
181 | PageData page1 = root; |
182 | PageData page2 = root.split(splitPoint); |
183 | int id = store.allocatePage(); |
184 | page1.setPageId(id); |
185 | page1.setParentPageId(rootPageId); |
186 | page2.setParentPageId(rootPageId); |
187 | PageDataNode newRoot = PageDataNode.create(this, rootPageId, PageData.ROOT); |
188 | newRoot.init(page1, pivot, page2); |
189 | store.update(page1); |
190 | store.update(page2); |
191 | store.update(newRoot); |
192 | root = newRoot; |
193 | } |
194 | row.setDeleted(false); |
195 | if (multiVersion) { |
196 | if (delta == null) { |
197 | delta = New.hashSet(); |
198 | } |
199 | boolean wasDeleted = delta.remove(row); |
200 | if (!wasDeleted) { |
201 | delta.add(row); |
202 | } |
203 | incrementRowCount(session.getId(), 1); |
204 | } |
205 | invalidateRowCount(); |
206 | rowCount++; |
207 | store.logAddOrRemoveRow(session, tableData.getId(), row, true); |
208 | } |
209 | |
210 | /** |
211 | * Read an overflow page page. |
212 | * |
213 | * @param id the page id |
214 | * @return the page |
215 | */ |
216 | PageDataOverflow getPageOverflow(int id) { |
217 | Page p = store.getPage(id); |
218 | if (p instanceof PageDataOverflow) { |
219 | return (PageDataOverflow) p; |
220 | } |
221 | throw DbException.get(ErrorCode.FILE_CORRUPTED_1, |
222 | p == null ? "null" : p.toString()); |
223 | } |
224 | |
225 | /** |
226 | * Read the given page. |
227 | * |
228 | * @param id the page id |
229 | * @param parent the parent, or -1 if unknown |
230 | * @return the page |
231 | */ |
232 | PageData getPage(int id, int parent) { |
233 | Page pd = store.getPage(id); |
234 | if (pd == null) { |
235 | PageDataLeaf empty = PageDataLeaf.create(this, id, parent); |
236 | // could have been created before, but never committed |
237 | store.logUndo(empty, null); |
238 | store.update(empty); |
239 | return empty; |
240 | } else if (!(pd instanceof PageData)) { |
241 | throw DbException.get(ErrorCode.FILE_CORRUPTED_1, "" + pd); |
242 | } |
243 | PageData p = (PageData) pd; |
244 | if (parent != -1) { |
245 | if (p.getParentPageId() != parent) { |
246 | throw DbException.throwInternalError(p + |
247 | " parent " + p.getParentPageId() + " expected " + parent); |
248 | } |
249 | } |
250 | return p; |
251 | } |
252 | |
253 | @Override |
254 | public boolean canGetFirstOrLast() { |
255 | return false; |
256 | } |
257 | |
258 | /** |
259 | * Get the key from the row. |
260 | * |
261 | * @param row the row |
262 | * @param ifEmpty the value to use if the row is empty |
263 | * @param ifNull the value to use if the column is NULL |
264 | * @return the key |
265 | */ |
266 | long getKey(SearchRow row, long ifEmpty, long ifNull) { |
267 | if (row == null) { |
268 | return ifEmpty; |
269 | } |
270 | Value v = row.getValue(mainIndexColumn); |
271 | if (v == null) { |
272 | throw DbException.throwInternalError(row.toString()); |
273 | } else if (v == ValueNull.INSTANCE) { |
274 | return ifNull; |
275 | } |
276 | return v.getLong(); |
277 | } |
278 | |
279 | @Override |
280 | public Cursor find(Session session, SearchRow first, SearchRow last) { |
281 | long from = first == null ? Long.MIN_VALUE : first.getKey(); |
282 | long to = last == null ? Long.MAX_VALUE : last.getKey(); |
283 | PageData root = getPage(rootPageId, 0); |
284 | return root.find(session, from, to, isMultiVersion); |
285 | |
286 | } |
287 | |
288 | /** |
289 | * Search for a specific row or a set of rows. |
290 | * |
291 | * @param session the session |
292 | * @param first the key of the first row |
293 | * @param last the key of the last row |
294 | * @param multiVersion if mvcc should be used |
295 | * @return the cursor |
296 | */ |
297 | Cursor find(Session session, long first, long last, boolean multiVersion) { |
298 | PageData root = getPage(rootPageId, 0); |
299 | return root.find(session, first, last, multiVersion); |
300 | } |
301 | |
302 | @Override |
303 | public Cursor findFirstOrLast(Session session, boolean first) { |
304 | throw DbException.throwInternalError(); |
305 | } |
306 | |
307 | long getLastKey() { |
308 | PageData root = getPage(rootPageId, 0); |
309 | return root.getLastKey(); |
310 | } |
311 | |
312 | @Override |
313 | public double getCost(Session session, int[] masks, TableFilter filter, |
314 | SortOrder sortOrder) { |
315 | long cost = 10 * (tableData.getRowCountApproximation() + |
316 | Constants.COST_ROW_OFFSET); |
317 | return cost; |
318 | } |
319 | |
320 | @Override |
321 | public boolean needRebuild() { |
322 | return false; |
323 | } |
324 | |
325 | @Override |
326 | public void remove(Session session, Row row) { |
327 | if (tableData.getContainsLargeObject()) { |
328 | for (int i = 0, len = row.getColumnCount(); i < len; i++) { |
329 | Value v = row.getValue(i); |
330 | if (v.isLinked()) { |
331 | session.unlinkAtCommit(v); |
332 | } |
333 | } |
334 | } |
335 | if (trace.isDebugEnabled()) { |
336 | trace.debug("{0} remove {1}", getName(), row); |
337 | } |
338 | if (rowCount == 1) { |
339 | removeAllRows(); |
340 | } else { |
341 | try { |
342 | long key = row.getKey(); |
343 | PageData root = getPage(rootPageId, 0); |
344 | root.remove(key); |
345 | invalidateRowCount(); |
346 | rowCount--; |
347 | } finally { |
348 | store.incrementChangeCount(); |
349 | } |
350 | } |
351 | if (multiVersion) { |
352 | // if storage is null, the delete flag is not yet set |
353 | row.setDeleted(true); |
354 | if (delta == null) { |
355 | delta = New.hashSet(); |
356 | } |
357 | boolean wasAdded = delta.remove(row); |
358 | if (!wasAdded) { |
359 | delta.add(row); |
360 | } |
361 | incrementRowCount(session.getId(), -1); |
362 | } |
363 | store.logAddOrRemoveRow(session, tableData.getId(), row, false); |
364 | } |
365 | |
366 | @Override |
367 | public void remove(Session session) { |
368 | if (trace.isDebugEnabled()) { |
369 | trace.debug("{0} remove", this); |
370 | } |
371 | removeAllRows(); |
372 | store.free(rootPageId); |
373 | store.removeMeta(this, session); |
374 | } |
375 | |
376 | @Override |
377 | public void truncate(Session session) { |
378 | if (trace.isDebugEnabled()) { |
379 | trace.debug("{0} truncate", this); |
380 | } |
381 | store.logTruncate(session, tableData.getId()); |
382 | removeAllRows(); |
383 | if (tableData.getContainsLargeObject() && tableData.isPersistData()) { |
384 | // unfortunately, the data is gone on rollback |
385 | session.commit(false); |
386 | database.getLobStorage().removeAllForTable(table.getId()); |
387 | } |
388 | if (multiVersion) { |
389 | sessionRowCount.clear(); |
390 | } |
391 | tableData.setRowCount(0); |
392 | } |
393 | |
394 | private void removeAllRows() { |
395 | try { |
396 | PageData root = getPage(rootPageId, 0); |
397 | root.freeRecursive(); |
398 | root = PageDataLeaf.create(this, rootPageId, PageData.ROOT); |
399 | store.removeFromCache(rootPageId); |
400 | store.update(root); |
401 | rowCount = 0; |
402 | lastKey = 0; |
403 | } finally { |
404 | store.incrementChangeCount(); |
405 | } |
406 | } |
407 | |
408 | @Override |
409 | public void checkRename() { |
410 | throw DbException.getUnsupportedException("PAGE"); |
411 | } |
412 | |
413 | @Override |
414 | public Row getRow(Session session, long key) { |
415 | return getRowWithKey(key); |
416 | } |
417 | |
418 | /** |
419 | * Get the row with the given key. |
420 | * |
421 | * @param key the key |
422 | * @return the row |
423 | */ |
424 | public Row getRowWithKey(long key) { |
425 | PageData root = getPage(rootPageId, 0); |
426 | return root.getRowWithKey(key); |
427 | } |
428 | |
429 | PageStore getPageStore() { |
430 | return store; |
431 | } |
432 | |
433 | @Override |
434 | public long getRowCountApproximation() { |
435 | return rowCount; |
436 | } |
437 | |
438 | @Override |
439 | public long getRowCount(Session session) { |
440 | if (multiVersion) { |
441 | Integer i = sessionRowCount.get(session.getId()); |
442 | long count = i == null ? 0 : i.intValue(); |
443 | count += rowCount; |
444 | count -= rowCountDiff; |
445 | return count; |
446 | } |
447 | return rowCount; |
448 | } |
449 | |
450 | @Override |
451 | public long getDiskSpaceUsed() { |
452 | PageData root = getPage(rootPageId, 0); |
453 | return root.getDiskSpaceUsed(); |
454 | } |
455 | |
456 | @Override |
457 | public String getCreateSQL() { |
458 | return null; |
459 | } |
460 | |
461 | @Override |
462 | public int getColumnIndex(Column col) { |
463 | // can not use this index - use the PageDelegateIndex instead |
464 | return -1; |
465 | } |
466 | |
467 | @Override |
468 | public void close(Session session) { |
469 | if (trace.isDebugEnabled()) { |
470 | trace.debug("{0} close", this); |
471 | } |
472 | if (delta != null) { |
473 | delta.clear(); |
474 | } |
475 | rowCountDiff = 0; |
476 | if (sessionRowCount != null) { |
477 | sessionRowCount.clear(); |
478 | } |
479 | // can not close the index because it might get used afterwards, |
480 | // for example after running recovery |
481 | writeRowCount(); |
482 | } |
483 | |
484 | Iterator<Row> getDelta() { |
485 | if (delta == null) { |
486 | List<Row> e = Collections.emptyList(); |
487 | return e.iterator(); |
488 | } |
489 | return delta.iterator(); |
490 | } |
491 | |
492 | private void incrementRowCount(int sessionId, int count) { |
493 | if (multiVersion) { |
494 | Integer id = sessionId; |
495 | Integer c = sessionRowCount.get(id); |
496 | int current = c == null ? 0 : c.intValue(); |
497 | sessionRowCount.put(id, current + count); |
498 | rowCountDiff += count; |
499 | } |
500 | } |
501 | |
502 | @Override |
503 | public void commit(int operation, Row row) { |
504 | if (multiVersion) { |
505 | if (delta != null) { |
506 | delta.remove(row); |
507 | } |
508 | incrementRowCount(row.getSessionId(), |
509 | operation == UndoLogRecord.DELETE ? 1 : -1); |
510 | } |
511 | } |
512 | |
513 | /** |
514 | * The root page has changed. |
515 | * |
516 | * @param session the session |
517 | * @param newPos the new position |
518 | */ |
519 | void setRootPageId(Session session, int newPos) { |
520 | store.removeMeta(this, session); |
521 | this.rootPageId = newPos; |
522 | store.addMeta(this, session); |
523 | store.addIndex(this); |
524 | } |
525 | |
526 | public void setMainIndexColumn(int mainIndexColumn) { |
527 | this.mainIndexColumn = mainIndexColumn; |
528 | } |
529 | |
530 | public int getMainIndexColumn() { |
531 | return mainIndexColumn; |
532 | } |
533 | |
534 | @Override |
535 | public String toString() { |
536 | return getName(); |
537 | } |
538 | |
539 | private void invalidateRowCount() { |
540 | PageData root = getPage(rootPageId, 0); |
541 | root.setRowCountStored(PageData.UNKNOWN_ROWCOUNT); |
542 | } |
543 | |
544 | @Override |
545 | public void writeRowCount() { |
546 | if (SysProperties.MODIFY_ON_WRITE && rootPageId == 0) { |
547 | // currently creating the index |
548 | return; |
549 | } |
550 | try { |
551 | PageData root = getPage(rootPageId, 0); |
552 | root.setRowCountStored(MathUtils.convertLongToInt(rowCount)); |
553 | } finally { |
554 | store.incrementChangeCount(); |
555 | } |
556 | } |
557 | |
558 | @Override |
559 | public String getPlanSQL() { |
560 | return table.getSQL() + ".tableScan"; |
561 | } |
562 | |
563 | int getMemoryPerPage() { |
564 | return memoryPerPage; |
565 | } |
566 | |
567 | /** |
568 | * The memory usage of a page was changed. The new value is used to adopt |
569 | * the average estimated memory size of a page. |
570 | * |
571 | * @param x the new memory size |
572 | */ |
573 | void memoryChange(int x) { |
574 | if (memoryCount < Constants.MEMORY_FACTOR) { |
575 | memoryPerPage += (x - memoryPerPage) / ++memoryCount; |
576 | } else { |
577 | memoryPerPage += (x > memoryPerPage ? 1 : -1) + |
578 | ((x - memoryPerPage) / Constants.MEMORY_FACTOR); |
579 | } |
580 | } |
581 | |
582 | @Override |
583 | public boolean isRowIdIndex() { |
584 | return true; |
585 | } |
586 | |
587 | } |