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.Session; |
11 | import org.h2.engine.SysProperties; |
12 | import org.h2.message.DbException; |
13 | import org.h2.result.Row; |
14 | import org.h2.result.SearchRow; |
15 | import org.h2.result.SortOrder; |
16 | import org.h2.store.Data; |
17 | import org.h2.store.Page; |
18 | import org.h2.store.PageStore; |
19 | import org.h2.table.Column; |
20 | import org.h2.table.IndexColumn; |
21 | import org.h2.table.RegularTable; |
22 | import org.h2.table.TableFilter; |
23 | import org.h2.util.MathUtils; |
24 | import org.h2.value.Value; |
25 | import org.h2.value.ValueNull; |
26 | |
27 | /** |
28 | * This is the most common type of index, a b tree index. |
29 | * Only the data of the indexed columns are stored in the index. |
30 | */ |
31 | public class PageBtreeIndex extends PageIndex { |
32 | |
33 | private static int memoryChangeRequired; |
34 | |
35 | private final PageStore store; |
36 | private final RegularTable tableData; |
37 | private final boolean needRebuild; |
38 | private long rowCount; |
39 | private int memoryPerPage; |
40 | private int memoryCount; |
41 | |
42 | public PageBtreeIndex(RegularTable table, int id, String indexName, |
43 | IndexColumn[] columns, |
44 | IndexType indexType, boolean create, Session session) { |
45 | initBaseIndex(table, id, indexName, columns, indexType); |
46 | if (!database.isStarting() && create) { |
47 | checkIndexColumnTypes(columns); |
48 | } |
49 | // int test; |
50 | // trace.setLevel(TraceSystem.DEBUG); |
51 | tableData = table; |
52 | if (!database.isPersistent() || id < 0) { |
53 | throw DbException.throwInternalError("" + indexName); |
54 | } |
55 | this.store = database.getPageStore(); |
56 | store.addIndex(this); |
57 | if (create) { |
58 | // new index |
59 | rootPageId = store.allocatePage(); |
60 | // TODO currently the head position is stored in the log |
61 | // it should not for new tables, otherwise redo of other operations |
62 | // must ensure this page is not used for other things |
63 | store.addMeta(this, session); |
64 | PageBtreeLeaf root = PageBtreeLeaf.create(this, rootPageId, PageBtree.ROOT); |
65 | store.logUndo(root, null); |
66 | store.update(root); |
67 | } else { |
68 | rootPageId = store.getRootPageId(id); |
69 | PageBtree root = getPage(rootPageId); |
70 | rowCount = root.getRowCount(); |
71 | } |
72 | this.needRebuild = create || (rowCount == 0 && store.isRecoveryRunning()); |
73 | if (trace.isDebugEnabled()) { |
74 | trace.debug("opened {0} rows: {1}", getName() , rowCount); |
75 | } |
76 | memoryPerPage = (Constants.MEMORY_PAGE_BTREE + store.getPageSize()) >> 2; |
77 | } |
78 | |
79 | @Override |
80 | public void add(Session session, Row row) { |
81 | if (trace.isDebugEnabled()) { |
82 | trace.debug("{0} add {1}", getName(), row); |
83 | } |
84 | // safe memory |
85 | SearchRow newRow = getSearchRow(row); |
86 | try { |
87 | addRow(newRow); |
88 | } finally { |
89 | store.incrementChangeCount(); |
90 | } |
91 | } |
92 | |
93 | private void addRow(SearchRow newRow) { |
94 | while (true) { |
95 | PageBtree root = getPage(rootPageId); |
96 | int splitPoint = root.addRowTry(newRow); |
97 | if (splitPoint == -1) { |
98 | break; |
99 | } |
100 | if (trace.isDebugEnabled()) { |
101 | trace.debug("split {0}", splitPoint); |
102 | } |
103 | SearchRow pivot = root.getRow(splitPoint - 1); |
104 | store.logUndo(root, root.data); |
105 | PageBtree page1 = root; |
106 | PageBtree page2 = root.split(splitPoint); |
107 | store.logUndo(page2, null); |
108 | int id = store.allocatePage(); |
109 | page1.setPageId(id); |
110 | page1.setParentPageId(rootPageId); |
111 | page2.setParentPageId(rootPageId); |
112 | PageBtreeNode newRoot = PageBtreeNode.create( |
113 | this, rootPageId, PageBtree.ROOT); |
114 | store.logUndo(newRoot, null); |
115 | newRoot.init(page1, pivot, page2); |
116 | store.update(page1); |
117 | store.update(page2); |
118 | store.update(newRoot); |
119 | root = newRoot; |
120 | } |
121 | invalidateRowCount(); |
122 | rowCount++; |
123 | } |
124 | |
125 | /** |
126 | * Create a search row for this row. |
127 | * |
128 | * @param row the row |
129 | * @return the search row |
130 | */ |
131 | private SearchRow getSearchRow(Row row) { |
132 | SearchRow r = table.getTemplateSimpleRow(columns.length == 1); |
133 | r.setKeyAndVersion(row); |
134 | for (Column c : columns) { |
135 | int idx = c.getColumnId(); |
136 | r.setValue(idx, row.getValue(idx)); |
137 | } |
138 | return r; |
139 | } |
140 | |
141 | /** |
142 | * Read the given page. |
143 | * |
144 | * @param id the page id |
145 | * @return the page |
146 | */ |
147 | PageBtree getPage(int id) { |
148 | Page p = store.getPage(id); |
149 | if (p == null) { |
150 | PageBtreeLeaf empty = PageBtreeLeaf.create(this, id, PageBtree.ROOT); |
151 | // could have been created before, but never committed |
152 | store.logUndo(empty, null); |
153 | store.update(empty); |
154 | return empty; |
155 | } else if (!(p instanceof PageBtree)) { |
156 | throw DbException.get(ErrorCode.FILE_CORRUPTED_1, "" + p); |
157 | } |
158 | return (PageBtree) p; |
159 | } |
160 | |
161 | @Override |
162 | public boolean canGetFirstOrLast() { |
163 | return true; |
164 | } |
165 | |
166 | @Override |
167 | public Cursor findNext(Session session, SearchRow first, SearchRow last) { |
168 | return find(session, first, true, last); |
169 | } |
170 | |
171 | @Override |
172 | public Cursor find(Session session, SearchRow first, SearchRow last) { |
173 | return find(session, first, false, last); |
174 | } |
175 | |
176 | private Cursor find(Session session, SearchRow first, boolean bigger, |
177 | SearchRow last) { |
178 | if (SysProperties.CHECK && store == null) { |
179 | throw DbException.get(ErrorCode.OBJECT_CLOSED); |
180 | } |
181 | PageBtree root = getPage(rootPageId); |
182 | PageBtreeCursor cursor = new PageBtreeCursor(session, this, last); |
183 | root.find(cursor, first, bigger); |
184 | return cursor; |
185 | } |
186 | |
187 | @Override |
188 | public Cursor findFirstOrLast(Session session, boolean first) { |
189 | if (first) { |
190 | // TODO optimization: this loops through NULL elements |
191 | Cursor cursor = find(session, null, false, null); |
192 | while (cursor.next()) { |
193 | SearchRow row = cursor.getSearchRow(); |
194 | Value v = row.getValue(columnIds[0]); |
195 | if (v != ValueNull.INSTANCE) { |
196 | return cursor; |
197 | } |
198 | } |
199 | return cursor; |
200 | } |
201 | PageBtree root = getPage(rootPageId); |
202 | PageBtreeCursor cursor = new PageBtreeCursor(session, this, null); |
203 | root.last(cursor); |
204 | cursor.previous(); |
205 | // TODO optimization: this loops through NULL elements |
206 | do { |
207 | SearchRow row = cursor.getSearchRow(); |
208 | if (row == null) { |
209 | break; |
210 | } |
211 | Value v = row.getValue(columnIds[0]); |
212 | if (v != ValueNull.INSTANCE) { |
213 | return cursor; |
214 | } |
215 | } while (cursor.previous()); |
216 | return cursor; |
217 | } |
218 | |
219 | @Override |
220 | public double getCost(Session session, int[] masks, TableFilter filter, |
221 | SortOrder sortOrder) { |
222 | return 10 * getCostRangeIndex(masks, tableData.getRowCount(session), |
223 | filter, sortOrder); |
224 | } |
225 | |
226 | @Override |
227 | public boolean needRebuild() { |
228 | return needRebuild; |
229 | } |
230 | |
231 | @Override |
232 | public void remove(Session session, Row row) { |
233 | if (trace.isDebugEnabled()) { |
234 | trace.debug("{0} remove {1}", getName(), row); |
235 | } |
236 | // TODO invalidate row count |
237 | // setChanged(session); |
238 | if (rowCount == 1) { |
239 | removeAllRows(); |
240 | } else { |
241 | try { |
242 | PageBtree root = getPage(rootPageId); |
243 | root.remove(row); |
244 | invalidateRowCount(); |
245 | rowCount--; |
246 | } finally { |
247 | store.incrementChangeCount(); |
248 | } |
249 | } |
250 | } |
251 | |
252 | @Override |
253 | public void remove(Session session) { |
254 | if (trace.isDebugEnabled()) { |
255 | trace.debug("remove"); |
256 | } |
257 | removeAllRows(); |
258 | store.free(rootPageId); |
259 | store.removeMeta(this, session); |
260 | } |
261 | |
262 | @Override |
263 | public void truncate(Session session) { |
264 | if (trace.isDebugEnabled()) { |
265 | trace.debug("truncate"); |
266 | } |
267 | removeAllRows(); |
268 | if (tableData.getContainsLargeObject()) { |
269 | database.getLobStorage().removeAllForTable(table.getId()); |
270 | } |
271 | tableData.setRowCount(0); |
272 | } |
273 | |
274 | private void removeAllRows() { |
275 | try { |
276 | PageBtree root = getPage(rootPageId); |
277 | root.freeRecursive(); |
278 | root = PageBtreeLeaf.create(this, rootPageId, PageBtree.ROOT); |
279 | store.removeFromCache(rootPageId); |
280 | store.update(root); |
281 | rowCount = 0; |
282 | } finally { |
283 | store.incrementChangeCount(); |
284 | } |
285 | } |
286 | |
287 | @Override |
288 | public void checkRename() { |
289 | // ok |
290 | } |
291 | |
292 | /** |
293 | * Get a row from the main index. |
294 | * |
295 | * @param session the session |
296 | * @param key the row key |
297 | * @return the row |
298 | */ |
299 | @Override |
300 | public Row getRow(Session session, long key) { |
301 | return tableData.getRow(session, key); |
302 | } |
303 | |
304 | PageStore getPageStore() { |
305 | return store; |
306 | } |
307 | |
308 | @Override |
309 | public long getRowCountApproximation() { |
310 | return tableData.getRowCountApproximation(); |
311 | } |
312 | |
313 | @Override |
314 | public long getDiskSpaceUsed() { |
315 | return tableData.getDiskSpaceUsed(); |
316 | } |
317 | |
318 | @Override |
319 | public long getRowCount(Session session) { |
320 | return rowCount; |
321 | } |
322 | |
323 | @Override |
324 | public void close(Session session) { |
325 | if (trace.isDebugEnabled()) { |
326 | trace.debug("close"); |
327 | } |
328 | // can not close the index because it might get used afterwards, |
329 | // for example after running recovery |
330 | try { |
331 | writeRowCount(); |
332 | } finally { |
333 | store.incrementChangeCount(); |
334 | } |
335 | } |
336 | |
337 | /** |
338 | * Read a row from the data page at the given offset. |
339 | * |
340 | * @param data the data |
341 | * @param offset the offset |
342 | * @param onlyPosition whether only the position of the row is stored |
343 | * @param needData whether the row data is required |
344 | * @return the row |
345 | */ |
346 | SearchRow readRow(Data data, int offset, boolean onlyPosition, |
347 | boolean needData) { |
348 | synchronized (data) { |
349 | data.setPos(offset); |
350 | long key = data.readVarLong(); |
351 | if (onlyPosition) { |
352 | if (needData) { |
353 | return tableData.getRow(null, key); |
354 | } |
355 | SearchRow row = table.getTemplateSimpleRow(true); |
356 | row.setKey(key); |
357 | return row; |
358 | } |
359 | SearchRow row = table.getTemplateSimpleRow(columns.length == 1); |
360 | row.setKey(key); |
361 | for (Column col : columns) { |
362 | int idx = col.getColumnId(); |
363 | row.setValue(idx, data.readValue()); |
364 | } |
365 | return row; |
366 | } |
367 | } |
368 | |
369 | /** |
370 | * Get the complete row from the data index. |
371 | * |
372 | * @param key the key |
373 | * @return the row |
374 | */ |
375 | SearchRow readRow(long key) { |
376 | return tableData.getRow(null, key); |
377 | } |
378 | |
379 | /** |
380 | * Write a row to the data page at the given offset. |
381 | * |
382 | * @param data the data |
383 | * @param offset the offset |
384 | * @param onlyPosition whether only the position of the row is stored |
385 | * @param row the row to write |
386 | */ |
387 | void writeRow(Data data, int offset, SearchRow row, boolean onlyPosition) { |
388 | data.setPos(offset); |
389 | data.writeVarLong(row.getKey()); |
390 | if (!onlyPosition) { |
391 | for (Column col : columns) { |
392 | int idx = col.getColumnId(); |
393 | data.writeValue(row.getValue(idx)); |
394 | } |
395 | } |
396 | } |
397 | |
398 | /** |
399 | * Get the size of a row (only the part that is stored in the index). |
400 | * |
401 | * @param dummy a dummy data page to calculate the size |
402 | * @param row the row |
403 | * @param onlyPosition whether only the position of the row is stored |
404 | * @return the number of bytes |
405 | */ |
406 | int getRowSize(Data dummy, SearchRow row, boolean onlyPosition) { |
407 | int rowsize = Data.getVarLongLen(row.getKey()); |
408 | if (!onlyPosition) { |
409 | for (Column col : columns) { |
410 | Value v = row.getValue(col.getColumnId()); |
411 | rowsize += dummy.getValueLen(v); |
412 | } |
413 | } |
414 | return rowsize; |
415 | } |
416 | |
417 | @Override |
418 | public boolean canFindNext() { |
419 | return true; |
420 | } |
421 | |
422 | /** |
423 | * The root page has changed. |
424 | * |
425 | * @param session the session |
426 | * @param newPos the new position |
427 | */ |
428 | void setRootPageId(Session session, int newPos) { |
429 | store.removeMeta(this, session); |
430 | this.rootPageId = newPos; |
431 | store.addMeta(this, session); |
432 | store.addIndex(this); |
433 | } |
434 | |
435 | private void invalidateRowCount() { |
436 | PageBtree root = getPage(rootPageId); |
437 | root.setRowCountStored(PageData.UNKNOWN_ROWCOUNT); |
438 | } |
439 | |
440 | @Override |
441 | public void writeRowCount() { |
442 | if (SysProperties.MODIFY_ON_WRITE && rootPageId == 0) { |
443 | // currently creating the index |
444 | return; |
445 | } |
446 | PageBtree root = getPage(rootPageId); |
447 | root.setRowCountStored(MathUtils.convertLongToInt(rowCount)); |
448 | } |
449 | |
450 | /** |
451 | * Check whether the given row contains data. |
452 | * |
453 | * @param row the row |
454 | * @return true if it contains data |
455 | */ |
456 | boolean hasData(SearchRow row) { |
457 | return row.getValue(columns[0].getColumnId()) != null; |
458 | } |
459 | |
460 | int getMemoryPerPage() { |
461 | return memoryPerPage; |
462 | } |
463 | |
464 | /** |
465 | * The memory usage of a page was changed. The new value is used to adopt |
466 | * the average estimated memory size of a page. |
467 | * |
468 | * @param x the new memory size |
469 | */ |
470 | void memoryChange(int x) { |
471 | if (memoryCount < Constants.MEMORY_FACTOR) { |
472 | memoryPerPage += (x - memoryPerPage) / ++memoryCount; |
473 | } else { |
474 | memoryPerPage += (x > memoryPerPage ? 1 : -1) + |
475 | ((x - memoryPerPage) / Constants.MEMORY_FACTOR); |
476 | } |
477 | } |
478 | |
479 | /** |
480 | * Check if calculating the memory is required. |
481 | * |
482 | * @return true if it is |
483 | */ |
484 | static boolean isMemoryChangeRequired() { |
485 | if (memoryChangeRequired-- <= 0) { |
486 | memoryChangeRequired = 10; |
487 | return true; |
488 | } |
489 | return false; |
490 | } |
491 | |
492 | } |