001: /*
002:
003: Derby - Class org.apache.derby.impl.store.access.btree.LeafControlRow
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.impl.store.access.btree;
023:
024: import org.apache.derby.iapi.reference.SQLState;
025: import org.apache.derby.iapi.services.sanity.SanityManager;
026: import org.apache.derby.iapi.services.io.FormatIdUtil;
027: import org.apache.derby.iapi.services.io.StoredFormatIds;
028: import org.apache.derby.iapi.services.io.TypedFormat;
029: import org.apache.derby.iapi.error.StandardException;
030:
031: import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;
032:
033: import org.apache.derby.iapi.store.access.AccessFactoryGlobals;
034: import org.apache.derby.iapi.store.access.ConglomerateController;
035: import org.apache.derby.iapi.store.access.Qualifier;
036: import org.apache.derby.iapi.store.access.RowUtil;
037: import org.apache.derby.iapi.store.access.ScanController;
038:
039: import org.apache.derby.iapi.store.raw.ContainerHandle;
040: import org.apache.derby.iapi.store.raw.FetchDescriptor;
041: import org.apache.derby.iapi.store.raw.Page;
042: import org.apache.derby.iapi.store.raw.RecordHandle;
043: import org.apache.derby.iapi.store.raw.Transaction;
044:
045: import org.apache.derby.iapi.types.DataValueDescriptor;
046:
047: import java.io.PrintStream;
048: import org.apache.derby.iapi.services.io.FormatableBitSet;
049:
050: /**
051: * @format_id ACCESS_BTREE_LEAFCONTROLROW_V1_ID
052: *
053: * @purpose Btree pages all have a control row at the front of every page. To
054: * determine the type of row, read the first column which is a format
055: * id and it tells what kind of control row it is.
056: *
057: * @upgrade This format was made obsolete in the kimono release.
058: *
059: * @disk_layout
060: * column 1 - control row type : StorableFormatId
061: * column 2 - left sibling page number : SQLLongint
062: * column 3 - right sibling page number: SQLLongint
063: * column 4 - parent page number : SQLLongint
064: * column 5 - level number (0 is leaf) : SQLLongint
065: * column 6 - isRoot : SQLLongint
066: * column 7 - Conglomerate object : null unless it is root else
067: * a Conglomerate object, matching
068: * that of current table.
069: * Currently this field
070: * is only used by logical undo and
071: * the type of object is inferred by
072: * the logical undo code.
073: **/
074:
075: public class LeafControlRow extends ControlRow {
076: /*
077: ** Constructors of BranchControlRow
078: */
079:
080: /**
081: * No arg constructor.
082: * <p>
083: * Public no arg constructor is for the monitor to call for format
084: * id implemenation, it should not be called for any other reason.
085: **/
086: public LeafControlRow() {
087: }
088:
089: /**
090: * Constructs a leaf-page control row, for a newly allocated leaf page.
091: *
092: * @param btree The open btree to allocate this page from.
093: * @param page The newly allocated page where the control row will
094: * be inserted.
095: * @param parent The parent of the leaf page. Set to null for root.
096: * RESOLVE (mikem) - set to null otherwise?
097: * @param isRoot Is this page the root of the tree?
098: *
099: * @exception StandardException Standard exception policy.
100: */
101: LeafControlRow(OpenBTree btree, Page page, ControlRow parent,
102: boolean isRoot) throws StandardException {
103: // All leaf pages are at level 0.
104: super (btree, page, 0, parent, isRoot);
105: }
106:
107: /* Private/Protected methods of This class: */
108:
109: /**
110: * Allocate a new leaf page to the conglomerate.
111: *
112: * @param btree The open conglomerate from which to get the leaf from
113: * @param parent The parent page of the newly allocated page, null if
114: * allocating root page.
115: *
116: * @exception StandardException Standard exception policy.
117: */
118: private static LeafControlRow Allocate(OpenBTree btree,
119: ControlRow parent) throws StandardException {
120: Page page = btree.container.addPage();
121:
122: // Create a control row for the new page.
123: LeafControlRow control_row = new LeafControlRow(btree, page,
124: parent, false);
125:
126: // Insert the control row on the page, in the first slot on the page.
127: // This operation is only done as part of a new tree or split, which
128: // which both will be undone physically so no logical undo record is
129: // needed.
130: byte insertFlag = Page.INSERT_INITIAL;
131: insertFlag |= Page.INSERT_DEFAULT;
132: RecordHandle rh = page.insertAtSlot(Page.FIRST_SLOT_NUMBER,
133: control_row.getRow(), (FormatableBitSet) null,
134: (LogicalUndo) null, insertFlag,
135: AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD);
136:
137: if (SanityManager.DEBUG) {
138: RecordHandle rh2 = null;
139:
140: rh2 = page.fetchFromSlot((RecordHandle) null,
141: page.FIRST_SLOT_NUMBER, new DataValueDescriptor[0],
142: (FetchDescriptor) null, true);
143:
144: SanityManager.ASSERT(rh.getId() == rh2.getId()
145: && rh.getPageNumber() == rh2.getPageNumber());
146: }
147:
148: // Page is returned latched.
149: return (control_row);
150: }
151:
152: /**
153: * Return the number of non-deleted rows from slot 1 through "startslot"
154: * <p>
155: * Return the number of non-deleted rows that exist on the page starting
156: * at slot one through "startslot".
157: * <p>
158: * RESOLVE (mikem) - is the expense of this routine worth it, it is only
159: * used for costing. Could an estimate from the nonDeletedRecordCount()
160: * be used instead?
161: *
162: * @return The requested non_deleted_row_count.
163: *
164: * @param startslot Count non deleted row up to and including this slot.
165: *
166: * @exception StandardException Standard exception policy.
167: **/
168: private float get_left_nondeleted_rowcnt(int startslot)
169: throws StandardException {
170: int non_deleted_row_count = 0;
171:
172: for (int slot = 1; slot <= startslot; slot++) {
173: if (!this .page.isDeletedAtSlot(slot)) {
174: non_deleted_row_count++;
175: }
176: }
177: return (non_deleted_row_count);
178: }
179:
180: /* Public Methods of LeafControlRow class: */
181:
182: /**
183: * Perform page specific initialization.
184: * <p>
185: **/
186: protected final void ControlRowInit() {
187: }
188:
189: /**
190: * Initialize conglomerate with one page, to be a 1 page btree.
191: *
192: * Given a conglomerate which already has one page allocated to it,
193: * initialize the page to be a leaf-root page with no entries. Allocate
194: * the control row and store it on the page.
195: *
196: * @param open_btree The open btree to initialize (container is open).
197: *
198: * @exception StandardException Standard exception policy.
199: */
200: public static void initEmptyBtree(OpenBTree open_btree)
201: throws StandardException {
202: Page page = open_btree.container
203: .getPage(ContainerHandle.FIRST_PAGE_NUMBER);
204:
205: // create a leaf control row for root page of a single page index //
206: LeafControlRow control_row = new LeafControlRow(open_btree,
207: page, null, true);
208:
209: byte insertFlag = Page.INSERT_INITIAL;
210: insertFlag |= Page.INSERT_DEFAULT;
211: RecordHandle rh = page.insertAtSlot(Page.FIRST_SLOT_NUMBER,
212: control_row.getRow(), (FormatableBitSet) null,
213: (LogicalUndo) null, insertFlag,
214: AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD);
215:
216: if (SanityManager.DEBUG) {
217: RecordHandle rh2 = null;
218:
219: rh2 = page.fetchFromSlot((RecordHandle) null,
220: Page.FIRST_SLOT_NUMBER, new DataValueDescriptor[0],
221: (FetchDescriptor) null, true);
222:
223: SanityManager.ASSERT(rh.getId() == rh2.getId()
224: && rh.getPageNumber() == rh2.getPageNumber());
225: }
226:
227: if (SanityManager.DEBUG) {
228: if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck")) {
229: control_row.checkConsistency(open_btree,
230: (ControlRow) null, true);
231: }
232: }
233:
234: page.unlatch();
235:
236: return;
237: }
238:
239: /*
240: ** Non - Debug/consistency check Methods of ControlRow:
241: */
242:
243: /**
244: * Get the number of columns in the control row.
245: * <p>
246: * Control rows all share the first columns as defined by this class and
247: * then add columns to the end of the control row. For instance a branch
248: * control row add a child page pointer field.
249: * <p>
250: *
251: * @return The total number of columns in the control row.
252: **/
253: protected final int getNumberOfControlRowColumns() {
254: return (this .CR_NCOLUMNS);
255: }
256:
257: /**
258: * Is the current page the leftmost leaf of tree?
259: * <p>
260: *
261: * @return true if the current page is the leftmost leaf of the tree,
262: * else return false.
263: *
264: * @exception StandardException Standard exception policy.
265: **/
266: public boolean isLeftmostLeaf() throws StandardException {
267: return (getleftSiblingPageNumber() == ContainerHandle.INVALID_PAGE_NUMBER);
268: }
269:
270: /**
271: * Is the current page the rightmost leaf of tree?
272: * <p>
273: *
274: * @return true if the current page is the rightmost leaf of the tree,
275: * else return false.
276: *
277: * @exception StandardException Standard exception policy.
278: **/
279: public boolean isRightmostLeaf() throws StandardException {
280: return (getrightSiblingPageNumber() == ContainerHandle.INVALID_PAGE_NUMBER);
281: }
282:
283: /**
284: ** Perform a search of this leaf page, ultimately returning the latched
285: ** leaf page and row slot after which the given key belongs.
286: ** The slot is returned in the result structure. If the key
287: ** exists on the page, the result.exact will be true. Otherwise,
288: ** result.exact will be false, and the row slot returned will be
289: ** the one immediately preceding the position at which the key
290: ** belongs.
291: *
292: * @exception StandardException Standard exception policy.
293: **/
294: public ControlRow search(SearchParameters sp)
295: throws StandardException {
296: searchForEntry(sp);
297:
298: if (sp.searchForOptimizer) {
299: // Update left_fraction to be used to estimate the number of
300: // rows left of the current search location.
301:
302: // after the code below startslot will be the slot that is one
303: // before the first slot to be returned by the scan positioning
304: // for this key, including GT/GE positioning. This is exactly
305: // what the LeafControlRow.positionAtStartForForwardScan() does,
306: // to position for the start of a scan.
307:
308: int startslot = sp.resultSlot;
309:
310: if (sp.resultExact) {
311: // we found exactly the row we are looking for.
312:
313: if (SanityManager.DEBUG)
314: SanityManager.ASSERT(sp.resultSlot > 0);
315:
316: // RESOLVE (mikem) - add in a search operator argument so that
317: // below can be if (op == ScanController.GE)
318:
319: if (sp.partial_key_match_op == SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH) {
320: // This means the scan was positioned for GE rather than GT
321: startslot--;
322: }
323: }
324:
325: // non_deleted_left_row is the number of actual rows left of the
326: // first row to be returned by a scan positioned as requested.
327: // The 0th slot is a control row which is not counted.
328: float non_deleted_left_rows = get_left_nondeleted_rowcnt(startslot);
329:
330: int non_deleted_row_count = this .page
331: .nonDeletedRecordCount();
332:
333: // System.out.println(
334: // "\n\t non_deleted_row_count = " + non_deleted_row_count +
335: // "\n\t non_deleted_left_rows = " + non_deleted_left_rows +
336: // "\n\t startslot = " + startslot);
337:
338: if (this .getIsRoot()) {
339: sp.current_fraction = 1;
340: sp.left_fraction = 0;
341: }
342:
343: // calculate the fraction of rows in the table which are left of
344: // the current slot in the search. After the search is completed
345: // (sp.left_fraction * number of rows), is the estimated number
346: // of rows to the left of the current row.
347:
348: if (non_deleted_row_count > 1)
349: sp.left_fraction += (sp.current_fraction)
350: * (non_deleted_left_rows / (non_deleted_row_count - 1));
351:
352: // no-one really uses current fraction after leaf is through with
353: // it. Set it to help diagnose algorithm.
354: if (non_deleted_row_count > 1)
355: sp.current_fraction = (sp.current_fraction)
356: * (((float) 1) / (non_deleted_row_count - 1));
357: }
358:
359: return (this );
360: }
361:
362: /**
363: * Search and return the left most leaf page.
364: * <p>
365: * Perform a recursive search, ultimately returning the
366: * leftmost leaf page which is the first leaf page in the
367: * leaf sibling chain. (This method might better be called
368: * getFirstLeafPage()).
369: *
370: * @return The leftmost leaf page.
371: *
372: * @param btree The open btree to associate latches/locks with.
373: *
374: * @exception StandardException Standard exception policy.
375: **/
376: protected ControlRow searchLeft(OpenBTree btree)
377: throws StandardException {
378: return (this );
379: }
380:
381: /**
382: * Search and return the right most leaf page.
383: * <p>
384: * Perform a recursive search, ultimately returning the
385: * rightmost leaf page which is the last leaf page in the
386: * leaf sibling chain. (This method might better be called
387: * getLastLeafPage()).
388: *
389: * @return The rightmost leaf page.
390: *
391: * @param btree The open btree to associate latches/locks with.
392: *
393: * @exception StandardException Standard exception policy.
394: **/
395: protected ControlRow searchRight(OpenBTree btree)
396: throws StandardException {
397: return (this );
398: }
399:
400: /**
401: ** Perform a recursive shrink operation for the key.
402: ** If this method returns true, the caller should
403: ** remove the corresponding entry for the page.
404: ** This routine is not guaranteed to successfully
405: ** shrink anything. The page lead to by the key might
406: ** turn out not to be empty by the time shrink gets
407: ** there, and shrinks will give up if there is a deadlock.
408: ** <P>
409: ** The receiver page must be latched on entry and is
410: ** returned unlatched.
411: *
412: * @exception StandardException Standard exception policy.
413: **/
414: protected boolean shrinkFor(OpenBTree btree,
415: DataValueDescriptor[] key) throws StandardException {
416: boolean shrink_me = false;
417:
418: try {
419: // If this page is empty (ie. only has a control row), and it's not
420: // the root page, unlink it. An empty btree consists of
421: // simply an empty leaf-root page.
422:
423: // RESOLVE (mikem) - may want this routine to try to purge
424: // committed delete rows here?
425:
426: if ((this .page.recordCount() == 1) && !getIsRoot()) {
427: // See if we can unlink this page (might not be able to because
428: // unlinking can cause deadlocks). A successful unlink
429: // unlatches the page.
430: shrink_me = unlink(btree);
431: }
432: } finally {
433: if (!shrink_me)
434: this .release();
435: }
436:
437: return (shrink_me);
438: }
439:
440: /**
441: * Perform a top down split pass making room for the the key in "row".
442: * <p>
443: * Perform a split such that a subsequent call to insert
444: * given the argument index row will likely find room for it. Since
445: * latches are released the client must code for the case where another
446: * user has grabbed the space made available by the split pass and be
447: * ready to do another split.
448: * <p>
449: * On entry, the parent is either null or latched, and the
450: * current page is latched. On exit, all pages will have been
451: * unlatched. If the parent is null, then this page is a root
452: * leaf page.
453: *
454: * @return page number of the newly allocated leaf page created by split.
455: *
456: * @param open_btree The open btree to associate latches with.
457: * @param template A scratch area to use while searching for split pass.
458: * @param parent_page The parent page of the current page in the split pass.
459: * starts at null for root.
460: * @param splitrow The key to make room for during the split pass.
461: * @param flag A flag used to direct where point of split should be
462: * chosen.
463: *
464: * @exception StandardException Standard exception policy.
465: **/
466: protected long splitFor(OpenBTree open_btree,
467: DataValueDescriptor[] template,
468: BranchControlRow parent_page,
469: DataValueDescriptor[] splitrow, int flag)
470: throws StandardException {
471: long current_leaf_pageno = this .page.getPageNumber();
472:
473: if (SanityManager.DEBUG) {
474: if (parent_page == null && (!this .getIsRoot()))
475: SanityManager.THROWASSERT(this
476: + " splitFor null parent and non-root");
477: }
478:
479: // See if this page has space.
480: if ((this .page.recordCount() - 1 < open_btree.getConglomerate().maxRowsPerPage)
481: && (this .page.spaceForInsert(splitrow,
482: (FormatableBitSet) null,
483: AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD))) {
484: // The splitFor() operation is complete, commit the work done
485: // before releasing the latches.
486: open_btree.getXactMgr().commit();
487:
488: if (parent_page != null)
489: parent_page.release();
490:
491: this .release();
492:
493: return (current_leaf_pageno);
494: }
495:
496: // RESOLVE (mikem) - for rows bigger than pages this assert may
497: // trigger until we have long rows.
498: if (SanityManager.DEBUG)
499: SanityManager.ASSERT(this .page.recordCount() > 1);
500:
501: // Track.LeafSplit++;
502:
503: if (this .getIsRoot()) {
504: // Track.LeafSplitRoot++;
505:
506: growRoot(open_btree, template, this );
507:
508: // At this point, this page has been unlatched. So code below this
509: // point must not access this object's fields.
510:
511: ControlRow new_root = ControlRow.Get(open_btree,
512: BTree.ROOTPAGEID);
513:
514: return (new_root.splitFor(open_btree, template, null,
515: splitrow, flag));
516: }
517:
518: // At this point we know that this page has to be split and
519: // that it isn't a root page.
520:
521: int splitpoint = (this .page.recordCount() - 1) / 2 + 1;
522:
523: if ((flag & ControlRow.SPLIT_FLAG_FIRST_ON_PAGE) != 0) {
524: // move all the row to the new page
525: splitpoint = 1;
526: } else if ((flag & ControlRow.SPLIT_FLAG_LAST_ON_PAGE) != 0) {
527: // This is not optimal as we would rather move no rows to the
528: // next page, but what should we use as a discriminator?
529: splitpoint = this .page.recordCount() - 1;
530: }
531:
532: if (SanityManager.DEBUG) {
533: if (splitpoint <= 0)
534: SanityManager.THROWASSERT(this
535: + " yikes! splitpoint of 0!");
536: }
537:
538: // Save away current split point leaf row, and build a branch row
539: // based on it.
540: DataValueDescriptor[] split_leaf_row = open_btree
541: .getConglomerate().createTemplate();
542:
543: this .page.fetchFromSlot((RecordHandle) null, splitpoint,
544: split_leaf_row, (FetchDescriptor) null, true);
545:
546: // Create the branch row to insert onto the parent page. For now
547: // use a fake page number because we don't know the real page
548: // number until the allocate is done, but want to delay the
549: // allocate until we know the insert will succeed.
550: BranchRow branchrow = BranchRow.createBranchRowFromOldLeafRow(
551: split_leaf_row, BranchRow.DUMMY_PAGE_NUMBER);
552:
553: // At this point we have guaranteed there is space in the parent
554: // page for splitrow, but it could be the case that the new
555: // "branchrow" does not fit on the parent page.
556: if (!parent_page.page.spaceForInsert(branchrow.getRow(),
557: (FormatableBitSet) null,
558: AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD)) {
559: // There is no room on the parent page to complete a split at
560: // the current level, so restart the split at top with the
561: // branchrow that did not fit. On return from this routine
562: // there is no way to know the state of the tree, so the
563: // current split pass recursion must end.
564: return (((BranchControlRow) parent_page).restartSplitFor(
565: open_btree, template, parent_page, this , branchrow
566: .getRow(), splitrow, flag));
567:
568: }
569: // Before moving the rows on the page, while having the latch on the
570: // page, notify btree scans that the rows on this page may be moving
571: // onto another page.
572: //
573: // RESOLVE (mikem) - need to pass conlgomid.
574: // RESOLVE (mikem) - some optimization later, we only need to notify
575: // the scans which are positioned on moving rows.
576: if (SanityManager.DEBUG)
577: SanityManager
578: .ASSERT(open_btree.init_open_user_scans != null);
579:
580: open_btree.init_open_user_scans.saveScanPositions(open_btree
581: .getConglomerate(), this .page);
582:
583: // Get exclusive RECORD_ID_PROTECTION_HANDLE lock to make sure that
584: // we wait for scans in other transactions to move off of this page
585: // before we split.
586:
587: if (!open_btree.getLockingPolicy()
588: .lockScan(this , parent_page, true /* for update */,
589: ConglomerateController.LOCK_UPD)) {
590: // we had to give up latches on this and parent_page to get the
591: // split lock. Redo the whole split pass as we have lost our
592: // latches. Just returning is ok, as the caller can not assume
593: // that split has succeeded in making space. Note that at this
594: // point in the split no write work has been done in the current
595: // internal transaction, so giving up here is fairly cheap.
596:
597: // RESOLVE RLL PERFORMANCE - we could keep a stack of visited
598: // pages so as to not have to redo the complete search.
599: return (current_leaf_pageno);
600: }
601:
602: // Create a new leaf page under the parent.
603: LeafControlRow newleaf = LeafControlRow.Allocate(open_btree,
604: parent_page);
605:
606: // Now that we know the page number of the new child page update
607: // the branch row to be inserted with the correct value.
608: branchrow.setPageNumber(newleaf.page.getPageNumber());
609:
610: // Test fail after allocation
611: if (SanityManager.DEBUG) {
612: if (SanityManager.DEBUG_ON("leaf_split_abort1")) {
613: throw StandardException
614: .newException(SQLState.BTREE_ABORT_THROUGH_TRACE);
615: }
616: }
617:
618: // Link it to the right of the current page.
619: newleaf.linkRight(open_btree, this );
620:
621: // Copy the index rows (from the splitpoint to the end of the page)
622: // from the old page to the new leaf, do not
623: // copy the control row. This routine will purge all the copied rows
624: // and maintain the deleted status of the moved rows.
625: int num_rows_to_move = this .page.recordCount() - splitpoint;
626:
627: if (SanityManager.DEBUG)
628: SanityManager.ASSERT(num_rows_to_move >= 0);
629:
630: if (num_rows_to_move != 0) {
631: this .page.copyAndPurge(newleaf.page, splitpoint,
632: num_rows_to_move, 1);
633: }
634:
635: // Test fail after new page has been updated.
636: if (SanityManager.DEBUG) {
637: if (SanityManager.DEBUG_ON("leaf_split_abort2")) {
638: throw StandardException
639: .newException(SQLState.BTREE_ABORT_THROUGH_TRACE);
640: }
641: }
642:
643: // Test fail after new page has been updated.
644: if (SanityManager.DEBUG) {
645: if (SanityManager.DEBUG_ON("leaf_split_abort3")) {
646: throw StandardException
647: .newException(SQLState.BTREE_ABORT_THROUGH_TRACE);
648: }
649: }
650:
651: // Find spot to insert branch row, and insert it.
652:
653: BranchRow branch_template = BranchRow
654: .createEmptyTemplate(open_btree.getConglomerate());
655: SearchParameters sp = new SearchParameters(branchrow.getRow(),
656: SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH,
657: branch_template.getRow(), open_btree, false);
658:
659: parent_page.searchForEntry(sp);
660:
661: // There must be space on the parent to insert the row!
662: if (SanityManager.DEBUG) {
663: SanityManager.ASSERT(parent_page.page.spaceForInsert(
664: branchrow.getRow(), (FormatableBitSet) null,
665: AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD));
666: }
667:
668: byte insertFlag = Page.INSERT_INITIAL;
669: insertFlag |= Page.INSERT_DEFAULT;
670: insertFlag |= Page.INSERT_UNDO_WITH_PURGE;
671: if (parent_page.page.insertAtSlot(sp.resultSlot + 1, branchrow
672: .getRow(), (FormatableBitSet) null, (LogicalUndo) null,
673: insertFlag,
674: AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD) == null) {
675:
676: throw StandardException
677: .newException(SQLState.BTREE_NO_SPACE_FOR_KEY);
678: }
679:
680: // branchrow is only valid while split_leaf_row remains unchanged.
681: branchrow = null;
682:
683: // RESOLVE (mikem) - this case breaks the btree currently - as the
684: // abort of the insert leaves a logical delete in the tree.
685: //
686: // Test fail after parent page has been updated.
687: if (SanityManager.DEBUG) {
688: if (SanityManager.DEBUG_ON("leaf_split_abort4")) {
689: throw StandardException
690: .newException(SQLState.BTREE_ABORT_THROUGH_TRACE);
691: }
692: }
693:
694: if (SanityManager.DEBUG) {
695: if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck")) {
696: this .checkConsistency(open_btree, parent_page, false);
697: newleaf
698: .checkConsistency(open_btree, parent_page,
699: false);
700: parent_page.checkConsistency(open_btree, null, false);
701: }
702: }
703:
704: // At this point a unit of work in the split down the tree has
705: // been performed in an internal transaction. This work must
706: // be committed before any latches are released.
707: open_btree.getXactMgr().commit();
708:
709: parent_page.release();
710: this .release(); // XXX (nat) Not good form to unlatch self.
711:
712: long new_leaf_pageno = newleaf.page.getPageNumber();
713: newleaf.release();
714:
715: // Because we are at the leaf level and have completed the split
716: // there is no more work, no latches should be held, and control
717: // is returned up the recursive stack, to the insert causing the
718: // split. Because latches are released, the inserter must recheck
719: // that there is now space available as some other thread of control
720: // could get in before he latches the page again.
721: return (new_leaf_pageno);
722: }
723:
724: /**
725: ** Grow a new root page from a leaf page. Slightly
726: ** tricky because we want to retain page 0 as the root.
727: ** <P>
728: ** On entry, the current leaf root page is expected
729: ** to be latched. On exit, all latches will have been
730: ** released.
731: ** <P>
732: ** The caller cannot not assume success. If we have to release latches
733: ** this routine just returns and assumes the caller will retry the
734: ** grow root if necessary.
735: **/
736: private static void growRoot(OpenBTree open_btree,
737: DataValueDescriptor[] template, LeafControlRow leafroot)
738: throws StandardException {
739: BranchControlRow branchroot = null;
740: LeafControlRow newleaf = null;
741:
742: // Before moving the rows on the page, while having the latch on the
743: // page, notify btree scans that the rows on this page may be moving
744: // onto another page.
745: //
746: open_btree.init_open_user_scans.saveScanPositions(open_btree
747: .getConglomerate(), leafroot.page);
748:
749: // Get exclusive RECORD_ID_PROTECTION_HANDLE lock to make sure that
750: // we wait for scans in other transactions to move off of this page
751: // before we grow root. If we don't wait, scanners in other
752: // transactions may be positioned on the leaf page which we are
753: // about to make into a branch page.
754:
755: if (!open_btree.getLockingPolicy().lockScan(leafroot,
756: (ControlRow) null, true /* for update */,
757: ConglomerateController.LOCK_UPD)) {
758: // We had to give up latches on leafroot to get the
759: // split lock. Redo the whole split pass as we have lost our
760: // latches - which may mean that the root has grown when we gave
761: // up the latch. Just returning is ok, as the caller can not assume
762: // that grow root has succeeded in making space. Note that at this
763: // point in the split no write work has been done in the current
764: // internal transaction, so giving up here is fairly cheap.
765:
766: return;
767: }
768:
769: // Allocate a new leaf page under the existing leaf root.
770:
771: newleaf = LeafControlRow.Allocate(open_btree, leafroot);
772:
773: // Test fail after allocation
774: if (SanityManager.DEBUG) {
775: if (SanityManager.DEBUG_ON("leaf_split_growRoot1")) {
776: throw StandardException
777: .newException(SQLState.BTREE_ABORT_THROUGH_TRACE);
778: }
779: }
780:
781: // Copy all the index rows from the root to the new leaf, do not
782: // copy the control row. This routine will purge all the copied
783: // rows and maintain the deleted status of the moved rows.
784:
785: if (SanityManager.DEBUG)
786: SanityManager.ASSERT((leafroot.page.recordCount() - 1) > 0);
787: leafroot.page.copyAndPurge(newleaf.page, 1, leafroot.page
788: .recordCount() - 1, 1);
789:
790: // Test fail after row copy
791: if (SanityManager.DEBUG) {
792: if (SanityManager.DEBUG_ON("leaf_split_growRoot2")) {
793: throw StandardException
794: .newException(SQLState.BTREE_ABORT_THROUGH_TRACE);
795: }
796: }
797:
798: // Test fail after purge
799: if (SanityManager.DEBUG) {
800: if (SanityManager.DEBUG_ON("leaf_split_growRoot3")) {
801: // Make sure tree is very trashed and logical recovery will
802: // not work.
803: leafroot.setLevel(42);
804: leafroot.setParent(42);
805: throw StandardException
806: .newException(SQLState.BTREE_ABORT_THROUGH_TRACE);
807: }
808: }
809:
810: // Put a branch control row on the root page, making the new leaf
811: // the left child. All leaf splits result in level-1 branch pages.
812: // This will be a branch-root page.
813:
814: // Construction of the BranchControlRow will set it as the aux
815: // object for the page, this in turn invalidates the previous aux
816: // object which is leafroot. Thus leafroot must not be used once
817: // the constructor returns.
818:
819: branchroot = new BranchControlRow(open_btree, leafroot.page, 1,
820: null, true, newleaf.page.getPageNumber());
821: leafroot = null;
822:
823: // Replace the old leaf root control row with the new branch root
824: // control row.
825: branchroot.page.updateAtSlot(0, branchroot.getRow(),
826: (FormatableBitSet) null);
827:
828: // Test fail after purge
829: if (SanityManager.DEBUG) {
830: if (SanityManager.DEBUG_ON("leaf_split_growRoot4")) {
831: throw StandardException
832: .newException(SQLState.BTREE_ABORT_THROUGH_TRACE);
833: }
834: }
835:
836: if (SanityManager.DEBUG) {
837: if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck")) {
838: newleaf.checkConsistency(open_btree, branchroot, false);
839: branchroot.checkConsistency(open_btree, null, false);
840: }
841: }
842:
843: // At this point a unit of work in the split down the tree has
844: // been performed in an internal transaction. This work must
845: // be committed before any latches are released.
846: open_btree.getXactMgr().commit();
847:
848: // Test fail after commit of split
849: if (SanityManager.DEBUG) {
850: if (SanityManager.DEBUG_ON("leaf_split_growRoot5")) {
851: throw StandardException
852: .newException(SQLState.BTREE_ABORT_THROUGH_TRACE);
853: }
854: }
855:
856: // The variable 'branchroot' refers to a page that was latched by
857: // leafroot. After a growRoot() from a leaf there will be no pages
858: // latched. It is up to the callers to reget the root page latched
859: // and continue their work.
860: //
861: if (branchroot != null)
862: branchroot.release();
863: if (leafroot != null)
864: leafroot.release();
865: if (newleaf != null)
866: newleaf.release();
867: }
868:
869: /**
870: * Return the left child pointer for the page.
871: * <p>
872: * Leaf pages don't have children, so they override this and return null.
873: *
874: * @return The page which is the leftmost child of this page.
875: *
876: * @param btree The open btree to associate latches/locks with.
877: *
878: * @exception StandardException Standard exception policy.
879: **/
880: protected ControlRow getLeftChild(OpenBTree btree)
881: throws StandardException {
882: return (null);
883: }
884:
885: /**
886: * Return the right child pointer for the page.
887: * <p>
888: * Leaf pages don't have children, so they override this and return null.
889: *
890: * @return The page which is the rightmost child of this page.
891: *
892: * @param btree The open btree to associate latches/locks with.
893: *
894: * @exception StandardException Standard exception policy.
895: **/
896: protected ControlRow getRightChild(OpenBTree btree)
897: throws StandardException {
898: return (null);
899: }
900:
901: /*
902: ** Debug/consistency check Methods of ControlRow:
903: */
904:
905: /**
906: ** Perform consistency checks on a leaf page.
907: **
908: ** Check consistency of the page and its children,
909: ** returning the number of pages seen, and throwing
910: ** errors if inconsistencies are found.
911: ** The checks specific to a leaf page are:
912: ** <menu>
913: ** <li> Page is at level 0.
914: ** <li> Version is a valid leaf page version.
915: ** <li> Control row has right number of columns for leaf.
916: ** </menu>
917: ** This method also performs the consistency checks that
918: ** are common to both leaf and branch pages.
919: ** @see ControlRow#checkGeneric
920: **
921: ** @exception StandardException Standard exception policy.
922: **/
923: public int checkConsistency(OpenBTree btree, ControlRow parent,
924: boolean check_other_pages) throws StandardException {
925: // Do the consistency checks that are common to all
926: // types of pages.
927: checkGeneric(btree, parent, check_other_pages);
928:
929: // Leaf specific, control row checks
930: if (SanityManager.DEBUG) {
931: SanityManager.ASSERT(this .getLevel() == 0,
932: "leaf not at level 0");
933:
934: // RESOLVE (mikem) - how to sanity check correct version?
935: /*
936: if (this.getVersion() != CURRENT_LEAF_VERSION)
937: SanityManager.THROWASSERT(
938: "Expected leaf version:(" +
939: CURRENT_LEAF_VERSION + ") but got (" +
940: this.getVersion());
941: */
942: SanityManager
943: .ASSERT(this .page.fetchNumFieldsAtSlot(CR_SLOT) == ControlRow.CR_NCOLUMNS);
944:
945: // The remaining checks are specific to leaf pages.
946:
947: // Check that every row has at least as many columns
948: // as the number of key fields in the b-tree.
949: int numslots = this .page.recordCount();
950: for (int slot = 1; slot < numslots; slot++) {
951: if (this .page.fetchNumFieldsAtSlot(slot) < btree
952: .getConglomerate().nKeyFields)
953: SanityManager.THROWASSERT("row[" + slot + "]"
954: + " has "
955: + this .page.fetchNumFieldsAtSlot(slot)
956: + " columns, should have at least"
957: + btree.getConglomerate().nKeyFields);
958:
959: // RESOLVE - the generic btree code should know nothing about
960: // the secondaryindex row location column, but put this here for
961: // now because I can't figure how to get a call out to the
962: // secondary index code at the page level consistency checking
963: // level.
964: }
965:
966: }
967:
968: // We checked one page (this one).
969: return 1;
970: }
971:
972: /**
973: ** Recursively print the tree starting at current node in tree.
974: ** This is a leaf so return.
975:
976: @exception StandardException Standard exception policy.
977: **/
978: public void printTree(OpenBTree btree) throws StandardException {
979: if (SanityManager.DEBUG) {
980: SanityManager.DEBUG_PRINT("p_tree", this .debugPage(btree));
981:
982: return;
983: }
984: }
985:
986: /*
987: * Methods of TypedFormat:
988: */
989:
990: /**
991: Return my format identifier.
992:
993: @see org.apache.derby.iapi.services.io.TypedFormat#getTypeFormatId
994: */
995: public int getTypeFormatId() {
996: return StoredFormatIds.ACCESS_BTREE_LEAFCONTROLROW_V1_ID;
997: }
998: }
|