0001: /*
0002:
0003: Derby - Class org.apache.derby.impl.store.access.btree.BTreeController
0004:
0005: Licensed to the Apache Software Foundation (ASF) under one or more
0006: contributor license agreements. See the NOTICE file distributed with
0007: this work for additional information regarding copyright ownership.
0008: The ASF licenses this file to you under the Apache License, Version 2.0
0009: (the "License"); you may not use this file except in compliance with
0010: the License. You may obtain a copy of the License at
0011:
0012: http://www.apache.org/licenses/LICENSE-2.0
0013:
0014: Unless required by applicable law or agreed to in writing, software
0015: distributed under the License is distributed on an "AS IS" BASIS,
0016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0017: See the License for the specific language governing permissions and
0018: limitations under the License.
0019:
0020: */
0021:
0022: package org.apache.derby.impl.store.access.btree;
0023:
0024: import java.io.IOException;
0025: import java.util.Properties;
0026:
0027: import org.apache.derby.iapi.reference.SQLState;
0028:
0029: import org.apache.derby.iapi.services.sanity.SanityManager;
0030:
0031: import org.apache.derby.iapi.services.io.Storable;
0032:
0033: import org.apache.derby.iapi.error.StandardException;
0034: import org.apache.derby.iapi.store.access.conglomerate.Conglomerate;
0035: import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;
0036: import org.apache.derby.iapi.store.access.conglomerate.TransactionManager;
0037: import org.apache.derby.iapi.store.access.AccessFactoryGlobals;
0038: import org.apache.derby.iapi.store.access.ConglomerateController;
0039: import org.apache.derby.iapi.store.access.DynamicCompiledOpenConglomInfo;
0040: import org.apache.derby.iapi.store.access.RowLocationRetRowSource;
0041: import org.apache.derby.iapi.store.access.RowUtil;
0042: import org.apache.derby.iapi.store.access.ScanController;
0043: import org.apache.derby.iapi.store.access.StaticCompiledOpenConglomInfo;
0044: import org.apache.derby.iapi.store.access.TransactionController;
0045:
0046: import org.apache.derby.iapi.store.raw.ContainerHandle;
0047: import org.apache.derby.iapi.store.raw.FetchDescriptor;
0048: import org.apache.derby.iapi.store.raw.LockingPolicy;
0049: import org.apache.derby.iapi.store.raw.Page;
0050: import org.apache.derby.iapi.store.raw.RecordHandle;
0051: import org.apache.derby.iapi.store.raw.Transaction;
0052:
0053: import org.apache.derby.iapi.types.DataValueDescriptor;
0054:
0055: import org.apache.derby.iapi.types.RowLocation;
0056:
0057: import org.apache.derby.iapi.services.io.FormatableBitSet;
0058: import org.apache.derby.impl.store.access.conglomerate.ConglomerateUtil;
0059: import org.apache.derby.impl.store.access.conglomerate.TemplateRow;
0060:
0061: /**
0062:
0063: A b-tree controller corresponds to an instance of an open b-tree conglomerate.
0064: <P>
0065: <B>Concurrency Notes<\B>
0066: <P>
0067: The concurrency rules are derived from OpenBTree.
0068: <P>
0069: @see OpenBTree
0070:
0071: **/
0072:
0073: public class BTreeController extends OpenBTree implements
0074: ConglomerateController {
0075:
0076: transient DataValueDescriptor[] scratch_template = null;
0077:
0078: /**
0079: * Whether to get lock on the row being inserted, usually this lock
0080: * has already been gotten when the row was inserted into the base table.
0081: **/
0082: boolean get_insert_row_lock;
0083:
0084: /* Constructors: */
0085:
0086: public BTreeController() {
0087: }
0088:
0089: /*
0090: ** private Methods of BTreeController
0091: */
0092:
0093: /**
0094: * Attempt to reclaim committed deleted rows from the page.
0095: * <p>
0096: * Get exclusive latch on page, and then loop backward through
0097: * page searching for deleted rows which are committed. The routine
0098: * assumes that it is called from a transaction which cannot have
0099: * deleted any rows on the page. For each deleted row on the page
0100: * it attempts to get an exclusive lock on the deleted row, NOWAIT.
0101: * If it succeeds, and since this row did not delete the row then the
0102: * row must have been deleted by a transaction which has committed, so
0103: * it is safe to purge the row. It then purges the row from the page.
0104: * <p>
0105: * Note that this routine may remove all rows from the page, it will not
0106: * attempt a merge in this situation. This is because this routine is
0107: * called from split which is attempting an insert on the given page, so
0108: * it would be a waste to merge the page only to split it again to allow
0109: * the insert of the row causing the split.
0110: *
0111: * @return true if at least one row was purged.
0112: *
0113: * @param open_btree The already open btree to use to get latch on page.
0114: * @param pageno The page number of the leaf to attempt the reclaim on.
0115: *
0116: * @exception StandardException Standard exception policy.
0117: **/
0118: private boolean reclaim_deleted_rows(OpenBTree open_btree,
0119: long pageno) throws StandardException {
0120: boolean purged_at_least_one_row = false;
0121: ControlRow controlRow = null;
0122:
0123: try {
0124:
0125: if ((controlRow = ControlRow.Get(open_btree, pageno)) == null)
0126: return (false);
0127:
0128: LeafControlRow leaf = (LeafControlRow) controlRow;
0129:
0130: BTreeLockingPolicy btree_locking_policy = open_btree
0131: .getLockingPolicy();
0132:
0133: // The number records that can be reclaimed is:
0134: // total recs - control row - recs_not_deleted
0135: int num_possible_commit_delete = leaf.page.recordCount()
0136: - 1 - leaf.page.nonDeletedRecordCount();
0137:
0138: if ((num_possible_commit_delete > 0)
0139: && (btree_locking_policy
0140: .lockScanForReclaimSpace(leaf))) {
0141: // Need to get an exclusive scan lock on the page before we can
0142: // do any sort of purges, otherwise other concurrent scans would
0143: // not work. If we can't get the lock NOWAIT, just give up on
0144: // purging rows and do the split without reclaiming rows.
0145:
0146: Page page = leaf.page;
0147:
0148: // RowLocation column is in last column of template.
0149: FetchDescriptor lock_fetch_desc = RowUtil
0150: .getFetchDescriptorConstant(scratch_template.length - 1);
0151:
0152: // loop backward so that purges which affect the slot table
0153: // don't affect the loop (ie. they only move records we
0154: // have already looked at).
0155: for (int slot_no = page.recordCount() - 1; slot_no > 0; slot_no--) {
0156: if (page.isDeletedAtSlot(slot_no)) {
0157: // try to get an exclusive lock on the row, if we can
0158: // then the row is a committed deleted row and it is
0159: // safe to purge it.
0160: if (btree_locking_policy
0161: .lockScanCommittedDeletedRow(
0162: open_btree, leaf,
0163: scratch_template,
0164: lock_fetch_desc, slot_no)) {
0165: // the row is a committed deleted row, purge it.
0166: page.purgeAtSlot(slot_no, 1, true);
0167:
0168: purged_at_least_one_row = true;
0169: }
0170: }
0171: }
0172:
0173: }
0174: } catch (java.lang.ClassCastException cce) {
0175: // because we give up the latch on the leaf before entering this
0176: // routine, the page might change from a leaf to branch. If that
0177: // happens this routine will get a ClassCastException, and we
0178: // just give up trying to reclaim space.
0179: } finally {
0180: if (controlRow != null)
0181: controlRow.release();
0182:
0183: return (purged_at_least_one_row);
0184: }
0185: }
0186:
0187: /**
0188: * Start an internal transaction and do the split.
0189: * <p>
0190: * This routine starts a new transaction, and handles any errors that
0191: * may come during the transaction. This transation must not obtain any
0192: * locks as they are likely to conflict with the current user transaction.
0193: * <p>
0194: * If attempt_to_reclaim_deleted_rows is true this routine will
0195: * attempt to reclaim space on the leaf page input, by purging
0196: * committed deleted rows from the leaf. If it succeeds in purging at
0197: * least one row, then it will commit the internal transaction and return
0198: * without actually performing a split.
0199: *
0200: * @param scratch_template A scratch template used to search a page.
0201: * @param rowToInsert The row to insert, make sure during split to
0202: * make room for this row.
0203: *
0204: * @exception StandardException Standard exception policy.
0205: **/
0206: private long start_xact_and_dosplit(
0207: boolean attempt_to_reclaim_deleted_rows, long leaf_pageno,
0208: DataValueDescriptor[] scratch_template,
0209: DataValueDescriptor[] rowToInsert, int flag)
0210: throws StandardException {
0211: TransactionManager split_xact = null;
0212: OpenBTree split_open_btree = null;
0213: ControlRow root = null;
0214:
0215: // Get an internal transaction to be used for the split.
0216: split_xact = this .init_open_user_scans.getInternalTransaction();
0217:
0218: // open the btree again so that actions on it take place in the
0219: // split_xact, don't get any locks in this transaction.
0220:
0221: if (SanityManager.DEBUG) {
0222: if (((getOpenMode() & ContainerHandle.MODE_FORUPDATE) != ContainerHandle.MODE_FORUPDATE)) {
0223: SanityManager
0224: .THROWASSERT("Container not opened with update should not cause split");
0225: }
0226: }
0227:
0228: boolean do_split = true;
0229: if (attempt_to_reclaim_deleted_rows) {
0230: // Get lock on base table.
0231:
0232: ConglomerateController base_cc = null;
0233:
0234: try {
0235: base_cc = this
0236: .getConglomerate()
0237: .lockTable(
0238: split_xact,
0239: (ContainerHandle.MODE_FORUPDATE | ContainerHandle.MODE_LOCK_NOWAIT),
0240: TransactionController.MODE_RECORD,
0241: TransactionController.ISOLATION_REPEATABLE_READ);
0242: } catch (StandardException se) {
0243: // any error just don't try to reclaim deleted rows. The
0244: // expected error is that we can't get the lock, which the
0245: // current interface throws as a containerNotFound exception.
0246: }
0247:
0248: if (base_cc != null) {
0249: // we got IX lock on the base table, so can try reclaim space.
0250:
0251: // We can only reclaim space by opening the btree in row lock
0252: // mode. Table level lock row recovery is hard as we can't
0253: // determine if the deleted rows we encounter have been
0254: // deleted by our parent caller and have been committed or
0255: // not. We will have to get those rows offline.
0256: split_open_btree = new OpenBTree();
0257: split_open_btree
0258: .init(
0259: this .init_open_user_scans,
0260: split_xact,
0261: null, // open the container.
0262: split_xact.getRawStoreXact(),
0263: false,
0264: (ContainerHandle.MODE_FORUPDATE | ContainerHandle.MODE_LOCK_NOWAIT),
0265: TransactionManager.MODE_RECORD,
0266: this
0267: .getConglomerate()
0268: .getBtreeLockingPolicy(
0269: split_xact
0270: .getRawStoreXact(),
0271: TransactionController.MODE_RECORD,
0272: LockingPolicy.MODE_RECORD,
0273: TransactionController.ISOLATION_REPEATABLE_READ,
0274: (ConglomerateController) base_cc,
0275: split_open_btree), this
0276: .getConglomerate(),
0277: (LogicalUndo) null,
0278: (DynamicCompiledOpenConglomInfo) null);
0279:
0280: // don't split if we reclaim any rows.
0281: do_split = !reclaim_deleted_rows(split_open_btree,
0282: leaf_pageno);
0283:
0284: split_open_btree.close();
0285: }
0286: }
0287:
0288: long new_leaf_pageno = leaf_pageno;
0289: if (do_split) {
0290: split_open_btree = new OpenBTree();
0291: split_open_btree
0292: .init(
0293: this .init_open_user_scans,
0294: split_xact,
0295: null, // open the container.
0296: split_xact.getRawStoreXact(),
0297: false,
0298: getOpenMode(), // use same mode this controller
0299: // was opened with
0300: TransactionManager.MODE_NONE,
0301: this
0302: .getConglomerate()
0303: .getBtreeLockingPolicy(
0304: split_xact
0305: .getRawStoreXact(),
0306: this .init_lock_level,
0307: LockingPolicy.MODE_RECORD,
0308: TransactionController.ISOLATION_REPEATABLE_READ,
0309: (ConglomerateController) null, // no base row locks during split
0310: split_open_btree), this
0311: .getConglomerate(),
0312: (LogicalUndo) null,
0313: (DynamicCompiledOpenConglomInfo) null);
0314:
0315: // Get the root page back, and perform a split following the
0316: // to-be-inserted key. The split releases the root page latch.
0317: root = ControlRow.Get(split_open_btree, BTree.ROOTPAGEID);
0318:
0319: if (SanityManager.DEBUG)
0320: SanityManager.ASSERT(root.page.isLatched());
0321:
0322: new_leaf_pageno = root.splitFor(split_open_btree,
0323: scratch_template, null, rowToInsert, flag);
0324:
0325: split_open_btree.close();
0326: }
0327:
0328: split_xact.commit();
0329:
0330: split_xact.destroy();
0331:
0332: return (new_leaf_pageno);
0333: }
0334:
0335: /**
0336: Insert a row into the conglomerate.
0337:
0338: @param rowToInsert The row to insert into the conglomerate. The stored
0339: representations of the row's columns are copied into a new row
0340: somewhere in the conglomerate.
0341:
0342: @return Returns 0 if insert succeeded. Returns
0343: ConglomerateController.ROWISDUPLICATE if conglomerate supports uniqueness
0344: checks and has been created to disallow duplicates, and the row inserted
0345: had key columns which were duplicate of a row already in the table. Other
0346: insert failures will raise StandardException's.
0347:
0348: @exception StandardException Standard exception policy.
0349: **/
0350: private int doIns(DataValueDescriptor[] rowToInsert)
0351: throws StandardException {
0352: LeafControlRow targetleaf = null;
0353: LeafControlRow save_targetleaf = null;
0354: int insert_slot = 0;
0355: int result_slot = 0;
0356: int ret_val = 0;
0357: boolean reclaim_deleted_rows_attempted = false;
0358:
0359: if (scratch_template == null)
0360: scratch_template = runtime_mem.get_template();
0361:
0362: if (SanityManager.DEBUG)
0363: this .isIndexableRowConsistent(rowToInsert);
0364:
0365: // Create the objects needed for the insert.
0366: // RESOLVE (mikem) - should we cache this in the controller?
0367: SearchParameters sp = new SearchParameters(rowToInsert,
0368: SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH,
0369: scratch_template, this , false);
0370:
0371: // RowLocation column is in last column of template.
0372: FetchDescriptor lock_fetch_desc = RowUtil
0373: .getFetchDescriptorConstant(scratch_template.length - 1);
0374: RowLocation lock_row_loc = (RowLocation) scratch_template[scratch_template.length - 1];
0375:
0376: // Row locking - lock the row being inserted.
0377:
0378: if (get_insert_row_lock) {
0379: // I don't hold any latch yet so I can wait on this lock, so I
0380: // don't care about return value from this call. This
0381: // lock can only wait if the base table row was inserted in a
0382: // separate transaction which never happens in sql tables, but
0383: // does happen in the sparse indexes that synchronization builds.
0384:
0385: this
0386: .getLockingPolicy()
0387: .lockNonScanRow(
0388: this .getConglomerate(),
0389: (LeafControlRow) null,
0390: (LeafControlRow) null,
0391: rowToInsert,
0392: (ConglomerateController.LOCK_INS | ConglomerateController.LOCK_UPD));
0393: }
0394:
0395: while (true) {
0396: // Search the location at which the new row should be inserted.
0397: if (SanityManager.DEBUG)
0398: SanityManager.ASSERT(this .container != null);
0399:
0400: targetleaf = (LeafControlRow) ControlRow.Get(this ,
0401: BTree.ROOTPAGEID).search(sp);
0402:
0403: // Row locking - first lock row previous to row being inserted:
0404: // o if (sp.resultExact) then the row must be deleted and
0405: // we will be replacing it with the new row, lock
0406: // the row before the slot as the previous key.
0407: // o else
0408: // we will be inserting after the current slot so
0409: // lock the current slot as the previous key.
0410: //
0411: int slot_after_previous = (sp.resultExact ? sp.resultSlot
0412: : sp.resultSlot + 1);
0413:
0414: boolean latch_released = false;
0415:
0416: latch_released = !this
0417: .getLockingPolicy()
0418: .lockNonScanPreviousRow(
0419: this .getConglomerate(),
0420: targetleaf,
0421: slot_after_previous,
0422: lock_fetch_desc,
0423: scratch_template,
0424: lock_row_loc,
0425: this ,
0426: (ConglomerateController.LOCK_INS_PREVKEY | ConglomerateController.LOCK_UPD),
0427: TransactionManager.LOCK_INSTANT_DURATION);
0428:
0429: // special test to see if latch release code works
0430: if (SanityManager.DEBUG) {
0431: latch_released = test_errors(this ,
0432: "BTreeController_doIns", false, this
0433: .getLockingPolicy(), targetleaf,
0434: latch_released);
0435: }
0436:
0437: if (latch_released) {
0438: // Had to release latch in order to get the lock, probably
0439: // because of a forward scanner, research tree, and try again.
0440: targetleaf = null;
0441: continue;
0442: }
0443:
0444: // If the row is there already, simply undelete it.
0445: // The rationale for this is, since the index does
0446: // not support duplicates, the only way we could
0447: // find a duplicate is if we found a deleted row.
0448: // If we could lock it, then no other transaction
0449: // is deleting it; either this transaction deleted
0450: // it earlier, or it's simply a row that the space
0451: // reclaimer hasn't reclaimed yet.
0452: // Since inserts are done directly (i.e., not to a
0453: // location provided by a scan, we will see the
0454: // deleted row).
0455: if (sp.resultExact) {
0456: result_slot = insert_slot = sp.resultSlot;
0457:
0458: if (this .getConglomerate().nKeyFields != this
0459: .getConglomerate().nUniqueColumns) {
0460: // The key fields match, but not the row location. We
0461: // must wait on the lock on the other row location before
0462: // preceding, so as to serialize behind any work being done
0463: // to the row as part of another transaction.
0464:
0465: latch_released = !this .getLockingPolicy()
0466: .lockNonScanRowOnPage(
0467: this .getConglomerate(), targetleaf,
0468: insert_slot, lock_fetch_desc,
0469: scratch_template, lock_row_loc,
0470: ConglomerateController.LOCK_UPD);
0471:
0472: if (latch_released) {
0473: // Had to release latch in order to get the lock,
0474: // probably to wait for deleting xact to commit or
0475: // abort. Research tree, and try again.
0476: targetleaf = null;
0477: continue;
0478: }
0479: }
0480:
0481: // The row better be deleted, or something is very wrong.
0482:
0483: if (!(targetleaf.page.isDeletedAtSlot(insert_slot))) {
0484: // attempt to insert a duplicate into the index.
0485: ret_val = ConglomerateController.ROWISDUPLICATE;
0486: break;
0487: } else {
0488: if (this .getConglomerate().nKeyFields == this
0489: .getConglomerate().nUniqueColumns) {
0490: // The row that we found deleted is exactly the new row.
0491: targetleaf.page.deleteAtSlot(insert_slot,
0492: false, this .btree_undo);
0493:
0494: break;
0495: } else if (this .getConglomerate().nUniqueColumns == (this
0496: .getConglomerate().nKeyFields - 1)) {
0497: // The row that we found deleted has matching keys
0498: // which form the unique key fields,
0499: // but the nonkey fields may differ (for now the
0500: // heap rowlocation is the only nonkey field
0501: // allowed).
0502:
0503: // RESOLVE BT39 (mikem) - when/if heap row location
0504: // is not fixed we must handle update failing for
0505: // out of space and split if it does. For now
0506: // if the update fails because of lack of space
0507: // an exception is thrown and the statement is
0508: // backed out. Should not happen very often.
0509: targetleaf.page.deleteAtSlot(insert_slot,
0510: false, this .btree_undo);
0511:
0512: boolean update_succeeded = true;
0513:
0514: try {
0515: int rowloc_index = this .getConglomerate().nKeyFields - 1;
0516: targetleaf.page
0517: .updateFieldAtSlot(
0518: insert_slot,
0519: rowloc_index,
0520: (DataValueDescriptor) RowUtil
0521: .getColumn(
0522: rowToInsert,
0523: (FormatableBitSet) null,
0524: rowloc_index),
0525: this .btree_undo);
0526: } catch (StandardException se) {
0527: // check if the exception is for out of space
0528: if (!se.getMessageId().equals(
0529: SQLState.DATA_NO_SPACE_FOR_RECORD)) {
0530: throw se;
0531: }
0532:
0533: // The statement exception is
0534: // because the update failed for out of
0535: // space (ie. the field got longer and there
0536: // is no room on the page for the expanded
0537: // field). Address this error by falling
0538: // through the code and doing a split.
0539: update_succeeded = false; // update failed.
0540: targetleaf.page.deleteAtSlot(insert_slot,
0541: true, this .btree_undo);
0542: }
0543:
0544: if (update_succeeded)
0545: break;
0546: } else {
0547: // Can only happen with non key fields in the btree.
0548: throw (StandardException
0549: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE));
0550: }
0551: }
0552: } else if (targetleaf.page.recordCount() - 1 < this
0553: .getConglomerate().maxRowsPerPage) {
0554: // The row wasn't there, so try to insert it
0555: // on the page returned by the search.
0556: insert_slot = sp.resultSlot + 1;
0557: result_slot = insert_slot + 1;
0558:
0559: // By default maxRowsPerPage is set to MAXINT, some tests
0560: // set it small to cause splitting to happen quicker with
0561: // less data.
0562:
0563: if (targetleaf.page.insertAtSlot(insert_slot,
0564: rowToInsert, (FormatableBitSet) null,
0565: this .btree_undo, Page.INSERT_DEFAULT,
0566: AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD) != null) {
0567: // Insert succeeded, so we're done.
0568:
0569: break;
0570: }
0571:
0572: // RESOLVE (mikem) - another long row issue.
0573: // For now if a row does not fit on a page and there
0574: // is only the control row on the page and at most one
0575: // other row on the page, throw an exception
0576:
0577: if (targetleaf.page.recordCount() <= 2) {
0578: throw StandardException
0579: .newException(SQLState.BTREE_NO_SPACE_FOR_KEY);
0580: }
0581:
0582: // start splitting ...
0583: }
0584:
0585: // Create some space by splitting pages.
0586:
0587: // determine where in page/table row causing split would go
0588: int flag = 0;
0589: if (insert_slot == 1) {
0590: flag |= ControlRow.SPLIT_FLAG_FIRST_ON_PAGE;
0591: if (targetleaf.isLeftmostLeaf())
0592: flag |= ControlRow.SPLIT_FLAG_FIRST_IN_TABLE;
0593: } else if (insert_slot == targetleaf.page.recordCount()) {
0594: flag |= ControlRow.SPLIT_FLAG_LAST_ON_PAGE;
0595: if (targetleaf.isRightmostLeaf())
0596: flag |= ControlRow.SPLIT_FLAG_LAST_IN_TABLE;
0597: }
0598:
0599: long targetleaf_pageno = targetleaf.page.getPageNumber();
0600:
0601: if ((targetleaf.page.recordCount() - targetleaf.page
0602: .nonDeletedRecordCount()) <= 0) {
0603: // Don't do reclaim work if there are no deleted records.
0604: reclaim_deleted_rows_attempted = true;
0605: }
0606:
0607: BranchRow branchrow = BranchRow
0608: .createBranchRowFromOldLeafRow(rowToInsert,
0609: targetleaf_pageno);
0610:
0611: // Release the target page because (a) it may change as a
0612: // result of the split, (b) the latch ordering requires us
0613: // to acquire latches from top to bottom, and (c) this
0614: // loop should be done in a system transaction.
0615: targetleaf.release();
0616: targetleaf = null;
0617:
0618: start_xact_and_dosplit(!reclaim_deleted_rows_attempted,
0619: targetleaf_pageno, scratch_template, branchrow
0620: .getRow(), flag);
0621:
0622: // only attempt to reclaim deleted rows once, otherwise the
0623: // split loop could loop forever, trying to reclaim a deleted
0624: // row that was not committed.
0625: reclaim_deleted_rows_attempted = true;
0626:
0627: // RESOLVE (mikem) possible optimization could be to save
0628: // split location and look there first, if this has
0629: // already caused a split. Or even return a latched page
0630: // from splitFor(). For now just execute the loop again
0631: // searching the tree for somewhere to put the row.
0632: }
0633:
0634: // set in-memory hint of where last row on page was inserted.
0635: targetleaf.last_search_result = result_slot;
0636:
0637: // Check that page just updated is consistent.
0638: if (SanityManager.DEBUG) {
0639: if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck")) {
0640: targetleaf.checkConsistency(this , null, true);
0641: }
0642: }
0643:
0644: // Done with the target page.
0645: targetleaf.release();
0646: targetleaf = null;
0647:
0648: // return the status about insert - 0 is ok, or duplicate status.
0649: return (ret_val);
0650: }
0651:
0652: /**
0653: * Just insert the row on the current page/slot if it fits.
0654: * <p>
0655: * @exception StandardException Standard exception policy.
0656: **/
0657: private boolean do_load_insert(DataValueDescriptor[] rowToInsert,
0658: LeafControlRow leaf, int insert_slot)
0659: throws StandardException {
0660: LeafControlRow old_leaf = null;
0661: boolean row_inserted = false;
0662: int num_rows_on_page = leaf.page.recordCount() - 1;
0663:
0664: if (SanityManager.DEBUG) {
0665: SanityManager
0666: .ASSERT(insert_slot == leaf.page.recordCount());
0667: SanityManager
0668: .ASSERT(leaf.getrightSiblingPageNumber() == ContainerHandle.INVALID_PAGE_NUMBER);
0669: this .isIndexableRowConsistent(rowToInsert);
0670: }
0671:
0672: if (num_rows_on_page < this .getConglomerate().maxRowsPerPage) {
0673: // By default maxRowsPerPage is set to MAXINT, some tests
0674: // set it small to cause splitting to happen quicker with
0675: // less data.
0676:
0677: if (SanityManager.DEBUG) {
0678: // Caller should have sorted and done duplicate checking.
0679:
0680: if (insert_slot > 1) {
0681: // verify that the row inserted is >= than previous row.
0682: int compare_result = ControlRow
0683: .CompareIndexRowFromPageToKey(
0684: leaf,
0685: insert_slot - 1,
0686: scratch_template,
0687: rowToInsert,
0688: this .getConglomerate().nUniqueColumns,
0689: 0,
0690: this .getConglomerate().ascDescInfo);
0691:
0692: if (compare_result >= 0) {
0693: // Rows must be presented in order, so the row we are
0694: // inserting must always be greater than the previous
0695: // row on the page.
0696: SanityManager.THROWASSERT("result = "
0697: + compare_result);
0698: }
0699: }
0700: }
0701:
0702: if (leaf.page.insertAtSlot(insert_slot, rowToInsert,
0703: (FormatableBitSet) null, this .btree_undo,
0704: Page.INSERT_DEFAULT,
0705: AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD) != null) {
0706: // Insert succeeded, so we're done.
0707: row_inserted = true;
0708: } else {
0709: // RESOLVE (mikem) - another long row issue.
0710: // For now if a row does not fit on a page and there
0711: // is only the control row on the page and at most one
0712: // other row on the page, throw an exception
0713:
0714: if (leaf.page.recordCount() <= 2) {
0715: throw StandardException
0716: .newException(SQLState.BTREE_NO_SPACE_FOR_KEY);
0717: }
0718: }
0719: }
0720:
0721: // Check that page just updated is consistent.
0722: if (SanityManager.DEBUG) {
0723: if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck")) {
0724: leaf.checkConsistency(this , null, true);
0725: }
0726: }
0727:
0728: return (row_inserted);
0729: }
0730:
0731: /**
0732: * Create room to insert a row to the right of the largest key in table.
0733: * <p>
0734: * Perform a split pass on the tree which will move the largest key in
0735: * leaf right to a new leaf, splitting parent branch pages as necessary.
0736: *
0737: * @exception StandardException Standard exception policy.
0738: **/
0739: private LeafControlRow do_load_split(
0740: DataValueDescriptor[] rowToInsert, LeafControlRow leaf)
0741: throws StandardException {
0742: LeafControlRow new_leaf = null;
0743:
0744: BranchRow branchrow = BranchRow.createBranchRowFromOldLeafRow(
0745: rowToInsert, leaf.page.getPageNumber());
0746:
0747: // Release the target page because (a) it may change as a
0748: // result of the split, (b) the latch ordering requires us
0749: // to acquire latches from top to bottom, and (c) this
0750: // loop should be done in a system transaction.
0751: long old_leafpage = leaf.page.getPageNumber();
0752:
0753: leaf.release();
0754: leaf = null;
0755:
0756: long new_leaf_pageno = start_xact_and_dosplit(
0757: false /* don't try to reclaim deleted rows */,
0758: old_leafpage,
0759: scratch_template,
0760: branchrow.getRow(),
0761: (ControlRow.SPLIT_FLAG_LAST_ON_PAGE | ControlRow.SPLIT_FLAG_LAST_IN_TABLE));
0762:
0763: new_leaf = (LeafControlRow) ControlRow.Get(this ,
0764: new_leaf_pageno);
0765:
0766: // The leaf must be the rightmost leaf in the table, the first time
0767: // the root grows from leaf to branch it will be a leaf with many
0768: // rows which will probably have to be split soon, after that it will
0769: // be a leaf with only one row. The current algorithm requires that
0770: // there be at least one row for duplicate checking (the duplicate
0771: // checking code does not handle going left to the previous leaf) -
0772: // this is the way the split at rightmost leaf row works currently.
0773: if (SanityManager.DEBUG) {
0774: if (new_leaf.getrightSiblingPageNumber() != ContainerHandle.INVALID_PAGE_NUMBER) {
0775: SanityManager
0776: .THROWASSERT("new_leaf.getrightSiblingPageNumber() = "
0777: + new_leaf.getrightSiblingPageNumber());
0778: }
0779: if (new_leaf.page.recordCount() <= 1) {
0780: SanityManager
0781: .THROWASSERT("new_leaf.page.recordCount() = "
0782: + new_leaf.page.recordCount());
0783: }
0784: }
0785:
0786: return (new_leaf);
0787: }
0788:
0789: /*
0790: ** public Methods of BTreeController
0791: */
0792:
0793: /**
0794: Initialize the controller for use.
0795: <p>
0796: Any changes to this method will probably have to be reflected in close as
0797: well.
0798: <p>
0799: Currently delegates to OpenBTree. If the btree controller ends up not
0800: having any state of its own, we can remove this method (the VM will
0801: dispatch to OpenBTree), gaining some small efficiency. For now, this
0802: method remains for clarity.
0803:
0804: @exception StandardException Standard exception policy.
0805: **/
0806: public void init(TransactionManager xact_manager, boolean hold,
0807: ContainerHandle container, Transaction rawtran,
0808: int open_mode, int lock_level,
0809: BTreeLockingPolicy btree_locking_policy,
0810: BTree conglomerate, LogicalUndo undo,
0811: StaticCompiledOpenConglomInfo static_info,
0812: DynamicCompiledOpenConglomInfo dynamic_info)
0813: throws StandardException {
0814: get_insert_row_lock = ((open_mode & TransactionController.OPENMODE_BASEROW_INSERT_LOCKED) == 0);
0815:
0816: super .init(xact_manager, xact_manager, container, rawtran,
0817: hold, open_mode, lock_level, btree_locking_policy,
0818: conglomerate, undo, dynamic_info);
0819: }
0820:
0821: /*
0822: ** Methods of ConglomerateController
0823: */
0824:
0825: /**
0826: Close the conglomerate controller.
0827: <p>
0828: Any changes to this method will probably have to be reflected in close as
0829: well.
0830: <p>
0831: Currently delegates to OpenBTree. If the btree controller ends up not
0832: having any state of its own, we can remove this method (the VM will
0833: dispatch to OpenBTree), gaining some small efficiency. For now, this
0834: method remains for clarity.
0835:
0836: @see ConglomerateController#close
0837: **/
0838: public void close() throws StandardException {
0839: super .close();
0840:
0841: // If we are closed due to catching an error in the middle of init,
0842: // xact_manager may not be set yet.
0843: if (getXactMgr() != null)
0844: getXactMgr().closeMe(this );
0845: }
0846:
0847: /**
0848: * Close conglomerate controller as part of terminating a transaction.
0849: * <p>
0850: * Use this call to close the conglomerate controller resources as part of
0851: * committing or aborting a transaction. The normal close() routine may
0852: * do some cleanup that is either unnecessary, or not correct due to the
0853: * unknown condition of the controller following a transaction ending error.
0854: * Use this call when closing all controllers as part of an abort of a
0855: * transaction.
0856: * <p)
0857: * This call is meant to only be used internally by the Storage system,
0858: * clients of the storage system should use the simple close() interface.
0859: * <p>
0860: * RESOLVE (mikem) - move this call to ConglomerateManager so it is
0861: * obvious that non-access clients should not call this.
0862: *
0863: * @param closeHeldScan If true, means to close controller even if
0864: * it has been opened to be kept opened
0865: * across commit. This is
0866: * used to close these controllers on abort.
0867: *
0868: * @return boolean indicating that the close has resulted in a real close
0869: * of the controller. A held scan will return false if
0870: * called by closeForEndTransaction(false), otherwise it
0871: * will return true. A non-held scan will always return
0872: * true.
0873: *
0874: * @exception StandardException Standard exception policy.
0875: **/
0876: public boolean closeForEndTransaction(boolean closeHeldScan)
0877: throws StandardException {
0878: super .close();
0879:
0880: if ((!getHold()) || closeHeldScan) {
0881: // If we are closed due to catching an error in the middle of init,
0882: // xact_manager may not be set yet.
0883: if (getXactMgr() != null)
0884: getXactMgr().closeMe(this );
0885:
0886: return (true);
0887: } else {
0888: return (false);
0889: }
0890: }
0891:
0892: /**
0893: Insert a row into the conglomerate.
0894: @see ConglomerateController#insert
0895:
0896: @param row The row to insert into the conglomerate. The stored
0897: representations of the row's columns are copied into a new row
0898: somewhere in the conglomerate.
0899:
0900: @return Returns 0 if insert succeeded. Returns
0901: ConglomerateController.ROWISDUPLICATE if conglomerate supports uniqueness
0902: checks and has been created to disallow duplicates, and the row inserted
0903: had key columns which were duplicate of a row already in the table. Other
0904: insert failures will raise StandardException's.
0905:
0906: @exception StandardException Standard exception policy.
0907: **/
0908: public int insert(DataValueDescriptor[] row)
0909: throws StandardException {
0910:
0911: if (isClosed()) {
0912: if (getHold()) {
0913: reopen();
0914: } else {
0915: throw StandardException.newException(
0916: SQLState.BTREE_IS_CLOSED, new Long(
0917: err_containerid));
0918: }
0919: }
0920:
0921: if (SanityManager.DEBUG) {
0922: SanityManager.ASSERT(this .container != null);
0923:
0924: TemplateRow.checkPartialColumnTypes(
0925: this .getConglomerate().format_ids,
0926: (FormatableBitSet) null, (int[]) null, row);
0927: }
0928:
0929: return doIns(row);
0930: }
0931:
0932: /**
0933: Return whether this is a keyed conglomerate.
0934: <p>
0935: All b-trees are keyed.
0936: @see ConglomerateController#isKeyed
0937: **/
0938: public boolean isKeyed() {
0939: return (true);
0940: }
0941:
0942: /*
0943: * Request the system properties associated with a table.
0944: * <p>
0945: * Request the value of properties that are associated with a table. The
0946: * following properties can be requested:
0947: * derby.storage.pageSize
0948: * derby.storage.pageReservedSpace
0949: * derby.storage.minimumRecordSize
0950: * derby.storage.initialPages
0951: * <p>
0952: * To get the value of a particular property add it to the property list,
0953: * and on return the value of the property will be set to it's current
0954: * value. For example:
0955: *
0956: * get_prop(ConglomerateController cc)
0957: * {
0958: * Properties prop = new Properties();
0959: * prop.put("derby.storage.pageSize", "");
0960: * cc.getTableProperties(prop);
0961: *
0962: * System.out.println(
0963: * "table's page size = " +
0964: * prop.getProperty("derby.storage.pageSize");
0965: * }
0966: *
0967: * @param prop Property list to fill in.
0968: *
0969: * @exception StandardException Standard exception policy.
0970: **/
0971: public void getTableProperties(Properties prop)
0972: throws StandardException {
0973: if (this .container == null) {
0974: throw StandardException
0975: .newException(SQLState.BTREE_IS_CLOSED, new Long(
0976: err_containerid));
0977: }
0978:
0979: container.getContainerProperties(prop);
0980:
0981: return;
0982: }
0983:
0984: /**
0985: * Request set of properties associated with a table.
0986: * <p>
0987: * Returns a property object containing all properties that the store
0988: * knows about, which are stored persistently by the store. This set
0989: * of properties may vary from implementation to implementation of the
0990: * store.
0991: * <p>
0992: * This call is meant to be used only for internal query of the properties
0993: * by jbms, for instance by language during bulk insert so that it can
0994: * create a new conglomerate which exactly matches the properties that
0995: * the original container was created with. This call should not be used
0996: * by the user interface to present properties to users as it may contain
0997: * properties that are meant to be internal to jbms. Some properties are
0998: * meant only to be specified by jbms code and not by users on the command
0999: * line.
1000: * <p>
1001: * Note that not all properties passed into createConglomerate() are stored
1002: * persistently, and that set may vary by store implementation.
1003: *
1004: * @param prop Property list to add properties to. If null, routine will
1005: * create a new Properties object, fill it in and return it.
1006: *
1007: * @exception StandardException Standard exception policy.
1008: **/
1009: public Properties getInternalTablePropertySet(Properties prop)
1010: throws StandardException {
1011: Properties ret_properties = ConglomerateUtil
1012: .createRawStorePropertySet(prop);
1013:
1014: getTableProperties(ret_properties);
1015:
1016: return (ret_properties);
1017: }
1018:
1019: /**
1020: * Load rows from rowSource into the opened btree.
1021: * <p>
1022: * Efficiently load rows into the already opened btree. The btree must
1023: * be table locked, as no row locks will be requested by this routine.
1024: * On exit from this routine the conglomerate will be closed (on both
1025: * error or success).
1026: * <p>
1027: * This routine does an almost bottom up build of a btree. It assumes
1028: * all rows arrive in sorted order, and inserts them directly into the
1029: * next (to the right) spot in the current leaf until there is no space.
1030: * Then it calls the generic split code to add the next leaf (RESOLVE -
1031: * in the future we could optimize this to split bottom up rather than
1032: * top down for create index).
1033: *
1034: * @exception StandardException Standard exception policy. If conglomerate
1035: * supports uniqueness checks and has been
1036: * created to disallow duplicates, and one of
1037: * the rows being loaded had key columns which
1038: * were duplicate of a row already in the
1039: * conglomerate, then raise
1040: * SQLState.STORE_CONGLOMERATE_DUPLICATE_KEY_EXCEPTION.
1041: *
1042: * @see Conglomerate#load
1043: **/
1044: public long load(TransactionManager xact_manager,
1045: boolean createConglom, RowLocationRetRowSource rowSource)
1046: throws StandardException {
1047: long num_rows_loaded = 0;
1048:
1049: if (SanityManager.DEBUG) {
1050: SanityManager
1051: .ASSERT(
1052: createConglom,
1053: "Cannot load a btree incrementally - it must either be entirely logged, or entirely not logged. Doesn't make sense to log only the allocation when one cannot guarantee to not touch any pre-existing pages");
1054: }
1055:
1056: if (scratch_template == null)
1057: scratch_template = runtime_mem.get_template();
1058:
1059: LeafControlRow current_leaf = null;
1060:
1061: try {
1062: // Btree must just have been created and empty, so there must
1063: // be one root leaf page which is empty except for the control row.
1064: current_leaf = (LeafControlRow) ControlRow.Get(this ,
1065: BTree.ROOTPAGEID);
1066: int current_insert_slot = 1;
1067:
1068: if (SanityManager.DEBUG) {
1069: // root must be empty except for the control row.
1070: SanityManager
1071: .ASSERT(current_leaf.page.recordCount() == 1);
1072: }
1073:
1074: // now loop thru the row source and insert into the btree
1075: FormatableBitSet validColumns = rowSource.getValidColumns();
1076:
1077: // get the next row and its valid columns from the rowSource
1078: DataValueDescriptor[] row;
1079: while ((row = rowSource.getNextRowFromRowSource()) != null) {
1080: num_rows_loaded++;
1081:
1082: if (SanityManager.DEBUG) {
1083: SanityManager.ASSERT(validColumns == null,
1084: "Does not support partial row");
1085: }
1086:
1087: while (true) {
1088: if (do_load_insert(row, current_leaf,
1089: current_insert_slot)) {
1090: // row inserted successfully.
1091: break;
1092: } else {
1093: // if insert fails, do a split pass. There is an edge
1094: // case where multiple split passes are necessary if
1095: // branch splits are necessary, thus the loop. It is
1096: // most likely that only a single split pass will be
1097: // necessary.
1098: current_leaf = do_load_split(row, current_leaf);
1099:
1100: current_insert_slot = current_leaf.page
1101: .recordCount();
1102: }
1103: }
1104: current_insert_slot++;
1105: }
1106:
1107: current_leaf.release();
1108: current_leaf = null;
1109:
1110: // Loading done, must flush all pages to disk since it is unlogged.
1111: if (!this .getConglomerate().isTemporary())
1112: container.flushContainer();
1113: } finally {
1114: this .close();
1115: }
1116:
1117: return (num_rows_loaded);
1118: }
1119:
1120: /*
1121: ** Methods of ConglomerateController which are not supported.
1122: */
1123:
1124: /**
1125: Delete a row from the conglomerate.
1126: @see ConglomerateController#delete
1127:
1128: @exception StandardException Standard exception policy.
1129: **/
1130: public boolean delete(RowLocation loc) throws StandardException {
1131: throw (StandardException
1132: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE));
1133: }
1134:
1135: /**
1136: Fetch the row at the given location.
1137: @see ConglomerateController#fetch
1138:
1139: @exception StandardException Standard exception policy.
1140: **/
1141: public boolean fetch(RowLocation loc, DataValueDescriptor[] row,
1142: FormatableBitSet validColumns) throws StandardException {
1143: throw (StandardException
1144: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE));
1145: }
1146:
1147: /**
1148: Fetch the row at the given location.
1149: @see ConglomerateController#fetch
1150:
1151: @exception StandardException Standard exception policy.
1152: **/
1153: public boolean fetch(RowLocation loc, DataValueDescriptor[] row,
1154: FormatableBitSet validColumns, boolean waitForLock)
1155: throws StandardException {
1156: throw (StandardException
1157: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE));
1158: }
1159:
1160: /**
1161: Insert a row into the conglomerate, and store its location in the
1162: provided template row location.
1163:
1164: Unimplemented by btree.
1165:
1166: @see ConglomerateController#insertAndFetchLocation
1167:
1168: @exception StandardException Standard exception policy.
1169: **/
1170: public void insertAndFetchLocation(DataValueDescriptor[] row,
1171: RowLocation templateRowLocation) throws StandardException {
1172: throw StandardException
1173: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE);
1174: }
1175:
1176: /**
1177: Return a row location object of the correct type to be
1178: used in calls to insertAndFetchLocation.
1179:
1180: @see ConglomerateController#newRowLocationTemplate
1181:
1182: @exception StandardException Standard exception policy.
1183: **/
1184: public RowLocation newRowLocationTemplate()
1185: throws StandardException {
1186: throw StandardException
1187: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE);
1188: }
1189:
1190: /**
1191: * Lock the given row location.
1192: * <p>
1193: * Should only be called by access.
1194: * <p>
1195: * This call can be made on a ConglomerateController that was opened
1196: * for locking only.
1197: * <p>
1198: * RESOLVE (mikem) - move this call to ConglomerateManager so it is
1199: * obvious that non-access clients should not call this.
1200: *
1201: * @return true if lock was granted, only can be false if wait was false.
1202: *
1203: * @param loc The "RowLocation" which describes the exact row to lock.
1204: * @param wait Should the lock call wait to be granted?
1205: *
1206: * @exception StandardException Standard exception policy.
1207: **/
1208: public boolean lockRow(RowLocation loc, int lock_operation,
1209: boolean wait, int lock_duration) throws StandardException {
1210: throw StandardException
1211: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE);
1212: }
1213:
1214: public boolean lockRow(long page_num, int record_id,
1215: int lock_operation, boolean wait, int lock_duration)
1216: throws StandardException {
1217: throw StandardException
1218: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE);
1219: }
1220:
1221: public void unlockRowAfterRead(RowLocation loc, boolean forUpdate,
1222: boolean row_qualifies) throws StandardException {
1223: throw StandardException
1224: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE);
1225: }
1226:
1227: /**
1228: Replace the entire row at the given location.
1229: @see ConglomerateController#replace
1230:
1231: @exception StandardException Standard exception policy.
1232: **/
1233: public boolean replace(RowLocation loc, DataValueDescriptor[] row,
1234: FormatableBitSet validColumns) throws StandardException {
1235: throw StandardException
1236: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE);
1237: }
1238: }
|