KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*
2
3    Derby - Class org.apache.derby.impl.store.access.btree.BTreeForwardScan
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 import org.apache.derby.iapi.services.io.Storable;
28
29 import org.apache.derby.iapi.error.StandardException;
30
31 import org.apache.derby.iapi.store.access.conglomerate.Conglomerate;
32 import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;
33 import org.apache.derby.iapi.store.access.conglomerate.ScanManager;
34 import org.apache.derby.iapi.store.access.conglomerate.TransactionManager;
35
36 import org.apache.derby.iapi.store.access.DynamicCompiledOpenConglomInfo;
37 import org.apache.derby.iapi.store.access.Qualifier;
38 import org.apache.derby.iapi.store.access.RowUtil;
39 import org.apache.derby.iapi.store.access.ScanController;
40 import org.apache.derby.iapi.store.access.ScanInfo;
41 import org.apache.derby.iapi.store.access.StaticCompiledOpenConglomInfo;
42 import org.apache.derby.iapi.store.access.TransactionController;
43
44 import org.apache.derby.iapi.store.raw.ContainerHandle;
45 import org.apache.derby.iapi.store.raw.LockingPolicy;
46 import org.apache.derby.iapi.store.raw.Page;
47 import org.apache.derby.iapi.store.raw.RecordHandle;
48 import org.apache.derby.iapi.store.raw.Transaction;
49
50 import org.apache.derby.iapi.types.DataValueDescriptor;
51
52 import org.apache.derby.iapi.types.RowLocation;
53
54 import org.apache.derby.impl.store.access.conglomerate.ConglomerateUtil;
55 import org.apache.derby.impl.store.access.conglomerate.TemplateRow;
56
57 import org.apache.derby.iapi.services.io.FormatableBitSet;
58 import org.apache.derby.iapi.store.access.BackingStoreHashtable;
59
60 /**
61
62   A b-tree scan controller corresponds to an instance of an open b-tree scan.
63   <P>
64   <B>Concurrency Notes<\B>
65   <P>
66   The concurrency rules are derived from OpenBTree.
67   <P>
68   @see OpenBTree
69
70 **/
71
72 public class BTreeForwardScan extends BTreeScan
73 {
74     /*
75     ** Private/Protected methods of This class, sorted alphabetically
76     */
77
78     /**
79     Position scan at "start" position.
80     <p>
81     Positions the scan to the slot just before the first record to be returned
82     from the scan. Returns the start page latched, and sets "current_slot" to
83     the slot number.
84
85     @exception StandardException Standard exception policy.
86     **/
87     protected void positionAtStartPosition(
88     BTreeRowPosition pos)
89         throws StandardException
90     {
91         positionAtStartForForwardScan(pos);
92     }
93
94     ///////////////////////////////////////////////
95 //
96 // RESOLVE (jamie): i had to add these simple
97 // super.init() super.close() calls to get mssdk302
98 // to work. I could not determine what the problem
99 // is. For the time being, please don't remove
100 // them even though they don't appear to serve a
101 // useful purpose.
102 //
103 ///////////////////////////////////////////////
104
105     /**
106     Initialize the scan for use.
107     <p>
108     Any changes to this method may have to be reflected in close as well.
109     <p>
110     The btree init opens the container (super.init), and stores away the
111     state of the qualifiers. The actual searching for the first position
112     is delayed until the first next() call.
113
114     @exception StandardException Standard exception policy.
115     **/
116     public void init(
117     TransactionManager xact_manager,
118     Transaction rawtran,
119     boolean hold,
120     int open_mode,
121     int lock_level,
122     BTreeLockingPolicy btree_locking_policy,
123     FormatableBitSet scanColumnList,
124     DataValueDescriptor[] startKeyValue,
125     int startSearchOperator,
126     Qualifier qualifier[][],
127     DataValueDescriptor[] stopKeyValue,
128     int stopSearchOperator,
129     BTree conglomerate,
130     LogicalUndo undo,
131     StaticCompiledOpenConglomInfo static_info,
132     DynamicCompiledOpenConglomInfo dynamic_info)
133         throws StandardException
134     {
135         super.init(
136             xact_manager, rawtran, hold, open_mode, lock_level,
137             btree_locking_policy, scanColumnList, startKeyValue,
138             startSearchOperator, qualifier, stopKeyValue,
139             stopSearchOperator, conglomerate, undo, static_info, dynamic_info);
140     }
141
142     /**
143     Close the scan.
144     **/
145     public void close()
146         throws StandardException
147     {
148         super.close();
149     }
150
151
152     /**
153      * Fetch the next N rows from the table.
154      * <p>
155      * Utility routine used by both fetchSet() and fetchNextGroup().
156      *
157      * @exception StandardException Standard exception policy.
158      **/
159     protected int fetchRows(
160     BTreeRowPosition pos,
161     DataValueDescriptor[][] row_array,
162     RowLocation[] rowloc_array,
163     BackingStoreHashtable hash_table,
164     long max_rowcnt,
165     int[] key_column_numbers)
166         throws StandardException
167     {
168
169         int ret_row_count = 0;
170         DataValueDescriptor[] fetch_row = null;
171         RecordHandle rh;
172
173         if (max_rowcnt == -1)
174             max_rowcnt = Long.MAX_VALUE;
175
176
177         if (this.scan_state == BTreeScan.SCAN_INPROGRESS)
178         {
179             // reposition the scan at the row just before the next one to
180 // return.
181 // This routine handles the mess of repositioning if the row or
182 // the page has disappeared. This can happen if a lock was not
183 // held on the row while not holding the latch (can happen if
184 // this scan is read uncommitted).
185 //
186 // code path tested by readUncommitted.sql:TEST 1
187 //
188 if (!reposition(pos, true))
189             {
190                 if (SanityManager.DEBUG)
191                 {
192                     SanityManager.THROWASSERT(
193                         "can not fail with 2nd param true.");
194                 }
195             }
196
197         }
198         else if (this.scan_state == SCAN_INIT)
199         {
200             // 1st positioning of scan (delayed from openScan).
201 positionAtStartPosition(pos);
202         }
203         else if (this.scan_state == SCAN_HOLD_INPROGRESS)
204         {
205             reopen();
206
207             this.scan_state = SCAN_INPROGRESS;
208
209             if (SanityManager.DEBUG)
210             {
211                 SanityManager.ASSERT(scan_position.current_positionKey != null);
212             }
213
214             // reposition the scan at the row just before the next one to
215 // return.
216 // This routine handles the mess of repositioning if the row or
217 // the page has disappeared. This can happen if a lock was not
218 // held on the row while not holding the latch.
219 //
220 // code path tested by holdCursor.sql: TEST 9
221 if (!reposition(pos, true))
222             {
223                 if (SanityManager.DEBUG)
224                 {
225                     SanityManager.THROWASSERT(
226                         "can not fail with 2nd param true.");
227                 }
228             }
229
230         }
231         else if (this.scan_state == SCAN_HOLD_INIT)
232         {
233             reopen();
234
235             positionAtStartForForwardScan(scan_position);
236         }
237         else
238         {
239             if (SanityManager.DEBUG)
240                 SanityManager.ASSERT(this.scan_state == SCAN_DONE);
241
242             return(0);
243         }
244
245         if (SanityManager.DEBUG)
246         {
247             SanityManager.ASSERT(
248                 init_template != null, "init_template is null");
249         }
250
251         if (SanityManager.DEBUG)
252         {
253             SanityManager.ASSERT(this.container != null,
254                 "BTreeScan.next() called on a closed scan.");
255
256             if (row_array != null)
257                 SanityManager.ASSERT(row_array[0] != null,
258                     "first array slot in fetchNextGroup() must be non-null.");
259
260             // Btree's don't support RowLocations yet.
261 if (rowloc_array != null)
262             {
263                 throw StandardException.newException(
264                         SQLState.BTREE_UNIMPLEMENTED_FEATURE);
265             }
266         }
267
268         // System.out.println("top of fetchRows, fetch_row = " + fetch_row);
269
270
271         // At this point:
272 // current_page is latched. current_slot is the slot on current_page
273 // just before the "next" record this routine should process.
274
275         // loop through successive leaf pages and successive slots on those
276 // leaf pages. Stop when either the last leaf is reached (current_page
277 // will be null), or when stopKeyValue is reached/passed. Along the
278 // way apply qualifiers to skip rows which don't qualify.
279
280         while (pos.current_leaf != null)
281         {
282             // System.out.println(
283 // "1 of fetchSet loop, ret_row_count = " + ret_row_count +
284 // "fetch_row = " + fetch_row);
285
286             while ((pos.current_slot + 1) < pos.current_leaf.page.recordCount())
287             {
288
289                 // System.out.println(
290 // "2 of fetchSet loop, ret_row_count = " + ret_row_count +
291 // "fetch_row = " + fetch_row +
292 // "hash_table = " + hash_table);
293
294
295                 // unlock the previous row if doing read.
296 if (pos.current_rh != null)
297                 {
298                     this.getLockingPolicy().unlockScanRecordAfterRead(
299                         pos, init_forUpdate);
300
301                     // current_rh is used to track which row we need to unlock,
302 // at this point no row needs to be unlocked.
303 pos.current_rh = null;
304                 }
305
306                 // Allocate a new row to read the row into.
307 if (fetch_row == null)
308                 {
309                     if (hash_table == null)
310                     {
311                         // point at allocated row in array if one exists.
312 if (row_array[ret_row_count] == null)
313                         {
314                             row_array[ret_row_count] =
315                                 runtime_mem.get_row_for_export();
316                         }
317
318                         fetch_row = row_array[ret_row_count];
319                     }
320                     else
321                     {
322                         // get a brand new row.
323 fetch_row = runtime_mem.get_row_for_export();
324                     }
325                 }
326
327                 // move scan current position forward.
328 pos.current_slot++;
329                 this.stat_numrows_visited++;
330
331                 rh =
332                     pos.current_leaf.page.fetchFromSlot(
333                         (RecordHandle) null,
334                         pos.current_slot, fetch_row,
335                         init_fetchDesc,
336                         true);
337
338
339                 pos.current_rh_qualified = true;
340
341                 // See if this is the stop row.
342 if (init_stopKeyValue != null)
343                 {
344                     // See if current row is the >= the stopKeyValue.
345 //
346 // ret > 0: key is greater than row on page.
347 // ret == 0: key is exactly the row on page if full key,
348 // or partial match if partial key.
349 // ret < 0: key is less than row on page.
350 //
351 int ret = ControlRow.CompareIndexRowToKey(
352                                 fetch_row,
353                                 init_stopKeyValue,
354                                 fetch_row.length,
355                                 0, this.getConglomerate().ascDescInfo);
356
357                     if ((ret == 0) &&
358                         (init_stopSearchOperator == ScanController.GE))
359                     {
360                         // if (partial) matched and stop is GE, end the scan.
361 ret = 1;
362                     }
363
364                     if (ret > 0)
365                     {
366                         // This is the first non-qualifying row. We're done.
367
368                         pos.current_leaf.release();
369                         pos.current_leaf = null;
370                         positionAtDoneScan(pos);
371
372                         return(ret_row_count);
373                     }
374                 }
375
376
377                 // Only lock rows that are < the stopKeyValue. No need to
378 // requalify against stop position after losing the latch
379 // as the only change that could have happened is that the
380 // row was marked deleted - the key value cannot change.
381 boolean latch_released =
382                     !this.getLockingPolicy().lockScanRow(
383                         this, this.getConglomerate(), pos,
384                         false,
385                         init_lock_fetch_desc,
386                         pos.current_lock_template,
387                         pos.current_lock_row_loc,
388                         false, init_forUpdate, lock_operation);
389
390                 // special test to see if latch release code works
391 if (SanityManager.DEBUG)
392                 {
393                     latch_released =
394                         test_errors(
395                             this,
396                             "BTreeScan_fetchNextGroup", false,
397                             this.getLockingPolicy(),
398                             pos.current_leaf, latch_released);
399                 }
400
401                 // At this point we have successfully locked this record, so
402 // remember the record handle so that it can be unlocked if
403 // necessary. If the above lock deadlocks, we will not try
404 // to unlock a lock we never got in close(), because current_rh
405 // is null until after the lock is granted.
406 pos.current_rh = rh;
407
408                 if (latch_released)
409                 {
410                     // lost latch on page in order to wait for row lock.
411 // Because we have scan lock on page, we need only
412 // call reposition() which will use the saved record
413 // handle to reposition to the same spot on the page.
414 // We don't have to search the
415 // tree again, as we have the a scan lock on the page
416 // which means the current_rh is valid to reposition on.
417
418                     if (this.getConglomerate().isUnique())
419                     {
420                         // Handle row location changing since lock request was
421 // initiated.
422 // In unique indexes, there is one case where an index
423 // row can have it's data lock key change (this usually
424 // cannot happen because only inserts and deletes are
425 // allowed - no updates). This case is an insert of a
426 // key, that exactly matches a committed deleted row,
427 // in a unique index. In that case the code updates
428 // the RowLocation column and flips the deleted bit to
429 // mark the row valid. The problem is that if this
430 // happens while we are waiting on a lock on the old
431 // RowLocation then when we wake up we have the wrong
432 // lock, and the row location we fetched earlier in
433 // this loop is invalid.
434
435                         while (latch_released)
436                         {
437                             if (!reposition(pos, false))
438                             {
439                                 if (SanityManager.DEBUG)
440                                 {
441                                     // can't fail while with scan lock
442 SanityManager.THROWASSERT(
443                                         "can not fail holding scan lock.");
444                                 }
445
446                                 // reposition will set pos.current_leaf to
447 // null, if it returns false so if the this
448 // ever does fail in delivered code, expect
449 // a null pointer exception on the next line,
450 // trying to call fetchFromSlot().
451
452                             }
453
454                             pos.current_leaf.page.fetchFromSlot(
455                                 (RecordHandle) null,
456                                 pos.current_slot, fetch_row,
457                                 init_fetchDesc,
458                                 true);
459
460                             latch_released =
461                                 !this.getLockingPolicy().lockScanRow(
462                                     this,
463                                     this.getConglomerate(),
464                                     pos,
465                                     false,
466                                     init_lock_fetch_desc,
467                                     pos.current_lock_template,
468                                     pos.current_lock_row_loc,
469                                     false, init_forUpdate, lock_operation);
470                         }
471                     }
472                     else
473                     {
474                         if (!reposition(pos, false))
475                         {
476                             if (SanityManager.DEBUG)
477                             {
478                                 // can't fail while with scan lock
479 SanityManager.THROWASSERT(
480                                     "can not fail holding scan lock.");
481                             }
482
483                             // reposition will set pos.current_leaf to
484 // null, if it returns false so if the this
485 // ever does fail in delivered code, expect
486 // a null pointer exception on the next line,
487 // trying to call isDeletedAtSlot().
488
489                         }
490
491                     }
492                 }
493
494
495                 if (pos.current_leaf.page.isDeletedAtSlot(pos.current_slot))
496                 {
497                     this.stat_numdeleted_rows_visited++;
498                     pos.current_rh_qualified = false;
499                 }
500                 else if (init_qualifier != null)
501                 {
502                     // Apply qualifiers if there are any.
503 pos.current_rh_qualified =
504                         this.process_qualifier(fetch_row);
505                 }
506
507                 if (pos.current_rh_qualified)
508                 {
509                     // qualifying row. Save position, release latch and return.
510
511                     // this.current_rh is save position of scan while latch is
512 // not held. It currently points at the current_slot in
513 // search (while latch is held).
514 if (SanityManager.DEBUG)
515                     {
516                         SanityManager.ASSERT(
517                             pos.current_leaf.page.getSlotNumber(pos.current_rh)
518                                 == pos.current_slot);
519                     }
520
521                     // Found qualifying row. Are we done fetching rows for the
522 // group?
523 ret_row_count++;
524                     stat_numrows_qualified++;
525
526                     if (hash_table != null)
527                     {
528                         if (hash_table.put(false, fetch_row))
529                             fetch_row = null;
530                     }
531                     else
532                     {
533                         fetch_row = null;
534                     }
535
536                     if (max_rowcnt <= ret_row_count)
537                     {
538                         // current_slot is invalid after releasing latch
539 pos.current_slot = Page.INVALID_SLOT_NUMBER;
540
541                         // exit fetch row loop and return to the client.
542 pos.current_leaf.release();
543                         pos.current_leaf = null;
544
545                         return(ret_row_count);
546                     }
547                 }
548             }
549
550             // Move position of the scan to slot 0 of the next page. If there
551 // is no next page current_page will be null.
552 positionAtNextPage(pos);
553
554             this.stat_numpages_visited++;
555         }
556
557         // Reached last leaf of tree.
558 positionAtDoneScan(pos);
559
560
561         // we need to decrement when we stop scan at the end of the table.
562 this.stat_numpages_visited--;
563
564         return(ret_row_count);
565     }
566 }
567
568
Popular Tags