KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*
2
3    Derby - Class org.apache.derby.impl.store.access.btree.BTree
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
25 import org.apache.derby.iapi.reference.SQLState;
26
27 import org.apache.derby.iapi.services.io.ArrayInputStream;
28 import org.apache.derby.iapi.services.io.FormatableBitSet;
29
30 import org.apache.derby.iapi.services.monitor.Monitor;
31 import org.apache.derby.iapi.services.sanity.SanityManager;
32
33 import org.apache.derby.iapi.services.io.FormatIdUtil;
34 import org.apache.derby.iapi.services.io.Storable;
35
36 import org.apache.derby.iapi.services.stream.InfoStreams;
37
38
39 import org.apache.derby.iapi.error.StandardException;
40 import org.apache.derby.iapi.store.access.conglomerate.Conglomerate;
41 import org.apache.derby.iapi.store.access.conglomerate.ScanManager;
42 import org.apache.derby.iapi.store.access.conglomerate.TransactionManager;
43 import org.apache.derby.iapi.store.access.ConglomerateController;
44 import org.apache.derby.iapi.store.access.DynamicCompiledOpenConglomInfo;
45 import org.apache.derby.iapi.store.access.Qualifier;
46 import org.apache.derby.iapi.store.access.RowLocationRetRowSource;
47 import org.apache.derby.iapi.store.access.RowUtil;
48 import org.apache.derby.iapi.store.access.ScanController;
49 import org.apache.derby.iapi.store.access.StaticCompiledOpenConglomInfo;
50 import org.apache.derby.iapi.store.access.TransactionController;
51
52 import org.apache.derby.iapi.store.raw.LockingPolicy;
53 import org.apache.derby.iapi.store.raw.Page;
54 import org.apache.derby.iapi.store.raw.RawStoreFactory;
55 import org.apache.derby.iapi.store.raw.RecordHandle;
56 import org.apache.derby.iapi.store.raw.ContainerHandle;
57 import org.apache.derby.iapi.store.raw.Transaction;
58 import org.apache.derby.iapi.store.raw.ContainerKey;
59
60 import org.apache.derby.iapi.types.DataValueDescriptor;
61
62 import org.apache.derby.iapi.types.RowLocation;
63
64 import org.apache.derby.impl.store.access.conglomerate.ConglomerateUtil;
65 import org.apache.derby.impl.store.access.conglomerate.GenericConglomerate;
66 import org.apache.derby.impl.store.access.conglomerate.OpenConglomerateScratchSpace;
67 import org.apache.derby.impl.store.access.conglomerate.TemplateRow;
68
69
70 import java.io.IOException JavaDoc;
71 import java.io.ObjectOutput JavaDoc;
72 import java.io.ObjectInput JavaDoc;
73
74 import java.util.Properties JavaDoc;
75
76
77 /**
78
79   A b-tree object corresponds to an instance of a b-tree conglomerate. It
80   contains the static information about a conglomerate which is built at
81   create conglomerate time.
82   <p>
83   This generic implementation is expected to be extended by the concreate
84   implementations.
85   <P>
86   The fields are set when the conglomerate is created and never changed
87   thereafter. When alter table is supported then it will change under the
88   control of a table level lock.
89   <p>
90   They have package scope because they're read by the scans and controllers.
91   <p>
92   A table of all conglomerates in the system is maintained by the accessmanager.
93   A cache of conglomerates is maintained in the accessmanager, and references
94   to the read only objects are handed out. A copy of the Conglomerate
95   object is kept in the control row of the root page, so that during logical
96   undo this information can be read without needing to access the possibly
97   corrupt table maintained by the access manager.
98 **/
99
100 public abstract class BTree extends GenericConglomerate
101 {
102     /**************************************************************************
103      * Public Constants of BTree class:
104      **************************************************************************
105      */
106
107     /**
108      * The page number of the root page is always at the fixed page number:
109      * ROOTPAGEID. This means that given an open container, during logical
110      * undo one can always find the root page and look up the conglomerate
111      * information.
112      **/
113     public static final long ROOTPAGEID = ContainerHandle.FIRST_PAGE_NUMBER;
114
115     /**
116     Property name for the maximum number of rows to place in a btree page (leaf
117     or branch). Equal to 'derby.access.btreeMaxRowPerPage'. Used by tests
118     and debugging to exactly control split points, and to make it easier to test
119     tall trees without needing lots of data.
120     */
121     public static final String JavaDoc PROPERTY_MAX_ROWS_PER_PAGE_PARAMETER =
122         (SanityManager.DEBUG ? "derby.access.btreeMaxRowPerPage" : null);
123
124     /* properties of a btree see create(). */
125     public static final String JavaDoc PROPERTY_ALLOWDUPLICATES = "allowDuplicates";
126     public static final String JavaDoc PROPERTY_NKEYFIELDS = "nKeyFields";
127     public static final String JavaDoc PROPERTY_NUNIQUECOLUMNS = "nUniqueColumns";
128     public static final String JavaDoc PROPERTY_PARENTLINKS = "maintainParentLinks";
129
130
131
132     /**************************************************************************
133      * Protected Fields of BTree class:
134      **************************************************************************
135      */
136
137     /**
138     The id of the container in which this b-tree is stored.
139     **/
140     protected ContainerKey id;
141
142     /**
143     The number of key fields.
144     **/
145     protected int nKeyFields;
146
147     /**
148     The number of uniqueness columns. These are the columns that
149     are considered for the purpose of detecting duplicate keys and rows.
150     **/
151     int nUniqueColumns;
152
153     /**
154     Whether the index allows duplicates or not.
155     **/
156     boolean allowDuplicates;
157
158     /**
159     Whether the parent should maintain links from child pages to their parent.
160     These links are only used for consistency checking purposes. They improve
161     consistency checking at the cost of run-time efficiency.
162     **/
163     boolean maintainParentLinks;
164
165     /**
166     Maximum rows per page to place on a btree leaf or nonleaf page. Used
167     by testing to finely control split points. Only changed for debugging
168     purposes.
169
170     RESOLVE (mikem) - this should not be static. Need to design a way in
171     debugging mode to get btree created with a persistent "maxRowsPerPage".
172     This hack makes all btrees get created with the "last" maxRowsPerPage
173     value set.
174     **/
175     static int maxRowsPerPage = Integer.MAX_VALUE;
176
177     /**
178     Format id of the conglomerate.
179     **/
180     protected int conglom_format_id;
181
182     /**
183     The array of format id's, one for each column in the template.
184     **/
185     int[] format_ids;
186
187     //columns sorting order information
188 // true - Ascending Order ; false -Descending Order
189 protected boolean[] ascDescInfo;
190
191     /*
192     ** Private Methods of BTree.
193     */
194
195     /*
196     ** Public Methods of BTree.
197     */
198
199
200     /**************************************************************************
201      * Abstract Protected locking methods of BTree:
202      * getBtreeLockingPolicy
203      * lockScan
204      * unlockScan
205      * lockPreviousRow
206      * lockRowOnPage
207      * lockRow
208      * lockTable
209      **************************************************************************
210      */
211
212     /**
213      * Create a new btree locking policy from scratch.
214      *
215      * @exception StandardException Standard exception policy.
216      **/
217     abstract protected BTreeLockingPolicy getBtreeLockingPolicy(
218     Transaction rawtran,
219     int lock_level,
220     int mode,
221     int isolation_level,
222     ConglomerateController base_cc,
223     OpenBTree open_btree)
224         throws StandardException;
225
226     /**
227      * Lock the base table.
228      * <p>
229      * Assumes that segment of the base container is the same as the segment
230      * of the btree segment.
231      * <p>
232      * RESOLVE - we really want to get the lock without opening the container.
233      * raw store will be providing this.
234      *
235      * @param xact_manager Transaction to associate the lock with.
236      *
237      * @exception StandardException Standard exception policy.
238      **/
239     abstract public ConglomerateController lockTable(
240     TransactionManager xact_manager,
241     int open_mode,
242     int lock_level,
243     int isolation_level)
244         throws StandardException;
245
246
247     /**************************************************************************
248      * Private/Protected methods of BTree:
249      **************************************************************************
250      */
251
252
253     /**
254      * Create a branch row template for this conglomerate.
255      * <p>
256      * Reads the format id's of each of the columns and manufactures object of
257      * the given type for each. It then uses these "empty" objects to create
258      * a template row. The object passed in is then added to the last column
259      * of the row.
260      *
261      * @return The new template.
262      *
263      * @exception StandardException Standard exception policy.
264      **/
265     final DataValueDescriptor[] createBranchTemplate(
266     DataValueDescriptor page_ptr)
267         throws StandardException
268     {
269         return(TemplateRow.newBranchRow(format_ids, page_ptr));
270     }
271
272
273     /**************************************************************************
274      * Public methods of BTree:
275      **************************************************************************
276      */
277
278     /**
279      * Create a template for this conglomerate.
280      * <p>
281      * Reads the format id's of each of the columns and manufactures object of
282      * the given type for each. It then uses these "empty" objects to create
283      * a template row.
284      * <p>
285      * This method is public so that B2IUndo() can call it.
286      *
287      * @return The new template.
288      *
289      * @exception StandardException Standard exception policy.
290      **/
291     final public DataValueDescriptor[] createTemplate()
292         throws StandardException
293     {
294         if (SanityManager.DEBUG)
295             SanityManager.ASSERT(format_ids != null);
296
297         return(TemplateRow.newRow((FormatableBitSet) null, format_ids));
298     }
299
300     /**
301      * Is this a "unique" index?
302      **/
303     final public boolean isUnique()
304     {
305         return(nKeyFields != nUniqueColumns);
306     }
307
308     /**************************************************************************
309      * Public Methods of Conglomerate Interface:
310      **************************************************************************
311      */
312
313     /**
314      * Add a column to the conglomerate.
315      * <p>
316      * Currently B2I does not support this operation.
317      * input template column.
318      *
319      * @param xact_manager Transaction to associate the lock with.
320      * @param column_id The column number to add this column at.
321      * @param template_column An instance of the column to be added to table.
322      *
323      * @exception StandardException Standard exception policy.
324      **/
325     public void addColumn(
326     TransactionManager xact_manager,
327     int column_id,
328     Storable template_column)
329         throws StandardException
330     {
331         throw StandardException.newException(
332                 SQLState.BTREE_UNIMPLEMENTED_FEATURE);
333     }
334
335     /**
336      * Get the id of the container of the conglomerate.
337      * <p>
338      * Will have to change when a conglomerate could have more than one
339      * container. The ContainerKey is a combination of the container id
340      * and segment id.
341      *
342      * @return The ContainerKey.
343      **/
344     public final ContainerKey getId()
345     {
346         return(id);
347     }
348
349
350     /**
351     Do the generic part of creating a b-tree conglomerate. This method
352     is called from the concrete subclass (which may also read some properties).
353     <p>
354     This method processes all properties which are generic to all BTree's. It
355     creates the container for the btree.
356     <p>
357
358     The following properties are generic to a b-tree conglomerate. :
359
360     <UL>
361     <LI>"allowDuplicates" (boolean). If set to true the table will allow
362     rows which are duplicate in key column's 0 through (nUniqueColumns - 1).
363     Currently only supports "false".
364     This property is optional, defaults to false.
365     <LI>"nKeyFields" (integer) Columns 0 through (nKeyFields - 1) will be
366     included in key of the conglomerate.
367     This implementation requires that "nKeyFields" must be the same as the
368     number of fields in the conglomerate, including the rowLocationColumn.
369     Other implementations may relax this restriction to allow non-key fields
370     in the index.
371     This property is required.
372     <LI>"nUniqueColumns" (integer) Columns 0 through "nUniqueColumns" will be
373     used to check for uniqueness. So for a standard SQL non-unique index
374     implementation set "nUniqueColumns" to the same value as "nKeyFields"; and
375     for a unique index set "nUniqueColumns" to "nKeyFields" - 1 (ie. don't
376     include the rowLocationColumn in the uniqueness check).
377     This property is required.
378     <LI>"maintainParentLinks" (boolean)
379     Whether the b-tree pages maintain the page number of their parent. Only
380     used for consistency checking. It takes a certain amount more effort to
381     maintain these links, but they're really handy for ensuring that the index
382     is consistent.
383     This property is optional, defaults to true.
384     </UL>
385
386     @exception StandardException Thrown by underlying raw store, or thrown by
387     this routine on an invalid containerid.
388     
389     **/
390
391     public void create(
392     Transaction rawtran,
393     int segmentId,
394     long input_containerid,
395     DataValueDescriptor[] template,
396     Properties JavaDoc properties,
397     int conglom_format_id,
398     int tmpFlag
399     )
400         throws StandardException
401     {
402         String JavaDoc result_string;
403
404         if (properties == null)
405         {
406             throw(
407                 StandardException.newException(
408                     SQLState.BTREE_PROPERTY_NOT_FOUND, PROPERTY_NKEYFIELDS));
409         }
410
411         // Check input arguments
412 allowDuplicates = (Boolean.valueOf(
413             properties.getProperty(PROPERTY_ALLOWDUPLICATES, "false"))).booleanValue();
414
415         result_string = properties.getProperty(PROPERTY_NKEYFIELDS);
416         if (result_string == null)
417         {
418             throw(
419                 StandardException.newException(
420                     SQLState.BTREE_PROPERTY_NOT_FOUND, PROPERTY_NKEYFIELDS));
421         }
422         else
423         {
424             nKeyFields = Integer.parseInt(result_string);
425         }
426
427         result_string = properties.getProperty(PROPERTY_NUNIQUECOLUMNS);
428         if (result_string == null)
429         {
430             throw(StandardException.newException(
431                 SQLState.BTREE_PROPERTY_NOT_FOUND, PROPERTY_NUNIQUECOLUMNS));
432         }
433         else
434         {
435             nUniqueColumns = Integer.parseInt(result_string);
436         }
437
438
439         if (SanityManager.DEBUG)
440         {
441             result_string =
442                 properties.getProperty(PROPERTY_MAX_ROWS_PER_PAGE_PARAMETER);
443
444             if (result_string != null)
445             {
446                 maxRowsPerPage = Integer.parseInt(result_string);
447             }
448         }
449
450         maintainParentLinks = (Boolean.valueOf(
451             properties.getProperty(PROPERTY_PARENTLINKS, "true"))).booleanValue();
452
453         // RESOLVE (mikem) - true for now, if we want to support non-key
454 // fields eventually this assert may be wrong.
455 if (SanityManager.DEBUG)
456         {
457             if (template.length != nKeyFields)
458             {
459                 SanityManager.THROWASSERT(
460                     "template.length (" + template.length +
461                     ") expected to equal nKeyFields (" +
462                     nKeyFields + ")");
463             }
464             SanityManager.ASSERT((nUniqueColumns == nKeyFields) ||
465                                  (nUniqueColumns == (nKeyFields - 1)));
466         }
467
468         // get format id's from each column in template and store it in the
469 // conglomerate state.
470 format_ids = ConglomerateUtil.createFormatIds(template);
471
472         // copy the format id of the conglomerate.
473 this.conglom_format_id = conglom_format_id;
474
475         // Create a container for the b-tree with default page size and
476 // fill up pages.
477 properties.put(RawStoreFactory.PAGE_RESERVED_SPACE_PARAMETER, "0");
478         properties.put(RawStoreFactory.MINIMUM_RECORD_SIZE_PARAMETER, "1");
479         properties.put(RawStoreFactory.PAGE_REUSABLE_RECORD_ID, "true");
480
481         long containerid =
482             rawtran.addContainer(
483                 segmentId, input_containerid,
484                 ContainerHandle.MODE_DEFAULT, properties, tmpFlag);
485
486         // Make sure the container was actually created.
487 // Open segment will get cleaned up when transaction is.
488 if (containerid <= 0)
489         {
490             throw(StandardException.newException(
491                     SQLState.BTREE_CANT_CREATE_CONTAINER));
492         }
493
494         if (SanityManager.DEBUG)
495         {
496             if (input_containerid != ContainerHandle.DEFAULT_ASSIGN_ID)
497                 SanityManager.ASSERT(containerid == input_containerid);
498         }
499
500         id = new ContainerKey(segmentId, containerid);
501     }
502
503     /**
504     Drop this btree.
505     This must be done by a concrete implementation.
506     @see Conglomerate#drop
507
508     @exception StandardException Standard exception policy.
509     **/
510     public abstract void drop(TransactionManager xact_manager)
511         throws StandardException;
512
513     /**
514     Load a b-tree. This must be done by a concrete implementation.
515     @see Conglomerate#load
516
517     @exception StandardException Standard exception policy.
518     **/
519     public abstract long load(
520     TransactionManager xact_manager,
521     boolean createConglom,
522     RowLocationRetRowSource rowSource)
523         throws StandardException;
524
525     public long getContainerid()
526     {
527         return(this.id.getContainerId());
528     }
529
530     /**
531      * Return dynamic information about the conglomerate to be dynamically
532      * reused in repeated execution of a statement.
533      * <p>
534      * The dynamic info is a set of variables to be used in a given
535      * ScanController or ConglomerateController. It can only be used in one
536      * controller at a time. It is up to the caller to insure the correct
537      * thread access to this info. The type of info in this is a scratch
538      * template for btree traversal, other scratch variables for qualifier
539      * evaluation, ...
540      * <p>
541      *
542      * @return The dynamic information.
543      *
544      * @param conglomId The identifier of the conglomerate to open.
545      *
546      * @exception StandardException Standard exception policy.
547      **/
548     public DynamicCompiledOpenConglomInfo getDynamicCompiledConglomInfo(
549     long conglomId)
550         throws StandardException
551     {
552         return(new OpenConglomerateScratchSpace(format_ids));
553     }
554
555
556     /**
557      * Is this conglomerate temporary?
558      * <p>
559      *
560      * @return whether conglomerate is temporary or not.
561      **/
562     public boolean isTemporary()
563     {
564         return (id.getSegmentId() == ContainerHandle.TEMPORARY_SEGMENT);
565     }
566
567     /**
568     Open a b-tree controller.
569     This must be done by a concrete implementation.
570     @see Conglomerate#open
571
572     @exception StandardException Standard exception policy.
573     **/
574     public abstract ConglomerateController open(
575     TransactionManager xact_manager,
576     Transaction rawtran,
577     boolean hold,
578     int open_mode,
579     int lock_level,
580     LockingPolicy locking_policy,
581     StaticCompiledOpenConglomInfo static_info,
582     DynamicCompiledOpenConglomInfo dynamic_info)
583         throws StandardException;
584
585
586
587     /**************************************************************************
588      * Public Methods of Storable Interface (via Conglomerate):
589      * This class is responsible for re/storing its own state.
590      **************************************************************************
591      */
592
593
594     /**
595     Return whether the value is null or not.
596     The containerid being zero is what determines nullness; subclasses
597     are not expected to override this method.
598     @see org.apache.derby.iapi.services.io.Storable#isNull
599     **/
600     public boolean isNull()
601     {
602         return id == null;
603     }
604
605     /**
606     Restore the in-memory representation to the null value.
607     The containerid being zero is what determines nullness; subclasses
608     are not expected to override this method.
609
610     @see org.apache.derby.iapi.services.io.Storable#restoreToNull
611     **/
612     public void restoreToNull()
613     {
614         id = null;
615     }
616
617     /**
618     Restore the in-memory representation from the stream.
619
620     @exception ClassNotFoundException Thrown if the stored representation is
621     serialized and a class named in the stream could not be found.
622
623     @exception IOException thrown by readObject()
624
625     
626     @see java.io.Externalizable#readExternal
627     */
628     public void readExternal(ObjectInput JavaDoc in)
629         throws IOException JavaDoc, ClassNotFoundException JavaDoc
630     {
631         // read in the conglomerate format id.
632 conglom_format_id = FormatIdUtil.readFormatIdInteger(in);
633
634         // XXX (nat) need to improve error handling
635 long containerid = in.readLong();
636         int segmentid = in.readInt();
637         nKeyFields = in.readInt();
638         nUniqueColumns = in.readInt();
639         allowDuplicates = in.readBoolean();
640         maintainParentLinks = in.readBoolean();
641
642         // read in the array of format id's
643 format_ids = ConglomerateUtil.readFormatIdArray(this.nKeyFields, in);
644
645         id = new ContainerKey(segmentid, containerid);
646     }
647
648     public void readExternalFromArray(ArrayInputStream in)
649         throws IOException JavaDoc, ClassNotFoundException JavaDoc
650     {
651         // read in the conglomerate format id.
652 conglom_format_id = FormatIdUtil.readFormatIdInteger(in);
653
654         // XXX (nat) need to improve error handling
655 long containerid = in.readLong();
656         int segmentid = in.readInt();
657         nKeyFields = in.readInt();
658         nUniqueColumns = in.readInt();
659         allowDuplicates = in.readBoolean();
660         maintainParentLinks = in.readBoolean();
661
662         // read in the array of format id's
663 format_ids = ConglomerateUtil.readFormatIdArray(this.nKeyFields, in);
664
665         id = new ContainerKey(segmentid, containerid);
666     }
667
668     
669     /**
670     Store the stored representation of the column value in the stream.
671     It might be easier to simply store the properties - which would certainly
672     make upgrading easier.
673
674     @exception IOException thrown by writeObject()
675
676     */
677     public void writeExternal(ObjectOutput JavaDoc out)
678         throws IOException JavaDoc
679     {
680         FormatIdUtil.writeFormatIdInteger(out, conglom_format_id);
681
682         out.writeLong(id.getContainerId());
683         out.writeInt((int) id.getSegmentId());
684         out.writeInt((nKeyFields));
685         out.writeInt((nUniqueColumns));
686         out.writeBoolean((allowDuplicates));
687         out.writeBoolean((maintainParentLinks));
688
689         ConglomerateUtil.writeFormatIdArray(format_ids, out);
690     }
691
692     /**************************************************************************
693      * Public toString() Method:
694      **************************************************************************
695      */
696
697     public String JavaDoc toString()
698     {
699         if (SanityManager.DEBUG)
700         {
701             return ("BTREE: containerid = " +
702                      (this.id == null ? "null" : this.id.toString()) +
703                      ";nKeyFields = " + nKeyFields +
704                      ";nUniqueColumns = " + nUniqueColumns +
705                      ";allowDuplicates = " + allowDuplicates);
706         }
707         else
708         {
709             return(super.toString());
710         }
711     }
712 }
713
Popular Tags