KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*
2
3    Derby - Class org.apache.derby.impl.store.access.btree.OpenBTree
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.services.sanity.SanityManager;
25
26 import org.apache.derby.iapi.error.StandardException;
27
28 import org.apache.derby.iapi.reference.SQLState;
29
30 import org.apache.derby.iapi.store.access.conglomerate.Conglomerate;
31 import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;
32 import org.apache.derby.iapi.store.access.conglomerate.TransactionManager;
33 import org.apache.derby.iapi.store.access.ConglomerateController;
34 import org.apache.derby.iapi.store.access.DynamicCompiledOpenConglomInfo;
35 import org.apache.derby.iapi.store.access.Qualifier;
36 import org.apache.derby.iapi.store.access.ScanController;
37 import org.apache.derby.iapi.store.access.TransactionController;
38 import org.apache.derby.iapi.store.access.SpaceInfo;
39 import org.apache.derby.iapi.store.raw.ContainerHandle;
40 import org.apache.derby.iapi.store.raw.LockingPolicy;
41 import org.apache.derby.iapi.store.raw.RecordHandle;
42 import org.apache.derby.iapi.store.raw.Transaction;
43
44 import org.apache.derby.iapi.types.DataValueDescriptor;
45
46 import org.apache.derby.iapi.types.RowLocation;
47
48 import org.apache.derby.impl.store.access.conglomerate.OpenConglomerateScratchSpace;
49
50
51
52 /**
53
54   An open b-tree contains fields and methods common to scans and controllers.
55   <P>
56   <B>Concurrency Notes<\B>
57   <P>
58   An instance of an open b-tree is owned by a single context. The b-tree code
59   assumes that the context ensures that only one thread at a time is using
60   the open b-tree. The open b-tree itself does not enforce or check this.
61
62 **/

63
64 public class OpenBTree
65 {
66     /*
67     ** Fields of OpenBTree
68     */

69
70     /**
71      * The following group of fields are all basic input parameters which are
72      * provided by the calling code when doing any sort of operation requiring
73      * an open conglomerate (openScan(), open(), openCostController(), ...).
74      * These are just saved values from what was initially input.
75      **/

76     private BTree init_conglomerate;
77
78     /**
79     The TransactionManager that open'd this btree. In the case of Internal
80     transactions used by split this will be the internal transaction, and
81     init_open_user_scans will be the user transaction that began the internal
82     transaction.
83     **/

84     private TransactionManager init_xact_manager;
85
86     private Transaction init_rawtran;
87
88     /**
89     The ContainerHandle mode the container is opened with. Remember this so
90     that if the BTree needs to do SMO with another transaction, it would open
91     the container with the same mode.
92     **/

93     private int init_openmode;
94
95     /**
96     Table or page locking?
97     **/

98     protected int init_lock_level;
99
100     private DynamicCompiledOpenConglomInfo init_dynamic_info;
101     private boolean init_hold;
102
103     /**
104     The Locking Policy to use for for access to this btree.
105     **/

106     private BTreeLockingPolicy init_btree_locking_policy;
107
108     
109     /**
110     The (open) container which contains the b-tree.
111     **/

112     protected ContainerHandle container;
113
114     /**
115     The conglomerate containerid for error reporting.
116     **/

117     protected long err_containerid;
118
119     /**
120     In the case of splits, notify all scans in this transaction to save their
121     current position by key, because the split may move the row they are
122     positioned on. This is done by calling open_user_scans.saveScanPositions().
123     Note that not all OpenBTree's will have a non-null open_user_scans. For
124     instance logical undo of btree operations will get a OpenBTree with a null
125     open_user_scans, this is all right because this operation should never need
126     to call saveScanPositions() (ie. it will never do a split).
127     **/

128     protected TransactionManager init_open_user_scans = null;
129
130
131     protected LogicalUndo btree_undo = null;
132
133     /**
134      * scratch space used for stuff like templates, export rows, ...
135      **/

136     protected OpenConglomerateScratchSpace runtime_mem;
137
138     /**************************************************************************
139      * Public Accessors of This class:
140      **************************************************************************
141      */

142     public final TransactionManager getXactMgr()
143     {
144         return(init_xact_manager);
145     }
146
147     public final Transaction getRawTran()
148     {
149         return(init_rawtran);
150     }
151     public final int getLockLevel()
152     {
153         return(init_lock_level);
154     }
155
156     public final ContainerHandle getContainer()
157     {
158         return(container);
159     }
160
161     public final int getOpenMode()
162     {
163         return(init_openmode);
164     }
165     
166     public final BTree getConglomerate()
167     {
168         return(init_conglomerate);
169     }
170
171     public final boolean getHold()
172     {
173         return(init_hold);
174     }
175     public final BTreeLockingPolicy getLockingPolicy()
176     {
177         return(init_btree_locking_policy);
178     }
179     public final void setLockingPolicy(BTreeLockingPolicy policy)
180     {
181         init_btree_locking_policy = policy;
182     }
183
184
185     public final boolean isClosed()
186     {
187         return(container == null);
188     }
189
190     public final OpenConglomerateScratchSpace getRuntimeMem()
191     {
192         return(runtime_mem);
193     }
194
195     /**************************************************************************
196      * Public Methods of RowCountable class:
197      **************************************************************************
198      */

199
200     /**
201      * Get the total estimated number of rows in the container.
202      * <p>
203      * The number is a rough estimate and may be grossly off. In general
204      * the server will cache the row count and then occasionally write
205      * the count unlogged to a backing store. If the system happens to
206      * shutdown before the store gets a chance to update the row count it
207      * may wander from reality.
208      * <p>
209      * This call is currently only supported on Heap conglomerates, it
210      * will throw an exception if called on btree conglomerates.
211      *
212      * @return The total estimated number of rows in the conglomerate.
213      *
214      * @exception StandardException Standard exception policy.
215      **/

216     public long getEstimatedRowCount()
217         throws StandardException
218     {
219         if (container == null)
220             reopen();
221
222         // Don't return 0 rows (return 1 instead), as this often leads the
223
// optimizer to produce plans which don't use indexes because of the 0
224
// row edge case.
225
//
226
// Eventually the plan is recompiled when rows are added, but we
227
// have seen multiple customer cases of deadlocks and timeouts
228
// because of these 0 row based plans.
229
long row_count =
230             this.container.getEstimatedRowCount(/* unused flag */ 0);
231
232         return(row_count == 0 ? 1 : row_count);
233     }
234
235     /**
236      * Set the total estimated number of rows in the container.
237      * <p>
238      * Often, after a scan, the client of RawStore has a much better estimate
239      * of the number of rows in the container than what store has. For
240      * instance if we implement some sort of update statistics command, or
241      * just after a create index a complete scan will have been done of the
242      * table. In this case this interface allows the client to set the
243      * estimated row count for the container, and store will use that number
244      * for all future references.
245      * <p>
246      * This call is currently only supported on Heap conglomerates, it
247      * will throw an exception if called on btree conglomerates.
248      *
249      * @param count the estimated number of rows in the container.
250      *
251      * @exception StandardException Standard exception policy.
252      **/

253     public void setEstimatedRowCount(long count)
254         throws StandardException
255     {
256         if (container == null)
257             reopen();
258
259         this.container.setEstimatedRowCount(count, /* unused flag */ 0);
260     }
261
262
263     /**************************************************************************
264      * Public Methods of ConglomerateController interface:
265      **************************************************************************
266      */

267
268     /**
269      * Check consistency of a btree.
270      * <p>
271      * Read in root and check consistency of entire tree. Currently raises
272      * sanity check errors.
273      * <p>
274      * RESOLVE (mikem) if this is to be supported in non-sanity servers what
275      * should it do?
276      *
277      * @exception StandardException Standard exception policy.
278      **/

279     public void checkConsistency()
280         throws StandardException
281     {
282         ControlRow root = null;
283
284         try
285         {
286             if (this.container == null)
287             {
288                 throw(StandardException.newException(
289                         SQLState.BTREE_IS_CLOSED, new Long JavaDoc(err_containerid)));
290             }
291
292             if (SanityManager.DEBUG)
293                 SanityManager.ASSERT(this.init_conglomerate.format_ids != null);
294
295             root = ControlRow.Get(this, BTree.ROOTPAGEID);
296
297             int actualpages = root.checkConsistency(this, null, true);
298
299             // RESOLVE (mikem) - anything useful to assert about number of pages
300
// in the tree?
301
}
302         finally
303         {
304             if (root != null)
305                 root.release();
306         }
307     }
308
309     /**************************************************************************
310      * Public Methods of ScanController interface:
311      **************************************************************************
312      */

313
314     /**
315      * is the open btree table locked?
316      **/

317     public boolean isTableLocked()
318     {
319         return(init_lock_level == TransactionController.MODE_TABLE);
320     }
321
322
323     /*
324     ** Methods of OpenBTree
325     */

326
327     /**
328     Initialize the open conglomerate.
329
330     If container is null, open the container, otherwise use the container
331     passed in.
332
333     @exception StandardException standard exception policy.
334     **/

335     /**
336      * Initialize the open conglomerate.
337      * <p>
338      * If container is null, open the container, otherwise use the container
339      * passed in. The container is always opened with no locking, it is up
340      * to the caller to make the appropriate container locking call.
341      * <p>
342      *
343      * @param open_user_scans The user transaction which opened this btree.
344      * @param xact_manager The current transaction, usually the same as
345      * "open_user_scans", but in the case of split it
346      * is the internal xact nested below the user xact.
347      * @param input_container The open container holding the index, if it is
348      * already open, else null which will mean this
349      * routine will open it.
350      * @param rawtran The current raw store transaction.
351      * @param open_mode The opening mode for the ContainerHandle.
352      * @param conglomerate Readonly description of the conglomerate.
353      * @param undo Logical undo object to associate with all updates
354      * done on this open btree.
355      *
356      *
357      * @exception StandardException Standard exception policy.
358      **/

359     public void init(
360     TransactionManager open_user_scans,
361     TransactionManager xact_manager,
362     ContainerHandle input_container,
363     Transaction rawtran,
364     boolean hold,
365     int open_mode,
366     int lock_level,
367     BTreeLockingPolicy btree_locking_policy,
368     BTree conglomerate,
369     LogicalUndo undo,
370     DynamicCompiledOpenConglomInfo dynamic_info)
371         throws StandardException
372     {
373         // If the b-tree is already open, close it.
374
if (this.container != null)
375         {
376             if (SanityManager.DEBUG)
377                 SanityManager.ASSERT(false, "why is the container open?");
378             close();
379         }
380         err_containerid = conglomerate.id.getContainerId();
381
382         // Locking policy to pass back to concrete implementation lock calls
383
this.init_btree_locking_policy = btree_locking_policy;
384
385         // if the conglomerate is temporary, open with IS_KEPT set.
386
// RESOLVE(mikem): track 1825
387
// don't want to open temp cantainer with IS_KEPT always.
388
if (conglomerate.isTemporary())
389             open_mode |= ContainerHandle.MODE_TEMP_IS_KEPT;
390
391         // now open the container if it wasn't already opened by the client.
392
// No locks will be requested by raw store on this open.
393
if (input_container == null)
394         {
395             // Open the container.
396
this.container =
397                 rawtran.openContainer(
398                     conglomerate.id,
399                     (LockingPolicy) null /* get no locks on btree */,
400                     open_mode);
401         }
402         else
403         {
404             // Use the open container passed in.
405
this.container = input_container;
406
407             // RESOLVE (sku) - ContainerHandle should have an interface to
408
// verify that it is opened with open_mode
409
}
410
411         if (this.container == null)
412         {
413             throw StandardException.newException(
414                     SQLState.BTREE_CONTAINER_NOT_FOUND,
415                     new Long JavaDoc(err_containerid));
416         }
417
418         // Remember the conglomerate so its properties can be found.
419
init_conglomerate = conglomerate;
420
421         // Remember the transaction manager so commit() can be called
422
init_xact_manager = xact_manager;
423
424         init_rawtran = rawtran;
425
426         init_openmode = open_mode;
427
428         // Isolation level of this btree.
429
init_lock_level = lock_level;
430
431         init_dynamic_info = dynamic_info;
432
433         init_hold = hold;
434
435
436         // Remember the transaction manager so saveScanPositions() can be called
437
this.init_open_user_scans = open_user_scans;
438
439         // Logical undo class to pass to raw store, on inserts/deletes.
440
this.btree_undo = undo;
441
442         // either use passed in "compiled" runtime scratch space, or create
443
// new space.
444
this.runtime_mem =
445             (dynamic_info != null ?
446              ((OpenConglomerateScratchSpace) dynamic_info) :
447              new OpenConglomerateScratchSpace(conglomerate.format_ids));
448
449     }
450
451     /**
452      * Open the container after it has been closed previously.
453      * <p>
454      * Open the container, obtaining necessary locks. Most work is actually
455      * done by RawStore.openContainer(). Will only reopen() if the container
456      * is not already open.
457      *
458      * @exception StandardException Standard exception policy.
459      **/

460     public ContainerHandle reopen()
461         throws StandardException
462     {
463         // reget transaction from context manager, in the case of XA
464
// transaction this may have changed.
465
//
466
/* TODO - XA transactions my change the current transaction on the
467          * context stack. Will want to something like:
468          *
469          * init_rawtran = context_manager.getcurrenttransaction()
470          */

471
472         // If the b-tree is already open, close it.
473

474         /*
475         if (this.container != null)
476         {
477             close();
478         }
479         */

480
481         if (SanityManager.DEBUG)
482         {
483             SanityManager.ASSERT(init_xact_manager != null);
484             SanityManager.ASSERT(init_xact_manager.getRawStoreXact() != null);
485             SanityManager.ASSERT(init_conglomerate != null);
486         }
487      
488         if (container == null)
489         {
490             // Open the container.
491
this.container =
492                 init_xact_manager.getRawStoreXact().openContainer(
493                     init_conglomerate.id,
494                     (LockingPolicy) null /* get no locks on btree */,
495                     init_openmode);
496         }
497
498         return(this.container);
499     }
500
501     /**
502     Close the open conglomerate.
503     **/

504     public void close()
505         throws StandardException
506     {
507         if (container != null)
508             container.close();
509         container = null;
510     }
511
512     /**
513     Check if all the
514     columns are Indexable and Storable. Eventually this routine could
515     check whether all the types were right also.
516
517     @exception StandardException Standard Exception Policy.
518     **/

519     void isIndexableRowConsistent(DataValueDescriptor[] row)
520         throws StandardException
521     {
522         if (SanityManager.DEBUG)
523         {
524             DataValueDescriptor[] template =
525                 this.init_conglomerate.createTemplate();
526
527             // RESOLVE - could just compare format id's rather than allocate
528
// objects.
529

530             for (int i = 0; i < row.length; i++)
531             {
532                 // RESOLVE (mikem) - use format id's for more efficient test.
533
if (!row[i].getClass().equals(template[i].getClass()))
534                 {
535                     SanityManager.THROWASSERT(
536                         "type of inserted column[" + i + "] = " +
537                         row[i].getClass().getName() +
538                         "type of template column[" + i + "] = " +
539                         template[i].getClass().getName());
540                 }
541             }
542         }
543     }
544
545     /**
546      * Return the container handle.
547      * <p>
548      * @return The open container handle of the btree.
549      **/

550     public ContainerHandle getContainerHandle()
551     {
552         return(container);
553     }
554     
555     /**
556      * get height of the tree.
557      * <p>
558      * Read in root and return the height (number of levels) of the tree.
559      * The level of a tree is 0 in the leaf and increases by 1 for each
560      * level of the tree as you go up the tree.
561      *
562      * @exception StandardException Standard exception policy.
563      **/

564     public int getHeight()
565         throws StandardException
566     {
567         // container.checkConsistency();
568

569         ControlRow root = null;
570
571         try
572         {
573             root = ControlRow.Get(this, BTree.ROOTPAGEID);
574
575             int height = root.getLevel() + 1;
576
577             return(height);
578         }
579         finally
580         {
581             if (root != null)
582                 root.release();
583         }
584     }
585
586     public RecordHandle makeRecordHandle(
587     long page_number,
588     int rec_id)
589         throws StandardException
590     {
591         return(
592             container.makeRecordHandle(
593                 page_number, rec_id));
594     }
595
596     /**
597      * Dump information about tree into the log.
598      * <p>
599      * Traverse the tree dumping info about tree into the log.
600      *
601      * @exception StandardException Standard exception policy.
602      **/

603     public void debugConglomerate()
604         throws StandardException
605     {
606         // container.checkConsistency();
607

608         ControlRow root = null;
609
610         try
611         {
612             if (SanityManager.DEBUG)
613             {
614                 SanityManager.DEBUG_PRINT(
615                     "p_tree", "BTREE Dump: containerId " + container.getId());
616                 SanityManager.DEBUG_PRINT(
617                     "p_tree", "BTREE Dump: btree " + this.init_conglomerate);
618             }
619
620             root = ControlRow.Get(this, BTree.ROOTPAGEID);
621             root.printTree(this);
622         }
623         finally
624         {
625             if (root != null)
626                 root.release();
627         }
628     }
629
630     /**
631      * Testing infrastructure to cause unusual paths through the code.
632      * <p>
633      * Through the use of debug flags allow test code to cause otherwise
634      * hard to cause paths through the code.
635      * <p>
636      *
637      * @return whether the latch has been released by this routine.
638      *
639      * @exception StandardException Standard exception policy.
640      **/

641     public static boolean test_errors(
642     OpenBTree open_btree,
643     String JavaDoc debug_string,
644     boolean release_scan_lock,
645     BTreeLockingPolicy btree_locking_policy,
646     LeafControlRow leaf,
647     boolean input_latch_released)
648         throws StandardException
649     {
650         boolean latch_released = input_latch_released;
651
652         // special test to see if latch release code works
653
if (SanityManager.DEBUG)
654         {
655             String JavaDoc debug_lost_latch = debug_string + "1";
656
657             if (SanityManager.DEBUG_ON(debug_lost_latch))
658             {
659                 // Simulate a lost latch because of a wait for a lock.
660
if (!latch_released)
661                 {
662                     if (release_scan_lock)
663                     {
664                         btree_locking_policy.unlockScan(
665                             leaf.page.getPageNumber());
666                     }
667                     leaf.release();
668
669                     latch_released = true;
670                     SanityManager.DEBUG_PRINT(
671                         debug_lost_latch, debug_lost_latch);
672                     SanityManager.DEBUG_CLEAR(debug_lost_latch);
673                 }
674             }
675
676             String JavaDoc debug_deadlock = debug_string + "2";
677
678             if (SanityManager.DEBUG_ON(debug_deadlock))
679             {
680                 SanityManager.DEBUG_PRINT(debug_deadlock, debug_deadlock);
681                 SanityManager.DEBUG_CLEAR(debug_deadlock);
682
683                 // Simulate a deadlock error.
684
StandardException se =
685                     StandardException.newException(
686                         SQLState.DEADLOCK, "fake deadlock", "fake victim");
687
688                 se.setReport(StandardException.REPORT_ALWAYS);
689                 throw se;
690             }
691         }
692
693         return(latch_released);
694     }
695
696     public SpaceInfo getSpaceInfo()
697         throws StandardException
698     {
699         return container.getSpaceInfo();
700     }
701
702     // return column Sort order information
703
public boolean[] getColumnSortOrderInfo()
704         throws StandardException
705     {
706         return init_conglomerate.ascDescInfo;
707     }
708 }
709
Popular Tags