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  (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  (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                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   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   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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags