KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*
2
3    Derby - Class org.apache.derby.impl.store.access.btree.LeafControlRow
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.reference.SQLState;
25 import org.apache.derby.iapi.services.sanity.SanityManager;
26 import org.apache.derby.iapi.services.io.FormatIdUtil;
27 import org.apache.derby.iapi.services.io.StoredFormatIds;
28 import org.apache.derby.iapi.services.io.TypedFormat;
29 import org.apache.derby.iapi.error.StandardException;
30
31 import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;
32
33 import org.apache.derby.iapi.store.access.AccessFactoryGlobals;
34 import org.apache.derby.iapi.store.access.ConglomerateController;
35 import org.apache.derby.iapi.store.access.Qualifier;
36 import org.apache.derby.iapi.store.access.RowUtil;
37 import org.apache.derby.iapi.store.access.ScanController;
38
39 import org.apache.derby.iapi.store.raw.ContainerHandle;
40 import org.apache.derby.iapi.store.raw.FetchDescriptor;
41 import org.apache.derby.iapi.store.raw.Page;
42 import org.apache.derby.iapi.store.raw.RecordHandle;
43 import org.apache.derby.iapi.store.raw.Transaction;
44
45 import org.apache.derby.iapi.types.DataValueDescriptor;
46
47 import java.io.PrintStream JavaDoc;
48 import org.apache.derby.iapi.services.io.FormatableBitSet;
49
50 /**
51  * @format_id ACCESS_BTREE_LEAFCONTROLROW_V1_ID
52  *
53  * @purpose Btree pages all have a control row at the front of every page. To
54  * determine the type of row, read the first column which is a format
55  * id and it tells what kind of control row it is.
56  *
57  * @upgrade This format was made obsolete in the kimono release.
58  *
59  * @disk_layout
60  * column 1 - control row type : StorableFormatId
61  * column 2 - left sibling page number : SQLLongint
62  * column 3 - right sibling page number: SQLLongint
63  * column 4 - parent page number : SQLLongint
64  * column 5 - level number (0 is leaf) : SQLLongint
65  * column 6 - isRoot : SQLLongint
66  * column 7 - Conglomerate object : null unless it is root else
67  * a Conglomerate object, matching
68  * that of current table.
69  * Currently this field
70  * is only used by logical undo and
71  * the type of object is inferred by
72  * the logical undo code.
73  **/
74
75 public class LeafControlRow extends ControlRow
76 {
77     /*
78     ** Constructors of BranchControlRow
79     */
80
81     /**
82      * No arg constructor.
83      * <p>
84      * Public no arg constructor is for the monitor to call for format
85      * id implemenation, it should not be called for any other reason.
86      **/
87     public LeafControlRow()
88     {
89     }
90
91     /**
92      * Constructs a leaf-page control row, for a newly allocated leaf page.
93      *
94      * @param btree The open btree to allocate this page from.
95      * @param page The newly allocated page where the control row will
96      * be inserted.
97      * @param parent The parent of the leaf page. Set to null for root.
98      * RESOLVE (mikem) - set to null otherwise?
99      * @param isRoot Is this page the root of the tree?
100      *
101      * @exception StandardException Standard exception policy.
102      */
103     LeafControlRow(
104     OpenBTree btree,
105     Page page,
106     ControlRow parent,
107     boolean isRoot)
108             throws StandardException
109     {
110         // All leaf pages are at level 0.
111 super(btree, page, 0, parent, isRoot);
112     }
113
114     /* Private/Protected methods of This class: */
115
116     /**
117      * Allocate a new leaf page to the conglomerate.
118      *
119      * @param btree The open conglomerate from which to get the leaf from
120      * @param parent The parent page of the newly allocated page, null if
121      * allocating root page.
122      *
123      * @exception StandardException Standard exception policy.
124      */
125     private static LeafControlRow Allocate(
126     OpenBTree btree,
127     ControlRow parent)
128         throws StandardException
129     {
130         Page page = btree.container.addPage();
131
132         // Create a control row for the new page.
133 LeafControlRow control_row =
134             new LeafControlRow(btree, page, parent, false);
135
136         // Insert the control row on the page, in the first slot on the page.
137 // This operation is only done as part of a new tree or split, which
138 // which both will be undone physically so no logical undo record is
139 // needed.
140 byte insertFlag = Page.INSERT_INITIAL;
141         insertFlag |= Page.INSERT_DEFAULT;
142         RecordHandle rh =
143             page.insertAtSlot(Page.FIRST_SLOT_NUMBER,
144                 control_row.getRow(),
145                 (FormatableBitSet) null,
146                 (LogicalUndo) null, insertFlag,
147                 AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD);
148
149         if (SanityManager.DEBUG)
150         {
151             RecordHandle rh2 = null;
152
153             rh2 = page.fetchFromSlot(
154                     (RecordHandle) null, page.FIRST_SLOT_NUMBER,
155                     new DataValueDescriptor[0], (FetchDescriptor) null, true);
156
157             SanityManager.ASSERT(rh.getId() == rh2.getId() &&
158                                  rh.getPageNumber() == rh2.getPageNumber());
159         }
160
161         // Page is returned latched.
162 return(control_row);
163     }
164
165     /**
166      * Return the number of non-deleted rows from slot 1 through "startslot"
167      * <p>
168      * Return the number of non-deleted rows that exist on the page starting
169      * at slot one through "startslot".
170      * <p>
171      * RESOLVE (mikem) - is the expense of this routine worth it, it is only
172      * used for costing. Could an estimate from the nonDeletedRecordCount()
173      * be used instead?
174      *
175      * @return The requested non_deleted_row_count.
176      *
177      * @param startslot Count non deleted row up to and including this slot.
178      *
179      * @exception StandardException Standard exception policy.
180      **/
181     private float get_left_nondeleted_rowcnt(
182     int startslot)
183         throws StandardException
184     {
185         int non_deleted_row_count = 0;
186
187         for (int slot = 1; slot <= startslot; slot++)
188         {
189             if (!this.page.isDeletedAtSlot(slot))
190             {
191                 non_deleted_row_count++;
192             }
193         }
194         return(non_deleted_row_count);
195     }
196
197
198     /* Public Methods of LeafControlRow class: */
199
200     /**
201      * Perform page specific initialization.
202      * <p>
203      **/
204     protected final void ControlRowInit()
205     {
206     }
207
208     /**
209      * Initialize conglomerate with one page, to be a 1 page btree.
210      *
211      * Given a conglomerate which already has one page allocated to it,
212      * initialize the page to be a leaf-root page with no entries. Allocate
213      * the control row and store it on the page.
214      *
215      * @param open_btree The open btree to initialize (container is open).
216      *
217      * @exception StandardException Standard exception policy.
218      */
219     public static void initEmptyBtree(
220     OpenBTree open_btree)
221         throws StandardException
222     {
223         Page page =
224             open_btree.container.getPage(ContainerHandle.FIRST_PAGE_NUMBER);
225
226         // create a leaf control row for root page of a single page index //
227 LeafControlRow control_row =
228             new LeafControlRow(open_btree, page, null, true);
229
230         byte insertFlag = Page.INSERT_INITIAL;
231         insertFlag |= Page.INSERT_DEFAULT;
232         RecordHandle rh =
233             page.insertAtSlot(
234                 Page.FIRST_SLOT_NUMBER,
235                 control_row.getRow(),
236                 (FormatableBitSet) null,
237                 (LogicalUndo) null, insertFlag,
238                 AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD);
239
240         if (SanityManager.DEBUG)
241         {
242             RecordHandle rh2 = null;
243
244             rh2 = page.fetchFromSlot(
245                     (RecordHandle) null,
246                     Page.FIRST_SLOT_NUMBER,
247                     new DataValueDescriptor[0], (FetchDescriptor) null, true);
248
249             SanityManager.ASSERT(rh.getId() == rh2.getId() &&
250                                  rh.getPageNumber() == rh2.getPageNumber());
251         }
252
253         if (SanityManager.DEBUG)
254         {
255             if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck"))
256             {
257                 control_row.checkConsistency(
258                     open_btree, (ControlRow) null, true);
259             }
260         }
261
262         page.unlatch();
263
264         return;
265     }
266
267     /*
268     ** Non - Debug/consistency check Methods of ControlRow:
269     */
270
271
272     /**
273      * Get the number of columns in the control row.
274      * <p>
275      * Control rows all share the first columns as defined by this class and
276      * then add columns to the end of the control row. For instance a branch
277      * control row add a child page pointer field.
278      * <p>
279      *
280      * @return The total number of columns in the control row.
281      **/
282     protected final int getNumberOfControlRowColumns()
283     {
284         return(this.CR_NCOLUMNS);
285     }
286
287     /**
288      * Is the current page the leftmost leaf of tree?
289      * <p>
290      *
291      * @return true if the current page is the leftmost leaf of the tree,
292      * else return false.
293      *
294      * @exception StandardException Standard exception policy.
295      **/
296     public boolean isLeftmostLeaf()
297         throws StandardException
298     {
299         return(getleftSiblingPageNumber() ==
300                ContainerHandle.INVALID_PAGE_NUMBER);
301     }
302
303     /**
304      * Is the current page the rightmost leaf of tree?
305      * <p>
306      *
307      * @return true if the current page is the rightmost leaf of the tree,
308      * else return false.
309      *
310      * @exception StandardException Standard exception policy.
311      **/
312     public boolean isRightmostLeaf()
313         throws StandardException
314     {
315         return(getrightSiblingPageNumber() ==
316                ContainerHandle.INVALID_PAGE_NUMBER);
317     }
318
319
320     /**
321      ** Perform a search of this leaf page, ultimately returning the latched
322      ** leaf page and row slot after which the given key belongs.
323      ** The slot is returned in the result structure. If the key
324      ** exists on the page, the result.exact will be true. Otherwise,
325      ** result.exact will be false, and the row slot returned will be
326      ** the one immediately preceding the position at which the key
327      ** belongs.
328      *
329      * @exception StandardException Standard exception policy.
330      **/
331     public ControlRow search(
332         SearchParameters sp)
333             throws StandardException
334     {
335         searchForEntry(sp);
336
337         if (sp.searchForOptimizer)
338         {
339             // Update left_fraction to be used to estimate the number of
340 // rows left of the current search location.
341
342             // after the code below startslot will be the slot that is one
343 // before the first slot to be returned by the scan positioning
344 // for this key, including GT/GE positioning. This is exactly
345 // what the LeafControlRow.positionAtStartForForwardScan() does,
346 // to position for the start of a scan.
347
348             int startslot = sp.resultSlot;
349
350             if (sp.resultExact)
351             {
352                 // we found exactly the row we are looking for.
353
354                 if (SanityManager.DEBUG)
355                     SanityManager.ASSERT(sp.resultSlot > 0);
356
357                 // RESOLVE (mikem) - add in a search operator argument so that
358 // below can be if (op == ScanController.GE)
359
360                 if (sp.partial_key_match_op ==
361                         SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH)
362                 {
363                     // This means the scan was positioned for GE rather than GT
364 startslot--;
365                 }
366             }
367
368             // non_deleted_left_row is the number of actual rows left of the
369 // first row to be returned by a scan positioned as requested.
370 // The 0th slot is a control row which is not counted.
371 float non_deleted_left_rows = get_left_nondeleted_rowcnt(startslot);
372
373             int non_deleted_row_count = this.page.nonDeletedRecordCount();
374
375             // System.out.println(
376 // "\n\t non_deleted_row_count = " + non_deleted_row_count +
377 // "\n\t non_deleted_left_rows = " + non_deleted_left_rows +
378 // "\n\t startslot = " + startslot);
379
380             if (this.getIsRoot())
381             {
382                 sp.current_fraction = 1;
383                 sp.left_fraction = 0;
384             }
385
386             // calculate the fraction of rows in the table which are left of
387 // the current slot in the search. After the search is completed
388 // (sp.left_fraction * number of rows), is the estimated number
389 // of rows to the left of the current row.
390
391             if (non_deleted_row_count > 1)
392                 sp.left_fraction +=
393                     (sp.current_fraction) *
394                     (non_deleted_left_rows / (non_deleted_row_count - 1));
395
396             // no-one really uses current fraction after leaf is through with
397 // it. Set it to help diagnose algorithm.
398 if (non_deleted_row_count > 1)
399                 sp.current_fraction =
400                     (sp.current_fraction) *
401                     (((float) 1) / (non_deleted_row_count - 1));
402         }
403
404         return(this);
405     }
406     
407     /**
408      * Search and return the left most leaf page.
409      * <p>
410      * Perform a recursive search, ultimately returning the
411      * leftmost leaf page which is the first leaf page in the
412      * leaf sibling chain. (This method might better be called
413      * getFirstLeafPage()).
414      *
415      * @return The leftmost leaf page.
416      *
417      * @param btree The open btree to associate latches/locks with.
418      *
419      * @exception StandardException Standard exception policy.
420      **/
421     protected ControlRow searchLeft(OpenBTree btree)
422         throws StandardException
423     {
424         return(this);
425     }
426
427     /**
428      * Search and return the right most leaf page.
429      * <p>
430      * Perform a recursive search, ultimately returning the
431      * rightmost leaf page which is the last leaf page in the
432      * leaf sibling chain. (This method might better be called
433      * getLastLeafPage()).
434      *
435      * @return The rightmost leaf page.
436      *
437      * @param btree The open btree to associate latches/locks with.
438      *
439      * @exception StandardException Standard exception policy.
440      **/
441     protected ControlRow searchRight(OpenBTree btree)
442         throws StandardException
443     {
444         return(this);
445     }
446
447
448     /**
449      ** Perform a recursive shrink operation for the key.
450      ** If this method returns true, the caller should
451      ** remove the corresponding entry for the page.
452      ** This routine is not guaranteed to successfully
453      ** shrink anything. The page lead to by the key might
454      ** turn out not to be empty by the time shrink gets
455      ** there, and shrinks will give up if there is a deadlock.
456      ** <P>
457      ** The receiver page must be latched on entry and is
458      ** returned unlatched.
459      *
460      * @exception StandardException Standard exception policy.
461      **/
462     protected boolean shrinkFor(
463     OpenBTree btree,
464     DataValueDescriptor[] key)
465         throws StandardException
466     {
467         boolean shrink_me = false;
468
469         try
470         {
471             // If this page is empty (ie. only has a control row), and it's not
472 // the root page, unlink it. An empty btree consists of
473 // simply an empty leaf-root page.
474
475             // RESOLVE (mikem) - may want this routine to try to purge
476 // committed delete rows here?
477
478             if ((this.page.recordCount() == 1) && !getIsRoot())
479             {
480                  // See if we can unlink this page (might not be able to because
481 // unlinking can cause deadlocks). A successful unlink
482 // unlatches the page.
483 shrink_me = unlink(btree);
484             }
485         }
486         finally
487         {
488             if (!shrink_me)
489                 this.release();
490         }
491
492         return(shrink_me);
493     }
494
495
496     /**
497      * Perform a top down split pass making room for the the key in "row".
498      * <p>
499      * Perform a split such that a subsequent call to insert
500      * given the argument index row will likely find room for it. Since
501      * latches are released the client must code for the case where another
502      * user has grabbed the space made available by the split pass and be
503      * ready to do another split.
504      * <p>
505      * On entry, the parent is either null or latched, and the
506      * current page is latched. On exit, all pages will have been
507      * unlatched. If the parent is null, then this page is a root
508      * leaf page.
509      *
510      * @return page number of the newly allocated leaf page created by split.
511      *
512      * @param open_btree The open btree to associate latches with.
513      * @param template A scratch area to use while searching for split pass.
514      * @param parent_page The parent page of the current page in the split pass.
515      * starts at null for root.
516      * @param splitrow The key to make room for during the split pass.
517      * @param flag A flag used to direct where point of split should be
518      * chosen.
519      *
520      * @exception StandardException Standard exception policy.
521      **/
522     protected long splitFor(
523     OpenBTree open_btree,
524     DataValueDescriptor[] template,
525     BranchControlRow parent_page,
526     DataValueDescriptor[] splitrow,
527     int flag)
528         throws StandardException
529     {
530         long current_leaf_pageno = this.page.getPageNumber();
531
532         if (SanityManager.DEBUG)
533         {
534             if (parent_page == null && ( ! this.getIsRoot()))
535                 SanityManager.THROWASSERT(
536                     this + " splitFor null parent and non-root");
537         }
538
539         // See if this page has space.
540 if ((this.page.recordCount() - 1 <
541                 open_btree.getConglomerate().maxRowsPerPage) &&
542             (this.page.spaceForInsert(splitrow, (FormatableBitSet) null,
543                 AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD)))
544         {
545             // The splitFor() operation is complete, commit the work done
546 // before releasing the latches.
547 open_btree.getXactMgr().commit();
548              
549             if (parent_page != null)
550                  parent_page.release();
551
552             this.release();
553
554             return(current_leaf_pageno);
555         }
556
557         // RESOLVE (mikem) - for rows bigger than pages this assert may
558 // trigger until we have long rows.
559 if (SanityManager.DEBUG)
560             SanityManager.ASSERT(this.page.recordCount() > 1);
561
562         // Track.LeafSplit++;
563
564         if (this.getIsRoot())
565         {
566             // Track.LeafSplitRoot++;
567
568             growRoot(open_btree, template, this);
569
570          
571             // At this point, this page has been unlatched. So code below this
572 // point must not access this object's fields.
573
574             ControlRow new_root = ControlRow.Get(open_btree, BTree.ROOTPAGEID);
575
576             return(
577                 new_root.splitFor(open_btree, template, null, splitrow, flag));
578         }
579
580         // At this point we know that this page has to be split and
581 // that it isn't a root page.
582
583         int splitpoint = (this.page.recordCount() - 1) / 2 + 1;
584
585         if ((flag & ControlRow.SPLIT_FLAG_FIRST_ON_PAGE) != 0)
586         {
587             // move all the row to the new page
588 splitpoint = 1;
589         }
590         else if ((flag & ControlRow.SPLIT_FLAG_LAST_ON_PAGE) != 0)
591         {
592             // This is not optimal as we would rather move no rows to the
593 // next page, but what should we use as a discriminator?
594 splitpoint = this.page.recordCount() - 1;
595         }
596
597         if (SanityManager.DEBUG)
598         {
599             if (splitpoint <= 0)
600                 SanityManager.THROWASSERT(this + " yikes! splitpoint of 0!");
601         }
602
603         // Save away current split point leaf row, and build a branch row
604 // based on it.
605 DataValueDescriptor[] split_leaf_row =
606             open_btree.getConglomerate().createTemplate();
607
608         this.page.fetchFromSlot(
609             (RecordHandle) null, splitpoint, split_leaf_row,
610             (FetchDescriptor) null, true);
611
612         // Create the branch row to insert onto the parent page. For now
613 // use a fake page number because we don't know the real page
614 // number until the allocate is done, but want to delay the
615 // allocate until we know the insert will succeed.
616 BranchRow branchrow = BranchRow.createBranchRowFromOldLeafRow(
617             split_leaf_row, BranchRow.DUMMY_PAGE_NUMBER);
618
619
620         // At this point we have guaranteed there is space in the parent
621 // page for splitrow, but it could be the case that the new
622 // "branchrow" does not fit on the parent page.
623 if (!parent_page.page.spaceForInsert(
624                 branchrow.getRow(), (FormatableBitSet) null,
625                 AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD))
626         {
627             // There is no room on the parent page to complete a split at
628 // the current level, so restart the split at top with the
629 // branchrow that did not fit. On return from this routine
630 // there is no way to know the state of the tree, so the
631 // current split pass recursion must end.
632 return(
633                 ((BranchControlRow) parent_page).restartSplitFor(
634                     open_btree, template, parent_page, this,
635                     branchrow.getRow(), splitrow, flag));
636
637         }
638         // Before moving the rows on the page, while having the latch on the
639 // page, notify btree scans that the rows on this page may be moving
640 // onto another page.
641 //
642 // RESOLVE (mikem) - need to pass conlgomid.
643 // RESOLVE (mikem) - some optimization later, we only need to notify
644 // the scans which are positioned on moving rows.
645 if (SanityManager.DEBUG)
646             SanityManager.ASSERT(open_btree.init_open_user_scans != null);
647
648         open_btree.init_open_user_scans.saveScanPositions(
649                 open_btree.getConglomerate(), this.page);
650
651         // Get exclusive RECORD_ID_PROTECTION_HANDLE lock to make sure that
652 // we wait for scans in other transactions to move off of this page
653 // before we split.
654
655         if (!open_btree.getLockingPolicy().lockScan(
656                 this, parent_page, true /* for update */,
657                 ConglomerateController.LOCK_UPD))
658         {
659             // we had to give up latches on this and parent_page to get the
660 // split lock. Redo the whole split pass as we have lost our
661 // latches. Just returning is ok, as the caller can not assume
662 // that split has succeeded in making space. Note that at this
663 // point in the split no write work has been done in the current
664 // internal transaction, so giving up here is fairly cheap.
665
666             // RESOLVE RLL PERFORMANCE - we could keep a stack of visited
667 // pages so as to not have to redo the complete search.
668 return(current_leaf_pageno);
669         }
670
671         // Create a new leaf page under the parent.
672 LeafControlRow newleaf =
673             LeafControlRow.Allocate(open_btree, parent_page);
674
675         // Now that we know the page number of the new child page update
676 // the branch row to be inserted with the correct value.
677 branchrow.setPageNumber(newleaf.page.getPageNumber());
678
679         // Test fail after allocation
680 if (SanityManager.DEBUG)
681         {
682             if (SanityManager.DEBUG_ON("leaf_split_abort1"))
683             {
684                 throw StandardException.newException(
685                         SQLState.BTREE_ABORT_THROUGH_TRACE);
686             }
687         }
688
689         // Link it to the right of the current page.
690 newleaf.linkRight(open_btree, this);
691
692
693         // Copy the index rows (from the splitpoint to the end of the page)
694 // from the old page to the new leaf, do not
695 // copy the control row. This routine will purge all the copied rows
696 // and maintain the deleted status of the moved rows.
697 int num_rows_to_move = this.page.recordCount() - splitpoint;
698
699         if (SanityManager.DEBUG)
700             SanityManager.ASSERT(num_rows_to_move >= 0);
701
702         if (num_rows_to_move != 0)
703         {
704             this.page.copyAndPurge(
705                 newleaf.page, splitpoint, num_rows_to_move, 1);
706         }
707
708         // Test fail after new page has been updated.
709 if (SanityManager.DEBUG)
710         {
711             if (SanityManager.DEBUG_ON("leaf_split_abort2"))
712             {
713                 throw StandardException.newException(
714                         SQLState.BTREE_ABORT_THROUGH_TRACE);
715             }
716         }
717
718         // Test fail after new page has been updated.
719 if (SanityManager.DEBUG)
720         {
721             if (SanityManager.DEBUG_ON("leaf_split_abort3"))
722             {
723                 throw StandardException.newException(
724                         SQLState.BTREE_ABORT_THROUGH_TRACE);
725             }
726         }
727
728         // Find spot to insert branch row, and insert it.
729
730
731         BranchRow branch_template =
732             BranchRow.createEmptyTemplate(open_btree.getConglomerate());
733         SearchParameters sp =
734             new SearchParameters(
735                 branchrow.getRow(),
736                 SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH,
737                 branch_template.getRow(),
738                 open_btree, false);
739
740         parent_page.searchForEntry(sp);
741
742         // There must be space on the parent to insert the row!
743 if (SanityManager.DEBUG)
744         {
745             SanityManager.ASSERT(
746                 parent_page.page.spaceForInsert(
747                     branchrow.getRow(), (FormatableBitSet) null,
748                     AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD));
749         }
750
751         byte insertFlag = Page.INSERT_INITIAL;
752         insertFlag |= Page.INSERT_DEFAULT;
753         insertFlag |= Page.INSERT_UNDO_WITH_PURGE;
754         if (parent_page.page.insertAtSlot(
755             sp.resultSlot + 1,
756             branchrow.getRow(),
757             (FormatableBitSet) null,
758             (LogicalUndo)null,
759             insertFlag,
760             AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD) == null) {
761
762             throw StandardException.newException(
763                     SQLState.BTREE_NO_SPACE_FOR_KEY);
764         }
765
766         // branchrow is only valid while split_leaf_row remains unchanged.
767 branchrow = null;
768
769         // RESOLVE (mikem) - this case breaks the btree currently - as the
770 // abort of the insert leaves a logical delete in the tree.
771 //
772 // Test fail after parent page has been updated.
773 if (SanityManager.DEBUG)
774         {
775             if (SanityManager.DEBUG_ON("leaf_split_abort4"))
776             {
777                 throw StandardException.newException(
778                         SQLState.BTREE_ABORT_THROUGH_TRACE);
779             }
780         }
781
782         if (SanityManager.DEBUG)
783         {
784             if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck"))
785             {
786                 this.checkConsistency(open_btree, parent_page, false);
787                 newleaf.checkConsistency(open_btree, parent_page, false);
788                 parent_page.checkConsistency(open_btree, null, false);
789             }
790         }
791
792         // At this point a unit of work in the split down the tree has
793 // been performed in an internal transaction. This work must
794 // be committed before any latches are released.
795 open_btree.getXactMgr().commit();
796
797         parent_page.release();
798         this.release(); // XXX (nat) Not good form to unlatch self.
799
800         long new_leaf_pageno = newleaf.page.getPageNumber();
801         newleaf.release();
802
803         // Because we are at the leaf level and have completed the split
804 // there is no more work, no latches should be held, and control
805 // is returned up the recursive stack, to the insert causing the
806 // split. Because latches are released, the inserter must recheck
807 // that there is now space available as some other thread of control
808 // could get in before he latches the page again.
809 return(new_leaf_pageno);
810     }
811
812     /**
813      ** Grow a new root page from a leaf page. Slightly
814      ** tricky because we want to retain page 0 as the root.
815      ** <P>
816      ** On entry, the current leaf root page is expected
817      ** to be latched. On exit, all latches will have been
818      ** released.
819      ** <P>
820      ** The caller cannot not assume success. If we have to release latches
821      ** this routine just returns and assumes the caller will retry the
822      ** grow root if necessary.
823      **/
824     private static void growRoot(
825     OpenBTree open_btree,
826     DataValueDescriptor[] template,
827     LeafControlRow leafroot)
828         throws StandardException
829     {
830         BranchControlRow branchroot = null;
831         LeafControlRow newleaf = null;
832
833
834         // Before moving the rows on the page, while having the latch on the
835 // page, notify btree scans that the rows on this page may be moving
836 // onto another page.
837 //
838 open_btree.init_open_user_scans.saveScanPositions(
839                 open_btree.getConglomerate(), leafroot.page);
840
841         // Get exclusive RECORD_ID_PROTECTION_HANDLE lock to make sure that
842 // we wait for scans in other transactions to move off of this page
843 // before we grow root. If we don't wait, scanners in other
844 // transactions may be positioned on the leaf page which we are
845 // about to make into a branch page.
846
847         if (!open_btree.getLockingPolicy().lockScan(
848                 leafroot, (ControlRow) null,
849                 true /* for update */,
850                 ConglomerateController.LOCK_UPD))
851         {
852             // We had to give up latches on leafroot to get the
853 // split lock. Redo the whole split pass as we have lost our
854 // latches - which may mean that the root has grown when we gave
855 // up the latch. Just returning is ok, as the caller can not assume
856 // that grow root has succeeded in making space. Note that at this
857 // point in the split no write work has been done in the current
858 // internal transaction, so giving up here is fairly cheap.
859
860             return;
861         }
862
863         // Allocate a new leaf page under the existing leaf root.
864
865         newleaf = LeafControlRow.Allocate(open_btree, leafroot);
866
867         // Test fail after allocation
868 if (SanityManager.DEBUG)
869         {
870             if (SanityManager.DEBUG_ON("leaf_split_growRoot1"))
871             {
872                 throw StandardException.newException(
873                         SQLState.BTREE_ABORT_THROUGH_TRACE);
874             }
875         }
876
877         // Copy all the index rows from the root to the new leaf, do not
878 // copy the control row. This routine will purge all the copied
879 // rows and maintain the deleted status of the moved rows.
880
881         if (SanityManager.DEBUG)
882             SanityManager.ASSERT((leafroot.page.recordCount() - 1) > 0);
883         leafroot.page.copyAndPurge(
884             newleaf.page, 1, leafroot.page.recordCount() - 1, 1);
885
886         // Test fail after row copy
887 if (SanityManager.DEBUG)
888         {
889             if (SanityManager.DEBUG_ON("leaf_split_growRoot2"))
890             {
891                 throw StandardException.newException(
892                         SQLState.BTREE_ABORT_THROUGH_TRACE);
893             }
894         }
895
896         // Test fail after purge
897 if (SanityManager.DEBUG)
898         {
899             if (SanityManager.DEBUG_ON("leaf_split_growRoot3"))
900             {
901                 // Make sure tree is very trashed and logical recovery will
902 // not work.
903 leafroot.setLevel(42);
904                 leafroot.setParent(42);
905                 throw StandardException.newException(
906                         SQLState.BTREE_ABORT_THROUGH_TRACE);
907             }
908         }
909
910         // Put a branch control row on the root page, making the new leaf
911 // the left child. All leaf splits result in level-1 branch pages.
912 // This will be a branch-root page.
913
914         // Construction of the BranchControlRow will set it as the aux
915 // object for the page, this in turn invalidates the previous aux
916 // object which is leafroot. Thus leafroot must not be used once
917 // the constructor returns.
918
919         branchroot = new BranchControlRow(
920             open_btree, leafroot.page, 1, null, true,
921             newleaf.page.getPageNumber());
922         leafroot = null;
923
924         // Replace the old leaf root control row with the new branch root
925 // control row.
926 branchroot.page.updateAtSlot(
927             0, branchroot.getRow(), (FormatableBitSet) null);
928
929         // Test fail after purge
930 if (SanityManager.DEBUG)
931         {
932             if (SanityManager.DEBUG_ON("leaf_split_growRoot4"))
933             {
934                 throw StandardException.newException(
935                         SQLState.BTREE_ABORT_THROUGH_TRACE);
936             }
937         }
938
939         if (SanityManager.DEBUG)
940         {
941             if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck"))
942             {
943                 newleaf.checkConsistency(open_btree, branchroot, false);
944                 branchroot.checkConsistency(open_btree, null, false);
945             }
946         }
947         
948         // At this point a unit of work in the split down the tree has
949 // been performed in an internal transaction. This work must
950 // be committed before any latches are released.
951 open_btree.getXactMgr().commit();
952
953         // Test fail after commit of split
954 if (SanityManager.DEBUG)
955         {
956             if (SanityManager.DEBUG_ON("leaf_split_growRoot5"))
957             {
958                 throw StandardException.newException(
959                         SQLState.BTREE_ABORT_THROUGH_TRACE);
960             }
961         }
962
963         // The variable 'branchroot' refers to a page that was latched by
964 // leafroot. After a growRoot() from a leaf there will be no pages
965 // latched. It is up to the callers to reget the root page latched
966 // and continue their work.
967 //
968 if (branchroot != null)
969             branchroot.release();
970         if (leafroot != null)
971             leafroot.release();
972         if (newleaf != null)
973             newleaf.release();
974     }
975     
976     /**
977      * Return the left child pointer for the page.
978      * <p>
979      * Leaf pages don't have children, so they override this and return null.
980      *
981      * @return The page which is the leftmost child of this page.
982      *
983      * @param btree The open btree to associate latches/locks with.
984      *
985      * @exception StandardException Standard exception policy.
986      **/
987     protected ControlRow getLeftChild(OpenBTree btree)
988         throws StandardException
989     {
990         return(null);
991     }
992
993     /**
994      * Return the right child pointer for the page.
995      * <p>
996      * Leaf pages don't have children, so they override this and return null.
997      *
998      * @return The page which is the rightmost child of this page.
999      *
1000     * @param btree The open btree to associate latches/locks with.
1001     *
1002     * @exception StandardException Standard exception policy.
1003     **/
1004    protected ControlRow getRightChild(OpenBTree btree)
1005        throws StandardException
1006    {
1007        return(null);
1008    }
1009
1010    /*
1011    ** Debug/consistency check Methods of ControlRow:
1012    */
1013
1014    /**
1015     ** Perform consistency checks on a leaf page.
1016     **
1017     ** Check consistency of the page and its children,
1018     ** returning the number of pages seen, and throwing
1019     ** errors if inconsistencies are found.
1020     ** The checks specific to a leaf page are:
1021     ** <menu>
1022     ** <li> Page is at level 0.
1023     ** <li> Version is a valid leaf page version.
1024     ** <li> Control row has right number of columns for leaf.
1025     ** </menu>
1026     ** This method also performs the consistency checks that
1027     ** are common to both leaf and branch pages.
1028     ** @see ControlRow#checkGeneric
1029     **
1030     ** @exception StandardException Standard exception policy.
1031     **/
1032    public int checkConsistency(
1033    OpenBTree btree,
1034    ControlRow parent,
1035    boolean check_other_pages
1036    )
1037        throws StandardException
1038    {
1039        // Do the consistency checks that are common to all
1040 // types of pages.
1041 checkGeneric(btree, parent, check_other_pages);
1042
1043        // Leaf specific, control row checks
1044 if (SanityManager.DEBUG)
1045        {
1046            SanityManager.ASSERT(this.getLevel() == 0, "leaf not at level 0");
1047
1048            // RESOLVE (mikem) - how to sanity check correct version?
1049 /*
1050            if (this.getVersion() != CURRENT_LEAF_VERSION)
1051                SanityManager.THROWASSERT(
1052                    "Expected leaf version:(" +
1053                    CURRENT_LEAF_VERSION + ") but got (" +
1054                    this.getVersion());
1055            */
1056            SanityManager.ASSERT(
1057                this.page.fetchNumFieldsAtSlot(CR_SLOT) ==
1058                ControlRow.CR_NCOLUMNS);
1059
1060            // The remaining checks are specific to leaf pages.
1061
1062            // Check that every row has at least as many columns
1063 // as the number of key fields in the b-tree.
1064 int numslots = this.page.recordCount();
1065            for (int slot = 1; slot < numslots; slot++)
1066            {
1067                if (this.page.fetchNumFieldsAtSlot(slot) <
1068                     btree.getConglomerate().nKeyFields)
1069                    SanityManager.THROWASSERT(
1070                        "row[" + slot + "]"
1071                            + " has " + this.page.fetchNumFieldsAtSlot(slot)
1072                            + " columns, should have at least" +
1073                            btree.getConglomerate().nKeyFields);
1074                
1075                // RESOLVE - the generic btree code should know nothing about
1076 // the secondaryindex row location column, but put this here for
1077 // now because I can't figure how to get a call out to the
1078 // secondary index code at the page level consistency checking
1079 // level.
1080 }
1081
1082        }
1083
1084        // We checked one page (this one).
1085 return 1;
1086    }
1087
1088    /**
1089     ** Recursively print the tree starting at current node in tree.
1090     ** This is a leaf so return.
1091
1092    @exception StandardException Standard exception policy.
1093     **/
1094    public void printTree(
1095    OpenBTree btree)
1096        throws StandardException
1097    {
1098        if (SanityManager.DEBUG)
1099        {
1100            SanityManager.DEBUG_PRINT("p_tree", this.debugPage(btree));
1101
1102            return;
1103        }
1104    }
1105
1106
1107    /*
1108     * Methods of TypedFormat:
1109     */
1110
1111
1112    /**
1113        Return my format identifier.
1114
1115        @see org.apache.derby.iapi.services.io.TypedFormat#getTypeFormatId
1116    */
1117    public int getTypeFormatId()
1118    {
1119        return StoredFormatIds.ACCESS_BTREE_LEAFCONTROLROW_V1_ID;
1120    }
1121}
1122
Popular Tags