001: /*
002:
003: Derby - Class org.apache.derby.impl.store.access.btree.BTreeMaxScan
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.impl.store.access.btree;
023:
024: import org.apache.derby.iapi.reference.SQLState;
025:
026: import org.apache.derby.iapi.services.sanity.SanityManager;
027:
028: import org.apache.derby.iapi.error.StandardException;
029:
030: import org.apache.derby.iapi.store.access.RowUtil;
031: import org.apache.derby.iapi.store.access.Qualifier;
032: import org.apache.derby.iapi.store.access.ScanController;
033:
034: import org.apache.derby.iapi.store.raw.FetchDescriptor;
035: import org.apache.derby.iapi.store.raw.Page;
036: import org.apache.derby.iapi.store.raw.RecordHandle;
037:
038: import org.apache.derby.iapi.types.DataValueDescriptor;
039:
040: import org.apache.derby.iapi.types.RowLocation;
041:
042: import org.apache.derby.iapi.store.access.BackingStoreHashtable;
043:
044: /**
045:
046: A b-tree scan controller corresponds to an instance of an open b-tree scan.
047: <P>
048: <B>Concurrency Notes<\B>
049: <P>
050: The concurrency rules are derived from OpenBTree.
051: <P>
052: @see OpenBTree
053:
054: **/
055:
056: /**
057:
058: A BTreeScan implementation that provides the 90% solution to the max on
059: btree problem. If the row is the last row in the btree it works very
060: efficiently. This implementation will be removed once backward scan is
061: fully functional.
062:
063: **/
064:
065: public class BTreeMaxScan extends BTreeScan {
066:
067: /**************************************************************************
068: * Private methods of This class:
069: **************************************************************************
070: */
071:
072: /**
073: * Fetch the maximum non-deleted row from the table.
074: *
075: * @exception StandardException Standard exception policy.
076: **/
077: private boolean fetchMaxRowFromBeginning(BTreeRowPosition pos,
078: DataValueDescriptor[] fetch_row) throws StandardException {
079: int ret_row_count = 0;
080: RecordHandle max_rh = null;
081:
082: // we need to scan until we hit the end of the table or until we
083: // run into a null. Use this template to probe the "next" row so
084: // that if we need to finish, fetch_row will have the right value.
085: DataValueDescriptor[] check_row_template = new DataValueDescriptor[1];
086: check_row_template[0] = fetch_row[0].getClone();
087: FetchDescriptor check_row_desc = RowUtil
088: .getFetchDescriptorConstant(1);
089:
090: // reopen the scan for reading from the beginning of the table.
091: reopenScan((DataValueDescriptor[]) null, ScanController.NA,
092: (Qualifier[][]) null, (DataValueDescriptor[]) null,
093: ScanController.NA);
094:
095: positionAtStartForForwardScan(pos);
096:
097: // At this point:
098: // current_page is latched. current_slot is the slot on current_page
099: // just before the "next" record this routine should process.
100:
101: // loop through successive leaf pages and successive slots on those
102: // leaf pages. Stop when either the last leaf is reached. At any
103: // time in the scan fetch_row will contain "last" non-deleted row
104: // seen.
105:
106: boolean nulls_not_reached = true;
107: while ((pos.current_leaf != null) && nulls_not_reached) {
108: while ((pos.current_slot + 1) < pos.current_leaf.page
109: .recordCount()) {
110: // unlock the previous row if doing read.
111: if (pos.current_rh != null) {
112: this .getLockingPolicy().unlockScanRecordAfterRead(
113: pos, init_forUpdate);
114:
115: // current_rh is used to track which row we need to unlock,
116: // at this point no row needs to be unlocked.
117: pos.current_rh = null;
118: }
119:
120: // move scan current position forward.
121: pos.current_slot++;
122: this .stat_numrows_visited++;
123:
124: // get current record handle for positioning but don't read
125: // data until we verify it is not deleted. rh is needed
126: // for repositioning if we lose the latch.
127: RecordHandle rh = pos.current_leaf.page.fetchFromSlot(
128: (RecordHandle) null, pos.current_slot,
129: check_row_template, null, true);
130:
131: // lock the row.
132: boolean latch_released = !this .getLockingPolicy()
133: .lockScanRow(this , this .getConglomerate(), pos,
134: false, init_lock_fetch_desc,
135: pos.current_lock_template,
136: pos.current_lock_row_loc, false,
137: init_forUpdate, lock_operation);
138:
139: // special test to see if latch release code works
140: if (SanityManager.DEBUG) {
141: latch_released = test_errors(this ,
142: "BTreeMaxScan_fetchNextGroup", false, this
143: .getLockingPolicy(),
144: pos.current_leaf, latch_released);
145: }
146:
147: // At this point we have successfully locked this record, so
148: // remember the record handle so that it can be unlocked if
149: // necessary. If the above lock deadlocks, we will not try
150: // to unlock a lock we never got in close(), because current_rh
151: // is null until after the lock is granted.
152: pos.current_rh = rh;
153:
154: if (latch_released) {
155: // lost latch on page in order to wait for row lock.
156: // Because we have scan lock on page, we need only
157: // call reposition() which will use the saved record
158: // handle to reposition to the same spot on the page.
159: // We don't have to search the
160: // tree again, as we have the a scan lock on the page
161: // which means the current_rh is valid to reposition on.
162: if (!reposition(pos, false)) {
163: if (SanityManager.DEBUG) {
164: // can't fail while with scan lock
165: SanityManager
166: .THROWASSERT("can not fail holding scan lock.");
167: }
168: }
169: }
170:
171: if (pos.current_leaf.page
172: .isDeletedAtSlot(pos.current_slot)) {
173: this .stat_numdeleted_rows_visited++;
174:
175: if (check_row_template[0].isNull()) {
176: // nulls sort at high end and are not to be returned
177: // by max scan, so search is over, return whatever is
178: // in fetch_row.
179: nulls_not_reached = false;
180: break;
181: }
182: } else if (check_row_template[0].isNull()) {
183: nulls_not_reached = false;
184: break;
185: } else {
186:
187: pos.current_leaf.page.fetchFromSlot(pos.current_rh,
188: pos.current_slot, fetch_row,
189: init_fetchDesc, true);
190:
191: stat_numrows_qualified++;
192: max_rh = pos.current_rh;
193: }
194: }
195:
196: // Move position of the scan to slot 0 of the next page. If there
197: // is no next page current_page will be null.
198: positionAtNextPage(pos);
199:
200: this .stat_numpages_visited++;
201: }
202:
203: // Reached last leaf of tree.
204: positionAtDoneScan(pos);
205:
206: // we need to decrement when we stop scan at the end of the table.
207: this .stat_numpages_visited--;
208:
209: return (max_rh != null);
210: }
211:
212: /**************************************************************************
213: * Protected implementation of abstract methods of BTreeScan class:
214: **************************************************************************
215: */
216:
217: /**
218: * disallow fetchRows on this scan type.
219: * <p>
220: * @exception StandardException Standard exception policy.
221: **/
222: protected int fetchRows(BTreeRowPosition pos,
223: DataValueDescriptor[][] row_array,
224: RowLocation[] rowloc_array,
225: BackingStoreHashtable hash_table, long max_rowcnt,
226: int[] key_column_numbers) throws StandardException {
227: throw StandardException
228: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE);
229: }
230:
231: /**
232: * Position scan at "start" position of the scan.
233: * <p>
234: * Positions the scan to the slot just after the first record to be
235: * returned from the backward scan. Returns the start page latched, and
236: * sets "current_slot" to the slot number just right of the first slot
237: * to return.
238: * <p>
239: *
240: * @exception StandardException Standard exception policy.
241: **/
242: protected void positionAtStartPosition(BTreeRowPosition pos)
243: throws StandardException {
244: boolean exact;
245:
246: // This routine should only be called from first next() call //
247: if (SanityManager.DEBUG) {
248: SanityManager.ASSERT(this .scan_state == SCAN_INIT);
249: SanityManager.ASSERT(pos.current_rh == null);
250: SanityManager.ASSERT(pos.current_positionKey == null);
251: SanityManager.ASSERT(pos.current_scan_pageno == 0);
252: }
253:
254: // Loop until you can lock the row previous to the first row to be
255: // returned by the scan, while holding the page latched, without
256: // waiting. If you have to wait, drop the latch, wait for the lock -
257: // which makes it likely if you wait for the lock you will loop just
258: // once, find the same lock satisfies the search and since you already
259: // have the lock it will be granted.
260: while (true) {
261: // Find the starting page and row slot, must start at root and
262: // search either for leftmost leaf, or search for specific key.
263: ControlRow root = ControlRow.Get(this , BTree.ROOTPAGEID);
264:
265: // include search of tree in page visited stats.
266: stat_numpages_visited += root.getLevel() + 1;
267:
268: if (init_startKeyValue == null) {
269: // No start given, position at last slot + 1 of rightmost leaf
270: pos.current_leaf = (LeafControlRow) root
271: .searchRight(this );
272:
273: pos.current_slot = pos.current_leaf.page.recordCount();
274: exact = false;
275: } else {
276: // only max needed, no start position supported.
277: throw StandardException
278: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE);
279: }
280:
281: // backward scan initial positioning will request a previous
282: // key lock for initial positioning. The actual scan will have
283: // to make 2 lock requests per row fetch, one for a previous key
284: // and one for lock on row it is positioned on. Optimizations
285: // can be made depending on isolation level.
286: //
287: // Note that this is not a "previous key" lock as the row we are
288: // locking is the max row to return. Get the scan lock at the
289: // same time.
290:
291: pos.current_slot--;
292: boolean latch_released = !this .getLockingPolicy()
293: .lockScanRow(this , this .getConglomerate(), pos,
294: true, init_lock_fetch_desc,
295: pos.current_lock_template,
296: pos.current_lock_row_loc, false,
297: init_forUpdate, lock_operation);
298: pos.current_slot++;
299:
300: // special test to see if latch release code works
301: if (SanityManager.DEBUG) {
302: latch_released = test_errors(this ,
303: "BTreeMaxScan_positionAtStartPosition", true,
304: this .getLockingPolicy(), pos.current_leaf,
305: latch_released);
306: }
307:
308: if (latch_released) {
309: // lost latch on pos.current_leaf, search the tree again.
310: pos.current_leaf = null;
311: continue;
312: } else {
313: // success! got all the locks, while holding the latch.
314: break;
315: }
316: }
317:
318: this .scan_state = SCAN_INPROGRESS;
319: pos.current_scan_pageno = pos.current_leaf.page.getPageNumber();
320:
321: if (SanityManager.DEBUG)
322: SanityManager.ASSERT(pos.current_leaf != null);
323: }
324:
325: /**************************************************************************
326: * Public Methods of This class:
327: **************************************************************************
328: */
329:
330: /**
331: * Fetch the maximum row in the table.
332: * <p>
333: * Utility routine used by both fetchSet() and fetchNextGroup().
334: *
335: * @exception StandardException Standard exception policy.
336: **/
337: public boolean fetchMax(DataValueDescriptor[] fetch_row)
338: throws StandardException {
339: BTreeRowPosition pos = scan_position;
340: int ret_row_count = 0;
341:
342: if (SanityManager.DEBUG) {
343: SanityManager.ASSERT(this .container != null,
344: "BTreeMaxScan.fetchMax() called on a closed scan.");
345: }
346:
347: if (this .scan_state == BTreeScan.SCAN_INPROGRESS) {
348: // Get current page of scan, with latch
349:
350: // reposition the scan at the row just before the next one to
351: // return.
352: // This routine handles the mess of repositioning if the row or
353: // the page has disappeared. This can happen if a lock was not
354: // held on the row while not holding the latch (can happen if
355: // this scan is read uncommitted).
356: if (!reposition(scan_position, true)) {
357: if (SanityManager.DEBUG) {
358: SanityManager
359: .THROWASSERT("can not fail with 2nd param true.");
360: }
361: }
362:
363: } else if (this .scan_state == SCAN_INIT) {
364: // 1st positioning of scan (delayed from openScan).
365: positionAtStartPosition(scan_position);
366: } else {
367: if (SanityManager.DEBUG)
368: SanityManager.ASSERT(this .scan_state == SCAN_DONE);
369:
370: return (false);
371: }
372:
373: // At this point:
374: // current_page is latched. current_slot is the slot on current_page
375: // just "right" of the "next" record this routine should process.
376:
377: boolean max_found = false;
378:
379: // if we can find a non-deleted row on this page then it is easy.
380:
381: if ((pos.current_slot - 1) > 0) {
382: // move scan current position forward.
383: pos.current_slot--;
384:
385: while (pos.current_slot > 0) {
386: this .stat_numrows_visited++;
387:
388: // get current record handle for positioning but don't read
389: // data until we verify it is not deleted. rh is needed
390: // for repositioning if we lose the latch.
391: RecordHandle rh = pos.current_leaf.page.fetchFromSlot(
392: (RecordHandle) null, pos.current_slot,
393: fetch_row, init_fetchDesc, true);
394:
395: boolean latch_released = !this .getLockingPolicy()
396: .lockScanRow(this , this .getConglomerate(), pos,
397: false, init_lock_fetch_desc,
398: pos.current_lock_template,
399: pos.current_lock_row_loc, false,
400: init_forUpdate, lock_operation);
401:
402: // At this point we have successfully locked this record, so
403: // remember the record handle so that it can be unlocked if
404: // necessary. If the above lock deadlocks, we will not try
405: // to unlock a lock we never got in close(), because current_rh
406: // is null until after the lock is granted.
407: pos.current_rh = rh;
408:
409: if (latch_released) {
410: // had to wait on lock while lost latch, now last page of
411: // index may have changed, give up on "easy/fast" max scan.
412: pos.current_leaf = null;
413: break;
414: }
415:
416: if (pos.current_leaf.page
417: .isDeletedAtSlot(pos.current_slot)) {
418: this .stat_numdeleted_rows_visited++;
419: pos.current_rh_qualified = false;
420: } else if (fetch_row[0].isNull()) {
421: pos.current_rh_qualified = false;
422: } else {
423: pos.current_rh_qualified = true;
424: }
425:
426: if (pos.current_rh_qualified) {
427: // return the qualifying max row.
428:
429: // Found qualifying row. Are we done fetching rows for the
430: // group?
431: ret_row_count++;
432: stat_numrows_qualified++;
433:
434: // current_slot is invalid after releasing latch
435: pos.current_slot = Page.INVALID_SLOT_NUMBER;
436:
437: max_found = true;
438: break;
439: } else {
440: pos.current_slot--;
441: }
442: }
443: }
444:
445: if (pos.current_leaf != null) {
446: // done with "last" page in table.
447: pos.current_leaf.release();
448: pos.current_leaf = null;
449: }
450:
451: // Reached last leaf of tree.
452: positionAtDoneScan(scan_position);
453:
454: if (!max_found) {
455: // max row in table was not last row in table
456: max_found = fetchMaxRowFromBeginning(scan_position,
457: fetch_row);
458: }
459:
460: return (max_found);
461: }
462: }
|