KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > derby > impl > store > access > btree > BTreeMaxScan


1 /*
2
3    Derby - Class org.apache.derby.impl.store.access.btree.BTreeMaxScan
4
5    Licensed to the Apache Software Foundation (ASF) under one or more
6    contributor license agreements. See the NOTICE file distributed with
7    this work for additional information regarding copyright ownership.
8    The ASF licenses this file to you under the Apache License, Version 2.0
9    (the "License"); you may not use this file except in compliance with
10    the License. You may obtain a copy of the License at
11
12       http://www.apache.org/licenses/LICENSE-2.0
13
14    Unless required by applicable law or agreed to in writing, software
15    distributed under the License is distributed on an "AS IS" BASIS,
16    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17    See the License for the specific language governing permissions and
18    limitations under the License.
19
20  */
21
22 package org.apache.derby.impl.store.access.btree;
23
24 import org.apache.derby.iapi.reference.SQLState;
25
26 import org.apache.derby.iapi.services.sanity.SanityManager;
27
28 import org.apache.derby.iapi.error.StandardException;
29
30 import org.apache.derby.iapi.store.access.RowUtil;
31 import org.apache.derby.iapi.store.access.Qualifier;
32 import org.apache.derby.iapi.store.access.ScanController;
33
34 import org.apache.derby.iapi.store.raw.FetchDescriptor;
35 import org.apache.derby.iapi.store.raw.Page;
36 import org.apache.derby.iapi.store.raw.RecordHandle;
37
38 import org.apache.derby.iapi.types.DataValueDescriptor;
39
40 import org.apache.derby.iapi.types.RowLocation;
41
42 import org.apache.derby.iapi.store.access.BackingStoreHashtable;
43
44
45 /**
46
47   A b-tree scan controller corresponds to an instance of an open b-tree scan.
48   <P>
49   <B>Concurrency Notes<\B>
50   <P>
51   The concurrency rules are derived from OpenBTree.
52   <P>
53   @see OpenBTree
54
55 **/
56
57 /**
58
59 A BTreeScan implementation that provides the 90% solution to the max on
60 btree problem. If the row is the last row in the btree it works very
61 efficiently. This implementation will be removed once backward scan is
62 fully functional.
63
64 **/
65
66 public class BTreeMaxScan extends BTreeScan
67 {
68
69     /**************************************************************************
70      * Private methods of This class:
71      **************************************************************************
72      */
73
74     /**
75      * Fetch the maximum non-deleted row from the table.
76      *
77      * @exception StandardException Standard exception policy.
78      **/
79     private boolean fetchMaxRowFromBeginning(
80     BTreeRowPosition pos,
81     DataValueDescriptor[] fetch_row)
82         throws StandardException
83     {
84         int ret_row_count = 0;
85         RecordHandle max_rh = null;
86
87         // we need to scan until we hit the end of the table or until we
88 // run into a null. Use this template to probe the "next" row so
89 // that if we need to finish, fetch_row will have the right value.
90 DataValueDescriptor[] check_row_template = new DataValueDescriptor[1];
91         check_row_template[0] = fetch_row[0].getClone();
92         FetchDescriptor check_row_desc = RowUtil.getFetchDescriptorConstant(1);
93
94         // reopen the scan for reading from the beginning of the table.
95 reopenScan(
96             (DataValueDescriptor[]) null,
97             ScanController.NA,
98             (Qualifier[][]) null,
99             (DataValueDescriptor[]) null,
100             ScanController.NA);
101
102         positionAtStartForForwardScan(pos);
103
104         // At this point:
105 // current_page is latched. current_slot is the slot on current_page
106 // just before the "next" record this routine should process.
107
108         // loop through successive leaf pages and successive slots on those
109 // leaf pages. Stop when either the last leaf is reached. At any
110 // time in the scan fetch_row will contain "last" non-deleted row
111 // seen.
112
113         boolean nulls_not_reached = true;
114         while ((pos.current_leaf != null) && nulls_not_reached)
115         {
116             while ((pos.current_slot + 1) < pos.current_leaf.page.recordCount())
117             {
118                 // unlock the previous row if doing read.
119 if (pos.current_rh != null)
120                 {
121                     this.getLockingPolicy().unlockScanRecordAfterRead(
122                         pos, init_forUpdate);
123
124                     // current_rh is used to track which row we need to unlock,
125 // at this point no row needs to be unlocked.
126 pos.current_rh = null;
127                 }
128
129                 // move scan current position forward.
130 pos.current_slot++;
131                 this.stat_numrows_visited++;
132
133                 // get current record handle for positioning but don't read
134 // data until we verify it is not deleted. rh is needed
135 // for repositioning if we lose the latch.
136 RecordHandle rh =
137                     pos.current_leaf.page.fetchFromSlot(
138                         (RecordHandle) null,
139                         pos.current_slot,
140                         check_row_template,
141                         null,
142                         true);
143
144                 // lock the row.
145 boolean latch_released =
146                     !this.getLockingPolicy().lockScanRow(
147                         this, this.getConglomerate(), pos,
148                         false,
149                         init_lock_fetch_desc,
150                         pos.current_lock_template,
151                         pos.current_lock_row_loc,
152                         false, init_forUpdate, lock_operation);
153
154                 // special test to see if latch release code works
155 if (SanityManager.DEBUG)
156                 {
157                     latch_released =
158                         test_errors(
159                             this,
160                             "BTreeMaxScan_fetchNextGroup", false,
161                             this.getLockingPolicy(),
162                             pos.current_leaf, latch_released);
163                 }
164
165                 // At this point we have successfully locked this record, so
166 // remember the record handle so that it can be unlocked if
167 // necessary. If the above lock deadlocks, we will not try
168 // to unlock a lock we never got in close(), because current_rh
169 // is null until after the lock is granted.
170 pos.current_rh = rh;
171
172                 if (latch_released)
173                 {
174                     // lost latch on page in order to wait for row lock.
175 // Because we have scan lock on page, we need only
176 // call reposition() which will use the saved record
177 // handle to reposition to the same spot on the page.
178 // We don't have to search the
179 // tree again, as we have the a scan lock on the page
180 // which means the current_rh is valid to reposition on.
181 if (!reposition(pos, false))
182                     {
183                         if (SanityManager.DEBUG)
184                         {
185                             // can't fail while with scan lock
186 SanityManager.THROWASSERT(
187                                 "can not fail holding scan lock.");
188                         }
189                     }
190                 }
191
192
193                 if (pos.current_leaf.page.isDeletedAtSlot(pos.current_slot))
194                 {
195                     this.stat_numdeleted_rows_visited++;
196
197                     if (check_row_template[0].isNull())
198                     {
199                         // nulls sort at high end and are not to be returned
200 // by max scan, so search is over, return whatever is
201 // in fetch_row.
202 nulls_not_reached = false;
203                         break;
204                     }
205                 }
206                 else if (check_row_template[0].isNull())
207                 {
208                     nulls_not_reached = false;
209                     break;
210                 }
211                 else
212                 {
213
214                     pos.current_leaf.page.fetchFromSlot(
215                         pos.current_rh,
216                         pos.current_slot, fetch_row, init_fetchDesc,
217                         true);
218
219                     stat_numrows_qualified++;
220                     max_rh = pos.current_rh;
221                 }
222             }
223
224             // Move position of the scan to slot 0 of the next page. If there
225 // is no next page current_page will be null.
226 positionAtNextPage(pos);
227
228             this.stat_numpages_visited++;
229         }
230
231
232         // Reached last leaf of tree.
233 positionAtDoneScan(pos);
234
235         // we need to decrement when we stop scan at the end of the table.
236 this.stat_numpages_visited--;
237
238         return(max_rh != null);
239     }
240
241     /**************************************************************************
242      * Protected implementation of abstract methods of BTreeScan class:
243      **************************************************************************
244      */
245
246     /**
247      * disallow fetchRows on this scan type.
248      * <p>
249      * @exception StandardException Standard exception policy.
250      **/
251     protected int fetchRows(
252     BTreeRowPosition pos,
253     DataValueDescriptor[][] row_array,
254     RowLocation[] rowloc_array,
255     BackingStoreHashtable hash_table,
256     long max_rowcnt,
257     int[] key_column_numbers)
258         throws StandardException
259     {
260         throw StandardException.newException(
261                 SQLState.BTREE_UNIMPLEMENTED_FEATURE);
262     }
263
264
265     /**
266      * Position scan at "start" position of the scan.
267      * <p>
268      * Positions the scan to the slot just after the first record to be
269      * returned from the backward scan. Returns the start page latched, and
270      * sets "current_slot" to the slot number just right of the first slot
271      * to return.
272      * <p>
273      *
274      * @exception StandardException Standard exception policy.
275      **/
276     protected void positionAtStartPosition(
277     BTreeRowPosition pos)
278         throws StandardException
279     {
280         boolean exact;
281
282         // This routine should only be called from first next() call //
283 if (SanityManager.DEBUG)
284         {
285             SanityManager.ASSERT(this.scan_state == SCAN_INIT);
286             SanityManager.ASSERT(pos.current_rh == null);
287             SanityManager.ASSERT(pos.current_positionKey == null);
288             SanityManager.ASSERT(pos.current_scan_pageno == 0);
289         }
290
291         // Loop until you can lock the row previous to the first row to be
292 // returned by the scan, while holding the page latched, without
293 // waiting. If you have to wait, drop the latch, wait for the lock -
294 // which makes it likely if you wait for the lock you will loop just
295 // once, find the same lock satisfies the search and since you already
296 // have the lock it will be granted.
297 while (true)
298         {
299             // Find the starting page and row slot, must start at root and
300 // search either for leftmost leaf, or search for specific key.
301 ControlRow root = ControlRow.Get(this, BTree.ROOTPAGEID);
302
303             // include search of tree in page visited stats.
304 stat_numpages_visited += root.getLevel() + 1;
305
306             if (init_startKeyValue == null)
307             {
308                 // No start given, position at last slot + 1 of rightmost leaf
309 pos.current_leaf = (LeafControlRow) root.searchRight(this);
310
311                 pos.current_slot = pos.current_leaf.page.recordCount();
312                 exact = false;
313             }
314             else
315             {
316                 // only max needed, no start position supported.
317 throw StandardException.newException(
318                         SQLState.BTREE_UNIMPLEMENTED_FEATURE);
319             }
320
321             // backward scan initial positioning will request a previous
322 // key lock for initial positioning. The actual scan will have
323 // to make 2 lock requests per row fetch, one for a previous key
324 // and one for lock on row it is positioned on. Optimizations
325 // can be made depending on isolation level.
326 //
327 // Note that this is not a "previous key" lock as the row we are
328 // locking is the max row to return. Get the scan lock at the
329 // same time.
330
331             pos.current_slot--;
332             boolean latch_released =
333                 !this.getLockingPolicy().lockScanRow(
334                     this, this.getConglomerate(), pos,
335                     true,
336                     init_lock_fetch_desc,
337                     pos.current_lock_template,
338                     pos.current_lock_row_loc,
339                     false, init_forUpdate, lock_operation);
340             pos.current_slot++;
341
342             // special test to see if latch release code works
343 if (SanityManager.DEBUG)
344             {
345                 latch_released =
346                     test_errors(
347                         this,
348                         "BTreeMaxScan_positionAtStartPosition", true,
349                         this.getLockingPolicy(), pos.current_leaf, latch_released);
350             }
351
352             if (latch_released)
353             {
354                 // lost latch on pos.current_leaf, search the tree again.
355 pos.current_leaf = null;
356                 continue;
357             }
358             else
359             {
360                 // success! got all the locks, while holding the latch.
361 break;
362             }
363         }
364
365         this.scan_state = SCAN_INPROGRESS;
366         pos.current_scan_pageno = pos.current_leaf.page.getPageNumber();
367
368         if (SanityManager.DEBUG)
369             SanityManager.ASSERT(pos.current_leaf != null);
370     }
371
372     /**************************************************************************
373      * Public Methods of This class:
374      **************************************************************************
375      */
376
377     /**
378      * Fetch the maximum row in the table.
379      * <p>
380      * Utility routine used by both fetchSet() and fetchNextGroup().
381      *
382      * @exception StandardException Standard exception policy.
383      **/
384     public boolean fetchMax(
385     DataValueDescriptor[] fetch_row)
386         throws StandardException
387     {
388         BTreeRowPosition pos = scan_position;
389         int ret_row_count = 0;
390
391         if (SanityManager.DEBUG)
392         {
393             SanityManager.ASSERT(this.container != null,
394                 "BTreeMaxScan.fetchMax() called on a closed scan.");
395         }
396
397
398         if (this.scan_state == BTreeScan.SCAN_INPROGRESS)
399         {
400             // Get current page of scan, with latch
401
402             // reposition the scan at the row just before the next one to
403 // return.
404 // This routine handles the mess of repositioning if the row or
405 // the page has disappeared. This can happen if a lock was not
406 // held on the row while not holding the latch (can happen if
407 // this scan is read uncommitted).
408 if (!reposition(scan_position, true))
409             {
410                 if (SanityManager.DEBUG)
411                 {
412                     SanityManager.THROWASSERT(
413                         "can not fail with 2nd param true.");
414                 }
415             }
416
417         }
418         else if (this.scan_state == SCAN_INIT)
419         {
420             // 1st positioning of scan (delayed from openScan).
421 positionAtStartPosition(scan_position);
422         }
423         else
424         {
425             if (SanityManager.DEBUG)
426                 SanityManager.ASSERT(this.scan_state == SCAN_DONE);
427
428             return(false);
429         }
430
431
432         // At this point:
433 // current_page is latched. current_slot is the slot on current_page
434 // just "right" of the "next" record this routine should process.
435
436
437         boolean max_found = false;
438
439         // if we can find a non-deleted row on this page then it is easy.
440
441         if ((pos.current_slot - 1) > 0)
442         {
443             // move scan current position forward.
444 pos.current_slot--;
445
446             while (pos.current_slot > 0)
447             {
448                 this.stat_numrows_visited++;
449
450                 // get current record handle for positioning but don't read
451 // data until we verify it is not deleted. rh is needed
452 // for repositioning if we lose the latch.
453 RecordHandle rh =
454                     pos.current_leaf.page.fetchFromSlot(
455                         (RecordHandle) null,
456                         pos.current_slot, fetch_row, init_fetchDesc,
457                         true);
458
459                 boolean latch_released =
460                     !this.getLockingPolicy().lockScanRow(
461                         this, this.getConglomerate(), pos,
462                         false,
463                         init_lock_fetch_desc,
464                         pos.current_lock_template,
465                         pos.current_lock_row_loc,
466                         false, init_forUpdate, lock_operation);
467
468                 // At this point we have successfully locked this record, so
469 // remember the record handle so that it can be unlocked if
470 // necessary. If the above lock deadlocks, we will not try
471 // to unlock a lock we never got in close(), because current_rh
472 // is null until after the lock is granted.
473 pos.current_rh = rh;
474
475
476                 if (latch_released)
477                 {
478                     // had to wait on lock while lost latch, now last page of
479 // index may have changed, give up on "easy/fast" max scan.
480 pos.current_leaf = null;
481                     break;
482                 }
483
484                 if (pos.current_leaf.page.isDeletedAtSlot(pos.current_slot))
485                 {
486                     this.stat_numdeleted_rows_visited++;
487                     pos.current_rh_qualified = false;
488                 }
489                 else if (fetch_row[0].isNull())
490                 {
491                     pos.current_rh_qualified = false;
492                 }
493                 else
494                 {
495                     pos.current_rh_qualified = true;
496                 }
497
498                 if (pos.current_rh_qualified)
499                 {
500                     // return the qualifying max row.
501
502                     // Found qualifying row. Are we done fetching rows for the
503 // group?
504 ret_row_count++;
505                     stat_numrows_qualified++;
506
507                     // current_slot is invalid after releasing latch
508 pos.current_slot = Page.INVALID_SLOT_NUMBER;
509
510                     max_found = true;
511                     break;
512                 }
513                 else
514                 {
515                     pos.current_slot--;
516                 }
517             }
518         }
519
520         if (pos.current_leaf != null)
521         {
522             // done with "last" page in table.
523 pos.current_leaf.release();
524             pos.current_leaf = null;
525         }
526
527         // Reached last leaf of tree.
528 positionAtDoneScan(scan_position);
529
530         if (!max_found)
531         {
532             // max row in table was not last row in table
533 max_found = fetchMaxRowFromBeginning(scan_position, fetch_row);
534         }
535
536         return(max_found);
537     }
538 }
539
Popular Tags