001: /*
002:
003: Derby - Class org.apache.derby.impl.store.access.btree.OpenBTree
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.services.sanity.SanityManager;
025:
026: import org.apache.derby.iapi.error.StandardException;
027:
028: import org.apache.derby.iapi.reference.SQLState;
029:
030: import org.apache.derby.iapi.store.access.conglomerate.Conglomerate;
031: import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;
032: import org.apache.derby.iapi.store.access.conglomerate.TransactionManager;
033: import org.apache.derby.iapi.store.access.ConglomerateController;
034: import org.apache.derby.iapi.store.access.DynamicCompiledOpenConglomInfo;
035: import org.apache.derby.iapi.store.access.Qualifier;
036: import org.apache.derby.iapi.store.access.ScanController;
037: import org.apache.derby.iapi.store.access.TransactionController;
038: import org.apache.derby.iapi.store.access.SpaceInfo;
039: import org.apache.derby.iapi.store.raw.ContainerHandle;
040: import org.apache.derby.iapi.store.raw.LockingPolicy;
041: import org.apache.derby.iapi.store.raw.RecordHandle;
042: import org.apache.derby.iapi.store.raw.Transaction;
043:
044: import org.apache.derby.iapi.types.DataValueDescriptor;
045:
046: import org.apache.derby.iapi.types.RowLocation;
047:
048: import org.apache.derby.impl.store.access.conglomerate.OpenConglomerateScratchSpace;
049:
050: /**
051:
052: An open b-tree contains fields and methods common to scans and controllers.
053: <P>
054: <B>Concurrency Notes<\B>
055: <P>
056: An instance of an open b-tree is owned by a single context. The b-tree code
057: assumes that the context ensures that only one thread at a time is using
058: the open b-tree. The open b-tree itself does not enforce or check this.
059:
060: **/
061:
062: public class OpenBTree {
063: /*
064: ** Fields of OpenBTree
065: */
066:
067: /**
068: * The following group of fields are all basic input parameters which are
069: * provided by the calling code when doing any sort of operation requiring
070: * an open conglomerate (openScan(), open(), openCostController(), ...).
071: * These are just saved values from what was initially input.
072: **/
073: private BTree init_conglomerate;
074:
075: /**
076: The TransactionManager that open'd this btree. In the case of Internal
077: transactions used by split this will be the internal transaction, and
078: init_open_user_scans will be the user transaction that began the internal
079: transaction.
080: **/
081: private TransactionManager init_xact_manager;
082:
083: private Transaction init_rawtran;
084:
085: /**
086: The ContainerHandle mode the container is opened with. Remember this so
087: that if the BTree needs to do SMO with another transaction, it would open
088: the container with the same mode.
089: **/
090: private int init_openmode;
091:
092: /**
093: Table or page locking?
094: **/
095: protected int init_lock_level;
096:
097: private DynamicCompiledOpenConglomInfo init_dynamic_info;
098: private boolean init_hold;
099:
100: /**
101: The Locking Policy to use for for access to this btree.
102: **/
103: private BTreeLockingPolicy init_btree_locking_policy;
104:
105: /**
106: The (open) container which contains the b-tree.
107: **/
108: protected ContainerHandle container;
109:
110: /**
111: The conglomerate containerid for error reporting.
112: **/
113: protected long err_containerid;
114:
115: /**
116: In the case of splits, notify all scans in this transaction to save their
117: current position by key, because the split may move the row they are
118: positioned on. This is done by calling open_user_scans.saveScanPositions().
119: Note that not all OpenBTree's will have a non-null open_user_scans. For
120: instance logical undo of btree operations will get a OpenBTree with a null
121: open_user_scans, this is all right because this operation should never need
122: to call saveScanPositions() (ie. it will never do a split).
123: **/
124: protected TransactionManager init_open_user_scans = null;
125:
126: protected LogicalUndo btree_undo = null;
127:
128: /**
129: * scratch space used for stuff like templates, export rows, ...
130: **/
131: protected OpenConglomerateScratchSpace runtime_mem;
132:
133: /**************************************************************************
134: * Public Accessors of This class:
135: **************************************************************************
136: */
137: public final TransactionManager getXactMgr() {
138: return (init_xact_manager);
139: }
140:
141: public final Transaction getRawTran() {
142: return (init_rawtran);
143: }
144:
145: public final int getLockLevel() {
146: return (init_lock_level);
147: }
148:
149: public final ContainerHandle getContainer() {
150: return (container);
151: }
152:
153: public final int getOpenMode() {
154: return (init_openmode);
155: }
156:
157: public final BTree getConglomerate() {
158: return (init_conglomerate);
159: }
160:
161: public final boolean getHold() {
162: return (init_hold);
163: }
164:
165: public final BTreeLockingPolicy getLockingPolicy() {
166: return (init_btree_locking_policy);
167: }
168:
169: public final void setLockingPolicy(BTreeLockingPolicy policy) {
170: init_btree_locking_policy = policy;
171: }
172:
173: public final boolean isClosed() {
174: return (container == null);
175: }
176:
177: public final OpenConglomerateScratchSpace getRuntimeMem() {
178: return (runtime_mem);
179: }
180:
181: /**************************************************************************
182: * Public Methods of RowCountable class:
183: **************************************************************************
184: */
185:
186: /**
187: * Get the total estimated number of rows in the container.
188: * <p>
189: * The number is a rough estimate and may be grossly off. In general
190: * the server will cache the row count and then occasionally write
191: * the count unlogged to a backing store. If the system happens to
192: * shutdown before the store gets a chance to update the row count it
193: * may wander from reality.
194: * <p>
195: * This call is currently only supported on Heap conglomerates, it
196: * will throw an exception if called on btree conglomerates.
197: *
198: * @return The total estimated number of rows in the conglomerate.
199: *
200: * @exception StandardException Standard exception policy.
201: **/
202: public long getEstimatedRowCount() throws StandardException {
203: if (container == null)
204: reopen();
205:
206: // Don't return 0 rows (return 1 instead), as this often leads the
207: // optimizer to produce plans which don't use indexes because of the 0
208: // row edge case.
209: //
210: // Eventually the plan is recompiled when rows are added, but we
211: // have seen multiple customer cases of deadlocks and timeouts
212: // because of these 0 row based plans.
213: long row_count = this .container
214: .getEstimatedRowCount(/* unused flag */0);
215:
216: return (row_count == 0 ? 1 : row_count);
217: }
218:
219: /**
220: * Set the total estimated number of rows in the container.
221: * <p>
222: * Often, after a scan, the client of RawStore has a much better estimate
223: * of the number of rows in the container than what store has. For
224: * instance if we implement some sort of update statistics command, or
225: * just after a create index a complete scan will have been done of the
226: * table. In this case this interface allows the client to set the
227: * estimated row count for the container, and store will use that number
228: * for all future references.
229: * <p>
230: * This call is currently only supported on Heap conglomerates, it
231: * will throw an exception if called on btree conglomerates.
232: *
233: * @param count the estimated number of rows in the container.
234: *
235: * @exception StandardException Standard exception policy.
236: **/
237: public void setEstimatedRowCount(long count)
238: throws StandardException {
239: if (container == null)
240: reopen();
241:
242: this .container.setEstimatedRowCount(count, /* unused flag */0);
243: }
244:
245: /**************************************************************************
246: * Public Methods of ConglomerateController interface:
247: **************************************************************************
248: */
249:
250: /**
251: * Check consistency of a btree.
252: * <p>
253: * Read in root and check consistency of entire tree. Currently raises
254: * sanity check errors.
255: * <p>
256: * RESOLVE (mikem) if this is to be supported in non-sanity servers what
257: * should it do?
258: *
259: * @exception StandardException Standard exception policy.
260: **/
261: public void checkConsistency() throws StandardException {
262: ControlRow root = null;
263:
264: try {
265: if (this .container == null) {
266: throw (StandardException.newException(
267: SQLState.BTREE_IS_CLOSED, new Long(
268: err_containerid)));
269: }
270:
271: if (SanityManager.DEBUG)
272: SanityManager
273: .ASSERT(this .init_conglomerate.format_ids != null);
274:
275: root = ControlRow.Get(this , BTree.ROOTPAGEID);
276:
277: int actualpages = root.checkConsistency(this , null, true);
278:
279: // RESOLVE (mikem) - anything useful to assert about number of pages
280: // in the tree?
281: } finally {
282: if (root != null)
283: root.release();
284: }
285: }
286:
287: /**************************************************************************
288: * Public Methods of ScanController interface:
289: **************************************************************************
290: */
291:
292: /**
293: * is the open btree table locked?
294: **/
295: public boolean isTableLocked() {
296: return (init_lock_level == TransactionController.MODE_TABLE);
297: }
298:
299: /*
300: ** Methods of OpenBTree
301: */
302:
303: /**
304: Initialize the open conglomerate.
305:
306: If container is null, open the container, otherwise use the container
307: passed in.
308:
309: @exception StandardException standard exception policy.
310: **/
311: /**
312: * Initialize the open conglomerate.
313: * <p>
314: * If container is null, open the container, otherwise use the container
315: * passed in. The container is always opened with no locking, it is up
316: * to the caller to make the appropriate container locking call.
317: * <p>
318: *
319: * @param open_user_scans The user transaction which opened this btree.
320: * @param xact_manager The current transaction, usually the same as
321: * "open_user_scans", but in the case of split it
322: * is the internal xact nested below the user xact.
323: * @param input_container The open container holding the index, if it is
324: * already open, else null which will mean this
325: * routine will open it.
326: * @param rawtran The current raw store transaction.
327: * @param open_mode The opening mode for the ContainerHandle.
328: * @param conglomerate Readonly description of the conglomerate.
329: * @param undo Logical undo object to associate with all updates
330: * done on this open btree.
331: *
332: *
333: * @exception StandardException Standard exception policy.
334: **/
335: public void init(TransactionManager open_user_scans,
336: TransactionManager xact_manager,
337: ContainerHandle input_container, Transaction rawtran,
338: boolean hold, int open_mode, int lock_level,
339: BTreeLockingPolicy btree_locking_policy,
340: BTree conglomerate, LogicalUndo undo,
341: DynamicCompiledOpenConglomInfo dynamic_info)
342: throws StandardException {
343: // If the b-tree is already open, close it.
344: if (this .container != null) {
345: if (SanityManager.DEBUG)
346: SanityManager.ASSERT(false,
347: "why is the container open?");
348: close();
349: }
350: err_containerid = conglomerate.id.getContainerId();
351:
352: // Locking policy to pass back to concrete implementation lock calls
353: this .init_btree_locking_policy = btree_locking_policy;
354:
355: // if the conglomerate is temporary, open with IS_KEPT set.
356: // RESOLVE(mikem): track 1825
357: // don't want to open temp cantainer with IS_KEPT always.
358: if (conglomerate.isTemporary())
359: open_mode |= ContainerHandle.MODE_TEMP_IS_KEPT;
360:
361: // now open the container if it wasn't already opened by the client.
362: // No locks will be requested by raw store on this open.
363: if (input_container == null) {
364: // Open the container.
365: this .container = rawtran.openContainer(conglomerate.id,
366: (LockingPolicy) null /* get no locks on btree */,
367: open_mode);
368: } else {
369: // Use the open container passed in.
370: this .container = input_container;
371:
372: // RESOLVE (sku) - ContainerHandle should have an interface to
373: // verify that it is opened with open_mode
374: }
375:
376: if (this .container == null) {
377: throw StandardException.newException(
378: SQLState.BTREE_CONTAINER_NOT_FOUND, new Long(
379: err_containerid));
380: }
381:
382: // Remember the conglomerate so its properties can be found.
383: init_conglomerate = conglomerate;
384:
385: // Remember the transaction manager so commit() can be called
386: init_xact_manager = xact_manager;
387:
388: init_rawtran = rawtran;
389:
390: init_openmode = open_mode;
391:
392: // Isolation level of this btree.
393: init_lock_level = lock_level;
394:
395: init_dynamic_info = dynamic_info;
396:
397: init_hold = hold;
398:
399: // Remember the transaction manager so saveScanPositions() can be called
400: this .init_open_user_scans = open_user_scans;
401:
402: // Logical undo class to pass to raw store, on inserts/deletes.
403: this .btree_undo = undo;
404:
405: // either use passed in "compiled" runtime scratch space, or create
406: // new space.
407: this .runtime_mem = (dynamic_info != null ? ((OpenConglomerateScratchSpace) dynamic_info)
408: : new OpenConglomerateScratchSpace(
409: conglomerate.format_ids));
410:
411: }
412:
413: /**
414: * Open the container after it has been closed previously.
415: * <p>
416: * Open the container, obtaining necessary locks. Most work is actually
417: * done by RawStore.openContainer(). Will only reopen() if the container
418: * is not already open.
419: *
420: * @exception StandardException Standard exception policy.
421: **/
422: public ContainerHandle reopen() throws StandardException {
423: // reget transaction from context manager, in the case of XA
424: // transaction this may have changed.
425: //
426: /* TODO - XA transactions my change the current transaction on the
427: * context stack. Will want to something like:
428: *
429: * init_rawtran = context_manager.getcurrenttransaction()
430: */
431:
432: // If the b-tree is already open, close it.
433: /*
434: if (this.container != null)
435: {
436: close();
437: }
438: */
439:
440: if (SanityManager.DEBUG) {
441: SanityManager.ASSERT(init_xact_manager != null);
442: SanityManager
443: .ASSERT(init_xact_manager.getRawStoreXact() != null);
444: SanityManager.ASSERT(init_conglomerate != null);
445: }
446:
447: if (container == null) {
448: // Open the container.
449: this .container = init_xact_manager
450: .getRawStoreXact()
451: .openContainer(
452: init_conglomerate.id,
453: (LockingPolicy) null /* get no locks on btree */,
454: init_openmode);
455: }
456:
457: return (this .container);
458: }
459:
460: /**
461: Close the open conglomerate.
462: **/
463: public void close() throws StandardException {
464: if (container != null)
465: container.close();
466: container = null;
467: }
468:
469: /**
470: Check if all the
471: columns are Indexable and Storable. Eventually this routine could
472: check whether all the types were right also.
473:
474: @exception StandardException Standard Exception Policy.
475: **/
476: void isIndexableRowConsistent(DataValueDescriptor[] row)
477: throws StandardException {
478: if (SanityManager.DEBUG) {
479: DataValueDescriptor[] template = this .init_conglomerate
480: .createTemplate();
481:
482: // RESOLVE - could just compare format id's rather than allocate
483: // objects.
484:
485: for (int i = 0; i < row.length; i++) {
486: // RESOLVE (mikem) - use format id's for more efficient test.
487: if (!row[i].getClass().equals(template[i].getClass())) {
488: SanityManager
489: .THROWASSERT("type of inserted column[" + i
490: + "] = "
491: + row[i].getClass().getName()
492: + "type of template column[" + i
493: + "] = "
494: + template[i].getClass().getName());
495: }
496: }
497: }
498: }
499:
500: /**
501: * Return the container handle.
502: * <p>
503: * @return The open container handle of the btree.
504: **/
505: public ContainerHandle getContainerHandle() {
506: return (container);
507: }
508:
509: /**
510: * get height of the tree.
511: * <p>
512: * Read in root and return the height (number of levels) of the tree.
513: * The level of a tree is 0 in the leaf and increases by 1 for each
514: * level of the tree as you go up the tree.
515: *
516: * @exception StandardException Standard exception policy.
517: **/
518: public int getHeight() throws StandardException {
519: // container.checkConsistency();
520:
521: ControlRow root = null;
522:
523: try {
524: root = ControlRow.Get(this , BTree.ROOTPAGEID);
525:
526: int height = root.getLevel() + 1;
527:
528: return (height);
529: } finally {
530: if (root != null)
531: root.release();
532: }
533: }
534:
535: public RecordHandle makeRecordHandle(long page_number, int rec_id)
536: throws StandardException {
537: return (container.makeRecordHandle(page_number, rec_id));
538: }
539:
540: /**
541: * Dump information about tree into the log.
542: * <p>
543: * Traverse the tree dumping info about tree into the log.
544: *
545: * @exception StandardException Standard exception policy.
546: **/
547: public void debugConglomerate() throws StandardException {
548: // container.checkConsistency();
549:
550: ControlRow root = null;
551:
552: try {
553: if (SanityManager.DEBUG) {
554: SanityManager.DEBUG_PRINT("p_tree",
555: "BTREE Dump: containerId " + container.getId());
556: SanityManager.DEBUG_PRINT("p_tree",
557: "BTREE Dump: btree " + this .init_conglomerate);
558: }
559:
560: root = ControlRow.Get(this , BTree.ROOTPAGEID);
561: root.printTree(this );
562: } finally {
563: if (root != null)
564: root.release();
565: }
566: }
567:
568: /**
569: * Testing infrastructure to cause unusual paths through the code.
570: * <p>
571: * Through the use of debug flags allow test code to cause otherwise
572: * hard to cause paths through the code.
573: * <p>
574: *
575: * @return whether the latch has been released by this routine.
576: *
577: * @exception StandardException Standard exception policy.
578: **/
579: public static boolean test_errors(OpenBTree open_btree,
580: String debug_string, boolean release_scan_lock,
581: BTreeLockingPolicy btree_locking_policy,
582: LeafControlRow leaf, boolean input_latch_released)
583: throws StandardException {
584: boolean latch_released = input_latch_released;
585:
586: // special test to see if latch release code works
587: if (SanityManager.DEBUG) {
588: String debug_lost_latch = debug_string + "1";
589:
590: if (SanityManager.DEBUG_ON(debug_lost_latch)) {
591: // Simulate a lost latch because of a wait for a lock.
592: if (!latch_released) {
593: if (release_scan_lock) {
594: btree_locking_policy.unlockScan(leaf.page
595: .getPageNumber());
596: }
597: leaf.release();
598:
599: latch_released = true;
600: SanityManager.DEBUG_PRINT(debug_lost_latch,
601: debug_lost_latch);
602: SanityManager.DEBUG_CLEAR(debug_lost_latch);
603: }
604: }
605:
606: String debug_deadlock = debug_string + "2";
607:
608: if (SanityManager.DEBUG_ON(debug_deadlock)) {
609: SanityManager.DEBUG_PRINT(debug_deadlock,
610: debug_deadlock);
611: SanityManager.DEBUG_CLEAR(debug_deadlock);
612:
613: // Simulate a deadlock error.
614: StandardException se = StandardException.newException(
615: SQLState.DEADLOCK, "fake deadlock",
616: "fake victim");
617:
618: se.setReport(StandardException.REPORT_ALWAYS);
619: throw se;
620: }
621: }
622:
623: return (latch_released);
624: }
625:
626: public SpaceInfo getSpaceInfo() throws StandardException {
627: return container.getSpaceInfo();
628: }
629:
630: // return column Sort order information
631: public boolean[] getColumnSortOrderInfo() throws StandardException {
632: return init_conglomerate.ascDescInfo;
633: }
634: }
|