--- /dev/null
+/*\r
+\r
+ Derby - Class org.apache.derby.impl.store.access.btree.BTreeMaxScan\r
+\r
+ Licensed to the Apache Software Foundation (ASF) under one or more\r
+ contributor license agreements. See the NOTICE file distributed with\r
+ this work for additional information regarding copyright ownership.\r
+ The ASF licenses this file to you under the Apache License, Version 2.0\r
+ (the "License"); you may not use this file except in compliance with\r
+ the License. You may obtain a copy of the License at\r
+\r
+ http://www.apache.org/licenses/LICENSE-2.0\r
+\r
+ Unless required by applicable law or agreed to in writing, software\r
+ distributed under the License is distributed on an "AS IS" BASIS,\r
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
+ See the License for the specific language governing permissions and\r
+ limitations under the License.\r
+\r
+ */\r
+\r
+package org.apache.derby.impl.store.access.btree;\r
+\r
+import org.apache.derby.iapi.reference.SQLState;\r
+\r
+import org.apache.derby.iapi.services.sanity.SanityManager;\r
+\r
+import org.apache.derby.iapi.error.StandardException; \r
+\r
+import org.apache.derby.iapi.store.access.RowUtil;\r
+import org.apache.derby.iapi.store.access.Qualifier;\r
+import org.apache.derby.iapi.store.access.ScanController;\r
+\r
+import org.apache.derby.iapi.store.raw.FetchDescriptor;\r
+import org.apache.derby.iapi.store.raw.Page;\r
+import org.apache.derby.iapi.store.raw.RecordHandle;\r
+\r
+import org.apache.derby.iapi.types.DataValueDescriptor;\r
+\r
+import org.apache.derby.iapi.types.RowLocation;\r
+\r
+import org.apache.derby.iapi.store.access.BackingStoreHashtable;\r
+\r
+\r
+/**\r
+\r
+ A b-tree scan controller corresponds to an instance of an open b-tree scan.\r
+ <P>\r
+ <B>Concurrency Notes<\B>\r
+ <P>\r
+ The concurrency rules are derived from OpenBTree.\r
+ <P>\r
+ @see OpenBTree\r
+\r
+**/\r
+\r
+/**\r
+\r
+A BTreeScan implementation that provides the 90% solution to the max on\r
+btree problem. If the row is the last row in the btree it works very\r
+efficiently. This implementation will be removed once backward scan is\r
+fully functional.\r
+\r
+**/\r
+\r
+public class BTreeMaxScan extends BTreeScan\r
+{\r
+\r
+ /**************************************************************************\r
+ * Private methods of This class:\r
+ **************************************************************************\r
+ */\r
+\r
+ /**\r
+ * Fetch the maximum non-deleted row from the table.\r
+ *\r
+ * @exception StandardException Standard exception policy.\r
+ **/\r
+ private boolean fetchMaxRowFromBeginning(\r
+ BTreeRowPosition pos,\r
+ DataValueDescriptor[] fetch_row)\r
+ throws StandardException\r
+ {\r
+ int ret_row_count = 0;\r
+ RecordHandle max_rh = null;\r
+\r
+ // we need to scan until we hit the end of the table or until we\r
+ // run into a null. Use this template to probe the "next" row so\r
+ // that if we need to finish, fetch_row will have the right value.\r
+ DataValueDescriptor[] check_row_template = new DataValueDescriptor[1];\r
+ check_row_template[0] = fetch_row[0].getClone();\r
+ FetchDescriptor check_row_desc = RowUtil.getFetchDescriptorConstant(1);\r
+\r
+ // reopen the scan for reading from the beginning of the table.\r
+ reopenScan(\r
+ (DataValueDescriptor[]) null,\r
+ ScanController.NA,\r
+ (Qualifier[][]) null,\r
+ (DataValueDescriptor[]) null,\r
+ ScanController.NA);\r
+\r
+ positionAtStartForForwardScan(pos);\r
+\r
+ // At this point:\r
+ // current_page is latched. current_slot is the slot on current_page\r
+ // just before the "next" record this routine should process.\r
+\r
+ // loop through successive leaf pages and successive slots on those\r
+ // leaf pages. Stop when either the last leaf is reached. At any\r
+ // time in the scan fetch_row will contain "last" non-deleted row\r
+ // seen.\r
+\r
+ boolean nulls_not_reached = true;\r
+ while ((pos.current_leaf != null) && nulls_not_reached)\r
+ {\r
+ while ((pos.current_slot + 1) < pos.current_leaf.page.recordCount())\r
+ {\r
+ // unlock the previous row if doing read.\r
+ if (pos.current_rh != null)\r
+ {\r
+ this.getLockingPolicy().unlockScanRecordAfterRead(\r
+ pos, init_forUpdate);\r
+\r
+ // current_rh is used to track which row we need to unlock,\r
+ // at this point no row needs to be unlocked.\r
+ pos.current_rh = null;\r
+ }\r
+\r
+ // move scan current position forward.\r
+ pos.current_slot++;\r
+ this.stat_numrows_visited++;\r
+\r
+ // get current record handle for positioning but don't read\r
+ // data until we verify it is not deleted. rh is needed\r
+ // for repositioning if we lose the latch.\r
+ RecordHandle rh = \r
+ pos.current_leaf.page.fetchFromSlot(\r
+ (RecordHandle) null,\r
+ pos.current_slot, \r
+ check_row_template,\r
+ null,\r
+ true);\r
+\r
+ // lock the row.\r
+ boolean latch_released =\r
+ !this.getLockingPolicy().lockScanRow(\r
+ this, this.getConglomerate(), pos,\r
+ false, \r
+ init_lock_fetch_desc,\r
+ pos.current_lock_template,\r
+ pos.current_lock_row_loc,\r
+ false, init_forUpdate, lock_operation);\r
+\r
+ // special test to see if latch release code works\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ latch_released = \r
+ test_errors(\r
+ this,\r
+ "BTreeMaxScan_fetchNextGroup", false, \r
+ this.getLockingPolicy(),\r
+ pos.current_leaf, latch_released);\r
+ }\r
+\r
+ // At this point we have successfully locked this record, so\r
+ // remember the record handle so that it can be unlocked if\r
+ // necessary. If the above lock deadlocks, we will not try\r
+ // to unlock a lock we never got in close(), because current_rh\r
+ // is null until after the lock is granted.\r
+ pos.current_rh = rh;\r
+\r
+ if (latch_released)\r
+ {\r
+ // lost latch on page in order to wait for row lock.\r
+ // Because we have scan lock on page, we need only\r
+ // call reposition() which will use the saved record\r
+ // handle to reposition to the same spot on the page.\r
+ // We don't have to search the\r
+ // tree again, as we have the a scan lock on the page\r
+ // which means the current_rh is valid to reposition on.\r
+ if (!reposition(pos, false))\r
+ {\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ // can't fail while with scan lock\r
+ SanityManager.THROWASSERT(\r
+ "can not fail holding scan lock.");\r
+ }\r
+ }\r
+ }\r
+\r
+\r
+ if (pos.current_leaf.page.isDeletedAtSlot(pos.current_slot))\r
+ {\r
+ this.stat_numdeleted_rows_visited++;\r
+\r
+ if (check_row_template[0].isNull())\r
+ {\r
+ // nulls sort at high end and are not to be returned\r
+ // by max scan, so search is over, return whatever is\r
+ // in fetch_row.\r
+ nulls_not_reached = false;\r
+ break;\r
+ }\r
+ }\r
+ else if (check_row_template[0].isNull())\r
+ {\r
+ nulls_not_reached = false;\r
+ break;\r
+ }\r
+ else \r
+ {\r
+\r
+ pos.current_leaf.page.fetchFromSlot(\r
+ pos.current_rh,\r
+ pos.current_slot, fetch_row, init_fetchDesc,\r
+ true);\r
+\r
+ stat_numrows_qualified++;\r
+ max_rh = pos.current_rh;\r
+ }\r
+ }\r
+\r
+ // Move position of the scan to slot 0 of the next page. If there\r
+ // is no next page current_page will be null.\r
+ positionAtNextPage(pos);\r
+\r
+ this.stat_numpages_visited++;\r
+ }\r
+\r
+\r
+ // Reached last leaf of tree.\r
+ positionAtDoneScan(pos);\r
+\r
+ // we need to decrement when we stop scan at the end of the table.\r
+ this.stat_numpages_visited--;\r
+\r
+ return(max_rh != null);\r
+ }\r
+\r
+ /**************************************************************************\r
+ * Protected implementation of abstract methods of BTreeScan class:\r
+ **************************************************************************\r
+ */\r
+\r
+ /**\r
+ * disallow fetchRows on this scan type.\r
+ * <p>\r
+ * @exception StandardException Standard exception policy.\r
+ **/\r
+ protected int fetchRows(\r
+ BTreeRowPosition pos,\r
+ DataValueDescriptor[][] row_array,\r
+ RowLocation[] rowloc_array,\r
+ BackingStoreHashtable hash_table,\r
+ long max_rowcnt,\r
+ int[] key_column_numbers)\r
+ throws StandardException\r
+ {\r
+ throw StandardException.newException(\r
+ SQLState.BTREE_UNIMPLEMENTED_FEATURE);\r
+ }\r
+\r
+\r
+ /**\r
+ * Position scan at "start" position of the scan.\r
+ * <p>\r
+ * Positions the scan to the slot just after the first record to be \r
+ * returned from the backward scan. Returns the start page latched, and \r
+ * sets "current_slot" to the slot number just right of the first slot\r
+ * to return.\r
+ * <p>\r
+ *\r
+ * @exception StandardException Standard exception policy.\r
+ **/\r
+ protected void positionAtStartPosition(\r
+ BTreeRowPosition pos)\r
+ throws StandardException\r
+ {\r
+ boolean exact;\r
+\r
+ // This routine should only be called from first next() call //\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ SanityManager.ASSERT(this.scan_state == SCAN_INIT);\r
+ SanityManager.ASSERT(pos.current_rh == null);\r
+ SanityManager.ASSERT(pos.current_positionKey == null);\r
+ SanityManager.ASSERT(pos.current_scan_pageno == 0);\r
+ }\r
+\r
+ // Loop until you can lock the row previous to the first row to be\r
+ // returned by the scan, while holding the page latched, without\r
+ // waiting. If you have to wait, drop the latch, wait for the lock -\r
+ // which makes it likely if you wait for the lock you will loop just\r
+ // once, find the same lock satisfies the search and since you already\r
+ // have the lock it will be granted.\r
+ while (true)\r
+ {\r
+ // Find the starting page and row slot, must start at root and\r
+ // search either for leftmost leaf, or search for specific key.\r
+ ControlRow root = ControlRow.get(this, BTree.ROOTPAGEID); \r
+\r
+ // include search of tree in page visited stats.\r
+ stat_numpages_visited += root.getLevel() + 1;\r
+\r
+ if (init_startKeyValue == null)\r
+ {\r
+ // No start given, position at last slot + 1 of rightmost leaf \r
+ pos.current_leaf = (LeafControlRow) root.searchRight(this);\r
+\r
+ pos.current_slot = pos.current_leaf.page.recordCount();\r
+ exact = false;\r
+ }\r
+ else\r
+ {\r
+ // only max needed, no start position supported.\r
+ throw StandardException.newException(\r
+ SQLState.BTREE_UNIMPLEMENTED_FEATURE);\r
+ }\r
+\r
+ // backward scan initial positioning will request a previous\r
+ // key lock for initial positioning. The actual scan will have\r
+ // to make 2 lock requests per row fetch, one for a previous key\r
+ // and one for lock on row it is positioned on. Optimizations\r
+ // can be made depending on isolation level.\r
+ // \r
+ // Note that this is not a "previous key" lock as the row we are\r
+ // locking is the max row to return. Get the scan lock at the\r
+ // same time.\r
+\r
+ pos.current_slot--;\r
+ boolean latch_released = \r
+ !this.getLockingPolicy().lockScanRow(\r
+ this, this.getConglomerate(), pos,\r
+ true, \r
+ init_lock_fetch_desc,\r
+ pos.current_lock_template,\r
+ pos.current_lock_row_loc,\r
+ false, init_forUpdate, lock_operation);\r
+ pos.current_slot++;\r
+\r
+ // special test to see if latch release code works\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ latch_released = \r
+ test_errors(\r
+ this,\r
+ "BTreeMaxScan_positionAtStartPosition", true,\r
+ this.getLockingPolicy(), pos.current_leaf, latch_released);\r
+ }\r
+\r
+ if (latch_released)\r
+ {\r
+ // lost latch on pos.current_leaf, search the tree again.\r
+ pos.current_leaf = null;\r
+ continue;\r
+ }\r
+ else\r
+ {\r
+ // success! got all the locks, while holding the latch.\r
+ break;\r
+ }\r
+ }\r
+\r
+ this.scan_state = SCAN_INPROGRESS;\r
+ pos.current_scan_pageno = pos.current_leaf.page.getPageNumber();\r
+\r
+ if (SanityManager.DEBUG)\r
+ SanityManager.ASSERT(pos.current_leaf != null);\r
+ }\r
+\r
+ /**************************************************************************\r
+ * Public Methods of This class:\r
+ **************************************************************************\r
+ */\r
+\r
+ /**\r
+ * Fetch the maximum row in the table.\r
+ * <p>\r
+ * Utility routine used by both fetchSet() and fetchNextGroup().\r
+ *\r
+ * @exception StandardException Standard exception policy.\r
+ **/\r
+ public boolean fetchMax(\r
+ DataValueDescriptor[] fetch_row)\r
+ throws StandardException\r
+ {\r
+ BTreeRowPosition pos = scan_position;\r
+ int ret_row_count = 0;\r
+\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ SanityManager.ASSERT(this.container != null,\r
+ "BTreeMaxScan.fetchMax() called on a closed scan.");\r
+ }\r
+\r
+\r
+ if (this.scan_state == BTreeScan.SCAN_INPROGRESS)\r
+ {\r
+ // Get current page of scan, with latch\r
+ \r
+ // reposition the scan at the row just before the next one to \r
+ // return.\r
+ // This routine handles the mess of repositioning if the row or \r
+ // the page has disappeared. This can happen if a lock was not \r
+ // held on the row while not holding the latch (can happen if\r
+ // this scan is read uncommitted).\r
+ if (!reposition(scan_position, true))\r
+ {\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ SanityManager.THROWASSERT(\r
+ "can not fail with 2nd param true.");\r
+ }\r
+ }\r
+\r
+ }\r
+ else if (this.scan_state == SCAN_INIT)\r
+ {\r
+ // 1st positioning of scan (delayed from openScan).\r
+ positionAtStartPosition(scan_position);\r
+ }\r
+ else\r
+ {\r
+ if (SanityManager.DEBUG)\r
+ SanityManager.ASSERT(this.scan_state == SCAN_DONE);\r
+\r
+ return(false);\r
+ }\r
+\r
+\r
+ // At this point:\r
+ // current_page is latched. current_slot is the slot on current_page\r
+ // just "right" of the "next" record this routine should process.\r
+\r
+\r
+ boolean max_found = false;\r
+\r
+ // if we can find a non-deleted row on this page then it is easy.\r
+\r
+ if ((pos.current_slot - 1) > 0)\r
+ {\r
+ // move scan current position forward.\r
+ pos.current_slot--;\r
+\r
+ while (pos.current_slot > 0)\r
+ {\r
+ this.stat_numrows_visited++;\r
+\r
+ // get current record handle for positioning but don't read\r
+ // data until we verify it is not deleted. rh is needed\r
+ // for repositioning if we lose the latch.\r
+ RecordHandle rh = \r
+ pos.current_leaf.page.fetchFromSlot(\r
+ (RecordHandle) null,\r
+ pos.current_slot, fetch_row, init_fetchDesc,\r
+ true);\r
+\r
+ boolean latch_released =\r
+ !this.getLockingPolicy().lockScanRow(\r
+ this, this.getConglomerate(), pos, \r
+ false, \r
+ init_lock_fetch_desc,\r
+ pos.current_lock_template,\r
+ pos.current_lock_row_loc,\r
+ false, init_forUpdate, lock_operation);\r
+\r
+ // At this point we have successfully locked this record, so\r
+ // remember the record handle so that it can be unlocked if\r
+ // necessary. If the above lock deadlocks, we will not try\r
+ // to unlock a lock we never got in close(), because current_rh\r
+ // is null until after the lock is granted.\r
+ pos.current_rh = rh;\r
+\r
+\r
+ if (latch_released)\r
+ {\r
+ // had to wait on lock while lost latch, now last page of\r
+ // index may have changed, give up on "easy/fast" max scan.\r
+ pos.current_leaf = null;\r
+ break;\r
+ }\r
+\r
+ if (pos.current_leaf.page.isDeletedAtSlot(pos.current_slot))\r
+ {\r
+ this.stat_numdeleted_rows_visited++;\r
+ pos.current_rh_qualified = false;\r
+ }\r
+ else if (fetch_row[0].isNull())\r
+ {\r
+ pos.current_rh_qualified = false;\r
+ }\r
+ else\r
+ {\r
+ pos.current_rh_qualified = true;\r
+ }\r
+\r
+ if (pos.current_rh_qualified)\r
+ {\r
+ // return the qualifying max row.\r
+\r
+ // Found qualifying row. Are we done fetching rows for the\r
+ // group?\r
+ ret_row_count++;\r
+ stat_numrows_qualified++;\r
+\r
+ // current_slot is invalid after releasing latch\r
+ pos.current_slot = Page.INVALID_SLOT_NUMBER;\r
+\r
+ max_found = true;\r
+ break;\r
+ }\r
+ else\r
+ {\r
+ pos.current_slot--;\r
+ }\r
+ }\r
+ }\r
+\r
+ if (pos.current_leaf != null)\r
+ {\r
+ // done with "last" page in table.\r
+ pos.current_leaf.release();\r
+ pos.current_leaf = null;\r
+ }\r
+\r
+ // Reached last leaf of tree.\r
+ positionAtDoneScan(scan_position);\r
+\r
+ if (!max_found)\r
+ {\r
+ // max row in table was not last row in table\r
+ max_found = fetchMaxRowFromBeginning(scan_position, fetch_row);\r
+ }\r
+\r
+ return(max_found);\r
+ }\r
+}\r
projects / Benchmarks_CSolver.git / blobdiff