| /* |
| |
| Derby - Class org.apache.derby.impl.store.access.btree.BTreeScan |
| |
| Licensed to the Apache Software Foundation (ASF) under one or more |
| contributor license agreements. See the NOTICE file distributed with |
| this work for additional information regarding copyright ownership. |
| The ASF licenses this file to you under the Apache License, Version 2.0 |
| (the "License"); you may not use this file except in compliance with |
| the License. You may obtain a copy of the License at |
| |
| http://www.apache.org/licenses/LICENSE-2.0 |
| |
| Unless required by applicable law or agreed to in writing, software |
| distributed under the License is distributed on an "AS IS" BASIS, |
| WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| See the License for the specific language governing permissions and |
| limitations under the License. |
| |
| */ |
| |
| package org.apache.derby.impl.store.access.btree; |
| |
| import org.apache.derby.iapi.reference.SQLState; |
| |
| import org.apache.derby.shared.common.sanity.SanityManager; |
| |
| import org.apache.derby.iapi.error.StandardException; |
| |
| import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo; |
| import org.apache.derby.iapi.store.access.conglomerate.ScanManager; |
| import org.apache.derby.iapi.store.access.conglomerate.TransactionManager; |
| |
| import org.apache.derby.iapi.store.access.ConglomerateController; |
| import org.apache.derby.iapi.store.access.DynamicCompiledOpenConglomInfo; |
| import org.apache.derby.iapi.store.access.Qualifier; |
| import org.apache.derby.iapi.store.access.RowUtil; |
| import org.apache.derby.iapi.store.access.ScanController; |
| import org.apache.derby.iapi.store.access.ScanInfo; |
| import org.apache.derby.iapi.store.access.StaticCompiledOpenConglomInfo; |
| |
| import org.apache.derby.iapi.store.raw.ContainerHandle; |
| import org.apache.derby.iapi.store.raw.FetchDescriptor; |
| import org.apache.derby.iapi.store.raw.LockingPolicy; |
| import org.apache.derby.iapi.store.raw.Page; |
| import org.apache.derby.iapi.store.raw.RecordHandle; |
| import org.apache.derby.iapi.store.raw.Transaction; |
| |
| import org.apache.derby.iapi.types.DataValueDescriptor; |
| |
| import org.apache.derby.iapi.types.RowLocation; |
| |
| import org.apache.derby.impl.store.access.conglomerate.TemplateRow; |
| |
| import org.apache.derby.iapi.services.io.FormatableBitSet; |
| import org.apache.derby.iapi.store.access.BackingStoreHashtable; |
| |
| /** |
| |
| A b-tree scan controller corresponds to an instance of an open b-tree scan. |
| <P> |
| <B>Concurrency Notes</B> |
| <P> |
| The concurrency rules are derived from OpenBTree. |
| <P> |
| @see OpenBTree |
| |
| **/ |
| |
| public abstract class BTreeScan extends OpenBTree implements ScanManager |
| { |
| |
| /* |
| ** Fields of BTreeScan |
| */ |
| |
| /** |
| * init_startKeyValue, init_qualifier, and init_stopKeyValue all are used |
| * to store * references to the values passed in when ScanController.init() |
| * is called. It is assumed that these are not altered by the client |
| * while the scan is active. |
| */ |
| protected Transaction init_rawtran = null; |
| protected boolean init_forUpdate; |
| protected FormatableBitSet init_scanColumnList; |
| protected DataValueDescriptor[] init_template; |
| protected DataValueDescriptor[] init_startKeyValue; |
| protected int init_startSearchOperator = 0; |
| protected Qualifier init_qualifier[][] = null; |
| protected DataValueDescriptor[] init_stopKeyValue; |
| protected int init_stopSearchOperator = 0; |
| protected boolean init_hold; |
| |
| |
| /** |
| * The fetch descriptor which describes the row to be returned by the scan. |
| **/ |
| protected FetchDescriptor init_fetchDesc; |
| |
| |
| /** |
| * A constant FetchDescriptor which describes the position of the |
| * RowLocation field within the btree, currently always the last column). |
| * Used by lock/unlock to fetch the RowLocation. |
| * Only needs to be allocated once per scan. |
| **/ |
| protected FetchDescriptor init_lock_fetch_desc; |
| |
| |
| BTreeRowPosition scan_position; |
| |
| |
| /** |
| * Whether the scan should requests UPDATE locks which then will be |
| * converted to X locks when the actual operation is performed. |
| **/ |
| protected boolean init_useUpdateLocks = false; |
| |
| /* |
| * There are 5 states a scan can be in. |
| * SCAN_INIT - A scan has started but no positioning has been done. |
| * The scan will be positioned when the first next() call |
| * has been made. None of the positioning state variables |
| * are valid in this state. |
| * SCAN_INPROGRESS - |
| * A scan is in this state after the first next() call. |
| * On exit from any BTreeScan method, while in this state, |
| * the scan "points" at a row which qualifies for the |
| * scan. While not maintaining latches on a page the |
| * current position of the scan is either kept by record |
| * handle or key. To tell which use the following: |
| * if (record key == null) |
| * record handle has current position |
| * else |
| * record key has current position |
| * |
| * SCAN_DONE - Once the end of the table or the stop condition is met |
| * then the scan is placed in this state. Only valid |
| * ScanController method at this point is close(). |
| * |
| * SCAN_HOLD_INIT - |
| * The scan has been opened and held open across a commit, |
| * at the last commit the state was SCAN_INIT. |
| * The scan has never progressed from the SCAN_INIT state |
| * during a transaction. When a next is done the state |
| * will either progress to SCAN_INPROGRESS or SCAN_DONE. |
| * |
| * SCAN_HOLD_INPROGRESS - |
| * The scan has been opened and held open across a commit, |
| * at the last commit the state was in SCAN_INPROGRESS. |
| * The transaction which opened the scan has committed, |
| * but the scan was opened with the "hold" option true. |
| * At commit the locks were released and the "current" |
| * position is remembered. In this state only two calls |
| * are valid, either next() or close(). When next() is |
| * called the scan is reopened, the underlying container |
| * is opened thus associating all new locks with the current |
| * transaction, and the scan continues at the "next" row. |
| */ |
| protected static final int SCAN_INIT = 1; |
| protected static final int SCAN_INPROGRESS = 2; |
| protected static final int SCAN_DONE = 3; |
| protected static final int SCAN_HOLD_INIT = 4; |
| protected static final int SCAN_HOLD_INPROGRESS = 5; |
| |
| /** |
| * Delay positioning the table at the start position until the first |
| * next() call. The initial position is done in positionAtStartPosition(). |
| */ |
| protected int scan_state = SCAN_INIT; |
| |
| /** |
| * Performance counters ... |
| */ |
| protected int stat_numpages_visited = 0; |
| protected int stat_numrows_visited = 0; |
| protected int stat_numrows_qualified = 0; |
| protected int stat_numdeleted_rows_visited = 0; |
| |
| /** |
| * What kind of row locks to get during the scan. |
| **/ |
| protected int lock_operation; |
| |
| |
| /** |
| * A 1 element array to turn fetchNext and fetch calls into |
| * fetchNextGroup calls. |
| **/ |
| protected DataValueDescriptor[][] fetchNext_one_slot_array = |
| new DataValueDescriptor[1][]; |
| |
| /* Constructors for This class: */ |
| |
| public BTreeScan() |
| { |
| } |
| |
| /* |
| ** Private/Protected methods of This class, sorted alphabetically |
| */ |
| |
| /** |
| * Fetch the next N rows from the table. |
| * <p> |
| * Utility routine used by both fetchSet() and fetchNextGroup(). |
| * |
| * @exception StandardException Standard exception policy. |
| **/ |
| abstract protected int fetchRows( |
| BTreeRowPosition pos, |
| DataValueDescriptor[][] row_array, |
| RowLocation[] rowloc_array, |
| BackingStoreHashtable hash_table, |
| long max_rowcnt, |
| int[] key_column_numbers) |
| throws StandardException; |
| |
| |
| /** |
| * Shared initialization code between init() and reopenScan(). |
| * <p> |
| * Basically save away input parameters describing qualifications for |
| * the scan, and do some error checking. |
| * |
| * @exception StandardException Standard exception policy. |
| **/ |
| private void initScanParams( |
| DataValueDescriptor[] startKeyValue, |
| int startSearchOperator, |
| Qualifier qualifier[][], |
| DataValueDescriptor[] stopKeyValue, |
| int stopSearchOperator) |
| throws StandardException |
| { |
| // startKeyValue init. |
| this.init_startKeyValue = startKeyValue; |
| if (RowUtil.isRowEmpty(this.init_startKeyValue)) |
| this.init_startKeyValue = null; |
| |
| // startSearchOperator init. |
| this.init_startSearchOperator = startSearchOperator; |
| |
| // qualifier init. |
| if ((qualifier != null) && (qualifier .length == 0)) |
| qualifier = null; |
| this.init_qualifier = qualifier; |
| |
| // stopKeyValue init. |
| this.init_stopKeyValue = stopKeyValue; |
| if (RowUtil.isRowEmpty(this.init_stopKeyValue)) |
| this.init_stopKeyValue = null; |
| |
| // stopSearchOperator init. |
| this.init_stopSearchOperator = stopSearchOperator; |
| |
| // reset the "current" position to starting condition. |
| // RESOLVE (mmm) - "compile" this. |
| scan_position = new BTreeRowPosition(this); |
| |
| scan_position.init(); |
| |
| scan_position.current_lock_template = |
| new DataValueDescriptor[this.init_template.length]; |
| |
| scan_position.current_lock_template[this.init_template.length - 1] = |
| scan_position.current_lock_row_loc = (RowLocation) |
| init_template[init_template.length - 1].cloneValue(false); |
| |
| // Verify that all columns in start key value, stop key value, and |
| // qualifiers are present in the list of columns described by the |
| // scanColumnList. |
| if (SanityManager.DEBUG) |
| { |
| if (init_scanColumnList != null) |
| { |
| // verify that all columns specified in qualifiers, start |
| // and stop positions are specified in the scanColumnList. |
| |
| FormatableBitSet required_cols; |
| |
| if (qualifier != null) |
| required_cols = RowUtil.getQualifierBitSet(qualifier); |
| else |
| required_cols = new FormatableBitSet(0); |
| |
| // add in start columns |
| if (this.init_startKeyValue != null) |
| { |
| required_cols.grow(this.init_startKeyValue.length); |
| for (int i = 0; i < this.init_startKeyValue.length; i++) |
| required_cols.set(i); |
| } |
| |
| if (this.init_stopKeyValue != null) |
| { |
| required_cols.grow(this.init_stopKeyValue.length); |
| for (int i = 0; i < this.init_stopKeyValue.length; i++) |
| required_cols.set(i); |
| } |
| |
| FormatableBitSet required_cols_and_scan_list = |
| (FormatableBitSet) required_cols.clone(); |
| |
| required_cols_and_scan_list.and(init_scanColumnList); |
| |
| // FormatableBitSet equals requires the two FormatableBitSets to be of same |
| // length. |
| required_cols.grow(init_scanColumnList.size()); |
| |
| if (!required_cols_and_scan_list.equals(required_cols)) |
| { |
| SanityManager.THROWASSERT( |
| "Some column specified in a Btree " + |
| " qualifier/start/stop list is " + |
| "not represented in the scanColumnList." + |
| "\n:required_cols_and_scan_list = " + |
| required_cols_and_scan_list + |
| "\n;required_cols = " + required_cols + |
| "\n;init_scanColumnList = " + init_scanColumnList); |
| } |
| } |
| } |
| } |
| |
| /** |
| * Position scan at "start" position for a forward scan. |
| * <p> |
| * Positions the scan to the slot just before the first record to be |
| * returned from the scan. Returns the start page latched, and |
| * sets "current_slot" to the slot number. |
| * <p> |
| * |
| * @exception StandardException Standard exception policy. |
| **/ |
| protected void positionAtStartForForwardScan( |
| BTreeRowPosition pos) |
| throws StandardException |
| { |
| boolean exact; |
| |
| // This routine should only be called from first next() call // |
| if (SanityManager.DEBUG) |
| { |
| SanityManager.ASSERT( |
| (scan_state == SCAN_INIT) || (scan_state == SCAN_HOLD_INIT)); |
| SanityManager.ASSERT(pos.current_rh == null); |
| SanityManager.ASSERT(pos.current_positionKey == null); |
| } |
| |
| // Loop until you can lock the row previous to the first row to be |
| // returned by the scan, while holding the page latched, without |
| // waiting. If you have to wait, drop the latch, wait for the lock - |
| // which makes it likely if you wait for the lock you will loop just |
| // once, find the same lock satisfies the search and since you already |
| // have the lock it will be granted. |
| while (true) |
| { |
| // Find the starting page and row slot, must start at root and |
| // search either for leftmost leaf, or search for specific key. |
| ControlRow root = ControlRow.get(this, BTree.ROOTPAGEID); |
| |
| // include search of tree in page visited stats. |
| stat_numpages_visited += root.getLevel() + 1; |
| |
| boolean need_previous_lock = true; |
| |
| if (init_startKeyValue == null) |
| { |
| // No start given, so position at 0 slot of leftmost leaf page |
| pos.current_leaf = (LeafControlRow) root.searchLeft(this); |
| |
| pos.current_slot = ControlRow.CR_SLOT; |
| exact = false; |
| } |
| else |
| { |
| // Search for the starting row. |
| |
| if (SanityManager.DEBUG) |
| SanityManager.ASSERT( |
| (init_startSearchOperator == ScanController.GE) || |
| (init_startSearchOperator == ScanController.GT)); |
| |
| SearchParameters sp = new SearchParameters( |
| init_startKeyValue, |
| ((init_startSearchOperator == ScanController.GE) ? |
| SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH : |
| SearchParameters.POSITION_RIGHT_OF_PARTIAL_KEY_MATCH), |
| init_template, this, false); |
| |
| pos.current_leaf = (LeafControlRow) root.search(sp); |
| |
| pos.current_slot = sp.resultSlot; |
| exact = sp.resultExact; |
| |
| // The way that scans are used, the caller calls next() |
| // to position on the first row. If the result of the |
| // search that found the starting page and slot was not |
| // exact, then the page/slot will refer to the row before |
| // the first qualifying row. The first call to next() |
| // will therefore move to the first (potentially) qualifying |
| // row. However, if the search was exact, then we don't |
| // want to move the position on the first call to next. |
| // In that case, by decrementing the slot, the first call |
| // to next will put us back on the starting row. |
| |
| if (exact && init_startSearchOperator == ScanController.GE) |
| { |
| pos.current_slot--; |
| |
| // A scan on a unique index, with a start position of |
| // GE, need not get a previous key lock to protect the |
| // range. Since it is unique no other key can go before |
| // the first row returned from the scan. |
| // |
| // RESOLVE - currently btree's only support allowDuplicates |
| // of "false", so no need to do the extra check, current |
| // btree implementation depends on RowLocation field |
| // making every key unique (duplicate indexes are supported |
| // by the nUniqueColumns and nKeyFields). |
| if (getConglomerate().nUniqueColumns < getConglomerate().nKeyFields) |
| { |
| // this implies unique index, thus no prev key. |
| need_previous_lock = false; |
| } |
| } |
| } |
| |
| boolean latch_released = false; |
| if (need_previous_lock) |
| { |
| latch_released = |
| !this.getLockingPolicy().lockScanRow( |
| this, pos, |
| init_lock_fetch_desc, |
| pos.current_lock_template, |
| pos.current_lock_row_loc, |
| true, init_forUpdate, |
| lock_operation); |
| } |
| |
| // special test to see if latch release code works |
| if (SanityManager.DEBUG) |
| { |
| latch_released = |
| test_errors( |
| this, |
| "BTreeScan_positionAtStartPosition", |
| null, // no need to save the position, since we'll |
| // retry the operation if the latch is released |
| this.getLockingPolicy(), |
| pos.current_leaf, latch_released); |
| } |
| |
| if (latch_released) |
| { |
| // lost latch on pos.current_leaf, search the tree again. |
| // Forget the current position since we'll use the start key |
| // to reposition on the start of the scan. |
| pos.init(); |
| continue; |
| } |
| else |
| { |
| // success! got all the locks, while holding the latch. |
| break; |
| } |
| } |
| |
| this.scan_state = SCAN_INPROGRESS; |
| |
| if (SanityManager.DEBUG) |
| SanityManager.ASSERT(pos.current_leaf != null); |
| } |
| |
| /** |
| * Position scan to 0 slot on next page. |
| * <p> |
| * Position to next page, keeping latch on previous page until we have |
| * latch on next page. This routine releases the latch on current_page |
| * once it has successfully gotten the latch on the next page. |
| * |
| * @param pos current row position of the scan. |
| * |
| * @exception StandardException Standard exception policy. |
| **/ |
| protected void positionAtNextPage( |
| BTreeRowPosition pos) |
| throws StandardException |
| { |
| |
| pos.next_leaf = (LeafControlRow) pos.current_leaf.getRightSibling(this); |
| |
| // Now that we either have the latch on next leaf, or there is no next |
| // leaf, we can release the latch on the current page. |
| |
| // unlock the previous row if doing read. |
| if (pos.current_rh != null) |
| { |
| this.getLockingPolicy().unlockScanRecordAfterRead( |
| pos, init_forUpdate); |
| } |
| |
| pos.current_leaf.release(); |
| pos.current_leaf = pos.next_leaf; |
| |
| // set up for scan to continue at beginning of next page. |
| pos.current_slot = Page.FIRST_SLOT_NUMBER; |
| pos.current_rh = null; |
| } |
| |
| /** |
| * <p> |
| * Position the scan after the last row on the previous page. Hold the |
| * latch on the current page until the previous page has been latched. If |
| * the immediate left sibling is empty, move further until a non-empty page |
| * is found or there are no more leaves to be found. The latch on the |
| * current page will be held until a non-empty left sibling page is found. |
| * </p> |
| * |
| * <p> |
| * This method never waits for a latch, as waiting for latches while |
| * holding another latch is only allowed when moving forward in the B-tree. |
| * Waiting while moving backward may result in deadlocks with scanners |
| * going forward. A {@code WaitError} is thrown if the previous page cannot |
| * be latched without waiting. {@code scan_position.current_leaf} will |
| * point to the same page as before the method was called in the case where |
| * a {@code WaitError} is thrown, and the page will still be latched. |
| * </p> |
| * |
| * @throws StandardException standard exception policy |
| * @throws WaitError if the previous page cannot be latched immediately |
| */ |
| protected void positionAtPreviousPage() |
| throws StandardException, WaitError { |
| BTreeRowPosition pos = scan_position; |
| |
| LeafControlRow leaf = |
| (LeafControlRow) pos.current_leaf.getLeftSibling(this); |
| |
| // Skip empty leaves. We don't want to stop on empty pages while |
| // moving backwards, since pages with no rows have no keys and we will |
| // need to save the current position by key if we cannot latch a page |
| // immediately. |
| while (leaf != null && isEmpty(leaf.page)) |
| { |
| final LeafControlRow next; |
| try { |
| next = (LeafControlRow) leaf.getLeftSibling(this); |
| } finally { |
| leaf.release(); |
| } |
| |
| // Successfully managed to latch the leaf to the left of the empty |
| // sibling page. Use that leaf instead. |
| leaf = next; |
| } |
| |
| // Now that we either have the latch on the first non-empty leaf to |
| // the left of the current leaf, or we have passed the leftmost leaf, |
| // we can release the latch on the current page. |
| |
| // Unlock the previous row if doing read. |
| if (pos.current_rh != null) |
| { |
| this.getLockingPolicy().unlockScanRecordAfterRead( |
| pos, init_forUpdate); |
| } |
| |
| pos.current_leaf.release(); |
| pos.current_leaf = leaf; |
| |
| // Set up for scan to continue at the end of the page. |
| pos.current_slot = (pos.current_leaf == null) ? |
| Page.INVALID_SLOT_NUMBER : pos.current_leaf.page.recordCount(); |
| pos.current_rh = null; |
| } |
| |
| /** |
| * Check if a B-tree page is empty. The control row, which is always |
| * present, is not counted. |
| * |
| * @param page the B-tree page to check |
| * @return true if the page is empty, false otherwise |
| * @throws StandardException standard exception policy |
| */ |
| static boolean isEmpty(Page page) throws StandardException { |
| // Because of the control row, the page should always have at least |
| // one record. It's empty if that's the only record on the page. |
| if (SanityManager.DEBUG) { |
| SanityManager.ASSERT( |
| page.recordCount() > 0, "Page without control row?"); |
| } |
| return page.recordCount() <= 1; |
| } |
| |
| /** |
| Position scan at "start" position. |
| <p> |
| Positions the scan to the slot just before the first record to be returned |
| from the scan. Returns the start page latched, and sets "current_slot" to |
| the slot number. |
| |
| @exception StandardException Standard exception policy. |
| **/ |
| abstract void positionAtStartPosition( |
| BTreeRowPosition pos) |
| throws StandardException; |
| |
| |
| /** |
| * Do any necessary work to complete the scan. |
| * |
| * @param pos current row position of the scan. |
| * |
| * @exception StandardException Standard exception policy. |
| **/ |
| protected void positionAtDoneScanFromClose( |
| BTreeRowPosition pos) |
| throws StandardException |
| { |
| // call unlockScanRecordAfterRead() before closing, currently |
| // this is only important for releasing RR locks on non-qualified |
| // rows. |
| // |
| // Otherwise the correct behavior happens as part of the close, ie.: |
| // |
| // for READ_UNCOMMITTED there is no lock to release, |
| // for READ_COMMITTED all read locks will be released, |
| // for REPEATABLE_READ or SERIALIZABLE no locks are released. |
| |
| if ((pos.current_rh != null) && !pos.current_rh_qualified) |
| { |
| if (pos.current_leaf == null || pos.current_leaf.page == null) |
| { |
| // If we are being called from a "normal" close then there |
| // will be no latch on current_leaf, get it and do the the |
| // unlock. We may be called sometimes, after an error where |
| // we may have the latch, in this case the transaction is about |
| // to be backed out anyway so don't worry about doing this |
| // unlock (thus why we only do the following code if we |
| // "don't" have lock, ie. pos.current_leaf== null). |
| |
| this.getLockingPolicy().unlockScanRecordAfterRead( |
| pos, init_forUpdate); |
| } |
| } |
| |
| pos.current_slot = Page.INVALID_SLOT_NUMBER; |
| pos.current_rh = null; |
| pos.current_positionKey = null; |
| this.scan_state = SCAN_DONE; |
| |
| return; |
| } |
| |
| /** |
| * Do work necessary to close a scan. |
| * <p> |
| * This routine can only be called "inline" from other btree routines, |
| * as it counts on the state of the pos to be correct. |
| * <p> |
| * Closing a scan from close() must handle long jumps from exceptions |
| * where the state of pos may not be correct. The easiest case is |
| * a lock timeout which has caused us not to have a latch on a page, |
| * but pos still thinks there is a latch. This is the easiest but |
| * other exceptions can also caused the same state at close() time. |
| **/ |
| protected void positionAtDoneScan( |
| BTreeRowPosition pos) |
| throws StandardException |
| { |
| |
| pos.current_slot = Page.INVALID_SLOT_NUMBER; |
| pos.current_rh = null; |
| pos.current_positionKey = null; |
| this.scan_state = SCAN_DONE; |
| |
| return; |
| } |
| |
| |
| /** |
| * process_qualifier - Determine if a row meets all qualifier conditions. |
| * <p> |
| * Check all qualifiers in the qualifier array against row. Return true |
| * if all compares specified by the qualifier array return true, else |
| * return false. |
| * <p> |
| * It is up to caller to make sure qualifier list is non-null. |
| * |
| * @param row The row with the same partial column list as the |
| * row returned by the current scan. |
| * |
| * @exception StandardException Standard exception policy. |
| */ |
| protected boolean process_qualifier( |
| DataValueDescriptor[] row) |
| throws StandardException |
| { |
| boolean row_qualifies = true; |
| Qualifier q; |
| |
| // Process the 2-d qualifier which is structured as follows: |
| // |
| // A two dimensional array is to be used to pass around a AND's and OR's |
| // in conjunctive normal form (CNF). The top slot of the 2 dimensional |
| // array is optimized for the more frequent where no OR's are present. |
| // The first array slot is always a list of AND's to be treated as |
| // described above for single dimensional AND qualifier arrays. The |
| // subsequent slots are to be treated as AND'd arrays or OR's. Thus |
| // the 2 dimensional array qual[][] argument is to be treated as the |
| // following, note if qual.length = 1 then only the first array is |
| // valid and // it is and an array of and clauses: |
| // |
| // (qual[0][0] and qual[0][0] ... and qual[0][qual[0].length - 1]) |
| // and |
| // (qual[1][0] or qual[1][1] ... or qual[1][qual[1].length - 1]) |
| // and |
| // (qual[2][0] or qual[2][1] ... or qual[2][qual[2].length - 1]) |
| // ... |
| // and |
| // (qual[qual.length - 1][0] or qual[1][1] ... or qual[1][2]) |
| |
| // First do the qual[0] which is an array of qualifer terms. |
| |
| if (SanityManager.DEBUG) |
| { |
| // routine should not be called if there is no qualifier |
| SanityManager.ASSERT(this.init_qualifier != null); |
| SanityManager.ASSERT(this.init_qualifier.length > 0); |
| } |
| |
| for (int i = 0; i < this.init_qualifier[0].length; i++) |
| { |
| // process each AND clause |
| |
| row_qualifies = false; |
| |
| // process each OR clause. |
| |
| q = this.init_qualifier[0][i]; |
| |
| // Get the column from the possibly partial row, of the |
| // q.getColumnId()'th column in the full row. |
| DataValueDescriptor columnValue = row[q.getColumnId()]; |
| |
| row_qualifies = |
| columnValue.compare( |
| q.getOperator(), |
| q.getOrderable(), |
| q.getOrderedNulls(), |
| q.getUnknownRV()); |
| |
| if (q.negateCompareResult()) |
| row_qualifies = !row_qualifies; |
| |
| // Once an AND fails the whole Qualification fails - do a return! |
| if (!row_qualifies) |
| return(false); |
| } |
| |
| // all the qual[0] and terms passed, now process the OR clauses |
| |
| for (int and_idx = 1; and_idx < this.init_qualifier.length; and_idx++) |
| { |
| // process each AND clause |
| |
| row_qualifies = false; |
| |
| if (SanityManager.DEBUG) |
| { |
| // Each OR clause must be non-empty. |
| SanityManager.ASSERT(this.init_qualifier[and_idx].length > 0); |
| } |
| |
| for (int or_idx = 0; |
| or_idx < this.init_qualifier[and_idx].length; or_idx++) |
| { |
| // process each OR clause. |
| |
| q = this.init_qualifier[and_idx][or_idx]; |
| |
| // Get the column from the possibly partial row, of the |
| // q.getColumnId()'th column in the full row. |
| DataValueDescriptor columnValue = row[q.getColumnId()]; |
| |
| row_qualifies = |
| columnValue.compare( |
| q.getOperator(), |
| q.getOrderable(), |
| q.getOrderedNulls(), |
| q.getUnknownRV()); |
| |
| if (q.negateCompareResult()) |
| row_qualifies = !row_qualifies; |
| |
| // once one OR qualifies the entire clause is TRUE |
| if (row_qualifies) |
| break; |
| } |
| |
| if (!row_qualifies) |
| break; |
| } |
| |
| return(row_qualifies); |
| } |
| |
| |
| /** |
| * Reposition the scan leaving and reentering the access layer. |
| * <p> |
| * When a scan leaves access it saves the RecordHandle of the record |
| * on the page. There are 2 cases to consider when trying to reposition |
| * the scan when re-entering access: |
| * o ROW has not moved off the page. |
| * If the row has not moved then the RecordHandle we have saved |
| * away is valid, and we just call RawStore to reposition on that |
| * RecordHandle (RawStore takes care of the row moving within |
| * the page). |
| * o ROW has moved off the page. |
| * This can only happen in the case of a btree split. In that |
| * case the splitter will have caused all scans positioned on |
| * this page within the same transaction to save a copy of the |
| * row that the scan was positioned on. Then to reposition the |
| * scan it is necessary to research the tree from the top using |
| * the copy of the row. |
| * |
| * There are a few cases where it is possible that |
| * the key no longer exists in the table. In the case of a scan held |
| * open across commit it is easy to imagine that the row the scan was |
| * positioned on could be deleted and subsequently purged from the table |
| * all before the scan resumes. Also in the case of read uncommitted |
| * the scan holds no lock on the current row, so it could be purged - |
| * in the following scenario for instance: read uncommitted transaction 1 |
| * opens scan and positions on row (1,2), transaction 2 deletes (1,2) and |
| * commits, transaction 1 inserts (1,3) which goes to same page as (1,2) |
| * and is going to cause a split, transaction 1 saves scan position as |
| * key, and then purges row (1, 2), when transaction |
| * 1 resumes scan (1, 2) no longer exists. missing_row_for_key_ok |
| * parameter is added as a sanity check to make sure it ok that |
| * repositioning does not go to same row that we were repositioned on. |
| * |
| * |
| * |
| * @param pos position to set the scan to. |
| * |
| * @param missing_row_for_key_ok if true and exact key is not found then |
| * scan is just set to key just left of |
| * the key (thus a next will move to the |
| * key just after "pos") |
| * |
| * @return returns true if scan has been repositioned successfully, else |
| * returns false if the position key could not be found and |
| * missing_row_for_key_ok was false indicating that scan could |
| * only be positioned on the exact key match. |
| * |
| * @exception StandardException Standard exception policy. |
| **/ |
| protected boolean reposition( |
| BTreeRowPosition pos, |
| boolean missing_row_for_key_ok) |
| throws StandardException |
| { |
| // RESOLVE (mikem) - performance - we need to do a buffer manager |
| // get for every row returned from the scan. It may be better to |
| // allow a reference to the page with no latch (ie. a fixed bit). |
| |
| if (this.scan_state != SCAN_INPROGRESS) |
| { |
| throw StandardException.newException( |
| SQLState.BTREE_SCAN_NOT_POSITIONED, |
| this.scan_state); |
| } |
| |
| // positionKey is always valid |
| if (SanityManager.DEBUG) |
| { |
| if (pos.current_positionKey == null) |
| SanityManager.THROWASSERT( |
| "pos.current_rh = (" + pos.current_rh + "), " + |
| "pos.current_positionKey = (" + |
| pos.current_positionKey + ")."); |
| } |
| |
| if (pos.current_positionKey == null) |
| { |
| throw StandardException.newException( |
| SQLState.BTREE_SCAN_INTERNAL_ERROR, |
| (pos.current_rh == null), |
| (pos.current_positionKey == null)); |
| } |
| |
| // If current_rh is non-null, we know the exact physical position of |
| // the scan before the latch on the leaf was released. Check if the |
| // row is still on that position so that we don't need to renavigate |
| // from the root of the B-tree in the common case. |
| if (pos.current_rh != null) |
| { |
| // Reposition to remembered spot on page. |
| |
| // Get the page object. If getPage() returns null, the page is |
| // not valid (could for instance have been removed by compress |
| // table) so we need to reposition by key instead. |
| Page page = container.getPage(pos.current_rh.getPageNumber()); |
| if (page != null) { |
| ControlRow row = |
| ControlRow.getControlRowForPage(container, page); |
| if (row instanceof LeafControlRow && |
| !row.page.isRepositionNeeded(pos.versionWhenSaved)) { |
| // No rows have been moved off the page after we released |
| // the latch, and the page is still a leaf page. No need |
| // to reposition by key. |
| pos.current_leaf = (LeafControlRow) row; |
| pos.current_slot = row.page.getSlotNumber(pos.current_rh); |
| pos.current_positionKey = null; |
| return true; |
| } |
| // We couldn't use the position specified by current_rh, so we |
| // need to reposition by key and may find the row on another |
| // page. Therefore, give up the latch on this page. |
| row.release(); |
| } |
| } |
| |
| SearchParameters sp = |
| new SearchParameters( |
| pos.current_positionKey, |
| // this is a full key search, so this arg is not used. |
| SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH, |
| init_template, this, false); |
| |
| pos.current_leaf = (LeafControlRow) |
| ControlRow.get(this, BTree.ROOTPAGEID).search(sp); |
| |
| if (!sp.resultExact && !missing_row_for_key_ok) |
| { |
| // Did not find key to exactly position on. |
| |
| pos.current_leaf.release(); |
| pos.current_leaf = null; |
| return (false); |
| } |
| |
| pos.current_slot = sp.resultSlot; |
| |
| // Need to update current_rh to the new position. current_rh should |
| // only be non-null if the row was locked when the position was saved, |
| // so we don't set it here if its old value is null. |
| if (pos.current_rh != null) { |
| pos.current_rh = pos.current_leaf.page. |
| getRecordHandleAtSlot(pos.current_slot); |
| } |
| |
| pos.current_positionKey = null; |
| |
| return(true); |
| } |
| |
| /* |
| ** Public Methods of BTreeScan |
| */ |
| |
| |
| /** |
| Initialize the scan for use. |
| <p> |
| Any changes to this method may have to be reflected in close as well. |
| <p> |
| The btree init opens the container (super.init), and stores away the |
| state of the qualifiers. The actual searching for the first position |
| is delayed until the first next() call. |
| |
| @exception StandardException Standard exception policy. |
| **/ |
| public void init( |
| TransactionManager xact_manager, |
| Transaction rawtran, |
| boolean hold, |
| int open_mode, |
| int lock_level, |
| BTreeLockingPolicy btree_locking_policy, |
| FormatableBitSet scanColumnList, |
| DataValueDescriptor[] startKeyValue, |
| int startSearchOperator, |
| Qualifier qualifier[][], |
| DataValueDescriptor[] stopKeyValue, |
| int stopSearchOperator, |
| BTree conglomerate, |
| LogicalUndo undo, |
| StaticCompiledOpenConglomInfo static_info, |
| DynamicCompiledOpenConglomInfo dynamic_info) |
| throws StandardException |
| { |
| super.init( |
| xact_manager, xact_manager, (ContainerHandle) null, rawtran, |
| hold, |
| open_mode, lock_level, btree_locking_policy, |
| conglomerate, undo, dynamic_info); |
| |
| |
| this.init_rawtran = rawtran; |
| this.init_forUpdate = |
| ((open_mode & ContainerHandle.MODE_FORUPDATE) == |
| ContainerHandle.MODE_FORUPDATE); |
| |
| // Keep track of whether this scan should use update locks. |
| this.init_useUpdateLocks = |
| ((open_mode & |
| ContainerHandle.MODE_USE_UPDATE_LOCKS) != 0); |
| |
| this.init_hold = hold; |
| |
| this.init_template = |
| runtime_mem.get_template(getRawTran()); |
| |
| this.init_scanColumnList = scanColumnList; |
| |
| this.init_lock_fetch_desc = |
| RowUtil.getFetchDescriptorConstant(init_template.length - 1); |
| |
| if (SanityManager.DEBUG) |
| { |
| SanityManager.ASSERT( |
| init_lock_fetch_desc.getMaxFetchColumnId() == |
| (init_template.length - 1)); |
| SanityManager.ASSERT( |
| (init_lock_fetch_desc.getValidColumnsArray())[init_template.length - 1] == 1); |
| } |
| |
| // note that we don't process qualifiers in btree fetch's |
| this.init_fetchDesc = |
| new FetchDescriptor( |
| init_template.length, init_scanColumnList,(Qualifier[][]) null); |
| |
| initScanParams( |
| startKeyValue, startSearchOperator, |
| qualifier, stopKeyValue, stopSearchOperator); |
| |
| |
| if (SanityManager.DEBUG) |
| { |
| SanityManager.ASSERT( |
| TemplateRow.checkColumnTypes( |
| getRawTran().getDataValueFactory(), |
| this.getConglomerate().format_ids, |
| this.getConglomerate().collation_ids, |
| init_template)); |
| } |
| |
| // System.out.println("initializing scan:" + this); |
| |
| // initialize default locking operation for the scan. |
| this.lock_operation = |
| (init_forUpdate ? |
| ConglomerateController.LOCK_UPD : |
| ConglomerateController.LOCK_READ); |
| |
| if (init_useUpdateLocks) |
| this.lock_operation |= ConglomerateController.LOCK_UPDATE_LOCKS; |
| |
| // System.out.println("Btree scan: " + this); |
| } |
| |
| |
| |
| /* |
| ** Methods of ScanController |
| */ |
| |
| /** |
| Close the scan. |
| **/ |
| public void close() |
| throws StandardException |
| { |
| // Scan is closed, make sure no access to any state variables |
| positionAtDoneScanFromClose(scan_position); |
| |
| super.close(); |
| |
| // null out so that these object's can get GC'd earlier. |
| this.init_rawtran = null; |
| this.init_template = null; |
| this.init_startKeyValue = null; |
| this.init_qualifier = null; |
| this.init_stopKeyValue = null; |
| |
| this.getXactMgr().closeMe(this); |
| } |
| |
| /** |
| Delete the row at the current position of the scan. |
| @see ScanController#delete |
| |
| @exception StandardException Standard exception policy. |
| **/ |
| public boolean delete() |
| throws StandardException |
| { |
| boolean ret_val = false; |
| |
| if (scan_state != SCAN_INPROGRESS) |
| throw StandardException.newException( |
| SQLState.AM_SCAN_NOT_POSITIONED); |
| |
| if (SanityManager.DEBUG) |
| { |
| SanityManager.ASSERT(this.container != null, |
| "BTreeScan.delete() called on a closed scan."); |
| SanityManager.ASSERT(init_forUpdate); |
| } |
| |
| try |
| { |
| // Get current page of scan, with latch. |
| if (!reposition(scan_position, false)) |
| { |
| throw StandardException.newException( |
| SQLState.AM_RECORD_NOT_FOUND, |
| err_containerid, |
| scan_position.current_rh.getPageNumber(), |
| scan_position.current_rh.getId()); |
| } |
| |
| |
| if (init_useUpdateLocks) |
| { |
| // RESOLVE (mikem) - I don't think lockScanRow() is the right |
| // thing to call. |
| |
| // if we are doing update locking, then we got an U lock on |
| // this row when the scan positioned on it, but now that we |
| // are doing a delete on the current position we need to upgrade |
| // the lock to X. |
| boolean latch_released = |
| !this.getLockingPolicy().lockScanRow( |
| this, scan_position, |
| init_lock_fetch_desc, |
| scan_position.current_lock_template, |
| scan_position.current_lock_row_loc, |
| false, init_forUpdate, lock_operation); |
| |
| // Special test to see if latch release code works. |
| if (SanityManager.DEBUG) |
| { |
| latch_released = test_errors( |
| this, "BTreeScan_delete_useUpdateLocks", |
| scan_position, getLockingPolicy(), |
| scan_position.current_leaf, latch_released); |
| } |
| |
| if (latch_released) |
| { |
| // lost latch on page in order to wait for row lock. |
| // reposition() will take care of the complexity of |
| // positioning on the correct page if the row has been |
| // moved to another page. |
| if (!reposition(scan_position, false)) |
| { |
| throw StandardException.newException( |
| SQLState.AM_RECORD_NOT_FOUND, |
| err_containerid, |
| scan_position.current_rh.getPageNumber(), |
| scan_position.current_rh.getId()); |
| } |
| } |
| } |
| |
| if (SanityManager.DEBUG) |
| { |
| // DERBY-2197: Assume no row locking here. If locking policy |
| // requires row locking, we would need to obtain a row lock at |
| // this point. |
| SanityManager.ASSERT( |
| (container.getLockingPolicy().getMode() != |
| LockingPolicy.MODE_RECORD), |
| "Locking policy requires row locking."); |
| } |
| |
| if (scan_position.current_leaf.page.isDeletedAtSlot( |
| scan_position.current_slot)) |
| { |
| ret_val = false; |
| } |
| else |
| { |
| scan_position.current_leaf.page.deleteAtSlot( |
| scan_position.current_slot, true, this.btree_undo); |
| ret_val = true; |
| } |
| |
| // See if we just deleted the last row on the page, in a btree a |
| // page with all rows still has 1 left - the control row. |
| // Do not reclaim the root page of the btree if there are no |
| // children since we were doing too many post commit actions in a |
| // benchmark which does an insert/commit/delete/commit operations |
| // in a single user system. Now with this change the work will |
| // move to the user thread which does the insert and finds no space |
| // on the root page. In that case it will try a split, which |
| // automatically first checks if there is committed deleted space |
| // that can be reclaimed. |
| |
| if (scan_position.current_leaf.page.nonDeletedRecordCount() == 1 && |
| !(scan_position.current_leaf.getIsRoot() && |
| scan_position.current_leaf.getLevel() == 0)) |
| { |
| this.getXactMgr().addPostCommitWork(new BTreePostCommit( |
| this.getXactMgr().getAccessManager(), |
| this.getConglomerate(), |
| scan_position.current_leaf.page.getPageNumber())); |
| } |
| } |
| finally |
| { |
| if (scan_position.current_leaf != null) |
| { |
| // release latch on page |
| savePositionAndReleasePage(); |
| } |
| } |
| |
| return(ret_val); |
| } |
| |
| /** |
| * A call to allow client to indicate that current row does not qualify. |
| * <p> |
| * Indicates to the ScanController that the current row does not |
| * qualify for the scan. If the isolation level of the scan allows, |
| * this may result in the scan releasing the lock on this row. |
| * <p> |
| * Note that some scan implimentations may not support releasing locks on |
| * non-qualifying rows, or may delay releasing the lock until sometime |
| * later in the scan (ie. it may be necessary to keep the lock until |
| * either the scan is repositioned on the next row or page). |
| * <p> |
| * This call should only be made while the scan is positioned on a current |
| * valid row. |
| * |
| * @exception StandardException Standard exception policy. |
| **/ |
| public void didNotQualify() |
| throws StandardException |
| { |
| } |
| |
| |
| /** |
| * Returns true if the current position of the scan still qualifies |
| * under the set of qualifiers passed to the openScan(). When called |
| * this routine will reapply all qualifiers against the row currently |
| * positioned and return true if the row still qualifies. If the row |
| * has been deleted or no longer passes the qualifiers then this routine |
| * will return false. |
| * <p> |
| * This case can come about if the current scan |
| * or another scan on the same table in the same transaction |
| * deleted the row or changed columns referenced by the qualifier after |
| * the next() call which positioned the scan at this row. |
| * <p> |
| * Note that for comglomerates which don't support update, like btree's, |
| * there is no need to recheck the qualifiers. |
| * <p> |
| * The results of a fetch() performed on a scan positioned on |
| * a deleted row are undefined. |
| * <p> |
| * @exception StandardException Standard exception policy. |
| **/ |
| public boolean doesCurrentPositionQualify() |
| throws StandardException |
| { |
| if (scan_state != SCAN_INPROGRESS) |
| throw StandardException.newException( |
| SQLState.AM_SCAN_NOT_POSITIONED); |
| |
| if (SanityManager.DEBUG) |
| { |
| SanityManager.ASSERT(this.container != null, |
| "BTreeScan.doesCurrentPositionQualify() called on a closed scan."); |
| } |
| |
| try |
| { |
| // Get current page of scan, with latch |
| if (!reposition(scan_position, false)) |
| { |
| // TODO - write unit test to get here, language always calls |
| // isCurrentPositionDeleted() right before calling this, so |
| // hard to write .sql test to exercise this. |
| |
| // if reposition fails it means the position of the scan |
| // has been purged from the table - for example if this is |
| // a uncommitted read scan and somehow the row was purged |
| // since the last positioning. |
| |
| return(false); |
| } |
| |
| if (SanityManager.DEBUG) |
| { |
| SanityManager.ASSERT( |
| scan_position.current_leaf.page.fetchNumFieldsAtSlot( |
| scan_position.current_slot) > 1); |
| } |
| |
| // Since btree row don't get updated, the only way a current |
| // position may not qualify is if it got deleted. |
| return( |
| !scan_position.current_leaf.page.isDeletedAtSlot( |
| scan_position.current_slot)); |
| } |
| finally |
| { |
| |
| if (scan_position.current_leaf != null) |
| { |
| // release latch on page. |
| savePositionAndReleasePage(); |
| } |
| } |
| } |
| |
| |
| /** |
| * Fetch the row at the current position of the Scan. |
| * |
| * @param row The row into which the value of the current |
| * position in the scan is to be stored. |
| * @param qualify indicates whether the qualifiers should be applied. |
| * |
| * @exception StandardException Standard exception policy. |
| */ |
| private void fetch(DataValueDescriptor[] row, boolean qualify) |
| throws StandardException |
| { |
| if (scan_state != SCAN_INPROGRESS) |
| throw StandardException.newException( |
| SQLState.AM_SCAN_NOT_POSITIONED); |
| if (SanityManager.DEBUG) |
| { |
| SanityManager.ASSERT(this.container != null, |
| "BTreeScan.fetch() called on a closed scan."); |
| } |
| |
| try |
| { |
| // Get current page of scan, with latch |
| if (!reposition(scan_position, false)) |
| { |
| // TODO - write unit test to get here, language always calls |
| // isCurrentPositionDeleted() right before calling this, so |
| // hard to write .sql test to exercise this. |
| |
| throw StandardException.newException( |
| SQLState.AM_RECORD_NOT_FOUND, |
| err_containerid, |
| scan_position.current_rh.getPageNumber(), |
| scan_position.current_rh.getId()); |
| } |
| |
| if (SanityManager.DEBUG) |
| { |
| SanityManager.ASSERT( |
| scan_position.current_leaf.page.fetchNumFieldsAtSlot( |
| scan_position.current_slot) > 1); |
| } |
| |
| scan_position.current_rh = |
| scan_position.current_leaf.page.fetchFromSlot( |
| (RecordHandle) null, |
| scan_position.current_slot, row, |
| qualify ? init_fetchDesc : null, |
| true); |
| |
| // The possibility is that the row at the current position |
| // has been marked as deleted (it cannot have been purged |
| // since the scan maintains a lock on the row, and purges |
| // are always done from system transactions). I'm not sure |
| // what the desired behavior is in this case. For now, |
| // just return null. |
| |
| // RESOLVE (mikem) - what should be done here? |
| if (scan_position.current_leaf.page.isDeletedAtSlot( |
| scan_position.current_slot)) |
| { |
| if (SanityManager.DEBUG) |
| SanityManager.ASSERT(false, "positioned on deleted row"); |
| } |
| } |
| finally |
| { |
| if (scan_position.current_leaf != null) |
| { |
| // release latch on page. |
| savePositionAndReleasePage(); |
| } |
| } |
| |
| return; |
| } |
| |
| /** |
| * @see org.apache.derby.iapi.store.access.ScanController#isHeldAfterCommit |
| */ |
| public boolean isHeldAfterCommit() throws StandardException |
| { |
| return (scan_state == SCAN_HOLD_INIT || |
| scan_state == SCAN_HOLD_INPROGRESS); |
| } |
| |
| /** |
| Fetch the row at the current position of the Scan. |
| @see ScanController#fetch |
| |
| @exception StandardException Standard exception policy. |
| **/ |
| public void fetch(DataValueDescriptor[] row) |
| throws StandardException |
| { |
| fetch(row, true); |
| } |
| |
| /** |
| * Fetch the row at the current position of the Scan without applying the |
| * qualifiers. |
| * @see ScanController#fetchWithoutQualify |
| * |
| * @exception StandardException Standard exception policy. |
| */ |
| public void fetchWithoutQualify(DataValueDescriptor[] row) |
| throws StandardException |
| { |
| fetch(row, false); |
| } |
| |
| /** |
| * Return ScanInfo object which describes performance of scan. |
| * <p> |
| * Return ScanInfo object which contains information about the current |
| * scan. |
| * <p> |
| * |
| * @see ScanInfo |
| * |
| * @return The ScanInfo object which contains info about current scan. |
| * |
| * @exception StandardException Standard exception policy. |
| **/ |
| public ScanInfo getScanInfo() |
| throws StandardException |
| { |
| return(new BTreeScanInfo(this)); |
| } |
| |
| /** |
| Returns true if the current position of the scan is at a |
| deleted row. This case can come about if the current scan |
| or another scan on the same table in the same transaction |
| deleted the row after the next() call which positioned the |
| scan at this row. |
| |
| The results of a fetch() performed on a scan positioned on |
| a deleted row are undefined. |
| |
| @exception StandardException Standard exception policy. |
| **/ |
| public boolean isCurrentPositionDeleted() |
| throws StandardException |
| { |
| boolean ret_val; |
| |
| if (scan_state != SCAN_INPROGRESS) |
| throw StandardException.newException( |
| SQLState.AM_SCAN_NOT_POSITIONED); |
| |
| if (SanityManager.DEBUG) |
| { |
| SanityManager.ASSERT(this.container != null, |
| "BTreeScan.isCurrentPositionDeleted() called on closed scan."); |
| } |
| try |
| { |
| // Get current page of scan, with latch |
| |
| if (reposition(scan_position, false)) |
| { |
| |
| if (SanityManager.DEBUG) |
| { |
| SanityManager.ASSERT( |
| scan_position.current_leaf.page.fetchNumFieldsAtSlot( |
| scan_position.current_slot) > 1); |
| } |
| |
| ret_val = |
| scan_position.current_leaf.page.isDeletedAtSlot( |
| scan_position.current_slot); |
| } |
| else |
| { |
| ret_val = false; |
| } |
| } |
| finally |
| { |
| if (scan_position.current_leaf != null) |
| { |
| // release latch on page. |
| savePositionAndReleasePage(); |
| } |
| } |
| |
| return(ret_val); |
| } |
| |
| /** |
| * Return whether this is a keyed conglomerate. |
| * <p> |
| * |
| * @return whether this is a keyed conglomerate. |
| **/ |
| public boolean isKeyed() |
| { |
| return(true); |
| } |
| |
| /** |
| * @see ScanController#positionAtRowLocation |
| * |
| * Not implemented for this class |
| */ |
| public boolean positionAtRowLocation (RowLocation rLoc) |
| throws StandardException |
| { |
| throw StandardException.newException( |
| SQLState.BTREE_UNIMPLEMENTED_FEATURE); |
| } |
| |
| /** |
| Move to the next position in the scan. |
| @see ScanController#next |
| |
| @exception StandardException Standard exception policy. |
| **/ |
| public boolean next() |
| throws StandardException |
| { |
| // Turn this call into a group fetch of a 1 element group. |
| fetchNext_one_slot_array[0] = runtime_mem.get_scratch_row(getRawTran()); |
| boolean ret_val = |
| fetchRows( |
| scan_position, |
| fetchNext_one_slot_array, |
| (RowLocation[]) null, |
| (BackingStoreHashtable) null, |
| 1, |
| (int[]) null) == 1; |
| |
| |
| return(ret_val); |
| } |
| |
| /** |
| Fetch the row at the next position of the Scan. |
| |
| If there is a valid next position in the scan then |
| the value in the template storable row is replaced |
| with the value of the row at the current scan |
| position. The columns of the template row must |
| be of the same type as the actual columns in the |
| underlying conglomerate. |
| |
| The resulting contents of templateRow after a fetchNext() |
| which returns false is undefined. |
| |
| The result of calling fetchNext(row) is exactly logically |
| equivalent to making a next() call followed by a fetch(row) |
| call. This interface allows implementations to optimize |
| the 2 calls if possible. |
| |
| @param row The template row into which the value |
| of the next position in the scan is to be stored. |
| |
| @return True if there is a next position in the scan, |
| false if there isn't. |
| |
| @exception StandardException Standard exception policy. |
| **/ |
| public boolean fetchNext(DataValueDescriptor[] row) |
| throws StandardException |
| { |
| boolean ret_val; |
| |
| // Turn this call into a group fetch of a 1 element group. |
| fetchNext_one_slot_array[0] = row; |
| ret_val = |
| fetchRows( |
| scan_position, |
| fetchNext_one_slot_array, |
| (RowLocation[]) null, |
| (BackingStoreHashtable) null, |
| 1, |
| (int[]) null) == 1; |
| |
| return(ret_val); |
| } |
| |
| /** |
| * Fetch the next N rows from the table. |
| * <p> |
| * The client allocates an array of N rows and passes it into the |
| * fetchNextSet() call. This routine does the equivalent of N |
| * fetchNext() calls, filling in each of the rows in the array. |
| * Locking is performed exactly as if the N fetchNext() calls had |
| * been made. |
| * <p> |
| * It is up to Access how many rows to return. fetchNextSet() will |
| * return how many rows were filled in. If fetchNextSet() returns 0 |
| * then the scan is complete, (ie. the scan is in the same state as if |
| * fetchNext() had returned false). If the scan is not complete then |
| * fetchNext() will return (1 <= row_count <= N). |
| * <p> |
| * The current position of the scan is undefined if fetchNextSet() |
| * is used (ie. mixing fetch()/fetchNext() and fetchNextSet() calls |
| * in a single scan does not work). This is because a fetchNextSet() |
| * request for 5 rows from a heap where the first 2 rows qualify, but |
| * no other rows qualify will result in the scan being positioned at |
| * the end of the table, while if 5 rows did qualify the scan will be |
| * positioned on the 5th row. |
| * <p> |
| * Qualifiers, start and stop positioning of the openscan are applied |
| * just as in a normal scan. |
| * <p> |
| * The columns of the row will be the standard columns returned as |
| * part of a scan, as described by the validColumns - see openScan for |
| * description. |
| * <p> |
| * Expected usage: |
| * |
| * // allocate an array of 5 empty row templates |
| * DataValueDescriptor[][] row_array = allocate_row_array(5); |
| * int row_cnt = 0; |
| * |
| * scan = openScan(); |
| * |
| * while ((row_cnt = scan.fetchNextSet(row_array) != 0) |
| * { |
| * // I got "row_cnt" rows from the scan. These rows will be |
| * // found in row_array[0] through row_array[row_cnt - 1] |
| * } |
| * |
| * <p> |
| * |
| * RESOLVE - This interface is being provided so that we can prototype |
| * the performance results it can achieve. If it looks like |
| * this interface is useful, it is very likely we will look |
| * into a better way to tie together the now 4 different |
| * fetch interfaces: fetch, fetchNext(), fetchNextGroup(), |
| * and fetchSet(). |
| * |
| * @return The number of qualifying rows found and copied into the |
| * provided array of rows. If 0 then the scan is complete, |
| * otherwise the return value will be: |
| * 1 <= row_count <= row_array.length |
| * |
| * @param row_array The array of rows to copy rows into. |
| * row_array[].length must >= 1. This routine |
| * assumes that all entries in the array |
| * contain complete template rows. |
| * |
| * @exception StandardException Standard exception policy. |
| **/ |
| public int fetchNextGroup( |
| DataValueDescriptor[][] row_array, |
| RowLocation[] rowloc_array) |
| throws StandardException |
| { |
| return( |
| fetchRows( |
| scan_position, |
| row_array, |
| rowloc_array, |
| (BackingStoreHashtable) null, |
| row_array.length, |
| (int[]) null)); |
| } |
| |
| public int fetchNextGroup( |
| DataValueDescriptor[][] row_array, |
| RowLocation[] old_rowloc_array, |
| RowLocation[] new_rowloc_array) |
| throws StandardException |
| { |
| // This interface is currently only used to move rows around in |
| // a heap table, unused in btree's -- so not implemented. |
| |
| throw StandardException.newException( |
| SQLState.BTREE_UNIMPLEMENTED_FEATURE); |
| } |
| |
| /** |
| * Insert all rows that qualify for the current scan into the input |
| * Hash table. |
| * <p> |
| * This routine scans executes the entire scan as described in the |
| * openScan call. For every qualifying unique row value an entry is |
| * placed into the HashTable. For unique row values the entry in the |
| * BackingStoreHashtable has a key value of the object stored in |
| * row[key_column_number], and the value of the data is row. For row |
| * values with duplicates, the key value is also row[key_column_number], |
| * but the value of the data is a Vector of |
| * rows. The caller will have to call "instanceof" on the data value |
| * object if duplicates are expected, to determine if the data value |
| * of the Hashtable entry is a row or is a Vector of rows. |
| * <p> |
| * Note, that for this routine to work efficiently the caller must |
| * ensure that the object in row[key_column_number] implements |
| * the hashCode and equals method as appropriate for it's datatype. |
| * <p> |
| * It is expected that this call will be the first and only call made in |
| * an openscan. Qualifiers and stop position of the openscan are applied |
| * just as in a normal scan. This call is logically equivalent to the |
| * caller performing the following: |
| * |
| * import java.util.Hashtable; |
| * |
| * hash_table = new Hashtable(); |
| * |
| * while (next()) |
| * { |
| * row = create_new_row(); |
| * fetch(row); |
| * if ((duplicate_value = |
| * hash_table.put(row[key_column_number], row)) != null) |
| * { |
| * Vector row_vec; |
| * |
| * // inserted a duplicate |
| * if ((duplicate_value instanceof vector)) |
| * { |
| * row_vec = (Vector) duplicate_value; |
| * } |
| * else |
| * { |
| * // allocate vector to hold duplicates |
| * row_vec = new Vector(2); |
| * |
| * // insert original row into vector |
| * row_vec.addElement(duplicate_value); |
| * |
| * // put the vector as the data rather than the row |
| * hash_table.put(row[key_column_number], row_vec); |
| * } |
| * |
| * // insert new row into vector |
| * row_vec.addElement(row); |
| * } |
| * } |
| * <p> |
| * The columns of the row will be the standard columns returned as |
| * part of a scan, as described by the validColumns - see openScan for |
| * description. |
| * RESOLVE - is this ok? or should I hard code somehow the row to |
| * be the first column and the row location? |
| * <p> |
| * Currently it is only possible to hash on the first column in the |
| * conglomerate, in the future we may change the interface to allow |
| * hashing either on a different column or maybe on a combination of |
| * columns. |
| * <p> |
| * No overflow to external storage is provided, so calling this routine |
| * on a 1 gigabyte conglomerate will incur at least 1 gigabyte of memory |
| * (probably failing with a java out of memory condition). If this |
| * routine gets an out of memory condition, or if "max_rowcnt" is |
| * exceeded then then the routine will give up, empty the Hashtable, |
| * and return "false." |
| * <p> |
| * On exit from this routine, whether the fetchSet() succeeded or not |
| * the scan is complete, it is positioned just the same as if the scan |
| * had been drained by calling "next()" until it returns false (ie. |
| * fetchNext() and next() calls will return false). |
| * reopenScan() can be called to restart the scan. |
| * <p> |
| * |
| * RESOLVE - until we get row counts what should we do for sizing the |
| * the size, capasity, and load factor of the hash table. |
| * For now it is up to the caller to create the Hashtable, |
| * Access does not reset any parameters. |
| * <p> |
| * RESOLVE - I am not sure if access should be in charge of allocating |
| * the new row objects. I know that I can do this in the |
| * case of btree's, but I don't think I can do this in heaps. |
| * Maybe this is solved by work to be done on the sort |
| * interface. |
| * |
| * |
| * @param max_rowcnt The maximum number of rows to insert into the |
| * Hash table. Pass in -1 if there is no maximum. |
| * @param key_column_numbers The column numbers of the columns in the |
| * scan result row to be the key to the Hashtable. |
| * "0" is the first column in the scan result |
| * row (which may be different than the first |
| * column in the row in the table of the scan). |
| * @param hash_table The java HashTable to load into. |
| * |
| * @exception StandardException Standard exception policy. |
| **/ |
| public void fetchSet( |
| long max_rowcnt, |
| int[] key_column_numbers, |
| BackingStoreHashtable hash_table) |
| throws StandardException |
| { |
| // System.out.println("fetchSet"); |
| |
| fetchRows( |
| scan_position, |
| (DataValueDescriptor[][]) null, |
| (RowLocation[]) null, |
| (BackingStoreHashtable) hash_table, |
| max_rowcnt, |
| key_column_numbers); |
| |
| return; |
| } |
| |
| |
| /** |
| Reposition the current scan. This call is semantically the same as if |
| the current scan had been closed and a openScan() had been called instead. |
| The scan is reopened with against the same conglomerate, and the scan |
| is reopened with the same "hold" and "forUpdate" parameters passed in |
| the original openScan. The previous template row continues to be used. |
| |
| @param startKeyValue An indexable row which holds a |
| (partial) key value which, in combination with the |
| startSearchOperator, defines the starting position of |
| the scan. If null, the starting position of the scan |
| is the first row of the conglomerate. |
| |
| @param startSearchOperator an operator which defines |
| how the startKeyValue is to be searched for. If |
| startSearchOperation is ScanController.GE, the scan starts on |
| the first row which is greater than or equal to the |
| startKeyValue. If startSearchOperation is ScanController.GT, |
| the scan starts on the first row whose key is greater than |
| startKeyValue. The startSearchOperation parameter is |
| ignored if the startKeyValue parameter is null. |
| |
| @param qualifier An array of qualifiers which, applied |
| to each key, restrict the rows returned by the scan. Rows |
| for which any one of the qualifiers returns false are not |
| returned by the scan. If null, all rows are returned. |
| |
| @param stopKeyValue An indexable row which holds a |
| (partial) key value which, in combination with the |
| stopSearchOperator, defines the ending position of |
| the scan. If null, the ending position of the scan |
| is the last row of the conglomerate. |
| |
| @param stopSearchOperator an operator which defines |
| how the stopKeyValue is used to determine the scan stopping |
| position. If stopSearchOperation is ScanController.GE, the scan |
| stops just before the first row which is greater than or |
| equal to the stopKeyValue. If stopSearchOperation is |
| ScanController.GT, the scan stops just before the first row whose |
| key is greater than startKeyValue. The stopSearchOperation |
| parameter is ignored if the stopKeyValue parameter is null. |
| |
| @exception StandardException Standard exception policy. |
| **/ |
| public final void reopenScan( |
| DataValueDescriptor[] startKeyValue, |
| int startSearchOperator, |
| Qualifier qualifier[][], |
| DataValueDescriptor[] stopKeyValue, |
| int stopSearchOperator) |
| throws StandardException |
| { |
| if (SanityManager.DEBUG) |
| { |
| if (!init_hold) |
| SanityManager.ASSERT(this.container != null, |
| "BTreeScan.reopenScan() called on non-held closed scan."); |
| |
| // should only be called by clients outside of store, so should |
| // not be possible for a latch to held. |
| SanityManager.ASSERT(scan_position.current_leaf == null); |
| } |
| |
| // call unlockScanRecordAfterRead() before setting the scan back |
| // to init state, so that we release the last lock if necessary (ie. |
| // for read committed). |
| // |
| |
| if (scan_position.current_rh != null) |
| { |
| this.getLockingPolicy().unlockScanRecordAfterRead( |
| scan_position, init_forUpdate); |
| } |
| |
| scan_position.current_slot = Page.INVALID_SLOT_NUMBER; |
| scan_position.current_rh = null; |
| scan_position.current_positionKey = null; |
| |
| initScanParams( |
| startKeyValue, startSearchOperator, |
| qualifier, stopKeyValue, stopSearchOperator); |
| |
| if (!init_hold) |
| this.scan_state = SCAN_INIT; |
| else |
| this.scan_state = |
| (this.container != null ? SCAN_INIT : SCAN_HOLD_INIT); |
| } |
| |
| /** |
| Reposition the current scan. This call is semantically the same as if |
| the current scan had been closed and a openScan() had been called instead. |
| The scan is reopened against the same conglomerate, and the scan |
| is reopened with the same "scan column list", "hold" and "forUpdate" |
| parameters passed in the original openScan. |
| <p> |
| The statistics gathered by the scan are not reset to 0 by a reopenScan(), |
| rather they continue to accumulate. |
| <p> |
| Note that this operation is currently only supported on Heap conglomerates. |
| Also note that order of rows within are heap are not guaranteed, so for |
| instance positioning at a RowLocation in the "middle" of a heap, then |
| inserting more data, then continuing the scan is not guaranteed to see |
| the new rows - they may be put in the "beginning" of the heap. |
| |
| @param startRowLocation An existing RowLocation within the conglomerate, |
| at which to position the start of the scan. The scan will begin at this |
| location and continue forward until the end of the conglomerate. |
| Positioning at a non-existent RowLocation (ie. an invalid one or one that |
| had been deleted), will result in an exception being thrown when the |
| first next operation is attempted. |
| |
| @param qualifier An array of qualifiers which, applied |
| to each key, restrict the rows returned by the scan. Rows |
| for which any one of the qualifiers returns false are not |
| returned by the scan. If null, all rows are returned. |
| |
| @exception StandardException Standard exception policy. |
| **/ |
| public void reopenScanByRowLocation( |
| RowLocation startRowLocation, |
| Qualifier qualifier[][]) |
| throws StandardException |
| { |
| throw StandardException.newException( |
| SQLState.BTREE_UNIMPLEMENTED_FEATURE); |
| } |
| |
| /* |
| ** Methods of ScanController, which are not supported by btree. |
| */ |
| |
| /** |
| Fetch the location of the current position in the scan. |
| @see ScanController#fetchLocation |
| |
| @exception StandardException Standard exception policy. |
| **/ |
| public void fetchLocation(RowLocation templateLocation) |
| throws StandardException |
| { |
| throw StandardException.newException( |
| SQLState.BTREE_UNIMPLEMENTED_FEATURE); |
| } |
| |
| /** |
| Return a row location object of the correct type to be |
| used in calls to fetchLocation. |
| @see org.apache.derby.iapi.store.access.GenericScanController#newRowLocationTemplate |
| |
| @exception StandardException Standard exception policy. |
| **/ |
| public RowLocation newRowLocationTemplate() |
| throws StandardException |
| { |
| throw StandardException.newException( |
| SQLState.BTREE_UNIMPLEMENTED_FEATURE); |
| } |
| |
| /** |
| Replace the entire row at the current position of the scan. |
| |
| Unimplemented interface by btree, will throw an exception. |
| |
| @see ScanController#replace |
| @exception StandardException Standard exception policy. |
| **/ |
| public boolean replace(DataValueDescriptor[] row, FormatableBitSet validColumns) |
| throws StandardException |
| { |
| throw StandardException.newException( |
| SQLState.BTREE_UNIMPLEMENTED_FEATURE); |
| } |
| |
| /* |
| ** Methods of ScanManager |
| */ |
| |
| |
| /** |
| Close the scan, a commit or abort is about to happen. |
| **/ |
| public boolean closeForEndTransaction(boolean closeHeldScan) |
| throws StandardException |
| { |
| if (!init_hold || closeHeldScan) |
| { |
| // Scan is closed, make sure no access to any state variables |
| positionAtDoneScan(scan_position); |
| |
| super.close(); |
| |
| // null out so that these object's can get GC'd earlier. |
| this.init_rawtran = null; |
| this.init_template = null; |
| this.init_startKeyValue = null; |
| this.init_qualifier = null; |
| this.init_stopKeyValue = null; |
| |
| this.getXactMgr().closeMe(this); |
| |
| return(true); |
| } |
| else |
| { |
| |
| if (this.scan_state == SCAN_INPROGRESS) |
| { |
| if (SanityManager.DEBUG) |
| { |
| SanityManager.ASSERT(scan_position != null); |
| SanityManager.ASSERT( |
| scan_position.current_positionKey != null, |
| "Position must be saved by key when tx ends"); |
| } |
| |
| // When the transaction ends, we release all the locks |
| // obtained in this scan, so the row we're positioned on is |
| // no longer locked. |
| scan_position.current_rh = null; |
| |
| this.scan_state = SCAN_HOLD_INPROGRESS; |
| } |
| else if (this.scan_state == SCAN_INIT) |
| { |
| this.scan_state = SCAN_HOLD_INIT; |
| } |
| |
| super.close(); |
| |
| return(false); |
| } |
| } |
| |
| /** |
| * Save the current scan position by key and release the latch on the leaf |
| * that's being scanned. This method should be called if the latch on a |
| * leaf needs to be released in the middle of the scan. The scan can |
| * later reposition to the saved position by calling {@code reposition()}. |
| * |
| * @param partialKey known parts of the key that should be saved, or |
| * {@code null} if the entire key is unknown and will have to be fetched |
| * from the page |
| * @param vcols an array which tells which columns of the partial key are |
| * valid (key columns that have 0 in this array are not valid, and their |
| * values must be fetched from the page), or {@code null} if all the |
| * columns are valid |
| * @throws StandardException if an error occurs while saving the position |
| * @see #reposition(BTreeRowPosition, boolean) |
| */ |
| void savePositionAndReleasePage(DataValueDescriptor[] partialKey, |
| int[] vcols) |
| throws StandardException { |
| |
| final Page page = scan_position.current_leaf.getPage(); |
| |
| if (SanityManager.DEBUG) { |
| SanityManager.ASSERT(page.isLatched(), "Page is not latched"); |
| SanityManager.ASSERT(scan_position.current_positionKey == null, |
| "Scan position already saved"); |
| |
| if (partialKey == null) { |
| SanityManager.ASSERT(vcols == null); |
| } |
| if (vcols != null) { |
| SanityManager.ASSERT(partialKey != null); |
| SanityManager.ASSERT(vcols.length <= partialKey.length); |
| } |
| } |
| |
| try { |
| DataValueDescriptor[] fullKey = scan_position.getKeyTemplate(); |
| |
| FetchDescriptor fetchDescriptor = null; |
| boolean haveAllColumns = false; |
| if (partialKey != null) { |
| int copiedCols = 0; |
| final int partialKeyLength = |
| (vcols == null) ? partialKey.length : vcols.length; |
| for (int i = 0; i < partialKeyLength; i++) { |
| if (vcols == null || vcols[i] != 0) { |
| fullKey[i].setValue(partialKey[i]); |
| copiedCols++; |
| } |
| } |
| if (copiedCols < fullKey.length) { |
| fetchDescriptor = |
| scan_position.getFetchDescriptorForSaveKey( |
| vcols, fullKey.length); |
| } else { |
| haveAllColumns = true; |
| } |
| } |
| |
| if (!haveAllColumns) { |
| RecordHandle rh = page.fetchFromSlot( |
| (RecordHandle) null, |
| scan_position.current_slot, |
| fullKey, |
| fetchDescriptor, |
| true); |
| |
| if (SanityManager.DEBUG) { |
| SanityManager.ASSERT(rh != null, "Row not found"); |
| } |
| } |
| |
| scan_position.current_positionKey = fullKey; |
| // Don't null out current_rh, we might be able to use it later if |
| // no rows are moved off the page. |
| //scan_position.current_rh = null; |
| scan_position.versionWhenSaved = page.getPageVersion(); |
| scan_position.current_slot = Page.INVALID_SLOT_NUMBER; |
| |
| } finally { |
| scan_position.current_leaf.release(); |
| scan_position.current_leaf = null; |
| } |
| } |
| |
| /** Shortcut for for savePositionAndReleasePage(null,null). */ |
| void savePositionAndReleasePage() throws StandardException { |
| savePositionAndReleasePage(null, null); |
| } |
| |
| public RecordHandle getCurrentRecordHandleForDebugging() |
| { |
| return(scan_position.current_rh); |
| } |
| |
| /* |
| ** Standard toString() method. Prints out current position in scan. |
| */ |
| public String toString() |
| { |
| if (SanityManager.DEBUG) |
| { |
| String string = |
| "\n\tbtree = " + this.getConglomerate() + |
| "\n\tscan direction = " + |
| (this instanceof BTreeForwardScan ? "forward" : |
| (this instanceof BTreeMaxScan ? "backward" : |
| "illegal")) + |
| "\n\t(scan_state:" + |
| (this.scan_state == SCAN_INIT ? "SCAN_INIT" : |
| this.scan_state == SCAN_INPROGRESS ? "SCAN_INPROGRESS" : |
| this.scan_state == SCAN_DONE ? "SCAN_DONE" : |
| this.scan_state == SCAN_HOLD_INIT ? "SCAN_HOLD_INIT" : |
| this.scan_state == SCAN_HOLD_INPROGRESS ? "SCAN_HOLD_INPROGRESS" : |
| "BAD_SCAN_STATE") + |
| "\n\trh:" + scan_position.current_rh + |
| "\n\tkey:" + scan_position.current_positionKey + ")" + |
| "\n\tinit_rawtran = " + init_rawtran + |
| "\n\tinit_hold = " + init_hold + |
| "\n\tinit_forUpdate = " + init_forUpdate + |
| "\n\tinit_useUpdateLocks = " + init_useUpdateLocks + |
| "\n\tinit_scanColumnList = " + init_scanColumnList + |
| "\n\tinit_scanColumnList.size() = "+ ( |
| (init_scanColumnList != null ? |
| init_scanColumnList.size() : 0)) + |
| "\n\tinit_template = " + |
| RowUtil.toString(init_template) + |
| "\n\tinit_startKeyValue = " + |
| RowUtil.toString(init_startKeyValue) + |
| "\n\tinit_startSearchOperator = " + |
| (init_startSearchOperator == ScanController.GE ? "GE" : |
| (init_startSearchOperator == ScanController.GT ? "GT" : |
| Integer.toString(init_startSearchOperator))) + |
| "\n\tinit_qualifier[] = " + init_qualifier + |
| "\n\tinit_stopKeyValue = " + |
| RowUtil.toString(init_stopKeyValue) + |
| "\n\tinit_stopSearchOperator = " + |
| (init_stopSearchOperator == ScanController.GE ? "GE" : |
| (init_stopSearchOperator == ScanController.GT ? "GT" : |
| Integer.toString(init_stopSearchOperator))) + |
| "\n\tstat_numpages_visited = " + |
| stat_numpages_visited + |
| "\n\tstat_numrows_visited = " + |
| stat_numrows_visited + |
| "\n\tstat_numrows_qualified = " + |
| stat_numrows_qualified + |
| "\n\tstat_numdeleted_rows_visited = " + |
| stat_numdeleted_rows_visited ; |
| |
| return(string); |
| } |
| else |
| { |
| return(null); |
| } |
| } |
| } |