001: /*
002:
003: Derby - Class org.apache.derby.impl.store.access.btree.BTree
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.impl.store.access.btree;
023:
024: import org.apache.derby.iapi.reference.SQLState;
025:
026: import org.apache.derby.iapi.services.io.ArrayInputStream;
027: import org.apache.derby.iapi.services.io.FormatableBitSet;
028:
029: import org.apache.derby.iapi.services.monitor.Monitor;
030: import org.apache.derby.iapi.services.sanity.SanityManager;
031:
032: import org.apache.derby.iapi.services.io.FormatIdUtil;
033: import org.apache.derby.iapi.services.io.Storable;
034:
035: import org.apache.derby.iapi.services.stream.InfoStreams;
036:
037: import org.apache.derby.iapi.error.StandardException;
038: import org.apache.derby.iapi.store.access.conglomerate.Conglomerate;
039: import org.apache.derby.iapi.store.access.conglomerate.ScanManager;
040: import org.apache.derby.iapi.store.access.conglomerate.TransactionManager;
041: import org.apache.derby.iapi.store.access.ConglomerateController;
042: import org.apache.derby.iapi.store.access.DynamicCompiledOpenConglomInfo;
043: import org.apache.derby.iapi.store.access.Qualifier;
044: import org.apache.derby.iapi.store.access.RowLocationRetRowSource;
045: import org.apache.derby.iapi.store.access.RowUtil;
046: import org.apache.derby.iapi.store.access.ScanController;
047: import org.apache.derby.iapi.store.access.StaticCompiledOpenConglomInfo;
048: import org.apache.derby.iapi.store.access.TransactionController;
049:
050: import org.apache.derby.iapi.store.raw.LockingPolicy;
051: import org.apache.derby.iapi.store.raw.Page;
052: import org.apache.derby.iapi.store.raw.RawStoreFactory;
053: import org.apache.derby.iapi.store.raw.RecordHandle;
054: import org.apache.derby.iapi.store.raw.ContainerHandle;
055: import org.apache.derby.iapi.store.raw.Transaction;
056: import org.apache.derby.iapi.store.raw.ContainerKey;
057:
058: import org.apache.derby.iapi.types.DataValueDescriptor;
059:
060: import org.apache.derby.iapi.types.RowLocation;
061:
062: import org.apache.derby.impl.store.access.conglomerate.ConglomerateUtil;
063: import org.apache.derby.impl.store.access.conglomerate.GenericConglomerate;
064: import org.apache.derby.impl.store.access.conglomerate.OpenConglomerateScratchSpace;
065: import org.apache.derby.impl.store.access.conglomerate.TemplateRow;
066:
067: import java.io.IOException;
068: import java.io.ObjectOutput;
069: import java.io.ObjectInput;
070:
071: import java.util.Properties;
072:
073: /**
074:
075: A b-tree object corresponds to an instance of a b-tree conglomerate. It
076: contains the static information about a conglomerate which is built at
077: create conglomerate time.
078: <p>
079: This generic implementation is expected to be extended by the concreate
080: implementations.
081: <P>
082: The fields are set when the conglomerate is created and never changed
083: thereafter. When alter table is supported then it will change under the
084: control of a table level lock.
085: <p>
086: They have package scope because they're read by the scans and controllers.
087: <p>
088: A table of all conglomerates in the system is maintained by the accessmanager.
089: A cache of conglomerates is maintained in the accessmanager, and references
090: to the read only objects are handed out. A copy of the Conglomerate
091: object is kept in the control row of the root page, so that during logical
092: undo this information can be read without needing to access the possibly
093: corrupt table maintained by the access manager.
094: **/
095:
096: public abstract class BTree extends GenericConglomerate {
097: /**************************************************************************
098: * Public Constants of BTree class:
099: **************************************************************************
100: */
101:
102: /**
103: * The page number of the root page is always at the fixed page number:
104: * ROOTPAGEID. This means that given an open container, during logical
105: * undo one can always find the root page and look up the conglomerate
106: * information.
107: **/
108: public static final long ROOTPAGEID = ContainerHandle.FIRST_PAGE_NUMBER;
109:
110: /**
111: Property name for the maximum number of rows to place in a btree page (leaf
112: or branch). Equal to 'derby.access.btreeMaxRowPerPage'. Used by tests
113: and debugging to exactly control split points, and to make it easier to test
114: tall trees without needing lots of data.
115: */
116: public static final String PROPERTY_MAX_ROWS_PER_PAGE_PARAMETER = (SanityManager.DEBUG ? "derby.access.btreeMaxRowPerPage"
117: : null);
118:
119: /* properties of a btree see create(). */
120: public static final String PROPERTY_ALLOWDUPLICATES = "allowDuplicates";
121: public static final String PROPERTY_NKEYFIELDS = "nKeyFields";
122: public static final String PROPERTY_NUNIQUECOLUMNS = "nUniqueColumns";
123: public static final String PROPERTY_PARENTLINKS = "maintainParentLinks";
124:
125: /**************************************************************************
126: * Protected Fields of BTree class:
127: **************************************************************************
128: */
129:
130: /**
131: The id of the container in which this b-tree is stored.
132: **/
133: protected ContainerKey id;
134:
135: /**
136: The number of key fields.
137: **/
138: protected int nKeyFields;
139:
140: /**
141: The number of uniqueness columns. These are the columns that
142: are considered for the purpose of detecting duplicate keys and rows.
143: **/
144: int nUniqueColumns;
145:
146: /**
147: Whether the index allows duplicates or not.
148: **/
149: boolean allowDuplicates;
150:
151: /**
152: Whether the parent should maintain links from child pages to their parent.
153: These links are only used for consistency checking purposes. They improve
154: consistency checking at the cost of run-time efficiency.
155: **/
156: boolean maintainParentLinks;
157:
158: /**
159: Maximum rows per page to place on a btree leaf or nonleaf page. Used
160: by testing to finely control split points. Only changed for debugging
161: purposes.
162:
163: RESOLVE (mikem) - this should not be static. Need to design a way in
164: debugging mode to get btree created with a persistent "maxRowsPerPage".
165: This hack makes all btrees get created with the "last" maxRowsPerPage
166: value set.
167: **/
168: static int maxRowsPerPage = Integer.MAX_VALUE;
169:
170: /**
171: Format id of the conglomerate.
172: **/
173: protected int conglom_format_id;
174:
175: /**
176: The array of format id's, one for each column in the template.
177: **/
178: int[] format_ids;
179:
180: //columns sorting order information
181: // true - Ascending Order ; false -Descending Order
182: protected boolean[] ascDescInfo;
183:
184: /*
185: ** Private Methods of BTree.
186: */
187:
188: /*
189: ** Public Methods of BTree.
190: */
191:
192: /**************************************************************************
193: * Abstract Protected locking methods of BTree:
194: * getBtreeLockingPolicy
195: * lockScan
196: * unlockScan
197: * lockPreviousRow
198: * lockRowOnPage
199: * lockRow
200: * lockTable
201: **************************************************************************
202: */
203:
204: /**
205: * Create a new btree locking policy from scratch.
206: *
207: * @exception StandardException Standard exception policy.
208: **/
209: abstract protected BTreeLockingPolicy getBtreeLockingPolicy(
210: Transaction rawtran, int lock_level, int mode,
211: int isolation_level, ConglomerateController base_cc,
212: OpenBTree open_btree) throws StandardException;
213:
214: /**
215: * Lock the base table.
216: * <p>
217: * Assumes that segment of the base container is the same as the segment
218: * of the btree segment.
219: * <p>
220: * RESOLVE - we really want to get the lock without opening the container.
221: * raw store will be providing this.
222: *
223: * @param xact_manager Transaction to associate the lock with.
224: *
225: * @exception StandardException Standard exception policy.
226: **/
227: abstract public ConglomerateController lockTable(
228: TransactionManager xact_manager, int open_mode,
229: int lock_level, int isolation_level)
230: throws StandardException;
231:
232: /**************************************************************************
233: * Private/Protected methods of BTree:
234: **************************************************************************
235: */
236:
237: /**
238: * Create a branch row template for this conglomerate.
239: * <p>
240: * Reads the format id's of each of the columns and manufactures object of
241: * the given type for each. It then uses these "empty" objects to create
242: * a template row. The object passed in is then added to the last column
243: * of the row.
244: *
245: * @return The new template.
246: *
247: * @exception StandardException Standard exception policy.
248: **/
249: final DataValueDescriptor[] createBranchTemplate(
250: DataValueDescriptor page_ptr) throws StandardException {
251: return (TemplateRow.newBranchRow(format_ids, page_ptr));
252: }
253:
254: /**************************************************************************
255: * Public methods of BTree:
256: **************************************************************************
257: */
258:
259: /**
260: * Create a template for this conglomerate.
261: * <p>
262: * Reads the format id's of each of the columns and manufactures object of
263: * the given type for each. It then uses these "empty" objects to create
264: * a template row.
265: * <p>
266: * This method is public so that B2IUndo() can call it.
267: *
268: * @return The new template.
269: *
270: * @exception StandardException Standard exception policy.
271: **/
272: final public DataValueDescriptor[] createTemplate()
273: throws StandardException {
274: if (SanityManager.DEBUG)
275: SanityManager.ASSERT(format_ids != null);
276:
277: return (TemplateRow.newRow((FormatableBitSet) null, format_ids));
278: }
279:
280: /**
281: * Is this a "unique" index?
282: **/
283: final public boolean isUnique() {
284: return (nKeyFields != nUniqueColumns);
285: }
286:
287: /**************************************************************************
288: * Public Methods of Conglomerate Interface:
289: **************************************************************************
290: */
291:
292: /**
293: * Add a column to the conglomerate.
294: * <p>
295: * Currently B2I does not support this operation.
296: * input template column.
297: *
298: * @param xact_manager Transaction to associate the lock with.
299: * @param column_id The column number to add this column at.
300: * @param template_column An instance of the column to be added to table.
301: *
302: * @exception StandardException Standard exception policy.
303: **/
304: public void addColumn(TransactionManager xact_manager,
305: int column_id, Storable template_column)
306: throws StandardException {
307: throw StandardException
308: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE);
309: }
310:
311: /**
312: * Get the id of the container of the conglomerate.
313: * <p>
314: * Will have to change when a conglomerate could have more than one
315: * container. The ContainerKey is a combination of the container id
316: * and segment id.
317: *
318: * @return The ContainerKey.
319: **/
320: public final ContainerKey getId() {
321: return (id);
322: }
323:
324: /**
325: Do the generic part of creating a b-tree conglomerate. This method
326: is called from the concrete subclass (which may also read some properties).
327: <p>
328: This method processes all properties which are generic to all BTree's. It
329: creates the container for the btree.
330: <p>
331:
332: The following properties are generic to a b-tree conglomerate. :
333:
334: <UL>
335: <LI>"allowDuplicates" (boolean). If set to true the table will allow
336: rows which are duplicate in key column's 0 through (nUniqueColumns - 1).
337: Currently only supports "false".
338: This property is optional, defaults to false.
339: <LI>"nKeyFields" (integer) Columns 0 through (nKeyFields - 1) will be
340: included in key of the conglomerate.
341: This implementation requires that "nKeyFields" must be the same as the
342: number of fields in the conglomerate, including the rowLocationColumn.
343: Other implementations may relax this restriction to allow non-key fields
344: in the index.
345: This property is required.
346: <LI>"nUniqueColumns" (integer) Columns 0 through "nUniqueColumns" will be
347: used to check for uniqueness. So for a standard SQL non-unique index
348: implementation set "nUniqueColumns" to the same value as "nKeyFields"; and
349: for a unique index set "nUniqueColumns" to "nKeyFields" - 1 (ie. don't
350: include the rowLocationColumn in the uniqueness check).
351: This property is required.
352: <LI>"maintainParentLinks" (boolean)
353: Whether the b-tree pages maintain the page number of their parent. Only
354: used for consistency checking. It takes a certain amount more effort to
355: maintain these links, but they're really handy for ensuring that the index
356: is consistent.
357: This property is optional, defaults to true.
358: </UL>
359:
360: @exception StandardException Thrown by underlying raw store, or thrown by
361: this routine on an invalid containerid.
362:
363: **/
364:
365: public void create(Transaction rawtran, int segmentId,
366: long input_containerid, DataValueDescriptor[] template,
367: Properties properties, int conglom_format_id, int tmpFlag)
368: throws StandardException {
369: String result_string;
370:
371: if (properties == null) {
372: throw (StandardException.newException(
373: SQLState.BTREE_PROPERTY_NOT_FOUND,
374: PROPERTY_NKEYFIELDS));
375: }
376:
377: // Check input arguments
378: allowDuplicates = (Boolean.valueOf(properties.getProperty(
379: PROPERTY_ALLOWDUPLICATES, "false"))).booleanValue();
380:
381: result_string = properties.getProperty(PROPERTY_NKEYFIELDS);
382: if (result_string == null) {
383: throw (StandardException.newException(
384: SQLState.BTREE_PROPERTY_NOT_FOUND,
385: PROPERTY_NKEYFIELDS));
386: } else {
387: nKeyFields = Integer.parseInt(result_string);
388: }
389:
390: result_string = properties.getProperty(PROPERTY_NUNIQUECOLUMNS);
391: if (result_string == null) {
392: throw (StandardException.newException(
393: SQLState.BTREE_PROPERTY_NOT_FOUND,
394: PROPERTY_NUNIQUECOLUMNS));
395: } else {
396: nUniqueColumns = Integer.parseInt(result_string);
397: }
398:
399: if (SanityManager.DEBUG) {
400: result_string = properties
401: .getProperty(PROPERTY_MAX_ROWS_PER_PAGE_PARAMETER);
402:
403: if (result_string != null) {
404: maxRowsPerPage = Integer.parseInt(result_string);
405: }
406: }
407:
408: maintainParentLinks = (Boolean.valueOf(properties.getProperty(
409: PROPERTY_PARENTLINKS, "true"))).booleanValue();
410:
411: // RESOLVE (mikem) - true for now, if we want to support non-key
412: // fields eventually this assert may be wrong.
413: if (SanityManager.DEBUG) {
414: if (template.length != nKeyFields) {
415: SanityManager.THROWASSERT("template.length ("
416: + template.length
417: + ") expected to equal nKeyFields ("
418: + nKeyFields + ")");
419: }
420: SanityManager.ASSERT((nUniqueColumns == nKeyFields)
421: || (nUniqueColumns == (nKeyFields - 1)));
422: }
423:
424: // get format id's from each column in template and store it in the
425: // conglomerate state.
426: format_ids = ConglomerateUtil.createFormatIds(template);
427:
428: // copy the format id of the conglomerate.
429: this .conglom_format_id = conglom_format_id;
430:
431: // Create a container for the b-tree with default page size and
432: // fill up pages.
433: properties.put(RawStoreFactory.PAGE_RESERVED_SPACE_PARAMETER,
434: "0");
435: properties.put(RawStoreFactory.MINIMUM_RECORD_SIZE_PARAMETER,
436: "1");
437: properties.put(RawStoreFactory.PAGE_REUSABLE_RECORD_ID, "true");
438:
439: long containerid = rawtran.addContainer(segmentId,
440: input_containerid, ContainerHandle.MODE_DEFAULT,
441: properties, tmpFlag);
442:
443: // Make sure the container was actually created.
444: // Open segment will get cleaned up when transaction is.
445: if (containerid <= 0) {
446: throw (StandardException
447: .newException(SQLState.BTREE_CANT_CREATE_CONTAINER));
448: }
449:
450: if (SanityManager.DEBUG) {
451: if (input_containerid != ContainerHandle.DEFAULT_ASSIGN_ID)
452: SanityManager.ASSERT(containerid == input_containerid);
453: }
454:
455: id = new ContainerKey(segmentId, containerid);
456: }
457:
458: /**
459: Drop this btree.
460: This must be done by a concrete implementation.
461: @see Conglomerate#drop
462:
463: @exception StandardException Standard exception policy.
464: **/
465: public abstract void drop(TransactionManager xact_manager)
466: throws StandardException;
467:
468: /**
469: Load a b-tree. This must be done by a concrete implementation.
470: @see Conglomerate#load
471:
472: @exception StandardException Standard exception policy.
473: **/
474: public abstract long load(TransactionManager xact_manager,
475: boolean createConglom, RowLocationRetRowSource rowSource)
476: throws StandardException;
477:
478: public long getContainerid() {
479: return (this .id.getContainerId());
480: }
481:
482: /**
483: * Return dynamic information about the conglomerate to be dynamically
484: * reused in repeated execution of a statement.
485: * <p>
486: * The dynamic info is a set of variables to be used in a given
487: * ScanController or ConglomerateController. It can only be used in one
488: * controller at a time. It is up to the caller to insure the correct
489: * thread access to this info. The type of info in this is a scratch
490: * template for btree traversal, other scratch variables for qualifier
491: * evaluation, ...
492: * <p>
493: *
494: * @return The dynamic information.
495: *
496: * @param conglomId The identifier of the conglomerate to open.
497: *
498: * @exception StandardException Standard exception policy.
499: **/
500: public DynamicCompiledOpenConglomInfo getDynamicCompiledConglomInfo(
501: long conglomId) throws StandardException {
502: return (new OpenConglomerateScratchSpace(format_ids));
503: }
504:
505: /**
506: * Is this conglomerate temporary?
507: * <p>
508: *
509: * @return whether conglomerate is temporary or not.
510: **/
511: public boolean isTemporary() {
512: return (id.getSegmentId() == ContainerHandle.TEMPORARY_SEGMENT);
513: }
514:
515: /**
516: Open a b-tree controller.
517: This must be done by a concrete implementation.
518: @see Conglomerate#open
519:
520: @exception StandardException Standard exception policy.
521: **/
522: public abstract ConglomerateController open(
523: TransactionManager xact_manager, Transaction rawtran,
524: boolean hold, int open_mode, int lock_level,
525: LockingPolicy locking_policy,
526: StaticCompiledOpenConglomInfo static_info,
527: DynamicCompiledOpenConglomInfo dynamic_info)
528: throws StandardException;
529:
530: /**************************************************************************
531: * Public Methods of Storable Interface (via Conglomerate):
532: * This class is responsible for re/storing its own state.
533: **************************************************************************
534: */
535:
536: /**
537: Return whether the value is null or not.
538: The containerid being zero is what determines nullness; subclasses
539: are not expected to override this method.
540: @see org.apache.derby.iapi.services.io.Storable#isNull
541: **/
542: public boolean isNull() {
543: return id == null;
544: }
545:
546: /**
547: Restore the in-memory representation to the null value.
548: The containerid being zero is what determines nullness; subclasses
549: are not expected to override this method.
550:
551: @see org.apache.derby.iapi.services.io.Storable#restoreToNull
552: **/
553: public void restoreToNull() {
554: id = null;
555: }
556:
557: /**
558: Restore the in-memory representation from the stream.
559:
560: @exception ClassNotFoundException Thrown if the stored representation is
561: serialized and a class named in the stream could not be found.
562:
563: @exception IOException thrown by readObject()
564:
565:
566: @see java.io.Externalizable#readExternal
567: */
568: public void readExternal(ObjectInput in) throws IOException,
569: ClassNotFoundException {
570: // read in the conglomerate format id.
571: conglom_format_id = FormatIdUtil.readFormatIdInteger(in);
572:
573: // XXX (nat) need to improve error handling
574: long containerid = in.readLong();
575: int segmentid = in.readInt();
576: nKeyFields = in.readInt();
577: nUniqueColumns = in.readInt();
578: allowDuplicates = in.readBoolean();
579: maintainParentLinks = in.readBoolean();
580:
581: // read in the array of format id's
582: format_ids = ConglomerateUtil.readFormatIdArray(
583: this .nKeyFields, in);
584:
585: id = new ContainerKey(segmentid, containerid);
586: }
587:
588: public void readExternalFromArray(ArrayInputStream in)
589: throws IOException, ClassNotFoundException {
590: // read in the conglomerate format id.
591: conglom_format_id = FormatIdUtil.readFormatIdInteger(in);
592:
593: // XXX (nat) need to improve error handling
594: long containerid = in.readLong();
595: int segmentid = in.readInt();
596: nKeyFields = in.readInt();
597: nUniqueColumns = in.readInt();
598: allowDuplicates = in.readBoolean();
599: maintainParentLinks = in.readBoolean();
600:
601: // read in the array of format id's
602: format_ids = ConglomerateUtil.readFormatIdArray(
603: this .nKeyFields, in);
604:
605: id = new ContainerKey(segmentid, containerid);
606: }
607:
608: /**
609: Store the stored representation of the column value in the stream.
610: It might be easier to simply store the properties - which would certainly
611: make upgrading easier.
612:
613: @exception IOException thrown by writeObject()
614:
615: */
616: public void writeExternal(ObjectOutput out) throws IOException {
617: FormatIdUtil.writeFormatIdInteger(out, conglom_format_id);
618:
619: out.writeLong(id.getContainerId());
620: out.writeInt((int) id.getSegmentId());
621: out.writeInt((nKeyFields));
622: out.writeInt((nUniqueColumns));
623: out.writeBoolean((allowDuplicates));
624: out.writeBoolean((maintainParentLinks));
625:
626: ConglomerateUtil.writeFormatIdArray(format_ids, out);
627: }
628:
629: /**************************************************************************
630: * Public toString() Method:
631: **************************************************************************
632: */
633:
634: public String toString() {
635: if (SanityManager.DEBUG) {
636: return ("BTREE: containerid = "
637: + (this .id == null ? "null" : this .id.toString())
638: + ";nKeyFields = " + nKeyFields
639: + ";nUniqueColumns = " + nUniqueColumns
640: + ";allowDuplicates = " + allowDuplicates);
641: } else {
642: return (super.toString());
643: }
644: }
645: }
|