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.lang.ref.SoftReference; |
9 | import java.util.Arrays; |
10 | |
11 | import org.h2.api.ErrorCode; |
12 | import org.h2.engine.Constants; |
13 | import org.h2.engine.Session; |
14 | import org.h2.engine.SysProperties; |
15 | import org.h2.message.DbException; |
16 | import org.h2.result.Row; |
17 | import org.h2.store.Data; |
18 | import org.h2.store.Page; |
19 | import org.h2.store.PageStore; |
20 | import org.h2.table.RegularTable; |
21 | import org.h2.value.Value; |
22 | |
23 | /** |
24 | * A leaf page that contains data of one or multiple rows. Format: |
25 | * <ul> |
26 | * <li>page type: byte (0)</li> |
27 | * <li>checksum: short (1-2)</li> |
28 | * <li>parent page id (0 for root): int (3-6)</li> |
29 | * <li>table id: varInt</li> |
30 | * <li>column count: varInt</li> |
31 | * <li>entry count: short</li> |
32 | * <li>with overflow: the first overflow page id: int</li> |
33 | * <li>list of key / offset pairs (key: varLong, offset: shortInt)</li> |
34 | * <li>data</li> |
35 | * </ul> |
36 | */ |
37 | public class PageDataLeaf extends PageData { |
38 | |
39 | private final boolean optimizeUpdate; |
40 | |
41 | /** |
42 | * The row offsets. |
43 | */ |
44 | private int[] offsets; |
45 | |
46 | /** |
47 | * The rows. |
48 | */ |
49 | private Row[] rows; |
50 | |
51 | /** |
52 | * For pages with overflow: the soft reference to the row |
53 | */ |
54 | private SoftReference<Row> rowRef; |
55 | |
56 | /** |
57 | * The page id of the first overflow page (0 if no overflow). |
58 | */ |
59 | private int firstOverflowPageId; |
60 | |
61 | /** |
62 | * The start of the data area. |
63 | */ |
64 | private int start; |
65 | |
66 | /** |
67 | * The size of the row in bytes for large rows. |
68 | */ |
69 | private int overflowRowSize; |
70 | |
71 | private int columnCount; |
72 | |
73 | private int memoryData; |
74 | |
75 | private boolean writtenData; |
76 | |
77 | private PageDataLeaf(PageDataIndex index, int pageId, Data data) { |
78 | super(index, pageId, data); |
79 | this.optimizeUpdate = index.getDatabase().getSettings().optimizeUpdate; |
80 | } |
81 | |
82 | /** |
83 | * Create a new page. |
84 | * |
85 | * @param index the index |
86 | * @param pageId the page id |
87 | * @param parentPageId the parent |
88 | * @return the page |
89 | */ |
90 | static PageDataLeaf create(PageDataIndex index, int pageId, int parentPageId) { |
91 | PageDataLeaf p = new PageDataLeaf(index, pageId, index.getPageStore() |
92 | .createData()); |
93 | index.getPageStore().logUndo(p, null); |
94 | p.rows = Row.EMPTY_ARRAY; |
95 | p.parentPageId = parentPageId; |
96 | p.columnCount = index.getTable().getColumns().length; |
97 | p.writeHead(); |
98 | p.start = p.data.length(); |
99 | return p; |
100 | } |
101 | |
102 | /** |
103 | * Read a data leaf page. |
104 | * |
105 | * @param index the index |
106 | * @param data the data |
107 | * @param pageId the page id |
108 | * @return the page |
109 | */ |
110 | public static Page read(PageDataIndex index, Data data, int pageId) { |
111 | PageDataLeaf p = new PageDataLeaf(index, pageId, data); |
112 | p.read(); |
113 | return p; |
114 | } |
115 | |
116 | private void read() { |
117 | data.reset(); |
118 | int type = data.readByte(); |
119 | data.readShortInt(); |
120 | this.parentPageId = data.readInt(); |
121 | int tableId = data.readVarInt(); |
122 | if (tableId != index.getId()) { |
123 | throw DbException.get(ErrorCode.FILE_CORRUPTED_1, |
124 | "page:" + getPos() + " expected table:" + index.getId() + |
125 | " got:" + tableId + " type:" + type); |
126 | } |
127 | columnCount = data.readVarInt(); |
128 | entryCount = data.readShortInt(); |
129 | offsets = new int[entryCount]; |
130 | keys = new long[entryCount]; |
131 | rows = new Row[entryCount]; |
132 | if (type == Page.TYPE_DATA_LEAF) { |
133 | if (entryCount != 1) { |
134 | DbException.throwInternalError("entries: " + entryCount); |
135 | } |
136 | firstOverflowPageId = data.readInt(); |
137 | } |
138 | for (int i = 0; i < entryCount; i++) { |
139 | keys[i] = data.readVarLong(); |
140 | offsets[i] = data.readShortInt(); |
141 | } |
142 | start = data.length(); |
143 | written = true; |
144 | writtenData = true; |
145 | } |
146 | |
147 | private int getRowLength(Row row) { |
148 | int size = 0; |
149 | for (int i = 0; i < columnCount; i++) { |
150 | size += data.getValueLen(row.getValue(i)); |
151 | } |
152 | return size; |
153 | } |
154 | |
155 | private int findInsertionPoint(long key) { |
156 | int x = find(key); |
157 | if (x < entryCount && keys[x] == key) { |
158 | throw index.getDuplicateKeyException(""+key); |
159 | } |
160 | return x; |
161 | } |
162 | |
163 | @Override |
164 | int addRowTry(Row row) { |
165 | index.getPageStore().logUndo(this, data); |
166 | int rowLength = getRowLength(row); |
167 | int pageSize = index.getPageStore().getPageSize(); |
168 | int last = entryCount == 0 ? pageSize : offsets[entryCount - 1]; |
169 | int keyOffsetPairLen = 2 + Data.getVarLongLen(row.getKey()); |
170 | if (entryCount > 0 && last - rowLength < start + keyOffsetPairLen) { |
171 | int x = findInsertionPoint(row.getKey()); |
172 | if (entryCount > 1) { |
173 | if (entryCount < 5) { |
174 | // required, otherwise the index doesn't work correctly |
175 | return entryCount / 2; |
176 | } |
177 | if (index.isSortedInsertMode()) { |
178 | return x < 2 ? 1 : x > entryCount - 1 ? entryCount - 1 : x; |
179 | } |
180 | // split near the insertion point to better fill pages |
181 | // split in half would be: |
182 | // return entryCount / 2; |
183 | int third = entryCount / 3; |
184 | return x < third ? third : x >= 2 * third ? 2 * third : x; |
185 | } |
186 | return x; |
187 | } |
188 | index.getPageStore().logUndo(this, data); |
189 | int x; |
190 | if (entryCount == 0) { |
191 | x = 0; |
192 | } else { |
193 | if (!optimizeUpdate) { |
194 | readAllRows(); |
195 | } |
196 | x = findInsertionPoint(row.getKey()); |
197 | } |
198 | written = false; |
199 | changeCount = index.getPageStore().getChangeCount(); |
200 | last = x == 0 ? pageSize : offsets[x - 1]; |
201 | int offset = last - rowLength; |
202 | start += keyOffsetPairLen; |
203 | offsets = insert(offsets, entryCount, x, offset); |
204 | add(offsets, x + 1, entryCount + 1, -rowLength); |
205 | keys = insert(keys, entryCount, x, row.getKey()); |
206 | rows = insert(rows, entryCount, x, row); |
207 | entryCount++; |
208 | index.getPageStore().update(this); |
209 | if (optimizeUpdate) { |
210 | if (writtenData && offset >= start) { |
211 | byte[] d = data.getBytes(); |
212 | int dataStart = offsets[entryCount - 1] + rowLength; |
213 | int dataEnd = offsets[x]; |
214 | System.arraycopy(d, dataStart, d, dataStart - rowLength, |
215 | dataEnd - dataStart + rowLength); |
216 | data.setPos(dataEnd); |
217 | for (int j = 0; j < columnCount; j++) { |
218 | data.writeValue(row.getValue(j)); |
219 | } |
220 | } |
221 | } |
222 | if (offset < start) { |
223 | writtenData = false; |
224 | if (entryCount > 1) { |
225 | DbException.throwInternalError(); |
226 | } |
227 | // need to write the overflow page id |
228 | start += 4; |
229 | int remaining = rowLength - (pageSize - start); |
230 | // fix offset |
231 | offset = start; |
232 | offsets[x] = offset; |
233 | int previous = getPos(); |
234 | int dataOffset = pageSize; |
235 | int page = index.getPageStore().allocatePage(); |
236 | firstOverflowPageId = page; |
237 | this.overflowRowSize = pageSize + rowLength; |
238 | writeData(); |
239 | // free up the space used by the row |
240 | Row r = rows[0]; |
241 | rowRef = new SoftReference<Row>(r); |
242 | rows[0] = null; |
243 | Data all = index.getPageStore().createData(); |
244 | all.checkCapacity(data.length()); |
245 | all.write(data.getBytes(), 0, data.length()); |
246 | data.truncate(index.getPageStore().getPageSize()); |
247 | do { |
248 | int type, size, next; |
249 | if (remaining <= pageSize - PageDataOverflow.START_LAST) { |
250 | type = Page.TYPE_DATA_OVERFLOW | Page.FLAG_LAST; |
251 | size = remaining; |
252 | next = 0; |
253 | } else { |
254 | type = Page.TYPE_DATA_OVERFLOW; |
255 | size = pageSize - PageDataOverflow.START_MORE; |
256 | next = index.getPageStore().allocatePage(); |
257 | } |
258 | PageDataOverflow overflow = PageDataOverflow.create(index.getPageStore(), |
259 | page, type, previous, next, all, dataOffset, size); |
260 | index.getPageStore().update(overflow); |
261 | dataOffset += size; |
262 | remaining -= size; |
263 | previous = page; |
264 | page = next; |
265 | } while (remaining > 0); |
266 | } |
267 | if (rowRef == null) { |
268 | memoryChange(true, row); |
269 | } else { |
270 | memoryChange(true, null); |
271 | } |
272 | return -1; |
273 | } |
274 | |
275 | private void removeRow(int i) { |
276 | index.getPageStore().logUndo(this, data); |
277 | written = false; |
278 | changeCount = index.getPageStore().getChangeCount(); |
279 | if (!optimizeUpdate) { |
280 | readAllRows(); |
281 | } |
282 | Row r = getRowAt(i); |
283 | if (r != null) { |
284 | memoryChange(false, r); |
285 | } |
286 | entryCount--; |
287 | if (entryCount < 0) { |
288 | DbException.throwInternalError(); |
289 | } |
290 | if (firstOverflowPageId != 0) { |
291 | start -= 4; |
292 | freeOverflow(); |
293 | firstOverflowPageId = 0; |
294 | overflowRowSize = 0; |
295 | rowRef = null; |
296 | } |
297 | int keyOffsetPairLen = 2 + Data.getVarLongLen(keys[i]); |
298 | int startNext = i > 0 ? offsets[i - 1] : index.getPageStore().getPageSize(); |
299 | int rowLength = startNext - offsets[i]; |
300 | if (optimizeUpdate) { |
301 | if (writtenData) { |
302 | byte[] d = data.getBytes(); |
303 | int dataStart = offsets[entryCount]; |
304 | System.arraycopy(d, dataStart, d, dataStart + rowLength, |
305 | offsets[i] - dataStart); |
306 | Arrays.fill(d, dataStart, dataStart + rowLength, (byte) 0); |
307 | } |
308 | } else { |
309 | int clearStart = offsets[entryCount]; |
310 | Arrays.fill(data.getBytes(), clearStart, clearStart + rowLength, (byte) 0); |
311 | } |
312 | start -= keyOffsetPairLen; |
313 | offsets = remove(offsets, entryCount + 1, i); |
314 | add(offsets, i, entryCount, rowLength); |
315 | keys = remove(keys, entryCount + 1, i); |
316 | rows = remove(rows, entryCount + 1, i); |
317 | } |
318 | |
319 | @Override |
320 | Cursor find(Session session, long minKey, long maxKey, boolean multiVersion) { |
321 | int x = find(minKey); |
322 | return new PageDataCursor(session, this, x, maxKey, multiVersion); |
323 | } |
324 | |
325 | /** |
326 | * Get the row at the given index. |
327 | * |
328 | * @param at the index |
329 | * @return the row |
330 | */ |
331 | Row getRowAt(int at) { |
332 | Row r = rows[at]; |
333 | if (r == null) { |
334 | if (firstOverflowPageId == 0) { |
335 | r = readRow(data, offsets[at], columnCount); |
336 | } else { |
337 | if (rowRef != null) { |
338 | r = rowRef.get(); |
339 | if (r != null) { |
340 | return r; |
341 | } |
342 | } |
343 | PageStore store = index.getPageStore(); |
344 | Data buff = store.createData(); |
345 | int pageSize = store.getPageSize(); |
346 | int offset = offsets[at]; |
347 | buff.write(data.getBytes(), offset, pageSize - offset); |
348 | int next = firstOverflowPageId; |
349 | do { |
350 | PageDataOverflow page = index.getPageOverflow(next); |
351 | next = page.readInto(buff); |
352 | } while (next != 0); |
353 | overflowRowSize = pageSize + buff.length(); |
354 | r = readRow(buff, 0, columnCount); |
355 | } |
356 | r.setKey(keys[at]); |
357 | if (firstOverflowPageId != 0) { |
358 | rowRef = new SoftReference<Row>(r); |
359 | } else { |
360 | rows[at] = r; |
361 | memoryChange(true, r); |
362 | } |
363 | } |
364 | return r; |
365 | } |
366 | |
367 | int getEntryCount() { |
368 | return entryCount; |
369 | } |
370 | |
371 | @Override |
372 | PageData split(int splitPoint) { |
373 | int newPageId = index.getPageStore().allocatePage(); |
374 | PageDataLeaf p2 = PageDataLeaf.create(index, newPageId, parentPageId); |
375 | for (int i = splitPoint; i < entryCount;) { |
376 | int split = p2.addRowTry(getRowAt(splitPoint)); |
377 | if (split != -1) { |
378 | DbException.throwInternalError("split " + split); |
379 | } |
380 | removeRow(splitPoint); |
381 | } |
382 | return p2; |
383 | } |
384 | |
385 | @Override |
386 | long getLastKey() { |
387 | // TODO re-use keys, but remove this mechanism |
388 | if (entryCount == 0) { |
389 | return 0; |
390 | } |
391 | return getRowAt(entryCount - 1).getKey(); |
392 | } |
393 | |
394 | PageDataLeaf getNextPage() { |
395 | if (parentPageId == PageData.ROOT) { |
396 | return null; |
397 | } |
398 | PageDataNode next = (PageDataNode) index.getPage(parentPageId, -1); |
399 | return next.getNextPage(keys[entryCount - 1]); |
400 | } |
401 | |
402 | @Override |
403 | PageDataLeaf getFirstLeaf() { |
404 | return this; |
405 | } |
406 | |
407 | @Override |
408 | protected void remapChildren(int old) { |
409 | if (firstOverflowPageId == 0) { |
410 | return; |
411 | } |
412 | PageDataOverflow overflow = index.getPageOverflow(firstOverflowPageId); |
413 | overflow.setParentPageId(getPos()); |
414 | index.getPageStore().update(overflow); |
415 | } |
416 | |
417 | @Override |
418 | boolean remove(long key) { |
419 | int i = find(key); |
420 | if (keys == null || keys[i] != key) { |
421 | throw DbException.get(ErrorCode.ROW_NOT_FOUND_WHEN_DELETING_1, |
422 | index.getSQL() + ": " + key + " " + (keys == null ? -1 : keys[i])); |
423 | } |
424 | index.getPageStore().logUndo(this, data); |
425 | if (entryCount == 1) { |
426 | freeRecursive(); |
427 | return true; |
428 | } |
429 | removeRow(i); |
430 | index.getPageStore().update(this); |
431 | return false; |
432 | } |
433 | |
434 | @Override |
435 | void freeRecursive() { |
436 | index.getPageStore().logUndo(this, data); |
437 | index.getPageStore().free(getPos()); |
438 | freeOverflow(); |
439 | } |
440 | |
441 | private void freeOverflow() { |
442 | if (firstOverflowPageId != 0) { |
443 | int next = firstOverflowPageId; |
444 | do { |
445 | PageDataOverflow page = index.getPageOverflow(next); |
446 | page.free(); |
447 | next = page.getNextOverflow(); |
448 | } while (next != 0); |
449 | } |
450 | } |
451 | |
452 | @Override |
453 | Row getRowWithKey(long key) { |
454 | int at = find(key); |
455 | return getRowAt(at); |
456 | } |
457 | |
458 | @Override |
459 | int getRowCount() { |
460 | return entryCount; |
461 | } |
462 | |
463 | @Override |
464 | void setRowCountStored(int rowCount) { |
465 | // ignore |
466 | } |
467 | |
468 | @Override |
469 | long getDiskSpaceUsed() { |
470 | return index.getPageStore().getPageSize(); |
471 | } |
472 | |
473 | @Override |
474 | public void write() { |
475 | writeData(); |
476 | index.getPageStore().writePage(getPos(), data); |
477 | data.truncate(index.getPageStore().getPageSize()); |
478 | } |
479 | |
480 | private void readAllRows() { |
481 | for (int i = 0; i < entryCount; i++) { |
482 | getRowAt(i); |
483 | } |
484 | } |
485 | |
486 | private void writeHead() { |
487 | data.reset(); |
488 | int type; |
489 | if (firstOverflowPageId == 0) { |
490 | type = Page.TYPE_DATA_LEAF | Page.FLAG_LAST; |
491 | } else { |
492 | type = Page.TYPE_DATA_LEAF; |
493 | } |
494 | data.writeByte((byte) type); |
495 | data.writeShortInt(0); |
496 | if (SysProperties.CHECK2) { |
497 | if (data.length() != START_PARENT) { |
498 | DbException.throwInternalError(); |
499 | } |
500 | } |
501 | data.writeInt(parentPageId); |
502 | data.writeVarInt(index.getId()); |
503 | data.writeVarInt(columnCount); |
504 | data.writeShortInt(entryCount); |
505 | } |
506 | |
507 | private void writeData() { |
508 | if (written) { |
509 | return; |
510 | } |
511 | if (!optimizeUpdate) { |
512 | readAllRows(); |
513 | } |
514 | writeHead(); |
515 | if (firstOverflowPageId != 0) { |
516 | data.writeInt(firstOverflowPageId); |
517 | data.checkCapacity(overflowRowSize); |
518 | } |
519 | for (int i = 0; i < entryCount; i++) { |
520 | data.writeVarLong(keys[i]); |
521 | data.writeShortInt(offsets[i]); |
522 | } |
523 | if (!writtenData || !optimizeUpdate) { |
524 | for (int i = 0; i < entryCount; i++) { |
525 | data.setPos(offsets[i]); |
526 | Row r = getRowAt(i); |
527 | for (int j = 0; j < columnCount; j++) { |
528 | data.writeValue(r.getValue(j)); |
529 | } |
530 | } |
531 | writtenData = true; |
532 | } |
533 | written = true; |
534 | } |
535 | |
536 | @Override |
537 | public String toString() { |
538 | return "page[" + getPos() + "] data leaf table:" + |
539 | index.getId() + " " + index.getTable().getName() + |
540 | " entries:" + entryCount + " parent:" + parentPageId + |
541 | (firstOverflowPageId == 0 ? "" : " overflow:" + firstOverflowPageId) + |
542 | " keys:" + Arrays.toString(keys) + " offsets:" + Arrays.toString(offsets); |
543 | } |
544 | |
545 | @Override |
546 | public void moveTo(Session session, int newPos) { |
547 | PageStore store = index.getPageStore(); |
548 | // load the pages into the cache, to ensure old pages |
549 | // are written |
550 | if (parentPageId != ROOT) { |
551 | store.getPage(parentPageId); |
552 | } |
553 | store.logUndo(this, data); |
554 | PageDataLeaf p2 = PageDataLeaf.create(index, newPos, parentPageId); |
555 | readAllRows(); |
556 | p2.keys = keys; |
557 | p2.overflowRowSize = overflowRowSize; |
558 | p2.firstOverflowPageId = firstOverflowPageId; |
559 | p2.rowRef = rowRef; |
560 | p2.rows = rows; |
561 | if (firstOverflowPageId != 0) { |
562 | p2.rows[0] = getRowAt(0); |
563 | } |
564 | p2.entryCount = entryCount; |
565 | p2.offsets = offsets; |
566 | p2.start = start; |
567 | p2.remapChildren(getPos()); |
568 | p2.writeData(); |
569 | p2.data.truncate(index.getPageStore().getPageSize()); |
570 | store.update(p2); |
571 | if (parentPageId == ROOT) { |
572 | index.setRootPageId(session, newPos); |
573 | } else { |
574 | PageDataNode p = (PageDataNode) store.getPage(parentPageId); |
575 | p.moveChild(getPos(), newPos); |
576 | } |
577 | store.free(getPos()); |
578 | } |
579 | |
580 | /** |
581 | * Set the overflow page id. |
582 | * |
583 | * @param old the old overflow page id |
584 | * @param overflow the new overflow page id |
585 | */ |
586 | void setOverflow(int old, int overflow) { |
587 | if (SysProperties.CHECK && old != firstOverflowPageId) { |
588 | DbException.throwInternalError("move " + this + " " + firstOverflowPageId); |
589 | } |
590 | index.getPageStore().logUndo(this, data); |
591 | firstOverflowPageId = overflow; |
592 | if (written) { |
593 | changeCount = index.getPageStore().getChangeCount(); |
594 | writeHead(); |
595 | data.writeInt(firstOverflowPageId); |
596 | } |
597 | index.getPageStore().update(this); |
598 | } |
599 | |
600 | private void memoryChange(boolean add, Row r) { |
601 | int diff = r == null ? 0 : 4 + 8 + Constants.MEMORY_POINTER + r.getMemory(); |
602 | memoryData += add ? diff : -diff; |
603 | index.memoryChange((Constants.MEMORY_PAGE_DATA + |
604 | memoryData + index.getPageStore().getPageSize()) >> 2); |
605 | } |
606 | |
607 | @Override |
608 | public boolean isStream() { |
609 | return firstOverflowPageId > 0; |
610 | } |
611 | |
612 | /** |
613 | * Read a row from the data page at the given position. |
614 | * |
615 | * @param data the data page |
616 | * @param pos the position to read from |
617 | * @param columnCount the number of columns |
618 | * @return the row |
619 | */ |
620 | private static Row readRow(Data data, int pos, int columnCount) { |
621 | Value[] values = new Value[columnCount]; |
622 | synchronized (data) { |
623 | data.setPos(pos); |
624 | for (int i = 0; i < columnCount; i++) { |
625 | values[i] = data.readValue(); |
626 | } |
627 | } |
628 | return RegularTable.createRow(values); |
629 | } |
630 | |
631 | } |